System|分散式|Dynamo
Reference：Dynamo： Amazon’s Highly Available Key-value Store
Dynamo是Amazon在07年SOSP上提出的分散式KV解決方案，是基於變種一致性Hash演算法與向量時間戳的Nosql資料庫，注重AP。
系統設計需求
QueryModel - 單純kv查詢
ACID - 沒有isolation，只允許單key
Efficience - 效能、成本、可靠性、永續性trade-off
Safety - 內網部署，不提供授權機制
Service Level Agreement - 不注重平均，注重極端99。9%的情況
Consistency - 最終一致性
Always writable - 衝突集中到Read從而避免拒絕write
Conflict Resolution - 應用伺服器決議衝突，自行決定適合方法
Incremental scalability：增加新節點影響最小。
Symmetry： 所有節點職責相同
Decentralization： 去中心化，p2p
Heterogeneity：
異構化
，可以單獨為某個節點提供更多容量而無需變更整體
系統架構
一致性Hash演算法改進
Sharding
首先是基本的帶虛擬節點的一致性hash保證partition，amazon給了標準答案。除了最基本的在增/刪時能均分負載之外，透過調整虛擬節點個數實現異構。
Replication
然後是保證replication，將Key對Node的查詢延伸到了後面N個
物理節點
，從而在負載均衡層面就達成了Replication。緊跟著的節點就是Coordinator，後繼作為Participant。這裡每個節點維護>N個物理節點（跳過相同地址的虛擬節點）的preference list以容錯
妙啊，可惜當時寫lab的時候沒看，負載均衡底下又整了個2PC。
Data Versioning - 向量時間戳
MVCC，資料都是immutable的，所有的寫操作並不會引起資料的修改，而是建立新版本的資料。
為了處理同時多個分支版本（e。g。 git merge）出現的問題，這裡採用向量時間戳： （node， counter）列表 。如果向量時間戳的每個維度都更大或者相同，則認為發生在其後；否則需要進行調解。
當進行寫操作時，使用者必須先指定對應的版本。
在Read時，將會順帶著返回對應的向量時間戳，以及所有分支。這個調解將由
客戶端
完成，然後透過寫操作把合併的時間戳寫回。
由於這裡key只涉及到相關的n個節點，因此向量時間戳的大小是有限的。當發生failure時，因為會新增伺服器，需要限制size增長。這裡透過為每個維度增加Modified Time，當
維度
超過10時就淘汰最老的。合併的時候會增加開銷，不過amazon表示生產環境沒遇到這問題。
讀寫執行流
請求可以透過普通的負載均衡，也可以直接指定coordinator
負載均衡會分發到隨機節點
上，然後該節點進行forward轉發給key對應的preference list第一個可用的伺服器作為coordinator。（這裡沒有用專門的節點做一致性hash，和之前提到的去中心化有關）
這裡用到了之前學過的演算法。讀和寫有著不同的Quorum，
和
，透過才成功
，這樣兩個majority之間必然存在交集。讀的開銷大時，讀的額度就應該適當減少，
vice versa
。也可以透過額度控制availability。
下面兩個情況都需要Quorum透過
寫的時候coordinator將會收到向量時間戳，並且通知前N個preference list的節點
讀的時候coordinator將會從N個節點收集向量時間戳，並且將結果返回給客戶端調解。
Weighted voting for replicated data
異常處理
hinted handoff
這裡的並不是嚴格的quorom，而是sloppy quorum，也就是跳過那些無法服務的節點。這樣的話即使節點崩了，讀寫的Quorum都是在這些可服務節點中進行選舉的，從而保證了availability。當然這樣肯定會犧牲一定的consistency（比如突然崩了一堆，結果你讀了新加入節點的資料）。
透過調節
可以改變操作的availability。
Replica synchronization
這裡用了Merkle tree，一種自底向上建立的雜湊樹。這個
資料結構
常常用來校驗資料的完整性，例如在TEE中進行記憶體的校驗。這裡的Merkle Tree是針對虛擬節點建立的，因為節點變動涉及的資料是以虛擬節點為單位。
建立時，Merkle Tree會把
相鄰block
進行hash，將相鄰hash再hash，最後變為單hash。
校驗時，自頂向下校驗，首先看根節點，然後向下直到葉。這樣可以最小化校驗的開銷。
也存在問題，例如物理節點加入/離開時，校驗會產生大量開銷。因此後面做了最佳化。
成員監測
gossip-based protocol
節點建立時隨機選擇一組虛擬節點進行對映，一開始的時候只知道本地資訊，每秒鐘隨機選一個peer交換資訊（一開始透過seed），最後知道
整體的view(
zero-hop DHT）。這裡也是利用最終一致性。
然後在負載均衡時，正確的forward到對應的peer上。（也就是說每個節點本身都承載著一致性hash的職責，去中心化）
External Discovery
假如讓A加入環，B也加入環，兩個節點都不知道彼此，因此無法gossip。因此需要seed，seed透過
靜態配置
或者服務配置，能夠被所有節點知曉，從而擔任溝通的橋樑。
Failure Detection
避免向那些無法達到的節點發送無意義的請求，如果請求失敗了，就替換節點，並且定期地詢問該節點是否恢復。每個節點只負責自己的
hinted handoff
。（分割槽情況，例如A->B無法通訊，但是C->B可以）
成員變化
這裡非常巧妙地利用上面提到的
實現了平滑擴容，節點新增時，原本的
依然能處理讀請求，同時那些透過gossip知道變化的節點會主動把不再負責的資料遷移到新增的節點上。因為虛擬節點，資料來源於不同節點，可以併發地遷移資料。
透過在source->dest間增加配置，已經遷移之後的資料將不會繼續被遷移。
最佳化
引數選擇
Amazon將（N，R，W）設定為（3，2，2），這裡的數值越大則C越大，越小則A越大。所以出於performance， durability， consistency， and availability 考慮選擇這個值。
Balancing Performance and Durability
增加
write buffer
，提高讀寫效能，降低永續性。
Ensuring Uniform Load distribution
下面的T為常數，Q為總分段數，S為總節點數目
Strategy 1： T random tokens per node and partition by token value
Strategy 2： T random tokens per node and equal sized partitions
Strategy 3： Q/S tokens
per node
， equal-sized partitions
客戶端協調
避免額外增加一個伺服器專門協調帶來的開銷
後臺任務
監控前臺讀寫資源佔用率，僅在空閒的時候進行同步、資料遷移等操作
Problem
： 高可用，可拓展性，高效能的KV
Related work
： 注重C而不是A， SQL資料庫維護太多額外資訊，不易拓展與負載均衡
Observation
： P2P + Quorum for R and W + Vector Clock
Solution
： P2P保證負載均衡與去中心化，Quorum保證可用性，向量時間戳進行MVCC
Evaluation
： 最終一致性，每個Dynamo都持有全域性view直接forward
Comments
： 如果繼續拓展，
全域性view
顯然不可維護，也不容易gossip。
