鍵值儲存（key-value store），也稱為鍵值資料庫，是一種非關聯式資料庫。每個唯一識別符以鍵的形式儲存，並關聯一個值。這種資料配對被稱為「鍵值（key-value）」對。

在鍵值對中，鍵必須是唯一的，與鍵關聯的值可以透過鍵來存取。鍵可以是純文字或雜湊值。基於效能的考量，較短的鍵效果更好。鍵長什麼樣子呢？以下是一些範例：

• 純文字鍵：「last_logged_in_at」
• 雜湊鍵：253DDEC4

鍵值對中的值可以是字串、清單、物件等。在鍵值儲存中，值通常被視為不透明的物件，例如 Amazon dynamo [1]、Memcached [2]、Redis [3] 等。

以下是鍵值儲存中的一段資料片段：

Table 1

在本章中，你的任務是設計一個鍵值儲存，支援以下操作：

• put(key, value) // 插入與「key」關聯的「value」
• get(key) // 取得與「key」關聯的「value」

Understand the problem and establish design scope#

沒有完美的設計。每個設計都會在讀取、寫入與記憶體使用量的權衡中達到特定的平衡。另一個必須做出的權衡是一致性與可用性之間的取捨。

在本章中，我們設計一個具有以下特性的鍵值儲存：

• 鍵值對的大小較小：小於 10 KB。
• 能儲存大數據。
• 高可用性：系統即使在故障期間也能快速回應。
• 高可擴展性：系統可以擴展以支援大型資料集。
• 自動擴展：根據流量自動新增或刪除伺服器。
• 可調整的一致性。
• 低延遲。

單一伺服器鍵值儲存#

開發位於單一伺服器上的鍵值儲存很容易。一個直覺的方法是將鍵值對儲存在雜湊表中，將所有東西都保存在記憶體中。雖然記憶體存取速度很快，但由於空間限制，要將所有東西都放入記憶體可能不可行。

可以做兩種最佳化以將更多資料放入單一伺服器中：

• 資料壓縮
• 只將經常使用的資料儲存在記憶體中，其餘的儲存在磁碟上

即使有這些最佳化，單一伺服器很快就會達到容量上限。要支援大數據，就需要分散式鍵值儲存。

分散式鍵值儲存#

分散式鍵值儲存也稱為分散式雜湊表（distributed hash table），它將鍵值對分散到許多伺服器上。在設計分散式系統時，了解 CAP（Consistency、Availability、Partition Tolerance）定理 很重要。

CAP 定理#

CAP 定理指出，分散式系統不可能同時提供以下三項保證中的兩項以上：一致性（consistency）、可用性（availability）與分區容錯性（partition tolerance）。讓我們先建立一些定義。

• 一致性（Consistency）：一致性意味著所有用戶端無論連到哪個節點，都會在同一時間看到相同的資料。
• 可用性（Availability）：可用性意味著任何請求資料的用戶端即使在某些節點停機時也能得到回應。
• 分區容錯性（Partition Tolerance）：分區（partition）表示兩個節點之間的通訊中斷。分區容錯性意味著即使網路發生分區，系統仍能繼續運作。

CAP 定理指出，必須犧牲三個特性中的一個才能支援其他兩個，如圖 1 所示。

如今，鍵值儲存根據其支援的兩個 CAP 特性來分類：

• CP（consistency 與 partition tolerance）系統：CP 鍵值儲存支援一致性與分區容錯性，犧牲可用性。
• AP（availability 與 partition tolerance）系統：AP 鍵值儲存支援可用性與分區容錯性，犧牲一致性。
• CA（consistency 與 availability）系統：CA 鍵值儲存支援一致性與可用性，犧牲分區容錯性。

由於網路故障無法避免，分散式系統必須容忍網路分區。因此，在實際應用中不存在 CA 系統。

以上大多是定義的部分。為了讓內容更容易理解，讓我們看一些具體範例。在分散式系統中，資料通常會被複製多份。假設資料在三個副本節點 n1、n2 與 n3 上被複製，如圖 2 所示。

理想情況

在理想世界中，網路分區從不發生。寫入 n1 的資料會自動被複製到 n2 與 n3。一致性與可用性都能達成。

真實世界的分散式系統

在分散式系統中，分區無法避免，當分區發生時，我們必須在一致性與可用性之間做選擇。在圖 3 中，n3 停機，無法與 n1 與 n2 通訊。如果用戶端將資料寫入 n1 或 n2，資料無法傳播到 n3。如果資料被寫入 n3 但尚未傳播到 n1 與 n2，則 n1 與 n2 將擁有過時的資料。

如果我們選擇一致性而非可用性（CP 系統），我們必須阻擋所有對 n1 與 n2 的寫入操作，以避免這三台伺服器之間的資料不一致，這會使系統不可用。銀行系統通常具有極高的一致性需求。例如，銀行系統顯示最新的餘額資訊至關重要。如果因網路分區而發生不一致，銀行系統會在不一致解決之前回傳錯誤。

然而，如果我們選擇可用性而非一致性（AP 系統），系統會持續接受讀取，即使可能回傳過時資料。對於寫入，n1 與 n2 會持續接受寫入，當網路分區解決時，資料會被同步到 n3。

選擇符合你使用情境的正確 CAP 保證是建立分散式鍵值儲存的重要步驟。你可以與面試官討論並據此設計系統。

系統元件#

在本節中，我們將討論用來建立鍵值儲存的核心元件與技術：

• 資料分區（Data partition）
• 資料複製（Data replication）
• 一致性（Consistency）
• 不一致解決（Inconsistency resolution）
• 故障處理（Handling failures）
• 系統架構圖
• 寫入路徑
• 讀取路徑

以下內容主要基於三個常見的鍵值儲存系統：Dynamo [4]、Cassandra [5] 與 BigTable [6]。

資料分區#

對於大型應用程式，將完整資料集放入單一伺服器是不可行的。最簡單的方式是將資料切分為較小的分區，並儲存到多台伺服器上。在分區資料時有兩個挑戰：

• 將資料均勻地分散到多台伺服器。
• 在新增或移除節點時將資料移動最小化。

前一章討論的一致性雜湊是解決這些問題的絕佳技術。讓我們在高層次上重新了解一致性雜湊如何運作。

• 首先，伺服器被放置在雜湊環上。在圖 4 中，八台伺服器（以 s0, s1, …, s7 表示）被放置在雜湊環上。
• 接下來，鍵被雜湊到同一個環上，並儲存在順時針方向遇到的第一台伺服器上。例如，key0 使用此邏輯儲存在 s1 上。

使用一致性雜湊來分區資料具有以下優點：

• 自動擴展（Automatic scaling）：伺服器可以根據負載自動新增與移除。
• 異質性（Heterogeneity）：每台伺服器的虛擬節點數量與伺服器容量成正比。例如，容量較高的伺服器會被分配較多的虛擬節點。

資料複製#

為了達成高可用性與可靠性，資料必須非同步地複製到 N 台伺服器上，其中 N 是可設定的參數。這 N 台伺服器是使用以下邏輯選擇的：在鍵被映射到雜湊環上的某個位置後，從該位置順時針走，並選擇環上前 N 台伺服器來儲存資料副本。在圖 5（N = 3）中，key0 被複製到 s1、s2 與 s3。

使用虛擬節點時，環上前 N 個節點可能屬於少於 N 台實體伺服器。為了避免此問題，我們在執行順時針走的邏輯時只選擇唯一的伺服器。

同一個資料中心中的節點常常會因為停電、網路問題、自然災害等同時故障。為了更高的可靠性，副本被放置在不同的資料中心中，並透過高速網路連接資料中心。

一致性#

由於資料被複製到多個節點上，必須在副本之間進行同步。Quorum 共識（Quorum consensus） 可以保證讀取與寫入操作的一致性。讓我們先建立一些定義。

• N = 副本的數量
• W = 大小為 W 的寫入 quorum。要使寫入操作被視為成功，寫入操作必須得到 W 個副本的確認。
• R = 大小為 R 的讀取 quorum。要使讀取操作被視為成功，讀取操作必須等待至少 R 個副本的回應。

考慮以下圖 6 中所示的範例，其中 N = 3。

W = 1 並不意味著資料寫入一台伺服器。例如，在圖 6 的設定中，資料被複製到 s0、s1 與 s2。W = 1 意味著協調者（coordinator）必須在寫入操作被視為成功之前至少收到一個確認。例如，如果我們從 s1 收到確認，我們就不再需要等待 s0 與 s2 的確認。協調者扮演用戶端與節點之間的代理角色。

W、R 與 N 的設定是延遲與一致性之間典型的權衡。如果 W = 1 或 R = 1，操作會快速回傳，因為協調者只需要等待任一副本的回應。如果 W 或 R > 1，系統提供更好的一致性；然而，查詢會較慢，因為協調者必須等待最慢副本的回應。

如果 W + R > N，可以保證強一致性，因為必須有至少一個重疊節點擁有最新的資料以確保一致性。

如何設定 N、W 與 R 以符合我們的使用情境？以下是一些可能的設定：

• 如果 R = 1 且 W = N，系統針對快速讀取最佳化。
• 如果 W = 1 且 R = N，系統針對快速寫入最佳化。
• 如果 W + R > N，可保證強一致性（通常 N = 3, W = R = 2）。
• 如果 W + R <= N，無法保證強一致性。

根據需求，我們可以調整 W、R、N 的值，以達到所需的一致性等級。

一致性模型#

一致性模型是設計鍵值儲存時要考慮的另一個重要因素。一致性模型定義資料一致性的程度，存在廣泛的可能一致性模型：

• 強一致性（Strong consistency）：任何讀取操作都會回傳對應於最新更新寫入資料項目結果的值。用戶端永遠不會看到過時的資料。
• 弱一致性（Weak consistency）：後續的讀取操作可能不會看到最新的值。
• 最終一致性（Eventual consistency）：這是弱一致性的特定形式。給予足夠的時間，所有更新都會被傳播，所有副本都會一致。

強一致性通常透過強制副本在每個副本都同意目前的寫入之前不接受新的讀取/寫入來達成。這種方法對於高可用性系統並不理想，因為它可能會阻擋新的操作。Dynamo 與 Cassandra 採用最終一致性，這也是我們為鍵值儲存所建議的一致性模型。對於並行寫入，最終一致性允許不一致的值進入系統，並強制用戶端讀取這些值來協調。下一節將解釋協調如何透過版本控制來運作。

不一致解決：版本控制#

複製帶來高可用性，但會導致副本之間的不一致。版本控制與**向量鎖（vector lock）**被用來解決不一致問題。版本控制意味著將每次資料修改視為新的不可變版本。在我們談論版本控制之前，讓我們以一個範例來解釋不一致是如何發生的：

如圖 7 所示，副本節點 n1 與 n2 都有相同的值。我們把這個值稱為原始 value。Server 1 與 server 2 從 get(“name”) 操作得到相同的值。

接下來，server 1 將名稱改為「johnSanFrancisco」，server 2 將名稱改為「johnNewYork」，如圖 8 所示。這兩個變更同時執行。現在我們有相互衝突的值，稱為版本 v1 與 v2。

在這個範例中，原始值可以被忽略，因為這些修改是基於它的。然而，沒有清楚的方法可以解決最後兩個版本的衝突。為了解決這個問題，我們需要一個版本控制系統，能夠偵測衝突並協調衝突。向量時鐘（vector clock） 是解決這個問題的常見技術。讓我們檢視向量時鐘如何運作。

向量時鐘是與資料項目相關聯的 [server, version] 對。它可以用來檢查一個版本是否優先於、後於另一個版本，或與其他版本衝突。

假設一個向量時鐘以 D([S1, v1], [S2, v2], …, [Sn, vn]) 表示，其中 D 是資料項目，v1 是版本計數器，s1 是伺服器編號等等。如果資料項目 D 被寫入伺服器 Si，系統必須執行以下任務之一：

• 如果 [Si, vi] 存在，則將 vi 加 1。
• 否則，建立新項目 [Si, 1]。

上述抽象邏輯以圖 9 中的具體範例來解釋。

1. 用戶端寫入資料項目 D1 到系統，寫入由伺服器 Sx 處理，現在它的向量時鐘為 D1[(Sx, 1)]。
2. 另一個用戶端讀取最新的 D1，將其更新為 D2，並寫回。D2 是 D1 的後代，所以它覆蓋 D1。假設寫入由同一台伺服器 Sx 處理，現在它的向量時鐘為 D2([Sx, 2])。
3. 另一個用戶端讀取最新的 D2，將其更新為 D3，並寫回。假設寫入由伺服器 Sy 處理，現在它的向量時鐘為 D3([Sx, 2], [Sy, 1]))。
4. 另一個用戶端讀取最新的 D2，將其更新為 D4，並寫回。假設寫入由伺服器 Sz 處理，現在它的向量時鐘為 D4([Sx, 2], [Sz, 1]))。
5. 當另一個用戶端讀取 D3 與 D4 時，它發現了一個衝突，這個衝突是因為資料項目 D2 同時被 Sy 與 Sz 修改而造成的。衝突由用戶端解決，並將更新後的資料送回伺服器。假設寫入由 Sx 處理，現在它的向量時鐘為 D5([Sx, 3], [Sy, 1], [Sz, 1])。我們稍後會解釋如何偵測衝突。

使用向量時鐘，可以很容易地分辨出版本 X 是版本 Y 的祖先（即沒有衝突），如果 Y 的向量時鐘中每個參與者的版本計數器都大於或等於 X 中對應的計數器。例如，向量時鐘 D([s0, 1], [s1, 1])] 是 D([s0, 1], [s1, 2]) 的祖先，因此沒有記錄衝突。

同樣地，可以分辨出版本 X 是 Y 的兄弟（即存在衝突），如果 Y 的向量時鐘中有任何參與者的計數器小於 X 中的對應計數器。例如，以下兩個向量時鐘表示存在衝突：D([s0, 1], [s1, 2]) 與 D([s0, 2], [s1, 1])。

雖然向量時鐘可以解決衝突，但有兩個明顯的缺點。首先，向量時鐘為用戶端增加了複雜性，因為它需要實作衝突解決邏輯。其次，向量時鐘中的 [server: version] 對可能會快速增長。

為了修正此問題，我們為長度設定一個閾值，如果超過上限，最舊的對會被移除。這可能會導致協調效率降低，因為無法準確判斷後代關係。然而，根據 Dynamo 論文 [4]，Amazon 在生產環境中尚未遇到此問題；因此，這對大多數公司而言可能是可接受的解決方案。

故障處理#

與任何大規模系統一樣，故障不僅無可避免而且常見。處理故障場景非常重要。在本節中，我們先介紹偵測故障的技術，然後檢視常見的故障解決策略。

故障偵測#

在分散式系統中，僅因為另一台伺服器這麼說就相信某台伺服器停機是不夠的。通常需要至少兩個獨立的資訊來源才能將伺服器標記為停機。

如圖 10 所示，全對全多播（all-to-all multicasting）是一個直接的解決方案。然而，當系統中有許多伺服器時，這種方式效率不高。

更好的解決方案是使用去中心化的故障偵測方法，例如 gossip 協定。Gossip 協定的運作方式如下：

• 每個節點維護一個節點成員清單，其中包含成員 ID 與心跳計數器。
• 每個節點定期將其心跳計數器加 1。
• 每個節點定期將心跳送到一組隨機節點，這些節點再傳播到另一組節點。
• 一旦節點收到心跳，成員清單會更新到最新資訊。
• 如果心跳超過預先定義的時間沒有增加，該成員被視為離線。

如圖 11 所示：

• 節點 s0 維護如左側所示的節點成員清單。
• 節點 s0 注意到節點 s2（成員 ID = 2）的心跳計數器長時間未增加。
• 節點 s0 將包含 s2 資訊的心跳送至一組隨機節點。一旦其他節點確認 s2 的心跳計數器長時間未更新，節點 s2 就被標記為停機，這個資訊被傳播到其他節點。

處理暫時性故障#

透過 gossip 協定偵測到故障後，系統需要部署某些機制以確保可用性。在嚴格 quorum 方法中，讀取與寫入操作可能會被阻擋，如 quorum 共識章節中所說明。

一種稱為「sloppy quorum」[4] 的技術被用來提升可用性。系統不強制執行 quorum 要求，而是在雜湊環上選擇前 W 個健康伺服器進行寫入，並選擇前 R 個健康伺服器進行讀取。離線的伺服器會被忽略。

如果某台伺服器因網路或伺服器故障而不可用，另一台伺服器會暫時處理請求。當停機的伺服器恢復時，變更會被推回以達成資料一致性。這個過程稱為提示交接（hinted handoff）。由於 s2 在圖 12 中不可用，讀取與寫入會由 s3 暫時處理。當 s2 恢復上線時，s3 會將資料交回 s2。

處理永久性故障#

提示交接用來處理暫時性故障。如果某個副本永久不可用怎麼辦？要處理這種情況，我們實作 anti-entropy 協定來保持副本同步。Anti-entropy 涉及比較每個副本上的每一份資料，並將每個副本更新為最新版本。Merkle tree 被用來偵測不一致並最小化傳輸的資料量。

引述自 Wikipedia [7]：「雜湊樹（hash tree）或 Merkle tree 是一種樹，其中每個非葉節點都標記為其子節點的標籤（在葉節點的情況下為值）的雜湊。雜湊樹允許對大型資料結構的內容進行有效率且安全的驗證。」

假設鍵空間是從 1 到 12，以下步驟顯示如何建立 Merkle tree。標示的方框表示不一致。

步驟 1：將鍵空間劃分為桶（在我們的範例中為 4 個），如圖 13 所示。桶被用作根層級節點，以維持樹的有限深度。

步驟 2：建立桶之後，使用均勻雜湊方法對桶中的每個鍵進行雜湊（圖 14）。

步驟 3：為每個桶建立單一雜湊節點（圖 15）。

步驟 4：透過計算子節點的雜湊向上建立樹直到根（圖 16）。

要比較兩個 Merkle tree，先從比較根的雜湊開始。如果根的雜湊一致，則兩台伺服器擁有相同的資料。如果根的雜湊不同，則先比較左子節點的雜湊，再比較右子節點的雜湊。你可以遍歷樹找出哪些桶不同步，並只同步那些桶。

使用 Merkle tree 時，需要同步的資料量與兩個副本之間的差異成正比，而不是它們所包含的資料量。在實際系統中，桶大小相當大。例如，一種可能的設定是每十億個鍵有一百萬個桶，因此每個桶只包含 1000 個鍵。

處理資料中心故障#

資料中心故障可能因停電、網路中斷、自然災害等而發生。要建立能處理資料中心故障的系統，跨多個資料中心複製資料很重要。即使某個資料中心完全離線，使用者仍可透過其他資料中心存取資料。

系統架構圖#

現在我們已經討論了設計鍵值儲存的不同技術考量，可以將焦點轉到架構圖上，如圖 17 所示。

架構的主要特性如下：

• 用戶端透過簡單的 API 與鍵值儲存通訊：get(key) 與 put(key, value)。
• 協調者是一個節點，扮演用戶端與鍵值儲存之間的代理角色。
• 節點使用一致性雜湊分布在環上。
• 系統完全去中心化，因此新增與移動節點可以是自動的。
• 資料被複製到多個節點上。
• 沒有單點故障，因為每個節點都有相同的職責集合。

由於設計是去中心化的，每個節點執行許多任務，如圖 18 所示。

寫入路徑#

圖 19 解釋當寫入請求被導向特定節點後會發生什麼事。請注意，寫入/讀取路徑的提議設計主要基於 Cassandra 的架構 [8]。

1. 寫入請求被持久化到 commit log 檔案中。
2. 資料被儲存到記憶體快取中。
3. 當記憶體快取已滿或達到預先定義的閾值時，資料會被刷入磁碟上的 SSTable [9]。

sorted-string table（SSTable）是 <key, value> 對的有序清單。對 SSTable 有興趣的讀者，請參考參考資料 [9]。

讀取路徑#

當讀取請求被導向特定節點後，它會先檢查資料是否在記憶體快取中。如果是，資料會被回傳給用戶端，如圖 20 所示。

如果資料不在記憶體中，則會從磁碟取得。我們需要一個有效率的方法來找出哪個 SSTable 包含該鍵。Bloom filter [10] 通常用來解決此問題。

當資料不在記憶體中時，讀取路徑如圖 21 所示。

1. 系統先檢查資料是否在記憶體中。如果不在，跳到步驟 2。
2. 如果資料不在記憶體中，系統檢查 bloom filter。
3. Bloom filter 用來找出哪些 SSTable 可能包含該鍵。
4. SSTable 回傳資料集的結果。
5. 資料集的結果被回傳給用戶端。

Summary#

本章涵蓋許多概念與技術。為了喚起記憶，下表總結了分散式鍵值儲存所使用的功能與對應技術。

Table 2