我們在進行 Mc 架構剖析時，除了學習 Mc 的系統架構、網絡模型、狀態機外，還對 Mc 的 slab 分配、Hashtable、LRU 有了簡單的了解。本節課，將進一步深入學習這些知識點。
接下來，進入 Memcached 進階的學習。會講解 Mc 是如何進行 key 定位，如何淘汰回收過期失效 key 的，還將分析 Mc 的內存管理 slab 機制，以及 Mc 進行數據存儲維護的關鍵機理，最后還會對 Mc 進行完整的協議分析，并以 Java 語言為例，介紹 Mc 常用的 client，以及如何進行調優及改進。
key 定位
哈希表
Mc 將數據存儲在 Item 中，然后這些 Item 會被 slabclass 的 4 個 LRU 管理。這些 LRU 都是通過雙向鏈表實現數據記錄的。雙向鏈表在進行增加、刪除、修改位置時都非常高效，但其獲取定位 key 的性能非常低下，只能通過鏈表遍歷來實現。因此，Mc 還通過 Hashtable，也就是哈希表，來記錄管理這些 Item，通過對 key 進行哈希計算，從而快速定位和讀取這些 key/value 所在的 Item，如下圖所示。
哈希表也稱散列表，可以通過把 key 映射到哈希表中的一個位置來快速訪問記錄，定位 key 的時間復雜度只有 O(1)。Mc 的哈希表實際是一個一維指針數組，數組的每個位置稱作一個 bucket，即一個桶。性能考慮的需要，Mc 的哈希表的長度設置為 2 的 N 次方。Mc 啟動時，默認會構建一個擁有 6.4萬 個桶的哈希表，隨著新 key 的不斷插入，哈希表中的元素超過閥值后，會對哈希表進行擴容，最大可以構建 2 的 32 次方個桶的哈希表，也就是說 Mc 哈希表經過多次擴容后，最多只能有不超過 43億 個桶。
哈希表設計
對于哈希表設計，有 2 個關鍵點，一個是哈希算法，一個是哈希沖突解決方案。Mc 使用的哈希算法有 2 種，分別是 Murmur3 Hash 和 Jenkins Hash。Mc 當前版本，默認使用 Murmur3 Hash 算法。不同的 key 通過 Hash 計算，被定位到了相同的桶，這就是哈希沖突。Mc 是通過對每個桶啟用一個單向鏈表，來解決哈希沖突問題的。
定位 key
Memcached 定位 key 時，首先根據 key 采用 Murmur3 或者 Jenkins 算法進行哈希計算，得到一個 32 位的無符號整型輸出，存儲到變量 hv 中。因為哈希表一般沒有 2^32 那么大，所以需要將 key 的哈希值映射到哈希表的范圍內。Mc 采用最簡單的取模算法作為映射函數，即采用 hv%hashsize 進行計算。由于普通的取模運算比較耗時，所以 Mc 將哈希表的長度設置為 2 的 n 次方，采用位運算進行優化，即采用 hv&hashmask 來計算。hashmask 即 2 的 n 次方 減 1。
定位到 key 所在的桶的位置后，如果是插入一個新數據，則將數據 Item 采用頭部插入法插入桶的單向鏈表中。如果是查找，則輪詢對應哈希桶中的那個單向鏈表，依次比對 key 字符串，key 相同則找到數據 Item。
如果哈希表桶中元素太多，這個鏈表輪詢耗時會比較長，所以在哈希表中元素達到桶數的 1.5 倍之后，Mc 會對哈希表進行 2 倍擴容。由于哈希表最多只有 43 億左右個桶，所以性能考慮，單個 Mc 節點最多存儲 65億 個 key/value。如果要存更多 key，則需要修改 Mc 源碼，將最大哈希，即 HASHPOWER_MAX， 進行調大設置。
哈希表擴容
當 Mc 的哈希表中，Item 數量大于 1.5 倍的哈希桶數量后，Mc 就對哈希表進行擴容處理。如下圖所示，Mc 的哈希擴容是通過哈希維護線程進行處理的。準備開始擴容時，哈希維護線程會首先將所有 IO 工作線程和輔助線程進行暫停，其中輔助線程包括 LRU 維護線程、slab 維護線程、LRU 爬蟲線程。待這些線程暫停后，哈希維護線程會將當前的主哈希表設為舊哈希表，然后將新的主哈希表擴容之前的 2 倍容量。然后，工作線程及輔助線程繼續工作，同時哈希維護線程開始逐步將 Item 元素從舊哈希表遷移到主哈希表。
Mc 在啟動時，會根據設置的工作線程數，來構建 一個 Item 鎖哈希表，線程越多，構建的鎖哈希表越大，對于 4 個線程，鎖哈希表有 4096 個桶，對于 10 個線程，鎖哈希表會有 8192 個桶，Item 鎖哈希表最多有 32k 個桶，1k 是 1024，即最多即 32768 個桶。Mc 的鎖哈希表中，每個桶對應一個 Item 鎖，所以 Mc 最多只有 32768 個 Item 鎖。
Mc 哈希表在讀取、變更以及擴容遷移過程中，先將 key hash 定位到 Item 鎖哈希表的鎖桶，然后對 Item 鎖進行加鎖，然后再進行實際操作。實際上，除了在哈希表，在其他任何時候，只要涉及到在對 Item 的操作，都會根據 Item 中的 key，進行 Item 哈希鎖桶加鎖，以避免 Item 被同時讀寫而產生臟數據。Mc 默認有 4096 個鎖桶，所以對 key 加鎖時，沖突的概率較小，而且 Mc 全部是內存操作，操作速度很快，即便申請時鎖被占用，也會很快被釋放。
Mc 哈希表在擴容時，哈希表維護線程，每次按 桶鏈表緯度 遷移，即一次遷移一個桶里單向鏈表的所有 Item 元素。在擴容過程中，如果要查找或插入 key，會參照遷移位置選擇哈希表。如果 key 對應的哈希桶在遷移位置之前，則到新的主哈希表進行查詢或插入，否則到舊哈希表進行查詢和插入。待全部擴容遷移完畢，所有的處理就會全部在新的主哈希表進行。
)
