# Introduction

本文描述了Facebook如何利用Memcached構建並擴展分散式鍵值存儲系統，支持世界上最大的社交網絡。
- 系統每秒處理數十億請求，保存數兆條目，為超過十億用戶提供豐富的體驗。

### 主要挑戰

受歡迎且具有吸引力的社交網絡網站需要應對顯著的基礎設施挑戰。
需要滿足的需求：
1. 近乎即時的通信
2. 從多個來源動態聚合內容
3. 能夠訪問和更新非常受歡迎的內容
4. 處理每秒數百萬用戶請求的可擴展性

### 解決方案

- 將開源版Memcache改進為Memcached，並使用它作為構建分散式鍵值存儲系統的基礎。
- 系統從單集群擴展到多個地理分佈的集群。
- 這是目前世界上最大的Memcached安裝，處理每秒超過十億請求，存儲數兆條目。

### 重點
- 提出了在不同規模下出現的重要主題。
- 性能、效率、容錯和一致性在所有規模下都很重要，但在某些特定規模下需要更多的努力來達到。
- 例如，在小規模下，資料一致性更容易實現，而在大規模下，則需要更多的資料複製。
- 隨著伺服器數量增加，找到最佳通訊排程變得更加重要。

### 主要貢獻
- 描述了Facebook的Memcached架構的演變。
- 確定了提高性能和增加記憶體效率的改進措施。
- 顯著提升了在大規模運行系統的機制。
- 描述了系統在生產環境中的工作負載。

# 概述 (Overview)

### 設計考量

- 使用者消耗的內容量遠超過創建的內容量，這導致了讀取資料的工作量佔主導地位，表明快取可以帶來顯著優勢。
- 讀取操作從多種來源獲取資料，如MySQL數據庫、HDFS安裝和後端服務，這種異質性需要靈活的快取策略來儲存來自不同來源的資料。
- Memcached 基本操作
1. Memcached 提供一組簡單的操作（set、get 和 delete），使其成為大規模分散式系統中的基本組件。
2. 開源版本提供單機內存雜湊表，本文討論了如何將這個基本組件變得更高效，並用它構建能每秒處理數十億請求的分散式鍵值儲存。

### 查詢快取 (Query Cache)
- 使用 Memcache 減輕資料庫的讀取負載，具體用作需求填充的look-aside cache
- 當網頁伺服器需要資料時，首先從 Memcache 請求，如果未找到，則從資料庫或其他後端服務檢索資料並將鍵值對存入快取。
- 對於寫入請求，網頁伺服器發出SQL指令給資料庫，然後發送刪除請求給Memcache以使任何過期資料失效。
- 選擇刪除而不是更新，因為刪除操作是冪等的(即重複操作多次結果仍舊一樣)。Memcache 不是資料的master來源，因此可以逐出（evict）快取的資料。

### 通用快取 (Generic Cache)
- Memcache 還被用作更通用的鍵值儲存，例如儲存預計算的機器學習算法結果，這些結果可以被各種應用使用。
- 新服務可以輕鬆利用現有基礎設施，而無需調整、優化、配置和維護大量伺服器群。


### Memcache 系統架構
- Memcached 原本沒有伺服器之間的協調，是單伺服器運行的in-memory hash table。
- 本文描述了如何構建基於 Memcached 的分散式鍵值儲存系統，使其能在Facebook的工作負載下運行。
- 系統提供配置、聚合和路由服務，以組織 Memcached 實例進入分散式系統。

### 部署規模
- 系統部署在三個不同規模上強調的主題：
1. 單集群伺服器：讀取密集型工作負載和廣泛的扇出（fan-out）。
2. 多前端集群：需要處理資料複製。
3. 全球分佈集群：需要提供一致的用戶體驗。
### 設計目標
1. 任何更改都必須影響面向用戶或運營的問題，範圍有限的優化很少被考慮。
2. 將讀取暫時過期資料的概率作為可調參數，以換取減少對後端儲存服務的過載。

## In a Cluster: Latency and Load

本節討論了在Facebook的Memcached集群內，如何處理延遲和負載問題，以確保系統的高效運行。

### 延遲考量
延遲是影響使用者體驗的關鍵因素。
- 為了減少延遲，Facebook對Memcached系統進行了多種優化。
- 使用了consistent hashing來確保資料分佈的均衡性，避免了單一伺服器成為瓶頸。
- 在客戶端實現了複雜的邏輯，以決定資料應該存儲在哪個伺服器上，從而減少查詢延遲。


### 負載管理
為了有效管理負載，Facebook採用了多種策略：
- 資料複製：某些關鍵資料會被複製到多個伺服器，以分散讀取負載。
- 動態調整：根據負載情況動態調整伺服器資源分配，確保資源利用率最大化。
- 自動排程：使用自動化工具來排程和管理伺服器，減少人工干預，提高系統可靠性。

### 性能優化
為了進一步優化性能，Facebook進行了以下改進：
- 客戶端和伺服器之間使用了高效的通信協議，以減少通信開銷。
- 在伺服器端實現了多層快取（cache），以提高資料訪問速度。
- 採用了先進的硬體技術，如SSD和高性能網卡，以提升系統整體性能。

### 容錯和高可用性

為了確保系統的高可用性，Facebook採取了以下措施：
- 使用資料複製技術來提高容錯能力，即使某個伺服器發生故障，資料也能從其他伺服器中獲取。
- 實現了自動故障轉移機制，當某個伺服器出現問題時，系統能自動將請求轉移到其他伺服器，確保服務不中斷。

### 持續改進
Facebook不斷監控系統運行情況，並根據數據進行優化和改進：
- 收集和分析系統運行數據，找出潛在的性能瓶頸和改進空間。
- 定期進行系統升級和優化，確保系統能夠應對不斷增長的使用者需求。

# 區域內：資料複製 (In a Region: Replication)

本節探討了在區域內實現資料複製的方法和挑戰，以確保系統的高可用性和一致性。
資料複製的必要性

- 資料複製的主要目的是提高系統的容錯能力和讀取性能。
- 透過將資料複製到多個伺服器，可以分散讀取負載，避免單一伺服器成為瓶頸。
- 一致性考量
- 在分散式系統中，保持資料的一致性是個挑戰。
- Facebook 使用了最終一致性模型（eventual consistency），即資料最終會在所有複製節點達到一致，但不保證即時一致。
- 為了在高流量下保持一致性，系統引入了多種技術，包括資料版本控制和衝突解決機制。

### 資料同步

- Facebook 採用了異步複製（asynchronous replication）的方法，將資料的寫入操作先記錄在主伺服器，然後再傳播到副本伺服器。
- 異步複製減少了寫入操作的延遲，但會帶來短暫的資料不一致性。

### 複製拓撲結構
- 系統的複製拓撲結構設計考量了效率和可靠性。
- 多層次複製：將資料分層次地複製到不同的伺服器，確保在某些伺服器故障時，資料仍能從其他伺服器獲取。
- 地理分佈：將資料複製到地理上分散的伺服器，以提高跨區域的數據訪問性能。

### 複製機制

- Facebook 使用了基於日誌的複製機制（log-based replication），即將資料變更記錄在日誌中，然後依次應用到副本伺服器。
- 這種機制能夠有效追蹤和同步資料變更，確保資料的一致性。

### 故障處理
- 為了應對伺服器故障，系統實現了自動故障轉移機制（failover mechanism）。
- 當主伺服器發生故障時，系統能自動將讀寫操作轉移到副本伺服器。
- 故障修復後，再將資料同步回主伺服器，恢復正常運行。


# 跨區域：一致性 (Across Regions: Consistency)

本節探討了在跨區域環境中如何保持資料的一致性，確保用戶在不同地理位置都能獲得一致的資料體驗。
### 一致性挑戰
- 跨區域分散式系統面臨的主要挑戰之一是資料一致性。
- 不同地理位置之間的通信延遲和網絡不穩定性，會導致資料同步的延遲和潛在的資料不一致性。

### 最終一致性模型 (Eventual Consistency)
- Facebook 採用了最終一致性模型，這意味著資料在某個時間點可能是不一致的，但最終會達到一致。
- 這種模型在處理大量讀寫操作時，可以提高系統的可伸縮性和性能。

### 跨區域資料同步
- 資料在區域內通過異步複製進行同步，確保在區域內的資料讀取延遲最小化。
- 跨區域資料同步則採用更多的延遲容忍策略，保證資料最終一致。

### 一致性協議
- Facebook 使用了一致性協議來管理跨區域的資料一致性。
- Paxos協議和Raft協議等分散式一致性算法被用來確保在多個伺服器之間達成一致。
- 這些協議可以在面臨網絡分區和伺服器故障的情況下，依然保持系統的一致性。

### 資料衝突解決

- 當發生資料衝突時，系統需要一套有效的衝突解決機制。
- Facebook 使用了基於版本的衝突解決策略，將資料版本號作為衝突判斷的依據。
- 衝突發生時，系統會選擇最新的資料版本或合併多個版本的資料，確保最終一致。

### 一致性優化
- 為了在提高一致性的同時不犧牲性能，Facebook 採用了多種優化策略：
- 局部寫操作：將大部分寫操作局限於區域內，僅將關鍵資料同步到其他區域，減少跨區域同步的頻率和延遲。
- 讀寫分離：將讀操作優先分配到最近的資料副本，減少跨區域讀取的延遲。
- 快取（Cache）優化：使用區域內的快取來加速資料訪問，減少跨區域讀取的次數。

# 單伺服器改進 (Single Server Improvements)

本節介紹了在單一伺服器上進行的改進措施，以提升Memcached的性能和可靠性。
### 記憶體管理

- Facebook 改進了 Memcached 的記憶體管理，以更有效地利用可用記憶體。
- 使用了動態記憶體分配策略，使得記憶體可以根據需要在不同的快取項目之間重新分配。
- 引入了垃圾回收機制，定期清理不再使用的記憶體，防止記憶體洩漏。

### 多執行緒支援
- 為了充分利用多核心處理器的能力，Facebook 為 Memcached 添加了多執行緒支援。
- 每個執行緒都可以處理來自客戶端的請求，從而提高了伺服器的並行處理能力。
- 使用鎖分離技術（lock striping）來減少執行緒之間的鎖競爭，提高執行效能。

### 高效網路通信
- 改進了伺服器與客戶端之間的網路通信，以減少通信延遲和開銷。
- 使用了非阻塞I/O和事件驅動的架構，確保伺服器可以高效地處理大量並發請求。
- 優化了TCP連接的管理，減少了連接建立和拆除的開銷。

### 儲存優化
- 改進了資料儲存的方式，以提高讀寫性能和資料可靠性。
- 使用了SSD作為儲存媒介，取代傳統的HDD，顯著提高了資料讀寫速度。
- 實現了資料快取（cache）機制，將常用資料儲存在高速快取中，減少對底層儲存的訪問次數。

### 資料壓縮
- 引入了資料壓縮技術，以減少資料的儲存空間和傳輸開銷。
- 將大資料塊進行壓縮後再儲存，節省記憶體空間。
- 在客戶端讀取資料時，進行解壓縮操作，確保資料完整性和可用性。

### 故障恢復
- 加強了單伺服器的故障恢復能力，確保在發生硬體故障或軟體錯誤時，系統可以快速恢復運行。
- 實現了自動重啟和故障轉移機制，當伺服器發生故障時，系統會自動重啟並重新載入資料。
- 使用資料複製和備份技術，確保在發生災難性故障時，資料可以從備份中恢復。

# Memcache 工作負載 (Memcache Workload)

本節介紹了Facebook在使用Memcache時遇到的各種工作負載類型及其特點。

### 工作負載特點
- Facebook的Memcache工作負載主要分為兩類：查詢快取和通用快取。

### 查詢快取 (Query Cache)
- 查詢快取用於減少資料庫讀取負載，將結果快取起來以便快速訪問。
- 查詢快取主要處理高頻讀取操作，減少對後端資料庫的壓力。
- 資料在快取中的存活時間（TTL, Time To Live）通常較短，因為查詢結果可能頻繁變化。
- 典型的工作負載模式是多讀少寫，讀取操作佔大多數。

### 通用快取 (Generic Cache)
- 通用快取用於存儲各種臨時資料和計算結果，供不同的應用使用。
- 這類快取的資料範圍廣泛，可能包括計算密集型應用的中間結果、機器學習模型的預計算結果等。
- 通用快取的TTL較長，因為這些資料不會頻繁變化。
- 工作負載模式較為多樣，包括讀取和寫入操作。

### 工作負載分析
- 對於查詢快取，讀取操作通常佔總操作的95%以上，寫入操作僅佔5%以下。
- 快取命中率（cache hit rate）是衡量查詢快取效果的重要指標。高命中率表示大部分查詢可以直接從快取中獲取，減少了後端負載。
- 對於通用快取，讀取和寫入操作的比例因應用而異，但通常寫入操作較多。
- 通用快取需要考慮資料一致性和持久性，以確保資料不會因伺服器故障而丟失。

### 性能優化策略
- 為了應對不同的工作負載，Facebook採用了多種性能優化策略：
- 動態調整快取大小和TTL，以適應不同應用的需求。
- 優化快取替換算法，確保最常用的資料能保留在快取中，減少快取淘汰率（cache eviction rate）。
- 使用記憶體和SSD結合的混合儲存方式，提高快取的存取速度和容量。

### 快取一致性
- 快取一致性是維持資料正確性的重要挑戰。
- Facebook使用多種技術確保快取的一致性，包括版本控制、資料標記和自動失效機制。
- 當資料更新時，會及時刪除或更新相關快取，以確保用戶獲取到最新的資料。

# 結論 (Conclusion)

本文介紹了Facebook如何利用Memcached構建和擴展分散式鍵值儲存系統，支持全球最大的社交網絡服務。
### 成功經驗
- Facebook的Memcached系統在大規模應用中取得了顯著成功，展示了多種有效的技術和策略：
- 高效的記憶體管理和多執行緒支援顯著提升了單伺服器性能。
- 使用consistent hashing、非同步複製和分散式一致性協議等技術，確保了系統的高可用性和資料一致性。
- 通過多層次的資料快取和優化策略，減少了後端資料庫的負載，提高了整體系統的response速度。

### 持續改進
Facebook不斷監控和優化Memcached系統，以應對不斷增長的用戶需求和多變的工作負載。
實時監控和動態調整技術，確保系統在高負載下仍能穩定運行。
持續研究和引入新的技術和方法，以提高系統的可伸縮性和可靠性。

### 挑戰與未來
雖然在應用中取得了很大的成功，但仍有一些挑戰需要面對：
1. 如何在保持高一致性的同時進一步提高系統性能。
2. 如何更高效地管理和儲存日益增長的海量資料。
3. 面對不斷變化的用戶需求，如何靈活調整系統架構和配置。