# 7.3 Dynamo: Amazon’s Highly Available Key-value Store

## 參考資料
- 翻譯
- https://arthurchiao.art/blog/amazon-dynamo-zh/
- 導讀
- https://blog.csdn.net/plm199513100/article/details/121731269
- https://blog.csdn.net/plm199513100/article/details/121915208
## Introduction
- 亞馬遜是遍布全球的電商平台，任何一丁點的損失都會造成大量市值流失，因此須著重在可靠性以及可用性，同時及為了迅速擴展，高擴展性也很重要
- 對於大型的分散式系統，故障是隨時都會發生的，因此軟體要試故障為可預期狀態，並且不影響其可用性或效能
- Dynamo 是用於管理對可靠性要求極高的服務之狀態，而這些服務也對 dynamo 的可靠性, 一致性, cost-effectiveness, 效能有著極高的控制程度
- 亞馬遜當中有些服務是使用簡單的 key-value 形式存取，像是暢銷排行榜, 購物車等等。假如使用 RDBMS，反而降低效率, 效能，限制擴充性 可用性
- Dynamo 是透過成熟技術來做到高擴展性, 高可用性
- consistent hashing: 做到 partition 和 replicated
- object versioning: 資料版本控制，實現一致性
- qurom-based, decentralized replica synchronization protocol: 達成一致性
- gossip based distributed failure detection and membership protocol: 錯誤偵測
- 重點: 本篇著重在高可用性, 高可靠性, 高擴展性, 極低延遲

## Background
- 對於簡單 key-value 存取的資料來說，如果是使用傳統的 RDBMS 需要特殊的硬體和訓練有素的工程師來操作，反而降低效率，也沒有簡單達到目的，並且傳統 RDBMS 更講求一致性，反而損失了可用性，也因為其複雜的結構，擴展性不高
- 對於運行 dynamo 的系統，有以下假設
- Query Model: 資料是簡單的鍵值操作，並且沒有複雜的資料關係 (data-relation)
- ACID Properties: 為了最大化可用性，犧牲一點一致性，並且不提供隔離機制，並只允許對單鍵操作
- Efficiency: 服務跟存儲系統達到嚴格的 SLA (等會介紹)，也就是要有一定程度的延遲跟吞吐量，並且擁有動態配置 dynamo 節點的能力，使服務在任何狀況下都能夠達到目標延遲以及吞吐
- Security: 因為是內部使用，不著重資安疑慮。
- Scalability: 每個服務都有自己的 dynamo 系統，要有一定程度的擴展性
- Service Level Agreements (SLA)
- 服務在一定請求程度下的效能保證
- 某個服務向客戶端保證，在 500 QPS 的負載下，它處理 99.9% 的請求 所花的時間都在能 300ms 以內。
- 在以往的研究中，是用 平均值, 中位數 或 標準差來表示 SLA，這樣可能只能表達大部分請求的狀況，但在亞馬遜，必須是幾乎所有請求都要達到理想狀況，因此直接設定在 99.9% 的請求率，後續也都以此做為數據表示基準
- 設計考量
- 前面提過，dynamo 為了最大化可用性，因此選擇弱一致性，並達到最終一致性。而採用弱一致性，就會有可能遇到版本衝突，延伸出兩個議題:
- 哪個階段去解決衝突: 讀 or 寫?
- 傳統研究是在寫的時候去處理衝突，讀的話盡可能簡單。
- 常見的就 qurom-based，然而只要有大部分的節點沒有通過，寫就失敗。這違反 dynamo 的不管怎樣都要有地方可以寫
- 因此選擇在讀的時候處理衝突
- 誰去解決衝突: 資料庫 和 應用程序
- 如果是交由資料庫處理，就採用最簡單的 last write wins
- 如果是交由應用程序處理，可以依照應用自身做彈性決定
> 像是購物車，可以將現有版本跟衝突版本合併在一起給使用者
- 持續擴充: 要能持續地擴充，且不影響原有運行的資料節點
- 對稱性: 每個節點負責的任務都一樣，不會有人突然是 leader，或是有不一樣的任務。對稱性簡單化系統
- 去中央化: 對稱性延伸出來的概念，可以為擴充性 可用性帶來更多可能
- 異構性: 不同節點的運算能力可以不同，而能力越強的，其負載就要更多

## 與其餘研究不同之處
1. Dynamo 追求"總是可寫"，不會因為沒達到大部分或是結點失效等問題導致無法寫入
2. Dynamo 作為亞馬遜專用的內部基礎設施，不必著重資安議題
3. 使用 Dynamo 的應用不會有複雜的層級命名空間(hierarchical namespaces)和複雜的資料關係(relation schema)
4. Dynamo 要確保 99.9% 的 讀/寫請求都能夠在極度嚴苛的目標(幾百毫秒以內)完成。因此不採用多層路由的架構，而是在每個節點保存足夠量的節點資訊，一步直接導到目標節點

## 系統架構
- 針對核心的分散式技術說明，包括資料分區、副本複製、版本控制、資料處理過程、錯誤處理 以及 擴展
- dynamo 對外提供兩個方法
- get(key): 返回屬於該 key 的 object，或是同樣都是該 key，但是有版本衝突的多個 object
- put(key): 將 key 透過一致性 hash 算法，決定 object 存入哪個節點，同時會協帶 context，包含 object 的一些 metadata，像是版本，讓 dynamo 可以確定此 request 的合法性

### 資料分散算法
- 系統將多個節點組成的存儲空間當作一個環，透過對一個 key 做 hash，他會落在任兩個節點之間或某節點之上。然後沿著順時針下去，找到的第一個比 hash 值大的節點 (想成順時針第一個遇到的節點)就是目標存儲位置。
- 此方法的好處是，在節點的加入或移除，只會影響其相鄰節點
- 此方法是比較初步的 hash 算法，這會導致附載不平衡，以及沒有針對節點的不同算力有效分配任務
- 提出虛擬節點的概念，一個物理結點內部會有多個虛擬節點，而虛擬節點可以做為一般結點在環上使用
- 好處1: 添加或刪除節點，數據變動較為平均，因為都是由同個物理節點管理
- 好處2: 可以根據物理節點的算力，決定要給予的虛擬節點數量

### 副本複製
- 透過多個節點副本，可以提高可用性以及持久性。這邊決定出一個參數 N，代表此 key-value object 在整個系統裡，應該要至少有 N 個副本
- 範例，假如 N 為 3，環的樣式如下，有一個 key k 被 hash 到 A 和 B 之間，因此該 object 就會在 B, C, D 各有一個副本。進而延伸，也可以看出 D 節點就會保存 (A, B]、(B, C] 和 (C, D] 的資料
- 對於一個 key，有存儲該 key 的所有節點可以組成一個列表叫做 preference list (優先列表)，而為了避免有結點失效，其長度會大於 N

### 版本控制
- 為了達成 always writable，假如遇到網路分區的狀況，就會有版本衝突的問題，需要透過調和(reconciliation)處理
> 購物車目前有 A B C: (v1, ABC)
> 使用者把 C 移走的這個行為沒有成功寫入: (v1, ABC), (v2-1, AB)
> 使用者加入 D，但因為系統並不知道 C 被移走了，因此對上個版本 v1 做操作: (v1, ABC), (v2-1, AB), (v2-2, ABCD)
> 系統回傳所有衝突的 v2 版本，由購物車應用處理衝突，最終呈現 ABCD
- 兩種調和方法
- syntactic reconciliation: 新版本正常汰換老版本
- semantic reconciliation: 因為某些原因導致版本出現分支，需透過應用程序協助處理
- 用購物車例子對照上述的調和方法，v1 因為 syntactic reconciliation 被汰換，而兩個衝突的 v2 透過購物車應用做 semantic reconciliation，對兩個分支做合併回傳結果
- dynamo 透過向量時間來記錄版本，確認兩版本之間有無因果性
- 向量時間: (node, counter)
- node 代表哪個 node 執行此次 write
- counter 代表該 node 對該 object 做過更改的次數
- 範例
- 第一個請求被 node Sx 處理，產生 object D1，其向量時間為 [(Sx, 1)]
- 第二個請求還是被 Sx 處理，產生 obejct D2，而 D2 明顯是 D1 的後代，因此可以完全覆蓋 D1，其向量時間為 [(Sx, 2)]
- 第三個請求被 Sy 處理，產生 object D3，向量時間變成 [(Sx, 2), (Sy, 1)]
- 第四個請求被 Sz 處理，但是因為 D3 的更新還沒寫到 Sz，Sz 不知道 D3 的存在，所以用 D2 去改，產生 object D4，向量時間為 [(Sx, 2), (Sz, 1)]
- 假如今天有個節點本身有 D1, D2 的紀錄，在收到 D4 後，就可以知道 D4 是 D1, D2 的後代，直接用 D4 覆蓋過去 (syntactic reconciliation)
- 假如今天有個節點只知道 D3，在收到 D4 後，從向量時間無法直接判定誰先誰後<b><u>(兩個 node，Sy,Sz 的 counter 無法直接比較)</u></b>，因此兩者都保留下來，使用者 call get() 就回傳 D3, D4，交由使用者處理 (semantic reconciliation)
- 使用者那邊更新完後，發送第五個請求，產生 object D5，向量時間為 [(Sx, 2), (Sy, 1), (Sz, 1)]。至此系統就可以知道 D5 會是 D1, D2, D3, D4 的後代

### 資料處理過程
- 當收到操作請求，有兩種處理方式
1. 請求路由給 load balancer，由 balancer 選擇一個合適節點
- 優: 應用端不用了解 dynamo 底層的實作
2. 透過 partition-aware 的函式庫，直接導向一個合適的節點
- 優: 延遲低，不用經過一次轉發
- Preference list 的第一個叫做 coordinator
- 為了達成一致性，對於讀/寫有設定門檻值R/W，代表執行相關操作最少須獲得的票數，且 R+W > N
- put 過程，coordinator 生成向量時間，並將副本保存在 preference list 中，前 N 個健康節點裡面(sloppy quorum)，其中如果有 W 個寫成功，便認為此寫入成功
- get 過程，coordinator 對 preference list 中，前 N 個健康結點做讀取，假如至少 R 個有讀成功，便返回結果。如果結果中，有多個不相干的衝突版本，也一併傳給應用端，由應用端做 reconcile

### 錯誤處理: Hinted Handoff
- 此種錯誤處理是針對短暫的節點失效，將請求轉交給其他結點暫為保存
- 前面提過，讀寫操作都是針對前 N 個健康節點，假設 N 為 3，本來應該要給 A 的請求，會寫入 A, B, C，但因為 A 壞掉了，往後變成 B, C, D。而給 D 的請求中，會特別提醒 (hint) 此請求本來應該要給 A 的，之後 D 會一直嘗試 ping A，假如 A 回來了，就把數據傳送回去給 A，而 D 本身就不會應用此請求。

### 錯誤處理: Replica synchronization
- 遇到長時間的節點失效，一個節點也沒辦法暫時保存太多東西，因此改採用直接與其餘節點進行數據同步操作，稱做反熵 (anti-entropy)
- 為了能夠快速對比兩個節點的數據不同，透過 merkle tree 比較。
- 葉子節點為數據本身，而每兩個數據可以 hash 出一個值，此值為這兩個數據葉子節點的父節點，以此向上推進，直到根結點
- 每個 node 針對不同的 key range 都有對應的 merkle tree，比較 2 個 node 中，同個 key range 的數據差異，先從根結點看起，假如一樣就是數據副本皆相同，假如不一樣，在一層層往下找，直到發現不同的地方為止

### Membership (節點之間的關係) and Failure Detection
- 當有結點加入或是離開，為了讓其他結點也可以快速知道這件事情，採用 gossip 算法傳遞。一個節點剛開始只知道自己目前負責的 key range，之後會一直持續地與多個節點進行此消息兌換，最終節點就會知道自身的 key range 也由哪些節點負責。只要一有結點離開或加入，這些信息都能夠快速更新
- (TODO) 種子節點
- 在有應用端發送請求的時候，兩個節點才會去看對方可不可以達到。而為了快速負責請求，假如 A 節點收不到 B 節點的回復，就算 B 結點跟其他節點是正常的，A 就直接認為 B 失效了，並由與 B 節點管理同個 key range 的其餘節點負責請求，然後定期檢查 B 可不可以正常連線

### Adding/Removing Storage Nodes
- 新結點加入，要把一些 key range 轉交由他負責；刪除也同理，只是反過來做
- 假如有一個 X 結點加入 A 和 B 之間，X就須負責 (F, G], (G, A] and (A, X] 之間的 key，而原本 B, C, D 上就不用再負責重複的 range 了。像是 (A, X] 原本會由 B 負責，X 加入後，B 要把這段交由 X 處理，而他自己就不用管了。
- 確保 key range 的均勻分布

## 實作
- 每個節點包含 3 個組件
- request coordination
- Membership and Failure Detection (沒特別提及)
- 本地持久存儲引擎 (資料庫)
- 本地持久存儲引擎
- dynamo 支持不同種類引擎以插件的方式作為資料庫，包括
- Berkeley Database (BDB) Transactional Data Store2
- BDB Java Edition
- MySQL
- an in-memory buffer with persistent backing store
- 透過插件的方式，不同面向的應用可以選擇最適合的引擎。如 BDB 可以負責幾十KB的資料，MySQL 可以處理大一點的
- request coordination
- 前面有提過 coordinator，dynamo 接收到應用端的請求後，由他負責主導讀寫操作
- read coordination
1. 發送讀取請求給節點
2. 等待所需的最少數量響應 (R)
3. 如果在規定的上限時間內收到的回應數量太少，認定請求失敗
4. 否則，收集物件的所有版本，確定應該傳回哪些
5. 如果開啟了版本化（versioning）配置，執行 syntactic reconciliation，產生一個不透明的寫入上下文（context），其中包含了合併之後的版本對應的的 vector clock
- 其中，如果有讀到過期版本，coordinator 會把有過期版本的節點，用新版本去覆蓋他，稱作 read repair，可以減少逆熵的工作
- write coordination
- 前面有提過 coordinator 是 preference list 的第一個，但是如果請求都一直由她來作，這會造成附載不平衡。因此 preference list 中任一個都可以當作寫操作的 coordinator
- 在寫之前，通常都會先讀過一遍，因此可以把前一次讀操作返回最快的那個節點作為下次寫操作的 coordinator，降低了請求處理的抖動性

##