比 Bloom Filter 節省25%空間！Ribbon Filter 在 Lindorm中的應用

1 前言

Lindorm是一個低成本高吞吐的多模資料庫，目前，Lindorm是阿里內部資料體量最大，覆蓋業務最廣的資料庫產品。超高的效能和低RT一直是Lindorm追求的目標，因此Lindorm也在不斷地最佳化和迭代，爭取在每個小點上都做到極致。這次，我們的最佳化的目標放到了Lindorm中的Bloom Filter上。

由於Bloom Filter只需要佔用極小的空間，便可以給出”可能存在“和”肯定不存在“的存在性判斷，因此可以提前過濾掉許多不必要的資料塊，從而節省了大量的磁碟IO。在Lindorm中Get操作就是透過運用低成本高效率的Bloom Filter來過濾掉大量無效的資料塊的，從而大幅度降低磁碟IO次數。

Bloom Filter儲存在了Lindorm的底層檔案LDFile中。在長期的生產觀察中，我們發現，Bloom Filter的空間佔用遠大於其他meta資料。在預設配置的錯誤率下，基本上100MB資料（壓縮後），就會產生1MB以上的BloomFilter，也就是BloomFilter會佔掉1%的儲存空間。對於磁碟儲存空間來說，1%的消耗並不多，但是，由於BloomFilter做為Lindorm讀鏈路上的關鍵鏈路，通常需要快取在記憶體中才能獲得更好地效能。記憶體資源對Lindorm來說是非常寶貴的資源，對於單機管理上TB資料的Lindorm節點來說，通常只有幾GB到幾十GB的記憶體來做快取。按照通常的規律，上TB的資料會產生幾十GB的Bloom Filter，這些Bloom Filter會把快取佔滿，導致資料無法進入快取，會嚴重影響使用者請求的記憶體命中率。因此，最佳化Bloom Filter的大小，意味著可以減少記憶體佔用，讓快取能夠載入更多使用者資料，從而最佳化Lindorm的讀效能。

為了最佳化BloomFilter， Lindorm也做了不少嘗試，比如引入

SuRF

，但我們發現，在空間佔用率上，SuRF並不比BloomFilter有優勢。因此，我們把目光轉向了2021年的一篇論文《Ribbon filter： practically smaller than Bloom and Xor》。這篇論文提出了一種新的Ribbon Filter，據論文的結論，Ribbon Filter相對Bloom Filter可以節省30%的空間。這個對我們來說是一個非常誘人的結論，節省30%空間意味著可以釋放30%的快取空間，讀請求的記憶體命中率會有很大一部分提升。

Ribbon Filter真的有論文中說的那麼神奇嗎？帶來空間節省的同時，會帶來副作用嗎？本文將這一全新的Ribbon Filter給大家做一個介紹，然後我們把Ribbon Filter引入了Lindorm中，並測試了Ribbon Filter在實際生產中的真實表現。

2 基本原理

2.1 Bloom Filter

Bloom Filter是Bloom在1970年提出的一種機率資料結構［1］，用來快速測試元素是否是集合的成員，存在一定的假陽性率（一般設定為0。01），不可能有假陰性率，即查詢返回“可能存在”或者“一定不存在”。可以新增元素到集合中，但不能刪除（有改進版本可以實現），新增的元素越多，假陽性率越大。對於給定的假陽性率e和元素數量n，Bloom Filter有一個最佳的空間大小，使得新增元素過程中，保證逐漸變大的假陽性率小於等於e。

Bloom Filter由一個長度為n的

01陣列array

組成。首先會將array陣列每個元素初始化設為0，對於集合A中的每個元素w，做k次雜湊，每次雜湊值都會對n取模得到一個索引，比如第i次雜湊，索引

，將array陣列中的對應位置置為1，最終array變成了一個部分元素為1的陣列。對於待檢測元素w同樣會做k次雜湊得到k個索引，如果陣列中對應位置都為1則元素w可能存在集合A中，否者一定不存在。

2.2 Xor Filter

Ribbon Filter是基於Xor Filter做的，在介紹Ribbon Filter之前，得先了解Xor Filter。Xor Filter是Thomas Mueller Graf和Daniel Lemire在2020年提出的［2］，也是用來檢測一個元素是不是集合中的一個成員，相比Bloom Filter，Xor Filter核心差異主要是如下：

Xor Filter有固定的

三個雜湊

函式，而Bloom Filter雜湊函式由假陽性率確定；

Xor Filter採用

XOR

方式按slot匹配，Bloom Filter使用AND方式進行按位匹配；

Xor Filter由一個

二維bit陣列

組成，Bloom Filter是一個一維bit陣列；

Xor Filter相比Bloom Filter最高能節省20%的空間。

輸入的元素經過多個雜湊函式生成的雜湊值不會像Bloom Filter一樣對映到一個bit位，而是對映到一個固定長度的slot，一個slot有多個bit位，且每個slot的bit位數相同。對於待檢測元素w，會經過k個雜湊函式生成k個雜湊值分別對映到對應slot上，然後對所有的k個slot中的元素進行異或運算得到結果r，元素w還會經過另外一個獨立的雜湊函式生成指紋fingerprint（w），和r作對比，如果相同則元素w可能存在集合A中，否者一定不存在。

接下來介紹Xor Filter的構造原理

開始先介紹幾個關鍵變數：

B存放著的r-bit的Xor Filter

n是參與構建Xor Filter的集合A元素數量

k是雜湊函式的個數（固定值3）

m是slot的個數

初始時令r=5，n=3，k=3，m=9，B所有元素為0，元素x，y，z分別經過3個雜湊函式對映到3個slot上，每一個元素經過一個獨立的雜湊函式生成指紋f（x）=11010，f（y）=10000，f（z）=01110，

我們可以看到slot7被元素z獨享，所以slot7能夠唯一標識z，將slot7打上標記z，並去除元素z的對映

此時slot5可以唯一標識元素y，將slot5打上標記y，並去除元素y的對映

現在只剩下最後一個元素x，f（x）可以放在slot1、slot3、slot6任一位置，這裡選擇slot1，slot3和slot6置為的5-bit 0，將f（x） xor slot2 xor slot3的結果放在slot1中，11010^00000^00000=11010，並回填其它帶有標記的slot，和前面操作一樣y元素slot5=f（y） xor slot1 xor slot6=10000^11010^00000=01010，z元素slot7=f（z） xor slot2 xor slot5=01110^00000^01010=00100

最終得到了構建好的Xor Filter，測試的時候，待檢測的元素w經過3個雜湊函式得到對應的slot索引h1（w），h2（w），h3（w），以及經過另一個雜湊函式得到指紋f（w），將指紋與B（h1（w）） xor B（h2（w）） xor B（h3（w））進行比較。如若相等，則表示元素w可能存在，否者一定不存在。

2.3 Ribbon Filter

Ribbon Filter是Peter C。 Dillinger和Stefan Walzer在2021年提出的［3］，Ribbon Filter主體是Xor Filter的實現，在其基礎上構建可以高效運算的

矩陣

，從而利用矩陣本身的高效運算來解決Xor Filter構建過程中的重複操作，相比Bloom Filter，Ribbon Filter會消耗更多的CPU，Ribbon Filter的核心優勢在於

節省空間

，所以會針對Xor Filter的二維陣列的求解過程做計算最佳化，Ribbon Filter會將二維陣列的求解過程轉化成解線性方程組Ax=b，並應用了基於行列式的

高斯消元法

，線性代數中求解執行緒方程組時會用到行列式運算，高斯消元法就是在求解執行緒方程組的過程中，將一個行列式轉化成上三角或者下三角矩陣。

相比Xor Filter， Ribbon Filter主要差異如下：

Ribbon Filter雜湊對映到陣列連續的一片索引，而Xor Filter僅有的3個雜湊函式每個都隨機對映；

Ribbon Filter構建過程使用

高斯消元法

，Xor Filter使用Peeling演算法；

Ribbon Filter二維bit陣列使用

列式儲存

，Xor Filter是行式儲存；

Ribbon Filter相比Bloom Filter最高能節省30%的空間。

讓我們看一下上節Xor Filter的元素w的查詢測試過程，雜湊對映用h（x）表示，

，

，

，即

= B［2］ xor B［4］ xor B［7］ ，那是不是可以表示成

，其中

是元素w雜湊對映的

特徵向量

，第2，4，7位為1（索引從0算起），對應了

，

，

的值，Z是二維bit陣列B的

矩陣

形式，

，同時注意

計算過程中加法運算要變成異或

XOR運算

。可以計算出query（w）=00100，

=

上節Xor Filter的構建過程可以用線性方程組表示成：

，二維bit陣列B可以透過求解該方程組得到，方程組的係數矩陣為

，第1行對應了元素x雜湊對映的特徵向量，第2行y，第3行z。

除了引入矩陣運算，Ribbon Filter還對二維bit陣列的儲存結構進行了調整，在Xor Filter中每個slot的r-bit連續儲存，且保證第i個slot中所有的bit都在第i+1個slot的r-bit前面，這種稱為

行式儲存結構

，而Ribbon Filter使用

列式儲存

，保證每w個slot的第j個bit都在第j+1個bit前面，w是Ribbon Filter雜湊對映到的連續索引的寬度，一般w>>r，如果使用行式儲存，查詢的時候需要從記憶體讀取所有的w個r-bit，然後做異或計算得到結果並與指紋對比，現在使用列式儲存，可以先讀取第1個w-bit，做一下異或計算並將結果與指紋的第1個bit比較，如果不同則表示查詢的元素不在集合內，直接返回False，否者繼續讀取接下來的w-bit並重復之前的過程。列式儲存帶來的好處有：

查詢過程不用讀取所有的bit，減少查詢時間；

對空間更友好，訪問w個連續記憶體空間變成了訪問r個連續記憶體空間。一般w=64，r=7。

2.4 效能對比

依據Ribbon Filter論文的效能對比結論，我們提取出本文關心的Bloom，Xor，Ribbon三者的效能對比。這裡的key用的是long資料型別，Construct包括新增key和求解方程。

從表中可以看出：

Ribbon構建時間是BlockedBloom的

7.5倍

；

Ribbon查詢時間是BlockedBloom的

2.8倍

；

Ribbon空間開銷是BlockedBloom的72%（（1+10。1%）/（1+52。0%）），節省了28%。

透過文章中的對比，我們發現Ribbon Filter雖然比Bloom Filter節省了28%的空間，但構建時間和查詢時間都有了一些明顯的上升。初看是一個時間換空間的做法，不過，論文中選用的Bloom Filter是BlockedBloom，這是2019年提出的一個基於Bloom Filter的最佳化版本［4］，本身效能就已經比較好，而且測試的Filter hash function都是針對long值的，而Lindorm中的Bloom Filter是針對byte陣列做hash的，效能表現可能不完全一致。因此，Ribbon Filter是否能在任何場景下都能Lindorm帶來效能提升，需要我們把Ribbon Filter引入Lindorm中，在生產環境做一些測試。

3。 應用Ribbon Filter

3.1 核心邏輯的實現

我們參考論文中的Ribbon Filter使用Java進行了實現並整合到Lindorm中。論文中有一種空間開銷更小的最佳化版本的Ribbon Filter，但是它不能保證構造成功，需要重試，這在Lindorm中是不能接受的，Lindorm中構建過濾器是不能失敗的，否則會導致Flush或者Compaction失敗。所以我們最後選用了寬度w=64的Homogeneous Ribbon Filter。

最終的實現有一些工程上的取捨，因此與論文還是存在一些差異：

論文中實現的Ribbon Filter使用的key型別是long型，在Lindorm中每個key是一個byte陣列；

論文中實現的Ribbon Filter構建的時候直接提供一個key陣列，但是在Lindorm中key是流式的一個個來，並且數量未知；

論文中實現的Ribbon Filter構建提供key陣列的大小n是已知的，可以透過公式

（錯誤率f已知）得到Ribbon Filter的空間大小，但是Lindorm中只提供空間大小bitSize和錯誤率f，key數量n未知，需要反向求出n；

論文中實現的Ribbon Filter輸出的是一個long型陣列，但是在Lindorm中得是一個ByteBuffer才能統一存到檔案系統中；

論文中實現的Ribbon Filter查詢過程可以使用類中全部中間變數，但是在Lindorm中查詢函式是靜態的，只有少部分meta資訊和存有Ribbon Filter的資料塊可以使用。

Ribbon Filter的構建：

Bloom Filter構建過程只需要新增元素即可，新增完了就構建完了，但是Ribbon Filter構建過程還包括求解方程階段，這個階段是最耗時的，這個階段放在哪個地方在什麼時間由誰呼叫來執行，會不會影響效能是一個大大的問題。目前是放在Ribbon Filter的寫過程中執行，寫之前會先求解方程，效能影響目前還沒發現。

Ribbon Filter的查詢：

Bloom只需要少量的meta資訊然後按需載入需要的Bloom Block，就可以完成查詢過程，meta資訊有VERSION，byteSize，hashCount，hashType，keyCount。Ribbon不需要hashCount欄位，其它都要，除此之外還需要numStarts（雜湊對映到的區間上限），upperNumColumns（指紋位數的向上取整），upperStartBlock（指示floor（r）位的slot與ceil（r）的slot的分界），後續引入失敗重試機制還得有雜湊種子seed欄位。

為了不改變meta資訊的長度，只將hashCount變成了slotCount（slot的數量），都是int型別，numStarts = slotCount-63，upperNumColumns = （ribbonBitSize + slotCount - 1） / slotCount，upperStartBlock = upperNumColumns * （slotCount >> 6） - （ribbonBitSize >> 6），這樣就完美了，從物理儲存層是不太能看出Bloom meta block和Ribbon meta block的區別的，既沒增欄位也沒減欄位也沒修改欄位型別。

3.2 初步測試

本次benchmark對比的是在Lindorm中應用的Bloom Filter和Ribbon Filter。這裡的key用的是byte陣列型別，key length是byte陣列大小；錯誤率都為1%，hash型別都是murmur，Construct包括新增key和求解方程。

1。 Construct，構建filter，單位是ns/key， n=10^6，下同。

可以看到，在Lindorm中，隨著Key長度的增長，構建Ribbon Filter的速度反而會更快

2。 Query，查詢

可以看到，在Lindorm中，隨著Key長度的增長，查詢Ribbon Filter的速度反而更快。

3。 space load，空間負載跟key length無關

從初步測試的結果來看，似乎測試結論比論文中更好，無論查詢速度，構建速度，Ribbon Filter都比Bloom Filter更優。我們分析，這是由於Lindorm中原來使用的BloomFilter是一個沒有最佳化過的原始版本，而且Bloom Filter查詢時需要多次執行hash函式，而hash bytes的消耗比論文中hash 數字的消耗要大的多，因此Ribbon Filter的查詢效能並沒有論文中說的那麼差，反而隨著key的長度變長，查詢的效能要強於原有的BloomFilter實現並且差距越來越大。

構建Filter時的結論也類似，隨著key長度的上升，RibbonFilter的構建速度更快，完全優於Bloom Filter。但在生產過程中，構建過濾器只佔Lindorm生產LDFile全過程中的很小一部分，基本上不會對Lindorm檔案的生成速度造成影響。在空間上，相同的錯誤率下，Ribbon Filter確實能比Bloom Filter節省25%的空間。

基於以上測試結論，我們覺得使用Ribbon Filter替代Bloom Filter，無論從哪個角度上來說，都是一個不錯的選擇。

3.3 生產測試

我們把Ribbon Filter整合在Lindorm寬表引擎中，進行了全鏈路的壓測，壓測機器的配置為

4核8GB

，使用

ESSD

儲存，壓測工具用的是

ycsb

本次測試的是批次讀的吞吐量對比測試和延遲對比測試，以及讀取過程中的快取命中率對比測試，以及major compaction效能對比測試。讀取測試根據rowKey的位元組數的不同分為四個場景：10bytes，25bytes，50bytes，300bytes。

測試表單節點分佈，load10億行資料，每行資料一個列族，共5列，每列value 20bytes，每行資料大概0。1kb，表大小100G左右，批次讀一次20行。

批次讀

吞吐量

對比

批次讀

平均延遲

對比

讀取過程中的

快取命中率

對比

單節點major compaction效能對比（cpu打滿）

Filter的meta資訊對比

生產的測試證實了我們在3。2節理論分析的結果。引入Ribbon Filter後，讀的吞吐最高有了18%的提升。讀RT有了最高15%的下降。吞吐的提升和RT的下降主要來源於使用Ribbon Filter後，過濾器空間的減少和記憶體命中率的提升。並且在不同的key大小下，Ribbon Filter均有好過Bloom Filter的表現。

在Compaction的對比測試中，大家也可以看到，使用Ribbon Filter與否對Compaction的速度基本沒有影響。

4 總結

本文研究了一種新的過濾器Ribbon Filter。我們根據論文的思路在Lindorm中進行了實現。經過測試，我們發現Ribbon Filter能夠節省25%的過濾器空間佔用，從而在各種條件下提升Lindorm的讀效能。Lindorm將在下一個版本中整合Ribbon Filter，帶給使用者極致地效能體驗。

另外，為了保證Ribbon Filter構建不失敗，我們選用了一種空間佔用相對較多的實現，我們將在Ribbon Filter的基礎上繼續做了一些探索，保證構建不失敗重試的前提下，進一步節省過濾器的空間。

參考文獻

［1］Burton H。 Bloom。 1970。 Space/Time Trade-offs in Hash Coding with Allowable Errors。 Commun。 ACM 13， 7 （1970）， 422–426。

［2］Thomas Mueller Graf and Daniel Lemire。 2020。 Xor Filters： Faster and Smaller Than Bloom and Cuckoo Filters。 ACM J。 Exp。 Algorithmics 25 （2020）， 1–16。 https：//doi。org/10。1145/3376122

［3］Dillinger， Peter C。 and Stefan Walzer。 “Ribbon filter： practically smaller than Bloom and Xor。” *ArXiv* abs/2103。02515 （2021）。

［4］Harald Lang， Thomas Neumann， Alfons Kemper， and Peter A。 Boncz。 2019。 Performance-Optimal Filtering： Bloom overtakes Cuckoo at High-Throughput。 Proc。 VLDB Endow。 12， 5 （2019）， 502–515。

作者：簫蘇 朝戈 正研

原文連結：http://click.aliyun.com/m/1000349558/

本文為阿里雲原創內容，未經允許不得轉載。