閱讀筆記：MemC3
並發布谷鳥哈希（Concurrent Cuckoo Hashing）
C3使用並發布谷鳥哈希表解決上面提到的第1和第3個問題。並發布谷鳥哈希是無鎖的開放定址哈希表。布谷鳥哈希表的查找複雜度為常數，插入的平均複雜度為常數。又由於是開放定址的，其空間利用率能達到90%，也即是載荷因子可以設置的大一點（通常鏈式哈希表的載荷因子（load factor）比較小，因為如果載荷因子比較大的，會出現很多長鏈影響性能）。無鎖的布谷鳥哈希是利用版本號實現的樂觀鎖（其實沒有鎖，靠的是原子操作和重試）。- 布谷鳥哈希表
首先介紹布谷鳥哈希表。布谷鳥哈希表與一般的開放定址哈希表不同之處在於，它自己有兩個哈希函數，也就是每一個鍵都在表裡有兩個不同的槽，也就是每一個鍵都有潛在的兩個位置進行存儲。舉個例子。假如有一個布谷鳥哈希表大小為8。有一個鍵為k=「aaa」，h1和h2是不同的哈希函數，那麼這個k就能存在a) h1(k) % 8 = 888 % 8 = 0, b) h2(k) % 8 = 889 % 8 = 1，也就是第0個槽和第1個槽中。至於具體選哪個槽和如果碰撞了怎麼辦，下面繼續講。但是有一點能夠明確，使用兩個哈希函數找到了槽，如果在槽里沒有找到對應的鍵，那這個鍵一定不存在於哈希表中。
那麼查找就簡單了，使用兩個哈希函數進行哈希，找到槽，直接看槽內有沒有就行。查找複雜度無疑是常數。
插入則略微有些複雜。基本流程是：
1. 使用h1和h2進行哈希，看看兩個槽位是否為空，如果有一個不為空，則插入。
2. 如果兩個槽位都不為空，則任選一個，把裡面存的鍵拿出來，把當前鍵插入（這樣保證了通過h1或者h2哈希能找到當前鍵）。對於拿出的鍵，跳至第1步（可以優化，此處簡化為1，2為了方便說明）。
當然這兩步有可能無限進行下去，或者執行的次數過多。無限進行是因為哈希函數在跳轉的路徑上創造了環；而執行次數過多可能是因為表裡的數據過多。因此通常要限制執行的步數，超過步數則擴大表的規模，同時重新哈希（實際上布谷鳥哈希的發明者認為除非表已經滿了，否則甚至不用擴大表的規模，重新哈希能找到一個性能更高的鍵分布）。這個執行次數的上限是一個經驗值。
插入的平均複雜度為常數。
刪除和查找類似，複雜度為常數。
- C3的布谷鳥哈希表
C3對布谷鳥哈希表進行了修改。原始的布谷鳥哈希表就是一個長數組，一些變種使用兩個數組，而C3的哈希表是一個大數組，每一個數組槽其實由固定大小的數組構成，示意圖如下：
這麼設計的好處有二，第一個是減少碰撞帶來的代價，畢竟現在一個哈希值對應了4個槽，那麼一個鍵有8個潛在槽可以插入；第二個是如果能確保4個連續槽是內存對其的，且大小小於等於CPU Cache line的長度，那麼這四個連續槽一次會被讀入處理器緩存，也就是說對任意一個槽訪問都是一個處理器時鐘可以完成的。傳統的鏈表遍歷需要根據指針回到內存，可能需要50個時鐘以上才能再把數據讀入緩存。為了壓縮連續四個槽的大小，使之能存入緩存的一行中，同時為了存可變長的鍵，每一槽實際上沒有存真正的鍵值對，而是存了一個部分哈希值和一個指向真正鍵值對的指針（如果部分哈希值和指針是16位元組，那麼4槽共64位元組，如果部分哈希值和指針是8位元組，則4槽32位元組）。部分哈希值的計算方法論文沒有提，但是給了一個文獻的鏈接，博主也沒有研究。不過可以確定的部分哈希值的性質有兩點：1）即便兩個不同的鍵在同一個哈希函數下產生了碰撞，也就是它們都會進行一個連續4槽位檢索，部分哈希值有很大機會區分兩者；2）部分哈希值也有可能碰撞。所以其實這個部分哈希值（tag）在這起了一個Bloom Filter的作用，即不匹配一定不是，匹配也不一定是，還得去對應鍵值對里做鍵匹配。
假定表已讀入緩存中，這種哈希表的查找，最壞是8次緩存訪問+8次內存訪問，可以理解為常數。
對於插入，和原始布谷鳥哈希類似，不過這次變成了8槽而不是2槽了。
這種設計對鏈式結構和開放地址的單數組式做出了妥協，努力降低兩者的缺點，保持兩者優點。例如開放式的做法能提高空間利用率（因為會一直跳，直到找到一個空槽或重新哈希）。開放式帶來的碰撞後的代價被4槽的設置緩解了，而4槽也克服了長度為O(n)的鏈式的缺點，同時部分哈希值和指針的設定解決了可變長鍵的問題，同時使得4個槽能一次放入緩存中。
此外，這個部分哈希值的使用還有一些值得研究的地方。包括為何兩個部分哈希值可以通過兩個哈希函數直接互算，但是需要讀另一篇論文，所以在此不表。
- C3的並發布谷鳥哈希表
一般的並發安全的靠的是鎖。如果靠鎖的話，無論是對哈希表進行全局鎖，還是對每一連續槽位進行單位鎖，還得是讀寫鎖，開銷都太大了。更別提對緩存置換的管理，也得加鎖。那麼性能最好還得無鎖才行。BWTree這篇文章就介紹過一個無鎖的並發安全數據結構。
C3這裡使用了樂觀鎖（其實不是鎖，理解方便起見的命名）。這裡再多提一下，由於論文使用的主要是以讀為主的Benchmark （5%或10%的寫，其餘是讀），所以讀的負擔最重。在這種前提下採用了樂觀鎖，否則可能得採用悲觀鎖。所謂樂觀，指的是在一系列操作完成後才檢查是否線程安全；所謂悲觀，是指每一步都要檢查是否線程安全，一旦認定不安全就回退。
先簡單介紹一下樂觀鎖的基本原理。
假設我們要保護並發環境下的一個數據結構，簡單一點直接用常見的鎖加上去，如果不用鎖的話，也得有個東西，要讓線程意識到其它線程的存在，特別是要意識到寫線程的存在。 比方說我們可以把鎖替換成一個bool變數，確保對這個變數的改變是原子的（處理器提供了相應的指令，在編程語言層面直接就可以使用）。那麼某個線程可以將鎖設置成true，其它線程就能意識到它存在了。工作流程如下：
- 線程原子查看變數，如果是假，將其原子修改成真。如果修改成功，那麼就獲得數據訪問權（其實也就是獲得了鎖）。如果修改失敗，那麼進入for循環
- 接1，如果查看為真，說明有線程在訪問數據，則for循環持續查看變數。
- 如果訪問數據的線程結束，將變數原子修改為假。
這樣我們就得到了一個沒有用鎖，但是實際和鎖的機理一樣的並發安全的代碼，只不過這個設計跟有鎖一樣糟糕。原因有二：
- 只有一個線程能訪問數據。
- 其它線程不得不忙等待。
那我們進一步想想，為什麼不能讓多個線程同時訪問數據吶，比如如果有多個讀的話，它們完全可以同時讀，如果有一個寫多個讀，那麼讓寫排它的進行寫，寫完一大批讀的直接進去讀，按理來說這樣的吞吐才最大化嘛。恭喜，這樣就我們就得到了一個讀寫鎖^_^。只是，能只用原子操作實現讀寫鎖么？答案是不能（或者博主認為不能）。原子操作是用於單變數的，沒有同時確保對多個變數進行原子操作的方法存在（當然你可以先用一個變數來保護原本的多個變數，不過這樣又跟鎖一樣了）。而通常讀寫鎖要依賴於兩個線程安全的計數器。
好，那我們就引入我們的正題，我們要用原子操作實現類似於讀寫鎖的機制，確保讀可以並發，同時消除「讀寫」衝突和「寫寫」衝突。
首先，我們設定一個變數，可以是一個無限長的數（理論上）。讀的線程只原子查看這個數，而寫線程可以原子修改這個數，這個變數用來保護我們的數據。假定這個數初始化為0。我們規定：
- 如果要寫線程要寫，先得來看變數，如果變數為偶數，那麼就原子加1（相當於獲得了鎖），然後可以寫；如果變數為奇數，那麼說明有已經有寫線程在寫，因此需要循環等待。
- 對於讀線程要讀，首先也得看變數，如果發現變數為奇數，那麼說明有寫線程在寫，如果去讀可能會讀到臟數據，所以循環等待；如果發現變數為偶數，那麼記下這個數字，然後去讀，當讀完結束後，再對比變數當前值，如果與記錄值不符，說明有寫變數來改過（或者正在改），有可能已經讀到了臟數據，那麼就放棄當前讀到的數據，重新循環。
這個就是樂觀鎖，它所依賴的這個變數，通常叫做版本號version number，也有用time stamp，也就是凡事能體現出時序關係的。
並發布谷鳥哈希表用了一個稍微複雜的版本，來確保有連續槽位里的數據交換的並發安全，這裡不再細講。
並發緩存管理（Concurrent Cache Management）
Memcached為了減少大量malloc和free產生的內存碎片，採用了特殊的優化的模式。它先分配很多塊，每塊1MB，在不塊里，進行了不同大小的桶的劃分。例如有兩個塊，共2MB，一個塊里可以劃分1KB的桶，另一塊劃分32KB的桶。對於相同大小桶的塊，用雙向鏈表進行連接，使用LRU進行管理。其問題在於，當存儲小數據對象時，雙鏈表指針和另外一些保證並發的數據結構的開銷，佔總使用內存比例過大（有的時候超過了50%）；對於基於鏈表的LRU的並發安全的保證，要靠鎖住整個鏈表，所有相關操作都被迫成為單線程模式，性能很差。
論文里採用了近似LRU置換法，並且配合併發布谷鳥哈希，實現了相對高效的內存管理。
近似LRU置換是對每一個桶集，用一個循環數組來管理，數組的基本單位是位。每一位是1，表示對應的桶最近被用過，0表示沒有。那麼對於內存的操作: 插入，查詢和置換來講，插入和查詢負責將對應的位設置為1，而置換會從循環數組某處開始，逐位查找，遇到0就選定對應桶進行置換，遇到1就把1變為0，然後看下一位。
這種方法實現了近似LRU的效果，同時空間利用率大大提高。
為了避免在置換時導致讀線程讀到臟數據，版本號在這裡被使用，用來阻止讀線程讀到被置換的數據。
推薦閱讀：
TAG:並發並行與分散式系統 |