pilosa - 搜索引擎新星

搜索引擎是比較成熟的領域。ElasticSearch功能全面，使用廣泛，是這個領域的事實標準。我在為Elasticell添加搜索功能時就研究了ElasticSearch如何實現數值和文本索引。

ElasticSearch目前採用BKD tree數據結構來實現多維數值的索引，包括一維的整數、浮點數，二維的geo-distance等。自然地，我就做了個Golang版的BKD tree。但後來發現有幾個缺陷難以克服：一是插入性能隨著文檔數目增多而明顯下降；二是插入過程涉及多個文件的創建和刪除，難以將該動作原子化，不利於故障恢復。

偶然的機會發現了pilosa。它是一個集群，底層是符合Roaring Bitmap規範的高效bit操作庫。Roaring Bitmap是posting list（即文檔ID列表）的一個編碼方式。它在編碼尺寸和集合運算（交、並、補、改、查）效率方面做了均衡。

此外pilosa還開創性地將二維比特矩陣用一維bitmap來表達。每1M列作為一個切片(slice)，將切片內所有行拼接成一個大的一維bitmap，對應disk上的一個文件。這樣的二維矩陣擴展性極佳。

相比之下，ElasticSearch對posting list的編碼（壓縮）用到的技術比較常見：整數變長編碼、對ID間隔而非ID自身編碼；讀出後需要解碼（解壓縮）。集合運算效率較差。

二維比特矩陣在搜索方面非常合適。考慮文本索引，需要存儲單詞(term)與文檔ID的關聯關係。term ID作為row id, document ID作為column id。查詢同時出現指定的兩個term的所有文檔，則只需要取出對應的兩行bitmap做一次交運算。

考慮數值索引，需要存儲數值（一個無符號整數）與文檔ID的關聯關係。文檔ID作為column id，數值二進位表達的所有比特（從LSB到MSB）作為各個row的值。查詢數值在指定範圍內的所有文檔ID，就是做O(M)次集合運算，其中M為數值最大值二進位表達的位數。官方博客對此有解讀，稱之為Range-Encoded Bitmaps。相關代碼只有百來行，有些費解。

pilosa一般部署為一個服務集群。集群上的每個結點負責若干切片(slice)。由一致性散列決定切片放置在哪些結點上。另外，集群規模藉助gossip協議來調整。

我們的Elasticell是兼容Redis的強一致分散式存儲。為了簡化運維，它的搜索應當與現有存儲集群結合，而不是另做一個專用於搜索的集群。幸運的是，將pilosa的單機功能剝離為一個library並不困難。Elasticell單機版搜索引擎基本完工，也開源了。集群版也基本完工，代碼已經合併到Elasticell主項目。做一個分散式的彈性的搜索引擎有不少挑戰，後續文章再聊。

最後來個廣告，我們很缺人！

張穎峰：DeepInsight英雄召集貼zhuanlan.zhihu.com
推薦閱讀：