內存管理，是架構師的基本功之一。如何掌握這項基本功，最好的方法是和開源的項目學習。memcache的內核設計，值得每一個架構師借鑒。

第一部分：知其然

關于memcache一些基礎特性，架構師必須知道：

• mc的核心職能是KV內存管理，value存儲最大為1M，它不支持復雜數據結構（哈希、列表、集合、有序集合等）；
• mc不支持持久化；
• mc支持key過期；
• mc持續運行很少會出現內存碎片，速度不會隨著服務運行時間降低；
• mc使用非阻塞IO復用網絡模型，使用監聽線程/工作線程的多線程模型；

memcache的這些特性，成竹在胸了嗎？

第二部分：知其原理(why, what)

第一部分，只停留在使用層面，除此之外，架構師還必須了解原理。

(1) memcache為什么不支持復雜數據結構？為什么不支持持久化？

業務決定技術方案，mc的誕生，以“以服務的方式，而不是庫的方式管理KV內存”為設計目標，它顛覆的是，KV內存管理組件庫，復雜數據結構與持久化并不是它的初衷。

當然，用“顛覆”這個詞未必不合適，庫和服務各有使用場景，只是在分布式的環境下，服務的使用范圍更廣。設計目標，誕生背景很重要，這一定程度上決定了實現方案，就如redis的出現，是為了有一個更好用，更多功能的緩存服務。

(2) memcache是用什么技術實現key過期的？

懶淘汰(lazy expiration)。

(3) memcache為什么能保證運行性能，且很少會出現內存碎片？

提前分配內存。

(4) memcache為什么要使用非阻塞IO復用網絡模型，使用監聽線程/工作線程的多線程模型，有什么優缺點？

目的是提高吞吐量。多線程能夠充分的利用多核，但會帶來一些鎖沖突。

第三部分：知其所以然，知其內核(how)

一個對技術內核充滿“好奇心”的架構師，必須了解細節，掌握內核。

畫外音：本文剛剛開始。

(1) memcache是什么實現內存管理，以減小內存碎片，是怎么實現分配內存的？

開講之前，先解釋幾個非常重要的概念：

• chunk：它是將內存分配給用戶使用的最小單元。
• item：用戶要存儲的數據，包含key和value，最終都存儲在chunk里。
• slab：它會管理一個固定chunk size的若干個chunk，而mc的內存管理，由若干個slab組成。

畫外音：為了避免復雜性，本文先不引入page的概念了。

如上圖所示，一系列slab，分別管理128B，256B，512B…的chunk內存單元。

將上圖中管理128B的slab0放大：

能夠發現slab中的一些核心數據結構是：

• chunk_size：該slab管理的是128B的chunk；
• free_chunk_list：用于快速找到空閑的chunk；
• chunk[]：已經預分配好，用于存放用戶item數據的實際chunk空間；

畫外音：其實還有lru_list。

(2) 假如用戶要存儲一個100B的item，是如何找到對應的可用chunk的呢？

會從最接近item大小的slab的chunk[]中，通過free_chunk_list快速找到對應的chunk，如上圖所示，與item大小最接近的chunk是128B。

(3) 為什么不會出現內存碎片呢？

拿到一個128B的chunk，去存儲一個100B的item，余下的28B不會再被其他的item所使用，即：實際上浪費了存儲空間，來減少內存碎片，保證訪問的速度。

畫外音：理論上，內存碎片幾乎不存在。

(4) memcache通過slab，chunk，free_chunk_list來快速分配內存，存儲用戶的item，那它又是如何快速實現key的查找的呢？

沒有什么特別算法：

• 通過hash表實現快速查找；
• 通過鏈表來解決沖突；

用最樸素的方式，實現key的快速查找。

(5) 隨著item的個數不斷增多，hash沖突越來越大，hash表如何保證查詢效率呢？

當item總數達到hash表長度的1.5倍時，hash表會動態擴容，rehash將數據重新分布，以保證查找效率不會不斷降低。

(6) 擴展hash表之后，同一個key在新舊hash表內的位置會發生變化，如何保證數據的一致性，以及如何保證遷移過程服務的可用性呢（肯定不能加一把大鎖，遷移完成數據，再重新服務吧）？

哈希表擴展，數據遷移是一個耗時的操作，會有一個專門的線程來實施，為了避免大鎖，采用的是“分段遷移”的策略。

當item數量達到閾值時，遷移線程會分段遷移，對hash表中的一部分桶進行加鎖，遷移數據，解鎖：

• 一來，保證不會有長時間的阻塞，影響服務的可用性；
• 二來，保證item不會在新舊hash表里不一致；

(7) 新的問題來了，對于已經存在于舊hash表中的item，可以通過上述方式遷移，那么在item遷移的過程中，如果有新的item插入，是應該插入舊hash表還是新hash表呢？

memcache的做法是，判斷舊hash表中，item應該插入的桶，是否已經遷移至新表中：

• 如果已經遷移，則item直接插入新hash表；
• 如果還沒有被遷移，則直接插入舊hash表，未來等待遷移線程來遷移至新hash表；

(8) 為什么要這么做呢，不能直接插入新hash表嗎？

memcache沒有給出官方的解釋，樓主揣測，這種方法能夠保證一個桶內的數據，只在一個hash表中（要么新表，要么舊表），任何場景下都不會出現，舊表新表查詢兩次，以提升查詢速度。

(9) memcache是怎么實現key過期的，懶淘汰(lazy expiration)具體是怎么玩的？

實現“超時”和“過期”，最常見的兩種方法是：

• 啟動一個超時線程，對所有item進行掃描，如果發現超時，則進行超時回調處理；
• 每個item設定一個超時信號通知，通知觸發超時回調處理；

這兩種方法，都需要有額外的資源消耗。

mc的查詢業務非常簡單，只會返回cache hit與cache miss兩種結果，這種場景下，非常適合使用懶淘汰的方式。

懶淘汰的核心是：

• item不會被主動淘汰，即沒有超時線程，也沒有信號通知來主動檢查；
• item每次會查詢(get)時，檢查一下時間戳，如果已經過期，被動淘汰，并返回cache miss；

舉個例子，假如set了一個key，有效期100s：

• 在第50s的時候，有用戶查詢(get)了這個key，判斷未過期，返回對應的value值；
• 在第200s的時候，又有用戶查詢(get)了這個key，判斷已過期，將item所在的chunk釋放，返回cache miss；

這種方式的實現代價很小，消耗資源非常低：

• 在item里，加入一個過期時間屬性；
• 在get時，加入一個時間判斷；

內存總是有限的，chunk數量有限的情況下，能夠存儲的item個數是有限的，假如chunk被用完了，該怎么辦？

(10) 仍然是上面的例子，假如128B的chunk都用完了，用戶又set了一個100B的item，要不要擠掉已有的item？

要。

這里的啟示是：

• 即使item的有效期設置為“永久”，也可能被淘汰；
• 如果要做全量數據緩存，一定要仔細評估，cache的內存大小，必須大于，全量數據的總大小，否則很容易踩坑；

(11) 擠掉哪一個item？怎么擠？

這里涉及LRU淘汰機制。

如果操作系統的內存管理，最常見的淘汰算法是FIFO和LRU：

• FIFO(first in first out)：最先被set的item，最先被淘汰；
• LRU(least recently used)：最近最少被使用(get/set)的item，最先被淘汰；

使用LRU算法擠掉item，需要增加兩個屬性：

• 最近item訪問計數；
• 最近item訪問時間；

并增加一個LRU鏈表，就能夠快速實現。

畫外音：所以，管理chunk的每個slab，除了free_chunk_list，還有lru_list。

內存管理，你學廢了嗎？

知其然，知其所以然。

思路比結論更重要。