前言
還記得我們在 資料庫基礎介紹 – 系統設計 08 講解過了關聯式資料庫，這一篇會更深入講解鍵值資料儲存（Key-Value Store）的原理，當然我下面也另外提供NoSQL 以及鍵值資料庫（Key-value database）的簡介。
什麼是NoSQL？
NoSQL 的意思是 Not Only SQL，是一種非關聯式資料庫，也就是說它不使用傳統的關聯式資料庫模型來儲存資料。NoSQL 資料庫通常使用更靈活、更可擴展的資料模型，例如：鍵值對、文件、圖形或寬表。這一篇就來好好講解鍵值資料庫（Key-value database）。
什麼是鍵值資料庫（Key-value database）？
鍵值資料庫使用雜湊表（Hash Table）等鍵值方法以鍵值對的形式儲存資料。鍵充當主鍵（Primary Key），值（Value）可以是從簡單標量值到複雜物件的任何值。常見的鍵值資料庫，包含：Amazon DynamoDB、Redis 。
鍵值資料儲存（Key-Value Store）
鍵值資料儲存（Key-Value Store）是一種分散式雜湊表（Distributed Hash Table），其中DHT是一種去中心化儲存方式，提供類似雜湊表的查找、儲存。雜湊表（Hash Table） 也是一個 Abstract Data Type （ADT），它的優點是通常可以用比較快的時間完成 Search operation 的動作。這邊先來講講雜湊（Hash）的原理，由雜湊函式（Hash Function）產生一組密鑰，並且是唯一的密鑰。鍵值儲存（Key-Value Store）則是將鑰匙綁入特定的值中，而值可以是 Map、Image之類的儲存類型。
通常我們會將值限制在相對較小的檔案大小，約略 MB 至 KB 的內容大小。鍵值資料儲存可以用在滿多不同的情境的，例如：建立一個 Messenger，並且將使用者對話去做儲存，這樣的情境就很適合使用此 NoSQL 的方式處理。
如何設計鍵值資料儲存？
如果要設計一個系統元件，首先就需要回歸到最原本的問題，此系統元件有哪些需求？如果忘了需求的讀者，建議可以觀看 軟體設計非功能性特性 – 系統設計 03 。
功能需求（Functional Requirement）
通常，鍵值儲存與一般資料庫相同，都有一些常見的功能，例如： get 和 put 之類的功能。不過鍵值儲存系統與一般儲存系統，在功能需求上還是有一些不同的。
- 可配置服務：某些系統可能會犧牲強一致性（Consistency）來換取更高的可用性（Availability）。鍵值儲存會需要提供可配置的服務，以便不同的系統中也可以使用一致性模型。
- 始終寫入的能力：系統需要具有寫入鍵值儲存的功能。如果使用者想要強一致性（Consistency），由於 CAP 定理的影響，勢必會捨棄可用性（Availability）。換句話說，在CAP中，更傾向Ｃ。
非功能需求（Non-Functional Requirement）
可擴展性（Scalability）：鍵值儲存要可以在全球的數萬台伺服器上運行。並且根據需求去新增或刪除伺服器，同時減少對服務可用性的影響，甚至不造成影響。另外，系統應該能夠處理鍵值儲存的大量使用者。
容錯（Fault Tolerance）：如果系統伺服器或系統元件發生故障，鍵值儲存應該要持續的運作而不間斷。
設計鍵值資料儲存
在開始設計系統前，首先設計簡單（Design Simple）的原則，需要先假設以下：
- 資料中心是可信任的。
- 資料儲存中的身份驗證都已完成。
- 使用者請求和回應是透過 HTTPS。
API設計
首先是 API 的設計，我們需要從功能面的角度來去思考需要哪些API，其中鍵值儲存與雜湊表（Hash Table）一樣，提供兩個主要功能：get 和 put。
Get 函式
get(key)
我們根據參數的鍵（Key）傳回對應的值。這裡也另外提一下 Data Replication 如何優化資料庫？- 系統設計 09 有提到的資料複製問題，當鍵值資料庫在進行複製資料時，它會找到與金鑰關聯的物件副本。如果儲存配置了較弱的資料一致性模型，則由系統完成。
Put 函式
put(key, value)
此函式用來儲存與鍵關聯的值，鍵值資料儲存會自動決定資料應放置的位置。另外系統通常保留有關儲存物件的元資料（Metadata）。未來也會再好好的介紹什麼是元資料（Metadata）。
增加可擴展性
對系統設計來說，可擴展性（Scalability）是非常重要的，因此在設計鍵值資料儲存（Key-Value Store）時，我們會將鍵值資料儲存在儲存節點中。隨著需求的變化，我們可能需要新增或刪除儲存節點。這代表我們需要在系統中的節點上對資料進行分區（Partition），以將負載分佈到所有節點上。如果尚未熟悉分區的讀者，可以參考 Data Partitioning 資料分區是什麼？ – 系統設計 10。
回到鍵值資料儲存中的分區，這邊提供一個範例：假設我們有四個節點，我們希望 40% 的請求發送到每個節點以平衡負載，解決這個問題的傳統方法是透過模運算子（Modulus Operator）來去做計算。每個到達的請求都有一個與之關聯的金鑰。當請求到來時，我們計算密鑰的雜湊值。然後，我們透過將雜湊值與節點數 m 來求餘數。
一致性雜湊（Consistent Hashing）
曾經我們在 DNS 是什麼？網域名稱系統介紹 – 系統設計 06 有介紹過各種不同類型的演算法來去處理流量問題，那麼如果討論到雜湊時，就不得不討論一致性雜湊（Consistent Hashing）演算法了。這個演算法是一個非常適合平衡節點負載的方法。
在一致性雜湊演算法中，我們需要先假定，有一個雜湊環（Hash Ring）從0 到 n−1，其中 n 是可用雜湊值的數量。我們使用每個節點的 ID，計算其雜湊值，並將其雜湊值透過映射（Mapping）到雜湊環（Hash Ring）。每個請求都由它在環中順時針方向移動找到的下一個節點完成。
每當一個新節點加入環中時，緊鄰的下一個節點都會受到影響。它必須與新添加的節點共享其資料，而其他節點不受影響。這樣的演算法很容易進行擴展，能夠將對節點的變更保持在最低限度。雜湊值是隨機分佈的，因此我們期望請求的負載是隨機的並且平均分佈在環上。
一致性雜湊的主要好處是，當節點加入或離開時，我們需要確保移動的鍵（Key）數量最少。不過在實務上，請求負載並不是平均分配的。任何處理大量資料的伺服器都可能成為分散式系統中的瓶頸。該節點會收到不成比例的大量資料儲存和搜尋請求，從而降低整體系統效能。這邊提供我覺得寫得很詳細的文章，提供讀者做參考，並且附上一致性雜湊的圖解。
使用虛擬節點（Virtual Nodes）
除了使用一致性雜湊演算法以外，我們也可以使用虛擬節點來確保節點之間的負載分佈更均勻。此方法是在同一個鍵上使用多個雜湊函式，而不是應用單一雜湊函式。
這邊快速舉例，假如我們有四個雜湊函數。對於每個節點，我們計算四個雜湊值並將它們放入環中。對於該請求，我們僅使用一個雜湊函數。無論請求到達環上的哪個位置，都會由沿著順時針方向移動時找到的下一個節點進行處理。每個伺服器有四個位置，因此請求的負載更加均勻。此外，如果一個節點比其他節點具有更多的硬體容量，我們可以透過使用額外的雜湊函數來添加更多的虛擬節點。這樣，它將在環中佔據更多位置並滿足更多請求。
資料複製（Data Replication）
這一篇 Data Replication 如何優化資料庫？- 系統設計 09 寫了關於資料庫複製的內容，到了鍵值資料庫，我們也會有多種不同的方法來處理資料複製。常見的資料複製包含：主從關係以及點對點關係。
主從複製（Primary-secondary）
在主從方法中，其中一個儲存區域是主要儲存區域，其他儲存區域是輔助儲存區域。輔助副本從主副本複製其資料。主要儲存區域用來處理寫入請求，而輔助服務則服務於讀取請求。另外如果主資料庫發生故障，我們將無法寫入存儲，並且它將成為單點故障。
點對點複製（Peer-to-peer）
在點對點方法中，所有儲存區域都是主要儲存區域，也會複製資料以保持更新。所有節點也都允許讀取和寫入。通常，在所有 n 個節點中進行複製效率低且成本高。相反，三個或五個是要複製的儲存節點數量的常見選擇。
結語
剛好接下來會有將近兩週的時間在國外旅行，不過依然會持續更新系統設計的技術文章，未來也會持續撰寫系統設計的內容。如果喜歡這類型的文章，也不妨留言給予鼓勵！
相關文章
Data Partitioning 資料分區是什麼？ – 系統設計 10
Data Replication 如何優化資料庫？- 系統設計 09
系統設計元件介紹 Building Block – 系統設計 05
Back-of-the-envelope 封底計算 – 系統設計 04
繁體中文 
English 
简体中文 
한국어 
日本語 
Español