【系統設計】分布式鍵值數據庫

鍵值存儲 ( key-value store )，也稱為 K/V 存儲或鍵值數據庫，這是一種非關系型數據庫。每個值都有一個唯一的 key 關聯，也就是我們常說的?鍵值對。

常見的鍵值存儲有 Redis, Amazon DynamoDB，Microsoft Azure Cosmos DB，Memcached，etcd 等。

你可以在 DB-Engines 網站上看到鍵值存儲的排行。

? 設計要求??

在這個面試的系統設計環節中，我們需要設計一個鍵值存儲，要滿足下面的幾個要求

??每個鍵值的數據小于 10kB。
??有存儲大數據的能力。
??高可用，高擴展性，低延遲。

? 單機版 - 鍵值存儲??

對于單個服務器來說，開發一個鍵值存儲相對來說會比較簡單，一種簡單的做法是，把鍵值都存儲在內存中的哈希表中，這樣查詢速度非常快。但是，由于內存的限制，把所有的數據放到內存中明顯是行不通的。

所以，對于熱點數據（經常訪問的數據）可以加載到內存中，而其他的數據可以存儲在磁盤。但是，當數據量比較大時，單個服務器仍然會很快達到容量瓶頸。

? 分布式 - 鍵值存儲??

分布式鍵值存儲也叫分布式哈希表，把鍵值分布在多臺服務器上。在設計分布式系統時，理解 CAP（一致性，可用性，分區容錯性）定理很重要。

? CAP 定理??

CAP 定理指出，在分布式系統中，不可能同時滿足一致性、可用性和分區容錯性。讓我們認識一下這三個定義：

??一致性：無論連接到哪一個節點，所有的客戶端在同一時間都會看到相同的數據。
??可用性：可用性意味著任何請求數據的客戶端都會得到響應，即使某些節點因故障下線。
??分區容錯性：分區表示兩個節點之間的網絡通信中斷。分區容錯性意味著，當存在網絡分區時，系統仍然可以繼續運行。

通常可以用 CAP 的兩個特性對鍵值存儲進行分類：

CP（一致性和分區容錯性）系統：犧牲可用性的同時支持一致性和分區容錯。

AP（可用性和分區容錯性）系統：犧牲一致性的同時支持可用性和分區容錯。

CA（一致性和可用性）系統：犧牲分區容錯性的同時支持一致性和可用性。

由于網絡故障是不可避免的，所以在分布式系統中，必須容忍網絡分區。

讓我們看一些具體的例子，在分布式系統中，為了保證高可用，數據通常會在多個系統中進行復制。假設數據在三個節點 n1, n2, n3 進行復制，如下：

理想情況

在理想的情況下，網絡分區永遠不會發生。寫入 n1 的數據會自動復制到 n2 和 n3，實現了一致性和可用性。

現實世界的分布式系統

在分布式系統中，網絡分區是無法避免的，當發生分區時，我們必須在一致性和可用性之間做出選擇。

在下圖中，n3 出現了故障，無法和 n1 和 n2 通信，如果客戶端把數據寫入 n1 或 n2，就沒辦法復制到 n3，就會出現數據不一致的情況。

如果我們選擇一致性優先（CP系統），當 n3 故障時，就必須阻止所有對 n1 和 n2 的寫操作，避免三個節點之間的數據不一致。涉及到錢的系統通常有極高的一致性要求。

如果我們選擇可用性優先（AP系統），當 n3 故障時，系統仍然可以正常的寫入讀取，但是可能會返回舊的數據，當網絡分區恢復后，數據再同步到 n3 節點。

選擇合適的 CAP 是構建分布式鍵值存儲的重要一環。

? 核心組件和技術??

接下來，我們會討論構建鍵值存儲的核心組件和技術：

??數據分區
??數據復制
??一致性
??不一致時的解決方案
??故障處理
??系統架構圖
??數據寫入和讀取流程

? 數據分區??

在數據量比較大場景中，把數據都存放在單個服務器明顯是不可行的，我們可以進行數據分區，然后保存到多個服務器中。

需要考慮到的是，多個服務器之間的數據應該是均勻分布的，在添加或者刪除節點時，需要移動的數據應該盡量少。

一致性哈希非常適合在這個場景中使用，下面的例子中，8臺服務器被映射到哈希環上，然后我們把鍵值的 key 也通過哈希算法映射到環上，然后找到順時針方向遇到的第一個服務器，并進行數據存儲。

使用一致性哈希，在添加和刪除節點時，只需要移動很少的一部分數據。

? 數據復制??

為了實現高可用性和可靠性，一條數據在某個節點寫入后，會復制到其他的節點，也就是我們常說的多副本。

那么問題來了，如果我們有 8 個節點，一條數據需要在每個節點上都存儲嗎？

并不是，副本數和節點數沒有直接關系。副本數應該是一個可配置的參數，假如副本數為 3，同樣可以借助一致性哈希環，按照順時針找到 3 個節點，并進行存儲，如下

? 一致性??

因為鍵值數據在多個節點上復制，所以我們必須要考慮到數據一致性問題。

Quorum 共識算法可以保證讀寫操作的一致性，我們先看一下 Quorum 算法中 NWR 的定義。

N?= 副本數, 也叫復制因子，在分布式系統中，表示同一條數據有多少個副本。

W?= 寫一致性級別，表示一個寫入操作，需要等待幾個節點的寫入后才算成功。

R?= 讀一致性級別，表示讀取一個數據時，需要同時讀取幾個副本數，然后取最新的數據。

如下圖，N = 3

注意，W = 1 并不意味著數據只寫到一個節點，控制寫入幾個節點的是 N 副本數。

N = 3 表示，一條數據會寫入到 3 個節點，W = 1 表示，只要收到任何節點的第一個寫入成功確認消息（ACK）后，就直接返回寫入成功。

這里的重點是，對 N、W、R的值進行不同的組合時，會產生不同的一致性效果。

??當 W + R > N 的時候，通常是 N = 3, W = R = 2，對于客戶端來講，整個系統能保證強一致性，一定能返回更新后的那份數據。
??當 W + R <= N 的時候，對于客戶端來講，整個系統只能保證最終一致性，所以可能會返回舊數據。

通過 Quorum NWR，可以調節系統一致性的程度。

? 一致性模型??

一致性模型是設計鍵值存儲要考慮的另外一個重要因素，一致性模型定義了數據一致性的程度。

??強一致性：?任何一個讀取操作都會返回一個最新的數據。
??弱一致性：?數據更新之后，讀操作可能會返回最新的值，也有可能會返回更新前的值。
??最終一致性：?這是弱一致性的另外一種形式。可能當前節點的值是不一致的，但是等待一段時間的數據同步之后，所有節點的值最終會保持一致。

強一致性的通常做法是，當有副本節點因為故障下線時，其他的副本會強制中止寫入操作。一致性程度比較高，但是犧牲了系統的高可用。

而 Dynamo 和 Cassandra 都采用了最終一致性，這也是鍵值存儲推薦使用的一致性模型，當數據不一致時，客戶端讀取多個副本的數據，進行協調并返回數據。

? 不一致的解決方案：版本控制??

多副本數據復制提供了高可用性，但是多副本可能會存在數據不一致的問題。

版本控制和向量時鐘（vector clock ）是一個很好的解決方案。向量時鐘是一組 [server，version] 數據，它通過版本來檢查數據是否發生沖突。

假設向量時鐘由 D([S1, v1], [S2, v2], ..., [Sn, vn]) 表示，其中 D 是數據項，v1 是版本計數器，下面是一個例子

1. 客戶端把數據 D1 寫入系統，寫入操作由 Sx 處理，服務器 Sx 現在有向量時鐘 D1[(Sx, 1)]。
2. 客戶端把 D2 寫入系統，假如這次還是由 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，檢查向量時鐘后發現沖突（因為不能判斷出兩個向量時鐘的順序關系），客戶端自己處理解決沖突，然后再次寫入。假如寫入是 Sx 處理，現在的向量時鐘是 D5([Sx, 3], [Sy, 1], [Sz, 1])。

注意，向量時鐘只能檢測到沖突，如何解決，那就需要客戶端讀取多個副本值自己處理了。

? 故障處理??

在分布式大型系統中，發生故障是很常見的，接下來，我會介紹常見的故障處理方案。

? 故障檢測??

一種很常見的方案是使用 Gossip 協議，我們看一下它的工作原理：

??每個節點維護一個節點成員列表，其中包含成員 ID 和心跳計數器。
??每個節點周期性地增加它的心跳計數器。
??每個節點周期性地向一組隨機節點發送心跳，這些節點依次傳播到另一組節點。
??一旦節點收到心跳，成員列表就會更新為最新信息。
??如果在定義的周期內，發現心跳計數器的值比較小，則認為該成員離線。

? 處理臨時故障??

通過 gossip 協議檢測到故障后，為了保證數據一致性，嚴格的 Quorum 算法會阻止寫入操作。而 sloppy quorum 可以在臨時故障的情況下，保證系統的可用性。

當網絡或者服務器故障導致服務不可用時，會找一個臨時的節點進行數據寫入，當宕機的節點再次啟動后，寫入操作會更新到這個節點上，保持數據一致性。

如下圖所示，當 s2 不可用時，寫入操作暫時由 s3 處理，在一致性哈希環上順時針查找到下一個節點就是s3，當 s2 重新上線時，s3 會把數據還給 s2。

? 處理長時間故障??

數據會在多個節點進行數據復制，假如節點發生故障下線，并且在一段時間后恢復，那么，節點之間的數據如何同步? 全量對比？明顯是低效的。我們需要一種高效的方法進行數據對比和驗證。

使用 Merkle 樹是一個很好的解決方案，Merkle 樹也叫做哈希樹，這是一種樹結構，最下面的葉節點包含數據或哈希值，每個中間節點是它的子節點內容的哈希值，根節點也是由它的子節點內容的哈希值組成。

下面的過程，展示了 Merkle 樹是如何構建的。

第 1 步，把鍵值的存儲空間劃分為多個桶，一個桶可以存放一定數量的鍵值。

第 2 步，創建桶之后，使用哈希算法計算每個鍵的哈希值。

第 3 步，根據桶里面的鍵的哈希值，計算桶的哈希值。

第 4 步，計算子節點的哈希值，并向上構建樹，直到根節點結束。

如果要比較兩個 Merkle 樹，首先要比較根哈希，如果根哈希一致，表示兩個節點有相同的數據。如果根哈希不一致，就遍歷匹配子節點，這樣可以快速找到不一致的數據，并進行數據同步。

? 系統架構圖??

我們已經討論了設計鍵值存儲要考慮到的技術問題，現在讓我們關注一下整體的架構圖，如下

這個架構主要有下面幾個特點：

??客戶端通過簡單的 API 和鍵值存儲進行通信，get (key) 和 put (key, value)。
? coordinator 協調器充當了客戶端和鍵值存儲之間的代理節點。
??所有節點映射到了一致性哈希環上。
??數據在多個節點上進行復制。

? 寫入流程??

下圖展示了數據寫入到存儲節點的過程，主要基于 Cassandra 的架構設計。

1. 寫入請求首先被持久化在提交日志文件中。
2. 然后數據保存在內存緩存中。
3. 當內存已滿或者達到閾值時，數據移動到本地磁盤的 SSTable，這是一種高階數據結構，感興趣的讀者自行查閱資料了解。

? 讀取流程??

在進行數據讀取時，它首先檢查數據是否在內存緩存中，如果是，就把數據返回給客戶端，如下圖所示：

如果數據不在內存中，就會從磁盤中檢索。我們需要一種高效的方法，找到數據在哪個 SSSTable 中，通常可以使用布隆過濾器來解決這個問題。

1. 系統首先檢查數據是否在內存緩存中。
2. 如果內存中沒有數據，系統會檢查布隆過濾器。
3. 布隆過濾器可以快速找出哪些 SSTables 可能包含密鑰。
4. SSTables 返回數據集的結果。
5. 結果返回給客戶端。

? Reference??

[0] System Design Interview Volume 2:
https://www.amazon.com/System-Design-Interview-Insiders-Guide/dp/1736049119

[1] Amazon DynamoDB: https://aws.amazon.com/dynamodb/

[2] memcached: https://memcached.org/

[3] Redis: https://redis.io/

[4] Dynamo: Amazon’s Highly Available Key-value Store: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

[5] Cassandra: https://cassandra.apache.org/

[6] Bigtable: A Distributed Storage System for Structured Data: https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf

[7] Merkle tree: https://en.wikipedia.org/wiki/Merkle_tree

[8] Cassandra architecture: https://cassandra.apache.org/doc/latest/architecture/

[9] SStable: https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

[10] Bloom filter https://en.wikipedia.org/wiki/Bloom_filter

END

做了一個 .NET 的學習網站，內容涵蓋了分布式系統，數據結構與算法，設計模式，操作系統，計算機網絡等，以及工作推薦和面試經驗分享，歡迎來撩。

回復 dotnet 獲取網站地址。

回復 面試題 獲取 .NET 面試題。

回復 程序員副業?獲取適合程序員的副業指南。