Bing搜索核心技術BitFunnel原理

2019 年 11 月 20 日
筆記

導語從90年代中期開始，人們普遍認識，對於內容索引來說，文件簽名技術比反向鏈接效果更差。最近幾年必應搜索引擎開發與部署了一套基於位分割的標籤索引。這種索引（也稱BitFunnel）替代了之前的基於反向索引的生產系統。這項轉移背後驅動的因素是反向鏈接需要運轉存儲代價。本篇內容將講述這項演算法上的創新發明，改變傳統上在雲計算框架上被認為無法使用的技術。BitFunnel演算法直接解決四項基礎位分割塊簽名的限制。同時，演算法的映射進入集群提供了避免和其他簽名聯繫的代價。這裡會先展示這些創新產生了比傳統位分割簽名的更顯著的效率提升，然後將會進行BitFunnel與分塊化Elias-Fano索引,MG4J,和Lucene等的對比。本文根據論文《BitFunnel: Revisiting Signatures for Search》和Bing團隊實踐分享影片，對BitFunnel原理進行分析解讀。

問題背景

假設我們一篇非常短的文檔：內容僅僅「big brown dog」這三個單詞，我們可以用固定長度的位向量對這組單詞進行編碼，也稱固定長度的位向量為文檔簽名或者布隆過濾器。簡單樣例這裡採取了十六位長度的位向量來進行操作，當然，在Bing系統上不會用這麼短的位向量，往往使用五千個以上的來進行表示。一開始，位向量全都是空的，因為還沒有進行數據的載入操作。

布隆過濾器初始化會設置哈稀函數的種數，哈稀函數是為了讓文檔單詞對應到位向量的固定位置上。這裡我使用了三種不同的哈稀函數來映射。映射結果如下：

從上圖可知，每個單詞都對應著位向量上面的三個位置上置1，然後我們得到了這份簡易文檔的文檔簽名，假如我們要搜索「cat」單詞在不在這份文檔裡面，我們只需要查詢「cat」單詞經過哈稀函數映射出來的三個位置上是否都為1就可以進行判定了，很明顯，有一個不為1，所以「cat」單詞並不在這份文檔裡面。

當我們搜索"big「單詞時，我們會發現三個位置均置為1，那麼我們可以判定「big」是這份文檔的可能成員。如下圖所示：

細心的你肯定注意到這裡用了可能兩個字，為什麼是可能成員呢？下圖是我們搜索的是「house」單詞的結果：

我們會發現這個單詞的所有映射位置也都是1，但實際上我們知道文檔里並沒有「house」單詞，這個存在的原因是因為有哈稀函數映射碰撞的存在，導致其他的位置也有相對應的1在文檔裡面補充了沒有為1的情況，這也是我們為什麼要用多種哈稀映射函數的原因，能夠降低這種錯誤率。

基於這樣的結構我們，假設我們存儲有十六篇文檔：A－P，依次建立了簽名，那麼有搜索需求：Query文檔（包含多個單詞）進來，通過下列查詢就可以得到可能匹配文檔：

這樣的思路無疑是非常直觀簡單且容易實現的，但是在網路中存儲的那些網頁，基本需要幾千位長度的位向量去表示，如果我們每一篇文檔都這樣去查詢匹配，假設我們有N篇文章，用了P個位的文檔簽名標記，我們的電腦CPU每次處理的位數為64位，那麼查詢一篇文章需要花費的代價就是 N＊（P/64）單位時間。

這樣的代價無疑是非常高昂的，因為現在文章的數量和長度乘積無疑是一個天文數字。一個非常巧妙的辦法就是將這個矩陣反轉過來，行列倒置，那麼我們的存儲由N＊P行列矩陣就變成了P＊N，很顯然，P遠遠小於N。那麼，我們的查詢文檔Query對應的只需要去匹配其中位為1的對應的文檔的行向量即可，過程如下：

從上圖流程可以看出，對應的只需要查詢對應為1的位向量行數的文章的情況就可以了，假設真實中查詢的文檔Query的為1位數是W位，在現實查詢中，W往往是少數幾個單詞去查詢，W遠遠小於P，對應列進行並運算，結果為1則該篇位置可能匹配，這樣查詢速度就大大提升。但是，還有一個問題就是現實中 N 的數量也非常龐大。

那麼這點如何處理呢？這就引進了今天要講的重點演算法：BitFunnel。

BitFunnel發明

等級行

等級行是原始行的簡單壓縮版本，能夠提高過濾速度，但同時也帶來了更高的錯誤率，讓我們看看等級行是怎麼運行的。我們將原始行稱為0-等級行，假設原始行是32位長度，那麼1-等級行就是由0－等級行對等截成兩半進行或運算獲得，那麼長度就降低了一半，更高等級行依此進行計算獲得，如下圖舉例所示：

那麼現在我們怎麼使用我們獲取的等級行呢？假設我們有3行32列需要匹配處理，那麼我們可以考慮將第一行壓縮成2－等級行，第二行壓縮成1－等級行，第三行保持不變。如果我們沒有這樣做，我們需要將3*32＝96位全部放進記憶體進行查詢處理才可以完成。而現在，（8+16+32）＝56位，詳細如下圖所示：

那麼查詢的時候，我們先將得出第一行和第二行的並運算結果，僅兩列需要去與第三行在進行處理，然後平移到第三行另一邊處理，再將第一行移動到第二行的另外一邊，這時候也是兩列均為1出現，然後與第三行處理，再轉移回去處理最後一次即可得出結果，四次處理計算流程如下：

以上這樣的處理我們可以大量地利用中間結果加快計算。

頻率布隆過濾器

傳統的布隆過濾器需要花費超長度的位向量才能做到滿足較低的錯誤率，而BitFunnel則使用頻率布隆過濾器來降低記憶體總量。什麼是頻率布隆過濾器？當我們在布隆過濾器中查詢僅僅查詢一個項目時，假設整個布隆過濾器為1的密度為10%，那麼當我們只使用一個哈稀函數（假設哈稀函數是完全隨機哈稀函數），那麼對應的碰撞率為10％，那麼隨著我們哈稀函數種類的增加，我們可以計算出錯誤率,d為布隆過濾器的概率密度，但這裡我們可以進一步提出新的概念信噪比：

noise是我們經常用的錯誤概率（假陽率: Fasle Positive Rate, FPR），然而很少人去關注信噪比概念。讓我們舉例一些實際查詢項目下的信噪比值：

信噪比給我們的啟示是：假設我們查詢的是"with"單詞，出現的頻次約為50%，如果只有一種哈稀函數，那麼它對應的信噪比分數為(0.5/((1-0.5)*${0.1}^1$)約為10.2，那麼，當「info」單詞，頻率約為10%時，那麼錯誤率與頻率相等下，信噪比下降，隨著頻率的下降，布隆過濾器密度會突出，提高了這些稀少單詞的錯誤率，因此就需要為這些稀少單詞增加更多的哈稀函數從而才能保持與高頻詞一致的信噪比，舉例只是到了「sawmill」單詞，但現實互聯網情況下，更小頻率出現的單詞非常多，往往需要10個以上的哈稀函數才能保持可接受的錯誤率。

就像查詢DNA裡面的特定稀少片段，傳統的布隆過濾器做法是默認設置許多的哈稀函數和佔用大量位數空間才能保障準確率。因此BitFunnel使用 Frequency Conscious Bloom Filter , 不同頻次的單詞使用不同種數的哈稀函數搜索匹配。

那麼等級行在這種應用下怎麼使用從而降低搜尋時間？BitFunnel結合了搜尋單詞的頻率和錯誤率的概念，提出了一種新的處理方案。

處理方案事實上就是用等級行數來關聯我們單詞：假設單詞"with"的反向文檔頻率為0.29，那麼用單條長度的原始行表示即可，「info」的為1，則用單條原始行還有一條1-等級行表示，後面則越稀缺的單詞，其IDF越高，我們就用更多的行來表示其解決方案。你可能會問這些單詞項目處理方案後面是不是存在簡單的模式？然而我們也不知道具體答案，我們過去使用BF演算法來通過確定的信噪比排序處理方案，同時也權衡查詢時間和記憶體總量。最終出現了十億中不同的解決方案，我們只評價了每種方案的IDF值，這一步花費了幾秒鐘，然後配置在系統中。

那麼，讓我們試試搜索一下「treacherous movies」是怎麼進行查詢的：

取出這兩個單詞的配置解決方案，然後將這兩個解決方案組合起來獲得下圖（形狀如漏斗）：

那麼我們就可以簡單直接地看出BitFunnel為什麼能夠這麼快了：

假設行的概率密度為0.1，那麼我們可以迅速前面四行就忽略了95%的列數。

集群間分享

以上的兩種概念（等級行以及 Frequency Conscious Bloom Filter）讓我們節約了大量的記憶體空間以及提高了查詢效率。現實中我們的文本物料在現在互聯網上已經是一個龐大的天文數字，以前還可以在單機上處理，現在已經無法單機處理，我們需要將龐大的矩陣切割出來放到不同的集群上處理，那麼我們怎麼做呢？

假設我們還是一共有十六篇文檔和十六位的表示，那麼矩陣表示為16*16，同時我們反轉得到了十六位＊十六篇，我們可以知道，短文章的文檔裡面為1的個數還是相當少的，屬於稀疏矩陣，會浪費相當大的空間存儲，而長篇的文章裡面1的個數相當高，其對應的錯誤率也很高。在BitFunnel中,集群間按不同文章的長度進行切割分享，下面例子切割成了三部分，實際上會按其他十到十五種不同組。

當按長度分好組後，我們就可以對稀疏部分進行壓縮存儲，密集的文章進行擴充位數存儲，降低錯誤率。

那麼隨之我們跟之前一樣就可以，當我們的查詢文檔Query對應只有三位為1是，我們分別對這三組的對應行求與運算即可得出結果：

這樣的計算方式實際上在90年代的時候就提出來了，但是一直不被認可。為什麼？當時普遍都還是在單個電腦上進行各種演算法操作，那麼在一台機器上又將數據如上圖一樣切割成三部分分別進行處理很明顯代價得不償失。原本只需要進行一遍操作的流程被複雜化了，而且事實上也不僅僅分割成三部分，往往是十幾類。而隨著時代的發展，我們現在擁有了分散式的集群，我們可以將不同的機器處理不同文章長度種類的文檔：

其次還有不同的是記憶體技術的發展，以前我們用每GB的花費金錢來衡量其中的成本是錯誤的方式：

傳統衡量方式上，硬碟獲得存儲1GB的空間只需要0.05美元，而DDR4需要7.44美元，導致了大量企業認為能夠增加存儲就不斷往硬碟上堆積，但這種方式很明顯是錯誤的。

假設公司有存儲數據總量為D，然後服務上需要查詢的文檔總量設置為Q，如果我們使用快速的機器，Q個查詢很快就完成了（Q量可以通過廣播的方式放進記憶體去各個數據分塊中快速查詢然後累計返回）：

如果我們用存儲大但是處理速度慢的機器，我們仍需要遍歷所有的數據才能獲得想要的數據總量：

如果我們採用BitFunnel的方式來處理，那麼，查詢量Q可以用(頻寬/總量)表示，引入這樣的概念就可以講之前硬碟和DDR4換一種計算方式，用每秒查詢頻寬量以及每美金每秒查詢頻寬量來表示之間能力差別，結果如下：

我們需要179倍的硬碟才能比得上DDR4，價格是DDR4的76倍代價。

處理錯誤率

最後我們來聊聊如何處理錯誤率，傳統上我們為了降低匹配錯誤率大幅度地提高了存儲代價。這樣做真的有意義么？實際上我們網頁搜索的目標並不是獲取與關鍵詞真的都完全匹配的網頁，而是獲取到內容最相符合的網頁。必應有一個Ranking Oracle系統，能夠計算一個查詢和文檔之間的符合分數來衡量文檔與用戶目標的價值。這個系統考慮了上千種訊號進行處理，甚至其中一些都不知道它是怎麼起作用的，因為這是基於機器學習在高維空間中學習所獲取的結果，同時也非常運行的代價也相當高。

假設我們有無限的查詢時間和查詢物料傳送給Ranking Oracle，讓它返回十項最相關的文檔資料，這將怎麼處理？幸運的是，我們有很好的解決方案。Bellevue Washington有一個大廈裡面有上千名的工程師，他們的主要工作就是避免網路傳來相同的文檔，主要策略的技術是通過過濾那些不能匹配布隆過濾器的文件。

在BitFunnel發明之前，主要採用反向索引。採用了BitFunnel之後運行的速度更快，但也同樣會生成錯誤樣本傳遞Ranking Oracle，BitFunnel之所以勝出在於能夠將錯誤樣本變少的同時保證時間效率。

對比

可以看出:BitFunnel的優勢在於速度和DQ低，但是有一定的錯誤率。

最後，是Bing使用BitFunnel後的效果圖：

希望各位技術牛人能夠從這Bing搜索BitFunnel技術實現文章中收穫並運用到實際工作中。

參考附錄：

[1] BitFunnel: Revisiting Signatures for Search，Bob Goodwin，Michael Hopcroft，Dan Luu，SIGIR 2017 https://www.youtube.com/watch?v=1-Xoy5w5ydM

[2] An Experimental Study of Bitmap Compression vs. Inverted List Compression, Wang, Jianguo and Lin, Chunbin and Papakonstantinou, Yannis and Swanson, Steven, SIGMOD 2017

[3] Weighted bloom filter. Jehoshua Bruck, Jie Gao, and Anxiao Jiang. In 2006 IEEE International Symposium on Information theory. IEEE.

[4] BitFunnel官方部落格：http://bitfunnel.org/