Dynamo：亚马逊的高可用键值存储
目錄
? ? ? ??1. 簡介
? ? ? ? 2. 背景
? ? ? ??3.?相關工作
? ? ? ??4.?系統(tǒng)結構
? ? ? ??5.?實現(xiàn)
? ? ? ??6.?經(jīng)驗和教訓
? ? ? ??7.?結論
Dynamo：亞馬遜的高可用鍵值存儲
摘要：大規(guī)模的可靠性是我們在?Amazon.com?面臨的最大挑戰(zhàn)之一，它是世界上最大的電子商務運營之一；即使是最輕微的停機也會帶來嚴重的財務后果，并影響客戶的信任。Amazon.com?平臺為世界各地的許多網(wǎng)站提供服務，它是在位于世界各地許多數(shù)據(jù)中心的數(shù)萬臺服務器和網(wǎng)絡組件的基礎架構之上構建的。在這種規(guī)模下，大大小小的組件不斷地發(fā)生故障，而面對這些故障時管理持久狀態(tài)的方式驅動著軟件系統(tǒng)的可靠性和可伸縮性。
本文介紹了?Dynamo 的設計和實現(xiàn)，Dynamo 是一個高度可用的鍵值存儲系統(tǒng)，亞馬遜的一些核心服務使用它來提供?"永遠在線"?的體驗。為了達到這種可用性水平，Dynamo 在某些故障情況下犧牲了一致性。它廣泛使用對象版本控制和應用程序輔助的沖突解決方式，為開發(fā)人員提供了一個新穎的接口。
?
1. 簡介
處理由數(shù)百萬個組件組成的基礎架構中的故障是我們正常的操作模式；在任何給定時間，總是有少量的服務器和網(wǎng)絡組件出現(xiàn)故障。因此，亞馬遜的軟件系統(tǒng)需要以一種將故障處理視為正常情況而不影響可用性或性能的方式來構建。
為了滿足可靠性和可擴展性需求，亞馬遜開發(fā)了多種存儲技術，其中最著名的可能是亞馬遜簡單存儲服務（也可在亞馬遜之外獲得，Amazon Simple?Storage Service?稱為亞馬遜?S3）。本文介紹了?Dynamo 的設計和實現(xiàn)，Dynamo 是為亞馬遜平臺構建的另一個高度可用和可擴展的分布式數(shù)據(jù)存儲。Dynamo 用于管理具有非常高的可靠性要求并且需要嚴格控制可用性、一致性、成本效益和性能之間權衡的服務狀態(tài)。亞馬遜的平臺有一套非常多樣化的應用程序，具有不同的存儲要求。一組選定的應用程序需要一種足夠靈活的存儲技術，以便應用程序設計人員能夠根據(jù)這些權衡來適當?shù)嘏渲盟麄兊臄?shù)據(jù)存儲，從而以最經(jīng)濟高效的方式實現(xiàn)高可用性和有保證的性能。
亞馬遜的平臺上有許多服務只需要對數(shù)據(jù)存儲進行主鍵訪問。對于許多服務，例如那些提供暢銷書列表、購物車、客戶偏好、會話管理、銷售排名和產(chǎn)品目錄的服務，使用關系數(shù)據(jù)庫的常見模式會導致效率低下，并限制規(guī)模和可用性。Dynamo 提供了一個簡單的主鍵接口來滿足這些應用程序的要求。
Dynamo?綜合了一些眾所周知的技術來實現(xiàn)可伸縮性和可用性：使用一致性哈希算法對數(shù)據(jù)進行分區(qū)和復制，并且通過對象版本控制來促進一致性。通過類似仲裁的技術和去中心化的副本同步協(xié)議來維護更新過程中副本之間的一致性。Dynamo?采用基于?gossip 的分布式故障檢測和成員協(xié)議。Dynamo?是一個完全去中心化的系統(tǒng)，只需要很少的人工管理。可以在?Dynamo?中添加和刪除存儲節(jié)點，而不需要任何手動分區(qū)或重新分配。
過去一年，Dynamo 一直是亞馬遜電子商務平臺許多核心服務的底層存儲技術。在繁忙的假日購物季節(jié)，它能夠高效地擴展到極端峰值負載，而沒有任何停機時間。例如，維護購物車的服務（購物車服務）為數(shù)千萬個請求提供服務，這些請求在一天內(nèi)導致超過?300?萬次結帳，而管理會話狀態(tài)的服務處理了數(shù)十萬個并發(fā)活動的會話。
這項工作對研究界的主要貢獻是評估如何將不同的技術結合起來，以提供一個高度可用的系統(tǒng)。它表明，最終一致的存儲系統(tǒng)可以用于要求苛刻的應用程序的生產(chǎn)中。它還提供了對這些技術的調(diào)整，以滿足對性能要求非常嚴格的生產(chǎn)系統(tǒng)的要求。
論文結構如下。第?2?節(jié)介紹了背景，第?3?節(jié)介紹了相關工作。第?4?節(jié)介紹了系統(tǒng)設計，第?5?節(jié)描述了實現(xiàn)。第?6?節(jié)詳細介紹了在生產(chǎn)中運行?Dynamo 獲得的經(jīng)驗和見解，第?7?節(jié)總結了本文。本文中有許多地方可能需要額外的信息，但保護亞馬遜的商業(yè)利益需要我們減少一些細節(jié)。因此，第?6?節(jié)中的數(shù)據(jù)中心內(nèi)部和數(shù)據(jù)中心之間的延遲、第?6.2?節(jié)中的絕對請求率以及第?6.3?節(jié)中的停機時間和工作負載是通過聚合度量而不是絕對細節(jié)來提供的。
?
?
2. 背景
亞馬遜的電子商務平臺由數(shù)百項服務組成，這些服務協(xié)同工作，提供從推薦、訂單執(zhí)行到欺詐檢測等功能。每個服務都通過一個明確明確定義的接口公開，并可通過網(wǎng)絡訪問。這些服務托管在一個基礎架構中，該基礎架構由遍布全球許多數(shù)據(jù)中心的數(shù)萬臺服務器組成。這些服務中的一些是無狀態(tài)的（即聚合來自其他服務的響應的服務），一些是有狀態(tài)的（即通過對存儲在持久存儲中的狀態(tài)執(zhí)行業(yè)務邏輯來生成響應的服務）。
傳統(tǒng)上，生產(chǎn)系統(tǒng)將狀態(tài)存儲在關系數(shù)據(jù)庫中。然而，對于許多更常見的狀態(tài)持久化使用模式，關系數(shù)據(jù)庫是一個遠非理想的解決方案。這些服務中的大多數(shù)只按主鍵存儲和檢索數(shù)據(jù)，不需要關系數(shù)據(jù)庫管理系統(tǒng)提供的復雜查詢和管理功能。這種多余的功能需要昂貴的硬件和高技能人員來操作，這使得它成為一種非常低效的解決方案。此外，可用的復制技術有限，通常選擇一致性而不是可用性。盡管近年來取得了許多進展，但擴展數(shù)據(jù)庫或使用智能分區(qū)方案進行負載平衡仍然不容易。
本文描述了?Dynamo，一種高度可用的數(shù)據(jù)存儲技術，解決了這些重要服務類別的需求。Dynamo有一個簡單的鍵/值接口，具有明確定義的一致性窗口，高度可用，資源使用高效，并有一個簡單的橫向擴展方案來解決數(shù)據(jù)集大小或請求速率的增長。每個使用?Dynamo 的服務都運行自己的?Dynamo 實例。
?
?
2.1?系統(tǒng)假設和要求
此類服務的存儲系統(tǒng)有以下要求：
查詢模型：對由關鍵字唯一標識的數(shù)據(jù)項的簡單讀寫操作。狀態(tài)存儲為由唯一鍵標識的二進制對象（即?Blobs）。沒有跨越多個數(shù)據(jù)項的操作，也不需要關系模式。這一要求是基于這樣的觀察，即亞馬遜的很大一部分服務可以使用這個簡單的查詢模型，并且不需要任何關系模式。Dynamo 面向需要存儲相對較小（通常小于1 MB）的對象的應用程序。
ACID?屬性：ACID（原子性、一致性、隔離性、持久性）是一組保證數(shù)據(jù)庫事務得到可靠處理的屬性。在數(shù)據(jù)庫環(huán)境中，對數(shù)據(jù)的單個邏輯操作稱為事務。亞馬遜的經(jīng)驗表明，提供ACID?保證的數(shù)據(jù)存儲往往可用性較差。這已經(jīng)得到業(yè)界和學術界的廣泛認可。Dynamo 的目標是一致性較弱的應用程序（ACID?中的?"C"）。Dynamo 不提供任何隔離保證，只允許單鍵更新。
效率：系統(tǒng)需要在商用硬件基礎設施上運行。在亞馬遜的平臺上，服務有嚴格的延遲要求，通常在分布的?99.9%?進行測量。鑒于狀態(tài)訪問在服務操作中起著至關重要的作用，存儲系統(tǒng)必須能夠滿足如此嚴格的服務層協(xié)議（參見下文第?2.2?節(jié)）。服務必須能夠配置?Dynamo，使其始終達到延遲和吞吐量要求。權衡是在性能、成本效率、可用性和耐用性保證方面。
其他假設：Dynamo?只被亞馬遜內(nèi)部服務使用。其操作環(huán)境被認為是友好的，并且沒有諸如認證和授權的安全相關要求。此外，由于每項服務都使用其獨特的?Dynamo 實例，其最初的設計目標是多達數(shù)百臺存儲主機的規(guī)模。我們將在后面的章節(jié)中討論?Dynamo 的可伸縮性限制和可能的可伸縮性相關擴展。
?
?
2.2?服務層協(xié)議
為了保證應用程序能夠在有限的時間內(nèi)交付其功能，平臺中的每個依賴項都需要以更嚴格的限制來交付其功能。客戶和服務簽訂服務層協(xié)議，這是一種正式協(xié)商的合同，客戶和服務就幾個與系統(tǒng)相關的特征達成一致，其中最突出的包括客戶對特定應用編程接口的預期請求速率分布以及在這些條件下的預期服務延遲。簡單?SLA?的一個例子是一個服務，它保證它將在?300?毫秒內(nèi)對其?99.9%?的請求提供響應，以達到每秒?500?個請求的峰值。
在亞馬遜去中心化的面向服務的基礎設施中，服務層協(xié)議扮演著重要的角色。例如，對一個電子商務站點的頁面請求通常需要呈現(xiàn)引擎通過向?150?多個服務發(fā)送請求來構造其響應。這些服務通常有多個依賴項，這些依賴項通常是其他服務，因此應用程序的調(diào)用圖有多個級別并不罕見。為了確保頁面呈現(xiàn)引擎能夠在頁面交付上保持明確的界限，調(diào)用鏈中的每個服務都必須遵守其性能契約。
圖?1?顯示了亞馬遜平臺架構的抽象視圖，其中動態(tài)網(wǎng)頁內(nèi)容是由頁面呈現(xiàn)組件生成的，而頁面呈現(xiàn)組件又會查詢許多其他服務。服務可以使用不同的數(shù)據(jù)存儲來管理其狀態(tài)，并且這些數(shù)據(jù)存儲只能在其服務邊界內(nèi)訪問（these?data stores are only accessible within its service boundaries）。一些服務充當聚合器（Aggregators），通過使用其他幾個服務來產(chǎn)生復合響應。通常，聚合器服務是無狀態(tài)的，盡管它們使用大量的緩存。
行業(yè)中形成面向性能的服務層協(xié)議的一種常見方法是使用平均值、中位數(shù)和預期方差來描述它。在亞馬遜，我們發(fā)現(xiàn)，如果目標是建立一個所有客戶都有良好體驗的系統(tǒng)，而不僅僅是大多數(shù)客戶，那么這些指標就不夠好。例如，如果使用廣泛的個性化技術，那么客戶歷史較早的請求更多的處理，這會影響高端分布的性能。以平均或中位響應時間表示的服務層協(xié)議不能解決這一重要客戶群體的問題。為了解決這個問題，在亞馬遜，服務層協(xié)議是在?99.9%?的分布中被傳遞和被測量的。99.9%?甚至更高百分比的選擇是基于成本效益分析，該分析表明成本顯著增加，從而大大提高了性能。亞馬遜生產(chǎn)系統(tǒng)的經(jīng)驗表明，與那些滿足基于平均值或中間值定義的服務層協(xié)議的系統(tǒng)相比，這種方法提供了更好的整體體驗。
在這篇文章中，有許多對這?99.9%?分布的引用，這反映了亞馬遜工程師從客戶體驗的角度對性能的不懈關注。許多論文都是關于平均值的，所以為了便于比較，這些都包含在內(nèi)了。然而，亞馬遜的工程和優(yōu)化工作并不關注平均值。一些技術，如寫協(xié)調(diào)器（write coordinators）的負載平衡選擇，純粹是為了控制?99.9%?的性能。
存儲系統(tǒng)通常在建立服務的服務層協(xié)議中起著重要的作用，尤其是在業(yè)務邏輯相對輕量級的情況下，就像許多亞馬遜服務一樣。然后，狀態(tài)管理成為服務的服務層協(xié)議的主要組成部分。?Dynamo 的主要設計考慮之一是讓服務控制它們的系統(tǒng)屬性，比如持久性和一致性，并讓服務在功能、性能和成本效益之間進行權衡。
?
?
2.3?設計考慮
商業(yè)系統(tǒng)中使用的數(shù)據(jù)復制算法傳統(tǒng)上執(zhí)行同步副本協(xié)調(diào)（synchronous replica coordination），以便提供高度一致的數(shù)據(jù)訪問接口。為了達到這種程度的一致性，這些算法被迫在某些故障情況下權衡數(shù)據(jù)的可用性。例如，不是處理答案正確性/不確定性，而是在完全確定答案是正確的之前，數(shù)據(jù)是不可用的。從早期的復制數(shù)據(jù)庫工作來看，眾所周知，當處理網(wǎng)絡故障的可能性時，強一致性和高數(shù)據(jù)可用性不能同時實現(xiàn)。因此，系統(tǒng)和應用程序需要知道在什么條件下可以實現(xiàn)哪些特性。
對于容易出現(xiàn)服務器和網(wǎng)絡故障的系統(tǒng)，可以通過使用樂觀復制技術來提高可用性，在樂觀復制技術中，允許將更改傳播到后臺的副本，并且允許并發(fā)、斷開連接的工作。這種方法的挑戰(zhàn)在于，它可能導致必須被檢測和被解決的沖突性的變更（The challenge?with this?approach is that it can lead to conflicting changes which?must be detected and resolved）。這個解決沖突的過程引入了兩個問題：什么時候解決，誰來解決。Dynamo 被設計成一個最終一致的數(shù)據(jù)存儲；也就是說，所有更新最終都會到達所有副本。
一個重要的設計考慮是決定何時執(zhí)行解決更新沖突的過程，即沖突是否應該在讀取或寫入期間解決。許多傳統(tǒng)數(shù)據(jù)存儲在寫入期間執(zhí)行沖突解決，并保持簡單的讀取復雜性。在這種系統(tǒng)中，如果數(shù)據(jù)存儲在給定時間不能到達所有（或大部分）副本，則寫入可能會被拒絕。另一方面，Dynamo 的目標是?"始終可寫"?數(shù)據(jù)存儲的設計空間（即，對寫入高度可用的數(shù)據(jù)存儲）。對于許多亞馬遜服務來說，拒絕客戶更新可能會導致糟糕的客戶體驗。例如，購物車服務必須允許客戶在網(wǎng)絡和服務器出現(xiàn)故障的情況下在購物車中添加和刪除商品。這一要求迫使我們將沖突解決的復雜性推到讀取過程上，以確保寫入永遠不會被拒絕。（何時解決）
下一個設計選擇是由誰來執(zhí)行沖突解決過程。這可以通過數(shù)據(jù)存儲或應用程序來完成。如果沖突解決是由數(shù)據(jù)存儲完成的，那么它的選擇是相當有限的。在這種情況下，數(shù)據(jù)存儲只能使用簡單的策略來解決沖突的更新，例如?"最后寫入成功"。另一方面，由于應用程序知道數(shù)據(jù)模式，它可以決定最適合其客戶體驗的沖突解決方法。例如，維護客戶購物車的應用程序可以選擇?"合并"?沖突的版本，并返回一個統(tǒng)一的購物車。盡管有這種靈活性，一些應用程序開發(fā)人員可能不想編寫他們自己的沖突解決機制，而是選擇將其下推到數(shù)據(jù)存儲，而數(shù)據(jù)存儲又選擇一個簡單的策略，如?"最后一次寫入獲勝"。（由誰解決）
設計中包含的其他關鍵原則有：
增量可擴展性：Dynamo 應該能夠一次橫向擴展一個存儲主機（以下簡稱為?"節(jié)點"），對系統(tǒng)操作員和系統(tǒng)本身的影響最小。
對稱性：Dynamo中的每個節(jié)點都應該和它的對等節(jié)點有相同的一套職責；不應該有一個或多個特殊的節(jié)點承擔特殊的角色或額外的責任。根據(jù)我們的經(jīng)驗，對稱簡化了系統(tǒng)配置和維護的過程。
去中心化：對稱性的延伸，設計應該支持去中心化的點對點技術，而不是集中控制。過去，集中控制導致停機，目標是盡可能避免停機。這導致了一個更簡單、更可擴展、更可用的系統(tǒng)。
異構性：系統(tǒng)需要能夠在其運行的基礎設施中利用異構性。例如，工作分配必須與各個服務器的能力成比例。這對于添加具有更高容量的新節(jié)點而不必一次升級所有主機是至關重要的。
?
?
3.?相關工作
3.1?P2P系統(tǒng)
有幾個?P2P?系統(tǒng)已經(jīng)研究了數(shù)據(jù)存儲和分發(fā)的問題。第一代?P2P?系統(tǒng)，如?Freenet?和Gnutella，主要用作文件共享系統(tǒng)。這些是非結構化?P2P?網(wǎng)絡的例子，其中對等體之間的覆蓋鏈路是任意建立的。在這些網(wǎng)絡中，搜索查詢通常會在網(wǎng)絡中泛濫，以找到盡可能多的共享數(shù)據(jù)的對等點。P2P?系統(tǒng)發(fā)展到下一代，成為眾所周知的結構化?P2P?網(wǎng)絡。這些網(wǎng)絡采用全球一致的協(xié)議，以確保任何節(jié)點都可以高效地將搜索查詢路由到擁有所需數(shù)據(jù)的對等點。像?Pastry?和和?Chord?這樣的系統(tǒng)使用路由機制來確保查詢可以在有限的跳數(shù)內(nèi)得到回答。為了減少由多跳路由引入的額外延遲，一些?P2P?系統(tǒng)采用?O(1) 路由，其中每個對等體在本地維護足夠的路由信息，使得它可以在恒定的跳數(shù)內(nèi)將請求（訪問數(shù)據(jù)項）路由到適當?shù)膶Φ润w。
各種存儲系統(tǒng)，如?Oceanstore?和?PAST?是建立在這些路由覆蓋的基礎上。Oceanstore?提供了一種全局、事務性、持久性存儲服務，支持對廣泛復制的數(shù)據(jù)進行序列化更新。為了允許并發(fā)更新，同時避免廣域鎖定固有的許多問題，它使用了基于沖突解決的更新模型。有的系統(tǒng)中引入了沖突解決，以減少事務中止的次數(shù)。Oceanstore?通過處理一系列更新來解決沖突，在它們之間選擇一個總順序，然后以該順序自動應用它們。它是為在不受信任的基礎架構上復制數(shù)據(jù)的環(huán)境而構建的。相比之下，PAST?為持久和不可變的對象提供了一個簡單的抽象層。它假設應用程序可以在其上構建必要的存儲語義（例如可變文件）。
?
?
3.2?分布式文件系統(tǒng)和數(shù)據(jù)庫
在文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)社區(qū)中，為了性能、可用性和持久性而分發(fā)數(shù)據(jù)已經(jīng)得到了廣泛的研究。與只支持扁平的名稱空間（flat namespaces）的?P2P?存儲系統(tǒng)相比，分布式文件系統(tǒng)通常支持分層名稱空間。像?Fixes?和?Coda?這樣的系統(tǒng)以犧牲一致性為代價來復制文件以獲得高可用性。更新沖突通常使用專門的沖突解決程序來管理。Farsite?系統(tǒng)是一個分布式文件系統(tǒng)，不像?NFS?那樣使用任何集中式服務器。Farsite?使用復制實現(xiàn)高可用性和可擴展性。GFS 是另一個分布式文件系統(tǒng)，用于托管谷歌內(nèi)部應用程序的狀態(tài)。GFS?使用一個簡單的設計，只有一個?master?來托管整個元數(shù)據(jù)，數(shù)據(jù)被分成塊并存儲在塊服務器中。Bayou?是一個分布式關系數(shù)據(jù)庫系統(tǒng)，它允許斷開連接的操作，并提供最終的數(shù)據(jù)一致性。
在這些系統(tǒng)中，Bayou、Coda?和?Ficus?允許斷開連接的操作，并對網(wǎng)絡分區(qū)和中斷等問題具有彈性。這些系統(tǒng)在沖突解決程序上有所不同。例如，Coda?和?Ficus?執(zhí)行系統(tǒng)級沖突解決，Bayou?允許應用程序級解決。然而，所有這些都保證了最終的一致性。與這些系統(tǒng)類似，?Dynamo 允許讀寫操作甚至在網(wǎng)絡分區(qū)期間繼續(xù)進行，并使用不同的沖突解決機制來解決更新的沖突。像?FAB?這樣的分布式塊存儲系統(tǒng)將大型對象分割成較小的塊，并以高度可用的方式存儲每個塊。與這些系統(tǒng)相比，鍵值存儲在這種情況下更合適，因為：(a) 它旨在存儲相對較小的對象（大小< 1M）。?(b) 鍵值存儲更容易根據(jù)每個應用程序進行配置。Antiquity?是一個廣域分布式存儲系統(tǒng)，旨在處理多個服務器故障。它使用安全日志（secure log）來保持數(shù)據(jù)完整性，在多臺服務器上復制每個日志以獲得持久性，并使用拜占庭容錯協(xié)議來確保數(shù)據(jù)一致性。與?Antiquity?相比，Dynamo 不關注數(shù)據(jù)完整性和安全性問題，而是為可信環(huán)境而構建。Bigtable?是一個用于管理結構化數(shù)據(jù)的分布式存儲系統(tǒng)。它維護一個稀疏的多維排序?map，并允許應用程序使用多個屬性訪問它們的數(shù)據(jù)。與?Bigtable?相比，Dynamo?的目標應用程序只需要鍵/值訪問，主要關注高可用性，即使在網(wǎng)絡分區(qū)或服務器出現(xiàn)故障時，更新也不會被拒絕。
傳統(tǒng)的復制關系數(shù)據(jù)庫系統(tǒng)關注于保證復制數(shù)據(jù)的強一致性問題。雖然強大的一致性為應用程序作者提供了一個方便的編程模型，但這些系統(tǒng)在可擴展性和可用性方面受到限制。這些系統(tǒng)不能處理網(wǎng)絡分區(qū)，因為它們通常提供強大的一致性保證。
?
?
3.3?討論
Dynamo 在目標要求方面不同于上述去中心化存儲系統(tǒng)。首先，Dynamo 主要面向那些需要?"始終可寫"?數(shù)據(jù)存儲的應用程序，在這些應用程序中，不會有因失敗或并發(fā)寫入而被拒絕的更新。這是許多亞馬遜應用程序的一個關鍵要求。其次，如前所述，Dynamo 是為單個管理域內(nèi)的基礎架構而構建的，其中所有節(jié)點都被認為是可信的。第三，使用?Dynamo?的應用程序不需要支持分層名稱空間（許多文件系統(tǒng)中的一種規(guī)范）或復雜的關系模式（由傳統(tǒng)數(shù)據(jù)庫支持）。第四，Dynamo 是為延遲敏感的應用程序而構建的，這些應用程序需要在數(shù)百毫秒內(nèi)執(zhí)行至少?99.9%?的讀寫操作。為了滿足這些嚴格的延遲要求，我們必須避免通過多個節(jié)點路由請求（這是?Chord?和?Pastry?等幾個分布式哈希表系統(tǒng)采用的典型設計）。這是因為多跳路由增加了響應時間的可變性，從而增加了更高百分比的延遲。Dynamo 可以被描述為零跳分布式哈希表（Dynamo can be?characterized as a zero-hop DHT），其中每個節(jié)點在本地維護足夠的路由信息，以將請求直接路由到適當?shù)墓?jié)點。
?
?
4.?系統(tǒng)結構
需要在生產(chǎn)環(huán)境中運行的存儲系統(tǒng)的體系結構非常復雜。除了實際的數(shù)據(jù)持久性組件之外，系統(tǒng)還需要針對負載均衡、成員資格和故障檢測、故障恢復、副本同步、過載處理、狀態(tài)轉移、并發(fā)和作業(yè)調(diào)度、請求編組、請求路由、系統(tǒng)監(jiān)控和報警以及配置管理等方面提供可擴展且強健的解決方案。描述每一個解決方案的細節(jié)是不可能的，所以本文主要關注?Dynamo 中使用的核心分布式系統(tǒng)技術：分區(qū)、復制、版本控制、成員資格、故障處理和擴展。表 1 總結了 Dynamo 使用的技術及其各自的優(yōu)勢。
?
4.1?系統(tǒng)接口
Dynamo 通過一個簡單的接口存儲與一個?key 相關聯(lián)的對象；它公開了兩個操作：get() 和put() 。get(key) 操作在存儲系統(tǒng)中定位與?key 相關聯(lián)的對象副本，并返回單個對象或具有沖突版本的對象列表以及上下文。put(key, context, object) 操作根據(jù)關聯(lián)的?key 確定對象的副本應該放在哪里，并將副本寫入磁盤。context?對調(diào)用方不透明的關于對象的系統(tǒng)元數(shù)據(jù)進行編碼，并包括諸如對象版本等信息。上下文信息與對象一起存儲，以便系統(tǒng)可以驗證?put?請求中提供的上下文對象的有效性。
Dynamo 將調(diào)用者提供的?key 和對象都視為不透明的字節(jié)數(shù)組。它對?key 應用?MD5?哈希來生成?128?位標識符，該標識符用于確定負責提供?key 的存儲節(jié)點。
?
?
4.2?分區(qū)算法
Dynamo 的關鍵設計要求之一是它必須逐步擴展。這需要一種在系統(tǒng)中的一組節(jié)點（即存儲主機）上動態(tài)劃分數(shù)據(jù)的機制。Dynamo 的分區(qū)方案依靠一致性哈希算法在多個存儲主機之間分配負載。在一致性哈希算法中，哈希函數(shù)的輸出范圍被視為固定的循環(huán)空間或?"環(huán)"（即最大的哈希值繞到最小的哈希值）。系統(tǒng)中的每個節(jié)點在這個空間內(nèi)被分配一個隨機值，代表它在環(huán)上的?"位置"。由?key 標識的每個數(shù)據(jù)項通過哈希數(shù)據(jù)項的?key 以產(chǎn)生其在環(huán)上的位置而被分配給一個節(jié)點，然后順時針遍歷環(huán)以找到位置大于該項的位置的第一個節(jié)點。因此，每個節(jié)點對其與環(huán)上的前一個節(jié)點之間的環(huán)中的區(qū)域負責。一致性哈希的主要優(yōu)點是，一個節(jié)點的離開或到達只影響它的近鄰，而其他節(jié)點不受影響。
基本的一致性哈希算法帶來了一些挑戰(zhàn)。首先，環(huán)上每個節(jié)點的隨機位置分配導致數(shù)據(jù)和負載分布不均勻。第二，基本算法忽略了節(jié)點性能的異質性（不同結點處理數(shù)據(jù)的能力不同）。為了解決這些問題，Dynamo 使用了一致性哈希算法的變體：不是將一個節(jié)點映射到圓中的一個點，而是將每個節(jié)點分配到環(huán)中的多個點。為此，Dynamo 使用了?"虛擬節(jié)點"?的概念。虛擬節(jié)點看起來像系統(tǒng)中的單個節(jié)點，但是每個節(jié)點可以負責多個虛擬節(jié)點。實際上，當一個新節(jié)點被添加到系統(tǒng)中時，它會在環(huán)中被分配多個位置（此后稱為?"tokens"）。第?6?節(jié)討論了微調(diào)?Dynamo 分區(qū)方案的過程。使用虛擬節(jié)點有以下優(yōu)點：
(1) 如果某個節(jié)點變得不可用（由于故障或日常維護），則該節(jié)點處理的負載將平均分布在剩余的可用節(jié)點上。
(2) 當一個節(jié)點再次變得可用時，或者一個新節(jié)點被添加到系統(tǒng)中時，新的可用節(jié)點從每個其他可用節(jié)點接受大致相等的負載量。
(3) 考慮到物理基礎架構的異構性，節(jié)點負責的虛擬節(jié)點數(shù)量可以根據(jù)其容量來決定。
?
?
4.3?復制
為了實現(xiàn)高可用性和持久性，Dynamo 在多臺主機上復制其數(shù)據(jù)。每個數(shù)據(jù)項在?N?個主機上復制，其中?N?是一個?"每個實例"?配置的參數(shù)。每個密鑰?k?被分配給一個協(xié)調(diào)器節(jié)點（在前一節(jié)中有描述）。協(xié)調(diào)器負責復制其范圍內(nèi)的數(shù)據(jù)項。除了在本地存儲其范圍內(nèi)的每個密鑰之外，協(xié)調(diào)器還在環(huán)中的?N-1?個順時針后續(xù)節(jié)點上復制這些密鑰。這導致一個系統(tǒng)，其中每個節(jié)點負責它和它的第?N?個前身之間的環(huán)的區(qū)域。在圖?2?中，節(jié)點?B?除了在本地存儲密鑰?k?之外，還在節(jié)點?C?和節(jié)點?D?復制密鑰?k。節(jié)點?D?將存儲屬于范圍?(A，B]、(B，C] 和?(C，D] 的鍵。
負責存儲特定?key 的節(jié)點列表稱為首選項列表。該系統(tǒng)的設計將在第?4.8?節(jié)中進行解釋，以便系統(tǒng)中的每個節(jié)點都可以確定對于任何特定的鍵，哪些節(jié)點應該在該列表中。考慮到節(jié)點故障，首選列表包含?N?個以上的節(jié)點。注意，通過使用虛擬節(jié)點，特定密鑰的前?N?個后繼位置可能由少于?N?個不同的物理節(jié)點擁有（即，一個節(jié)點可以持有前?N?個位置中的多于一個）。為了解決這個問題，通過跳過環(huán)中的位置來構建鍵的偏好列表，以確保該列表僅包含不同的物理節(jié)點。
?
?
4.4?數(shù)據(jù)版本控制
Dynamo?提供了最終的一致性，允許更新異步傳播到所有副本。在所有副本應用更新之前，put() 調(diào)用可能會返回到其調(diào)用者，這可能會導致后續(xù)?get() 操作可能會返回沒有最新更新的對象的情況。如果沒有失敗，則更新傳播時間有一個界限。但是，在某些故障情況下（例如，服務器中斷或網(wǎng)絡分區(qū)），更新可能不會在很長一段時間內(nèi)到達所有副本。
亞馬遜的平臺上有一類應用可以容忍這種不一致，并且可以被構建為在這些條件下運行。例如，購物車應用程序要求?"添加到購物車"?操作永遠不能被忘記或拒絕。如果購物車的最新狀態(tài)不可用，并且用戶對購物車的舊版本進行了更改，則該更改仍然有意義，應該保留。但與此同時，它不應該取代購物車當前不可用的狀態(tài)，購物車本身可能包含應該保留的更改。請注意，"添加到購物車"?和?"從購物車中刪除項目"?操作都被轉換為向?Dynamo 發(fā)出的請求。當顧客想要將物品添加到購物車（或從購物車中移除）并且最新版本不可用時，該物品被添加到舊版本（或從舊版本中移除），并且不同的版本稍后被協(xié)調(diào)處理。
為了提供這種保證，Dynamo 將每次修改的結果視為數(shù)據(jù)的新的不可變版本。它允許一個對象的多個版本同時出現(xiàn)在系統(tǒng)中。大多數(shù)情況下，新版本包含以前的版本，系統(tǒng)本身可以確定權威版本（語法協(xié)調(diào)）。但是，在出現(xiàn)故障和并發(fā)更新的情況下，可能會發(fā)生版本分支，從而導致對象的版本沖突。在這些情況下，系統(tǒng)無法協(xié)調(diào)同一對象的多個版本，客戶端必須執(zhí)行協(xié)調(diào)，以便將數(shù)據(jù)演化的多個分支折疊回一個分支（語義協(xié)調(diào)）。折疊操作的一個典型例子是?"合并"?客戶購物車的不同版本。使用這種協(xié)調(diào)機制，"添加到購物車"?操作永遠不會丟失。但是，刪除的項目可能會重新出現(xiàn)。
重要的是要理解，某些故障模式可能會導致系統(tǒng)不僅有兩個版本，而且有幾個版本的相同數(shù)據(jù)。存在網(wǎng)絡分區(qū)和節(jié)點故障時的更新可能會導致對象具有不同的版本，系統(tǒng)需要在將來對其進行協(xié)調(diào)。這要求我們設計明確承認同一數(shù)據(jù)的多個版本的可能性的應用程序（為了永遠不會丟失任何更新）。
Dynamo 使用矢量時鐘來捕捉同一對象不同版本之間的因果關系。向量時鐘實際上是(node, counter) 對的列表。一個矢量時鐘與每個對象的每個版本相關聯(lián)。人們可以通過檢查一個對象的矢量時鐘來確定它的兩個版本是在平行的分支上還是有因果關系。如果第一個對象時鐘上的計數(shù)器小于或等于第二個時鐘上的所有節(jié)點，那么第一個是第二個的祖先，可以被忘記。否則，這兩個變化被認為是沖突的，需要和解。
在?Dynamo?中，當客戶端希望更新一個對象時，它必須指定要更新哪個版本。這是通過傳遞它從先前的讀取操作中獲得的上下文來完成的，該上下文包含向量時鐘信息。在處理一個讀請求時，如果?Dynamo?訪問了多個無法在語法上協(xié)調(diào)的分支，它將返回葉子處的所有對象，以及上下文中相應的版本信息。使用該上下文的更新被認為已經(jīng)協(xié)調(diào)了不同的版本，并且分支被折疊成單個新版本。
為了說明矢量時鐘的使用，讓我們考慮圖?3?所示的例子。客戶端寫入新對象。處理這個鍵的寫操作的節(jié)點（比如Sx）增加了它的序列號，并使用它來創(chuàng)建數(shù)據(jù)的向量時鐘。系統(tǒng)現(xiàn)在有了對象?D1?及其相關的時鐘?[(Sx，1)]。客戶端更新對象。假設同一個節(jié)點也處理這個請求。系統(tǒng)現(xiàn)在也有對象?D2?和它相關的時鐘?[(Sx，2)]。D2?是?D1?的后裔，因此對?D1?寫得過多，然而可能有?D1?的復制品在尚未見到?D2?的節(jié)點上徘徊。讓我們假設同一個客戶端再次更新對象，并且不同的服務器（比如Sy）處理該請求。系統(tǒng)現(xiàn)在有數(shù)據(jù)?D3?及其相關時鐘[(Sx，2)，(Sy，1)]。
接下來，假設一個不同的客戶端讀取?D2，然后嘗試更新它，另一個節(jié)點（比如Sz）執(zhí)行寫入。系統(tǒng)現(xiàn)在有?D4（D2?的后裔），它的版本時鐘是?[(Sx，2)，(Sz，1)]。知道?D1?或?D2?的節(jié)點可以在接收到?D4?及其時鐘時確定?D1?和?D2?被新數(shù)據(jù)覆蓋并且可以被垃圾回收。知道?D3?并接收?D4?的節(jié)點會發(fā)現(xiàn)它們之間沒有因果關系。換句話說，D3?和?D4?的變化沒有相互反映。數(shù)據(jù)的兩個版本都必須保存并呈現(xiàn)給客戶端（在讀取時），以便進行語義協(xié)調(diào)。
現(xiàn)在假設一些客戶端讀取?D3?和?D4（上下文將反映這兩個值都是通過讀取找到的）。讀者的上下文是?D3?和?D4?時鐘的摘要，即?[(Sx，2)，(Sy，1)，(Sz，1)]。如果客戶端執(zhí)行協(xié)調(diào)，并且節(jié)點?Sx?協(xié)調(diào)寫入，Sx?將更新其在時鐘中的序列號。新數(shù)據(jù)?D5?將有以下時鐘：[(Sx，3)，(Sy，1)，(Sz，1)]。
向量時鐘的一個可能問題是，如果許多服務器協(xié)調(diào)對對象的寫入，向量時鐘的大小可能會增加。實際上，這是不可能的，因為寫入通常由首選項列表中的前?N?個節(jié)點之一處理。在網(wǎng)絡分區(qū)或多個服務器出現(xiàn)故障的情況下，寫請求可能由不在首選項列表前?N?個節(jié)點中的節(jié)點處理，導致矢量時鐘的大小增加。在這些情況下，最好限制矢量時鐘的大小。為此，Dynamo 采用了以下時鐘截斷方案：與每個?(node, counter)?對一起，Dynamo 存儲一個時間戳，該時間戳指示節(jié)點上次更新數(shù)據(jù)項的時間。當向量時鐘中的?(node, counter)?對的數(shù)量達到閾值（比如?10）時，從時鐘中移除最老的對。顯然，這種截斷方案會導致協(xié)調(diào)效率低下，因為不能準確地導出后代關系。然而，這個問題在生產(chǎn)中沒有出現(xiàn)，因此這個問題沒有得到徹底調(diào)查分析。
?
?
4.5 get() 和?put() 操作的執(zhí)行
Dynamo 中的任何存儲節(jié)點都有資格接收任何?key 的客戶端?get 和?put 操作。在本節(jié)中，為了簡單起見，我們描述了如何在無故障環(huán)境中執(zhí)行這些操作，在后續(xù)章節(jié)中，我們描述了如何在故障期間執(zhí)行讀寫操作。
get 和?put 操作都是使用亞馬遜的基礎設施特定的請求處理框架通過?HTTP 協(xié)議調(diào)用的。客戶端可以使用兩種策略來選擇節(jié)點：(1) 通過通用負載平衡器路由其請求，該負載平衡器將根據(jù)負載信息選擇節(jié)點，或者?(2) 使用分區(qū)感知客戶端庫，該庫將請求直接路由到適當?shù)膮f(xié)調(diào)器節(jié)點。第一種方法的優(yōu)點是客戶端不必在其應用程序中鏈接任何特定于?Dynamo 的代碼，而第二種策略可以實現(xiàn)更低的延遲，因為它跳過了潛在的轉發(fā)步驟。
處理讀或寫操作的節(jié)點稱為協(xié)調(diào)器。通常，這是首選項列表中前?N?個節(jié)點中的第一個。如果請求是通過負載均衡器接收的，則訪問?key 的請求可以被路由到環(huán)中的任何隨機節(jié)點。在這種情況下，如果接收請求的節(jié)點不在所請求?key 的首選項列表的前?N?名中，則該節(jié)點將不會協(xié)調(diào)它。相反，該節(jié)點會將請求轉發(fā)給首選項列表中前?N?個節(jié)點中的第一個。讀寫操作涉及首選項列表中的前?N?個健康節(jié)點，跳過那些關閉或不可訪問的節(jié)點。當所有節(jié)點都正常時，訪問鍵的首選列表中的前?N?個節(jié)點。當存在節(jié)點故障或網(wǎng)絡分區(qū)時，訪問在首選項列表中排名較低的節(jié)點。
為了保持副本之間的一致性，Dynamo 使用了類似于使用法定人數(shù)系統(tǒng)（quorum systems）中使用的一致性協(xié)議。該協(xié)議有兩個關鍵的可配置值：R?和?W。R?是成功讀取操作必須參與的最小節(jié)點數(shù)。W 是成功寫入操作必須參與的最小節(jié)點數(shù)。設置?R?和?W，使得?R + W > N?產(chǎn)生一個類似群體的系統(tǒng)。在這個模型中，get（或?put）操作的延遲由最慢的復制決定。因此，R?和?W?通常配置為小于?N，以提供更好的延遲。
當接收到一個?key?的?put() 請求時，協(xié)調(diào)器為新版本生成向量時鐘，并在本地寫入新版本。然后，協(xié)調(diào)器將新版本（連同新的矢量時鐘）發(fā)送到?N?個排名最高的可到達節(jié)點。如果至少有?W-1?節(jié)點響應，則認為寫入成功。
類似地，對于?get() 請求，協(xié)調(diào)器從該關鍵字的首選項列表中排名最高的?N?個可達節(jié)點請求該關鍵字的所有現(xiàn)有數(shù)據(jù)版本，然后在將結果返回給客戶端之前等待?R?個響應。如果協(xié)調(diào)器最終收集了數(shù)據(jù)的多個版本，它會返回所有它認為不相關的版本。然后，不同的版本被協(xié)調(diào)，取代當前版本的協(xié)調(diào)版本被寫回。
?
?
4.6?處理故障：提示移交
如果?Dynamo 使用傳統(tǒng)的方法，它將在服務器故障和網(wǎng)絡分區(qū)期間不可用，并且即使在最簡單的故障條件下也會降低耐用性。為了彌補這一點，它沒有強制執(zhí)行嚴格的法定人數(shù)成員，而是使用了?"草率的法定人數(shù)"；所有讀和寫操作都是在首選項列表中的前?N?個健康節(jié)點上執(zhí)行的，這可能不總是在遍歷一致性哈希環(huán)時遇到的前?N?個節(jié)點。
考慮圖?2?中給出的?Dynamo 配置的例子，N?=?3。在本例中，如果節(jié)點?A?在寫入操作期間暫時關閉或不可訪問，則通常位于節(jié)點?A?上的副本現(xiàn)在將被發(fā)送到節(jié)點?D。這樣做是為了保持所需的可用性和持久性保證。發(fā)送到?D?的副本在其元數(shù)據(jù)中將有一個提示，提示哪個節(jié)點是副本的預期接收者（在本例中為?A）。收到提示副本的節(jié)點會將它們保存在一個單獨的本地數(shù)據(jù)庫中，并定期進行掃描。一旦檢測到?A?已經(jīng)恢復，D?將嘗試將副本傳送給?A。一旦傳輸成功，D?可以從其本地存儲中刪除該對象，而不會減少系統(tǒng)中副本的總數(shù)。
使用提示切換，Dynamo 確保讀寫操作不會因臨時節(jié)點或網(wǎng)絡故障而失敗。需要最高級別可用性的應用程序可以將?W?設置為?1，這可以確保只要系統(tǒng)中的單個節(jié)點將?key 持久寫入其本地存儲，寫入就可以被接受。因此，只有當系統(tǒng)中的所有節(jié)點都不可用時，寫請求才會被拒絕。但實際上，生產(chǎn)中的亞馬遜大部分服務都設置了較高的?W，以滿足期望的耐用性水平。第?6?節(jié)將更詳細地討論配置?N、R?和?W。
高度可用的存儲系統(tǒng)必須能夠處理整個數(shù)據(jù)中心的故障。數(shù)據(jù)中心故障是由于斷電、冷卻故障、網(wǎng)絡故障和自然災害造成的。Dynamo?配置為每個對象在多個數(shù)據(jù)中心之間復制。本質上，key 的首選列表是這樣構建的，即存儲節(jié)點分布在多個數(shù)據(jù)中心。這些數(shù)據(jù)中心通過高速網(wǎng)絡連接在一起。這種跨多個數(shù)據(jù)中心復制的方案允許我們在不中斷數(shù)據(jù)的情況下處理整個數(shù)據(jù)中心的故障。
?
?
4.7?處理永久故障：副本同步
如果系統(tǒng)成員流失率較低并且節(jié)點故障是暫時的，則暗示切換效果最佳。在某些情況下，提示副本（hinted replicas）在返回到原始副本節(jié)點之前變得不可用。為了處理這種和其他對持久性的威脅，Dynamo 實現(xiàn)了一個反熵（anti-entropy）（副本同步）協(xié)議來保持副本的同步。
為了更快地檢測副本之間的不一致，并最大限度地減少傳輸?shù)臄?shù)據(jù)量，Dynamo 使用了Merkle?樹。Merkle?樹是一種?hash 樹，葉子是各個鍵的值的哈希。樹中較高的父節(jié)點是它們各自子節(jié)點的?hash。Merkle?樹的主要優(yōu)點是可以獨立檢查樹的每個分支，而不需要節(jié)點下載整個樹或整個數(shù)據(jù)集。此外，Merkle?樹有助于減少需要傳輸?shù)臄?shù)據(jù)量，同時檢查副本之間的不一致性。例如，如果兩棵樹的根的哈希值相等，則樹中葉節(jié)點的值相等，并且節(jié)點不需要同步。如果沒有，則意味著某些副本的值不同。在這種情況下，節(jié)點可以交換子節(jié)點的哈希值，并且該過程繼續(xù)進行，直到到達樹葉，此時主機可以識別?"不同步"?的?key。Merkle?樹最大限度地減少了同步所需傳輸?shù)臄?shù)據(jù)量，并減少了反熵過程中執(zhí)行的磁盤讀取次數(shù)。
Dynamo 使用?Merkle?樹進行反熵，如下所示：每個節(jié)點為其托管的每個?key 范圍（虛擬節(jié)點覆蓋的密鑰集）維護一個單獨的?Merkle?樹。這允許節(jié)點比較一個鍵范圍內(nèi)的鍵是否是最新的。在該方案中，兩個節(jié)點交換對應于它們共同擁有的?key 范圍的?Merkle?樹的根。隨后，使用上述樹遍歷方案，節(jié)點確定它們是否有任何差異，并執(zhí)行適當?shù)耐絼幼鳌Ｔ摲桨傅娜秉c是，當節(jié)點加入或離開系統(tǒng)時，許多關鍵范圍會改變，從而需要重新計算樹。然而，這個問題是通過第?6.2?節(jié)中描述的細化分區(qū)方案來解決的。
?
?
4.8?成員資格和故障檢測
4.8.1?Ring Membership
在亞馬遜的環(huán)境中，節(jié)點中斷（由于故障和維護任務）通常是短暫的，但可能會持續(xù)很長時間。節(jié)點中斷很少意味著永久脫離，因此不應導致分區(qū)分配的重新平衡或不可達副本的修復。類似地，手動錯誤可能會導致新?Dynamo 節(jié)點的意外啟動。由于這些原因，使用顯式機制來啟動從?Dynamo 環(huán)添加和移除節(jié)點被認為是合適的。管理員使用命令行工具或瀏覽器連接到?Dynamo 節(jié)點，并發(fā)布成員資格更改，以將節(jié)點加入環(huán)或從環(huán)中刪除節(jié)點。服務于該請求的節(jié)點將成員變更及其發(fā)布時間寫入持久存儲。成員關系的變化形成了一個歷史，因為節(jié)點可以多次刪除和添加回來。基于?gossip 協(xié)議傳播成員關系的變化，并維護最終一致的成員關系視圖。每個節(jié)點每秒鐘都會聯(lián)系一個隨機選擇的對等節(jié)點，這兩個節(jié)點可以有效地協(xié)調(diào)它們持久的成員關系變化歷史。
當一個節(jié)點第一次啟動時，它選擇它的令牌集（set of tokens）（一致性哈希空間中的虛擬節(jié)點），并將節(jié)點映射到它們各自的令牌集。映射保存在磁盤上，最初只包含本地節(jié)點和令牌集。存儲在不同?Dynamo 節(jié)點上的映射在協(xié)調(diào)成員資格改變歷史的相同通信交換期間被協(xié)調(diào)。因此，分區(qū)和放置信息也通過基于?gossip 協(xié)議傳播，并且每個存儲節(jié)點都知道其對等節(jié)點處理的令牌范圍。這允許每個節(jié)點將?key 的讀/寫操作直接轉發(fā)到正確的節(jié)點集。
?
4.8.2?外部發(fā)現(xiàn)
上述機制可能暫時導致一個邏輯分區(qū)的?Dynamo?環(huán)。例如，管理員可以聯(lián)系節(jié)點?A?將節(jié)點?A?加入環(huán)，然后聯(lián)系節(jié)點?B?將節(jié)點?B?加入環(huán)。在這種情況下，節(jié)點?A?和節(jié)點?B?都認為自己是環(huán)中的一員，但兩者都不會立即意識到對方。為了防止邏輯分區(qū)，一些?Dynamo 節(jié)點扮演種子的角色。種子是通過外部機制被發(fā)現(xiàn)，同時，所有節(jié)點都知道它的存在。因為所有節(jié)點最終都用一個種子來協(xié)調(diào)它們的成員關系，所以邏輯分區(qū)是極不可能的。種子可以從靜態(tài)配置或配置服務中獲得。種子通常是?Dynamo 環(huán)中功能齊全的節(jié)點。
?
4.8.3?故障檢測
Dynamo中的故障檢測用于避免在?get() 和?put() 操作期間以及傳輸分區(qū)和提示副本時嘗試與不可達的對等體通信。為了避免失敗的通信嘗試，故障檢測的純本地概念是完全足夠的：如果節(jié)點?B?不響應節(jié)點?A?的消息（即使節(jié)點?B?響應節(jié)點?C?的消息），節(jié)點?A?可以認為節(jié)點?B?失敗。在?Dynamo 環(huán)中產(chǎn)生節(jié)點間通信的客戶端請求的穩(wěn)定速率存在的情況下，當節(jié)點?B?未能響應消息時，節(jié)點?A?迅速發(fā)現(xiàn)節(jié)點?B?無響應；然后，節(jié)點?A?使用備用節(jié)點來服務映射到節(jié)點?B?的分區(qū)的請求；甲定期重試乙，以檢查后者的恢復。在沒有客戶端請求來驅動兩個節(jié)點之間的流量的情況下，兩個節(jié)點都不需要知道另一個節(jié)點是否可達和響應。
去中心化故障檢測協(xié)議使用簡單的?gossip 協(xié)議，使系統(tǒng)中的每個節(jié)點能夠了解其他節(jié)點的加入（或離開）。關于去中心化式故障檢測器和影響其準確性的參數(shù)的詳細信息，請感興趣的讀者參考。Dynamo 的早期設計使用去中心化的故障檢測器來保持故障狀態(tài)的全局一致性。后來確定，顯式節(jié)點加入和離開方法消除了對故障狀態(tài)全局視圖的需要。這是因為節(jié)點通過顯式節(jié)點加入和離開方法被通知永久節(jié)點添加和移除，并且當單個節(jié)點無法與其他節(jié)點通信時（在轉發(fā)請求時），臨時節(jié)點故障被檢測到。
?
4.9?添加/刪除存儲節(jié)點
當一個新節(jié)點（比如說?X）被添加到系統(tǒng)中時，它會被分配一些令牌，這些令牌隨機分布在環(huán)上。對于分配給節(jié)點?X?的每個密鑰范圍，可能有許多節(jié)點（小于或等于?N）當前負責處理屬于其令牌范圍內(nèi)的密鑰。由于將密鑰范圍分配給?X，一些現(xiàn)有的節(jié)點不再需要它們的一些密鑰，這些節(jié)點將這些密鑰傳輸給?X。讓我們考慮一個簡單的自舉場景，其中節(jié)點?X?被添加到圖?2?所示的?A?和?B 之間的環(huán)中。當?X?被添加到系統(tǒng)中時，它負責將密鑰存儲在范圍(F，G]、(G，A] 和?(A，X] 中。因此，節(jié)點?B、C?和?D?不再需要存儲這些各自范圍內(nèi)的密鑰。因此，節(jié)點?B、C?和?D?將向?X?提供并在?X?確認后傳輸適當?shù)拿荑€集。當一個節(jié)點從系統(tǒng)中移除時，密鑰的重新分配以相反的過程發(fā)生。
運行經(jīng)驗表明，這種方法在存儲節(jié)點之間均勻地分配密鑰分配負載，這對于滿足延遲要求和確保快速引導非常重要。最后，通過在源節(jié)點和目標節(jié)點之間添加一輪確認，可以確保目標節(jié)點在給定的密鑰范圍內(nèi)不會接收到任何重復的傳輸。
?
?
5.?實現(xiàn)
在?Dynamo?中，每個存儲節(jié)點都有三個主要的軟件組件：請求協(xié)調(diào)、成員資格和故障檢測以及本地持久性引擎。所有這些組件都是用?Java?實現(xiàn)的。
Dynamo 的本地持久組件允許插入不同的存儲引擎。正在使用的引擎是?Berkeley?數(shù)據(jù)庫（BDB）事務數(shù)據(jù)存儲、BDB Java?版、MySQL?和一個帶有持久后備存儲的內(nèi)存緩沖區(qū)。設計可插拔持久性組件的主要原因是選擇最適合應用程序訪問模式的存儲引擎。例如，BDB?通常可以處理幾十?kb 的對象，而?MySQL?可以處理更大的對象。應用程序根據(jù)其對象大小分布選擇?Dynamo 的本地持久性引擎。Dynamo 的大多數(shù)生產(chǎn)實例使用?BDB?交易數(shù)據(jù)存儲。
請求協(xié)調(diào)組件建立在事件驅動的消息傳遞基礎之上，其中消息處理流水線被分成多個階段，類似于?SEDA?架構。所有通信都是使用?Java NIO?通道實現(xiàn)的。協(xié)調(diào)器通過從一個或多個節(jié)點收集數(shù)據(jù)（在讀取的情況下）或在一個或多個節(jié)點存儲數(shù)據(jù)（用于寫入）來代表客戶端執(zhí)行讀取和寫入請求。每個客戶端請求都會導致在接收客戶端請求的節(jié)點上創(chuàng)建一個狀態(tài)機。狀態(tài)機包含識別負責密鑰的節(jié)點、發(fā)送請求、等待響應、可能進行重試、處理響應以及將響應打包到客戶端的所有邏輯。每個狀態(tài)機實例只處理一個客戶端請求。例如，讀操作實現(xiàn)以下狀態(tài)機：(1) 向節(jié)點發(fā)送讀請求，(2) 等待所需響應的最小數(shù)量，(3) 如果在給定的時間范圍內(nèi)收到太少的響應，則請求失敗，(4) 否則收集所有數(shù)據(jù)版本并確定要返回的版本，以及(5) 如果啟用了版本控制，則執(zhí)行語法協(xié)調(diào)并生成包含所有剩余版本的矢量時鐘的不透明寫上下文。為了簡潔起見，省略了故障處理和重試狀態(tài)。
在讀響應返回給調(diào)用方之后，狀態(tài)機等待一小段時間以接收任何未完成的響應。如果在任何響應中返回了過時版本，協(xié)調(diào)器會用最新版本更新這些節(jié)點。這個過程被稱為讀取修復，因為它在一個時刻修復了錯過最近更新的副本，并且解除了反熵協(xié)議必須做的事情。
如前所述，寫請求由首選項列表中的前?N?個節(jié)點之一協(xié)調(diào)。盡管總是希望讓前?N?個節(jié)點中的第一個節(jié)點來協(xié)調(diào)寫入，從而在單個位置序列化所有寫入，但這種方法導致了不均勻的負載分布，從而導致違反服務層協(xié)議。這是因為請求負載不是均勻分布在對象之間的。為了解決這個問題，首選項列表中的前?N?個節(jié)點中的任何一個都可以協(xié)調(diào)寫入。特別地，由于每次寫操作通常跟隨讀操作，所以寫操作的協(xié)調(diào)器被選擇為對存儲在請求的上下文信息中的先前讀操作做出最快響應的節(jié)點。這種優(yōu)化使我們能夠選擇包含由之前的讀取操作讀取的數(shù)據(jù)的節(jié)點，從而增加了獲得?"讀-寫"?一致性的機會。它還減少了請求處理性能的可變性，從而將性能提高到?99.9%。
?
?
6.?經(jīng)驗和教訓
Dynamo?被幾種不同配置的服務使用。這些實例因其版本協(xié)調(diào)邏輯和讀/寫仲裁特征而不同。以下是?Dynamo 使用的主要模式：
業(yè)務邏輯特定的協(xié)調(diào)：這是?Dynamo 的一個常見用例。每個數(shù)據(jù)對象跨多個節(jié)點復制。在不同版本的情況下，客戶端應用程序執(zhí)行自己的協(xié)調(diào)邏輯。前面討論的購物車服務就是這類服務的一個典型例子。它的業(yè)務邏輯通過合并客戶購物車的不同版本來協(xié)調(diào)對象。
基于時間戳的協(xié)調(diào)：這種情況與前一種情況的不同之處僅在于協(xié)調(diào)機制。在不同版本的情況下，Dynamo 執(zhí)行簡單的基于時間戳的?"最后寫入獲勝"?的協(xié)調(diào)邏輯；即具有最大物理時間戳值的對象被選為正確的版本。維護客戶會話信息的服務是使用這種模式的服務的一個很好的例子。
高性能讀取引擎：雖然?Dynamo 被構建為一個?"始終可寫"?的數(shù)據(jù)存儲，但一些服務正在調(diào)整其仲裁特征，并將其用作高性能讀取引擎。通常，這些服務的讀取請求率很高，只有少量更新。在這種配置中，通常將?R?設置為?1，將?W?設置為?N。對于這些服務，Dynamo 提供了跨多個節(jié)點分區(qū)和復制數(shù)據(jù)的能力，從而提供了增量可擴展性。其中一些實例充當存儲在更大權重后備存儲中的數(shù)據(jù)的權威持久性緩存。維護產(chǎn)品目錄和促銷項目的服務屬于這一類。
Dynamo 的主要優(yōu)勢是其客戶端應用程序可以調(diào)整?N、R?和?W?的值，以實現(xiàn)所需的性能、可用性和耐用性水平。例如，N?的值決定了每個物體的耐久性。Dynamo 的用戶使用的一個典型的?N?值是?3。
W?和?R?的值影響對象的可用性、持久性和一致性。例如，如果?W?設置為?1，則只要系統(tǒng)中至少有一個節(jié)點可以成功處理寫請求，系統(tǒng)就永遠不會拒絕寫請求。然而，較低的?W?和?R?值會增加不一致的風險，因為寫請求被認為是成功的，并返回給客戶端，即使它們沒有被大多數(shù)副本處理。這還會在寫入請求成功返回到客戶端時引入一個持久性漏洞窗口，即使它只在少數(shù)節(jié)點上保持不變（This?also introduces a vulnerability window for durability when a write?request is successfully returned to the client even?though it has?been persisted at only a small number of nodes）。
傳統(tǒng)方法認為耐用性和可用性是相輔相成的。然而，這里不一定是這樣。例如，可以通過增加?W?來減少持久性的漏洞窗口。這可能會增加拒絕請求的概率（從而降低可用性），因為需要更多的存儲主機處于活動狀態(tài)才能處理寫請求。Dynamo 的幾個實例使用的常見配置 ?(N,R,W)?是（3，2，2）。選擇這些值是為了滿足必要的性能、持久性、一致性和可用性級別協(xié)議。
本節(jié)中介紹的所有測量都是在運行配置為（3，2，2）的實時系統(tǒng)上進行的，該系統(tǒng)運行數(shù)百個具有相同硬件配置的節(jié)點。如前所述，Dynamo 的每個實例都包含位于多個數(shù)據(jù)中心的節(jié)點。這些數(shù)據(jù)中心通常通過高速網(wǎng)絡鏈接連接。回想一下，要生成成功的?get（或?put）響應，節(jié)點需要響應協(xié)調(diào)器。顯然，數(shù)據(jù)中心之間的網(wǎng)絡延遲會影響響應時間，節(jié)點（及其數(shù)據(jù)中心位置）的選擇會滿足應用程序的目標服務層協(xié)議。
?
?
6.1?平衡性能和耐用性
雖然?Dynamo 的主要設計目標是建立一個高度可用的數(shù)據(jù)存儲，但性能在亞馬遜的平臺上是一個同樣重要的標準。如前所述，為了提供一致的客戶體驗，亞馬遜的服務將性能目標設置在較高的百分點（如?99.9%?或?99.99%）。使用?Dynamo 的服務需要的典型服務層協(xié)議是?99.9%?的讀寫請求在?300?毫秒內(nèi)執(zhí)行。
由于?Dynamo 運行在標準的商用硬件組件上，這些組件的輸入/輸出吞吐量遠遠低于高端企業(yè)服務器，因此為讀寫操作提供一致的高性能是一項非常重要的任務。多個存儲節(jié)點參與讀寫操作使其更具挑戰(zhàn)性，因為這些操作的性能受到最慢的讀寫副本的限制。圖?4?顯示了?30?天內(nèi)?Dynamo 讀寫操作的平均延遲和?99.9%?延遲。如圖所示，延遲呈現(xiàn)出明顯的晝夜模式，這是傳入請求速率的晝夜模式的結果（即，白天和夜晚之間的請求速率存在顯著差異）。此外，寫延遲明顯高于讀延遲，因為寫操作總是導致磁盤訪問。還有，99.9%?的延遲約為?200?毫秒，比平均值高一個數(shù)量級。這是因為?99.9%?的延遲受幾個因素的影響，如請求負載的可變性、對象大小和位置模式。
雖然這種性能水平對于許多服務來說是可以接受的，但是一些面向客戶的服務需要更高的性能水平。對于這些服務，Dynamo 提供了權衡耐用性保證和性能的能力。在優(yōu)化中，每個存儲節(jié)點在其內(nèi)存中維護一個對象緩沖區(qū)。每個寫操作都存儲在緩沖區(qū)中，并由寫線程定期寫入存儲。在該方案中，讀取操作首先檢查所請求的密鑰是否存在于緩沖區(qū)中。如果是這樣，則從緩沖區(qū)而不是存儲引擎中讀取對象。
這種優(yōu)化使得?99.9%?的延遲在高峰流量期間降低了?5?倍，即使是一千個對象的非常小的緩沖區(qū)也是如此（參見圖?5）。此外，如圖所示，寫緩沖可以消除較高百分比的延遲。顯然，這個方案是以性能換取耐用性的。在這種方案中，服務器崩潰會導致緩沖區(qū)中排隊的寫入丟失。為了降低持久性風險，寫入操作被細化為讓協(xié)調(diào)器從?N?個副本中選擇一個來執(zhí)行?"持久性寫入"。因為協(xié)調(diào)器只等待?W?響應，所以寫操作的性能不受單個副本執(zhí)行的持久寫操作的性能的影響。
?
?
6.2?確保均勻的負載分布
Dynamo 使用一致的哈希算法在副本之間劃分其?key 空間，并確保均勻的負載分布。假設?key 的訪問分布不是高度傾斜的，統(tǒng)一的?key 分布可以幫助我們實現(xiàn)統(tǒng)一的負載分布。具體來說，Dynamo 的設計假設即使在訪問分布中存在明顯的偏斜，在分布的流行端也有足夠的?key，以便處理熱點?key 的負載可以通過分區(qū)均勻地分布在節(jié)點上。本節(jié)討論了?Dynamo 中的負載不平衡以及不同分區(qū)策略對負載分布的影響。
為了研究負載不平衡及其與請求負載的相關性，對每個節(jié)點接收的請求總數(shù)進行了?24?小時的測量，細分為?30?分鐘的間隔。在給定的時間窗口內(nèi)，如果節(jié)點的請求負載偏離平均負載的值小于某個閾值（此處為?15%），則該節(jié)點被視為?"不平衡"。否則，該節(jié)點被視為?"失衡"。圖?6?顯示了這段時間內(nèi)?"失衡"（以下稱為?"失衡比率"）的節(jié)點比例。作為參考，整個系統(tǒng)在此期間接收到的相應請求負載也被繪制出來。如圖所示，不平衡率隨著負載的增加而降低。例如，在低負載期間，不平衡率高達?20%，而在高負載期間，不平衡率接近?10%。直觀地說，這可以用以下事實來解釋：在高負載下，大量熱點?key 被訪問，并且由于密鑰的均勻分布，負載被均勻分布。然而，在低負載（負載是測量的峰值負載的?1/8）期間，訪問的熱點 key 較少，從而導致更高的負載不平衡。本節(jié)討論了?Dynamo 的分區(qū)方案是如何隨著時間的推移而演變的，以及它對負載分布的影響。
策略1：每個節(jié)點測試隨機令牌，并根據(jù)令牌值進行分區(qū)：這是在生產(chǎn)中部署的初始策略（在第?4.2?節(jié)中有所描述）。在這個方案中，每個節(jié)點都被分配了?T?個令牌（從散列空間中統(tǒng)一隨機選擇）。所有節(jié)點的標記根據(jù)它們在哈希空間中的值進行排序。每兩個連續(xù)的標記定義一個范圍。最后一個標記和第一個標記形成一個范圍，該范圍在散列空間中從最高值到最低值?"環(huán)繞"。因為令牌是隨機選擇的，所以范圍大小不一。隨著節(jié)點加入和離開系統(tǒng)，令牌集會發(fā)生變化，因此范圍也會發(fā)生變化。請注意，維護每個節(jié)點的成員資格所需的空間隨著系統(tǒng)中節(jié)點數(shù)量的增加而線性增加。
使用此策略時，遇到了以下問題。首先，當一個新節(jié)點加入系統(tǒng)時，它需要從其他節(jié)點?"竊取"?它的密鑰范圍。然而，將密鑰范圍移交給新節(jié)點的節(jié)點必須掃描它們的本地持久性存儲來檢索適當?shù)臄?shù)據(jù)項集合。請注意，在生產(chǎn)節(jié)點上執(zhí)行這樣的掃描操作很棘手，因為掃描是高度資源密集型操作，并且需要在后臺執(zhí)行，而不會影響客戶性能。這要求我們以最低優(yōu)先級運行引導任務。然而，這大大降低了引導過程，在繁忙的購物季節(jié)，當節(jié)點每天處理數(shù)百萬個請求時，引導幾乎需要一天才能完成。第二，當一個節(jié)點加入/離開系統(tǒng)時，由許多節(jié)點處理的?key 范圍發(fā)生變化，并且需要重新計算新范圍的?Merkle?樹，這是一個在生產(chǎn)系統(tǒng)上執(zhí)行的非常重要的操作。最后，由于密鑰范圍的隨機性，沒有簡單的方法來拍攝整個密鑰空間的快照，這使得存檔過程變得復雜。在這個方案中，歸檔整個密鑰空間需要我們分別從每個節(jié)點檢索密鑰，這是非常低效的。
?
這種策略的根本問題是數(shù)據(jù)分區(qū)和數(shù)據(jù)放置的方案是相互交織的。例如，在某些情況下，為了處理請求負載的增加，最好向系統(tǒng)添加更多的節(jié)點。但是，在這種情況下，不可能在不影響數(shù)據(jù)分區(qū)的情況下添加節(jié)點。理想情況下，最好使用獨立的分區(qū)和放置方案。為此，評估了以下戰(zhàn)略：
策略2：每個節(jié)點?T?個隨機令牌和相等大小的分區(qū)：在這個策略中，散列空間被分成?Q?個相等大小的分區(qū)/范圍，每個節(jié)點被分配?T?個隨機令牌。Q?通常設置為?Q >> N?和?Q >> S*T，其中?S?是系統(tǒng)中的節(jié)點數(shù)。在這種策略中，令牌僅用于構建將散列空間中的值映射到有序節(jié)點列表的函數(shù)，而不是決定分區(qū)。一個分區(qū)被放置在從該分區(qū)的末端順時針遍歷一致性哈希環(huán)時遇到的前?N?個唯一節(jié)點上。圖?7?說明了?N?=?3?的策略。在這個例子中，節(jié)點?A、B、C?在從包含密鑰?k1?的分區(qū)的末端遍歷環(huán)時遇到。這種策略的主要優(yōu)點是：(1) 分區(qū)和分區(qū)放置的解耦，以及?(2) 能夠在運行時更改放置方案。
?
策略3：每個節(jié)點?Q/S?令牌，大小相等的分區(qū)：與策略?2?類似，該策略將哈希空間劃分為Q?個大小相等的分區(qū)，分區(qū)的放置與分區(qū)方案解耦。此外，每個節(jié)點都被分配了?Q/S?令牌，其中?S?是系統(tǒng)中的節(jié)點數(shù)。當一個節(jié)點離開系統(tǒng)時，它的令牌被隨機分配給剩余的節(jié)點，這樣這些屬性被保留。類似地，當一個節(jié)點加入系統(tǒng)時，它會以保留這些屬性的方式從系統(tǒng)中的節(jié)點?"竊取"?令牌。
對于一個?S?=?30，N?=?3?的系統(tǒng)，對這三種策略的效率進行了評估。然而，公平地比較這些不同的策略是困難的，因為不同的策略有不同的配置來調(diào)整它們的效率。例如，策略?1?的負載分布屬性取決于令牌的數(shù)量（即?T），而策略?3?取決于分區(qū)的數(shù)量（即?Q）。比較這些策略的一個公平的方法是評估負載分布的偏差，而所有策略都使用相同的空間來維護其成員信息。例如，在策略?1?中，每個節(jié)點需要維護環(huán)中所有節(jié)點的令牌位置，而在策略?3?中，每個節(jié)點需要維護關于分配給每個節(jié)點的分區(qū)的信息。
在我們的下一個實驗中，通過改變相關參數(shù)（T?和?Q）來評估這些策略。每種策略的負載平衡效率是針對每個節(jié)點需要維護的不同大小的成員信息來衡量的，其中負載平衡效率定義為每個節(jié)點服務的平均請求數(shù)與最熱節(jié)點服務的最大請求數(shù)之比。
結果如圖?8?所示。如圖所示，策略?3?實現(xiàn)了最好的負載平衡效率，而策略?2?的負載平衡效率最差。在很短的時間內(nèi)，策略?2?充當了從使用策略?1?遷移到策略?3?的過程中的臨時設置。與策略?1?相比，策略?3?實現(xiàn)了更高的效率，并將每個節(jié)點上維護的成員信息的大小減少了三個數(shù)量級。雖然存儲不是主要問題，但是節(jié)點周期性地散布成員信息，因此希望盡可能緊湊地保存該信息。除此之外，由于以下原因，策略?3?是有利的，并且部署更簡單：(1) 更快的引導/恢復：由于分區(qū)范圍是固定的，它們可以存儲在單獨的文件中，這意味著可以通過簡單地傳輸文件來將分區(qū)作為一個單元重新定位（避免定位特定項目所需的隨機訪問）。這簡化了引導和恢復過程。(2) 易于存檔：數(shù)據(jù)集的定期存檔是大多數(shù)亞馬遜存儲服務的強制性要求。在策略?3?中，歸檔由?Dynamo?存儲的整個數(shù)據(jù)集更簡單，因為分區(qū)文件可以單獨歸檔。相比之下，在策略?1?中，令牌是隨機選擇的，并且將存儲在?Dynamo 中的數(shù)據(jù)存檔需要分別從各個節(jié)點檢索密鑰，這通常是低效和緩慢的。策略?3?的缺點是改變節(jié)點成員需要協(xié)調(diào)，以保持分配所需的屬性。
?
?
6.3?分歧版本：什么時候，有多少？
如前所述，Dynamo 旨在權衡一致性和可用性。為了了解不同故障對一致性的精確影響，需要多種因素的詳細數(shù)據(jù)：停機時間、故障類型、組件可靠性、工作負載等。詳細介紹這些數(shù)字超出了本文的范圍。但是，本節(jié)討論了一個很好的總結指標：在實際生產(chǎn)環(huán)境中應用程序所看到的不同版本的數(shù)量。
數(shù)據(jù)項的不同版本出現(xiàn)在兩種情況下。第一種是當系統(tǒng)面臨諸如節(jié)點故障、數(shù)據(jù)中心故障和網(wǎng)絡分區(qū)等故障情況時。第二種情況是，系統(tǒng)正在處理大量并發(fā)寫入單個數(shù)據(jù)項的操作，而多個節(jié)點最終會同時協(xié)調(diào)更新。從可用性和效率的角度來看，最好在任何給定的時間將不同版本的數(shù)量保持在盡可能低的水平。如果版本不能單獨基于向量時鐘進行語法協(xié)調(diào)，它們必須被傳遞給業(yè)務邏輯進行語義協(xié)調(diào)。語義協(xié)調(diào)會給服務帶來額外的負載，因此最好盡量減少對它的需求。
在我們的下一個實驗中，返回購物車服務的版本數(shù)量被分析了?24?小時。在此期間，99.94%的請求只看到一個版本；0.00057%?的請求看到?2?個版本；0.00047%?的請求看到了?3?個版本，0.00009%?的請求看到了?4?個版本。這說明發(fā)散版本很少被創(chuàng)造出來（This shows?that divergent versions are created rarely）。
經(jīng)驗表明，不同版本數(shù)量的增加不是由失敗造成的，而是由于并發(fā)編寫器數(shù)量的增加。并發(fā)寫入數(shù)量的增加通常是由忙碌的機器人（自動化客戶端程序）觸發(fā)的，很少是由人類觸發(fā)的。由于故事的敏感性，這個問題沒有詳細討論。
?
?
6.4?客戶端驅動或服務器驅動的協(xié)調(diào)
如第?5?節(jié)所述，Dynamo 有一個請求協(xié)調(diào)組件，它使用狀態(tài)機來處理傳入的請求。負載平衡器將客戶端請求統(tǒng)一分配給環(huán)中的節(jié)點。任何?Dynamo 節(jié)點都可以作為讀取請求的協(xié)調(diào)者。另一方面，寫請求將由鍵的當前首選項列表中的一個節(jié)點協(xié)調(diào)。這種限制是由于這些優(yōu)選節(jié)點具有創(chuàng)建新版本標記的額外責任，該新版本標記必然包含由寫請求更新的版本。請注意，如果?Dynamo 的版本方案基于物理時間戳，任何節(jié)點都可以協(xié)調(diào)寫請求。
請求協(xié)調(diào)的另一種方法是將狀態(tài)機移動到客戶端節(jié)點。在這個方案中，客戶端應用程序使用一個庫在本地執(zhí)行請求協(xié)調(diào)。客戶端定期選擇一個隨機的?Dynamo 節(jié)點，并下載其?Dynamo 成員狀態(tài)的當前視圖。使用這些信息，客戶端可以確定哪組節(jié)點構成了任何給定鍵的首選列表。讀取請求可以在客戶端節(jié)點處被協(xié)調(diào)，從而避免了額外的網(wǎng)絡跳躍，如果請求被負載均衡器分配給一個隨機的?Dynamo 節(jié)點，則會產(chǎn)生額外的網(wǎng)絡跳躍。如果?Dynamo?使用基于時間戳的版本控制，則寫操作要么轉發(fā)到鍵的首選項列表中的節(jié)點，要么可以在本地進行協(xié)調(diào)。
客戶端驅動的協(xié)調(diào)方法的一個重要優(yōu)點是不再需要負載平衡器來統(tǒng)一分配客戶端負載。通過將密鑰近乎統(tǒng)一地分配給存儲節(jié)點，公平的負載分布得到了隱含的保證。顯然，這個方案的效率取決于客戶端的成員信息有多新。目前，客戶端每?10?秒鐘輪詢一個隨機的?Dynamo 節(jié)點以獲取成員更新。基于?pull?的方法比基于?push?的方法更受歡迎，因為前者可以更好地適應大量客戶端，并且需要在服務器上維護非常少的客戶端狀態(tài)。但是，在最壞的情況下，客戶端可能會暴露于過期成員身份達?10?秒鐘。在這種情況下，如果客戶端檢測到其成員資格表過時（例如，當某些成員不可訪問時），它將立即刷新其成員資格信息。
表?2?顯示了與服務器驅動的方法相比，使用客戶端驅動的協(xié)調(diào)在?24?小時內(nèi)觀察到的99.9%?的延遲改善和平均值。如表中所示，對于?99.9%?的延遲，客戶端驅動的協(xié)調(diào)方法將延遲減少了至少?30?毫秒，并將平均值減少了?3?到?4?毫秒。延遲的改善是因為客戶端驅動的方法消除了負載平衡器的開銷和當請求被分配給隨機節(jié)點時可能產(chǎn)生的額外網(wǎng)絡跳。如表中所示，平均潛伏期往往明顯低于?99.9%?的潛伏期。這是因為?Dynamo 的存儲引擎緩存和寫緩沖區(qū)有很好的命中率。此外，由于負載平衡器和網(wǎng)絡會給響應時間帶來額外的可變性，因此?99.9%?的響應時間增益高于平均值。
?
?
6.5?平衡后臺和前臺任務
除了正常的前臺?put/get 操作之外，每個節(jié)點還執(zhí)行不同種類的后臺任務，用于副本同步和數(shù)據(jù)切換（由于提示或添加/移除節(jié)點）。在早期的生產(chǎn)環(huán)境中，這些后臺任務觸發(fā)了資源爭用問題，并影響了常規(guī)?put?和?get?操作的性能。因此，有必要確保后臺任務僅在常規(guī)關鍵操作未受到顯著影響時運行。為此，后臺任務與準入控制機制相結合。每個后臺任務都使用這個控制器來保留資源（例如數(shù)據(jù)庫）的運行時間片，在所有后臺任務之間共享。基于前臺任務的監(jiān)控性能的反饋機制被用來改變可用于后臺任務的切片的數(shù)量。
準入控制器在執(zhí)行?"前臺"?put/get 操作時，不斷監(jiān)視資源訪問的行為。受監(jiān)控的方面包括磁盤操作的延遲、由于鎖爭用和事務超時導致的數(shù)據(jù)庫訪問失敗以及請求隊列等待時間。此信息用于檢查給定跟蹤時間窗口中延遲（或失敗）的百分比是否接近所需的閾值。例如，后臺控制器檢查第?99% 數(shù)據(jù)庫讀取延遲（過去?60?秒內(nèi)）與預設閾值（比如?50?毫秒）的接近程度。控制器使用這種比較來評估前臺操作的資源可用性。隨后，它決定多少時間片可用于后臺任務，從而使用反饋循環(huán)來限制后臺活動的侵入性。
?
?
6.6?討論
本節(jié)總結了?Dynamo 在實施和維護過程中獲得的一些經(jīng)驗。在過去的兩年里，亞馬遜的許多內(nèi)部服務都使用了?Dynamo，并且為其應用程序提供了很高的可用性。特別是，應用程序?99.9995%?的請求都收到了成功的響應（沒有超時），迄今為止沒有發(fā)生數(shù)據(jù)丟失事件。
此外，Dynamo 的主要優(yōu)勢是它提供了必要的旋鈕，使用三個參數(shù)來根據(jù)他們的需要調(diào)整他們的實例。與流行的商業(yè)數(shù)據(jù)存儲不同，Dynamo 向開發(fā)人員公開了數(shù)據(jù)一致性和協(xié)調(diào)邏輯問題。一開始，人們可能會認為應用程序邏輯會變得更加復雜。然而，從歷史上看，亞馬遜的平臺是為高可用性而構建的，許多應用程序都是為處理不同的故障模式和可能出現(xiàn)的不一致而設計的。因此，移植這樣的應用程序來使用?Dynamo 是一個相對簡單的任務。對于希望使用?Dynamo 的新應用程序，在開發(fā)的初始階段需要進行一些分析，以選擇合適的沖突解決機制來適當?shù)貪M足業(yè)務案例。最后，Dynamo 采用了完全成員模型，其中每個節(jié)點都知道其對等體托管的數(shù)據(jù)。為此，每個節(jié)點主動與系統(tǒng)中的其他節(jié)點共享完整的路由表。該模型適用于包含數(shù)百個節(jié)點的系統(tǒng)。然而，將這種設計擴展為運行數(shù)萬個節(jié)點并不容易，因為維護路由表的開銷會隨著系統(tǒng)大小的增加而增加。這個限制可以通過在?Dynamo 中引入分層擴展來克服。此外，請注意，這個問題由?O(1)?DHT系統(tǒng)主動解決。
?
?
7.?結論
本文描述了一個高度可用和可擴展的數(shù)據(jù)存儲庫?Dynamo，用于存儲亞馬遜電子商務平臺的一些核心服務的狀態(tài)。Dynamo 提供了所需的可用性和性能水平，并成功地處理了服務器故障、數(shù)據(jù)中心故障和網(wǎng)絡分區(qū)。Dynamo?具有增量可伸縮性，允許服務所有者根據(jù)其當前的請求負載進行上下伸縮。Dynamo 允許服務所有者通過調(diào)整參數(shù)?N、R?和?W?來定制他們的存儲系統(tǒng)，以滿足他們期望的性能、耐用性和一致性服務層協(xié)議。
Dynamo 在過去一年的生產(chǎn)使用表明，去中心化技術可以結合起來提供一個單一的高可用性系統(tǒng)。它在最具挑戰(zhàn)性的應用程序環(huán)境中的成功表明，最終一致的存儲系統(tǒng)可以成為高可用性應用程序的構建模塊
超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生總結
以上是生活随笔為你收集整理的Dynamo：亚马逊的高可用键值存储的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Megastore：为交互式服务提供可扩
- 下一篇： Amazon Aurora：高吞吐量云原