memcached 最初部署時，通常與後端網路伺服器並置，使用備用 RAM 和 CPU 週期。重要的是，它在保持快速運作的同時，CPU 使用率必須保持低，否則它會影響它試圖改善的應用程式的效能。

隨著時間推移，部署樣式已改變。經常有較少的專用節點，但有較多的 RAM，但備用 CPU。除此之外，網路要求一次可以擷取數十到數百個物件，而要求延遲對整體影響較大。

這篇文章重點在於減少浪費快取空間的過期項目、一般的 LRU 改進，以及延遲一致性。

原始實作

在 1.4.x 及更早版本中，memcached 中的 LRU 是標準的雙向連結清單：有一個頭部和一個尾部。新的項目插入到頭部，驅逐從尾部彈出。如果存取一個項目，它會從其位置取消連結，然後重新連結到頭部（在此稱為「碰撞」），回到 LRU 的頂部。

沒有背景執行緒主動維護資料。如果一個項目過期，它會留在記憶體中，直到它再次被存取。在查詢過期項目時，記憶體會被釋放，並傳回 MISS 給客戶端。

過期項目只會在以下情況下移除

• 當故意刪除時
• 當透過 SET 覆寫時
• 當過期後透過 GET、ADD 等重新存取時。
• 當需要驅逐時，它會查看尾部周圍的幾個項目，以尋找過期的項目來回收，而不是驅逐實際的尾部。

早期進行了一項重要的最佳化，導致一個項目每 60 秒只會碰撞一次。因此，非常頻繁存取的項目避免了過度的互斥鎖定和變異。

即使熱門項目並非總是在 LRU 中「碰撞」，一次擷取數百個項目可能會碰撞到其中至少幾個（或潛在地全部，如果使用者從點心休息回來）。這可能會導致互斥競爭激增、延遲不均，以及伺服器上過度的 CPU 使用率。

多執行緒可擴充性受到 LRU 鎖定的嚴重限制。使用原始 LRU，擴充到 8 個工作執行緒以上很困難。一旦進行最佳化，非常讀取密集的工作負載已幾乎線性擴充到 48 個核心。

我們採取了極簡主義的方法來尋找新的演算法。程式碼變動必須相對較小，向下相容，且易於測試和驗證。最終使用者也有各種未知的負載模式，需要更通用的方法。

分段 LRU

第一項改良：我們建構了一個修改過的 LRU，其靈感來自 2Q、分段 LRU 的設計，以及 OpenBSD 檔案系統緩衝快取的命名。

LRU 被分割成四個子 LRU。每個子 LRU 都有自己的互斥鎖定。它們都由單一背景執行緒管理，稱為「LRU 維護器」，詳情如下。

每個項目都有兩個位元旗標，用來表示活動層級。

• 已擷取：如果項目曾經被要求，則設定
• 活動中：如果項目已第二次存取，則設定。當項目被提升或移動時移除。

熱門充當緩衝佇列，因為項目很可能展現強烈的時間局部性或非常短的 TTL（存活時間）。因此，項目在熱門中絕不會被提升：一旦項目到達佇列尾端，如果項目活動中（3），則會移動到溫暖；如果項目不活動（5），則會移動到冷卻。

溫暖充當掃描工作負載的緩衝，例如網路爬蟲讀取舊文章。從未被命中兩次的項目無法進入溫暖。溫暖項目有較高的機會用完其 TTL，同時也能減少鎖定競爭。如果尾端項目活動中，我們會將其提升回頭端（4）。否則，我們會將不活動的項目移動到冷卻（7）。

冷卻包含最不活動的項目。不活動的項目會從熱門（5）和溫暖（7）流動到冷卻。一旦記憶體已滿，項目會從冷卻的尾端驅逐。如果項目變得活動中，它會被排隊，以非同步方式移動到溫暖（6）。如果冷卻發生大量或大量命中，提升佇列可能會溢位，而且項目會保持不活動。在過載情況下，從冷卻提升會變成機率性的，而不是封鎖工作執行緒。

暫時充當具有非常短 TTL（2）（通常為數秒）的新項目的佇列。暫時中的項目絕不會被提升，也不會流動到其他 LRU，進而節省 CPU 和鎖定競爭。它目前預設未啟用。

熱門和溫暖 LRU 的大小主要受到所用記憶體百分比的限制，而冷卻和暫時則不受限制。熱門和溫暖有次要的尾端年齡限制，相對於冷卻的尾端年齡。這可防止非常閒置的項目不必要地持續存在於活動佇列中。

LRU 維護器執行緒

這一切都由 LRU 維護器背景執行緒串聯起來。它有一個簡單的工作：

• 反覆運算每個子 LRU，並窺探尾端項目。
• 確保每個子 LRU 都符合其限制，必要時移動項目。
• 回收過期的尾端項目。
• 處理來自冷卻 LRU 的任何非同步提升。

這有一個警告，持續過載的 SET 對於特定區塊類別可能會耗盡要驅逐的 COLD 項目。如果發生這種情況，SET 會進入「直接回收」模式，工作執行緒會在將項目從 HOT 和 WARM 推出時遭到封鎖。

摘要

除了記憶體效率外，分段 LRU 對效能有幾個主要影響。

1. 直接擷取時，項目絕不會碰撞。您可以一次擷取 500 個金鑰，而且絕不會需要等待 LRU 鎖定。
2. 項目會非同步碰撞。設定或擷取流量中的短暫爆發會導致 HOT 或 WARM 中暫時失衡。
3. 額外的互斥鎖有助於擴充寫入作業。
4. 每個項目元資料大小沒有增加。

這些系統的效率會因工作負載而異。如果您插入許多 TTL 為 60 秒的項目，並與 TTL 為 86400 (1D) 的項目混合，那麼 60 秒的項目會浪費記憶體，直到它們被擷取或降至尾端。在此同時，系統會驅逐剩餘使用時間為數小時的項目。

這仍然是一個非常有效的快取。由於它是 LRU，因此 TTL 較長的頻繁請求項目可能會留在頭部，並且可以自由地使用其 TTL。

LRU 爬蟲

此實作仍有一些未解決的問題

調整快取大小很困難。我的 RAM 太多嗎？太少嗎？中間有那麼多浪費，很難說。存取模式不一致的項目（例如：使用者外出吃午餐或睡覺）可能會導致過度遺漏。較大（多千位元組）的過期項目可以為數百個較小的項目騰出空間，或讓它們儲存更長時間。

解決這些問題導致 LRU 爬蟲，這是一種非同步瀏覽快取中項目的機制。它能夠回收過期項目，並且可以檢查整個快取或其子集。

爬蟲是一個單一背景執行緒，它將特殊爬蟲項目插入每個區塊類別中每個子 LRU 的尾端。然後，它會同時從底部到頂端，將每個爬蟲項目向後瀏覽 LRU。爬蟲會檢查它通過的每個項目，以查看它是否已過期，如果過期，則會回收。

它會查看類別 1 中的一個項目，HOT，然後查看類別 1 WARM 中的一個項目，依此類推。如果類別 5 有十個項目，而類別 1 有一百萬個，它會快速完成對類別 5 的掃描，然後花很長時間完成類別 1。

它在掃描每個子 LRU 時會建立一個 TTL 剩餘時間的直方圖。然後，它使用直方圖來決定重新掃描每個 LRU 的積極程度。例如，如果類別 1 有一百萬個 TTL 為 0 的項目，它將每小時最多掃描類別 1 一次。如果類別 5 有 100000 個項目，其中 1% 將在 5 分鐘內過期，它將排程在 5 分鐘後重新執行。如果需要，它可以每隔幾秒重新掃描一次。

排程很強大：較高的區塊類別自然有較少的項目佔用更多空間。它可以非常快速地掃描和重新掃描大型項目，以保持低死亡記憶體比率。它可以反覆掃描類別 50，即使掃描類別 1 一次需要 10 分鐘。

結合分段 LRU，LRU 爬蟲程式可能會得知「HOT」永遠不值得掃描，但 WARM 和 COLD 會產生豐碩的結果。或者相反：如果 HOT 有許多 TTL 較低的項目，則爬蟲程式可以保持其乾淨，同時避免掃描相對較大的 COLD。這有助於減少掃描工作量，即使是在單一區塊類別中。

如果我們嘗試從頭到尾遍歷雜湊表來達成此目的。一個剩餘 TTL 為 10 秒的 1MB 項目將不會再次被看到，直到雜湊表中的每個項目都一次被查看。

摘要

這個次要程序涵蓋了管理具有 TTL 資料的 LRU 大部分剩餘低效率。純粹的 LRU 沒有孔洞或過期項目的概念，而檔案系統緩衝池通常會以類似大小（例如 8k 區塊）保留資料。

使用背景程序挑選無效資料，同時自我聚焦在它可以發揮最大效益的地方，回收了幾乎所有無效記憶體。現在可以更容易地評估快取實際佔用多少記憶體。

其他功能可以而且已經建立在 LRU 爬蟲程式之上

lru_crawler metadump <classid,classid|all>
example output:
key=foo exp=1539196410 la=1539196351 cas=3 fetch=no cls=1 size=64

這個指令，採取類別 ID 清單或「全部」，將非同步列印快取中每個項目的金鑰和元資料資訊。

調整 Memcached

LRU 程式碼有幾個選項可以在執行中的執行個體上變更。

lru [tune|mode|temp_ttl] [option list]

• 「模式」flat|segmented：您可以在執行時從分段 LRU 切換到傳統 LRU 模式，反之亦然。HOT 或 WARM 中的項目將非同步排放到 COLD，而 COLD 將成為主要的 LRU。

• 「調整」：採用「HOT 百分比」、「WARM 百分比」、「最大 HOT 年齡係數」、「最大 WARM 年齡係數」作為參數。這允許您動態地使用較大或較小的 HOT 或 WARM 佇列來試驗命中率。

lru tune 10 25 0.1 2.0

在此範例中，HOT 限制在記憶體的 10%，或尾部年齡為 COLD 尾部年齡的 10%。WARM 限制在記憶體的 25%，或 COLD 尾部年齡的 200%。如果需要，LRU 維護程式將移動項目以符合新的限制。

• 「temp_ttl」ttl：設定為 -1 以停用，或高於 0 以在執行時啟用 TEMP LRU 的使用。任何以低於指定 TTL 輸入的物件將直接進入 TEMP，並保留在那裡，直到過期或以其他方式刪除。

這些都可以透過命令列啟動選項進行調整，請使用「-h」指令取得最新的啟動選項。

來源中的 doc/protocol.txt 擁有關於即時調整的最新詳細資訊。它也包含與此程式碼相關的新統計計數器的說明，這些說明大部分出現在「統計項目」輸出中。

結論

這篇文章介紹了兩項改善，它們會影響記憶體效率，並在 memcached 1.5.0 中預設啟用。

軟體社群中有許多新穎且有趣的點子，我們將持續嘗試這些點子。建立一個適用於一般工作概況的高速金鑰/值快取需要仔細評估折衷方案。這些功能的實作工作總共花了數週，但生產測試在數年間導致了微小的變更。

我們已經展示出大幅改善 memcached 記憶體效率的可能性，同時也改善了延遲概況。這是透過在背景執行緒中使用有限的 CPU 量來達成。