本文簡要闡述libcuckoo項目的兩篇論文基礎。如有錯漏之處，歡迎指出一起讨論交流。
論文1
《MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing》
這篇論文主要講了在多線程模式下如何提升cuckoo hash table的吞吐。
問題
傳統hash表在并發效率上并不高，使用連結清單解決哈希沖突效率低，使用分shard的模式并不能提升熱點負載。
改進一：Tag-based Lookup/Insert
kv不存儲在hash表中，hash表的每個slot隻存儲 對這個key的 tag 和真實存儲這個key的指針。如此一次可讀取單個bucket内的所有slot資訊，對cache line也十分友好。
查找過程優先比較tag，tag命中後再全比較key。
同時提供了 主bucket id和備 bucket id的函數公式計算，可通過tag加其中一個主bucket id推算出備bucket id。友善查找移動合适的bucket。
改進二：Concurrent Cuckoo Hashing
通過DFS算法找到key 遷移bucket的路線圖，查找過程非互斥，找到之後再嘗試從最後的key開始往前挪動，挪動的過程才是互斥的行為。可以查找多條路徑，找到最優的路徑移動bucket。
每個bucket有對應的一個原子版本号，對應這個bucket下的所有slot，本質上是lock striping。雖然粒度粗了，但是和每個slot都有版本号相比，減少了記憶體消耗。
在此基礎上實作了樂觀鎖，每個insert之前先對版本号+1，完成之後再對版本号+1。每個讀操作之前先讀取版本号，如果是奇數，說明有insert正在進行，放棄重試。如果是偶數，再讀取之後再重新擷取一下版本号，如果版本号已經發生了改變，放棄重新擷取。
改進三：Clock LRU
傳統的LRU算法會使用雙向連結清單來實作，通過移動連結清單來計算出最近通路的key。這種方法空間使用率低。
使用一個環形的bit資料結構來替換雙向連結清單。每個bit代表了slot的位置，當有insert/update發生時，這個slot的bit被置為1。有個獨立的evict掃描器，從環形bit開始掃描，遇到為1的置為0，繼續向前掃描，遇到0的則将對應的slot的資料設定為需要淘汰。淘汰的過程中也使用上述的樂觀鎖，與insert/update一緻，避免髒讀。
論文2
《Algorithmic Improvements for Fast Concurrent Cuckoo Hashing》
這篇論文是基于上一篇論文提出的進一步優化提高吞吐量。其中關于HTM部分的優化本文略過。
改進一：BFS
将DFS 路徑查找改成BFS，盡量找到最短的路徑。
論文測試出最适合的單個bucket最适合的slot個數是8，
論文在讀和寫吞吐的平衡中找到最合适的桶深度為8，8個slot會超過一個cache line，論文認為可一次讀取兩個cache line，經實踐是最優配置。
改進二：Fine-grained Locking
論文1中當需要挪動bucket時，對路徑圖中key的bucket都提前加上了鎖，鎖的力度太大。同時讀的時候如果發生更改，每次都需要重試，很容易發生了活鎖。
由此論文2提出更細粒度的鎖，使用spinlock替換版本号實作lock-striped。對于cuckoo hash來說，無論如何移動bucket，最終資料的操作粒度在主備bucket之中操作，是以在lookup/insert過程中，都細粒度到隻是對兩個bucket的操作，每次都是擷取兩個bucket的鎖。
結束語
雲資料庫Redis版（ApsaraDB for Redis）是一種穩定可靠、性能卓越、可彈性伸縮的資料庫服務。基于飛天分布式系統和全SSD盤高性能存儲，支援主備版和叢集版兩套高可用架構。提供了全套的容災切換、故障遷移、線上擴容、性能優化的資料庫解決方案。歡迎各位購買使用：
阿裡雲redis