摘要

Amazon 是世界上最大的電商之一册烈。

在這里我們所遇到的最大挑戰(zhàn)之一就是超大規(guī)模下的穩(wěn)定性問題（reliability at massive scale）。即使是最微小的故障（the slightest outage）骂倘，也會造成巨大的經(jīng)濟 損失眼滤，而且會降低客戶對我們的信任。Amazon.com 作為一個為全球提供 web 服務(wù)的平臺历涝， 其底層的基礎(chǔ)設(shè)施是由分布在全球的數(shù)據(jù)中心中成千上萬的服務(wù)器和網(wǎng)絡(luò)設(shè)備組成的诅需。在如 此龐大的規(guī)模下漾唉，大大小小的組件故障是不斷在發(fā)生的，而我們應(yīng)對這些故障時所采取 的管理持久狀態(tài)的方式（the way persistent state is managed）堰塌，驅(qū)動著軟件系 統(tǒng)的可靠性（reliability）和可擴展性（scalability）的發(fā)展赵刑。

本文介紹 Dynamo —— 一個高可用鍵值存儲系統(tǒng) —— 的設(shè)計和實現(xiàn)。Amazon 的一些核心 服務(wù)就是基于 Dynamo 提供不間斷服務(wù)的（always-on experience）场刑。為了達到這種等級的 可用性（level of availability）般此，Dynamo 犧牲了幾種特定故障場景下的一致性。另 外牵现，Dynamo 大量使用了對象版本化（object versioning）和應(yīng)用協(xié)助的沖突解決 （application-assisted conflict resolution）機制铐懊，給開發(fā)者提供了一種新穎的接口。

摘要

Amazon 是世界上最大的電商之一瞎疼。

在這里我們所遇到的最大挑戰(zhàn)之一就是超大規(guī)模下的穩(wěn)定性問題（reliability at massive scale）科乎。即使是最微小的故障（the slightest outage），也會造成巨大的經(jīng)濟 損失丑慎，而且會降低客戶對我們的信任喜喂。Amazon.com 作為一個為全球提供 web 服務(wù)的平臺瓤摧， 其底層的基礎(chǔ)設(shè)施是由分布在全球的數(shù)據(jù)中心中成千上萬的服務(wù)器和網(wǎng)絡(luò)設(shè)備組成的竿裂。在如 此龐大的規(guī)模下，大大小小的組件故障是不斷在發(fā)生的照弥，而我們應(yīng)對這些故障時所采取 的管理持久狀態(tài)的方式（the way persistent state is managed）腻异，驅(qū)動著軟件系 統(tǒng)的可靠性（reliability）和可擴展性（scalability）的發(fā)展。

本文介紹 Dynamo —— 一個高可用鍵值存儲系統(tǒng) —— 的設(shè)計和實現(xiàn)这揣。Amazon 的一些核心 服務(wù)就是基于 Dynamo 提供不間斷服務(wù)的（always-on experience）悔常。為了達到這種等級的 可用性（level of availability），Dynamo 犧牲了幾種特定故障場景下的一致性给赞。另 外机打，Dynamo 大量使用了對象版本化（object versioning）和應(yīng)用協(xié)助的沖突解決 （application-assisted conflict resolution）機制，給開發(fā)者提供了一種新穎的接口片迅。

1. 引言

Amazon 是一個全球電商平臺残邀，峰值用戶達到幾千萬。支撐 Amazon 的是分布在全球的數(shù)據(jù) 中心中成千上萬的服務(wù)器柑蛇。Amazon 平臺對性能芥挣、可靠性和效率等指標有著很高的要求 。而且耻台，為了支撐持續(xù)增長（continous growth）空免，平臺需要有高度的可擴展性。可 靠性是我們最重要的需求之一盆耽，因為即使是最微小的故障也會造成巨大的經(jīng)濟損失蹋砚，而且 會降低客戶對我們的信任扼菠。

我們從打造 Amazon 平臺的切身實踐中總結(jié)出的一條經(jīng)驗是：一個系統(tǒng)的可靠性和可擴展 性取決于如何管理它的應(yīng)用狀態(tài)。

The reliability and scalability of a system is dependent on how its application state is managed.

Amazon 使用的是高度去中心化的坝咐、松耦合的娇豫、面向服務(wù)的架構(gòu)，由幾百個服務(wù)組成畅厢。這樣 的環(huán)境對永遠可用（always available）的存儲技術(shù)有著強烈的需求冯痢。例如，即使磁 盤掛掉框杜、路由抖動浦楣、甚至數(shù)據(jù)中心被颶風摧毀，用戶應(yīng)該仍然能向他們的購物車添加和查看 商品咪辱。要實現(xiàn)這樣的目標振劳，管理購物車的系統(tǒng)就必須永遠能讀寫它的 數(shù)據(jù)倉庫，而且 數(shù)據(jù)倉庫還要跨多個數(shù)據(jù)中心可用油狂。

對于我們這種由幾百萬臺設(shè)備組成的基礎(chǔ)設(shè)施历恐，故障是家常便飯；在任何時刻都會有比例小 但數(shù)量不少（small but significant number）的服務(wù)器和網(wǎng)絡(luò)設(shè)備發(fā)生故障专筷。因此弱贼， Amazon 的軟件系統(tǒng)要將故障視為正常的、可預期的行為（treat failure handling as the normal case）磷蛹，不應(yīng)因設(shè)備故障而影響可用性和性能吮旅。

為了滿足可靠性和可擴展性的需求，Amazon 開發(fā)了一些存儲技術(shù)味咳，S3 （Simple Storage Service）可能是最廣為人知的一種庇勃。本文介紹 Amazon 的另一個存儲產(chǎn)品 Dynamo —— 一個 高可用鍵值存儲數(shù)據(jù)倉庫（data store）—— 的設(shè)計和實現(xiàn)。

Dynamo 用于管理對可靠性要求非常高的服務(wù)的狀態(tài)槽驶，這些服務(wù)還要求對可靠性责嚷、一致 性、成本-效率（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 平臺有很多類型的應(yīng)用罕拂，不同的類型對存儲的需求差異很大。例如堡纬，其中一類應(yīng)用 希望能 數(shù)據(jù)倉庫的配置足夠靈活聂受，以便在成本最經(jīng)濟的方式下，由開發(fā)者來決定如何 在可用性和性能之間取得折中烤镐。

Amazon 的一些服務(wù)只需以主鍵（primary key）的方式訪問數(shù)據(jù)倉庫蛋济。對于很多服 務(wù)，例如暢銷排行榜炮叶、購物車碗旅、客戶喜好偏向渡处、session 管理、銷售排名祟辟、商品目錄等等医瘫， 常見的關(guān)系型數(shù)據(jù)庫會非常低效，而且限制了規(guī)模的擴展性和可用性旧困。Dynamo 提供了只使 用主鍵（primary key only）的訪問接口來滿足這類應(yīng)用的需求醇份。

Dynamo 基于一些眾所周知的（****well known****）技術(shù)實現(xiàn)了可擴展性和高可用性：

• 數(shù)據(jù)通過一致性哈希分散和復制（partitioned and replicated）[10]
• 通過對象版本化（object versioning）實現(xiàn)一致性 [12]
• 副本之間的一致性由一種類似仲裁的技術(shù)（quorum-like technique）和一個去中 心化的副本同步協(xié)議（replica synchroni protocol）保證
• gossip-based 分布式故障檢測和成員檢測（membership）協(xié)議

Dynamo 是一個只需最少人工管理的、完全去中心化的系統(tǒng)吼具。

Dynamo is a completely decentralized system with minimal need for manual administration.

向 Dynamo 添加或移除存儲節(jié)點不需要人工 partition（調(diào)整哈希節(jié)點）或 redistribution（在節(jié)點之間重新平衡數(shù)據(jù)分布）僚纷。

Dynamo 在過去的幾年已經(jīng)成為 Amazon 很多核心服務(wù)的底層存儲技術(shù)。在節(jié)假日購物高峰 拗盒，它能實現(xiàn)不停服（平滑）擴容以支持極高的峰值負載怖竭。例如購物車服務(wù)的幾千萬請求會 產(chǎn)生單日 300 萬次的付款動作，管理 session 狀態(tài)的服務(wù)能處理幾千萬的并發(fā)活躍用戶等 等陡蝇。

本文對該領(lǐng)域的****主要貢獻：

• 評估了如何通過組合不同技術(shù)實現(xiàn)一個高度可用的（highly-available）系統(tǒng)
• 證明了最終一致性存儲系統(tǒng)可以用于生產(chǎn)環(huán)境痊臭，滿足應(yīng)用的高要求
• 展示了若干優(yōu)化技術(shù)，以滿足生產(chǎn)環(huán)境的非常嚴格的性能要求

本文章節(jié)結(jié)構(gòu)介紹（略登夫，見下面全文）广匙。

2. 背景

Amazon 的電商平臺由幾百個服務(wù)組成，它們協(xié)同工作悼嫉，提供的服務(wù)包羅萬象艇潭，從推薦系統(tǒng) 到訂單處理到欺詐檢測等等。每個服務(wù)對外提供定義良好的 API戏蔑，被其他服務(wù)通過網(wǎng)絡(luò)的方 式訪問。這些服務(wù)運行在分布在全球的數(shù)據(jù)中心中鲁纠，成千上萬的服務(wù)器組成的基礎(chǔ)設(shè)施之上 总棵。有些服務(wù)是無狀態(tài)的（例如，聚合其他服務(wù)的響應(yīng)的服務(wù)）改含，有些是有狀態(tài)的（例如情龄，基 于存儲在數(shù)據(jù)倉庫里的狀態(tài)，執(zhí)行業(yè)務(wù)邏輯并產(chǎn)生響應(yīng)的服務(wù)）捍壤。

傳統(tǒng)上骤视，生產(chǎn)系統(tǒng)使用關(guān)系型數(shù)據(jù)庫來存儲狀態(tài)。但對很多持久狀態(tài)的存儲需求來說鹃觉， 關(guān)系型數(shù)據(jù)庫并不是一種理想的方式专酗。這一類型中的大多數(shù)服務(wù)只用主鍵去檢索，并不需要 RDBMS 提供的復雜查詢和管理功能盗扇。這些額外的功能需要昂貴的硬件和專門的技能祷肯，而實際 上服務(wù)根本用不到沉填，最終的結(jié)果就是使用關(guān)系型數(shù)據(jù)庫非常不經(jīng)濟。另外佑笋，這類數(shù)據(jù)庫的復 制功能很受限翼闹，而且通常是靠犧牲可用性來換一致性。雖然近些年有了一些改進蒋纬，但總 體來說水平擴展（scale-out）以及使用智能（smart）partitioning 來做負載均衡還是很不 方便猎荠。

本文介紹 Dynamo 是如何解決以上需求的。Dynamo 有易用的 key/value 接口蜀备，高度可用 法牲，有定義清晰的一致性窗口（clearly defined consistency window），資源使用效率很高 琼掠，并且有易用的水平擴展方案以解決請求量或數(shù)據(jù)增長帶來的挑戰(zhàn)拒垃。每個使用 Dynamo 的 服務(wù)，使用的都是它們獨立的一套 Dynamo 系統(tǒng)瓷蛙。

Each service that uses Dynamo runs its own Dynamo instances.

2.1 系統(tǒng)假設(shè)與需求

Dynamo 對使用它的服務(wù)有如下幾點假設(shè)悼瓮。

查詢模型（Query Model）

通過唯一的 key 對數(shù)據(jù)進行讀寫。狀態(tài)以二進制對象（binary objects艰猬，e.g. blobs）形式存儲横堡，以唯一的 key 索引。

任何操作都不會跨多個 data items（數(shù)據(jù)單元）冠桃，沒有關(guān)系型 schema 需求命贴。

Dynamo 面向的應(yīng)用存儲的都是相對較小的文件（一般小于 1 MB）。

ACID 特性

ACID（Atomicity, Consistency, Isolation, Durability）是一組保證數(shù)據(jù)庫事務(wù)可 靠執(zhí)行的特性食听。在數(shù)據(jù)庫領(lǐng)域胸蛛，對數(shù)據(jù)的單次邏輯操作（single logical operation） 稱為一次事務(wù)（transaction）。 我們在 Amazon 的實踐表明樱报，讓數(shù)據(jù)倉庫支持 ACID 會使得它的可用性（availability） 非常差葬项，工業(yè)界和學術(shù)界也已經(jīng)就這一點達成了廣泛共識 [5]。

Dynamo 的目標應(yīng)用具有這樣的特點：如果能給可用性（ACID 里面的 A）帶來很大提升 迹蛤，那犧牲一些一致性（C）也是允許的民珍。

Dynamo 不提供任何隔離保證，并且只允許帶單個 key 的更新操作（permit only single key updates）盗飒。

效率（Efficiency）

系統(tǒng)需要運行在通用硬件（commodity hardware）之上嚷量。Amazon 的服務(wù)對延遲有著嚴格的 要求，通常用百分位值（percentile）P99.9 衡量逆趣。

考慮到對狀態(tài)數(shù)據(jù)的訪問是服務(wù)的核心操作之一蝶溶，我們的存儲系統(tǒng)必須滿足那些嚴格的 SLA （見 Section 2.2）。另外汗贫，服務(wù)要有配置 Dynamo 的能力身坐，以便能滿足服務(wù)的延遲和吞吐 需求秸脱。最終，就是在性能部蛇、成本效率摊唇、可用性和持久性之間取得折中。

其他方面

Dynamo 定位是 Amazon 內(nèi)部使用涯鲁，因此我們假設(shè)環(huán)境是安全的巷查，不需要考慮認證和鑒權(quán) 等安全方面的問題。

另外抹腿，由于設(shè)計中每個服務(wù)都使用各自的一套 Dynamo岛请，因此 Dynamo 的初始設(shè)計規(guī)模是 幾百個存儲節(jié)點。后面會討論可擴展性限制的問題警绩，以及可能的解決方式崇败。

2.2 SLA (Service Level Agreements)

要保證一個應(yīng)用完成請求所花的時間有一個上限（bounded time），它所依賴的那些服務(wù)就要有一個更低的上限肩祥。對于給定的系統(tǒng)特性后室，其中最主要的是客戶端期望的請求 率分布（request rate distribution），客戶端和服務(wù)端會定義一個 SLA****（服務(wù)級別 協(xié)議）來作為契約混狠。

舉個簡單例子：某個服務(wù)向客戶端保證岸霹，在 500 QPS 的負載下，它處理 99.9% 的請求 所花的時間都在能 300ms 以內(nèi)。

在 Amazon 的去中心化的、面向服務(wù)的基礎(chǔ)設(shè)施中鸿竖，SLA 扮演著重要角色。例如模捂，對購物 頁面的一次請求，在典型情況下會使渲染引擎向多達 150 個服務(wù)發(fā)送子請求，而這些子服 務(wù)又都有自己的依賴，最終形成一張多層的（more than one level）調(diào)用圖（call graph ）皇筛。為了保證渲染引擎能在一個上限時間內(nèi)返回一個頁面，調(diào)用鏈中的所有服務(wù)就都必須遵 循各自的性能契約（contract）坠七。

image

圖 1 Amazon 平臺的面向服務(wù)架構(gòu)

圖 1 是一張簡化之后的 Amazon 平臺架構(gòu)圖∑毂剩可以看到彪置，動態(tài) web 內(nèi)容由頁面渲染組件 提供，而它是通過調(diào)用其他的一些服務(wù)來完成這項工作的蝇恶。

每個服務(wù)可以選擇不同類型的數(shù)據(jù)倉庫（data store）來管理（存儲）它們的狀態(tài)數(shù)據(jù)拳魁， 這些數(shù)據(jù)倉庫只能在各自的服務(wù)邊界（service boundaries）內(nèi)訪問。一些服務(wù)會通過聚 合其他服務(wù)的數(shù)據(jù)來組合產(chǎn)生一個響應(yīng)（composite response）撮弧。典型情況下潘懊，聚合服務(wù)（ aggregator service）是無狀態(tài)的姚糊，雖然它們大量使用緩存技術(shù)。

對于面向性能的 SLA（performance oriented SLA）授舟，業(yè)內(nèi)一般習慣使用平均值救恨、中位數(shù) 和方差來描述。但在 Amazon 我們發(fā)現(xiàn)释树，要打造一個讓所有用戶——而不是大部分用戶——都 有良好體驗的系統(tǒng)肠槽，以上 SLA 并不合適。例如奢啥，如果使用了個性化推薦技術(shù)秸仙，那用戶的 訪問歷史越多，他的請求被處理的時間就越長桩盲，最終落到了性能分布的長尾區(qū)寂纪。基于平均 值或中位數(shù)的 SLA 并不能反映這種情況赌结。為了解決這個問題捞蛋，我們使用了 P99.9 分布。****99.9% 這個精度是經(jīng)過大量實驗分析姑曙，權(quán)衡了成本和性能之后得到的襟交。 我們在生產(chǎn)環(huán)境的實驗顯示，這比基于均值或中位數(shù)的 SLA 有更好的用戶體驗伤靠。

本文多處都將引用 P99.9 分布捣域，這也顯示了 Amazon 的工程師對提高用戶體驗所做的持續(xù) 不斷的努力。一些基于均值的論文宴合，我們會在它真正有意義的場景才拿出來作為比較焕梅，但我 們自己的工程和優(yōu)化都不是以均值 SLA 為核心的。某些技術(shù)卦洽，例如 write coordinator（寫操作協(xié)調(diào)者）贞言，是完全面向 P99.9 來控制性能的。

存儲系統(tǒng)在構(gòu)建一個服務(wù)的 SLA 中經(jīng)常扮演著重要角色阀蒂，尤其是業(yè)務(wù)邏輯相對輕量的 場景该窗，Amazon 的服務(wù)即屬于這一類。因此蚤霞，狀態(tài)管理 就成了服務(wù)的 SLA 的主要 部分酗失。

Dynamo 的設(shè)計目標之一就是：允許服務(wù)自己控制自己的系統(tǒng)特性——例如持久性和一 致性——讓服務(wù)自己決定如何在功能、性能和成本效率之間取得折中昧绣。

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 設(shè)計考慮

商業(yè)系統(tǒng)中數(shù)據(jù)復制算法一般都是同步的规肴，以提供一個強一致性的數(shù)據(jù)訪問接口。 為了達到這種級別的一致性，這些算法被迫犧牲了某些故障場景下的數(shù)據(jù)可用性拖刃。例如删壮， 如果數(shù)據(jù)有沖突，它們會禁止訪問這個數(shù)據(jù)兑牡，直到數(shù)據(jù)的不一致完全得到了解決央碟。在早期，這 種復制式數(shù)據(jù)庫（replicated database）是可以工作的发绢。

但眾所周知硬耍，分布式系統(tǒng)是無法同時滿足強一致性、高可用性和正確處理網(wǎng)絡(luò)故障（CAP ）這幾個條件的 [2, 11]边酒。因此经柴，系統(tǒng)和應(yīng)用都需要知道，在什么場景下選擇滿足什么 特性墩朦。

對于服務(wù)器和網(wǎng)絡(luò)故障較高的場景坯认，可以通過樂觀復制（optimistic replication ）技術(shù)增強可用性，在后臺將數(shù)據(jù)變動同步到其他節(jié)點氓涣，并發(fā)更新和失聯(lián)也是可以容忍 的牛哺。這種方式的問題是會導致數(shù)據(jù)沖突，需要檢測并解決沖突劳吠。而解決數(shù)據(jù)沖突又會帶 來兩個額外問題：

• 何時解決引润？
• 誰來解決？

Dynamo 設(shè)計為****最終一致數(shù)據(jù)倉庫（eventually consistent data store）痒玩，即淳附，最終 所有的更新會應(yīng)用到所有的副本。

何時解決沖突蠢古？

設(shè)計時的一個重要考慮是：何時解決更新沖突奴曙，例如，是讀的時候還是寫的時候草讶。

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.

一些傳統(tǒng)的數(shù)據(jù)倉庫是在寫的時候解決沖突洽糟，這樣可以保證讀的復雜度很低 [7]。 在這種系統(tǒng)中堕战，任何時候如果數(shù)據(jù)倉庫不能訪問所有（或者大多數(shù)）副本坤溃，寫就會被拒絕。

Dynamo 的設(shè)計與此相反嘱丢，它的目標是提供一個“永遠可寫”（always writable）的數(shù)據(jù) 倉庫（例如浇雹，一個對寫操作高度可用的數(shù)據(jù)倉庫）。對很多 Amazon 服務(wù)來說屿讽，拒絕寫 入會造成很差的用戶體驗。比如即使發(fā)生服務(wù)器或網(wǎng)絡(luò)故障，也應(yīng)該允許用戶往購物車添 加或刪除商品伐谈。這個需求使我們將解決沖突的復雜度放到了讀操作烂完，以保證寫永遠不會 被拒絕。

誰來解決沖突诵棵？

下一個需要考慮的問題是：誰來解決沖突抠蚣。數(shù)據(jù)倉庫和應(yīng)用都可以做這件事情。

如果由數(shù)據(jù)倉庫來做履澳，那選擇會相當受限嘶窄。在這種情況下，數(shù)據(jù)倉庫只能使用一些 非常簡單的策略距贷，例如“最后一次寫有效”（last write wins） [22]柄冲，來解決更新沖突。

另一方面忠蝗，由于應(yīng)用理解數(shù)據(jù)描述的是什么（application is aware of the data schema）现横，它可以自主選擇對用戶體驗最好的沖突解決算法。例如阁最，購物車應(yīng)用可以選擇“ 合并”沖突的版本戒祠，返回一個合并后的（unified）購物車。盡管這樣可以帶來很大的靈活性 速种，但一些應(yīng)用開發(fā)者并不想自己實現(xiàn)一套沖突解決機制姜盈，因此在這種情況下，解決沖突的問 題就下放給了數(shù)據(jù)倉庫配阵，由后者來選擇一些簡單的策略馏颂，例如 “l(fā)ast write wins”。

其他設(shè)計原則

• 增量擴展性（Incremental scalability）：應(yīng)當支持逐機器（節(jié)點）擴容闸餐，而 且對系統(tǒng)及運維人員帶來的影響盡量小
• 對稱性（Symmetry）：每個節(jié)點的職責應(yīng)該是相同的饱亮，不應(yīng)當出現(xiàn)某些節(jié)點承擔 特殊職責或特殊角色的情況。以我們的實踐經(jīng)驗舍沙，對稱性簡化了系統(tǒng)的交付和運維
• 去中心化（Decentralization）：“****去中心化****”****是****“****對稱性****”****的進一步擴展近上，系統(tǒng)應(yīng) 該是去中心化的、點對點的拂铡，而不應(yīng)該是集中式控制的壹无。在過去，集中式控制導致了很多 服務(wù)故障（outage）感帅，我們應(yīng)當極力避免它斗锭。去中心化會使得系統(tǒng)更簡單、更具擴展性和 可用性
• 異構(gòu)性（Heterogeneity）：系統(tǒng)要能夠利用到基礎(chǔ)設(shè)施的異構(gòu)性失球。例如岖是，負載的 分布要和存儲節(jié)點的能力成比例帮毁。對于逐步加入能力更強的新節(jié)點，而不是一次升級所 有節(jié)點來說豺撑，這種異構(gòu)支持能力是不可或缺的

3. 相關(guān)工作

3.1 點對點系統(tǒng)（Peer to Peer Systems）

一些點對點（peer-to-peer, P2P）系統(tǒng)關(guān)注了數(shù)據(jù)存儲和分散（data storage and distribution）的問題烈疚。

P2P 系統(tǒng)

第一代 P2P 系統(tǒng)，例如 Freenet 和 Gnutella聪轿，在文件共享系統(tǒng)（file sharing system） 領(lǐng)域使用廣泛爷肝。它們都是非受信（untrusted）P2P 網(wǎng)絡(luò)的代表，節(jié)點之間的 overlay （網(wǎng)絡(luò)術(shù)語陆错，和 underlay 對應(yīng)灯抛，請參考 Wikipedia 或其他資料，譯者注）鏈路都是隨機 （隨意）建立的（established arbitrarily）音瓷。在這種網(wǎng)絡(luò)中对嚼，一次查詢請求通常是泛 洪（flood）到整張網(wǎng)絡(luò)，找到盡量多的共享這個數(shù)據(jù)的節(jié)點外莲。

結(jié)構(gòu)化 P2P 系統(tǒng)

P2P 網(wǎng)絡(luò)到下一代猪半，就是有名的結(jié)構(gòu)化 P2P 網(wǎng)絡(luò)（structured P2P network）。這種 網(wǎng)絡(luò)使用了全局一致性協(xié)議（globally consistent protocol）偷线，保證任何一個節(jié)點可以 高效地將查詢請求路由到存儲這個數(shù)據(jù)的節(jié)點磨确。

Pastry [16] 和 Chord [20] 這樣的系統(tǒng)利用路由機制可以保證查詢在若干（有上限） 跳（a bounded number of hops）之內(nèi)收到應(yīng)答。

為了減少多跳（multi-hop）路由帶來的額外延遲声邦，一些 P2P 系統(tǒng)（例如 [14]）使用了 O(1)****路由機制乏奥，在這種機制中，每個節(jié)點維護了足夠多的路由信息亥曹，因此它可以 將（訪問數(shù)據(jù)的）請求在常量跳數(shù)（constant number of hops）內(nèi)路由到合適的對端節(jié)點 邓了。

包括 Oceanstore [9] 和 PAST [17] 在內(nèi)的很多存儲系統(tǒng)都是構(gòu)建在這種路由（routing） overlay 之上的。Oceanstore 提供全球分布的媳瞪、事務(wù)型的骗炉、持久的存儲服務(wù)，支持分布在 很大地理范圍內(nèi)的副本的串行化更新（serialized updates on widely replicated data） 蛇受。為了支持并發(fā)更新句葵，同時避免廣域鎖（wide-are locking）內(nèi)在的一些問題，它使用了一 種基于沖突解決（conflict resolution）的更新模型兢仰。conflict resolution 在 [21] 中 提出乍丈，用于減少事務(wù)異常中止（transaction abort）的數(shù)量。Oceanstore 處理沖突的方式是 ：對并發(fā)更新進行排序（order）把将，將排好序的若干個更新作為原子操作應(yīng)用到所有副本轻专。 Oceanstore 是為在不受信的基礎(chǔ)設(shè)施上做數(shù)據(jù)復制的場景設(shè)計的。

作為對比察蹲，PAST 是在 Pastry 之上提供了一個簡單的抽象層请垛，以此來提供持久和不可變對 象（persistent and immutable objects）催训。它假設(shè)應(yīng)用可以在它之上構(gòu)建自己需要的 存儲語義（storage semantics）（例如可變文件）。

3.2 分布式文件系統(tǒng)與數(shù)據(jù)庫

文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)領(lǐng)域已經(jīng)對通過分散數(shù)據(jù)（distributing data）來提高性能叼屠、可 用性和持久性進行了廣泛研究瞳腌。和 P2P 存儲系統(tǒng)只支持扁平命名空間（flat namespace）相比，典型的分布式文件系統(tǒng)都支持層級化的命名空間（hierarchical namespace）镜雨。

• Ficus [5] 和 Coda [19] 這樣的系統(tǒng)通過文件復制來提高可用性，代價是犧牲一致性儿捧。 解決更新沖突一般都有各自特殊的解決方式
• Farsite [1] 是一不使用中心式服務(wù)器（例如 NFS）的分布式文件系統(tǒng)荚坞，它通過復制實現(xiàn) 高可用和高擴展
• Google File System [6] 是另一個分布式文件系統(tǒng)，用于存儲 Google 內(nèi)部應(yīng)用的 狀態(tài)數(shù)據(jù)菲盾。GFS 的設(shè)計很簡單颓影，一個主節(jié)點（master）管理所有元數(shù)據(jù)，數(shù)據(jù)進行分片（ chunk）懒鉴，存儲到不同數(shù)據(jù)節(jié)點（chunkservers）诡挂。
• Bayou 是一個分布式關(guān)系型數(shù)據(jù)庫系統(tǒng)，允許在失聯(lián)情況下進行操作（disconnected operation）临谱，提供最終一致性

在這些系統(tǒng)中璃俗，Bayou、Coda 和 Ficus 都支持失聯(lián)情況下進行操作悉默，因此對網(wǎng)絡(luò)分裂和宕 機都有很強的彈性城豁，它們的不同之處在于如何解決沖突。例如抄课，Coda 和 Ficus 在系統(tǒng)層面 解決（system level conflict resolution）唱星，而 Bayou 是在應(yīng)用層面（application level）。相同的是跟磨，它們都提供最終一致性间聊。與這些系統(tǒng)類似，Dynamo 允許在網(wǎng)絡(luò)發(fā)生 分裂的情況下繼續(xù)執(zhí)行讀寫操作抵拘，然后通過不同的沖突解決機制來處理更新沖突哎榴。

分布式塊存儲系統(tǒng)（distributed block storage system），例如 FAB [18]仑濒，將一個大塊 分割成很多小塊并以很高的可用性的方式存儲叹话。和這類系統(tǒng)相比，我們的場景更適合使用鍵 值存儲墩瞳，原因包括：

• 系統(tǒng)定位是存儲相對較小的文件（ size < 1 MB）
• 鍵值存儲（key-value store）更容易在應(yīng)用級別針對單個應(yīng)用（per-application）進行配置

Antiquity 是一個廣域分布式文件系統(tǒng)驼壶，設(shè)計用于處理多個服務(wù)器掛掉的情況 [23]。它使 用安全日志（secure log）保證數(shù)據(jù)完整性喉酌，在不同服務(wù)器之間復制 secure log 來保 證持久性（durability）热凹，使用拜占庭容錯協(xié)議（Byzantine fault tolerance protocols）保證數(shù)據(jù)一致性泵喘。與此不同，Dynamo 并不將數(shù)據(jù)完整性和安全性作為主要關(guān) 注點般妙，因為我們面向的是受信環(huán)境纪铺。

Bigtable 是一個管理結(jié)構(gòu)化數(shù)據(jù)（structured data）的分布式文件系統(tǒng)，它維護了一 張稀疏的多維有序映射表（sparse, multi-dimensional sorted map）碟渺，允許應(yīng)用通過多重 屬性訪問它們的數(shù)據(jù)（access their data using multiple attributes） [2]鲜锚。與此不同 ，Dynamo 面向的應(yīng)用都是以 key/value 方式訪問數(shù)據(jù)的苫拍，我們的主要關(guān)注點是高可用 芜繁，即使在發(fā)生網(wǎng)絡(luò)分裂或服務(wù)器宕機的情況下，寫請求也是不會被拒絕的绒极。

傳統(tǒng)的復制型關(guān)系數(shù)據(jù)庫系統(tǒng)（replicated relational database systems）都將關(guān)注點放 在保證副本的強一致性骏令。雖然強一致性可以給應(yīng)用的寫操作提供方便的編程模型， 但導致系統(tǒng)的擴展性和可用性非常受限 [7]垄提，無法處理網(wǎng)絡(luò)分裂的情況榔袋。

3.3 討論

Dynamo 面臨的需求使得它與前面提到的集中式存儲系統(tǒng)都不相同。

首先铡俐，Dynamo 針對的主要是需要****“****永遠可寫的****”****（****always writable****）數(shù)據(jù)倉庫的應(yīng)用凰兑， 即使發(fā)生故障或并發(fā)更新，寫也不應(yīng)該被拒絕高蜂。對于 Amazon 的很多應(yīng)用來說聪黎，這一點是非 常關(guān)鍵的。

第二备恤，Dynamo 構(gòu)建在受信的稿饰、單一管理域的基礎(chǔ)設(shè)施之上。

第三露泊，使用 Dynamo 的應(yīng)用沒有層級命名空間（****hierarchical namespace****）的需求（這是很 多文件系統(tǒng)的標配）喉镰，也沒有復雜的關(guān)系型 schema 的需求（很多傳統(tǒng)數(shù)據(jù)庫都支持）。

第四惭笑，Dynamo 是為延遲敏感型應(yīng)用（latency sensitive application）設(shè)計的侣姆，至少 99.9% 的讀寫操作都要在幾百毫秒內(nèi)完成。為了到達如此嚴格的響應(yīng)要求沉噩，在多節(jié)點 之間對請求進行路由的方式（被很多分布式哈希表系統(tǒng)使用捺宗，例如 Chord 和 Pastry ）就無法使用了。因為多跳路由會增加響應(yīng)時間的抖動性川蒙，因此會增加長尾部分的延遲蚜厉。 Dynamo 可以被描述為：一個零跳（****zero hop****）分布式哈希表（****DHT****）墓阀，每個節(jié)點在本地 維護了足夠多的路由信息凰锡，能夠?qū)⒄埱笾苯勇酚傻胶线m節(jié)點吏口。

4. 系統(tǒng)架構(gòu)

生產(chǎn)級別的存儲系統(tǒng)的架構(gòu)是很復雜的蝠咆。除了最終存儲數(shù)據(jù)的組件之外，系統(tǒng)還要針對下列 方面制定可擴展和健壯的解決方案：負載均衡贰健、成員管理（membership）胞四、故障檢測、故障 恢復伶椿、副本同步辜伟、過載處理（overload handling）、狀態(tài)轉(zhuǎn)移悬垃、并發(fā)和任務(wù)調(diào)度游昼、請求 marshalling、請求路由（routing）尝蠕、系統(tǒng)監(jiān)控和告警，以及配置管理载庭。

詳細描述以上提到的每一方面顯然是不可能的看彼，因此本文將關(guān)注下面幾項 Dynamo 用到的分 布式系統(tǒng)核心技術(shù)：

• partitioning（分區(qū)，經(jīng)哈希決定將數(shù)據(jù)存儲到哪個/些節(jié)點）
• 復制（replication）
• 版本化（versioning）
• 成員管理（membership）
• 故障處理（failure handling）
• 規(guī)模擴展（scaling）

表 1 總結(jié)了 Dynamo 使用的這些技術(shù)及每項技術(shù)的好處囚聚。

表 1 Dynamo 用到的技術(shù)及其好處

image

Partition

• 技術(shù)：一致性哈希
• 好處：增量可擴展性

寫高可用

• 技術(shù)：讀時協(xié)調(diào)（解決沖突）的向量時鐘（vector clocks with reconciliation during reads）
• 好處：version size（靖榕？）和更新頻率（update rates）解耦

短時故障處理

• 技術(shù)：寬松的選舉和 hinted handoff（移交給其他節(jié)點處理，附帶提示信息）
• 好處：部分副本不可用時顽铸，仍然可以提供高可用性和持久性

持久（permanent）故障恢復

• 技術(shù)：基于 Merkle tree 的逆熵（anti-entropy）
• 好處：后臺同步版本不一致的副本

成員管理和故障檢測

• 技術(shù)：基于 Gossip 的成員管理協(xié)議和故障檢測
• 好處：保持了架構(gòu)的對稱性茁计，無需一個中心組件（centralized registry）來存儲成員和節(jié)點狀態(tài)等信息

4.1 系統(tǒng)接口

Dynamo 存儲鍵值對象的接口非常簡單，它提供兩個操作：

• get()
• put()

get(key) 會定位到存儲系統(tǒng)中 key 對應(yīng)的所有對象副本谓松，返回對象 ——可能是單個對 象星压，也可能是一個對象列表（有沖突情況下，包括了所有版本）—— 以及一個 context****（ 上下文）鬼譬。

put(key) 確定對象應(yīng)該存放的位置娜膘，然后寫到相應(yīng)的磁盤。

context 包含了系統(tǒng)中對象的元數(shù)據(jù)优质，例如對象的版本竣贪，對調(diào)用方是不透明的（ opaque）。上下文信息是和對象存儲在一起的巩螃，這樣系統(tǒng)很容易驗證 put 請求的 context 是否合法演怎。

Dynamo 將調(diào)用方提供的 key 和對象都視為不透明的字節(jié)序列（opaque array of bytes） 。它對 key 應(yīng)用 MD5 哈希得到一個 128bit 的 ID避乏，并根據(jù)這個 ID 計算應(yīng)該存儲 到哪些節(jié)點爷耀。

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 數(shù)據(jù)分散（Partitioning）算法

Dynamo 的核心需求之一是：系統(tǒng)必須支持增量擴展（scale incrementally）。 這就要求有一種機制能夠?qū)?shù)據(jù)分散到系統(tǒng)中的不同的節(jié)點（例如淑际，以一臺機器作為一個 節(jié)點的維度）上畏纲。

Dynamo 的分散方案基于一致性哈希 [10]扇住。在一致性哈希中，哈希函數(shù)的輸出是一個 固定的范圍盗胀，通常作為一個循環(huán)空間艘蹋，或稱環(huán)（ring）。每個節(jié)點都會隨 機分配一個在這個循環(huán)空間內(nèi)的值票灰，這個值代表了節(jié)點在這個環(huán)上的位置女阀。

用如下方式找到一個數(shù)據(jù)項（data item）對應(yīng)的存儲節(jié)點：

1. 首先對它的 key 做哈希得到一個哈希值
2. 然后，在環(huán)上沿著順時針方向找到第一個所帶的值比這個哈希值更大的節(jié)點（前面 提到每個節(jié)點都會被分配一個值）

即屑迂，每個節(jié)點要負責環(huán)上從它自己到它的下一個節(jié)點之間的區(qū)域浸策。一致性哈希的主要好處是 ：添加或刪除節(jié)點只會影響相鄰的節(jié)點，其他節(jié)點不受影響惹盼。

The principle advantage of consistent hashing is that departure or arrival of a node only affects its immediate neighbors and other nodes remain unaffected.

但是庸汗，初級的一致性哈希算法在這里是有一些問題的。 首先手报，給每個節(jié)點隨機分配一個位置會導致數(shù)據(jù)和負載的非均勻分布蚯舱。 其次，初級的一致性哈希算法沒有考慮到節(jié)點的異構(gòu)因素掩蛤，導致性能不理想枉昏。

為了解決這些問題，Dynamo 使用了一致性哈希的一個變種（和 [10, 20] 的類似）：每個 節(jié)點并不是映射到環(huán)上的一個點揍鸟，而是多個點兄裂。

Intead of mapping a node to a single point in the circle, each node gets assigned to multiple points in the ring.

為了實現(xiàn)這種設(shè)計，Dynamo 使用了虛擬節(jié)點（virtual node）的概念阳藻。一個虛擬節(jié)點 看上去和一個普通節(jié)點一樣晰奖，但實際上可能管理不止一臺虛擬節(jié)點。具體來說稚配， 當一個新節(jié)點添加到系統(tǒng)后畅涂，它會在環(huán)上被分配多個位置（對應(yīng)多個 token）。 我們會在 Section 6 介紹 Dynamo 分散策略（算法）的深入調(diào)優(yōu) 道川。

虛擬節(jié)點可以代來如下好處：

1. 當一個節(jié)點不可用時（故障或例行維護）午衰，這個節(jié)點的負載會均勻分散到其他可用節(jié)點上
2. 當一個節(jié)點重新可用時，或新加入一個節(jié)點時冒萄，這個節(jié)點會獲得與其他節(jié)點大致相同的 負載
3. 一個節(jié)點負責的虛擬節(jié)點的數(shù)量可用根據(jù)節(jié)點容量來決定臊岸，這樣可用充分利用物理基礎(chǔ) 設(shè)施中的異構(gòu)性信息

4.3 數(shù)據(jù)復制（Replication）

為了實現(xiàn)高可用性和持久性，Dynamo 將數(shù)據(jù)復制到多臺機器上尊流。每個數(shù)據(jù)會被復制到 N 臺 機器帅戒，這里的 N 是每套 Dynamo 可以自己配置的。

上節(jié)介紹到，每個 key k****逻住，會被分配一個 coordinator****（協(xié)調(diào)者）節(jié)點钟哥。 coordinator 負責落到它管理的范圍內(nèi)的數(shù)據(jù)的復制。它除了自己存儲一份之外瞎访，還會 在環(huán)上順時針方向的其他 N-1 個節(jié)點存儲一份副本腻贰。因此在系統(tǒng)中，每個節(jié)點要負責從 它自己往后的一共 N 個節(jié)點扒秸。

例如播演，圖 2 中，B 除了自己存儲一份之外伴奥，還會將其復制到 C 和 D 節(jié)點写烤。因此，D 實際 存儲的數(shù)據(jù)拾徙，其 key 的范圍包括 (A, B]洲炊、(B, C] 和 (C, D]（例如，落在 (A, B] 范圍內(nèi)的 key 會沿順時針方向找到第一個值比它大的節(jié)點尼啡，因此找到的是 B选浑，而 B 會 將自己存儲的數(shù)據(jù)復制到 C 和 D，因此 D 會包含 key 在 (A, B] 范圍內(nèi)的對象玄叠。其他 幾個范圍也是類似的。譯者注）拓提。

image

圖 2 Dynamo 哈希環(huán)上 key 的分散（partition）和復制（replication）

存儲某個特定 key 的所有節(jié)點組成一個列表读恃，稱為 preference list（優(yōu)先列表）。 我們在 4.8 節(jié)會看到代态，Dynamo 的設(shè)計是寺惫，對于給定的 key，每個節(jié)點都能決定哪些 節(jié)點可以進入這個列表蹦疑。為了應(yīng)對節(jié)點失敗的情況西雀，preference list 會包含多余 N 個節(jié) 點。

另外注意歉摧，由于我們引入了虛擬節(jié)點艇肴，存儲一個 key 的 N 個節(jié)點，實際上對應(yīng)的物理節(jié) 點可能少于 N 個（例如叁温，一個節(jié)點可能會占用環(huán)上的不止一個節(jié)點）再悼。為了避免這個問題 ，preference list 在選擇節(jié)點的時候會跳過一些位置膝但，以保證 list 里面的節(jié)點都在不 同的物理節(jié)點上冲九。

4.4 數(shù)據(jù)版本化（Data Versioning）

Dynamo 提供最終一致性，所有更新操作會異步地傳遞給所有的副本跟束。

put() 操作返回時莺奸，數(shù)據(jù)（更新）可能還沒有應(yīng)用到所有副本丑孩，因此緊接著的 get() 操作可能獲取不到最新數(shù)據(jù)。在沒有故障的情況下灭贷，傳遞更新的耗時有一個上限温学；但在特定 故障場景下（例如服務(wù)器宕機或網(wǎng)絡(luò)分裂），更新可能會在限定的時間內(nèi)無法傳遞到所有副 本氧腰。

Amazon 有些應(yīng)用是可以容忍這種不一致性的枫浙，應(yīng)用在這種情況下能繼續(xù)運行。例如古拴，購物 車應(yīng)用要求“添加到購物車”的請求永遠不能被丟失或拒絕箩帚。如果購物車的最新狀態(tài)不可用， 而用戶對一個稍老版本的購物車狀態(tài)做了修改黄痪，那這種修改也是有意義的紧帕，需要保留；但它 不能直接覆蓋最新的狀態(tài)桅打，因為最新的狀態(tài)中可能也有一些修改需要保留是嗜。這里要注意，不 管是“添加到購物車”還是“從購物車刪除”挺尾，在系統(tǒng)中轉(zhuǎn)換成的都是 Dynamo 的 put() 操作 鹅搪。如果最新的狀態(tài)不可用，而用戶又基于稍的大版本做了修改遭铺，那這兩個版本都需要保留丽柿， 由隨后的步驟來處理更新沖突。

如何解決更新沖突

為了滿足以上需求魂挂，Dynamo 將每次修改結(jié)果都作為一個新的甫题、不可變的版本。

Dynamo treats the result of each modification as a new and immutable version of the data.

即涂召，允許系統(tǒng)中同時存在多個不同版本坠非。

沖突調(diào)和（使一致化）方式

• syntactic reconciliation（基于句法的調(diào)和）
• semantic reconciliation（基于語義的調(diào)和）

在大部分情況下，新版本都包含老版本的數(shù)據(jù)果正，而且系統(tǒng)自己可以判斷哪個是權(quán)威版本 （syntactic reconciliation）炎码。

但是，在發(fā)生故障并且存在并發(fā)更新的場景下舱卡，版本會發(fā)生分叉（version branching）辅肾， 導致沖突的對象版本。系統(tǒng)本身無法處理這種情況轮锥，需要客戶端介入矫钓，將多個分支合并成 一個（semantic reconciliation）。一個典型的例子是：合并多個不同版本的購物車。 有了這種調(diào)和機制（reconciliation mechanism）新娜，“添加到購物車”操作就永遠不會失敗 赵辕；但是，這種情況會導致已經(jīng)刪除的商品偶爾又在購物車中冒出來（resurface）概龄。

有很重要的一點需要注意：某些故障模式（failure mode）會導致存在多個沖突的版本还惠，而 不僅僅是兩個。服務(wù)器故障或網(wǎng)絡(luò)分裂會導致一個對象有多個版本私杜，每個版本有各自的子歷 史（version sub-histories）蚕键，隨后要由系統(tǒng)來將它們一致化。這需要將應(yīng)用 設(shè)計為：顯式承認多版本存在的可能性（以避免丟失任何更新）

向量時鐘

Dynamo 使用向量時鐘（****vector clock****）****[12] 來跟蹤同一對象不同版本之間的因果性衰粹。 一個向量時鐘就是一個 (node, counter) 列表锣光。一個向量時鐘關(guān)聯(lián)了一個對象的所有版 本，可以通過它來判斷對象的兩個版本是否在并行的分支上铝耻，或者它們是否有因果關(guān)系誊爹。 如果對象的第一個時鐘上的所有 counter 都小于它的第二個時鐘上的 counter****，那第一個 時鐘就是第二的祖先瓢捉，可以安全的刪除频丘；否則，這兩個修改就是有沖突的泡态，需要 reconciliation搂漠。

在 Dynamo 中，客戶端更新一個對象時某弦，必須指明基于哪個版本進行更新状答。流程是先執(zhí) 行讀操作，拿到 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 是如何工作的。

image

圖 3 一個對象在一段時間內(nèi)的版本演進

首先幕随，客戶端寫入一個對象蚁滋。處理這個 key 的寫請求的節(jié)點 Sx 增加 key 的序列號（計 數(shù)），并用這個序列號創(chuàng)建對象的 vector clock。至此辕录，系統(tǒng)有了一個對象 D1 和它的 時鐘 [(Sx, 1)]睦霎。

第二步，客戶端更新這個對象走诞。假設(shè)還是 Sx 處理這個請求副女。此時，系統(tǒng)有了對象 D2 和它的時鐘 [(Sx, 2)]蚣旱。D2 是 D1 的后代碑幅，因此可以覆蓋 D1；但是塞绿，****D1 在 其他節(jié)點上的副本可能還沒有看到 D2 這次更新沟涨。

第三步，假設(shè)還是這個客戶端位隶，再次更新了對象拷窜，并且這次是由另外的一個節(jié)點 Sy 處理 請求。此時涧黄，系統(tǒng)有了 D3 和它的時鐘 [(Sx, 2), (Sy, 1)].

接下來篮昧，假設(shè)另一個客戶端讀取 D2，并嘗試更新它笋妥，寫請求由另一個節(jié)點 Sz 處理懊昨。 現(xiàn)在，系統(tǒng)有 D4（D2 的后代）春宣，版本 clock 是 [(Sx, 2), (Sz, 1)]酵颁。如果一個節(jié) 點知道 D1 和 D2，那它收到 D4 和它的 clock 后月帝，就可以斷定 D1 和 D2 被同 一個新數(shù)據(jù)覆蓋了躏惋，因此可以安全地刪除 D1 和 D2。但如果一個節(jié)點只知道 D3嚷辅，那它受 到 D4 后就看不出這兩個版本有何因果關(guān)系簿姨。換言之，****D3 和 D4 各自的改動并沒 有反映在對方之中簸搞。因此這兩個版本都應(yīng)當被保留扁位，然后交給客戶端，由客戶端（在下一次 讀到時候）執(zhí)行 semantic reconciliation趁俊。

現(xiàn)在域仇，假設(shè)一些客戶端把 D3 和 D4 都讀到了（context 會同時顯示 D3 和 D4 ）。讀操作返回的 context 綜合了 D3 和 D4 的 clock寺擂，即 [(Sx, 2), (Sy, 1), (Sz, 1)]暇务。如果客戶端執(zhí)行 reconciliation泼掠，并且節(jié)點 Sx 執(zhí)行協(xié)調(diào)寫（coordinates the write），Sx 會更新自己在 clock 中的序列號般卑。最終新生成的數(shù)據(jù) D5 的 clock 格式如下：[(Sx, 3), (Sy, 1), (Sz, 1)]武鲁。

Vector clock 的潛在問題

vector clock 的一個潛在問題是：如果有多個節(jié)點先后 coordinate 同一個對象 的寫操作，那這個對象的 clock vector 會變得很長蝠检。但在實際中這不太可能發(fā)生沐鼠，因為 寫操作 coordination 只會由 preference list 中前 N 個 節(jié)點中的一個來執(zhí)行。 只有在網(wǎng)絡(luò)分裂或多臺服務(wù)器掛掉的情況下叹谁，寫操作才可能由非 preference list 前 N 個 節(jié)點來執(zhí)行饲梭，導致 vector clock 變長。在這種情況下焰檩，應(yīng)該要限制 vector clock 的長度 憔涉。

Dynamo 采用了一種 clock 截斷方案（clock truncation scheme）： 另外保存一個和 (node, counter) 對應(yīng)的時間戳，記錄對應(yīng)的節(jié)點最后一次更新該記錄 的時間析苫。當 vector clock 里的 (node, counter) 數(shù)量達到一個閾值（例如兜叨，10）時， 就刪除最老的一項衩侥。

顯然国旷，這種截斷方案會給 reconciliation 帶來一定問題，因為截斷后可能無法精確判斷部 分后代的因果關(guān)系茫死。但到目前為止跪但，我們還沒有在生產(chǎn)環(huán)境遇到這個問題，因此沒有繼續(xù)深 入研究下去峦萎。

4.5 get() 和 put() 的執(zhí)行過程

在 Dynamo 中屡久，任何存儲節(jié)點都可以接受任何 key 的 get 和 put 操作請求。

Any storage node in Dynamo is eligible to receive client get and put operations for any key.

本節(jié)先介紹在無故障場景下這些操作是如何執(zhí)行的爱榔，下一節(jié)介紹有故障的場景被环。

get 和 put 操作由 Amazon 基礎(chǔ)設(shè)施相關(guān)的請求處理框架發(fā)起，使用 HTTP详幽。 客戶端有兩種選擇：

1. 將請求路由到負載均衡器蛤售，由后者根據(jù)負載信息選擇一個后端節(jié)點
2. 使用能感知 partition 的客戶端，直接將請求路由到某 coordinator 節(jié)點

第一種方式的好處是使用客戶端的應(yīng)用不需要了解任何 Dynamo 相關(guān)的代碼妒潭，第二種的好處 是延遲更低，因為跳過了一次潛在的轉(zhuǎn)發(fā)步驟揣钦。

負責處理讀或?qū)懻埱蟮墓?jié)點稱為 coordinator雳灾。通常情況下，這是 preference list 內(nèi)前 N 個節(jié)點中的第一個節(jié)點冯凹。如果請求是經(jīng)過負載均衡器轉(zhuǎn)發(fā)的谎亩，那這個請求 可能會被轉(zhuǎn)發(fā)到環(huán)上的任意一個節(jié)點炒嘲。在這種情況下，如果收到請求的節(jié)點不是 preference list 的 前 N 個節(jié)點中的一個匈庭，那它就不會處理這個請求夫凸，而是將其轉(zhuǎn)發(fā)到 preference list 前 N 個節(jié)點中的第一個節(jié)點。

讀或?qū)懖僮餍枰?preference list 中前 N 個節(jié)點處于健康狀態(tài)阱持，如果有 down 或不可 訪問狀態(tài)的節(jié)點夭拌，要跳過。如果所有節(jié)點都是健康的衷咽，那就取 preference list 的前 N 個 節(jié)點鸽扁。如果發(fā)生節(jié)點故障或網(wǎng)絡(luò)分裂，優(yōu)先訪問 preference list 中編號較小的節(jié)點镶骗。

讀寫操作仲裁算法

為了保證副本的一致性桶现，Dynamo 使用了一種類似仲裁系統(tǒng)（quorum systems）的一致性協(xié)議。 這個協(xié)議有兩個配置參數(shù)：R 和 W：

• R：允許執(zhí)行一次讀操作所需的最少投票者
• W：允許執(zhí)行一次寫操作所需的最少投票者

設(shè)置 R + W > N（R 或 W 至少有一個超過半數(shù) N/2鼎姊，譯者注）骡和，就得到了一 個類似仲裁的系統(tǒng)。

在這種模型下相寇，一次 get （或 put）的延遲由 R（或 W）個副本中最慢的一個決 定慰于。因此，為了降低延遲裆赵，R 和 W 通常設(shè)置的比 N 小东囚。

寫和讀過程

當收到一個 put() 請求后睹酌，coordinator 會為新版本生成 vector clock嘀倒，并將其保存到 節(jié)點本地；然后贰军，將新版本（及對應(yīng)的新 vector clock）發(fā)送給 N 個排在最前面的植兰、可到 達的節(jié)點份帐。只要有至少 W-1 個節(jié)點返回成功，這次寫操作就認為是成功了楣导。

類似地废境，對于一次 get() 請求，coordinator 會向排在最前面的 N 個（highest-ranked ）可訪問的節(jié)點請求這個 key 對應(yīng)的數(shù)據(jù)的版本筒繁，等到 R 個響應(yīng)之后噩凹，就將結(jié)果返回給客 戶端。如果 coordinator 收集到了多個版本毡咏，它會將所有它認為沒有因果關(guān)系的版本返 回給客戶端驮宴。客戶端需要對版本進行 reconcile呕缭，合并成一個最新版本堵泽，然后將結(jié)果寫回 Dynamo修己。

4.6 短時故障處理: Hinted Handoff（移交給其他節(jié)點臨時保存）

如果使用傳統(tǒng)仲裁算法，Dynamo 無法在服務(wù)器宕機或網(wǎng)絡(luò)分裂的時候仍然保持可用迎罗，而且 在遇到最簡單故障情況下睬愤，持久性（durability）也會降低。

因此纹安，Dynamo 采用了一種寬松的仲裁機制（sloppy quorum）：所有讀和寫操作在 preference list 的前 N 個健康節(jié)點上執(zhí)行尤辱；注意這 N 個節(jié)點不一定就是前 N 個節(jié)點， 因為遇到不健康的節(jié)點钻蔑，會沿著一致性哈希環(huán)的順時針方向順延啥刻。

image

圖 2 Dynamo 哈希環(huán)上 key 的分散（partition）和復制（replication）

以圖 2 的配置為例，其中 N=3咪笑。如果 A 臨時不可用可帽，正常情況下應(yīng)該到達 A 的寫請求就 會發(fā)送到 D。這樣設(shè)計是為了保證期望達到的可用性和持久性窗怒。發(fā)送到 D 的副本的元 數(shù)據(jù)中會提示（hint）這個副本本來應(yīng)該發(fā)送給誰（這里是 A）映跟，然后這個數(shù)據(jù)會被 D 保存到本地的一個獨立數(shù)據(jù)庫中，并且有一個定期任務(wù)不斷掃描扬虚，一旦 A 可用了努隙，就將 這個數(shù)據(jù)發(fā)送回 A，然后 D 就可以從本地數(shù)據(jù)庫中將其刪除了辜昵，這樣系統(tǒng)內(nèi)的副本數(shù)還 是保持不變荸镊。

使用這種 hinted handoff 的方式，Dynamo 保證了在節(jié)點或網(wǎng)絡(luò)發(fā)生短時故障時讀和寫 操作不會失敗堪置。希望可用性最高的應(yīng)用可以將 W 設(shè)為 1躬存，這樣可以保證只要一個節(jié)點 完成寫，這次寫操作就被系統(tǒng)接受了舀锨。在這種情況下岭洲，除非全部節(jié)點都不可用，否則寫操作 就不會被拒絕坎匿。但實際上盾剩，大部分 Amazon 的應(yīng)用都是設(shè)置一個比 1 大的值，以達到期望 的持久性（durability）等級替蔬。我們會在第 6 節(jié)更深入地討論 N告私、R 和 W 的配置。

高度可用的存儲系統(tǒng)必須能夠處理整個數(shù)據(jù)中心掛掉的情況承桥。掉電驻粟、制冷失效、網(wǎng)絡(luò)故 障以及自然災難都會導致整個數(shù)據(jù)中心發(fā)生故障快毛。Dynamo 可以配置向多個數(shù)據(jù)中心同步 副本格嗅，只要將 preference list 里的節(jié)點分散到不同數(shù)據(jù)中心。這些數(shù)據(jù)中心之間 通過高速網(wǎng)絡(luò)互連唠帝。這使得我們可以在整個數(shù)據(jù)中心掛掉的情況下仍然可以提供服務(wù)屯掖。

4.7 持久（permanent）故障處理: 副本跨數(shù)據(jù)中心同步

在節(jié)點成員變動較小、節(jié)點故障只是短時的情況下襟衰，hinted handoff 方式工作良好贴铜。但也 有一些場景，在 hinted 副本移交給原本應(yīng)該存儲這個副本的節(jié)點之前瀑晒，該副本就不可用了 绍坝。為了解決這個問題，以及其他威脅到持久性（durability）的場景苔悦，Dynamo 實現(xiàn)了一種 逆熵（副本同步）協(xié)議來保證副本是同步的轩褐。

To handle this and other threats to durability, Dynamo implements an anti-entropy (replica synchronization) protocol to keep the replicas synchronized.

Merkle Tree

為了實現(xiàn)快速檢測副本之間的不一致性，以及最小化轉(zhuǎn)移的數(shù)據(jù)量玖详，Dynamo 使用了 Merkle trees [13].

一個 Merkle tree 就是一個哈希樹把介，其葉子節(jié)點是 key 對應(yīng)的 value 的哈希值。 父節(jié)點是其子節(jié)點的哈希蟋座。

Merkle tree 的主要優(yōu)點是：

• 每個分支都可以獨立查看（check）拗踢，節(jié)點無需下載整棵樹或者整個數(shù)據(jù)集
• 減少檢查副本一致性時所需傳輸?shù)臄?shù)據(jù)量

例如，如果兩棵樹的根節(jié)點的哈希值相同向臀，那這兩棵樹的葉子節(jié)點必然相同巢墅，這兩臺 node 之間就無需任何同步；否則券膀，就說明兩臺 node 之間的某些副本是不同的君纫，這種情 況下兩臺 node 就需要交換樹的子節(jié)點哈希值，直到到達葉Ring Membership子節(jié)點三娩，就找到了未同步（out of sync）的 key庵芭。Merkle tree 最小化了同步時需要轉(zhuǎn)移的數(shù)據(jù)量，減少了逆熵過程中 讀取磁盤的次數(shù)雀监。

Dynamo 使用 Merkle tree 實現(xiàn)逆熵的過程如下：每個節(jié)點為每段 key range（一臺 虛擬節(jié)點所覆蓋的 key 的范圍）維護了一棵單獨的 Merkle tree双吆。

這使得節(jié)點之間可以比較 key range，確定其維護的 range 內(nèi)的 key 是否是最新的（up to date）会前。在這種方案中好乐，兩個節(jié)點會交換他們都有的 key range 所對應(yīng)的 Merkle tree 的 根節(jié)點。然后瓦宜，基于前面提到的樹遍歷方式蔚万， node 可以判斷是是否有不一致，如果有临庇，就 執(zhí)行同步反璃。

這種方案的缺點是：每當有節(jié)點加入或離開系統(tǒng)時昵慌，一些 key range 會變，因此對應(yīng)的 tree 需要重新計算淮蜈。我們會在 6.2 節(jié)介紹如何通過改進的 partitioning scheme 解決 這個問題斋攀。

4.8 節(jié)點成員（Membership）管理和故障檢測

4.8.1 哈希環(huán)（ring）成員

在 Amazon 的環(huán)境中，節(jié)點服務(wù)不可用（故障或維護導致的）通常情況下持續(xù)時間都很短梧田， 但也存在中斷比較長的情況淳蔼。一個節(jié)點服務(wù)中斷并不能說明這個節(jié)點永久性的離開了系統(tǒng)， 因此不應(yīng)該導致系統(tǒng)對 partition 進行再平衡（rebalance）裁眯，或者修復無法訪問的副本鹉梨。 與此類似，無意的手動操作可能導致新的節(jié)點加入到 Dynamo穿稳。

因此存皂，為了避免以上這些問題，我們決定使用顯式機制（explicit mechanism）來向 Dynamo Ring 增刪節(jié)點司草。管理員通過命令行或 web 方式連接到 Dynamo node艰垂，然后下發(fā) 一個成員變更命令，來將這個 node 添加到 ring 或從 ring 刪除埋虹。負責處理這個請求的 node 將成員變動信息和對應(yīng)的時間寫入持久存儲猜憎。成員變動會形成歷史記錄，因為一個節(jié) 點可能會多次從系統(tǒng)中添加和刪除搔课。Dynamo 使用一個 gossip-based 的算法通告（ propagete）成員變動信息胰柑，維護成員的一份最終一致視圖。

每個節(jié)點每秒會隨機選擇另一個節(jié)點作為對端爬泥，這兩個節(jié)點會高效地 reconcile 它們的成 員變動歷史柬讨。

一個節(jié)點第一次起來時，首先會選擇它的 token 集合（一致性哈吓鄯龋空間內(nèi)的虛擬節(jié)點 ）踩官，然后將節(jié)點映射到各自的 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.

映射關(guān)系會持久存儲到磁盤上境输，初始時只包含本節(jié)點（local node）和 token set蔗牡。存 儲在不同 Dynamo 節(jié)點上的映射關(guān)系，會在節(jié)點交換成員變動歷史時被 reconcile嗅剖。因 此辩越，partitioning 和 placement（數(shù)據(jù)的放置信息）也會通過 gossip 協(xié)議進行擴散，最 終每個節(jié)點都能知道其他節(jié)點負責的 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.

這使得每個節(jié)點可以將一個 key 的讀/寫操作直接發(fā)送給正確的節(jié)點進行處理黔攒。

4.8.2 系統(tǒng)外部發(fā)現(xiàn)（External Discovery）和種子節(jié)點

以上機制可能導致 Dynamo ring 在邏輯上臨時分裂。

例如，管理員先聯(lián)系 node A督惰，將 A 將入 ring不傅，然后又聯(lián)系 node B 加入 ring。在這種情 況下赏胚，A 和 B 都會認為它們自己是 ring 的成員蛤签，但不會立即感知到對方。

為了避免邏輯分裂栅哀，我們會將一些 Dynamo 節(jié)點作為種子節(jié)點。種子節(jié)點是通過外部機 制（external mechanism）發(fā)現(xiàn)的称龙，所有節(jié)點都知道種子節(jié)點的存在留拾。因為所有節(jié)點最終都 會和種子節(jié)點 reconcile 成員信息，所以邏輯分裂就幾乎不可能發(fā)生了鲫尊。

種子或者從靜態(tài)配置文件中獲取痴柔，或者從一個配置中心獲取。通常情況下疫向，種子節(jié)點具有普 通節(jié)點的全部功能咳蔚。

4.8.3 故障檢測

故障檢測在 Dynamo 中用于如下場景下跳過不可達的節(jié)點：

• get() 和 put() 操作時
• 轉(zhuǎn)移 partition 和 hinted replica 時

要避免嘗試與不可達節(jié)點通信，一個純本地概念（pure local notion）的故障檢測就 足夠了：節(jié)點 B 只要沒有應(yīng)答節(jié)點 A 的消息搔驼，A 就可以認為 B 不可達（即使 B 可以應(yīng)答 C 的消息）谈火。

在客戶端有持續(xù)頻率的請求的情況下，Dynamo ring 的節(jié)點之間就會有持續(xù)的交互舌涨；因此只 要 B 無法應(yīng)答消息糯耍，A 可以很快就可以發(fā)現(xiàn)；在這種情況下囊嘉，A 可以選擇和與 B 同屬一個 partition 的其他節(jié)點來處理請求温技，并定期地檢查 B 是否活過來了。

在沒有持續(xù)的客戶端請求的情況下扭粱，兩個節(jié)點都不需要知道另一方是否可達舵鳞。

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.

去中心化故障檢測協(xié)議使用簡單的 gossip 風格協(xié)議，使得系統(tǒng)內(nèi)的每個節(jié)點都可以感知 到其他節(jié)點的加入或離開琢蛤。想詳細了解去中心化故障檢測機制及其配置蜓堕，可以參考 [8]。

Dynamo 的早期設(shè)計中使用了一個去中心化的故障檢測器來維護故障狀態(tài)的全局一致視圖 （globally consistent view of failure state）虐块。

后來我們發(fā)現(xiàn)俩滥，我們顯式的節(jié)點加入和離開機制使得這種全局一致視圖變得多余了。因 為節(jié)點的真正（permanent）加入和離開消息贺奠，依靠的是我們的顯式添加和刪除節(jié)點機制霜旧， 而臨時的加入和離開，由于節(jié)點之間的互相通信（轉(zhuǎn)發(fā)請求時），它們自己就會發(fā)現(xiàn)挂据。

4.9 添加/移除存儲節(jié)點

當一個新節(jié)點 X 加入到系統(tǒng)后以清，它會獲得一些隨機分散在 ring 上的 token。對每 個分配給 X 的 key range崎逃，當前可能已經(jīng)有一些（小于等于 N 個）節(jié)點在負責處理了 掷倔。因此,將 key range 分配給 X 后，這些節(jié)點就不需要處理這些 key 對應(yīng)的請求了个绍，而 要將 keys 轉(zhuǎn)給 X勒葱。

考慮一個簡單的情況：X 加入 圖 2 中 A 和 B 之間。這樣巴柿，X 就負責處理落到 (F, G], (G, A] and (A, X] 之間的 key凛虽。結(jié)果，B广恢、C 和 D 節(jié)點就不需負責相應(yīng) range 了凯旋。因此，在收到 X 的轉(zhuǎn)移 key 請求之后钉迷，B****至非、****C 和 D 會向 X 轉(zhuǎn)移相 應(yīng)的 key。當移除一個節(jié)點時糠聪，key 重新分配的順序和剛才相反荒椭。

image

圖 2

我們的實際運行經(jīng)驗顯示，這種方式可以在存儲節(jié)點之間保持 key 的均勻分布舰蟆，這對 于保證延遲需求和快速 bootstrapping 是非常重要的戳杀。另外，在源和目的節(jié)點之間加了確 認（轉(zhuǎn)移）夭苗，可以保證不會轉(zhuǎn)移重復的 key range信卡。

5. 實現(xiàn)

Dynamo 中的每個存儲節(jié)點上主要有三個組件，都是用 Java 實現(xiàn)的：

• request coordination（請求協(xié)調(diào)）組件
• 成員驗證和故障檢測組件
• 本地持久存儲引擎

本地存儲引擎

Dynamo 的本地持久存儲組件支持以插件的方式使用不同的存儲引擎题造。在使用的引擎包括：

• Berkeley Database (BDB) Transactional Data Store2
• BDB Java Edition
• MySQL
• an in-memory buffer with persistent backing store

將其設(shè)計為可插拔的原因是：為不同應(yīng)用訪問類型選擇最合適的存儲引擎傍菇。例如，BDB 通常用于處理幾十 KB 大小的對象界赔，而 MySQL 可以處理更大的對象丢习。應(yīng)用可以根據(jù)它們的 對象大小分布選擇合適的持久化引擎。

我們生產(chǎn)環(huán)境的 Dynamo 大部分使用的都是 BDB Transactional Data Store淮悼。

請求協(xié)調(diào)

request coordination 組件構(gòu)建在一個事件驅(qū)動的消息系統(tǒng)之上咐低，其中的消息處理 pipeline 分為多個階段，和 SEDA 架構(gòu)類似 [24]袜腥。所有通信都基于 Java NIO channel 實現(xiàn)见擦。

coordinator 代替客戶端執(zhí)行讀和寫請求：讀操作時會從一個或多個節(jié)點收集數(shù)據(jù)，寫操作 時會向一個或多個節(jié)點存儲數(shù)據(jù)。每個客戶端請求都會在收到這個請求的節(jié)點上創(chuàng)建一個狀 態(tài)機鲤屡。這個狀態(tài)機包含了識別 key 對應(yīng)的節(jié)點损痰、發(fā)送請求、等待響應(yīng)酒来、重試卢未、處理響應(yīng)和 組合響應(yīng)返回給客戶端等所有邏輯。

read coordination

每個狀態(tài)機處理且只處理一個客戶端請求堰汉。例如辽社，一個讀操作實現(xiàn)了包含如下步驟的狀態(tài)機：

1. 發(fā)送讀請求給節(jié)點
2. 等待所需的最少數(shù)量響應(yīng)
3. 如果在規(guī)定的上限時間內(nèi)收到的響應(yīng)數(shù)量太少，認定請求失敗
4. 否則翘鸭，收集對象的所有版本爹袁，確定應(yīng)該返回哪些
5. 如果打開了版本化（versioning）配置，執(zhí)行 syntactic reconciliation矮固，生成一個不 透明的寫上下文（context），其中包含了合并之后的版本對應(yīng)的的 vector clock

為了描述的簡單譬淳，以上沒有提及故障處理和重試的步驟档址。

讀操作的響應(yīng)發(fā)送給調(diào)用方之后，狀態(tài)機會繼續(xù)等待一小段時間邻梆，接收可能的有效響應(yīng)（ outstanding responses守伸，例如最小數(shù)量響應(yīng)之外的其他節(jié)點的響應(yīng)，譯者注）浦妄。

如果返回中有過期版本（stale version）尼摹，coordinator 就需要合并版本，并將最新版本 更新回這些節(jié)點剂娄。這個過程稱為“讀時修復”（read repair）蠢涝，因為它在一個樂觀的 時間點（at an opportunistic time）修復了那些錯過了最新更新的副本（replicas that have missed a recent update），減少了逆熵協(xié)議的工作（本來應(yīng)該是稍后由逆 熵協(xié)議做的）和二。

write coordination

前面提到過耳胎，寫請求是由 preference list 內(nèi)的前 N 個節(jié)點中的任意一個 coordinate 的 怕午∮粝В總是讓 N 個節(jié)點中的第一個來 coordinate 有一些好處堡距，例如可以使得在同一個地方完 成寫操作的順序化（serializing all writes），但是，這種方式也有缺點：它會導致不均 勻的負載分布吏颖，損害 SLA搔体。這是因為對象請求并不是均勻分布的（request load is not uniformly distributed across objects）。

為了解決這個問題半醉，preference list 內(nèi)的所有 N 個節(jié)點都可以 coordinate 寫操作疚俱。 而且，因為一個寫操作之前通常有一個讀操作缩多，因此寫操作的 coordinator 都選擇為：前 一次讀操作返回最快的那個節(jié)點呆奕，這個信息存儲在讀操作返回的上下文中。

這項優(yōu)化還使在下一次讀取時衬吆，前一次讀操作選中的存儲這個數(shù)據(jù)的節(jié)點更容易被選中梁钾，提 高了“讀取剛寫入的數(shù)據(jù)”（“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. 測試結(jié)果及學到的經(jīng)驗

Dynamo 被幾種不同類型的服務(wù)使用，每種場景下的配置不同。這些不同體現(xiàn)在 vesion reconciliation 邏輯和讀/寫仲裁特點上煌集。幾種主要的場景：

• 業(yè)務(wù)邏輯相關(guān)的 reconciliation：這種場景使用很廣。每個數(shù)據(jù)對象都會復制到不同節(jié) 點上方面，發(fā)生版本沖突時由應(yīng)用執(zhí)行自己的 reconciliation 邏輯。前文提到的購物 車服務(wù)就是一個典型的例子颓屑，應(yīng)用自己來合并沖突的購物車版本
• 基于時間戳的 reconciliation：和第一種的不同僅僅是 reconciliation 機制。當 發(fā)生版本沖突時器腋，Dynamo 根據(jù)“****最后一次寫勝出****”（last write wins）機制，例如措左， 選擇時間戳最近的一個版本作為最終版本。一個例子是維護客戶 session 信息的服務(wù)
• 高性能讀引擎：雖然 Dynamo 設(shè)計為永遠可寫（always writeable） 數(shù)據(jù)倉庫, 但 一些服務(wù)通過對 Dynamo 的仲裁特性進行調(diào)優(yōu)（****tuning****），而將其作為一個高性能讀引 擎使用。典型情況下蝌借，這類服務(wù)有很高的讀頻率和很小的寫頻率凝化。在這種配置中瞧哟， R 一般設(shè)為 1****，****W 設(shè)為 N傍衡。對于這些服務(wù)，Dynamo 提供了 partition 和數(shù)據(jù)跨 多節(jié)點復制的能力绣的，因而提供了增量可擴展性。數(shù)據(jù)的權(quán)威持久緩存（the authoritative persistence cache for data）存儲在更重量級的后端存儲中（more heavy weight backing stores）盼理。維護產(chǎn)品目錄和促銷商品的服務(wù)會用到這種類型 的 Dynamo 配置

Dynamo 的最大優(yōu)勢是：客戶端應(yīng)用可以通過對 N畴椰、R 和 W 三個參數(shù)進行調(diào)優(yōu)來達到期 望的性能抓艳、可用性和持久性等級。

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 設(shè)為 1，那只要系統(tǒng)還 有一臺正常的 node香椎，寫操作就不會被拒絕。但是，太小的 W 和 R 配置會增加不一致的風 險慎框，因為一次寫操作即使在沒有大多數(shù)副本都寫成功的情況下，還是會給客戶端返回成功。 這也導致存在一個風險窗口（vulnerability window）：一次寫操作即使只在少量節(jié) 點上完成了持久化硫嘶，也會向客戶端返回成功称近。

傳統(tǒng)觀點認為凳谦，持久性和可用性是相伴而生（go hand in hand）的，但在這里不一定成立绊诲。 例如，增加 W 就會減小持久性的風險窗口世舰；但是，這可能會增加請求被拒絕的概率（因此 降低了可用性），因為這種情況下需要更多的健康存儲節(jié)點來處理寫請求喷好。

我們最常用的 Dynamo 集群 (N,R,W) 配置是 (3,2,2)。這個配置符合我們所需的 性能、持久性哆键、一致性和可用性（SLA）等級。

本節(jié)所有的數(shù)據(jù)都是從一套線上 Dynamo 環(huán)境獲得的，配置是 (3,2,2)颂碘， 有幾百臺節(jié)點（a couple hundred nodes）塔拳，配置利用到了異構(gòu)硬件信息澎胡。

之前我們提到稚伍，每套 Dynamo 的節(jié)點都是跨數(shù)據(jù)中心部署的，這些數(shù)據(jù)中心之間通過高速網(wǎng) 絡(luò)互聯(lián)。執(zhí)行一次成功的 get （或 put）需要 R （或 W）個節(jié)點向 coordinator 發(fā)送響應(yīng)猴贰，因此很明顯，數(shù)據(jù)中心之間的時延會影響到響應(yīng)時間，因此在選擇節(jié)點（以及它 所在的數(shù)據(jù)中心的位置）的時候要特別注意碱鳞，以保證能滿足應(yīng)用期望的 SLA星岗。

6.1 性能和持久性的平衡

雖然 Dynamo 的首要設(shè)計目標是一個高可用數(shù)據(jù)倉庫缰儿，但性能指標在 Amazon 也同樣重要烙常。 前面提到過，為了提供一致的用戶體驗，Amazon 的服務(wù)會設(shè)置一個很高的用百分比衡量的 （例如 P99.9 或 P99.99）性能指標德澈。典型的 SLA 指標是：讀和寫操作的 P99.9 要 在 300ms 以內(nèi)成。

由于 Dynamo 是在通用硬件上運行的，和高端企業(yè)級服務(wù)器相比忽肛，I/O 吞吐性能要差 很多，因此提供一致的高性能讀寫并不是一項簡單的工作。而且手销，每次讀/寫操作都要涉 及多臺節(jié)點，給這項工作帶來了更大的挑戰(zhàn)性兽埃，因為最終的性能受限于最慢的那個副本所 在的節(jié)點。

通用配置下的性能

圖 4 顯示了 30 天內(nèi) Dynamo 的讀和寫操作延遲平均值和 P99.9：

image

圖 4 2006 年 12 月峰值請求季的讀寫延遲平均值和 P99.9。 X 軸一個刻度 12 小時敢伸。延遲走勢和每天的請求量走勢一致，延遲的 P99.9 比平均值要大一個數(shù)量級。

從圖上可以看出弃揽，延遲曲線每天的走勢（diurnal pattern）都類似，這和平臺每天的請求 量走勢也是一致的（例如，白天和晚上的請求量明顯不一樣）娜庇。另外，寫延遲明顯高于讀延 遲，因為寫操作永遠需要訪問磁盤汁掠。另外，P99.9 大約為 200ms****乞榨，比平均值高一 個數(shù)量級趾访。這是因為 P99.9 有很多影響因素申鱼，例如請求負載變化、對象大小和 locality patterns。

低延遲配置下的性能

以上性能對很多服務(wù)來說都足夠了猴鲫，但有少數(shù)面向用戶的服務(wù)姻几，它們對性能有更高的要求抚恒。 對于這種情況盒音，Dynamo 提供了犧牲持久性換性能的能力。具體來說，每個存儲節(jié)點會 在主內(nèi)存中維護一個對象緩存（object buffer）绳姨，寫操作將數(shù)據(jù)存儲到緩存直接返回， 另有一個獨立的寫線程定期將數(shù)據(jù)寫入磁盤。讀操作會先檢查緩存中是否有碾盐，如果有，就直 接從緩存讀涩盾，從而避免了訪問存儲引擎址儒。

這項優(yōu)化可以將峰值流量期間的 P99.9 降低到原來的 1/5，即使只使用一個很小的 喧伞、只能存放 1000 個對象的緩存，見圖 5绩郎。

image

圖 5 帶緩存和不帶緩存的 P99.9 性能對比潘鲫，時間跨度 24 小時，X 軸一個刻度一個小時

另外肋杖，從圖中可以看到怨喘，緩存寫（write buffering）可以對百分比延遲進行平滑徘郭。顯然镇草， 這種方案中持久性和性能之間做了折中：一臺節(jié)點掛掉會導致緩存里還未落盤的數(shù)據(jù)丟失祟偷。 為了減小這種風險滓侍，寫操作進行了優(yōu)化（refine），由 coordinator 從 N 個副本中選擇 一個進行持久化寫入（durable write）南片。因為 coordinator 只等待 W 個寫操作嚼锄，因此整 體的寫操作不受這次寫盤操作的影響。

以上優(yōu)化的意思是主经，每次寫操作到達 coordinator 時抽高，它會將請求轉(zhuǎn)發(fā)給相應(yīng)個節(jié)點莹桅， 這些節(jié)點都是寫完內(nèi)存 buffer 就直接返回的；除此之外，coordinator 還會挑一個節(jié)點 進行持久寫入，跟其他節(jié)點的寫是并行進行的疟游，這樣可以降低其他節(jié)點掛掉時內(nèi)存數(shù)據(jù)丟 失的風險干签。由于 coordinator 只等待 W 個結(jié)果就返回了浩峡，因此雖然這個執(zhí)行持久寫的節(jié) 點（相對）很慢，但 coordinator 并不會依賴它的結(jié)果才返回呻惕，因此文中說對寫性能來 說是沒有影響的棚亩，譯者注。

6.2 均勻負載分布（Uniform Load distribution）

Dynamo 通過一致性哈希將它的 key 空間進行 partition跪呈，保證負載分布的均勻性晶丘。 只要 key 的訪問不是極度不均衡，均勻的 key 分布就可以幫助我們實現(xiàn)負載的均衡分布。 特別地，即使出現(xiàn)了明顯的 key 訪問不平衡的情況，只要這些 key 足夠多，Dynamo 也能 保證這些 key 在后端節(jié)點之間是均衡分散的火诸。 本節(jié)介紹 Dynamo 中的負載不平衡問題秋秤，幾種解決策略及其對負載分布的影響。

為了研究負載不平衡（load imbalance）以及它和請求負載（request load）的相關(guān)性，我 們測量了 24 個小時內(nèi)每臺節(jié)點收到的請求量阿浓，以 30 分鐘作為一個點他嚷。在規(guī)定的時間內(nèi)， 只要節(jié)點收到的請求量偏離平均值的程度不超過一個閾值（例如搔扁，15%）爸舒，這臺節(jié)點就認為 是平衡的（inbalance）；否則稿蹲，就是不平衡的（out of balance）扭勉。

圖 6 展示了不平衡的節(jié)點所占的比例（imbalance ratio）：

image

圖 6 不平衡節(jié)點比例，及其負載（請求數(shù)）苛聘，X 軸一個刻度 30 分鐘

作為參考涂炎，圖中也畫出了這段期間系統(tǒng)的總負載（請求量）。從圖中可以看出设哗，隨著請求量 的上升唱捣，不平衡的比例在下降。例如网梢，低負載期間的不平衡比例高達 20%震缭，而高負載期間降 到了 10%。直觀上可以解釋：隨著負載（請求量）的上升战虏，大量的活躍 key 的訪問會均勻 的分發(fā)到節(jié)點拣宰，導致負載平衡分布。而低峰期間（請求量只有峰值的 1/8）烦感，只有很少的 活躍 key 訪問巡社，導致負載非常不平衡。

本節(jié)接下來介紹 Dynamo 的 partition scheme 是如何隨時間演進的手趣，以及它對負載分布的 影響晌该。

策略 1：每個節(jié)點 T 個隨機 token，按 token 值分散

這是生產(chǎn)環(huán)境最早部署的策略（在 4.2 節(jié)介紹過了）绿渣。

在這種策略中朝群，會給每個節(jié)點（從哈希空間）隨機分配 T 個 token怯晕。所有節(jié)點的 token 在哈锨逼裕空間中是有序的（按 token 值）。兩個相鄰的 token 定義一個范圍（ key range）舟茶。最后一個 token 和第一個 token 收尾相連。

因為 token 是隨機選擇的，因此范圍有大有小吧凉。當有節(jié)點加入或離開系統(tǒng)的時隧出，token 集合會變化，導致范圍也會跟著變阀捅。注意胀瞪，每個節(jié)點用來維護成員信息所需的空間隨著 系統(tǒng)中的節(jié)點數(shù)線性增長。

這種策略在使用過程中發(fā)現(xiàn)如下幾個問題饲鄙。

首先凄诞，一個新節(jié)點加入到系統(tǒng)后，需要從其他節(jié)點“偷”出它要用的 key range忍级。 這會導致那些需要將一部分 key range 移交給新節(jié)點的節(jié)點帆谍，掃描它們?nèi)康谋镜爻志么?儲，以過濾出所需的數(shù)據(jù)轴咱。在生產(chǎn)環(huán)境環(huán)境執(zhí)行這種掃描操作是很棘手的汛蝙，因為它 會占用大量磁盤 IO；為了不影響正常的請求處理朴肺，需要把這個任務(wù)放到后臺窖剑。 這要求我們只能將新節(jié)點加入集群的任務(wù)調(diào)到最低優(yōu)先級。這帶來的后果就是戈稿，節(jié)點上線的 速度非常慢西土，尤其是購物高峰季每天處理百萬請求時，上線一臺節(jié)點需要花費幾乎一整天時 間鞍盗。

第二需了，一個節(jié)點加入或離開系統(tǒng)時，很多節(jié)點負責的 key range 會發(fā)生變化橡疼，對應(yīng)的 Merkle tree 需要重新計算援所。對于生產(chǎn)環(huán)境來說，這也是一項不小的工作欣除。

最后住拭，由于 key range 的隨機性，無法快速地對整個 key 空間進行快照（snapshot）历帚。 這使得存檔（備份）工作變得復雜滔岳。在這種方案下，我們進行一次快照需要分別從所有節(jié) 點獲取 key挽牢，非常低效谱煤。

這種策略的根本問題出在：數(shù)據(jù)的 partition 和 placement 方案混在了一起（ intertwined）。例如禽拔，在某些場景下希望通過增加節(jié)點應(yīng)對請求量的上漲刘离，但是在這種方 案中室叉，無法做到添加新節(jié)點不影響數(shù)據(jù) partition。

理想情況下硫惕，應(yīng)該使用獨立的數(shù)據(jù) partition 和 placement 方案茧痕。為此，我們考察了下面的幾種方案恼除。

Strategy 2: 每個節(jié)點 T 個隨機 token踪旷，平均分散

這種策略將哈希空間分為 Q 個相同大小的 partition/range豁辉，每個節(jié)點分配 T 個 隨 機 token令野。Q 的選擇通常要滿足：Q >> N 和 Q >> S*T（>>：遠大于，譯者注）徽级， 其中 S 是系統(tǒng)中節(jié)點的數(shù)量气破。

在這種策略中，token 僅用于哈匣易罚空間的值映射到有序節(jié)點列表的過程堵幽，并不影響數(shù) 據(jù) partition。

一個 partition 會放在從該 partition 末尾開始沿順時針方向得到的前 N 個獨立節(jié)點弹澎。

image

圖 7 三種策略中 key 的 partition 和 placement朴下。N=3，A苦蒿、B殴胧、 C 是 key k1 的 preference list 中的三個獨立節(jié)點。陰影區(qū)域表示 preference list 是 [A,B,C] 的 key range佩迟，箭頭表示不同節(jié)點對應(yīng)的 token 位置

圖 7 展示了 N=3 時這種策略的示意圖团滥。

這種策略的主要優(yōu)點：

1. 將數(shù)據(jù)的 partition 和 placement 解耦
2. 提供了在運行時更改 placement 方案的能力

Strategy 3: 每個節(jié)點 Q/S 個 token, 平均分散

和策略 2 類似，策略 3 也將哈媳ㄇ浚空間等分為 Q 個 partition灸姊，而且 placement 從 partition 解耦。不同的是秉溉，每個節(jié)點會分配 Q/S 個 token力惯，其中 S 是系統(tǒng)中的節(jié)點 數(shù)量。

當一個節(jié)點離開時召嘶，它的 token 會隨機地分配給其他節(jié)點父晶，因此 Q/S 個 token 的特性 還是能成立。類似地弄跌，當一個節(jié)點加入系統(tǒng)時甲喝，它會從其他節(jié)點“偷”一些 token 過來，同 時保證 Q/S 特性仍然成立铛只。

幾種策略的性能對比

對一套 S=30埠胖，N=3 的 Dynamo 測試了以上三種策略糠溜。需要說明的是，公平地比較這三 種策略的性能是很難做到的押袍，因為它們有各自特殊的配置可以調(diào)優(yōu)诵冒。例如凯肋，策略 1 的負載 分布特性取決于 token 的數(shù)量（例如 T）谊惭，而策略 3 取決于 partition 的數(shù)量（例如 Q）。

一種比較公平的方式是：所有的策略都使用相同大小的空間存儲成員信息時侮东，測量它們的 負載分布傾斜度（skew in load distribution）圈盔。例如，策略 1 中每個節(jié)點需要為環(huán)上 的全部節(jié)點維護各自的 token 位置悄雅，而策略 3 中每個節(jié)點需要維護系統(tǒng)分配給每個節(jié)點的 partition 信息驱敲。

實驗中我們將通過改變相關(guān)的參數(shù)（T 和 Q）來評估這三種策略。測試每個節(jié)點需要維 護的成員信息的大锌硐小（size）不同時众眨，幾種策略的負載均衡效率。其中負載均衡效率（ load balancing efficiency）的定義是：每個節(jié)點平均處理的請求數(shù) / 負載最高的節(jié)點處 理的請求數(shù)容诬。

結(jié)果如圖 8 所示娩梨。

image

圖 8 三種策略的負載均衡效率對比，30 個幾點览徒，N=3狈定，每個節(jié)點維護相同大小的元數(shù)據(jù)

如圖所示，策略 3 取得了最好的負載均衡性能习蓬，策略 2 最差纽什。在某段較短的時期內(nèi)， 策略 2 充當了將線上的一些 Dynamo 從策略 1 遷移到策略 3 的過渡策略躲叼。

和 策略 1 相比芦缰，策略 3 性能更好，而且減少了每個節(jié)點所需維護的成員信息的大小枫慷。

雖然存儲這些成員信息并不會占用太多存儲让蕾，但是，節(jié)點通過 gossip 協(xié)議定期地將成員 信息發(fā)送給其他節(jié)點（gossip the membership information periodically）流礁，因此保 持這些信息越緊湊越好涕俗。

此外，策略 3 部署更加方便神帅，原因包括：

1. bootstrap 和恢復更快：因為 partition 范圍是固定的再姑，因此可以將其存放 到單獨的文件，這樣下次 relocation 的時候可以直接將整個文件發(fā)送給其他節(jié)點 （避免了為了定位特點的數(shù)據(jù)而進行的隨機訪問）找御。簡化了 bootstrap 和恢復的過程
2. 易于存檔：定期對數(shù)據(jù)集（dataset）進行存檔是 Amazon 存儲服務(wù)的硬性要求之一 元镀。在策略 3 中绍填，存檔過程會變得更容易，因為 partition 文件可以單獨存檔栖疑。作為對 比讨永，在策略 1 中，token 是隨機選取的遇革，存檔的時候需要從所有節(jié)點分別獲取它們存儲 的 key 信息卿闹，通常非常低效，速度也很慢萝快。

策略 3 的不足：變更節(jié)點成員時锻霎，需要 coordination，以保持平均分配所需的前提特 性（preserve the properties required of the assignment）揪漩。

6.3 版本分叉：什么時候旋恼？有多少？

我們已經(jīng)提到過奄容，Dynamo 是通過犧牲一些一致性（consistency）來換可用性（ availability）的冰更。要準確地理解不同類型的一致性失敗帶來的影響需要考慮很多因素：故障時 常（outage length）、失敗類型（type of failures）昂勒、組件可靠性蜀细、負載等等。 詳細地展示這些數(shù)據(jù)超出了本文范圍叁怪。但是审葬，本節(jié)可以提供一個很好的總結(jié)指標：一份真實 的生產(chǎn)環(huán)境里應(yīng)用看到的分叉版本數(shù)量（number of divergent versions seen by the application）。

有兩種情況會出現(xiàn)數(shù)據(jù)版本的分叉：

1. 遇到節(jié)點失敗奕谭、數(shù)據(jù)中心故障或網(wǎng)絡(luò)分裂等故障場景
2. 同一數(shù)據(jù)對象的大量并發(fā)寫操作涣觉，不同節(jié)點都在 coordinating 寫操作

從使用性（usability）和效率的角度，最好在任何時間都保證分叉的版本數(shù)盡量小血柳。

如果沖突的版本無法僅通過向量時鐘做句法調(diào)和（syntactically reconcile）官册，那就需要 將它們交給業(yè)務(wù)邏輯，執(zhí)行語義調(diào)和（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 會給服務(wù)引入額外的負擔膝宁，因此應(yīng)當越少越好。

我們采集了 24 小時內(nèi)返回到購物車應(yīng)用的版本數(shù)量根吁。結(jié)果顯示在這段時間內(nèi)员淫，99.94% 的請求看到的都是一個版本（無沖突）；0.00057% 的請求看到能 2 個击敌，0.00047% 能看 到 3 個介返，0.00009% 的能看到 4 個。這說明版本分叉的概率還是相當小的。

實驗還顯示圣蝎，導致分叉版本數(shù)量增多的并不是故障刃宵，而是并發(fā)寫數(shù)量的增加。并發(fā)寫數(shù)據(jù)上 升通常都是 busy robots（自動化客戶端程序）導致的徘公，極少是人（的應(yīng)用）導致的牲证。由于 涉及商業(yè)機密，在此不再就這一問題進行更深入的討論关面。

6.4 客戶端驅(qū)動或服務(wù)端驅(qū)動的 Coordination

第 5 節(jié)提到坦袍，Dynamo 有一個 request coordination 組件，利用狀態(tài)機處理收到的請求缭裆。

服務(wù)端驅(qū)動

客戶請求會通過負載均衡器均勻地分發(fā)給哈希環(huán)上的所有節(jié)點键闺。每個節(jié)點都可以作為讀請求 的 coordinator，而寫操作的 coordinator 必須由 key 的 preference list 里面的節(jié)點 才能充當澈驼。有這種限制是因為，preference list 中的這些節(jié)點被賦予了額外的職責：創(chuàng) 建一個新的版本戳（version stamp）筛武，在因果關(guān)系上包含被它的寫操作更新的版本缝其。注 意，如果 Dynamo 的版本化方案使用的是物理時間戳（physical timestamps）徘六，那任何節(jié) 點都可以 coordinate 寫操作内边。

客戶端驅(qū)動

另一中 coordinate request 的方式是：將狀態(tài)機前移到客戶端（move the state machine to the client nodes）。在這種方式中待锈，客戶端應(yīng)用使用庫（library）在本地執(zhí) 行請求 coordination漠其。每個客戶端定期地隨機選擇一個 Dynamo 節(jié)點，下載它的系統(tǒng)成員 狀態(tài)（Dynamo membership state）的當前視圖（current view）竿音。有了這個信息和屎，客戶端 就可以知道任何 key 對應(yīng)的 preference list 由哪些節(jié)點組成。

讀請求可以在客戶端節(jié)點（client node）coordinate春瞬，因此如果請求是被負載均衡器隨機 分給一個 Dynamo 節(jié)點柴信，那這種方式可以避免額外的網(wǎng)絡(luò)轉(zhuǎn)發(fā)跳數(shù)。寫操作或者轉(zhuǎn)發(fā)給 key 對應(yīng)的 preference list 里面的一個節(jié)點宽气，或者随常，如果使用的是基于時間戳的版本化方式 ，可以在本地 coordinate萄涯。

客戶端驅(qū)動的一個重要優(yōu)勢是：不再需要一個負載均衡器才能均勻地分發(fā)客戶負載绪氛。 在存儲節(jié)點上近乎均勻分布的 key，暗含了（implicitly guaranteed）負載的均勻分布涝影。

顯然枣察，這種方式的效率取決于客戶端側(cè)的成員信息的新鮮程度（how fresh the membership information）。當前袄琳，每個客戶端會每隔 10s 隨機地輪詢（poll）一個 Dynamo 節(jié)點询件， 獲取成員更新（membership updates）燃乍。這里選用 pull 而不是 push 模型是考慮前者在大 量客戶端的情況下可擴展性更好，而且相比于客戶端側(cè)宛琅，只需在服務(wù)端側(cè)維護很少的狀態(tài)信 息刻蟹。

然而，在最差的情況下嘿辟，客戶端的 membership 信息會有 10s 的臟數(shù)據(jù)舆瘪。 因此，如果客戶端檢測到它的成員表（membership table）過期了（例如红伦，當一些成員不可 達的時候）英古，它會立即更新它的成員信息。

性能對比

表 2 顯示了客戶端驅(qū)動比服務(wù)端驅(qū)動的 coordination 的性能提升昙读，測量時間為 24 個小時召调。

表 2 客戶端驅(qū)動和服務(wù)端驅(qū)動的 coordination 性能對比

image

從中可以看出，客戶端驅(qū)動的方式比服務(wù)端方式 P99.9 減少了至少 30ms蛮浑，平均值減少 了 3ms~4ms唠叛。

延遲降低是因為客戶端驅(qū)動的方式?jīng)]有了負載均衡器的開銷，而且減少了可能的將請求轉(zhuǎn)發(fā) 給一個隨機節(jié)點的網(wǎng)絡(luò)跳數(shù)沮稚。

另外從表中還可以看出艺沼，平均延遲遠遠小于 P99.9。這是因為 Dynamo 的存儲引擎緩存（ storage engine caches）和寫緩存（write buffer）命中率很高蕴掏。

另外障般，由于負載均衡器和網(wǎng)絡(luò)會給延遲引入額外的抖動性，因此 P99.9 的性能提升要比 均值更明顯盛杰。

6.5 平衡后臺和前臺任務(wù)

每個節(jié)點除了執(zhí)行正常的前臺 put/get 操作之外挽荡，還需要為副本同步和數(shù)據(jù)移交（ handoff）（由于 hinting 或添加/刪除節(jié)點）執(zhí)行不同種類的后臺任務(wù)。

在早期的生產(chǎn)系統(tǒng)中饶唤，這些后臺任務(wù)觸發(fā)了資源競爭問題募狂，影響了常規(guī)的 get/put 操 作性能。

因此祸穷，必須在保證常規(guī)的關(guān)鍵操作不受明顯影響的情況下雷滚，才允許執(zhí)行后臺任務(wù)需曾。為此，我 們將后臺任務(wù)關(guān)聯(lián)了一種許可控制機制（admission control mechanism）商源。每個后臺 任務(wù)通過這個控制器申請資源（例如數(shù)據(jù)庫）的運行時時間片（runtime slice）牡彻，這 些資源是在所有后臺任務(wù)之間共享的庄吼。對前臺任務(wù)性能的監(jiān)控會通過反饋機制改變后臺 任務(wù)可以使用的時間片數(shù)量。

許可控制器（admission controller）在執(zhí)行一個前臺 put/get 操作的時候渐行，會持續(xù) 監(jiān)控資源訪問的狀況殊轴。監(jiān)控的指標包括磁盤操作延遲、鎖競爭和事務(wù)超時導致的數(shù)據(jù)庫 訪問失敗次數(shù)我磁，以及請求隊列的等待時間。這些信息用于判斷在給定的時間窗口之內(nèi)的延遲 （或失斢舾薄）性能是否在可接受的范圍內(nèi)存谎。例如，后臺控制器檢查數(shù)據(jù)庫（過去 60s）的 P99 讀延遲是否離預設(shè)的閾值（例如 50ms）足夠近恰聘∏邕叮控制器正是根據(jù)這些對比信息為 前臺操作評估資源的可用性兼蕊，然后決定給后臺任務(wù)分配多少時間片惧所，因此利用反饋回路限制 了后臺任務(wù)的侵入性（intrusiveness ）斩祭。[4] 也研究了類似的后臺任務(wù)管理問題。

6.6 討論

本節(jié)總結(jié)我們在開發(fā)和維護 Dynamo 的過程中獲得的一些經(jīng)驗履因。

很多 Amazon 的內(nèi)部服務(wù)在過去的兩年都開始使用 Dynamo栅迄，它給應(yīng)用提供了非常高等級（ significant levels）的可用性。具體來說憋活，使用 Dynamo 的應(yīng)用，響應(yīng)成功率（不包括超 時辜梳？）達到了 99.9995%（applications have received successful responses (without timing out) for 99.9995% of its requests）冗美，并且到目前位置還沒有發(fā) 生過丟失數(shù)據(jù)的情況节预。

Dynamo 的主要優(yōu)勢是：給應(yīng)用提供了配置能力安拟，應(yīng)用可以根據(jù)自己的需求對 (N,R,W) 進 行調(diào)優(yōu)。

和流行的商業(yè)數(shù)據(jù)倉庫不同拙泽，Dynamo 將數(shù)據(jù)一致性和 reconciliation 邏輯開放給了開發(fā) 者。剛開始時荷荤，有人可能會覺得這樣會使應(yīng)用邏輯變得更復雜蕴纳。但從傳統(tǒng)來看（ historically），Amazon 平臺就是為高可用設(shè)計的喇潘，很多應(yīng)用在設(shè)計的時候就考慮了如 何處理可能出現(xiàn)的各種故障模式（failure modes）和不一致問題絮吵。對于這類應(yīng)用來說蹬敲， 適配 Dynamo 相對還是比較簡單的急波。對于想要使用 Dynamo 的新應(yīng)用澄暮，就需要首先花一些時 間做一些分析伸辟，在開發(fā)初期，選擇滿足業(yè)務(wù)需求的合適的沖突解決機制（conflict resolution mechanisms）静稻。

最后，Dynamo 采用了一種full membership model（完整成員模型）恰梢，在這種模型中， 每個節(jié)點都知道它的對端（peer）節(jié)點存儲哪些數(shù)據(jù)摧茴。在實現(xiàn)中苛白，每個節(jié)點要主動將完整路 由表 gossip 給系統(tǒng)內(nèi)的其他節(jié)點。這個模型對幾百臺、上千臺節(jié)點的規(guī)模很適用薇芝。但 對于上萬臺節(jié)點的規(guī)模就不適應(yīng)了，因為維護這么大一個系統(tǒng)的路由表開銷會大大增加耍贾。 但是优床，可以通過向 Dynamo 引入hierarchical extensions（層級擴展）來解決這個限制。 O(1) 復雜度的的動態(tài)哈希樹系統(tǒng)（DHS）（例如 [14]）解決的就是這種問題移层。

this problem is actively addressed by O(1) DHT systems(e.g., [14]).

7. 結(jié)束語

本文介紹了 Dynamo，一個高可用频蛔、高可擴展的數(shù)據(jù)倉庫（data store），在 Amazon 電商 平臺用于存儲許多核心服務(wù)的狀態(tài)數(shù)據(jù)三圆。

Dynamo 提供了期望的可用性和性能等級，可以正確地處理服務(wù)器故障路媚、數(shù)據(jù)中心故障和網(wǎng) 絡(luò)分裂。

Dynamo 可以增量擴展弛矛，允許服務(wù)所有者根據(jù)負載高低動態(tài)的對 Dynamo 系統(tǒng)進行擴縮容丈氓； 允許服務(wù)所有者根據(jù)他們的性能湾笛、持久性和一致性 SLA 需求蓖墅，通過調(diào)優(yōu) NRW 三個參 數(shù)來定制化它們的存儲系統(tǒng)。

過去幾年 Dynamo 在生產(chǎn)環(huán)境的實踐表明：一些去中心化技術(shù)結(jié)合起來贪壳，可以提供一個高度 可用的系統(tǒng)。這種在極具挑戰(zhàn)性的應(yīng)用環(huán)境的成功也表明蚂且，最終一致性存儲系統(tǒng)可以作為 高可用應(yīng)用（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.

參考文獻

1. Adya, et al. Farsite: federated, available, and reliable storage for an incompletely trusted environment. SIGOPS 2002
2. Bernstein, P.A., et al. An algorithm for concurrency control and recovery in replicated distributed databases. ACM Trans. on Database Systems, 1984
3. Chang, et al. Bigtable: a distributed storage system for structured data. In Proceedings of the 7th Conference on USENIX Symposium on Operating Systems Design and Implementation, 2006
4. Douceur, et al. Process-based regulation of low-importance processes. SIGOPS 2000
5. Fox, et al. Cluster-based scalable network services. SOSP, 1997
6. Ghemawat, et al. The Google file system. SOSP, 2003
7. Gray, et al. The dangers of replication and a solution. SIGMOD 1996
8. Gupta, et al. On scalable and efficient distributed failure detectors. In Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing. 2001
9. Kubiatowicz, et al. OceanStore: an architecture for global-scale persistent storage. SIGARCH Comput. Archit. News, 2000
10. Karger, et al. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. STOC 1997
11. Lindsay, et al. “Notes on Distributed Databases”, Research Report RJ2571(33471), IBM Research, 1979
12. Lamport, L. Time, clocks, and the ordering of events in a distributed system. ACM Communications, 1978
13. Merkle, R. A digital signature based on a conventional encryption function. Proceedings of CRYPTO, 1988
14. Ramasubramanian, et al. Beehive: O(1)lookup performance for power-law query distributions in peer-topeer overlays. In Proceedings of the 1st Conference on Symposium on Networked Systems Design and Implementation, , 2004
15. Reiher, et al. Resolving file conflicts in the Ficus file system. In Proceedings of the USENIX Summer 1994 Technical Conference, 1994
16. Rowstron, et al. Pastry: Scalable, decentralized object location and routing for large-scale peerto- peer systems. Proceedings of Middleware, 2001.
17. Rowstron, et al. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. Proceedings of Symposium on Operating Systems Principles, 2001
18. Saito, et al. FAB: building distributed enterprise disk arrays from commodity components. SIGOPS 2004
19. Satyanarayanan, et al. Coda: A Resilient Distributed File System. IEEE Workshop on Workstation Operating Systems, 1987.
20. Stoica, et al. Chord: A scalable peer-to-peer lookup service for internet applications. SIGCOMM 2001
21. Terry, et al. Managing update conflicts in Bayou, a weakly connected replicated storage system. SOSP 1995
22. Thomas. A majority consensus approach to concurrency control for multiple copy databases. ACM Transactions on Database Systems, 1979.
23. Weatherspoon, et al. Antiquity: exploiting a secure log for wide-area distributed storage. SIGOPS 2007
24. Welsh, et al. SEDA: an architecture for well-conditioned, scalable internet services. SOSP 2001