written by 欽誠，禎祺

Cuckoo Hashing 的引入

在indexlib的底層，需要一個高性能的Key/Value引擎來提供類似python Dict/ Java HashMap/ C++ unordered map（這些數據結構的性能不能接受）的支持。最基本的就是支持insert(key, value)和find(key)這兩種操作。原本我們有Dense Hash Table和Chain Hash Table這兩種數據結構，但是它們各自都有明顯的缺點。

Dense Hash Table就是普通的用線性探查解決沖突的哈希表，如圖所示。當插入F時，通過哈希函數將F映射到表中所指位置，發現該位置已存有D了，向后掃描探查，直到碰到一個空位，再將F插入。而查詢一個G時，則需要從對應的位置開始向后找，直到找到G（命中），或找到空位（G不在表中）。這種結構對內存的利用不佳，如果想讓哈希表盡量存滿(k, v)對，那么插入/查詢的性能將會嚴重下降。

Chain Hash Table是利用拉鏈法解決沖突的哈希表，它的特點是空間利用率比較高，除了順序存下所有(k, v)對之外僅需要一個索引來記錄鏈表頭，但由于鏈表的空間不連續，導致查詢性能一般。

• 在我們實現的版本中，圖中的A,H,P,J,B,M,Q,D,W存在一塊連續的內存區域中，但它們的順序不一定，我們將其稱作鏈表區域。
• 一種較簡單的優化是在全部插入操作完成之后，重新整理鏈表區域，把同一條鏈上的結點歸到連續的區域，即鏈表空間中嚴格按照A, H, P, J, B, M, Q, D, W的順序存儲。這樣，查詢時若要遍歷鏈表，不需要“跳”著訪問，而是訪問連續的地址。
• 但這個步驟本身花費不小（可能的額外空間、時間），并且由于索引區域和鏈表區域仍不連續，需要兩次訪存，其性能仍然存疑。

Cuckoo Hash Table是本次引入的數據結構，它用了兩個哈希函數來解決沖突。Cuckoo查詢操作的理論復雜度為最差O(1)，優于Dense的期望查詢復雜度O(1)和Chain的O(1+α)，而Cuckoo的插入復雜度為均攤O(1)。我們引入Cuckoo是希望它在實際應用中，能夠在較高的空間利用率下，仍然維持不錯的查詢性能。

• Cuckoo利用兩個哈希函數來實現最差O(1)的查詢復雜度：
  對任意一個Key可求出兩個哈希值，相當于映射到兩個桶，如A被映射到1,4，說明它可以被存到1號或4號桶，而實際在1號桶。本圖中，用箭頭連接某個Key實際存入的桶和另一個對應的桶，如1--->4。
• 當插入一個F時，如果對應的兩個桶至少有一個為空，則將其插入到這個位置，否則任選一個桶，不妨設為A所在的1號桶。我們將其中原有的A = Key’/Value’踢出，將新的F存入。對于剛取出的A，它之所以存儲在1號桶是因為用了兩個哈希函數之一，那么我們用另外一個哈希函數，知道A對應的位置還有4號桶。若4號桶為空，則將A放入，整個過程就結束了。而事實上，4號桶中還存有B = Key’’/Value’’，那么把它們踢出并重復上面的操作。整個過程中進行踢出、填入操作的，形如“1->4-> … ->空位”這樣的序列我們將其稱為Cuckoo Kick路徑。
• 當查詢一個F時，分別檢查它的的哈希值對應的兩個位置即可。

我們的Cuckoo哈希表的特性

使用4路組相聯

不進行組相聯的Cuckoo，只能達到50%左右的容積率，就會開始出現插不進去新的(k, v)對的情況。而如果用組相聯，則可以大幅提高容積率。組相聯即上圖中的一個位置，變為現在的一組位置，它們對應同一個哈希值。我們使用的4路組相聯，可以在性能無明顯下降時達到超過90%的容積率。

如果使用k路的組相聯，那么一次查詢就意味著最多要查2k個桶。因此如果使用更多的路數進行組相聯，雖然可以進一步提高容積率，但同時會導致每一次查詢操作時掃描過多的桶，導致讀性能下降，不能接受。我們常見的使用場景是8bit key + 8bit value和 8bit key + 4bit value。對于第一種情況，4路組相聯可以保證每次查的一個block在同一個cache line中，而即使是第二種，也最多跨兩個cache line。相當于利用cache line內的訪問，來減少組相聯對讀性能的影響。

使用BFS尋找Cuckoo Kick路徑

我們遇到沖突時，先不急著將Key/Value踢出，而是使用廣度優先搜索，從A和B分別開始找一條完整的Cuckoo Kick路徑，每一步都將組相聯的4個桶一起加入BFS隊列，這樣可以保證找到的路徑是最短的一條。找到之后，先把路徑上最后一個Key/Value移到空位，形成新的空位，再把倒數第二個Key/Value移到空位，以此類推。

支持增加哈希函數：

在容積率達到較高（如90%）以后，如果希望再插入新的(k, v)對，那么插入過程中BFS尋找的Cuckoo Kick路徑將會越來越長（見性能測試部分），插入性能將會快速下降。因此，我們在插入失敗時，選擇添加一個哈希函數（從2個變為3個，再不行變為4個，5個…，這意味著每個key對應的block從2個變成更多），讓BFS搜索樹從二叉樹變成多叉樹，使得找到一條Cuckoo Kick路徑更加容易，在損失一些讀性能的前提下，提高了容積率。

名詞定義

• 我們的哈希表將key, value對完整地存下來，簡稱為(k, v)對
• 將哈希表中用來存儲(k, v)對的位置稱為桶（bucket），因此表體就是桶的數組
• 容積率(occupancy) = 已存有(k, v)對的桶數/總桶數，相當于空間利用率/load factor
• insert/插入/寫，表示將一個(k, v)對插入哈希表
• find/查詢/讀/lookup，表示在哈希表中查詢key對應的value
• 命中/查詢成功/positive lookup，表示find函數在哈希表中成功找到了所查的key
• 不命中/查不到/negative lookup，表示find函數發現key不在哈希表中
• QPS(query per second或reqs per second) = 平均每秒完成的insert或find操作的次數
• Cuckoo的組相聯意味著每4個桶對應同一個哈希值，這4個桶稱為一個塊（block）
• 一張Dense哈希表包括：表頭（header）+ 表體（bucket的數組）
• 一張Cuckoo哈希表包括：表頭（header）+ 表體（block的數組）+ 輔助數據結構（臨時，僅插入時使用，不需要存下來）

參考資料

• Cuckoo Hashing for Undergraduates, Rasmus Pagh
• MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing, NSDI’13
• Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, eurosys’14
• https://brilliant.org/wiki/cuckoo-filter/
• https://en.wikipedia.org/wiki/Cuckoo_hashing
• http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/05/linear-probing.html

Cuckoo Hashing性能測試

容積率

經過測試，在桶數較多的前提下（>10000），使用純隨機數據并且不使用增加哈希函數的功能，在插入性能明顯下降之前可以達到92%左右的容積率，不考慮性能的因素，在第一次有key插入失敗之前可以達到98%的容積率。

使用增加哈希函數的功能一起測試，一般可以達到100%的容積率，在1000000個桶的哈希表上進行容積率測試，結果如下表：

哈希函數個數23456

可達到的容積率	98.02%	99.92%	>99.995%	>99.995%	100%

插入性能

由于Cuckoo Hash Table的特性，在容積率較低時，一次插入掃描的桶數、代碼邏輯的復雜程度都高于Dense，導致只能獲得2000000左右的QPS。而隨著容積率的上升，越來越多的插入操作需要通過找Cuckoo Kick路徑來獲得一個空桶，而這個路徑的長度也相應增長，其占用的時間、空間資源大幅上升。因此，整體的插入性能應該是比不上Dense和Chain的。

向一個有100,000,000個桶的Cuckoo Hash Table中不斷插入key，它花費總時間的趨勢如圖所示。在容積率達到85%之前，插入時間基本是一條直線，說明沒有明顯的性能變化。而在約92%-93%之后，插入性能開始發生急劇下降。

總體來說，Cuckoo的插入性能是遠遜與Dense Hash Table的，雖然Dense的性能在高容積率時也會快速下降，但容積率直到90%時插入性能仍遠高于Cuckoo。

查詢性能

考慮到我們引入Cuckoo 時，就是希望其能在較高的容積率下保持不錯的查詢性能，以在離線場景能節省空間，因此可以接受稍差一些的插入性能。所以，插入性能暫不在后面進一步討論的范圍內（即使插入也可以類似地使用Cuckoo性能優化這一節的方法來進行優化），而將關注點轉移到查詢性能上。

我們預期的查詢性能是Dense在容積率較低時肯定性能出色，而隨著容積率上升到70%-80%，每次查詢遍歷的桶數將快速上升，導致查詢時間成比例的上升；Cuckoo預計的性能將不怎么受到容積率的影響，隨著容積率的上升，查詢性能只會緩慢下降；因此，在一定的容積率（如70%）時，其性能將會超過Dense，并逐漸將其甩開。

但是，實測的查詢性能卻并不理想，雖然前兩個估計基本滿足了，但是Cuckoo性能超過Dense的容積率節點卻非常靠后，具體數據展示在Cuckoo、Dense、Chain性能對比。

其它性能測試

除以上的常規測試之外，還對Cache Line對齊、存儲在第二個哈希函數對應位置占比等進行了測試（哈希表包含100,000,000個桶，里面裝了90,000,000組(k, v)對），結論主要有以下幾點：

• Cache Line如果不對齊，將導致10%-12%的性能下降。
• 查詢全部命中時，只有23%的命中了第二個哈希函數對應的位置。
• 直接改為不查第二個哈希函數（只遍歷第一個哈希函數對應的block，沒有查到就退出），性能為原本的5倍。
• 8路組相聯的性能較4路差很多，5路組相聯較4路也有下降。

Cuckoo、Dense、Chain性能對比

在進行對比測試之前，已經初步優化了Cuckoo的代碼，包括做了一些循環展開、條件判斷的順序調整、優化代碼邏輯等等。為了保證Cuckoo與Dense、Chain格式盡量在公平的條件下進行對比測試，控制實驗條件如下：

• 盡量為表體使用同樣大小的內存，因此，Cuckoo和Dense表中包含的桶數是相同的，均為100,000,000。在建表時，Cuckoo會多用一些額外的輔助結構，它們占用了一定內存，但這部分最終是不用存下來的。
• 容積率統一設置為90%，即插入過程在插入90,000,000個(k, v)對后結束，之后開始測試查詢性能。由于Chain不存在容積率的概念，我們仍按照保持內存大小一致的原則，用90,000,000個桶存下所有插入的(k, v)對（存多條鏈），剩下10,000,000個桶的空間作為索引（存鏈表頭）。
• Key和Value各占用8個字節，Cuckoo Hash Table還滿足表體的首字節地址為64的倍數，以確保Cache Line對齊（即一個Block對應一個Cache Line）。
• 采用一組實際的user_id數據進行測試。

測試結果如下圖所示，橫軸為哈希表的容積率，縱軸為查詢操作的QPS。可以看出，在絕大部分key不命中的場景，反而是Chain哈希具有較好的性能，這是因為Chain每次查詢訪問的空間連續，且它不需要判斷桶是否為empty，少一次比較操作，效率相對較高。而Cuckoo和Dense對于每個桶的檢查是完全一致的，我們原本認為性能的差異應當對應于每次查詢平均遍歷的桶數/Cache Miss次數的差異。

在圖示查詢不命中的實測數據中，如果我們對Cuckoo和Dense這兩種閉鏈哈希進行對比的話，僅在較低的容積率50%時，Dense的查詢性能比Cuckoo好；在容積率為60%及以上，Cuckoo的性能就超過了使用線性探查的Dense；在容積率達到90%以后，Dense的性能已經退化到無法使用的地步。

這一結果基本符合我們的預期：Dense Hash Table隨著越來越多的key的插入桶數組，空桶位越來越少，并且，key不命中的場景是需要遍歷所有連續存有(k, v)對的桶（它們會跨越多個Cache Line，有多次Cache Miss），直到找到一個空桶，才能確定這個key確實不存在；而Cuckoo在大多數情況只有一次Cache Miss（掃第一個哈希函數對應的block），偶爾會有兩次Cache Miss（掃第一個和第二個哈希函數對應的兩個block），因此在容積率達到一定時，性能將會超過Dense。

然而，在全部命中的場景，Cuckoo的表現則不盡如人意，從橫軸（容積率）來看，Dense的性能一路領先，直到達到90%的容積率時，性能才被Cuckoo反超，可以說離我們的期望有較大的差距。因為按照我們最初的想法（上一段中的預期），即使是命中的場景，只要容積率達到60%-70%，Dense也應該比Cuckoo掃描更多的桶，從而QPS比Cuckoo低。可是，實測數據卻說明Dense的性能直到90%才被超過，這個差異將在Cuckoo性能分析與優化一節進行分析。

另一方面，插入完成后進行過鏈表區域整理的Chain哈希的查詢性能則基本處于Cuckoo和Dense兩者之間，考慮到在不命中時其性能領先，在容積率處于70%-90%之間時Chain也不失為一種解決方案。

Cuckoo 性能分析與優化

性能差異分析

首先回顧一下我們的預期：Cuckoo和Dense對于每個桶的檢查是完全一致的，它們之間性能的差異應當在每次查詢平均遍歷的桶數/Cache Line數上。由于Dense就是普通的線性探查哈希，在容積率較高時，一個key實際存儲的位置，相較于這個key通過哈希函數求出來的桶，往往需要探查較長的距離，也就是和Cuckoo相比（一次查詢最多遍歷8個桶）要遍歷更多的桶。

考慮到實測結果，特別是key全部命中的情況，不符合我們的預期。于是我們統計了Cuckoo和Dense每次查詢平均遍歷的桶數，以判斷以下假設的正確性：在較高的容積率時，Dense會比Cuckoo遍歷更多的桶，這些桶跨越更多的Cache Lines。

容積率Cuckoo查不到Cuckoo查到Dense查不到Dense查到

80%	5.67461	2.90213	12.9941	3.00045
90%	6.74718	3.30731	50.4867	5.49856

上表展示的是每次查詢平均掃描的桶數，可以看出，在Key查不到的情況下，Dense每次需要遍歷的桶數遠超Cuckoo需要遍歷的桶數，因此性能不如Cuckoo也是合理的。但是，它們之間性能的實際差距遠沒有遍歷的桶數的差距那么大。

而在Key全部命中的情況下，由于數據比較隨機，Dense的散列效果并不差，在容積率為80%時平均遍歷的桶數僅略多于Cuckoo，在90%時則超過較多，約為Cuckoo的1.7倍。然而，實測性能告訴我們容積率在80%甚至85%時，Dense的性能還領先于Cuckoo，90%時也只是略差于Cuckoo。綜上所述，我們之前認為的“性能和遍歷的桶數/Cache Miss次數成反比”這一斷言存在一定的問題，我們需要找到其中隱藏的其他因素的影響。

一種可能的解釋是Dense的空間局部性較好，每次查詢操作都是由給定的key求出哈希值，再從哈希值對應的桶開始，向后連續遍歷一些桶，直到找到這個key或者碰到一個空桶。即使這些桶跨越了較多的Cache Line，CPU還是能較好地進行分支預測、預取到緩存等操作。Cuckoo雖然做了Cache Line對齊，且每次查詢最多會訪問兩個block，即兩個Cache Line的數據，但這兩個行之間沒有任何聯系，進行訪存的時候CPU沒有優化的余地，且還比Dense多了一次取模運算。考慮其它性能測試b)c)提到的，僅23%的操作訪問了第二個哈希函數對應的行（占總操作的23/123），卻導致了超過50%的性能差異，可見Cuckoo訪問“第二行”的開銷是相當大的。因此，在80%左右的容積率下，雖然Dense訪問的桶數略多于Cuckoo，但它憑借優良的空間局部性挽回了不少性能；而Cuckoo被少數“需要訪問第二個哈希函數的查詢操作”中的第二次取模、第二次訪存所拖累，所以性能不如Dense。

為了驗證這種解釋，我們使用Intel VTune抓取CPU數據，我們發現Cuckoo的查詢函數中，有一條cmp匯編指令的平均CPI（Clockticks per Instructions）非常高，而這句指令前面是哈希函數（包括取模獲取桶號）以及訪存，并且訪存指令依賴于取模的結果、cmp指令依賴于訪存的結果，這一系列操作加起來可能占用數百個時鐘周期。雖然上述指令的CPI并沒有異常，但可以推測VTune是把這一系列指令的時鐘周期算在了cmp指令上。

通過進一步查詢資料以及和intel工程師的合作，基本可以確認瓶頸就是在取模、訪存操作上（和Dense的差距也就在于Cuckoo可能用到的第二個哈希函數對應的取模、訪存），而且我們使用的64位取模指令花費的時間可以達到32位取模的數倍。由于這幾句匯編指令前后還存在數據依賴，更導致流水線幾乎停頓，并且在這期間，超標量處理器的多個發射指令的port也只有一個能被使用。

取模與預取優化

最終，我們應用了兩個優化：

經過測試，發現僅將64位取模語句直接修改為32位取模就可以獲得15%的性能提升。但在特定場景下的總桶數的確是可能超過4G的，因此考慮下述兩種解決方案：

• a) 將一個大表拆成多個桶數不超過4G的小表

這就需要將key的值分段進行索引，一段索引到表，一段索引到個桶。這樣就存在潛在的問題：一個是不同小表的容積率可能不會均衡；一個是可能需要兩次取模。

• b) 在桶數較少時，使用32位取模，桶數較多時仍維持64位取模

這種修改比較容易實現，也足以優化大多數場景。可是，這就需要我們加入對桶數的條件判斷，既可以每次取模時判斷，也可以在建表前判斷，并用函數指針確定每次調用的時64位模還是32位模。后者雖然不需要做多次判斷，但是函數指針的存在導致代碼不能內聯，實測的性能是：

32位取模>每次條件判斷使用哪種>函數指針>64位取模。

在應用了1.b)的優化后，減少了取模運算消耗的時間，可以利用這一點再對訪存操作再進行優化。我們嘗試加入了prefetch預取，即在讀取第一個哈希函數對應的block之前，計算第二個哈希函數對應的block號，并利用__builtin_prefetch()語句顯式的預取第二行的內容到Cache。經過多輪實驗，最終確定的（在高容積率下）性能最優的執行順序如下:

計算哈希、取模，得到第1個block的位置

預取第1個block

計算哈希、取模，得到第2個block的位置

預取第2個block

查詢第1個block

查詢第2個block

本實驗依然在“100,000,000個桶，90,000,000個(k, v)對”的條件下進行，可以看出32位取模對性能有約15%的影響，預取在這一基礎上，又對總性能有約20%的提升。圖中prefetch1是僅預取第2個block的另一種寫法，prefetch2對應上述的執行順序。由于低容積率下絕大多數時候不需要遍歷第二個block，這種方式實際上是略微犧牲了低容積率下的性能的。但是，對于高容積率的情況，不命中時有約74%的會查到第2個block，因此性能有大幅提高。命中時雖然僅有23%的查詢會訪問第二個block，但是基于以下幾點原因，性能同樣得到了提高。

• 優化之前，我們已知23%的操作訪問了第2個block，卻占用了總時間的50%。
• 應用32位取模后，多余的取模操作造成的負面影響已經被大幅減小。
• 現代CPU都是超標量、流水線、多核處理器，以開發機的Intel Haswell處理器為例，它的每個核心中都有6個可以同時發射指令的port（6條超標量流水線），Skylake則有8個，每個核心中有一個scheduler決定將指令發射到哪個端口，優化前，VTune數據顯示我們對port的利用不佳，大多數時候都只能用到其中1個port。優化后，預取操作雖然屬于訪存操作，需要花費較多的時鐘周期，但它只需要占用6個中的1個支持內存load的port（并非6個port都支持內存load的操作）。這就意味著，在進行預取的同時，其余的port上仍然可以進行計算、比較等指令，比如，預取第1個block和計算第2個哈希可以在不同port上并行，預取第2個block和查詢第1個block也應當可以并行。

總結

在應用了這兩項優化之后，重新進行Cuckoo和Dense的性能對比，可以明顯地看到Cuckoo性能的提升，我們的優化有不錯的效果。現在基本可以認為，在80%的容積率時，Cuckoo的整體查詢性能已經超過了Dense。（不命中的場景QPS達到了Dense的兩倍，命中時以約5%的差距稍稍落后于Dense。）

幾點以后需要注意的地方：

Intel Vtune的數據，未必會將CPI的統計與匯編指令一一對應，在我們的測試中，會將連續幾條的累積（包括取模、訪存）計在一條cmp指令上。

64位取模和32位取模的耗時的巨大差異需要留意，最好使用32位取模，條件允許的情況下將除數設為2的冪，用位運算進行取模。

對一些有規律，并且計算、訪存交替進行的操作，可以通過預取來提升性能，讓訪存和計算并行起來。

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的Cuckoo Hashing的应用及性能优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。