[第002號(hào)]

Bing搜索引擎.png

摘要

自從90年代中期以來(lái)，大家普遍認(rèn)為簽名文件在各個(gè)方面敗落與索引文件在文檔索引方面。在最近幾年Bing搜索引擎開發(fā)和部署了一套基于bit-sliced signatures故觅，這種索引技術(shù)被稱作BitFunnel，取代了原先基于倒排索引（inverted index）的產(chǎn)品系統(tǒng)翎苫。從倒排索引卻換到當(dāng)前方式背后驅(qū)動(dòng)因素是運(yùn)營(yíng)成本的節(jié)省兔院。這篇論文描述了算法的創(chuàng)新和改變，在云計(jì)算環(huán)境下讓我們有機(jī)會(huì)去重新審視那些過(guò)去被認(rèn)為不能使用的技術(shù)谆吴。BitFunnel算法解決了bit-sliced block signatures的四個(gè)基本的限制倒源。與此同時(shí)，我們把算法映射到集群上也給我們提供了機(jī)會(huì)去避免伴隨簽名的其他的代價(jià)句狼。我們?cè)诮酉聛?lái)展示了這種創(chuàng)新產(chǎn)生的明顯的性能相比較于傳統(tǒng)的bit-sliced signatures笋熬，而且比對(duì)BitFunnel與Partitioned Elias-Fano Indexes，MG4J和Lucene腻菇。

研究過(guò)程

1. 介紹

基于簽名的方法會(huì)帶來(lái)四個(gè)挑戰(zhàn)胳螟；
（1）確定一個(gè)term是否匹配昔馋，需要檢查現(xiàn)有集合中的所有文檔。相比于倒排索引需要消耗更多的CPU和內(nèi)存資源糖耸。
（2）簽名需要足夠長(zhǎng)為了滿足可接受的false positive rate秘遏，即使是搜索最不常見的terms。
（3）網(wǎng)絡(luò)文檔長(zhǎng)短差異很大蔬捷，而受限于布隆過(guò)濾器和可接受的false positive rate的原因垄提，簽名必須足夠長(zhǎng)容納最長(zhǎng)的文檔。
（4）基于簽名的格式配置不容易理解周拐。
作者提出了一系列的技術(shù)來(lái)應(yīng)對(duì)這些挑戰(zhàn)铡俐；
（1）引入higher rank row解決查詢執(zhí)行的時(shí)間。
（2）引入frequency-conscious signatures來(lái)減少內(nèi)存空間妥粟。
（3）全集分級(jí)來(lái)減少文檔大小差異审丘。
（4）開發(fā)了一套系統(tǒng)性能代價(jià)模型并使用該模型高效的定義有約束的最優(yōu)化配置。

2. 背景和前期工作

2.1 倒排索引（Inverted Indexes）

倒排索引原理.png

2.2 Bit-String Signatures

對(duì)term使用多個(gè)hash函數(shù)進(jìn)行計(jì)算勾给，計(jì)算結(jié)果的所在位置設(shè)置為1滩报。

Bit-String Signatures.png

2.3 Bit-Slice Signatures

BitFunnel重新定義的簽名文件。簽名播急，顧名思義脓钾，就是對(duì)需要索引的每個(gè)文檔進(jìn)行一個(gè)簽名。在BitFunnel中桩警，簽名表示為文檔中的一系列term的集合可训，用bloom filter表示。假設(shè)每個(gè)term用一個(gè)bit vector表示捶枢，那么整個(gè)文檔的簽名就是它包含所有term的union握截，對(duì)于query來(lái)說(shuō)，它的簽名也是一樣的定義烂叔。如同bloom filter定義谨胞，這些term的bit vector從hash函數(shù)產(chǎn)生，假如所有的簽名都基于同樣的hash函數(shù)蒜鸡，那么所有的簽名就是等長(zhǎng)的胯努，把這些簽名按照列組織在一起，就是簽名文件的bit-slice的布局逢防，可以進(jìn)行多文檔檢索叶沛。下圖是一個(gè)16bit的多文檔以及query簽名文件格式。
多文檔檢索胞四，加快并行處理速度

Bit-Slice Signatures.png

2.4 Bit-Slice Blocked Signatures

Bit-Sliced布局的問(wèn)題在于恬汁，如果查詢的term非常稀疏，那么代價(jià)就比較高昂，因?yàn)橐残枰獙?duì)每個(gè)文檔的所有bit掃描才可以得出結(jié)果氓侧，因此一種改進(jìn)是Bit-Sliced Block簽名脊另，理念是讓多個(gè)文檔的簽名共享一列，共享的文檔數(shù)被成為block factor约巷，這樣可以縮短行的長(zhǎng)度偎痛，但卻是以增加false positive為代價(jià)的。這種技術(shù)增加了復(fù)雜度但是帶來(lái)的收益不大独郎。

3. BitFunnel系統(tǒng)

3.1 架構(gòu)概覽

Bing維護(hù)一個(gè)多份踩麦、異地備份的網(wǎng)絡(luò)索引，每一個(gè)都被切分成BitFunnel節(jié)點(diǎn)集群氓癌。下圖顯示的是一個(gè)單一集群谓谦，查詢是分布式的，每一個(gè)節(jié)點(diǎn)收到查詢請(qǐng)求之后贪婉，把他解析成一個(gè)抽象語(yǔ)法樹反粥，重寫樹到可執(zhí)行計(jì)劃中然后在本地編譯，然后將編譯后的計(jì)劃廣播到剩下的集群疲迂，集群中的節(jié)點(diǎn)是并行的運(yùn)行編譯的計(jì)劃才顿，返回結(jié)果到計(jì)劃節(jié)點(diǎn)進(jìn)行聚合。這些結(jié)果被傳遞到其他系統(tǒng)尤蒿，對(duì)滿足條件的文檔進(jìn)行打分并返回給用戶郑气。

BitFunnel集群.png

3.2 False Positive的代價(jià)

False Positive.png

對(duì)于網(wǎng)絡(luò)搜索的場(chǎng)景False Positive是可以接受的。

4. BitFunnel創(chuàng)新點(diǎn)

4.1 Higher Rank Rows

BitFunnel的第一個(gè)工作是讓block factor不固定腰池，也就是每個(gè)term是用不同的block factor hash到多個(gè)Bit-Sliced Block簽名文件中尾组，具體來(lái)說(shuō)，block factor是2的整數(shù)冪巩螃，同時(shí)引入一個(gè)概念叫做row rank演怎，表示block factor的冪指數(shù)匕争。因此row rank為0跟row rank為r的簽名文件的對(duì)應(yīng)列的文檔的關(guān)系為：

row rank關(guān)系

其中w為機(jī)器的字寬的對(duì)數(shù)避乏，例如64bit機(jī)器的w為6。舉栗來(lái)說(shuō)甘桑，假如w為2拍皮，有3個(gè)row rank分別為0，1跑杭，2的Bit-Slice Block簽名文件铆帽，那么rank=1的簽名文件中第4列的文檔為「4，12」德谅，對(duì)應(yīng)rank=2的簽名文檔第0列的文檔就是「0爹橱，4，8窄做，12」愧驱。

不同row rank

不同row rank

現(xiàn)在假設(shè)有一query组砚，分別對(duì)應(yīng)不同的row rank簽名文件匹配了對(duì)應(yīng)的行（就是在不同的row rank簽名文件當(dāng)中吻商，拿query的部分term來(lái)做匹配），如上圖所示糟红，那么最終的結(jié)果應(yīng)當(dāng)是這三行求交的結(jié)果艾帐。可是不同row rank的行長(zhǎng)均不同盆偿，那么如何進(jìn)行求交呢柒爸？答案是針對(duì)row rank高的行進(jìn)行循環(huán)填充，生成它跟row rank 0等價(jià)的對(duì)應(yīng)結(jié)果事扭，然后再求交揍鸟，如下圖所示：

查詢方式

4.2 Frequency Conscious Signatures

BitFunnel的另一個(gè)工作在于bloom filter本身。眾所周知句旱，在bloom filter中有一個(gè)常量k表示對(duì)term hash的次數(shù)阳藻，這個(gè)k對(duì)于任意term都是不變的。在實(shí)際中谈撒，不同的term詞頻是不一樣的腥泥，要達(dá)到相同的false positive率，低頻詞相比高頻詞需要更高的k值啃匿。BitFunnel的做法是引入weighted bloom filter[3]來(lái)針對(duì)term分配不同的hash次數(shù)蛔外，從而起到節(jié)約內(nèi)存的效果。

4.3 Shareding by Document Length

第三個(gè)設(shè)計(jì)在于分布式溯乒，同樣由于bloom filter的因素夹厌，文檔長(zhǎng)短不一卻用等長(zhǎng)的簽名文件表示，同樣會(huì)引入更高的false positive裆悄，因此BitFunnel的做法是將長(zhǎng)度相近的文檔索引在同一個(gè)sharding矛纹。

5. 性能模型和最優(yōu)化

5.1 預(yù)備知識(shí)

5.1.1 信號(hào)在Higher Rank Row

rank r與rank 0之間的關(guān)系：

image.png

5.1.2 噪音在Rank-0 Equivalent Row

在循環(huán)補(bǔ)位的時(shí)候會(huì)引入噪音。

image.png

image.png

5.1.3 相關(guān)噪音和不相關(guān)噪音

作者對(duì)Row Rank高位循環(huán)補(bǔ)位生成Rank-0 Equivalent Row產(chǎn)生的噪音分為了相關(guān)噪音和不相關(guān)噪音光稼，相關(guān)噪音使用“C”表示或南，不相關(guān)噪音使用“U”表示，在查詢中為0或者噪音艾君，rank中為信號(hào)1的是相關(guān)噪音采够，其他事非相關(guān)噪音。
行的交集可以有效的消除不相關(guān)噪音冰垄，但是對(duì)相關(guān)噪音的影響不大蹬癌。

5.2 信噪比

image.png

image.png

image.png

image.png

5.3 查詢執(zhí)行時(shí)間

image.png

5.4 內(nèi)存消耗

image.png

5.5 選擇Term配置

對(duì)于每一個(gè)term，給定信噪比、機(jī)器字讀和內(nèi)存消耗可以得出最優(yōu)的行配置逝薪。

image.png

6. 實(shí)驗(yàn)評(píng)估

實(shí)驗(yàn)數(shù)據(jù)來(lái)源與實(shí)驗(yàn)條件

6.1 匹配時(shí)間 vs 四字節(jié)

image.png

查詢時(shí)間與四字節(jié)數(shù)量有相關(guān)性伴奥，而且IDF值越大相關(guān)性越強(qiáng)。

6.2 Frequency Conscious Signatures和Higher Rank Rows表現(xiàn)

創(chuàng)新表現(xiàn).png

Frequency Conscious Signatures技術(shù)相對(duì)于經(jīng)典的布隆過(guò)濾器在對(duì)內(nèi)存空間的優(yōu)化同時(shí)還提升了速度翼闽，Higher Rank Rows主要表現(xiàn)在對(duì)速度的提升上拾徙。

6.3 與當(dāng)前索引（倒排索引）技術(shù)對(duì)照

對(duì)比.png

從表里可以看出BitFunnel在所有數(shù)據(jù)集里都超過(guò)PEF，但是通過(guò)巨大代價(jià)帶來(lái)——內(nèi)存的消耗感局。數(shù)據(jù)集A中尼啡，使用了5倍的內(nèi)存獲得了1.62%的false positive。從5個(gè)數(shù)據(jù)集看出询微，MG4J性能低于PEF崖瞭，他們使用相同的算法，只是MG4J使用Java實(shí)現(xiàn)撑毛。除了在數(shù)據(jù)集C中书聚，MG4J性能都好于Lucene。

7. 結(jié)論

這篇論文重訪了bit-sliced signatures并且描述了在當(dāng)前商業(yè)搜索引擎中的使用藻雌，這個(gè)曾經(jīng)使用倒排索引技術(shù)的搜索引擎雌续。基于簽名技術(shù)的方法會(huì)帶來(lái)一些挑戰(zhàn)胯杭，作者開發(fā)了一系列技術(shù)來(lái)減少內(nèi)存空間的消耗和提高查詢速度驯杜。更進(jìn)一步的，作者提出了性能模型可以把系統(tǒng)的配置作為一個(gè)最優(yōu)化問(wèn)題來(lái)處理做个。

心得體會(huì)

我的體會(huì)

參考文獻(xiàn)

1. 論文解讀
2. 布隆過(guò)濾器
3. BitFunnel性能評(píng)估
4. Apache Lucene初探