跳到主要内容

Dynamo

Motivation​

在那個當下的Distributed DB的solution都是以Consistency為主，並沒有一套以Availability為主的Distributed DB，對於Amazon的業務來說Availability比Consistency更重要。

要解決的問題​

  • Partitioning
  • High Availability for writes
  • Handling temporary failures
  • Recovering from permanent failures
  • Membership and failure detection

Partitioning​

Dynamo DB用Consistent Hashing來做partitioning，每個cluster都會有一個ring，當要找某個key的時候，就會用hash(key)來找到該key所在的ring上的位置，然後往下找到第一個node，就是該key所在的node。

Amazon的Consistent Hash提出三種做法，第一種是每個node有T個token，這T個token被隨意的分配在ring上。第二種是每個node一樣有T個token，但是ring被分成Q個區塊，Q >> N且Q >> S*T(S是node number)。第三種是ring被分成Q個區塊，每個node有Q/S的token。

經過實驗，Strategy 3的表現最好，當node數目多，每個node的token就比較少，當node數目少，每個node的token就比較多，每個node的負擔就比較均勻。

High Availability for writes​

Dynamo DB犧牲Consistency來滿足Availability，因此即使每個node都可以接受write。每個write的先後順序用vector clock來決定，如果conflict就讓client來做merge，如果client不想處理conflict，也可以用簡單的last write wins之類的作法。

Handling temporary failures​

Dynamo DB是quorum based的作法，因此需要決定W、R和N，雖然用了Consistency Hashing和virtual node的概念，還是得保證資料必須被存在R個不同的node上。

但如果其中一台或以上的node暫時掛掉，為了讓client可以持續地寫入，Dynamo DB會找一個不在原本該被寫的node來"暫存"資料，並且會把這筆資料實際上屬於哪個node的資料記在metadata，並持續的看看node回來了沒，回來的話把data傳過去，然後把本地的資料刪掉。

Recovering from permanent failures​

如果node真的永久下線了，那它在ring中的位置要有人來補，為了避免不必要的傳輸，資料是以Merkle tree，有需要sync data的時候，只需要比較節點的hash value，找到第一個不相同的subtree來傳輸。

這個傳輸也會挑時間，它跑在background並且有個計算的方式來決定傳輸會不會影響線上的效能，對效能影響不大的情況下，才會做sync。

Membership and failure detection​

Dynamo DB是leaderless的架構，membership的管理是透過gossip-based的方式，每個node會每十秒隨機挑一個其他node來同步member狀況，採取eventual consistent的作法。

值得一提的是，Dynamo DB為了latency在長尾的表現也很好( 99th99_{th} 以後)，所以選擇把這些資訊做在client端，每個client知道自己要打哪個node，省掉load balancer那層帶來的轉發不確定。

經驗與結論​

Amazon的線上跑的結論是，**99.9995%**的request都沒有timeout或是被drop，**99.94%**的request只看到1個version，**0.00057%**的request看到兩個version，**0.00047%**看到這三個version，而且大部分的write conflict都是自動化程式造成的，真人使用者造成的比例極低。

把routing的邏輯做在Client side也有效的把latency降低，在各個部分(包括 99.9th99.9_{th})的latency都比在server side有個load balancer要好。