Dynamo 是 Amazon 的高可用分布式鍵值存儲（key/value storage）系統。這篇論文發表 的時候（2007）它還只是一個內部服務，現在（改名為 DynamoDB）已經發展成 AWS 最核心 的存儲產品（服務）之一，與 S3 等並列。據了解，國內某一線大廠的公有雲鍵值 存儲服務，也是參考這篇文章設計和實現的。
現在提到鍵值存儲，大家首先想到的可能是 Redis，那麼 Dynamo 和 Redis 是不是競品， 只是一個開源一個是商業的？不是的，二者針對的場景不同，這裡非常粗地列舉幾方面：
- 使用場景：Dynamo 定位是永遠可寫（always writable）的持久文件系統，Redis 主要用作（易失）緩存或內存資料庫
- 存儲方式：Dynamo 是磁碟，Redis 是內存
- 系統規模：Dynamo 是 分布式 （distributed）存儲系統，設計之初（2006）就能支 撐幾百台 node；Redis 是 單機或集群（主從複製 ），規模不同
- 性能指標：以上差異必然導致各自設計時的性能考慮（例如延遲、吞吐、容錯等）和實 際的性能量級不同
精讀一篇經典比泛讀幾十篇水文收穫要大的多，尤其是那些領域開山之作。這篇論文適合精讀。
翻譯僅供個人學習交流。由於譯者水平有限，本文不免存在遺漏或錯誤之處。如有疑問， 請查閱原文。
以下是譯文。
摘要
Amazon 是世界上最大的電商之一。
在這裡我們所遇到的最大挑戰之一就是 超大規模下的穩定性問題 （reliability at massive scale）。即使是最微小的故障（the slightest outage），也會造成巨大的經濟 損失，而且會降低客戶對我們的信任。 Amazon.com 作為一個為全球提供 web 服務的平台， 其底層的基礎設施是由分布在全球的數據中心中成千上萬的伺服器和網絡設備組成的。在如 此龐大的規模下，大大小小的組件故障是不斷在發生的，而我們應對這些故障時所採取 的 管理持久狀態的方式 （the way persistent state is managed）， 驅動著軟體系 統的可靠性（reliability）和可擴展性（scalability）的發展 。
本文介紹 Dynamo —— 一個 高可用鍵值存儲系統 —— 的設計和實現。Amazon 的一些核心 服務就是基於 Dynamo 提供不間斷服務的（always-on experience）。為了達到這種等級的 可用性（level of availability），Dynamo 犧牲了幾種特定故障場景下的一致性 。另 外，Dynamo 大量使用了 對象版本化 （object versioning）和 應用協助的衝突解決 （application-assisted conflict resolution）機制，給開發者提供了一種新穎的接口。
1. 引言
Amazon 是一個全球電商平台，峰值用戶達到幾千萬。支撐 Amazon 的是分布在全球的數據 中心中成千上萬的伺服器。Amazon 平台對 性能、可靠性和效率 等指標有著很高的要求 。而且，為了支撐持續增長（continous growth），平台需要有 高度的可擴展性 。 可 靠性是我們最重要的需求之一 ，因為即使是最微小的故障也會造成巨大的經濟損失，而且 會降低客戶對我們的信任。
我們從打造 Amazon 平台的切身實踐中總結出的一條經驗是： 一個系統的可靠性和可擴展 性取決於如何管理它的應用狀態 。
The reliability and scalability of a system is dependent on how its application state is managed.
Amazon 使用的是高度去中心化的、松耦合的、面向服務的架構，由幾百個服務組成。這樣 的環境對 永遠可用 （always available）的存儲技術有著強烈的需求。例如， 即使磁 盤掛掉、路由抖動、甚至數據中心被颶風摧毀，用戶應該仍然能向他們的購物車添加和查看 商品 。要實現這樣的目標，管理購物車的系統就必須永遠能讀寫它的 數據倉庫，而且 數據倉庫還要跨多個數據中心可用。
對於我們這種由幾百萬台設備組成的基礎設施，故障是家常便飯；在任何時刻都會有 比例小 但數量不少 （small but significant number）的伺服器和網絡設備發生故障。因此， Amazon 的軟體系統要 將故障視為正常的、可預期的行為（treat failure handling as the normal case），不應因設備故障而影響可用性和性能 。
為了滿足可靠性和可擴展性的需求，Amazon 開發了一些存儲技術，S3 （Simple Storage Service）可能是最廣為人知的一種。本文介紹 Amazon 的另一個存儲產品 Dynamo —— 一個 高可用鍵值存儲數據倉庫（data store）—— 的設計和實現。
Dynamo 用於管理 對可靠性要求非常高的服務 的狀態，這些服務還要求對可靠性、一致 性、成本-效率（cost-effectiveness）和性能有很強的控制能力。
Dynamo is used to manage the state of services that have very high reliability requirements and need tight control over the tradeoffs between availability, consistency, cost-effectiveness and performance.
Amazon 平台有很多類型的應用，不同的類型對存儲的需求差異很大。例如，其中一類應用 希望能 數據倉庫的配置足夠靈活，以便在成本最經濟的方式下，由開發者來決定如何 在可用性和性能之間取得折中 。
Amazon 的一些服務 只需以主鍵（primary key）的方式訪問數據倉庫 。對於很多服 務，例如暢銷排行榜、購物車、客戶喜好偏向、session 管理、銷售排名、商品目錄等等， 常見的關係型資料庫會非常低效，而且限制了規模的擴展性和可用性。Dynamo 提供了只使 用主鍵（primary key only）的訪問接口來滿足這類應用的需求。
Dynamo 基於一些眾所周知的（well known）技術實現了可擴展性和高可用性：
- 數據通過 一致性哈希 分散和複製（partitioned and replicated）[10]
- 通過 對象版本化 （object versioning）實現一致性 [12]
- 副本之間的一致性由一種 類似仲裁的技術 （quorum-like technique）和一個去中 心化的 副本同步協議 （replica synchroni protocol）保證
- gossip-based 分布式故障檢測和成員檢測（membership）協議
Dynamo 是一個只需最少人工管理的、完全去中心化的系統。
Dynamo is a completely decentralized system with minimal need for manual administration.
向 Dynamo 添加或移除存儲節點不需要人工 partition（調整哈希節點）或 redistribution（在節點之間重新平衡數據分布）。
Dynamo 在過去的幾年已經成為 Amazon 很多核心服務的底層存儲技術。在節假日購物高峰 ，它能實現不停服（平滑）擴容以支持極高的峰值負載。例如購物車服務的幾千萬請求會 產生單日 300 萬次的付款動作，管理 session 狀態的服務能處理幾千萬的並發活躍用戶等 等。
本文對該領域的主要貢獻：
- 評估了如何通過組合不同技術實現一個高度可用的（highly-available）系統
- 證明了最終一致性存儲系統可以用於生產環境，滿足應用的高要求
- 展示了若干優化技術，以滿足生產環境的非常嚴格的性能要求
本文章節結構介紹（略，見下面全文）。
2. 背景
Amazon 的電商平台由幾百個服務組成，它們協同工作，提供的服務包羅萬象，從推薦系統 到訂單處理到欺詐檢測等等。每個服務對外提供定義良好的 API，被其他服務通過網絡的方 式訪問。這些服務運行在分布在全球的數據中心中，成千上萬的伺服器組成的基礎設施之上 。有些服務是無狀態的（例如，聚合其他服務的響應的服務），有些是有狀態的（例如，基 於存儲在數據倉庫里的狀態，執行業務邏輯並產生響應的服務）。
傳統上，生產系統使用關係型資料庫來存儲狀態。但對很多 持久狀態的存儲 需求來說， 關係型資料庫並不是一種理想的方式。這一類型中的大多數服務只用主鍵去檢索，並不需要 RDBMS 提供的複雜查詢和管理功能。這些額外的功能需要昂貴的硬體和專門的技能，而實際 上服務根本用不到，最終的結果就是使用關係型資料庫非常不經濟。另外，這類資料庫的復 制功能很受限，而且通常是靠 犧牲可用性來換一致性 。雖然近些年有了一些改進，但總 體來說水平擴展（scale-out）以及使用智能（smart）partitioning 來做負載均衡還是很不 方便。
本文介紹 Dynamo 是如何解決以上需求的。Dynamo 有易用的 key/value 接口，高度可用 ，有定義清晰的一致性窗口（clearly defined consistency window），資源使用效率很高 ，並且有易用的水平擴展方案以解決請求量或數據增長帶來的挑戰。 每個使用 Dynamo 的 服務，使用的都是它們獨立的一套 Dynamo 系統 。
Each service that uses Dynamo runs its own Dynamo instances.
2.1 系統假設與需求
Dynamo 對使用它的服務有如下幾點假設。
查詢模型（Query Model）
通過唯一的 key 對數據進行讀寫。狀態以 二進位對象 （binary objects，e.g. blobs）形式存儲，以唯一的 key 索引。
任何操作都不會跨多個 data items（數據單元），沒有關係型 schema 需求。
Dynamo 面向的應用 存儲的都是相對較小的文件（一般小於 1 MB） 。
ACID 特性
ACID（Atomicity, Consistency, Isolation, Durability）是一組保證資料庫事務可 靠執行的特性。在資料庫領域，對數據的單次邏輯操作（single logical operation） 稱為一次事務（transaction）。 我們在 Amazon 的實踐表明，讓數據倉庫支持 ACID 會使得它的可用性（availability） 非常差，工業界和學術界也已經就這一點達成了廣泛共識 [5]。
Dynamo 的目標應用具有這樣的特點：如果能給可用性（ACID 裡面的 A）帶來很大提升 ，那犧牲一些一致性（C）也是允許的。
Dynamo 不提供任何隔離保證，並且只允許帶單個 key 的更新操作（permit only single key updates）。
效率（Efficiency）
系統需要運行在通用硬體（commodity hardware）之上。Amazon 的服務對延遲有著嚴格的 要求，通常用百分位值（percentile） P99.9 衡量。
考慮到對狀態數據的訪問是服務的核心操作之一，我們的存儲系統必須滿足那些嚴格的 SLA （見 Section 2.2）。另外，服務要有配置 Dynamo 的能力，以便能滿足服務的延遲和吞吐 需求。最終，就是在性能、成本效率、可用性和持久性之間取得折中。
其他方面
Dynamo 定位是 Amazon 內部使用，因此我們假設環境是安全的，不需要考慮認證和鑒權 等安全方面的問題。
另外， 由於設計中每個服務都使用各自的一套 Dynamo，因此 Dynamo 的初始設計規模是 幾百個存儲節點 。後面會討論可擴展性限制的問題，以及可能的解決方式。
2.2 SLA (Service Level Agreements)
要 保證一個應用完成請求所花的時間有一個上限 （bounded time），它所依賴的那些服 務就要有一個更低的上限。 對於給定的系統特性 ，其中最主要的是客戶端期望的 請求 率分布 （request rate distribution），**客戶端和服務端會定義一個 SLA（服務級別 協議）**來作為契約。
舉個簡單例子：某個服務向客戶端保證，在 500 QPS 的負載下，它處理 99.9% 的請求 所花的時間都在能 300ms 以內。
在 Amazon 的去中心化的、面向服務的基礎設施中，SLA 扮演著重要角色。例如，對購物 頁面的一次請求，在典型情況下會使渲染引擎向多達 150 個服務發送子請求，而這些子服 務又都有自己的依賴，最終形成一張多層的（more than one level）調用圖（call graph ）。為了保證渲染引擎能在一個上限時間內返回一個頁面，調用鏈中的所有服務就都必須遵 循各自的性能契約（contract）。
圖 1 是一張簡化之後的 Amazon 平台架構圖。可以看到，動態 web 內容由頁面渲染組件 提供，而它是通過調用其他的一些服務來完成這項工作的。
每個服務可以選擇不同類型的數據倉庫（data store）來管理（存儲）它們的狀態數據， 這些數據倉庫只能在各自的服務邊界（service boundaries）內訪問。一些服務會通過聚 合其他服務的數據來組合產生一個響應（composite response）。典型情況下，聚合服務（ aggregator service）是無狀態的，雖然它們大量使用緩存技術。
對於面向性能的 SLA（performance oriented SLA），業內一般習慣使用 平均值、中位數 和方差 來描述。但在 Amazon 我們發現，要打造一個讓所有用戶——而不是大部分用戶——都 有良好體驗的系統，以上 SLA 並不合適。例如， 如果使用了個性化推薦技術，那用戶的 訪問歷史越多，他的請求被處理的時間就越長，最終落到了性能分布的長尾區 。基於平均 值或中位數的 SLA 並不能反映這種情況。為了解決這個問題， 我們使用了 P99.9 分布。99.9% 這個精度是經過大量實驗分析，權衡了成本和性能之後得到的 。 我們在生產環境的實驗顯示，這比基於均值或中位數的 SLA 有更好的用戶體驗。
本文多處都將引用 P99.9 分布，這也顯示了 Amazon 的工程師對提高用戶體驗所做的持續 不斷的努力。一些基於均值的論文，我們會在它真正有意義的場景才拿出來作為比較，但我 們自己的工程和優化都不是以 均值 SLA 為核心的。某些技術，例如 write coordinator（寫操作協調者），是完全面向 P99.9 來控制性能的。
存儲系統在構建一個服務的 SLA 中經常扮演著重要角色，尤其是業務邏輯相對輕量的 場景，Amazon 的服務即屬於這一類。因此， 狀態管理 就成了服務的 SLA 的主要 部分 。
Dynamo 的設計目標之一就是：允許服務自己控制自己的系統特性——例如持久性和一 致性—— 讓服務自己決定如何在功能、性能和成本效率之間取得折中 。
One of the main design considerations for Dynamo is to give services control over their system properties, such as durability and consistency, and to let services make their own tradeoffs between functionality, performance and cost-effectiveness.
2.3 設計考慮
商業系統中數據複製算法一般都是同步的，以提供一個強一致性的數據訪問接口。 為了達到這種級別的一致性，這些算法被迫犧牲了某些故障場景下的數據可用性。例如， 如果數據有衝突，它們會禁止訪問這個數據，直到數據的不一致完全得到了解決。在早期，這 種 複製式資料庫 （replicated database）是可以工作的。
但眾所周知，分布式系統是無法同時滿足**強一致性、高可用性和正確處理網絡故障（CAP ）**這幾個條件的 [2, 11]。 因此，系統和應用都需要知道，在什麼場景下選擇滿足什麼 特性 。
對於 伺服器和網絡故障較高的場景 ，可以通過 樂觀複製 （optimistic replication ）技術增強 可用性 ，在後台將數據變動同步到其他節點，並發更新和失聯也是可以容忍 的。這種方式的問題是會 導致數據衝突，需要檢測並解決衝突 。而解決數據衝突又會帶 來兩個額外問題：
- 何時解決？
- 誰來解決？
Dynamo 設計為最終一致數據倉庫（eventually consistent data store），即，最終 所有的更新會應用到所有的副本。
何時解決衝突？
設計時的一個重要考慮是： 何時解決更新衝突 ，例如，是讀的時候還是寫的時候。
An important design consideration is to decide when to perform the process of resolving update conflicts, i.e., whether conflicts should be resolved during reads or writes.
一些傳統的數據倉庫是在 寫的時候解決衝突 ，這樣可以 保證讀的複雜度很低 [7]。 在這種系統中，任何時候 如果數據倉庫不能訪問所有（或者大多數）副本，寫就會被拒絕 。
Dynamo 的設計與此相反，它的目標是提供一個**「永遠可寫」（always writable）**的數據 倉庫（例如，一個對寫操作高度可用的數據倉庫）。對很多 Amazon 服務來說，拒絕寫 入會造成很差的用戶體驗。比如即使發生伺服器或網絡故障，也應該允許用戶往購物車添 加或刪除商品。 這個需求使我們將解決衝突的複雜度放到了讀操作，以保證寫永遠不會 被拒絕 。
誰來解決衝突？
下一個需要考慮的問題是： 誰來解決衝突 。 數據倉庫 和 應用 都可以做這件事情。
如果由數據倉庫來做，那選擇會相當受限。在這種情況下，數據倉庫只能使用一些 非常簡單的策略，例如**「最後一次寫有效」**（last write wins） [22]，來解決更新衝突。
另一方面，由於 應用理解數據描述的是什麼 （application is aware of the data schema）， 它可以自主選擇對用戶體驗最好的衝突解決算法 。例如，購物車應用可以選擇「 合併」衝突的版本，返回一個合併後的（unified）購物車。儘管這樣可以帶來很大的靈活性 ，但一些應用開發者並不想自己實現一套衝突解決機制，因此在這種情況下，解決衝突的問 題就下放給了數據倉庫，由後者來選擇一些簡單的策略，例如 「last write wins」。
其他設計原則
- 增量擴展性 （Incremental scalability）：應當支持 逐機器（節點）擴容 ，而 且對系統及運維人員帶來的影響儘量小
- 對稱性 （Symmetry）： 每個節點的職責應該是相同的 ，不應當出現某些節點承擔 特殊職責或特殊角色的情況。以我們的實踐經驗， 對稱性簡化了系統的交付和運維
- 去中心化 （Decentralization）： 「去中心化」是「對稱性」的進一步擴展 ，系統應 該是去中心化的、點對點的，而不應該是集中式控制的。在過去，集中式控制導致了很多 服務故障（outage），我們應當極力避免它。去中心化會使得系統更簡單、更具擴展性和 可用性
- 異構性 （Heterogeneity）：系統要能夠利用到基礎設施的異構性。例如， 負載的 分布要和存儲節點的能力成比例 。對於逐步加入能力更強的新節點，而不是一次升級所 有節點來說，這種異構支持能力是不可或缺的
3. 相關工作
3.1 點對點系統（Peer to Peer Systems）
一些點對點（peer-to-peer, P2P）系統關注了 數據存儲和分散 （data storage and distribution）的問題。
P2P 系統
第一代 P2P 系統，例如 Freenet 和 Gnutella，在文件共享系統（file sharing system） 領域使用廣泛。它們都是 非受信（untrusted）P2P 網絡 的代表，節點之間的 overlay （網絡術語，和 underlay 對應，請參考 Wikipedia 或其他資料，譯者注）鏈路都是隨機 （隨意）建立的（established arbitrarily）。在這種網絡中，一次查詢請求通常是 泛 洪（flood）到整張網絡，找到儘量多的共享這個數據的節點 。
結構化 P2P 系統
P2P 網絡到下一代，就是有名的 結構化 P2P 網絡 （structured P2P network）。這種 網絡使用了全局一致性協議（globally consistent protocol），保證 任何一個節點可以 高效地將查詢請求路由到存儲這個數據的節點 。
Pastry [16] 和 Chord [20] 這樣的系統 利用路由機制可以保證查詢在若干（有上限） 跳 （a bounded number of hops）之內收到應答。
為了減少多跳（multi-hop）路由帶來的額外延遲，一些 P2P 系統（例如 [14]）使用了 O(1)路由機制 ，在這種機制中， 每個節點維護了足夠多的路由信息 ，因此它可以 將（訪問數據的）請求在常量跳數（constant number of hops）內路由到合適的對端節點 。
包括 Oceanstore [9] 和 PAST [17] 在內的很多存儲系統都是構建在這種路由（routing） overlay 之上的。Oceanstore 提供全球分布的、事務型的、持久的存儲服務，支持分布在 很大地理範圍內的副本的串行化更新（serialized updates on widely replicated data） 。 為了支持並發更新，同時避免廣域鎖 （wide-are locking）內在的一些問題，它使用了一 種基於衝突解決（conflict resolution）的更新模型。conflict resolution 在 [21] 中 提出，用於減少事務異常中止（transaction abort）的數量。 Oceanstore 處理衝突的方式是 ：對並發更新進行排序（order），將排好序的若干個更新作為原子操作應用到所有副本 。 Oceanstore 是為在 不受信的基礎設施上做數據複製的場景 設計的。
作為對比，PAST 是在 Pastry 之上提供了一個簡單的抽象層，以此來提供持久和 不可變對 象 （persistent and immutable objects）。它假設 應用可以在它之上構建自己需要的 存儲語義 （storage semantics）（例如可變文件）。
3.2 分布式文件系統與資料庫
文件系統和資料庫系統領域已經對 通過分散數據（distributing data）來提高性能、可 用性和持久性 進行了廣泛研究。和 P2P 存儲系統只支持扁平命名空間 （flat namespace）相比， 典型的分布式文件系統都支持層級化的命名空間 （hierarchical namespace）。
- Ficus [5] 和 Coda [19] 這樣的系統通過文件複製來提高可用性，代價是犧牲一致性。 解決更新衝突一般都有各自特殊的解決方式
- Farsite [1] 是一不使用中心式伺服器（例如 NFS）的分布式文件系統，它通過複製實現 高可用和高擴展
- Google File System [6] 是另一個分布式文件系統，用於存儲 Google 內部應用的 狀態數據。GFS 的設計很簡單，一個主節點（master）管理所有元數據，數據進行分片（ chunk），存儲到不同數據節點（chunkservers）。
- Bayou 是一個分布式關係型資料庫系統，允許在失聯情況下進行操作（disconnected operation），提供最終一致性
在這些系統中，Bayou、Coda 和 Ficus 都支持失聯情況下進行操作，因此對網絡分裂和宕 機都有很強的彈性，它們的不同之處在於如何解決衝突。例如，Coda 和 Ficus 在系統層面 解決（system level conflict resolution），而 Bayou 是在應用層面（application level）。相同的是，它們都提供最終一致性。與這些系統類似， Dynamo 允許在網絡發生 分裂的情況下繼續執行讀寫操作，然後通過不同的衝突解決機制來處理更新衝突 。
分布式塊存儲系統（distributed block storage system），例如 FAB [18]，將一個大塊 分割成很多小塊並以很高的可用性的方式存儲。和這類系統相比， 我們的場景更適合使用鍵 值存儲 ，原因包括：
- 系統定位是 存儲相對較小的文件 （ size < 1 MB ）
- 鍵值存儲 （key-value store）更容易在應用級別 針對單個應用 （per-application）進行配置
Antiquity 是一個廣域分布式文件系統，設計用於處理多個伺服器掛掉的情況 [23]。它使 用 安全日誌 （secure log）保證數據完整性，在不同伺服器之間複製 secure log 來保 證持久性（durability），使用 拜占庭容錯協議 （Byzantine fault tolerance protocols）保證數據一致性。與此不同， Dynamo 並不將數據完整性和安全性作為主要關 注點，因為我們面向的是受信環境 。
Bigtable 是一個管理結構化數據（structured data）的分布式文件系統，它維護了一 張稀疏的多維有序映射表（sparse, multi-dimensional sorted map），允許應用通過多重 屬性訪問它們的數據（access their data using multiple attributes） [2]。與此不同 ， Dynamo 面向的應用都是以 key/value 方式訪問數據的，我們的主要關注點是高可用 ，即使在發生網絡分裂或伺服器宕機的情況下，寫請求也是不會被拒絕的。
傳統的複製型關係資料庫系統（replicated relational database systems）都將關注點放 在 保證副本的強一致性 。雖然強一致性可以 給應用的寫操作提供方便的編程模型 ， 但導致系統的擴展性和可用性非常受限 [7]，無法處理網絡分裂的情況。
3.3 討論
Dynamo 面臨的需求使得它與前面提到的集中式存儲系統都不相同。
首先，Dynamo 針對的主要是 需要「永遠可寫的」（always writable）數據倉庫的應用 ， 即使發生故障或並發更新，寫也不應該被拒絕。對於 Amazon 的很多應用來說，這一點是非 常關鍵的。
第二，Dynamo 構建在 受信的、單一管理域的基礎設施 之上。
第三，使用 Dynamo 的應用 沒有層級命名空間（hierarchical namespace）的需求 （這是很 多文件系統的標配），也沒有複雜的關係型 schema 的需求（很多傳統資料庫都支持）。
第四，Dynamo 是為 延遲敏感型應用 （latency sensitive application）設計的，至少 99.9% 的讀寫操作都要在幾百毫秒內完成。為了到達如此嚴格的響應要求，在多節點 之間對請求進行路由的方式（被很多分布式哈希表系統使用，例如 Chord 和 Pastry ）就無法使用了。因為多跳路由會增加響應時間的抖動性，因此會增加長尾部分的延遲。 Dynamo 可以被描述為：一個 零跳（zero hop）分布式哈希表（DHT） ，每個節點在本地 維護了足夠多的路由信息，能夠將請求直接路由到合適節點。
4. 系統架構
生產級別的存儲系統的架構是很複雜的。除了最終存儲數據的組件之外，系統還要針對下列 方面制定可擴展和健壯的解決方案：負載均衡、成員管理（membership）、故障檢測、故障 恢復、副本同步、過載處理（overload handling）、狀態轉移、並發和任務調度、請求 marshalling、請求路由（routing）、系統監控和告警，以及配置管理。
詳細描述以上提到的每一方面顯然是不可能的，因此本文將關注下面幾項 Dynamo 用到的分 布式系統核心技術：
- partitioning（分區，經哈希決定將數據存儲到哪個/些節點）
- 複製（replication）
- 版本化（versioning）
- 成員管理（membership）
- 故障處理（failure handling）
- 規模擴展（scaling）
Partition
- 技術： 一致性哈希
- 好處：增量可擴展性
寫高可用
- 技術：讀時協調（解決衝突）的 向量時鐘 （vector clocks with reconciliation during reads）
- 好處：version size（？）和更新頻率（update rates）解耦
短時故障處理
- 技術： 寬鬆的選舉和 hinted handoff （移交給其他節點處理，附帶提示信息）
- 好處：部分副本不可用時，仍然可以提供高可用性和持久性
持久（permanent）故障恢復
- 技術： 基於 Merkle tree 的逆熵 （anti-entropy）
- 好處：後台同步版本不一致的副本
成員管理和故障檢測
- 技術： 基於 Gossip 的成員管理協議和故障檢測
- 好處：保持了 架構的對稱性 ，無需一個中心組件（centralized registry）來存儲成員和節點狀態等信息
4.1 系統接口
Dynamo 存儲鍵值對象的接口非常簡單，它提供兩個操作：
get()
put()
get(key) 會定位到存儲系統中 key 對應的所有對象副本， 返回對象 ——可能是單個對 象，也可能是一個對象列表（有衝突情況下，包括了所有版本）—— 以及一個 context（ 上下文） 。
put(key) 確定對象應該存放的位置，然後寫到相應的磁碟。
context 包含了系統中對象的元數據，例如對象的版本， 對調用方是不透明的 （ opaque）。 上下文信息是和對象存儲在一起的 ，這樣系統很 容易驗證 put 請求的 context 是否合法 。
Dynamo 將調用方提供的 key 和對象都視為不透明的字節序列 （opaque array of bytes） 。它 對 key 應用 MD5 哈希得到一個 128bit 的 ID，並根據這個 ID 計算應該存儲 到哪些節點 。
Dynamo treats both the key and the object supplied by the caller as an opaque array of bytes. It applies a MD5 hash on the key to generate a 128-bit identifier, which is used to determine the storage nodes that are responsible for serving the key.
4.2 數據分散（Partitioning）算法
Dynamo 的核心需求之一是：系統必須支持 增量擴展 （scale incrementally）。 這就要求有一種機制能夠將數據分散到系統中的不同的節點（例如，以一台機器作為一個 節點的維度）上。
Dynamo 的 分散方案基於一致性哈希 [10]。在一致性哈希中，哈希函數的 輸出是一個 固定的範圍，通常作為一個循環空間，或稱環（ring） 。 每個節點都會隨 機分配一個在這個循環空間內的值 ，這個值代表了節點在這個環上的位置。
用如下方式找到一個數據項（data item）對應的存儲節點：
- 首先對它的 key 做哈希得到一個哈希值
- 然後，在環上沿著順時針方向找到第一個 所帶的值比這個哈希值更大的節點 （前面 提到每個節點都會被分配一個值）
即，每個節點要負責環上從它自己到它的下一個節點之間的區域。 一致性哈希的主要好處是 ：添加或刪除節點只會影響相鄰的節點，其他節點不受影響。
The principle advantage of consistent hashing is that departure or arrival of a node only affects its immediate neighbors and other nodes remain unaffected.
但是， 初級的一致性哈希算法在這裡是有一些問題的 。 首先，給每個節點隨機分配一個位置會導致數據和負載的非均勻分布。 其次，初級的一致性哈希算法沒有考慮到節點的異構因素，導致性能不理想。
為了解決這些問題，Dynamo 使用了一致性哈希的一個變種（和 [10, 20] 的類似）： 每個 節點並不是映射到環上的一個點，而是多個點 。
Intead of mapping a node to a single point in the circle, each node gets assigned to multiple points in the ring.
為了實現這種設計，Dynamo 使用了 虛擬節點 （virtual node）的概念。一個虛擬節點 看上去和一個普通節點一樣，但 實際上可能管理不止一台虛擬節點 。具體來說， 當一個新節點添加到系統後，它會在環上被分配多個位置（對應多個 token） 。 我們會在 Section 6 介紹 Dynamo 分散策略（算法）的深入調優 。
虛擬節點可以代來如下好處：
- 當一個節點不可用時（故障或例行維護），這個節點的負載會均勻分散到其他可用節點上
- 當一個節點重新可用時，或新加入一個節點時，這個節點會獲得與其他節點大致相同的 負載
- 一個節點負責的虛擬節點的數量可用根據節點容量來決定，這樣可用充分利用物理基礎 設施中的異構性信息
4.3 數據複製（Replication）
為了實現高可用性和持久性，Dynamo 將數據複製到多台機器上。每個數據會被複製到 N 台 機器，這裡的 N 是每套 Dynamo 可以自己配置的。
上節介紹到，**每個 key k，會被分配一個 coordinator（協調者）**節點。 coordinator 負責落到它管理的範圍內的數據的複製 。它除了自己存儲一份之外，還會 在環上順時針方向的其他 N-1 個節點存儲一份副本。因此在系統中，每個節點要負責從 它自己往後的一共 N 個節點。
例如，圖 2 中，B 除了自己存儲一份之外，還會將其複製到 C 和 D 節點。因此，D 實際 存儲的數據，其 key 的範圍包括 (A, B] 、 (B, C] 和 (C, D] （例如，落在 (A, B] 範圍內的 key 會沿順時針方向找到第一個值比它大的節點，因此找到的是 B，而 B 會 將自己存儲的數據複製到 C 和 D，因此 D 會包含 key 在 (A, B] 範圍內的對象。其他 幾個範圍也是類似的。譯者注）。
存儲某個特定 key 的所有節點組成一個列表，稱為 preference list （優先列表）。 我們在 4.8 節會看到，Dynamo 的設計是， 對於給定的 key，每個節點都能決定哪些 節點可以進入這個列表 。 為了應對節點失敗的情況，preference list 會包含多餘 N 個節 點 。
另外注意，由於我們引入了虛擬節點，存儲一個 key 的 N 個節點，實際上對應的物理節 點可能少於 N 個（例如，一個節點可能會占用環上的不止一個節點）。為了避免這個問題 ， preference list 在選擇節點的時候會跳過一些位置，以保證 list 裡面的節點都在不 同的物理節點上 。
4.4 數據版本化（Data Versioning）
Dynamo 提供最終一致性，所有更新操作會異步地傳遞給所有的副本。
put() 操作返回時，數據（更新）可能還沒有應用到所有副本，因此緊接著的 get() 操作可能獲取不到最新數據。在沒有故障的情況下，傳遞更新的耗時有一個上限；但在特定 故障場景下（例如伺服器宕機或網絡分裂），更新可能會在限定的時間內無法傳遞到所有副 本。
Amazon 有些應用是可以容忍這種不一致性的，應用在這種情況下能繼續運行。例如，購物 車應用要求「添加到購物車」的請求永遠不能被丟失或拒絕。如果購物車的最新狀態不可用， 而用戶對一個稍老版本的購物車狀態做了修改，那這種修改也是有意義的，需要保留；但它 不能直接覆蓋最新的狀態，因為最新的狀態中可能也有一些修改需要保留。這裡要注意，不 管是「添加到購物車」還是「從購物車刪除」，在系統中轉換成的都是 Dynamo 的 put() 操作 。如果最新的狀態不可用，而用戶又基於稍的大版本做了修改，那這兩個版本都需要保留， 由隨後的步驟來處理更新衝突。
如何解決更新衝突
為了滿足以上需求，Dynamo 將每次修改結果都作為一個新的、不可變的版本 。
Dynamo treats the result of each modification as a new and immutable version of the data.
即，允許系統中同時存在多個不同版本。
衝突調和（使一致化）方式
- syntactic reconciliation（ 基於句法的調和 ）
- semantic reconciliation（ 基於語義的調和 ）
在 大部分情況下，新版本都包含老版本的數據，而且系統自己可以判斷哪個是權威版本 （syntactic reconciliation）。
但是，在發生故障並且存在並發更新的場景下，版本會發生分叉（version branching）， 導致衝突的對象版本。 系統本身無法處理這種情況，需要客戶端介入，將多個分支合併成 一個 （semantic reconciliation）。一個典型的例子是：合併多個不同版本的購物車。 有了這種調和機制（reconciliation mechanism），「添加到購物車」操作就永遠不會失敗 ；但是，這種情況會導致 已經刪除的商品偶爾又在購物車中冒出來 （resurface）。
有很重要的一點需要注意：某些故障模式（failure mode）會導致存在多個衝突的版本，而 不僅僅是兩個。伺服器故障或網絡分裂會導致一個對象有多個版本，每個版本有各自的子歷 史（version sub-histories），隨後要由系統來將它們一致化。這需要 將應用 設計為：顯式承認多版本存在的可能性（以避免丟失任何更新）
向量時鐘
Dynamo 使用向量時鐘（vector clock）[12] 來跟蹤同一對象不同版本之間的因果性。 一個向量時鐘就是一個 (node, counter) 列表。一個向量時鐘關聯了一個對象的所有版 本，可以通過它來判斷對象的兩個版本是否在並行的分支上，或者它們是否有因果關係。 如果對象的第一個時鐘上的所有 counter 都小於它的第二個時鐘上的 counter，那第一個 時鐘就是第二的祖先，可以安全的刪除；否則，這兩個修改就是有衝突的，需要 reconciliation 。
在 Dynamo 中， 客戶端更新一個對象時，必須指明基於哪個版本進行更新 。流程是先執 行讀操作，拿到 context，其中包含了 vector clock 信息，然後寫的時候帶上這個 context。
在處理讀請求的時候，如果 Dynamo 能夠訪問到多個版本，並且無法 reconcile 這些版本 ，那它就會返回所有版本，並在 context 中附帶各自的 vector clock 信息。 基於 context 指定版本更新的方式解決了衝突 ，將多個分支重新合併為一個唯 一的新分支。
An update using this context is considered to have reconciled the divergent versions and the branches are collapsed into a single new version.
一個具體例子
我們通過 圖 3 來展示 vector clock 是如何工作的。
首先，客戶端寫入一個對象。處理這個 key 的寫請求的節點 Sx 增加 key 的序列號（計 數），並用這個序列號創建對象的 vector clock。至此，系統有了一個對象 D1 和它的 時鐘 [(Sx, 1)] 。
第二步，客戶端更新這個對象。假設還是 Sx 處理這個請求。此時，系統有了對象 D2 和它的時鐘 [(Sx, 2)] 。 D2 是 D1 的後代，因此可以覆蓋 D1 ； 但是，D1 在 其他節點上的副本可能還沒有看到 D2 這次更新 。
第三步，假設還是這個客戶端，再次更新了對象，並且這次是由另外的一個節點 Sy 處理 請求。此時，系統有了 D3 和它的時鐘 [(Sx, 2), (Sy, 1)] .
接下來，假設另一個客戶端讀取 D2 ，並嘗試更新它，寫請求由另一個節點 Sz 處理。 現在，系統有 D4 （ D2 的後代），版本 clock 是 [(Sx, 2), (Sz, 1)] 。如果一個節 點知道 D1 和 D2 ，那它收到 D4 和它的 clock 後，就可以斷定 D1 和 D2 被同 一個新數據覆蓋了，因此可以安全地刪除 D1 和 D2。但如果一個節點只知道 D3 ，那它受 到 D4 後就看不出這兩個版本有何因果關係。 換言之，D3 和 D4 各自的改動並沒 有反映在對方之中。因此這兩個版本都應當被保留，然後交給客戶端，由客戶端（在下一次 讀到時候）執行 semantic reconciliation 。
現在，假設一些客戶端把 D3 和 D4 都讀到了（ context 會同時顯示 D3 和 D4 ）。讀操作返回的 context 綜合了 D3 和 D4 的 clock，即 [(Sx, 2), (Sy, 1), (Sz, 1)] 。如果客戶端執行 reconciliation，並且節點 Sx 執行協調寫（coordinates the write）， Sx 會更新自己在 clock 中的序列號。最終新生成的數據 D5 的 clock 格式如下： [(Sx, 3), (Sy, 1), (Sz, 1)] 。
Vector clock 的潛在問題
vector clock 的一個潛在問題是： 如果有多個節點先後 coordinate 同一個對象 的寫操作，那這個對象的 clock vector 會變得很長 。但在實際中這不太可能發生，因為 寫操作 coordination 只會由 preference list 中前 N 個 節點中的一個來執行。 只有在網絡分裂或多台伺服器掛掉的情況下，寫操作才可能由非 preference list 前 N 個 節點來執行，導致 vector clock 變長。在這種情況下，應該要限制 vector clock 的長度 。
Dynamo 採用了一種 clock 截斷方案（clock truncation scheme）： 另外保存一個和 (node, counter) 對應的時間戳，記錄對應的節點最後一次更新該記錄 的時間。當 vector clock 里的 (node, counter) 數量達到一個閾值（例如，10）時， 就刪除最老的一項。
顯然，這種截斷方案會給 reconciliation 帶來一定問題，因為截斷後可能無法精確判斷部 分後代的因果關係。但到目前為止，我們還沒有在生產環境遇到這個問題，因此沒有繼續深 入研究下去。
4.5 get() 和 put() 的執行過程
在 Dynamo 中，任何存儲節點都可以接受任何 key 的 get 和 put 操作請求。
Any storage node in Dynamo is eligible to receive client get and put operations for any key.
本節先介紹在無故障場景下這些操作是如何執行的，下一節介紹有故障的場景。
get 和 put 操作由 Amazon 基礎設施相關的請求處理框架發起，使用 HTTP。 客戶端有兩種選擇：
- 將請求路由到負載均衡器，由後者根據負載信息選擇一個後端節點
- 使用能感知 partition 的客戶端，直接將請求路由到某 coordinator 節點
第一種方式的好處是使用客戶端的應用不需要了解任何 Dynamo 相關的代碼，第二種的好處 是延遲更低，因為跳過了一次潛在的轉發步驟。
負責處理讀或寫請求的節點稱為 coordinator。 通常情況下 ，這是 preference list 內前 N 個節點中的 第一個節點 。如果請求是經過負載均衡器轉發的，那這個請求 可能會被轉發到環上的任意一個節點。在這種情況下，如果收到請求的節點不是 preference list 的 前 N 個節點中的一個，那它就不會處理這個請求，而是將其轉發到 preference list 前 N 個節點中的第一個節點。
讀或寫操作需要 preference list 中前 N 個節點處於健康狀態，如果有 down 或不可 訪問狀態的節點，要跳過。如果所有節點都是健康的，那就取 preference list 的前 N 個 節點。如果發生節點故障或網絡分裂，優先訪問 preference list 中編號較小的節點。
讀寫操作仲裁算法
為了保證副本的一致性，Dynamo 使用了一種類似仲裁系統（quorum systems）的一致性協議。 這個協議有兩個配置參數： R 和 W ：
R
W
設置 R + W > N（ R 或 W 至少有一個超過半數 N/2，譯者注）， 就得到了一 個類似仲裁的系統 。
在這種模型下，一次 get （或 put ）的延遲由 R （或 W ）個 副本中最慢的一個決 定 。因此，為了降低延遲， R 和 W 通常設置的比 N 小。
寫和讀過程
當收到一個 put() 請求後，coordinator 會為新版本生成 vector clock，並將其保存到 節點本地；然後，將新版本（及對應的新 vector clock）發送給 N 個排在最前面的、可到 達的節點。只要有至少 W-1 個節點返回成功，這次寫操作就認為是成功了。
類似地，對於一次 get() 請求，coordinator 會向排在最前面的 N 個（highest-ranked ）可訪問的節點請求這個 key 對應的數據的版本，等到 R 個響應之後，就將結果返回給客 戶端。如果 coordinator 收集到了多個版本，它會 將所有它認為沒有因果關係的版本返 回給客戶端 。客戶端需要對版本進行 reconcile，合併成一個最新版本，然後將結果寫回 Dynamo。
4.6 短時故障處理: Hinted Handoff（移交給其他節點臨時保存）
如果使用傳統仲裁算法，Dynamo 無法在伺服器宕機或網絡分裂的時候仍然保持可用，而且 在遇到最簡單故障情況下，持久性（durability）也會降低。
因此，Dynamo 採用了一種 寬鬆的仲裁機制 （sloppy quorum）： 所有讀和寫操作在 preference list 的前 N 個健康節點上執行 ；注意這 N 個節點不一定就是前 N 個節點， 因為遇到不健康的節點，會沿著一致性哈希環的順時針方向順延。
以圖 2 的配置為例，其中 N=3。 如果 A 臨時不可用，正常情況下應該到達 A 的寫請求就 會發送到 D 。這樣設計是為了保證期望達到的可用性和持久性。 發送到 D 的副本的元 數據中會提示（hint）這個副本本來應該發送給誰 （這裡是 A），然後這個數據會被 D 保存到本地的一個獨立資料庫中，並且有一個 定期任務不斷掃描，一旦 A 可用了，就將 這個數據發送回 A ，然後 D 就可以從本地資料庫中將其刪除了，這樣系統內的副本數還 是保持不變。
使用這種 hinted handoff 的方式，Dynamo 保證了在節點或網絡發生短時故障時讀和寫 操作不會失敗 。希望可用性最高的應用可以將 W 設為 1，這樣可以保證只要一個節點 完成寫，這次寫操作就被系統接受了。在這種情況下，除非全部節點都不可用，否則寫操作 就不會被拒絕。但實際上，大部分 Amazon 的應用都是設置一個比 1 大的值，以達到期望 的持久性（durability）等級。我們會在第 6 節更深入地討論 N 、 R 和 W 的配置。
高度可用的存儲系統必須能夠處理整個數據中心掛掉的情況。 掉電、製冷失效、網絡故 障以及自然災難都會導致整個數據中心發生故障。Dynamo 可以配置 向多個數據中心同步 副本 ，只要 將 preference list 里的節點分散到不同數據中心 。這些數據中心之間 通過高速網絡互連。這使得我們可以在整個數據中心掛掉的情況下仍然可以提供服務。
4.7 持久（permanent）故障處理: 副本跨數據中心同步
在節點成員變動較小、節點故障只是短時的情況下，hinted handoff 方式工作良好。但也 有一些場景，在 hinted 副本移交給原本應該存儲這個副本的節點之前，該副本就不可用了 。為了解決這個問題，以及其他威脅到持久性（durability）的場景，Dynamo 實現了一種 逆熵（副本同步）協議 來 保證副本是同步的 。
To handle this and other threats to durability, Dynamo implements an anti-entropy (replica synchronization) protocol to keep the replicas synchronized.
Merkle Tree
為了實現 快速檢測副本之間的不一致性，以及最小化轉移的數據量 ，Dynamo 使用了 Merkle trees [13].
一個 Merkle tree 就是一個 哈希樹 ，其葉子節點是 key 對應的 value 的哈希值 。 父節點是其子節點的哈希 。
Merkle tree 的主要優點是：
- 每個分支都可以獨立查看（check），節點無需下載整棵樹或者整個數據集
- 減少檢查副本一致性時所需傳輸的數據量
例如，如果兩棵樹的根節點的哈希值相同，那這兩棵樹的葉子節點必然相同，這兩台 node 之間就無需任何同步；否則，就說明兩台 node 之間的某些副本是不同的，這種情 況下兩台 node 就需要交換樹的子節點哈希值，直到到達葉子節點，就找到了未同步（out of sync）的 key。Merkle tree 最小化了同步時需要轉移的數據量， 減少了逆熵過程中 讀取磁碟的次數 。
Dynamo 使用 Merkle tree 實現 逆熵的過程 如下： 每個節點為每段 key range（一台 虛擬節點所覆蓋的 key 的範圍）維護了一棵單獨的 Merkle tree 。
這使得節點之間可以比較 key range，確定其維護的 range 內的 key 是否是最新的（up to date）。在這種方案中，兩個節點會交換他們都有的 key range 所對應的 Merkle tree 的 根節點。然後，基於前面提到的樹遍歷方式， node 可以判斷是是否有不一致，如果有，就 執行同步。
這種方案的缺點是： 每當有節點加入或離開系統時，一些 key range 會變，因此對應的 tree 需要重新計算 。我們會在 6.2 節介紹如何通過改進的 partitioning scheme 解決 這個問題。
4.8 節點成員（Membership）管理和故障檢測
4.8.1 哈希環（ring）成員
在 Amazon 的環境中，節點服務不可用（故障或維護導致的）通常情況下持續時間都很短， 但也存在中斷比較長的情況。一個節點服務中斷並不能說明這個節點永久性的離開了系統， 因此不應該導致系統對 partition 進行再平衡（rebalance），或者修復無法訪問的副本。 與此類似，無意的手動操作可能導致新的節點加入到 Dynamo。
因此，為了避免以上這些問題，我們決定 使用顯式機制（explicit mechanism）來向 Dynamo Ring 增刪節點 。管理員通過命令行或 web 方式連接到 Dynamo node，然後下發 一個成員變更命令，來將這個 node 添加到 ring 或從 ring 刪除。負責處理這個請求的 node 將成員變動信息和對應的時間寫入持久存儲。成員變動會形成歷史記錄，因為一個節 點可能會多次從系統中添加和刪除。Dynamo 使用一個 gossip-based 的算法通告（ propagete）成員變動信息 ，維護成員的一份最終一致視圖。
每個節點每秒會隨機選擇另一個節點作為對端，這兩個節點會高效地 reconcile 它們的成 員變動歷史。
一個節點第一次起來時，首先會選擇它的 token 集合（一致性哈希空間內的虛擬節點 ），然後 將節點映射到各自的 token 集合 。
When a node starts for the first time, it chooses its set of tokens (virtual nodes in the consistent hash space) and maps nodes to their respective token sets.
映射關係會持久存儲到磁碟上，初始時只包含本節點（local node）和 token set。存 儲在不同 Dynamo 節點上的 映射關係，會在節點交換成員變動歷史時被 reconcile 。因 此，partitioning 和 placement（數據的放置信息）也會通過 gossip 協議進行擴散， 最 終每個節點都能知道其他節點負責的 token 範圍 。
The mappings stored at different Dynamo nodes are reconciled during the same communication exchange that reconciles the membership change histories.
Therefore, partitioning and placement information also propagates via the gossip-based protocol and each storage node is aware of the token ranges handled by its peers.
這 使得每個節點可以將一個 key 的讀/寫操作直接發送給正確的節點 進行處理。
4.8.2 系統外部發現（External Discovery）和種子節點
以上機制 可能導致 Dynamo ring 在邏輯上臨時分裂 。
例如，管理員先聯繫 node A，將 A 將入 ring，然後又聯繫 node B 加入 ring。在這種情 況下，A 和 B 都會認為它們自己是 ring 的成員，但不會立即感知到對方。
為了避免邏輯分裂，我們會將一些 Dynamo 節點作為種子節點。種子節點是通過外部機 制（external mechanism）發現的，所有節點都知道種子節點的存在。因為所有節點最終都 會和種子節點 reconcile 成員信息，所以邏輯分裂就幾乎不可能發生了。
種子或者從靜態配置文件中獲取，或者從一個配置中心獲取。通常情況下，種子節點具有普 通節點的全部功能。
4.8.3 故障檢測
故障檢測在 Dynamo 中用於如下場景下跳過不可達的節點：
- get() 和 put() 操作時
- 轉移 partition 和 hinted replica 時
要避免嘗試與不可達節點通信，一個 純本地概念（pure local notion）的故障檢測 就 足夠了：節點 B 只要沒有應答節點 A 的消息，A 就可以認為 B 不可達（即使 B 可以應答 C 的消息）。
在客戶端有持續頻率的請求的情況下，Dynamo ring 的節點之間就會有持續的交互；因此只 要 B 無法應答消息，A 可以很快就可以發現；在這種情況下，A 可以選擇和與 B 同屬一個 partition 的其他節點來處理請求，並定期地檢查 B 是否活過來了。
在沒有持續的客戶端請求的情況下，兩個節點都不需要知道另一方是否可達。
In the absence of client requests to drive traffic between two nodes, neither node really needs to know whether the other is reachable and responsive.
去中心化故障檢測協議使用簡單的 gossip 風格協議，使得系統內的每個節點都可以感知 到其他節點的加入或離開。想詳細了解去中心化故障檢測機制及其配置，可以參考 [8]。
Dynamo 的早期設計中使用了一個去中心化的故障檢測器來維護故障狀態的全局一致視圖 （globally consistent view of failure state）。
後來我們發現，我們 顯式的節點加入和離開機制 使得這種全局一致視圖變得多餘了。因 為節點的真正（permanent）加入和離開消息，依靠的是我們的顯式添加和刪除節點機制， 而臨時的加入和離開，由於節點之間的互相通信（轉發請求時），它們自己就會發現。
4.9 添加/移除存儲節點
當一個新節點 X 加入到系統後，它會 獲得一些隨機分散在 ring 上的 token 。對每 個分配給 X 的 key range，當前可能已經有一些（小於等於 N 個）節點在負責處理了 。因此,將 key range 分配給 X 後，這些節點就不需要處理這些 key 對應的請求了，而 要將 keys 轉給 X 。
考慮一個簡單的情況： X 加入 圖 2 中 A 和 B 之間。這樣， X 就負責處理落到 (F, G], (G, A] and (A, X] 之間的 key。結果， B 、 C 和 D 節點就不需負責相應 range 了。因此，在收到 X 的轉移 key 請求之後， B、C 和 D 會向 X 轉移相 應的 key 。當移除一個節點時，key 重新分配的順序和剛才相反。
我們的實際運行經驗顯示，這種方式 可以在存儲節點之間保持 key 的均勻分布 ，這對 於保證延遲需求和快速 bootstrapping 是非常重要的。另外，在源和目的節點之間加了確 認（轉移），可以保證不會轉移重複的 key range。
5. 實現
Dynamo 中的 每個存儲節點上主要有三個組件 ，都是用 Java 實現的：
- request coordination（請求協調）組件
- 成員驗證和故障檢測組件
- 本地持久存儲引擎
本地存儲引擎
Dynamo 的本地持久存儲組件支持以插件的方式使用不同的存儲引擎。在使用的引擎包括：
- Berkeley Database (BDB) Transactional Data Store2
- BDB Java Edition
- MySQL
- an in-memory buffer with persistent backing store
將其設計為可插拔的原因是： 為不同應用訪問類型選擇最合適的存儲引擎 。例如，BDB 通常用於處理幾十 KB 大小的對象，而 MySQL 可以處理更大的對象。應用可以根據它們的 對象大小分布選擇合適的持久化引擎。
我們生產環境的 Dynamo 大部分使用的都是 BDB Transactional Data Store。
請求協調
request coordination 組件構建在一個事件驅動的消息系統之上，其中的消息處理 pipeline 分為多個階段，和 SEDA 架構類似 [24]。所有通信都基於 Java NIO channel 實現。
coordinator 代替客戶端執行讀和寫請求：讀操作時會從一個或多個節點收集數據，寫操作 時會向一個或多個節點存儲數據。每個客戶端請求都會 在收到這個請求的節點上創建一個狀 態機 。這個狀態機包含了識別 key 對應的節點、發送請求、等待響應、重試、處理響應和 組合響應返回給客戶端等所有邏輯。
read coordination
每個狀態機處理且只處理一個客戶端請求。例如，一個讀操作實現了包含如下步驟的狀態機：
- 發送讀請求給節點
- 等待所需的最少數量響應
- 如果在規定的上限時間內收到的響應數量太少，認定請求失敗
- 否則，收集對象的所有版本，確定應該返回哪些
- 如果打開了版本化（versioning）配置，執行 syntactic reconciliation，生成一個不 透明的寫上下文（context），其中包含了合併之後的版本對應的的 vector clock
為了描述的簡單，以上沒有提及故障處理和重試的步驟。
讀操作的響應發送給調用方之後，狀態機會繼續等待一小段時間，接收可能的有效響應（ outstanding responses，例如最小數量響應之外的其他節點的響應，譯者注）。
如果返回中有過期版本（stale version），coordinator 就需要合併版本，並將最新版本 更新回這些節點。這個過程稱為**「讀時修復」（read repair） ，因為它 在一個樂觀的 時間點**（at an opportunistic time） 修復了那些錯過了最新更新的副本 （replicas that have missed a recent update）， 減少了逆熵協議的工作 （本來應該是稍後由逆 熵協議做的）。
write coordination
前面提到過，寫請求是由 preference list 內的前 N 個節點中的任意一個 coordinate 的 。總是讓 N 個節點中的第一個來 coordinate 有一些好處，例如可以使得在同一個地方完 成寫操作的順序化（serializing all writes），但是，這種方式也有缺點：它會導致不均 勻的負載分布，損害 SLA。這是因為對象請求並不是均勻分布的（request load is not uniformly distributed across objects）。
為了解決這個問題， preference list 內的所有 N 個節點都可以 coordinate 寫操作 。 而且，因為一個寫操作之前通常有一個讀操作，因此寫操作的 coordinator 都選擇為： 前 一次讀操作返回最快的那個節點 ，這個信息存儲在讀操作返回的上下文中。
這項優化還使在下一次讀取時，前一次讀操作選中的存儲這個數據的節點更容易被選中，提 高了「讀取剛寫入的數據」（「read-your-writes」）的機率。
This optimization enables us to pick the node that has the data that was read by the preceding read operation thereby increasing the chances of getting 「read-your-writes」 consistency.
同時，還降低了請求處理性能的抖動性，提高了 P99.9 性能。
6. 測試結果及學到的經驗
Dynamo 被幾種不同類型的服務使用，每種場景下的配置不同。這些不同體現在 vesion reconciliation 邏輯和讀/寫仲裁特點上。幾種主要的場景：
- 業務邏輯相關的 reconciliation ：這種場景使用很廣。每個數據對象都會複製到不同節 點上，發生 版本衝突時由應用執行自己的 reconciliation 邏輯 。前文提到的購物 車服務就是一個典型的例子，應用自己來合併衝突的購物車版本
- 基於時間戳的 reconciliation ：和第一種的不同僅僅是 reconciliation 機制。當 發生版本衝突時，Dynamo 根據**「最後一次寫勝出」**（last write wins）機制，例如， 選擇時間戳最近的一個版本作為最終版本。一個例子是維護客戶 session 信息的服務
- 高性能讀引擎 ：雖然 Dynamo 設計為永遠可寫（always writeable） 數據倉庫, 但 一些服務通過 對 Dynamo 的仲裁特性進行調優（tuning），而將其作為一個高性能讀引 擎使用 。典型情況下，這類服務有很高的讀頻率和很小的寫頻率。 在這種配置中， R 一般設為 1，W 設為 N 。對於這些服務，Dynamo 提供了 partition 和數據跨 多節點複製的能力，因而提供了增量可擴展性。 數據的權威持久緩存 （the authoritative persistence cache for data）存儲在更重量級的後端存儲中（more heavy weight backing stores）。 維護產品目錄和促銷商品的服務 會用到這種類型 的 Dynamo 配置
Dynamo 的最大優勢是： 客戶端應用可以通過對 N、R 和 W 三個參數進行調優來達到期 望的性能、可用性和持久性等級 。
The main advantage of Dynamo is that its client applications can tune the values of N, R and W to achieve their desired levels of performance, availability and durability.
例如，N 的大小決定了每個對象的持久性。Dynamo 用戶最常用的 N 配置是 3。
W 和 R 的值會影響對象的可用性、持久性和一致性。例如，如果 W 設為 1，那隻要系統還 有一台正常的 node，寫操作就不會被拒絕。但是，太小的 W 和 R 配置會增加不一致的風 險，因為一次寫操作即使在沒有大多數副本都寫成功的情況下，還是會給客戶端返回成功。 這也導致存在一個 風險窗口 （vulnerability window）： 一次寫操作即使只在少量節 點上完成了持久化，也會向客戶端返回成功 。
傳統觀點認為，持久性和可用性是相伴而生（go hand in hand）的，但在這裡不一定成立。 例如，增加 W 就會減小持久性的風險窗口；但是，這可能會增加請求被拒絕的機率（因此 降低了可用性），因為這種情況下需要更多的健康存儲節點來處理寫請求。
我們 最常用的 Dynamo 集群 (N,R,W) 配置是 (3,2,2) 。這個配置符合我們所需的 性能、持久性、一致性和可用性（SLA）等級。
本節所有的數據都是從一套線上 Dynamo 環境獲得的，配置是 (3,2,2) ， 有幾百台節點（a couple hundred nodes），配置利用到了異構硬體信息。
之前我們提到，每套 Dynamo 的節點都是跨數據中心部署的，這些數據中心之間通過高速網 絡互聯。執行一次成功的 get （或 put ）需要 R （或 W ）個節點向 coordinator 發送響應，因此很明顯，數據中心之間的時延會影響到響應時間，因此在選擇節點（以及它 所在的數據中心的位置）的時候要特別注意，以保證能滿足應用期望的 SLA。
6.1 性能和持久性的平衡
雖然 Dynamo 的首要設計目標是一個高可用數據倉庫，但性能指標在 Amazon 也同樣重要。 前面提到過，為了提供一致的用戶體驗，Amazon 的服務會設置一個很高的用百分比衡量的 （例如 P99.9 或 P99.99 ）性能指標。典型的 SLA 指標是：讀和寫操作的 P99.9 要 在 300ms 以內成。
由於 Dynamo 是在 通用硬體 上運行的，和高端企業級伺服器相比， I/O 吞吐性能要差 很多 ，因此提供一致的高性能讀寫並不是一項簡單的工作。而且，每次讀/寫操作都要涉 及多台節點，給這項工作帶來了更大的挑戰性，因為 最終的性能受限於最慢的那個副本所 在的節點 。
通用配置下的性能
圖 4 顯示了 30 天內 Dynamo 的讀和寫操作延遲平均值和 P99.9 ：
從圖上可以看出，延遲曲線每天的走勢（diurnal pattern）都類似，這和平台每天的請求 量走勢也是一致的（例如，白天和晚上的請求量明顯不一樣）。另外，寫延遲明顯高於讀延 遲，因為 寫操作永遠需要訪問磁碟 。另外， P99.9 大約為 200ms，比平均值高一 個數量級 。這是因為 P99.9 有很多影響因素，例如請求負載變化、對象大小和 locality patterns。
低延遲配置下的性能
以上性能對很多服務來說都足夠了，但有少數面向用戶的服務，它們對性能有更高的要求。 對於這種情況，Dynamo 提供了 犧牲持久性換性能 的能力。具體來說，每個存儲節點會 在主內存中維護一個對象緩存 （object buffer），寫操作將數據存儲到緩存直接返回， 另有一個獨立的寫線程定期將數據寫入磁碟。讀操作會先檢查緩存中是否有，如果有，就直 接從緩存讀，從而避免了訪問存儲引擎。
這項優化可以 將峰值流量期間的 P99.9 降低到原來的 1/5 ，即使只使用一個很小的 、只能存放 1000 個對象的緩存，見圖 5。
另外，從圖中可以看到，緩存寫（write buffering）可以對百分比延遲進行平滑。顯然， 這種方案中持久性和性能之間做了折中：一台 節點掛掉會導致緩存里還未落盤的數據丟失 。 為了減小這種風險，寫操作進行了優化（refine），由 coordinator 從 N 個副本中選擇 一個進行持久化寫入 （durable write）。因為 coordinator 只等待 W 個寫操作，因此整 體的寫操作不受這次寫盤操作的影響。
以上優化的意思是，每次寫操作到達 coordinator 時，它會將請求轉發給相應個節點， 這些節點都是寫完內存 buffer 就直接返回的；除此之外，coordinator 還會挑一個節點 進行持久寫入，跟其他節點的寫是並行進行的，這樣可以降低其他節點掛掉時內存數據丟 失的風險。由於 coordinator 只等待 W 個結果就返回了，因此雖然這個執行持久寫的節 點（相對）很慢，但 coordinator 並不會依賴它的結果才返回，因此文中說對寫性能來 說是沒有影響的，譯者注。
6.2 均勻負載分布（Uniform Load distribution）
Dynamo 通過一致性哈希將它的 key 空間進行 partition，保證負載分布的均勻性。 只要 key 的訪問不是極度不均衡，均勻的 key 分布就可以幫助我們實現負載的均衡分布。 特別地，即使出現了明顯的 key 訪問不平衡的情況，只要這些 key 足夠多，Dynamo 也能 保證這些 key 在後端節點之間是均衡分散的。 本節介紹 Dynamo 中的負載不平衡問題，幾種解決策略及其對負載分布的影響。
為了研究負載不平衡（load imbalance）以及它和請求負載（request load）的相關性，我 們測量了 24 個小時內每台節點收到的請求量，以 30 分鐘作為一個點。在規定的時間內， 只要節點收到的請求量偏離平均值的程度不超過一個閾值（例如，15%），這台節點就認為 是平衡的（inbalance）；否則，就是不平衡的（out of balance）。
圖 6 展示了不平衡的節點所占的比例（imbalance ratio）：
作為參考，圖中也畫出了這段期間系統的總負載（請求量）。從圖中可以看出，隨著請求量 的上升，不平衡的比例在下降。例如，低負載期間的不平衡比例高達 20%，而高負載期間降 到了 10%。直觀上可以解釋：隨著負載（請求量）的上升，大量的活躍 key 的訪問會均勻 的分發到節點，導致負載平衡分布。而低峰期間（請求量只有峰值的 1/8），只有很少的 活躍 key 訪問，導致負載非常不平衡。
本節接下來介紹 Dynamo 的 partition scheme 是如何隨時間演進的，以及它對負載分布的 影響。
策略 1：每個節點 T 個隨機 token，按 token 值分散
這是生產環境最早部署的策略（在 4.2 節介紹過了）。
在這種策略中，會 給每個節點（從哈希空間）隨機分配 T 個 token 。所有節點的 token 在哈希空間中是有序的（按 token 值）。 兩個相鄰的 token 定義一個範圍 （ key range）。最後一個 token 和第一個 token 收尾相連。
因為 token 是隨機選擇的，因此範圍有大有小。 當有節點加入或離開系統的時，token 集合會變化，導致範圍也會跟著變 。注意， 每個節點用來維護成員信息所需的空間隨著 系統中的節點數線性增長 。
這種策略在使用過程中發現如下幾個問題。
首先，一個 新節點加入到系統後，需要從其他節點「偷」出它要用的 key range 。 這會導致那些需要將一部分 key range 移交給新節點的節點， 掃描它們全部的本地持久存 儲 ，以過濾出所需的數據。在生產環境環境執行這種掃描操作是很棘手的，因為它 會 占用大量磁碟 IO ；為了不影響正常的請求處理，需要把這個任務放到後台。 這要求我們只能將新節點加入集群的任務調到最低優先級。這帶來的後果就是， 節點上線的 速度非常慢 ，尤其是購物高峰季每天處理百萬請求時，上線一台節點需要花費幾乎一整天時 間。
第二，一個節點加入或離開系統時，很多節點負責的 key range 會發生變化，對應的 Merkle tree 需要重新計算 。對於生產環境來說，這也是一項不小的工作。
最後，由於 key range 的隨機性， 無法快速地對整個 key 空間進行快照 （snapshot）。 這使得存檔（備份）工作變得複雜。在這種方案下，我們進行一次快照需要分別從所有節 點獲取 key，非常低效。
這種策略的根本問題出在：數據的 partition 和 placement 方案混在了一起（ intertwined）。例如，在某些場景下希望通過增加節點應對請求量的上漲，但是在這種方 案中， 無法做到添加新節點不影響數據 partition 。
理想情況下，應該使用獨立的數據 partition 和 placement 方案。為此，我們考察了下面的幾種方案。
Strategy 2: 每個節點 T 個隨機 token，平均分散
這種策略將哈希空間分為 Q 個相同大小的 partition/range，每個節點分配 T 個 隨 機 token。 Q 的選擇通常要滿足： Q >> N 和 Q >> S*T （ >> ：遠大於，譯者注）， 其中 S 是系統中節點的數量。
在這種策略中，token 僅用於 哈希空間的值映射到有序節點列表 的過程，並 不影響數 據 partition 。
一個 partition 會放在從該 partition 末尾開始 沿順時針方向得到的前 N 個獨立節點 。
圖 7 展示了 N=3 時這種策略的示意圖。
這種策略的主要優點：
- 將數據的 partition 和 placement 解耦
- 提供了在運行時更改 placement 方案的能力
Strategy 3: 每個節點 Q/S 個 token, 平均分散
和策略 2 類似，策略 3 也將哈希空間等分為 Q 個 partition，而且 placement 從 partition 解耦。不同的是，每個節點會分配 Q/S 個 token，其中 S 是系統中的節點 數量。
當一個節點離開時，它的 token 會隨機地分配給其他節點，因此 Q/S 個 token 的特性 還是能成立。類似地，當一個節點加入系統時，它會從其他節點「偷」一些 token 過來，同 時保證 Q/S 特性仍然成立。
幾種策略的性能對比
對一套 S=30 ， N=3 的 Dynamo 測試了以上三種策略。需要說明的是，公平地比較這三 種策略的性能是很難做到的，因為它們有各自特殊的配置可以調優。例如，策略 1 的負載 分布特性取決於 token 的數量（例如 T ），而策略 3 取決於 partition 的數量（例如 Q ）。
一種比較公平的方式是： 所有的策略都使用相同大小的空間存儲成員信息時，測量它們的 負載分布傾斜度 （skew in load distribution）。例如，策略 1 中每個節點需要為環上 的全部節點維護各自的 token 位置，而策略 3 中每個節點需要維護系統分配給每個節點的 partition 信息。
實驗中我們將通過改變相關的參數（ T 和 Q ）來評估這三種策略。測試每個節點需要維 護的成員信息的大小（size）不同時，幾種策略的 負載均衡效率 。其中負載均衡效率（ load balancing efficiency）的定義是：每個節點平均處理的請求數 / 負載最高的節點處 理的請求數。
結果如圖 8 所示。
如圖所示， 策略 3 取得了最好的負載均衡性能，策略 2 最差 。在某段較短的時期內， 策略 2 充當了將線上的一些 Dynamo 從策略 1 遷移到策略 3 的過渡策略。
和 策略 1 相比，策略 3 性能更好，而且減少了每個節點所需維護的成員信息的大小。
雖然存儲這些成員信息並不會占用太多存儲，但是，節點通過 gossip 協議定期地將成員 信息發送給其他節點（gossip the membership information periodically），因此 保 持這些信息越緊湊越好。
此外，策略 3 部署更加方便，原因包括：
- bootstrap 和恢復更快 ：因為 partition 範圍是固定的 ，因此可以將其存放 到 單獨的文件 ，這樣下次 relocation 的時候可以直接將 整個文件 發送給其他節點 （避免了為了定位特點的數據而進行的 隨機訪問 ）。簡化了 bootstrap 和恢復的過程
- 易於存檔 ：定期對數據集（dataset）進行存檔是 Amazon 存儲服務的硬性要求之一 。在策略 3 中，存檔過程會變得更容易，因為 partition 文件可以單獨存檔。作為對 比，在策略 1 中，token 是隨機選取的，存檔的時候需要從所有節點分別獲取它們存儲 的 key 信息，通常非常低效，速度也很慢。
策略 3 的不足： 變更節點成員時，需要 coordination ，以保持平均分配所需的前提特 性（preserve the properties required of the assignment）。
6.3 版本分叉：什麼時候？有多少？
我們已經提到過，Dynamo 是通過犧牲一些一致性（consistency）來換可用性（ availability）的。要準確地理解不同類型的一致性失敗帶來的影響需要考慮很多因素：故障時 常（outage length）、失敗類型（type of failures）、組件可靠性、負載等等。 詳細地展示這些數據超出了本文範圍。但是，本節可以提供一個很好的總結指標：一份真實 的生產環境裡 應用看到的分叉版本數量 （number of divergent versions seen by the application）。
有兩種情況會出現數據版本的分叉：
- 遇到節點失敗、數據中心故障或網絡分裂等故障場景
- 同一數據對象的大量並發寫操作，不同節點都在 coordinating 寫操作
從使用性（usability）和效率的角度，最好在任何時間都保證分叉的版本數儘量小。
如果衝突的版本無法僅通過向量時鐘做句法調和（syntactically reconcile），那就需要 將它們交給業務邏輯，執行語義調和（semantic reconciliation）。
If the versions cannot be syntactically reconciled based on vector clocks alone, they have to be passed to the business logic for semantic reconciliation.
Semantic reconciliation 會給服務引入額外的負擔，因此應當越少越好。
我們採集了 24 小時內返回到購物車應用的版本數量。結果顯示在這段時間內， 99.94% 的請求看到的都是一個版本（無衝突）； 0.00057% 的請求看到能 2 個， 0.00047% 能看 到 3 個， 0.00009% 的能看到 4 個。這說明版本分叉的機率還是相當小的。
實驗還顯示，導致分叉版本數量增多的並不是故障，而是並發寫數量的增加。並發寫數據上 升通常都是 busy robots（自動化客戶端程序）導致的，極少是人（的應用）導致的。由於 涉及商業機密，在此不再就這一問題進行更深入的討論。
6.4 客戶端驅動或服務端驅動的 Coordination
第 5 節提到，Dynamo 有一個 request coordination 組件，利用狀態機處理收到的請求。
服務端驅動
客戶請求會通過負載均衡器均勻地分發給哈希環上的所有節點。每個節點都可以作為讀請求 的 coordinator，而寫操作的 coordinator 必須由 key 的 preference list 裡面的節點 才能充當。有這種限制是因為，preference list 中的這些節點 被賦予了額外的職責：創 建一個新的版本戳（version stamp），在因果關係上包含被它的寫操作更新的版本 。注 意，如果 Dynamo 的版本化方案使用的是物理時間戳（physical timestamps），那任何節 點都可以 coordinate 寫操作。
客戶端驅動
另一中 coordinate request 的方式是： 將狀態機前移到客戶端 （move the state machine to the client nodes）。在這種方式中，客戶端應用使用庫（library）在本地執 行請求 coordination。每個客戶端定期地隨機選擇一個 Dynamo 節點，下載它的系統成員 狀態（Dynamo membership state）的當前視圖（current view）。有了這個信息，客戶端 就可以知道任何 key 對應的 preference list 由哪些節點組成。
讀請求可以在客戶端節點（client node）coordinate，因此如果請求是被負載均衡器隨機 分給一個 Dynamo 節點，那這種方式可以避免額外的網絡轉發跳數。寫操作或者轉發給 key 對應的 preference list 裡面的一個節點，或者，如果使用的是基於時間戳的版本化方式 ，可以在本地 coordinate。
客戶端驅動的一個重要 優勢 是：不再需要一個負載均衡器才能均勻地分發客戶負載。 在存儲節點上近乎均勻分布的 key，暗含了（implicitly guaranteed）負載的均勻分布。
顯然，這種方式的效率取決於客戶端側的成員信息的新鮮程度（how fresh the membership information）。當前，每個客戶端會每隔 10s 隨機地輪詢（poll）一個 Dynamo 節點， 獲取成員更新（membership updates）。這裡選用 pull 而不是 push 模型是考慮前者在大 量客戶端的情況下可擴展性更好，而且相比於客戶端側，只需在服務端側維護很少的狀態信 息。
然而，在最差的情況下，客戶端的 membership 信息會有 10s 的髒數據。 因此，如果客戶端檢測到它的成員表（membership table）過期了（例如，當一些成員不可 達的時候），它會立即更新它的成員信息。
性能對比
表 2 顯示了客戶端驅動比服務端驅動的 coordination 的性能提升，測量時間為 24 個小時。
從中可以看出，客戶端驅動的方式比服務端方式 P99.9 減少了至少 30ms ，平均值減少 了 3ms~4ms 。
延遲降低是因為客戶端驅動的方式沒有了負載均衡器的開銷，而且減少了可能的將請求轉發 給一個隨機節點的網絡跳數。
另外從表中還可以看出，平均延遲遠遠小於 P99.9 。這是因為 Dynamo 的存儲引擎緩存（ storage engine caches）和寫緩存（write buffer）命中率很高。
另外，由於負載均衡器和網絡會給延遲引入額外的抖動性，因此 P99.9 的性能提升要比 均值更明顯。
6.5 平衡後台和前台任務
每個節點除了執行正常的前台 put / get 操作之外，還需要為副本同步和數據移交（ handoff）（由於 hinting 或添加/刪除節點）執行不同種類的後台任務。
在早期的生產系統中，這些後台任務觸發了資源競爭問題，影響了常規的 get / put 操 作性能。
因此，必須在保證常規的關鍵操作不受明顯影響的情況下，才允許執行後台任務。為此，我 們將後台任務關聯了一種 許可控制機制 （admission control mechanism）。每個後台 任務通過這個控制器 申請資源（例如資料庫）的運行時時間片 （runtime slice），這 些資源是在所有後台任務之間共享的。對前台任務性能的監控會通過 反饋機制 改變後台 任務可以使用的時間片數量。
許可控制器（admission controller）在執行一個前台 put / get 操作的時候，會持續 監控資源訪問的狀況。 監控的指標 包括磁碟操作延遲、鎖競爭和事務超時導致的資料庫 訪問失敗次數，以及請求隊列的等待時間。這些信息用於判斷在給定的時間窗口之內的延遲 （或失敗）性能是否在可接受的範圍內。例如，後台控制器檢查資料庫（過去 60s ）的 P99 讀延遲是否離預設的閾值（例如 50ms ）足夠近。控制器正是根據這些對比信息為 前台操作評估資源的可用性，然後決定給後台任務分配多少時間片，因此利用反饋迴路限制 了後台任務的侵入性（intrusiveness ）。[4] 也研究了類似的後台任務管理問題。
6.6 討論
本節總結我們在開發和維護 Dynamo 的過程中獲得的一些經驗。
很多 Amazon 的內部服務在過去的兩年都開始使用 Dynamo，它給應用提供了非常高等級（ significant levels）的可用性。具體來說，使用 Dynamo 的應用，響應成功率（不包括超 時？）達到了 99.9995% （ applications have received successful responses (without timing out) for 99.9995% of its requests ），並且到目前位置還沒有發 生過丟失數據的情況。
Dynamo 的主要優勢是：給應用提供了配置能力，應用可以根據自己的需求對 (N,R,W) 進 行調優。
和流行的商業數據倉庫不同，Dynamo 將數據一致性和 reconciliation 邏輯開放給了開發 者。剛開始時，有人可能會覺得這樣會使應用邏輯變得更複雜。但從傳統來看（ historically），Amazon 平台就是為高可用設計的，很多 應用在設計的時候就考慮了如 何處理可能出現的各種故障模式（failure modes）和不一致問題 。對於這類應用來說， 適配 Dynamo 相對還是比較簡單的。對於想要使用 Dynamo 的新應用，就需要首先花一些時 間做一些分析，在開發初期，選擇滿足業務需求的合適的衝突解決機制（conflict resolution mechanisms）。
最後，Dynamo 採用了一種 full membership model （完整成員模型），在這種模型中， 每個節點都知道它的對端（peer）節點存儲哪些數據。在實現中，每個節點要主動將完整路 由表 gossip 給系統內的其他節點。這個模型 對幾百台、上千台節點的規模很適用 。但 對於上萬台節點的規模就不適應了，因為維護這麼大一個系統的路由表開銷會大大增加。 但是，可以通過向 Dynamo 引入 hierarchical extensions （層級擴展）來解決這個限制。 O(1) 複雜度的的動態哈希樹系統（DHS）（例如 [14]）解決的就是這種問題。
this problem is actively addressed by O(1) DHT systems(e.g., [14]).
7. 結束語
本文介紹了 Dynamo，一個高可用、高可擴展的數據倉庫（data store），在 Amazon 電商 平台用於存儲許多核心服務的狀態數據。
Dynamo 提供了期望的可用性和性能等級，可以正確地處理伺服器故障、數據中心故障和網 絡分裂。
Dynamo 可以增量擴展，允許服務所有者根據負載高低動態的對 Dynamo 系統進行擴縮容； 允許服務所有者根據他們的性能、持久性和一致性 SLA 需求，通過調優 N``R``W 三個參 數來定製化它們的存儲系統。
過去幾年 Dynamo 在生產環境的實踐表明：一些去中心化技術結合起來，可以提供一個高度 可用的系統。這種在極具挑戰性的應用環境的成功也表明， 最終一致性存儲系統可以作為 高可用應用（highly available applications）的一塊基石 。
The production use of Dynamo for the past year demonstrates that decentralized techniques can be combined to provide a single highly-available system. Its success in one of the most challenging application environments shows that an eventualconsistent storage system can be a building block for highlyavailable applications.
致謝
The authors would like to thank Pat Helland for his contribution to the initial design of Dynamo. We would also like to thank Marvin Theimer and Robert van Renesse for their comments. Finally, we would like to thank our shepherd, Jeff Mogul, for his detailed comments and inputs while preparing the camera ready version that vastly improved the quality of the paper.