原文地址Dynamo

摘要

面對(duì)世界上最大的電商網(wǎng)站 Amazon.com类垫，我們遇到的最大挑戰(zhàn)之一就是海量規(guī)模下后臺(tái)的可靠性罗晕；即使是稍微的短暫停止服務(wù)仔掸，也會(huì)造成重大的經(jīng)濟(jì)損失鸯旁，并影響消費(fèi)者對(duì)Amazon的信任噪矛。Amazon.com平臺(tái)提供了許多互聯(lián)網(wǎng)服務(wù)，分布在全世界各地的多個(gè)數(shù)據(jù)中心的數(shù)萬(wàn)臺(tái)服務(wù)器以及網(wǎng)絡(luò)組件共同構(gòu)建了Amazon的底層基礎(chǔ)設(shè)施铺罢。在這樣的規(guī)模下艇挨，各個(gè)組件的失效持續(xù)的發(fā)生著，在這些失效情況下仍然需要維持一致狀態(tài)韭赘，這個(gè)需求驅(qū)動(dòng)著軟件系統(tǒng)的可靠性和擴(kuò)展性的發(fā)展缩滨。

本文展示了Dynamo的設(shè)計(jì)和實(shí)現(xiàn)，Dynamo是一個(gè)高可用的key-value存儲(chǔ)系統(tǒng)泉瞻，Aamzon的一些服務(wù)使用它來(lái)提供"永遠(yuǎn)在線"的服務(wù)脉漏。要達(dá)到這個(gè)水平的可用性，Dynamo在一些場(chǎng)景下犧牲了一致性袖牙。它廣泛的使用了對(duì)象版本以及應(yīng)用程序輔助解決沖突的方式鸠删，提供了一個(gè)新穎的接口給開發(fā)者使用。

關(guān)鍵詞

算法, 管理, 測(cè)量, 性能, 設(shè)計(jì), 可靠性.

1. 簡(jiǎn)介

Amazon運(yùn)行著一個(gè)全球范圍的電商平臺(tái)贼陶，高峰期服務(wù)于千萬(wàn)級(jí)別的消費(fèi)者刃泡，使用了分布在世界各地的多個(gè)數(shù)據(jù)中心的數(shù)萬(wàn)臺(tái)服務(wù)器。Amazon平臺(tái)對(duì)性能碉怔，可靠性和效率方面有著嚴(yán)格的要求烘贴，同時(shí)為了支持連續(xù)的擴(kuò)容，還需要很強(qiáng)的擴(kuò)展性撮胧〗白伲可靠性是其中最重要的要求之一，因?yàn)榧词故巧晕⒌耐Ｖ挂幌路?wù)芹啥，也會(huì)造成重大的經(jīng)濟(jì)損失锻离，并影響消費(fèi)者對(duì)Amazon的信任。此外墓怀，為了支持持續(xù)的增長(zhǎng)汽纠，平臺(tái)還需要是可擴(kuò)展的。

從維護(hù)Amazon平臺(tái)中我們學(xué)到一點(diǎn)傀履，一個(gè)系統(tǒng)的可靠性和擴(kuò)展性依賴于如何管理應(yīng)用程序的狀態(tài)虱朵。Amazon使用了一個(gè)高度去中心化，松散耦合，面向服務(wù)的架構(gòu)碴犬，其中包含了數(shù)百個(gè)服務(wù)絮宁。在這個(gè)環(huán)境中，對(duì)存儲(chǔ)技術(shù)有個(gè)特別的需求服协，那就是必須永遠(yuǎn)可用绍昂。舉例來(lái)說(shuō)，用戶應(yīng)該總是可以看到并添加商品到他們的購(gòu)物車偿荷，即使是硬盤壞掉了窘游，網(wǎng)絡(luò)路線抖動(dòng)，或者數(shù)據(jù)中心被龍卷風(fēng)摧毀遭顶。因此张峰，購(gòu)物車服務(wù)使用的數(shù)據(jù)存儲(chǔ)必須永遠(yuǎn)是可以讀取和寫入的，并且可以跨越數(shù)據(jù)中心使用棒旗。

在由數(shù)百萬(wàn)個(gè)組件組成的基礎(chǔ)設(shè)施中處理故障的情況是我們的標(biāo)準(zhǔn)運(yùn)作模式喘批。在任意時(shí)間，總有一小部分很小但很重要的服務(wù)器以及網(wǎng)絡(luò)組件是處于故障狀態(tài)铣揉。因此饶深，在構(gòu)建Amazon的軟件系統(tǒng)時(shí)，必須把這些故障處理看作是普通情況逛拱，并且不影響可用性和性能敌厘。

為了達(dá)到可靠性和擴(kuò)展性的要求，Amazon開發(fā)了一些存儲(chǔ)技術(shù)朽合，其中Amazon Simple Storage(在Amazon外部也可使用俱两，叫做Amazon S3)可能是最著名的一個(gè)。本文了展示了Dynamo的設(shè)計(jì)與實(shí)現(xiàn)曹步，另外一個(gè)為Amazon平臺(tái)設(shè)計(jì)的宪彩，高可用高擴(kuò)展性的分布式存儲(chǔ)技術(shù)。Dynamo被用于管理服務(wù)的狀態(tài)讲婚，它有著很高的可靠性要求尿孔，并且需要嚴(yán)格的處理可用性、一致性筹麸、成本效益活合、性能之間的平衡。Amazon平臺(tái)包含了各個(gè)差異很大的服務(wù)物赶，它們對(duì)存儲(chǔ)的要求各不相同白指。一部分應(yīng)用程序需要存儲(chǔ)技術(shù)足夠靈活，讓應(yīng)用程序設(shè)計(jì)人員能夠通過(guò)合適的配置來(lái)最低成本的達(dá)到高可用和高性能块差。

Amazon平臺(tái)上有很多服務(wù)侵续，只需要通過(guò)主鍵來(lái)訪問(wèn)數(shù)據(jù)倔丈。對(duì)于那些提供熱銷列表憨闰，購(gòu)物車状蜗，用戶偏好，會(huì)話管理鹉动，商品排名轧坎，產(chǎn)品目錄的服務(wù)來(lái)說(shuō)，使用關(guān)系型數(shù)據(jù)庫(kù)會(huì)導(dǎo)致性能低下泽示，并且限制了擴(kuò)展性和可用性缸血。Dynamo提供了一個(gè)簡(jiǎn)單的主鍵接口，來(lái)滿足這些應(yīng)用的需求械筛。

Dynammo混合了一些知名的技術(shù)來(lái)達(dá)到擴(kuò)展性和可用性: 數(shù)據(jù)的分片和備份使用一致性哈希^[1]捎泻，一致性使用對(duì)象版本技術(shù)^[2]來(lái)提供。副本之間的一致性由一個(gè)類仲裁技術(shù)以及去中心化的同步協(xié)議來(lái)保證埋哟。Dynamo使用了基于gossip的分布式故障探測(cè)技術(shù)和成員協(xié)議笆豁。 Dynamo是一個(gè)完全的去中心化系統(tǒng)，需要很少的人工管理赤赊。存儲(chǔ)節(jié)點(diǎn)可以隨時(shí)添加到Dynamo或者從Dynamo中刪除闯狱，不需要任何人工參與或者重新分布。

在過(guò)去一年抛计，Dynamo已經(jīng)成為了Amazon商務(wù)平臺(tái)的一些核心服務(wù)的底層存儲(chǔ)技術(shù)哄孤。它能夠在繁忙的假日購(gòu)物季不停服的擴(kuò)展到極高的負(fù)載。比如吹截，對(duì)于負(fù)責(zé)購(gòu)物車的服務(wù)瘦陈，一天之內(nèi)要處理千萬(wàn)級(jí)別的請(qǐng)求，導(dǎo)致超過(guò)3百萬(wàn)的結(jié)算處理波俄；以及會(huì)話管理服務(wù)晨逝，在同一時(shí)刻處理這上百萬(wàn)的并發(fā)活躍會(huì)話。

這項(xiàng)工作對(duì)于研發(fā)團(tuán)隊(duì)最大的貢獻(xiàn)是弟断，評(píng)估了如何將多個(gè)不同的技術(shù)結(jié)合在一起咏花，以提供一個(gè)高可用的系統(tǒng)。它說(shuō)明了一個(gè)最終一致性的存儲(chǔ)系統(tǒng)是可以用在生產(chǎn)環(huán)境中阀趴，并被最嚴(yán)格的應(yīng)用程序使用的昏翰。同時(shí)它提供了一些洞見，關(guān)于如何調(diào)試這些技術(shù)以滿足生產(chǎn)環(huán)境中對(duì)性能要求及其嚴(yán)格的應(yīng)用程序刘急。

本文的結(jié)構(gòu)如下: 第二節(jié)講述背景棚菊，第三節(jié)介紹相關(guān)工作。第四節(jié)講述系統(tǒng)設(shè)計(jì)叔汁，第五節(jié)描述了實(shí)現(xiàn)统求。第六節(jié)詳述了通過(guò)在生產(chǎn)環(huán)境運(yùn)行Dynamo得到的經(jīng)驗(yàn)和洞見检碗，第七節(jié)總結(jié)了全文。這篇論文有些地方本應(yīng)該多添加一些信息码邻，但是由于要保護(hù)Amazon的商業(yè)利益折剃，只能減少細(xì)節(jié)討論。出于這個(gè)原因像屋，第六節(jié)中的數(shù)據(jù)中心內(nèi)和跨數(shù)據(jù)中心延遲怕犁，6.2節(jié)中的絕對(duì)請(qǐng)求速率，6.3節(jié)中的停服時(shí)長(zhǎng)和工作負(fù)載己莺，都是總體測(cè)量而不是完全的細(xì)節(jié)奏甫。

2. 背景

Amazon商業(yè)平臺(tái)由數(shù)百個(gè)服務(wù)共同組成，它們協(xié)同工作凌受，提供包括推薦阵子，完成訂單，欺詐檢測(cè)等功能胜蛉。每個(gè)服務(wù)都提供一組定義良好的接口挠进，并且只能通過(guò)網(wǎng)絡(luò)來(lái)訪問(wèn)。這些服務(wù)運(yùn)行在位于世界各地的許多數(shù)據(jù)中心的數(shù)萬(wàn)臺(tái)服務(wù)器組成的基礎(chǔ)設(shè)施之上腾么。其中一些服務(wù)是無(wú)狀態(tài)的(比如聚合其他服務(wù)響應(yīng)的服務(wù))奈梳，一些服務(wù)是有狀態(tài)的(比如執(zhí)行業(yè)務(wù)邏輯的服務(wù)會(huì)根據(jù)持久存儲(chǔ)中的狀態(tài)來(lái)產(chǎn)生響應(yīng))。

傳統(tǒng)的生產(chǎn)環(huán)境將服務(wù)狀態(tài)存儲(chǔ)在關(guān)系型數(shù)據(jù)庫(kù)中解虱。然而攘须，對(duì)于通用的狀態(tài)存儲(chǔ)來(lái)說(shuō)，關(guān)系型數(shù)據(jù)庫(kù)是遠(yuǎn)不夠理想的殴泰。大多數(shù)的服務(wù)只需要通過(guò)主鍵來(lái)讀寫數(shù)據(jù)于宙，它們用不上RDBMS提供的哪些復(fù)雜的查詢和管理功能。這些多出來(lái)的功能需要昂貴的硬件以及高技能的人員來(lái)維護(hù)悍汛，導(dǎo)致這種方案非常低效捞魁。此外，可用的副本技術(shù)是很有限的离咐，而且通常犧牲可用性來(lái)達(dá)到一致性谱俭。雖然近些年出現(xiàn)了很多進(jìn)展，但數(shù)據(jù)庫(kù)的擴(kuò)容和負(fù)載均衡仍然不好做宵蛀。

本文描述的高可用數(shù)據(jù)存儲(chǔ)技術(shù)Dynamo昆著，正是為了滿足這一類服務(wù)的需求而研發(fā)的。Dynamo提供簡(jiǎn)單的key/value接口术陶，它是高可用的喘落，并有一個(gè)定義清晰的一致性窗口笙僚，它在資源使用方面是非常高效的敌蚜，并且有一個(gè)簡(jiǎn)單的擴(kuò)容方案，以應(yīng)對(duì)數(shù)據(jù)量或者請(qǐng)求量的增長(zhǎng)摆碉。每個(gè)使用Dynamo的服務(wù)都運(yùn)行它自己的Dynamo實(shí)例。

2.1 系統(tǒng)假設(shè)和要求

這一類服務(wù)的存儲(chǔ)系統(tǒng)有如下要求:

查詢模型：簡(jiǎn)單的讀寫操作, 通過(guò)唯一主鍵脓豪。狀態(tài)被存儲(chǔ)為二進(jìn)制對(duì)象巷帝，并通過(guò)唯一主鍵識(shí)別。沒有操作會(huì)跨多條數(shù)據(jù)跑揉，同時(shí)不需要關(guān)系schema锅睛。這個(gè)要求是基于以下觀察得出的：Amazon的服務(wù)中有相當(dāng)大的部分都可以使用這種簡(jiǎn)單的查詢模型埠巨，不需要任何關(guān)系schema历谍。Dynamo的目標(biāo)應(yīng)用程序需要存儲(chǔ)的對(duì)象都比較小(通常小于1M)。

ACID屬性：ACID(原子性辣垒，一致性望侈，隔離性，持久性)是一組用于保證數(shù)據(jù)庫(kù)事務(wù)可以可靠的執(zhí)行的屬性勋桶。在數(shù)據(jù)庫(kù)中脱衙，一個(gè)單獨(dú)的邏輯操作叫做一次事務(wù)。根據(jù)在Amazon的經(jīng)驗(yàn)例驹，提供了ACID保證的數(shù)據(jù)存儲(chǔ)系統(tǒng)的可用性都比較差捐韩。業(yè)界和學(xué)術(shù)界已經(jīng)廣泛的認(rèn)識(shí)到這一點(diǎn)^[3]。Dynamo的目標(biāo)應(yīng)用程序需要的是高可用性鹃锈，在弱一致性的情況下也可以工作荤胁。Dynamo不提供任何隔離級(jí)別的保證，并且只允許單個(gè)key的更新操作屎债。

效率：這個(gè)系統(tǒng)需要運(yùn)行在廉價(jià)的硬件設(shè)備上仅政。在Amazon平臺(tái)中，服務(wù)都有嚴(yán)格的延遲限制盆驹，這個(gè)延遲都是在99.9%分位進(jìn)行測(cè)量圆丹。由于獲取狀態(tài)在服務(wù)邏輯中是比較核心的角色，存儲(chǔ)系統(tǒng)必須能夠滿足這個(gè)SLA(參見后面2.2章節(jié))躯喇。這些服務(wù)必須能夠通過(guò)配置Dynamo來(lái)保證他們的低延遲和高吞吐要求辫封。因此需要在性能，效益廉丽，可用性和持久性之間做權(quán)衡取舍倦微。

其他假設(shè)：Dynamo只會(huì)被Amazon內(nèi)部服務(wù)使用。假設(shè)它的運(yùn)行環(huán)境是沒有敵意的雅倒，沒有認(rèn)證鑒權(quán)之類的安全要求璃诀。除此之外，由于每個(gè)服務(wù)都使用自己的Dynamo實(shí)例蔑匣，最初的設(shè)計(jì)是認(rèn)為Dynamo最多會(huì)擴(kuò)展到上百臺(tái)主機(jī)劣欢。 在后續(xù)章節(jié)我們會(huì)繼續(xù)討論擴(kuò)展性的限制以及可用的擴(kuò)展方案棕诵。

2.2 服務(wù)水平協(xié)議(SLA)

為了保證一個(gè)應(yīng)用程序能夠在指定的時(shí)間內(nèi)完成它的所有功能，它所依賴的每個(gè)服務(wù)則需要在更加嚴(yán)格的時(shí)間內(nèi)完成其功能凿将⌒Ｌ祝客戶端和服務(wù)端共同遵從服務(wù)水平協(xié)議，這個(gè)協(xié)議指定了一些系統(tǒng)相關(guān)的特性牧抵，其中比較重要的一點(diǎn)是笛匙，客戶端承若對(duì)指定API的請(qǐng)求量，而服務(wù)端則承諾在這個(gè)請(qǐng)求量下服務(wù)的響應(yīng)延遲犀变。舉個(gè)簡(jiǎn)單例子妹孙，服務(wù)端承若在每秒請(qǐng)求量不超過(guò)500時(shí)，保證99.9%的請(qǐng)求都可以在300ms內(nèi)響應(yīng)获枝。

在Amazon的去中心化面向服務(wù)的架構(gòu)中蠢正，SLA扮演著非常重要的角色。比如省店，當(dāng)一個(gè)頁(yè)面請(qǐng)求到達(dá)渲染引擎時(shí)嚣崭，后者往往需要向后端超過(guò)150個(gè)服務(wù)發(fā)送請(qǐng)求，才能構(gòu)建響應(yīng)的數(shù)據(jù)懦傍。這些服務(wù)又會(huì)有很多依賴雹舀，而這些依賴又是一些其他服務(wù)，因此一個(gè)應(yīng)用的調(diào)用棧往往不止一層粗俱。為了保證渲染引擎能夠在確定的時(shí)間范圍內(nèi)響應(yīng)頁(yè)面請(qǐng)求说榆，這些服務(wù)都需要嚴(yán)格遵守他們的性能約定，也就是SLA源梭。

soa.jpg

圖1是Amazon平臺(tái)架構(gòu)的一個(gè)簡(jiǎn)化描述娱俺，其中渲染組件需要向許多其他服務(wù)發(fā)起請(qǐng)求，以產(chǎn)生最終的動(dòng)態(tài)頁(yè)面內(nèi)容废麻。一個(gè)服務(wù)可以使用多種存儲(chǔ)系統(tǒng)來(lái)管理它們的狀態(tài)荠卷，并且這些存儲(chǔ)系統(tǒng)只有這個(gè)服務(wù)能夠訪問(wèn)。一些服務(wù)做著聚合的工作烛愧，通過(guò)使用幾個(gè)其他服務(wù)來(lái)產(chǎn)生一個(gè)復(fù)合的響應(yīng)油宜。這些聚合服務(wù)一般都是無(wú)狀態(tài)的，雖然他們使用了大量緩存怜姿。

業(yè)界經(jīng)常使用平均數(shù)慎冤，中位數(shù)，預(yù)期變化來(lái)描述SLA沧卢。在Amazon蚁堤，我們發(fā)現(xiàn)如果想要構(gòu)建一個(gè)讓所有用戶滿意而不是大部分用戶滿意的系統(tǒng)，這些測(cè)量方式還是不夠的但狭。比如披诗，如果為了滿足老顧客的需求而大量使用個(gè)性化的技術(shù)撬即，會(huì)影響高位分布的性能。通過(guò)中位數(shù)來(lái)描述的SLA呈队，是不能照顧到那部分重要用戶的剥槐。為了解決這個(gè)問(wèn)題，Amazon內(nèi)部都通過(guò)99.9%來(lái)表示和測(cè)量SLA宪摧。之所以選擇99.9%而不是更高粒竖，是基于成本收益的考慮，分析顯示當(dāng)進(jìn)一步提高性能時(shí)几于，耗費(fèi)的成本將會(huì)顯著提高蕊苗。從維護(hù)Amazon生產(chǎn)環(huán)境得到的經(jīng)驗(yàn)看，這種方案相比于使用中位數(shù)的SLA孩革，在整體上提供了更好的性能表現(xiàn)岁歉。

本文中多次提到99.9%分位，這反映了Amazon的工程師開始從用戶的角度來(lái)看待性能問(wèn)題膝蜈。很多論文報(bào)告都用平均數(shù)來(lái)指定SLA，本文使用了這些報(bào)告作為對(duì)比之用熔掺。然而饱搏，Amazon的工作不是針對(duì)平均數(shù)的，一些技術(shù)手段例如負(fù)載均衡置逻，完全是用來(lái)達(dá)到99.9%分位的性能目標(biāo)的推沸。

存儲(chǔ)系統(tǒng)在構(gòu)建服務(wù)的SLA中是非常重要的，特別是像大多數(shù)Amzon服務(wù)那樣券坞，業(yè)務(wù)邏輯很輕量鬓催。狀態(tài)管理就變成了服務(wù)SLA中最核心的組件。Dynamo最重要的設(shè)計(jì)考慮之一就是恨锚，讓服務(wù)能控制系統(tǒng)屬性宇驾，比如持久性、一致性猴伶，服務(wù)能夠自己在功能课舍、性能、成本收益方面做出權(quán)衡取舍他挎。

2.3 設(shè)計(jì)考慮

傳統(tǒng)商用系統(tǒng)中的數(shù)據(jù)拷貝算法通常使用同步復(fù)制的方式筝尾，以保證數(shù)據(jù)的強(qiáng)一致性。為了達(dá)到這種程度的一致性办桨，這些算法被迫在某些故障場(chǎng)景下降低可用性筹淫。比如，這些算法不會(huì)去處理結(jié)果的正確性呢撞，而是讓數(shù)據(jù)保持不可用直到確認(rèn)數(shù)據(jù)是正確的损姜。從很早的數(shù)據(jù)庫(kù)復(fù)制研究中可以看到庵寞，當(dāng)需要處理網(wǎng)絡(luò)故障的情況，強(qiáng)一致性和高可用性是不能同時(shí)做到的^[4]薛匪。因此系統(tǒng)和程序都需要了解在哪種情況下能夠達(dá)到哪種要求捐川。

對(duì)于容易出現(xiàn)服務(wù)器和網(wǎng)絡(luò)故障的系統(tǒng)，可以通過(guò)樂(lè)觀復(fù)制技術(shù)來(lái)提升可用性逸尖，在這種方式中古沥，副本的更新操作都在后臺(tái)進(jìn)行，可以容忍并發(fā)娇跟、網(wǎng)絡(luò)斷開的情形岩齿。這種方法的問(wèn)題在于它會(huì)導(dǎo)致數(shù)據(jù)沖突，而沖突是必須被檢測(cè)到并解決的苞俘。解決沖突的過(guò)程又引入兩個(gè)問(wèn)題：何時(shí)解決以及誰(shuí)來(lái)解決盹沈。Dynamo被設(shè)計(jì)為最終一致性的數(shù)據(jù)存儲(chǔ)，也就說(shuō)所有副本最終會(huì)達(dá)到一致狀態(tài)吃谣。

一個(gè)重要的設(shè)計(jì)考慮是決定何時(shí)去解決更新導(dǎo)致的沖突乞封，即，是應(yīng)該在讀還是寫的過(guò)程中解決沖突岗憋。很多傳統(tǒng)的數(shù)據(jù)存儲(chǔ)系統(tǒng)在寫的過(guò)程中處理沖突肃晚，從而保持讀操作的簡(jiǎn)單性^[5]。在這種系統(tǒng)中仔戈，如果無(wú)法在指定的時(shí)間內(nèi)將數(shù)據(jù)寫入到所有副本(或者大部分副本)中時(shí)关串，寫操作會(huì)被拒絕。另一方面监徘，Dynamo的設(shè)計(jì)目標(biāo)是一個(gè)"總是可以寫入"的數(shù)據(jù)存儲(chǔ)系統(tǒng)晋修，即，一個(gè)對(duì)寫操作來(lái)說(shuō)高可用的存儲(chǔ)凰盔。對(duì)一些Amazon的服務(wù)來(lái)說(shuō)墓卦，拒絕用戶的更新操作會(huì)導(dǎo)致很差勁的用戶體驗(yàn)。比如廊蜒，購(gòu)物車服務(wù)必須能夠讓用戶隨時(shí)的添加和刪除商品到他們的購(gòu)物車中趴拧，無(wú)論是網(wǎng)絡(luò)還是服務(wù)器出了故障。這個(gè)需求迫使我們把沖突解決的復(fù)雜性放到讀操作中處理山叮，從而保證寫操作永遠(yuǎn)不會(huì)被拒絕著榴。

接下來(lái)要考慮的是誰(shuí)來(lái)處理沖突。這個(gè)既可以讓存儲(chǔ)系統(tǒng)做屁倔，也可以讓應(yīng)用程序做脑又。如果讓存儲(chǔ)系統(tǒng)來(lái)解決沖突，它的選擇會(huì)相當(dāng)受限。這樣的情況下问麸，存儲(chǔ)系統(tǒng)只能用簡(jiǎn)單的策略來(lái)解決沖突往衷，比如"最后一個(gè)寫有效"^[6]。另一方面严卖，應(yīng)用程序了解數(shù)據(jù)的結(jié)構(gòu)席舍，它可以據(jù)此得到對(duì)用戶體驗(yàn)最好的數(shù)據(jù)沖突解決方案。比如哮笆，購(gòu)物車服務(wù)可以選擇合并沖突的數(shù)據(jù)来颤，返回一個(gè)統(tǒng)一的購(gòu)物車。盡管這樣做很靈活稠肘，但是應(yīng)用程序開發(fā)者可能不想寫自己的沖突解決方案福铅，而是將問(wèn)題推給數(shù)據(jù)存儲(chǔ)層，最終導(dǎo)致仍然使用"最后一個(gè)寫入有效"的簡(jiǎn)單策略來(lái)解決沖突项阴。

其他重要的設(shè)計(jì)考慮包括：

增量可擴(kuò)展性：Dynamo應(yīng)該能夠支持一次擴(kuò)展一個(gè)節(jié)點(diǎn)滑黔，同時(shí)最小化對(duì)操作者和系統(tǒng)的影響。

對(duì)稱性：Dynamo中的每個(gè)節(jié)點(diǎn)都應(yīng)該和其他節(jié)點(diǎn)具有相同的職責(zé)环揽；不應(yīng)該有不同的節(jié)點(diǎn)略荡，或者扮演特殊角色的節(jié)點(diǎn)。根據(jù)我們的經(jīng)驗(yàn)薯演，對(duì)稱結(jié)構(gòu)簡(jiǎn)化了系統(tǒng)的配置和維護(hù)撞芍。

去中心化：對(duì)稱性的延伸，系統(tǒng)應(yīng)該使用去中心化的P2P技術(shù)跨扮，而不是集中控制。集中控制系統(tǒng)曾經(jīng)導(dǎo)致停服验毡，我們的目標(biāo)是盡可能的避免這種情況衡创。這種設(shè)計(jì)可以得到一個(gè)更簡(jiǎn)單、更易于擴(kuò)展晶通、可用性更強(qiáng)的系統(tǒng)璃氢。

異構(gòu)性：系統(tǒng)需要有能力利用異構(gòu)的基礎(chǔ)設(shè)施。例如狮辽，工作負(fù)載必須能夠根據(jù)單個(gè)服務(wù)器的能力不同來(lái)按比例的分配一也。想要在添加高性能的新節(jié)點(diǎn)時(shí)避免升級(jí)全部的節(jié)點(diǎn)，這個(gè)能力是至關(guān)重要的喉脖。

3. 相關(guān)研究

3.1 P2P系統(tǒng)

有幾個(gè)P2P系統(tǒng)曾研究過(guò)數(shù)據(jù)的存儲(chǔ)和分布問(wèn)題椰苟。第一代P2P系統(tǒng)，比如Freenet树叽，Gnutella^[7]舆蝴，主要用作文件分享系統(tǒng)。這些都是節(jié)點(diǎn)間任意連接的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的例子。這種網(wǎng)絡(luò)中充滿了查詢請(qǐng)求洁仗，這些請(qǐng)求都盡力尋找盡可能多的共享數(shù)據(jù)節(jié)點(diǎn)层皱。P2P演化到第二代，也就是知名的結(jié)構(gòu)化P2P網(wǎng)絡(luò)赠潦。這種網(wǎng)絡(luò)使用了一個(gè)全局一致性協(xié)議叫胖，以保證任意節(jié)點(diǎn)都可以將一個(gè)查詢請(qǐng)求路由到包含需求數(shù)據(jù)的節(jié)點(diǎn)上。像Pastry^[8]和Chord^[9]之類的系統(tǒng)她奥，使用路由機(jī)制來(lái)保證查詢請(qǐng)求可以在有限的幾個(gè)網(wǎng)絡(luò)跳轉(zhuǎn)來(lái)回中得到響應(yīng)瓮增。為了減少多跳路由帶來(lái)的額外延遲，一些P2P系統(tǒng)維護(hù)了一個(gè)本地路由信息方淤，這樣它就可以在常數(shù)跳轉(zhuǎn)次數(shù)內(nèi)將請(qǐng)求路由到合適的節(jié)點(diǎn)钉赁。

各種不同的存儲(chǔ)系統(tǒng)，比如Oceanstore^[10]和PAST^[11]携茂，構(gòu)建在這些路由機(jī)制之上你踩。Oceanstore提供了一個(gè)全局的，事務(wù)的讳苦，持久性的存儲(chǔ)服務(wù)带膜，支持對(duì)大量復(fù)制數(shù)據(jù)的順序更新。為了能夠在并發(fā)更新時(shí)避免大面積鎖導(dǎo)致的問(wèn)題鸳谜，它使用了基于沖突解決的數(shù)據(jù)更新模型膝藕。引入沖突解決方案^[12]是為了減少事務(wù)失敗的次數(shù)。Oceanstore處理沖突的方式是咐扭，對(duì)一系列更新操作芭挽，確定一個(gè)最終的順序，然后按照這個(gè)順序來(lái)原子的執(zhí)行這些更新蝗肪。它是針對(duì)數(shù)據(jù)會(huì)被復(fù)制到不可信任的基礎(chǔ)設(shè)施上這種情況建立的袜爪。作為對(duì)比，PAST提供了一個(gè)構(gòu)建在Pastry之上的簡(jiǎn)單抽象層薛闪，主要用于持久性和不可變對(duì)象辛馆。它假設(shè)應(yīng)用程序可以在此基礎(chǔ)之上構(gòu)建自己所需的存儲(chǔ)語(yǔ)義(比如不可變文件)。

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

數(shù)據(jù)分布的性能豁延，可用性和持久性在文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)社區(qū)被廣泛的研究過(guò)昙篙。相比與P2P存儲(chǔ)系統(tǒng)的扁平命名空間，分布式文件系統(tǒng)能夠支持層次命名空間诱咏。像Ficus^[13]和Coda^[14]這樣的系統(tǒng)給文件做副本苔可，以一致性為代價(jià)提供高可用性。更新沖突通常由指定的沖突解決方案來(lái)處理胰苏。Farsite^[15]是一個(gè)沒有使用任何中心服務(wù)器的分布式文件系統(tǒng)硕蛹，類似于NFS醇疼。Farsite通過(guò)使用副本來(lái)達(dá)到高可用性和可擴(kuò)展性。Google文件系統(tǒng)是另外一個(gè)分布式文件系統(tǒng)法焰，主要用于存儲(chǔ)Google內(nèi)部應(yīng)用的狀態(tài)秧荆。GFS使用了一個(gè)簡(jiǎn)潔的設(shè)計(jì): 使用一個(gè)master服務(wù)器來(lái)存儲(chǔ)所有的metadata，同時(shí)文件數(shù)據(jù)被拆分為多個(gè)塊(chunk)埃仪，存儲(chǔ)在chunkserver中乙濒。Bayou是一個(gè)分布式的關(guān)系型數(shù)據(jù)庫(kù)，可以容忍網(wǎng)絡(luò)斷開的情況卵蛉，提供最終一致性^[16]颁股。

以上系統(tǒng)中，Bayou,Coda和Ficus允許網(wǎng)絡(luò)斷開下的操作傻丝，對(duì)網(wǎng)絡(luò)分裂和停運(yùn)具有彈性甘有。這些系統(tǒng)在沖突解決方案上各不相同。比如葡缰，Coda和Ficus采用了系統(tǒng)級(jí)的解決方法亏掀，而Bayou則允許應(yīng)用程序基本的解決方法。然而以上所有系統(tǒng)泛释，都提供最終一致性滤愕。和這些系統(tǒng)相似，Dynamo也允許在網(wǎng)絡(luò)分裂的情況下執(zhí)行讀寫操作怜校，同事說(shuō)使用多種機(jī)制來(lái)解決沖突间影。分布式塊存儲(chǔ)系統(tǒng)，比如FAB^[17]茄茁，將大尺寸對(duì)象拆分為多個(gè)小的塊魂贬，單獨(dú)存儲(chǔ)每個(gè)塊，并保證高可用裙顽。相比于這些系統(tǒng)随橘，key-value式存儲(chǔ)可能更合適，原因如下: (a) 主要用于存儲(chǔ)相對(duì)比較小的對(duì)象(小于1M)锦庸，(b)對(duì)應(yīng)用程序來(lái)說(shuō)，key-value式存儲(chǔ)更容易配置蒲祈。Antiquity是一個(gè)廣域的分布式存儲(chǔ)系統(tǒng)甘萧，能夠應(yīng)對(duì)多個(gè)服務(wù)器故障的情形^[18]。它使用安全日志來(lái)保證數(shù)據(jù)的完整性梆掸，這些日志被持久化記錄到多個(gè)副本扬卷，同時(shí)使用拜占庭容錯(cuò)協(xié)議來(lái)保證數(shù)據(jù)的一致性。和Antiquity不同酸钦，Dynamo不用太關(guān)注數(shù)據(jù)完整性和安全性怪得，因?yàn)樗饕糜谝粋€(gè)信任的環(huán)境。Bigtable是一個(gè)用于管理結(jié)構(gòu)化數(shù)據(jù)的分布式數(shù)據(jù)庫(kù)。它維護(hù)了一個(gè)稀疏的徒恋，多維的有序map蚕断，允許應(yīng)用程序使用多個(gè)屬性來(lái)訪問(wèn)數(shù)據(jù)^[19]。和Bigtable相比入挣，Dynamo的目標(biāo)應(yīng)用程序只需要key-value式的訪問(wèn)數(shù)據(jù)亿乳，首要關(guān)注高可用性，保證即使在網(wǎng)絡(luò)斷開和服務(wù)器故障情況下也不會(huì)拒絕更新請(qǐng)求。

傳統(tǒng)的復(fù)制型關(guān)系數(shù)據(jù)庫(kù)主要關(guān)注副本數(shù)據(jù)的強(qiáng)一致性問(wèn)題。雖然強(qiáng)一致性能讓應(yīng)用程序的編程模型非常簡(jiǎn)單扁位，但是這樣的系統(tǒng)在擴(kuò)展性和可用性方面是很受限制的^[20]耘纱。這些系統(tǒng)無(wú)法處理網(wǎng)絡(luò)分裂的情形，因?yàn)樗麄兺ǔＬ峁?qiáng)一致性保證窒篱。

3.3 討論

由于目標(biāo)需求不同，Dynamo和上述的去中心化存儲(chǔ)系統(tǒng)都不相同。首先带斑，Dynamo的目標(biāo)應(yīng)用程序需要一個(gè)"永遠(yuǎn)可寫"的數(shù)據(jù)存儲(chǔ)，即使在故障和并發(fā)寫的情況下酿雪，也不會(huì)拒絕更新請(qǐng)求遏暴。第二，如上面提到的指黎，Dynano被假設(shè)構(gòu)建在一個(gè)單獨(dú)的環(huán)境中朋凉，其中每個(gè)節(jié)點(diǎn)都是可信任的。第三醋安，使用Dynamo的應(yīng)用程序并不需要層次命名空間(類似于文件系統(tǒng))和數(shù)據(jù)結(jié)構(gòu)schema(關(guān)系型數(shù)據(jù)庫(kù))杂彭。第四，Dynamo的目標(biāo)應(yīng)用程序都與延遲敏感吓揪，需要至少99.9%的請(qǐng)求能夠在幾百ms內(nèi)完成亲怠。為了滿足延遲的需求，我們必須避免在多個(gè)節(jié)點(diǎn)間進(jìn)行請(qǐng)求路由(這是一些基于hash的分布式系統(tǒng)典型做法柠辞，如Chord和Pastry)团秽。這是因?yàn)槎啻温酚稍黾恿隧憫?yīng)次數(shù)，從而提高了整體響應(yīng)耗時(shí)叭首。Dynamo可以認(rèn)為是一個(gè)零跳(zero-hop)的分布式hash表(DHT)习勤，其中每個(gè)節(jié)點(diǎn)都在本地維護(hù)了足夠的路由信息，從而使得請(qǐng)求可以一次就轉(zhuǎn)發(fā)到合適的節(jié)點(diǎn)上焙格。

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

一個(gè)能夠在生產(chǎn)環(huán)境中工作的存儲(chǔ)系統(tǒng)的架構(gòu)是比較復(fù)雜的图毕。除了數(shù)據(jù)持久化組件之外，系統(tǒng)還需要在復(fù)制均衡眷唉，成員管理予颤，故障探測(cè)囤官，副本同步，過(guò)載處理蛤虐，狀態(tài)遷移党饮，并發(fā)，任務(wù)調(diào)度笆焰，請(qǐng)求編組劫谅，請(qǐng)求路由，系統(tǒng)監(jiān)控和告警嚷掠，配置管理這些方面做到可擴(kuò)展和健壯捏检。討論所有這些解決方案的細(xì)節(jié)是不可能的，因此本文將主要關(guān)注Dynamo中使用的核心分布式系統(tǒng)技術(shù)：分片不皆，復(fù)制贯城，版本，成員管理霹娄，故障處理能犯，擴(kuò)展。

tech_in_d.jpg

表 1展示了Dynamo使用的技術(shù)以及它們各自的優(yōu)勢(shì)

4.1 系統(tǒng)接口

Dynamo使用一個(gè)簡(jiǎn)單的接口來(lái)存儲(chǔ)對(duì)象犬耻，這些對(duì)象都通過(guò)一個(gè)key關(guān)聯(lián)起來(lái)踩晶；它暴露了兩種操作：get()和put()。get(key)操作會(huì)定位key所關(guān)聯(lián)的對(duì)象副本所在位置枕磁，然后返回這個(gè)對(duì)象渡蜻，或者返回一個(gè)對(duì)象列表，其中包括沖突的版本以及上下文计济。put(key, context, object)操作通過(guò)key來(lái)決定應(yīng)該把object放在哪些位置茸苇，然后將副本寫入硬盤。上下文包括了對(duì)調(diào)用方不透明的對(duì)象元數(shù)據(jù)沦寂，以及一些其他信息学密，比如對(duì)象的版本。上下文信息和object存儲(chǔ)在一起传藏，這樣能夠讓系統(tǒng)在處理put請(qǐng)求時(shí)驗(yàn)證上下文的有效性腻暮。

Dynamo將調(diào)用方提供的key和object看作是不透明的字節(jié)數(shù)組。它對(duì)key進(jìn)行MD5哈希運(yùn)算毯侦，得到一個(gè)128位的標(biāo)識(shí)符西壮，通過(guò)這個(gè)標(biāo)識(shí)符來(lái)決定哪些節(jié)點(diǎn)應(yīng)該對(duì)這個(gè)key負(fù)責(zé)。

4.2 分片算法

Dynamo的核心需求之一是它必須能夠支持增量擴(kuò)展叫惊。這需要一個(gè)機(jī)制能夠動(dòng)態(tài)的將數(shù)據(jù)分布到系統(tǒng)中的節(jié)點(diǎn)上。Dynamo的分片方案依賴于一致性哈希將數(shù)據(jù)分布到多個(gè)存儲(chǔ)節(jié)點(diǎn)上做修。在一致性哈希^[21]中霍狰，哈希函數(shù)的輸出范圍被當(dāng)作一個(gè)固定的圓形空間抡草，或者一個(gè)環(huán)(hash的最大值和最小值連接)。系統(tǒng)中的每個(gè)節(jié)點(diǎn)都被隨機(jī)分配到這個(gè)環(huán)上的某個(gè)位置蔗坯。每條數(shù)據(jù)都按照以下方式被分配到一個(gè)節(jié)點(diǎn)：先計(jì)算這個(gè)數(shù)據(jù)key的hash值康震，將hash值映射到環(huán)上，然后在環(huán)上順時(shí)針尋找第一個(gè)節(jié)點(diǎn)宾濒。這樣每個(gè)節(jié)點(diǎn)都只需要對(duì)上一個(gè)節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)之間的區(qū)間負(fù)責(zé)腿短。一致性hash的好處是，一個(gè)節(jié)點(diǎn)的進(jìn)入和退出都只影響它鄰近的節(jié)點(diǎn)绘梦，而其他的節(jié)點(diǎn)不會(huì)收到影響橘忱。

基本的一致性哈希算法帶來(lái)了一些問(wèn)題。首先卸奉，節(jié)點(diǎn)被隨機(jī)的分片到環(huán)上钝诚，這會(huì)導(dǎo)致數(shù)據(jù)和壓力分布不均勻。第二榄棵，基本算法忽視了各個(gè)節(jié)點(diǎn)間的不同凝颇。為了解決這些問(wèn)題，Dynamo使用了一致性哈希的一個(gè)變體(和附錄^[22]中的相似)疹鳄；每個(gè)節(jié)點(diǎn)映射到哈希環(huán)上的多個(gè)節(jié)點(diǎn)拧略，而不是一個(gè)節(jié)點(diǎn)上。為此瘪弓，Dynamo使用了"虛擬節(jié)點(diǎn)"的概念垫蛆。一個(gè)虛擬節(jié)點(diǎn)看上去就像系統(tǒng)中的一個(gè)節(jié)點(diǎn)，但是每個(gè)節(jié)點(diǎn)可以對(duì)應(yīng)多個(gè)虛擬節(jié)點(diǎn)杠茬。當(dāng)一個(gè)節(jié)點(diǎn)添加到系統(tǒng)中時(shí)月褥，它被分配到哈希環(huán)上的多個(gè)位置(后面稱作tokens)。第六章會(huì)討論Dynamo中微調(diào)分片方案的過(guò)程瓢喉。

使用虛擬節(jié)點(diǎn)有以下好處：

• 如果一個(gè)節(jié)點(diǎn)不可用了(故障或者路由問(wèn)題)宁赤，這個(gè)節(jié)點(diǎn)的壓力會(huì)平均的分配到其他可用的節(jié)點(diǎn)上
• 當(dāng)故障節(jié)點(diǎn)恢復(fù)可用，或者一個(gè)新節(jié)點(diǎn)加入到系統(tǒng)中栓票，其他各個(gè)節(jié)點(diǎn)會(huì)分配大致相同的壓力給新節(jié)點(diǎn)
• 一個(gè)節(jié)點(diǎn)負(fù)責(zé)的虛擬節(jié)點(diǎn)個(gè)數(shù)可以根據(jù)節(jié)點(diǎn)的能力决左，即基礎(chǔ)設(shè)施狀態(tài)，來(lái)確定走贪。

4.3 復(fù)制

為了達(dá)到高可用性和持久性佛猛，Dynamo將數(shù)據(jù)復(fù)制到多個(gè)服務(wù)器上。每條數(shù)據(jù)被復(fù)制到N個(gè)服務(wù)器上坠狡，其中N由配置項(xiàng)"per-instance"指定继找。每個(gè)key，k逃沿，被分配給協(xié)調(diào)節(jié)點(diǎn)(下一節(jié)說(shuō)明)婴渡。協(xié)調(diào)者負(fù)責(zé)落到它的范圍中的數(shù)據(jù)的復(fù)制幻锁。協(xié)調(diào)者除了將落到自己的范圍中的數(shù)據(jù)存儲(chǔ)在本地之外，還要將這些數(shù)據(jù)存儲(chǔ)在后續(xù)N-1個(gè)節(jié)點(diǎn)上边臼，也就是哈希環(huán)上順時(shí)針?lè)较蚝罄m(xù)N-1個(gè)節(jié)點(diǎn)哄尔。這導(dǎo)致系統(tǒng)中的每個(gè)節(jié)點(diǎn)都需要負(fù)責(zé)從它自己到后續(xù)第N個(gè)節(jié)點(diǎn)的范圍。在圖2中柠并，節(jié)點(diǎn)B除了k存儲(chǔ)在本地之外岭接，還將k復(fù)制到節(jié)點(diǎn)C和D。節(jié)點(diǎn)D會(huì)存儲(chǔ)落到(A,B], (B,C], (C,D]范圍內(nèi)的key臼予。

node.png

用于存儲(chǔ)某個(gè)指定key的節(jié)點(diǎn)列表被稱作首選列表(preference list)鸣戴。在第4.8節(jié)中將會(huì)說(shuō)明，系統(tǒng)被設(shè)計(jì)為瘟栖，每個(gè)節(jié)點(diǎn)都可以知道任意key的首選列表包括哪些節(jié)點(diǎn)葵擎。考慮到節(jié)點(diǎn)故障半哟，首選列表中的節(jié)點(diǎn)數(shù)會(huì)大于N酬滤。需要注意到，由于使用了虛擬節(jié)點(diǎn)寓涨，對(duì)某個(gè)指定key盯串，前N個(gè)后續(xù)節(jié)點(diǎn)可能被少于N個(gè)不同的物理節(jié)點(diǎn)擁有(一個(gè)節(jié)點(diǎn)可能對(duì)應(yīng)這個(gè)N個(gè)節(jié)點(diǎn)中的多個(gè))。為了解決這個(gè)問(wèn)題戒良，在構(gòu)建一個(gè)key的首選列表時(shí)体捏，可能會(huì)跳過(guò)一些節(jié)點(diǎn)，導(dǎo)致首選列表是一個(gè)不連續(xù)的列表糯崎，從而保證列表中只包含不同的物理節(jié)點(diǎn)几缭。

4.4 數(shù)據(jù)版本

Dynamo提供最終一致性，允許數(shù)據(jù)更新異步的傳播到各個(gè)副本上沃呢。put操作可能在更新同步到所有副本之前就返回了年栓，這會(huì)導(dǎo)致后續(xù)的get()操作得不到最新的數(shù)據(jù)。如果沒有故障薄霜，所有副本的更新有確定的時(shí)間范圍某抓。然而，在故障的情形下(比如服務(wù)器宕機(jī)或者網(wǎng)絡(luò)斷開)惰瓜，即使在更長(zhǎng)的時(shí)間內(nèi)否副，更新也可能沒有到達(dá)所有的副本。

Amazon平臺(tái)上有一類應(yīng)用可以容忍這種不一致崎坊，并且能夠在這種情況下工作备禀。比如，購(gòu)物車服務(wù)需要保證"添加到購(gòu)物車"操作永遠(yuǎn)不會(huì)被拒絕或者遺忘。如果購(gòu)物車最新狀態(tài)是不可用的痹届，用戶就將在老版本的購(gòu)物車上進(jìn)行更改呻待，這些更改仍然是有意義并且應(yīng)該被保留的。但同時(shí)队腐，購(gòu)物車的這個(gè)狀態(tài)不應(yīng)該確定當(dāng)前不可用的狀態(tài)，因?yàn)椴豢捎玫臓顟B(tài)可能包含一些應(yīng)該保留的更改奏篙。注意到柴淘，"添加到購(gòu)物車"和"從購(gòu)物車刪除"操作都被轉(zhuǎn)化為Dynamo的put請(qǐng)求。當(dāng)用戶向購(gòu)物車中添加商品秘通，同時(shí)購(gòu)物車最新狀態(tài)是不可用的为严，那么這些商品就會(huì)被添加到一個(gè)老的版本中，狀態(tài)的分歧在之后再進(jìn)行解決肺稀。

為了保證這一點(diǎn)第股，Dynamo將每次修改都看作是數(shù)據(jù)的一個(gè)新的，不可更改的版本话原。它允許一個(gè)對(duì)象的多個(gè)版本同時(shí)出現(xiàn)在系統(tǒng)中夕吻。大部分情況下，新版本會(huì)合并到舊版本之外繁仁，并且系統(tǒng)能夠判斷哪個(gè)版本是權(quán)威版本涉馅。然而，版本分叉是可能出現(xiàn)的黄虱，當(dāng)遇到故障或者并發(fā)更新時(shí)稚矿，就可能導(dǎo)致對(duì)象的多個(gè)沖突版本。這種情況下捻浦，系統(tǒng)無(wú)法解決同一對(duì)象的多個(gè)版本沖突晤揣，必須由客戶端來(lái)解決這些沖突，將多個(gè)版本重新合并回一個(gè)版本朱灿。使用這種機(jī)制昧识，"添加到購(gòu)物車"操作永遠(yuǎn)不會(huì)丟失，但是刪除的商品可能會(huì)再次出現(xiàn)母剥。

一些故障情形可能會(huì)導(dǎo)致系統(tǒng)中一個(gè)數(shù)據(jù)出現(xiàn)多于兩個(gè)的不同版本滞诺，理解這一點(diǎn)非常重要。在節(jié)點(diǎn)故障环疼，網(wǎng)絡(luò)斷開時(shí)進(jìn)行更新习霹，可能會(huì)導(dǎo)致一個(gè)對(duì)象出現(xiàn)多個(gè)版本，系統(tǒng)需要在后續(xù)解決這些沖突炫隶。這導(dǎo)致我們需要設(shè)計(jì)應(yīng)用程序的時(shí)候淋叶，必須讓它能夠應(yīng)對(duì)一份數(shù)據(jù)可能出現(xiàn)多個(gè)版本的情況(從而不會(huì)丟失任何更新)。

Dynamo使用矢量鐘(vector clocks)^[23]來(lái)確定同一數(shù)據(jù)的多個(gè)版本之間的因果關(guān)系伪阶。矢量鐘是一個(gè)(節(jié)點(diǎn)煞檩，計(jì)數(shù)器)的列表处嫌。一個(gè)矢量鐘和任意對(duì)象的每個(gè)版本關(guān)聯(lián)著。通過(guò)檢查矢量鐘斟湃，可以決定一個(gè)對(duì)象的兩個(gè)版本是并行關(guān)系還是有一個(gè)先后順序熏迹。如果第一個(gè)對(duì)象矢量鐘上的計(jì)數(shù)器值小于等于第二個(gè)對(duì)象矢量鐘上的所有計(jì)數(shù)器，那么第一個(gè)對(duì)象就是第二個(gè)對(duì)象的祖先凝赛，可以被丟掉注暗。否則的話，這兩個(gè)對(duì)象版本就被認(rèn)為是沖突的墓猎，需求協(xié)調(diào)解決捆昏。

在Dynamo中，如果客戶端想要更新一個(gè)對(duì)象毙沾，它必須指定它要更新的版本骗卜。通過(guò)傳遞上下文來(lái)指定，上下文是在之前的讀操作中獲取的左胞，其中包括了一個(gè)矢量鐘寇仓。在處理讀請(qǐng)求時(shí)，如果出現(xiàn)一個(gè)對(duì)象有多個(gè)版本罩句，而Dynamo無(wú)法決定哪個(gè)版本有效時(shí)焚刺，它會(huì)將對(duì)象所有版本連同上下文信息都返回給調(diào)用方。如果更新請(qǐng)求中帶有上下文门烂，說(shuō)明客戶端剛剛解決了沖突乳愉，對(duì)象所有的版本分支將會(huì)合并為一個(gè)。

vector.jpg

為了說(shuō)明矢量種的機(jī)制屯远，考慮圖3中的例子蔓姚。客戶端寫入一個(gè)新的對(duì)象慨丐，節(jié)點(diǎn)Sx處理這個(gè)寫請(qǐng)求坡脐，并用自增序列號(hào)來(lái)構(gòu)建這個(gè)對(duì)象的矢量鐘。現(xiàn)在系統(tǒng)中有一個(gè)對(duì)象D1房揭，它的矢量鐘是[(Sx,1)]备闲。接著客戶端更新了這個(gè)對(duì)象，假設(shè)仍然是節(jié)點(diǎn)Sx處理這個(gè)請(qǐng)求⊥北現(xiàn)在系統(tǒng)中有了對(duì)象D2以及它的矢量鐘[(Sx,2)]恬砂。D2來(lái)自D1，因此它覆蓋了D1蓬痒，然而可能有一些D1的副本還沒有看到D2(譯注:這句話本身沒有錯(cuò)泻骤，但是對(duì)比圖3，會(huì)造成一些混淆)。假設(shè)此時(shí)客戶端又發(fā)起一次更新請(qǐng)求狱掂，另一個(gè)節(jié)點(diǎn)Sy處理了這個(gè)請(qǐng)求演痒。此時(shí)系統(tǒng)中有了數(shù)據(jù)D3，它的矢量鐘是[(Sx,2), (Sy,1)]趋惨。

接下來(lái)鸟顺，假設(shè)客戶端讀取到了D2然后要更新它，另一個(gè)節(jié)點(diǎn)Sz處理了這個(gè)寫請(qǐng)求器虾。此時(shí)系統(tǒng)中有了D4诊沪，它的版本矢量鐘是[(Sx,2), (Sz,1)]。如果一個(gè)節(jié)點(diǎn)能夠知道D1和D2曾撤，那么如果他收到了D4以及它的矢量鐘，那么這個(gè)節(jié)點(diǎn)可以決定D1和D2都會(huì)被新的數(shù)據(jù)覆蓋晕粪，因此可以回收了挤悉。如果一個(gè)節(jié)點(diǎn)知道D3，然后又收到了D4巫湘，那么這個(gè)節(jié)點(diǎn)將無(wú)法判斷這兩個(gè)數(shù)據(jù)的關(guān)系装悲。換句話說(shuō)，D3和D4中包含了對(duì)方不了解的更新尚氛。這兩個(gè)版本的數(shù)據(jù)都必須保留下來(lái)诀诊，并在處理讀請(qǐng)求時(shí)返回給客戶端，由客戶端來(lái)解決沖突阅嘶。

現(xiàn)在假設(shè)某個(gè)客戶端讀到了D3和D4(上下文會(huì)反映出兩個(gè)值都被讀到了)属瓣。讀到的上下文是D3和D4的矢量鐘的結(jié)合，也就是[(Sx,2), (Sy,1), (Sz,1)]讯柔。如果客戶端處理了沖突抡蛙，節(jié)點(diǎn)Sx處理了寫操作魂迄，Sx會(huì)更新它的矢量鐘的序號(hào)粗截。新的數(shù)據(jù)D5的矢量鐘如下:[(Sx,3), (Sy,1), (Sz,1)]。

矢量鐘可能出現(xiàn)的一個(gè)問(wèn)題是捣炬，如果很多個(gè)服務(wù)器處理了對(duì)同一個(gè)對(duì)象的更新操作熊昌，那么矢量鐘的長(zhǎng)度可能會(huì)持續(xù)增大。在實(shí)際中湿酸，這個(gè)問(wèn)題不太可能出現(xiàn)婿屹，因?yàn)閷懖僮骰径际潜皇走x列表的前N個(gè)節(jié)點(diǎn)處理了。在網(wǎng)絡(luò)斷開和多個(gè)服務(wù)器故障的情況下稿械，寫操作可能不會(huì)被首選列表中的節(jié)點(diǎn)處理选泻，這會(huì)導(dǎo)致矢量鐘的長(zhǎng)度增大。為了應(yīng)對(duì)這個(gè)問(wèn)題，Dynamo使用了如下的矢量鐘截?cái)喾桨福簩?duì)每個(gè)(節(jié)點(diǎn)页眯，計(jì)數(shù))對(duì)梯捕，Dynamo同時(shí)存儲(chǔ)了一個(gè)時(shí)間戳，記錄了最近一次當(dāng)前節(jié)點(diǎn)更新數(shù)據(jù)的時(shí)間窝撵。當(dāng)矢量鐘的(節(jié)點(diǎn)傀顾，計(jì)數(shù))根數(shù)到達(dá)閾值(比如10個(gè))的時(shí)候，最舊的數(shù)據(jù)將會(huì)被刪除碌奉。很明顯這種截?cái)喾绞綍?huì)導(dǎo)致解決沖突時(shí)效率低下短曾，因?yàn)闊o(wú)法得到準(zhǔn)確的后續(xù)信息。然而在生產(chǎn)環(huán)境中沒有出現(xiàn)過(guò)問(wèn)題赐劣，因此這個(gè)問(wèn)題還沒有徹底研究嫉拐。

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

Dynamo中的任意節(jié)點(diǎn)都可以接收客戶對(duì)任意key的get和put操作請(qǐng)求。為了簡(jiǎn)潔起見魁兼，本節(jié)將會(huì)描述在沒有故障的環(huán)境中這些操作時(shí)如何處理的婉徘，后續(xù)章節(jié)我們會(huì)講解在故障的時(shí)候讀寫操作是如何執(zhí)行的。

讀寫請(qǐng)求都是通過(guò)HTTP協(xié)議咐汞，使用Amazon特定基礎(chǔ)設(shè)施的請(qǐng)求處理框架來(lái)調(diào)用的盖呼。客戶端有兩個(gè)選擇節(jié)點(diǎn)的策略可選：(1)使用另一個(gè)通用的負(fù)責(zé)均衡器來(lái)路由請(qǐng)求化撕，這將根據(jù)負(fù)載信息選擇一個(gè)節(jié)點(diǎn)几晤，(2)使用一個(gè)了解分片信息的客戶端程序庫(kù)，這將直接將請(qǐng)求路由到合適的協(xié)調(diào)節(jié)點(diǎn)植阴。第一個(gè)策略的好處是客戶端不需要鏈接任何Dynamo特定的代碼到應(yīng)用程序中蟹瘾，第二個(gè)策略的好處是可以跳過(guò)一次潛在的轉(zhuǎn)發(fā)，從而延遲更低墙贱。

處理讀寫操作的節(jié)點(diǎn)叫做協(xié)調(diào)者(coordinator)热芹。典型的，這個(gè)節(jié)點(diǎn)是首選列表前N個(gè)中的第一個(gè)惨撇。如果請(qǐng)求是通過(guò)一個(gè)負(fù)載均衡器發(fā)送的伊脓，那么請(qǐng)求可能會(huì)落到哈希環(huán)的一個(gè)隨機(jī)節(jié)點(diǎn)上。這種情形下魁衙，如果這個(gè)節(jié)點(diǎn)不是首選列表前N個(gè)中的一個(gè)报腔，它不會(huì)處理這個(gè)請(qǐng)求，而是把請(qǐng)求轉(zhuǎn)發(fā)給首選列表前N個(gè)中的第一個(gè)節(jié)點(diǎn)剖淀。

讀寫操作只會(huì)涉及到首選列表中前N個(gè)健康的節(jié)點(diǎn)纯蛾，會(huì)跳過(guò)那些故障或者無(wú)法訪問(wèn)的節(jié)點(diǎn)。如果所有的節(jié)點(diǎn)都是健康的纵隔，key所對(duì)應(yīng)的首選列表中前N個(gè)節(jié)點(diǎn)都會(huì)被訪問(wèn)到翻诉。如果有節(jié)點(diǎn)故障或者網(wǎng)絡(luò)斷開問(wèn)題炮姨，首選列表中靠后的節(jié)點(diǎn)也會(huì)被訪問(wèn)到。

為了維持副本之間的一致性碰煌，Dynamo使用了一個(gè)類似于仲裁系統(tǒng)的一致性協(xié)議舒岸。這個(gè)協(xié)議有兩個(gè)關(guān)鍵配置值：R和W。R是指一次成功的讀操作中參與節(jié)點(diǎn)的最少個(gè)數(shù)。W是指一次成功的寫操作中參與節(jié)點(diǎn)的最少個(gè)數(shù)。設(shè)置R和W以滿足R + W > n愚隧，就產(chǎn)生了一個(gè)仲裁系統(tǒng)。在這個(gè)模型中洪乍，一次讀寫操作的延遲取決于R(W)中最慢的那個(gè)副本。由于這個(gè)原因夜焦，R和W一般被配置為小于N壳澳，以提供更好的延遲。

當(dāng)收到對(duì)一個(gè)key的put操作時(shí)茫经，協(xié)調(diào)節(jié)點(diǎn)產(chǎn)生新版本數(shù)據(jù)的矢量鐘并在本地記錄這個(gè)版本钾埂。然后協(xié)調(diào)節(jié)點(diǎn)將新版本信息(以及最新的矢量鐘)發(fā)送給前N個(gè)可以連接到的節(jié)點(diǎn)。如果有W-1或更多個(gè)節(jié)點(diǎn)響應(yīng)了科平，那么這個(gè)寫操作就被認(rèn)為是成功的。

類似的姜性，對(duì)于get請(qǐng)求瞪慧，協(xié)調(diào)者會(huì)請(qǐng)求首選列表中的前N個(gè)節(jié)點(diǎn)以獲取這個(gè)key的所有版本，然后等待R個(gè)節(jié)點(diǎn)響應(yīng)部念，之后才能返回結(jié)果給客戶端弃酌。如果協(xié)調(diào)者最后聚集了數(shù)據(jù)的多個(gè)版本，它會(huì)返回它認(rèn)為沒有因果關(guān)系的多個(gè)版本儡炼。這些不同的版本會(huì)被客戶端協(xié)調(diào)解決沖突妓湘，然后協(xié)調(diào)后的版本會(huì)代替當(dāng)前版本，并寫回到節(jié)點(diǎn)中乌询。

4.6 處理故障: 暗示移交((Hinted Handoff)

如果Dynamo使用傳統(tǒng)的仲裁方案榜贴，那么當(dāng)出現(xiàn)服務(wù)器故障或網(wǎng)絡(luò)斷開的情況時(shí)，它就是不可用的 妹田，并且在最簡(jiǎn)單的故障情形下也會(huì)降低持久性唬党。為了補(bǔ)救這一點(diǎn)，Dynamo沒有使用嚴(yán)格的仲裁協(xié)議鬼佣，而是使用了"馬虎仲裁(sloppy quorum)"驶拱。所有的讀寫操作都在首選列表的前N個(gè)健康節(jié)點(diǎn)上進(jìn)行，有可能不是在哈希環(huán)上順時(shí)針遍歷時(shí)遇到的前N個(gè)節(jié)點(diǎn)晶衷。

考慮圖2中的例子蓝纲，Dynamo被配置為N=3阴孟。這個(gè)例子中，如果在寫操作的處理中税迷，節(jié)點(diǎn)A暫時(shí)的故障或無(wú)法訪問(wèn)了永丝，那么本來(lái)應(yīng)該在節(jié)點(diǎn)A上的數(shù)據(jù)副本會(huì)被發(fā)送到節(jié)點(diǎn)D上。這樣做是為了滿足可用性和持久性的保證翁狐。發(fā)送到節(jié)點(diǎn)D上的數(shù)據(jù)副本的元信息中會(huì)有一個(gè)暗示(hint)类溢，說(shuō)明這個(gè)數(shù)據(jù)副本本來(lái)應(yīng)該是在那個(gè)節(jié)點(diǎn)上(此處是節(jié)點(diǎn)A)。收到暗示副本的節(jié)點(diǎn)會(huì)把它們存儲(chǔ)在一個(gè)隔離的本地?cái)?shù)據(jù)庫(kù)中露懒，并且周期性的掃描闯冷，當(dāng)檢測(cè)到節(jié)點(diǎn)A恢復(fù)了，節(jié)點(diǎn)D就會(huì)嘗試把這個(gè)數(shù)據(jù)副本發(fā)送給節(jié)點(diǎn)A懈词。一旦發(fā)送成功了蛇耀，節(jié)點(diǎn)D就會(huì)從本地存儲(chǔ)中刪除這個(gè)副本，同時(shí)并不會(huì)減少系統(tǒng)中副本的數(shù)量坎弯。

使用暗示移交纺涤，Dynamo可以保證讀寫操作都不會(huì)因?yàn)闀簳r(shí)的故障或網(wǎng)絡(luò)問(wèn)題而失敗。對(duì)可用性要求比較高的應(yīng)用可以將W設(shè)置為1抠忘，這樣可以保證撩炊，在處理寫請(qǐng)求時(shí)只要系統(tǒng)中有一個(gè)節(jié)點(diǎn)將數(shù)據(jù)寫入到本地存儲(chǔ)，寫請(qǐng)求就能成功返回崎脉。因此拧咳，只有在系統(tǒng)中所有節(jié)點(diǎn)都不可用時(shí)，寫請(qǐng)求才會(huì)被拒絕囚灼。然而在實(shí)際中骆膝，大部分Amzon應(yīng)用在生產(chǎn)環(huán)境中會(huì)設(shè)置一個(gè)較高的W，為了達(dá)到需要的持久性灶体。第6章會(huì)更詳細(xì)地討論N阅签，R和W的設(shè)置。

一個(gè)高可用存儲(chǔ)系統(tǒng)具有應(yīng)對(duì)整個(gè)數(shù)據(jù)中心故障的能力是非常重要的蝎抽。由于斷電政钟，冷卻系統(tǒng)故障，網(wǎng)絡(luò)錯(cuò)誤以及自然災(zāi)害樟结，數(shù)據(jù)中心可能出現(xiàn)故障锥涕。Dynamo被配置為每個(gè)對(duì)象都在多個(gè)數(shù)據(jù)中心存儲(chǔ)副本。本質(zhì)上說(shuō)狭吼，一個(gè)key的首選列表被設(shè)計(jì)為层坠，其中的存儲(chǔ)節(jié)點(diǎn)分布在不同的數(shù)據(jù)中心。這些數(shù)據(jù)中心通過(guò)高速網(wǎng)絡(luò)進(jìn)行連接刁笙。這種在多數(shù)據(jù)中心分布副本的方案使得我們能夠應(yīng)對(duì)單個(gè)數(shù)據(jù)中的故障破花，保證數(shù)據(jù)服務(wù)持續(xù)運(yùn)行谦趣。

4.7 處理永久故障：副本同步

在系統(tǒng)成員變化很少，節(jié)點(diǎn)只會(huì)短租故障的情況下座每，暗示移交能夠工作的很好前鹅。但是也會(huì)有這樣的場(chǎng)景，暗示副本在它們寫回到原來(lái)的節(jié)點(diǎn)之前就不可用了峭梳。為了處理這種情況以及其他對(duì)持久性的威脅舰绘，Dynamo實(shí)現(xiàn)了一個(gè)逆熵(anti-entropy，副本同步)協(xié)議來(lái)保持副本之間的同步葱椭。

為了快速檢測(cè)出副本間的不一致捂寿，同時(shí)最小化傳輸?shù)臄?shù)據(jù)量，Dynamo使用Merkle樹^[24]孵运。Merkle樹是一個(gè)哈希樹秦陋，它的葉子節(jié)點(diǎn)是一些單獨(dú)的key的哈希值，父節(jié)點(diǎn)是它自己子節(jié)點(diǎn)的哈希值治笨。Merkle樹的一個(gè)主要好處是驳概，樹中的每一條分支都可以單獨(dú)的檢測(cè)，而不需要把整棵樹的所有數(shù)據(jù)都下載下來(lái)旷赖。此外顺又，在檢測(cè)到副本之間不一致時(shí)，減少需要傳輸?shù)臄?shù)據(jù)量這一點(diǎn)上等孵，Merkle樹也有幫助待榔。比如，如果兩個(gè)Merkle樹的根節(jié)點(diǎn)值是一樣的流济，那么所有的葉子節(jié)點(diǎn)的值也是相同的。如果不是腌闯，那就說(shuō)明有些副本的值不一樣绳瘟。這種情況下，節(jié)點(diǎn)之間可以交換根節(jié)點(diǎn)的子節(jié)點(diǎn)的哈希值進(jìn)行比較姿骏，如此執(zhí)行直到葉子節(jié)點(diǎn)糖声，此時(shí)會(huì)發(fā)現(xiàn)某兩個(gè)key是"不同步"的。Merkle樹最小化了為同步而需要傳輸?shù)臄?shù)據(jù)量分瘦，同時(shí)減少了在整個(gè)逆熵過(guò)程中讀取磁盤的次數(shù)蘸泻。

Dynamo按照如下方式在逆熵中使用Merkle樹：每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)單獨(dú)的Merkle樹，這棵樹中包括了當(dāng)前節(jié)點(diǎn)處理的key范圍中所有的key嘲玫。這可以讓節(jié)點(diǎn)間進(jìn)行比較從而了解范圍內(nèi)的key是否是最新的悦施。這種方案中，兩個(gè)節(jié)點(diǎn)根據(jù)他們共同處理的key范圍來(lái)交換相應(yīng)的Merkle樹根節(jié)點(diǎn)去团。接著使用上面描述的遍歷樹的方案來(lái)決定它們是否有不同的地方抡诞，然后進(jìn)行相應(yīng)的同步處理穷蛹。這個(gè)方案的劣勢(shì)在于，在節(jié)點(diǎn)進(jìn)入和離開系統(tǒng)時(shí)昼汗，很多key范圍會(huì)變化肴熏，因此Merkle樹需要重新計(jì)算。第6.2節(jié)中描述了一種更精巧的分片方案顷窒，解決了這個(gè)問(wèn)題蛙吏。

4.8 成員關(guān)系和故障檢測(cè)

4.8.1 環(huán)成員關(guān)系

在Amazon的環(huán)境中，節(jié)點(diǎn)停服往往都是暫時(shí)的鞋吉，但是可能會(huì)持續(xù)一小會(huì)鸦做。一個(gè)節(jié)點(diǎn)的停服很少意味著永久退出系統(tǒng)，因此不會(huì)導(dǎo)致重新分布數(shù)據(jù)或者修復(fù)不可訪問(wèn)的副本坯辩。類似的馁龟，人為失誤可能導(dǎo)致非預(yù)期的加入新節(jié)點(diǎn)到系統(tǒng)中。由于這些原因漆魔，使用一種顯式的機(jī)制來(lái)初始化新節(jié)點(diǎn)和刪除節(jié)點(diǎn)被認(rèn)為是合適的坷檩。管理員使用一個(gè)命令行工具或者瀏覽器來(lái)連接到Dynamo并發(fā)起一個(gè)成員關(guān)系的變更，從哈希環(huán)中刪除或者添加一個(gè)節(jié)點(diǎn)改抡。處理變更請(qǐng)求的節(jié)點(diǎn)將成員關(guān)系的變更以及發(fā)生的時(shí)間寫入到持久化存儲(chǔ)中矢炼。成員關(guān)系的變更形成了一個(gè)歷史記錄，因?yàn)楣?jié)點(diǎn)可以多次的刪除和添加到系統(tǒng)中阿纤。一個(gè)基于gossip的協(xié)議在節(jié)點(diǎn)之間傳播變更信息句灌，維持成員關(guān)系的最終一致性。
每個(gè)節(jié)點(diǎn)每秒鐘和另外一個(gè)隨機(jī)選擇的節(jié)點(diǎn)進(jìn)行通信欠拾，兩個(gè)節(jié)點(diǎn)交換他們的成員關(guān)系變更歷史胰锌。

一個(gè)節(jié)點(diǎn)初次啟動(dòng)時(shí)，它會(huì)選擇虛擬節(jié)點(diǎn)并將虛擬節(jié)點(diǎn)映射到哈希環(huán)上各自相應(yīng)的范圍藐窄。這個(gè)映射關(guān)系會(huì)持久化到硬盤上资昧，并且一開始的時(shí)候只包括當(dāng)前節(jié)點(diǎn)的映射信息。系統(tǒng)中其他節(jié)點(diǎn)的映射信息在后續(xù)的同步變更歷史時(shí)會(huì)逐步完善荆忍。因此格带，分片和位置信息也是通過(guò)基于gossip的協(xié)議進(jìn)行傳播，系統(tǒng)中每個(gè)存儲(chǔ)節(jié)點(diǎn)都知道其他所有節(jié)點(diǎn)的虛擬節(jié)點(diǎn)映射關(guān)系刹枉。這就使得每個(gè)節(jié)點(diǎn)都可以將一個(gè)key的讀寫請(qǐng)求直接轉(zhuǎn)發(fā)到正確的節(jié)點(diǎn)上叽唱。

4.8.2 外部發(fā)現(xiàn)

上述機(jī)制可能導(dǎo)致短暫的邏輯上的哈希環(huán)分裂。比如微宝，管理員將節(jié)點(diǎn)A加入到哈希環(huán)中棺亭，然后又將節(jié)點(diǎn)B加入到哈希環(huán)中。此時(shí)蟋软，節(jié)點(diǎn)A和節(jié)點(diǎn)B都認(rèn)為自己是在系統(tǒng)中的侦铜，但是它們都不能立即知道彼此的存在专甩。為了防止這個(gè)問(wèn)題，一部分Dynamo節(jié)點(diǎn)會(huì)扮演種子的角色钉稍。種子節(jié)點(diǎn)通過(guò)外部機(jī)制發(fā)現(xiàn)涤躲，并且所有節(jié)點(diǎn)都知道它們。因?yàn)樗械墓?jié)點(diǎn)最終都會(huì)和種子節(jié)點(diǎn)交換成員關(guān)系變更歷史贡未，邏輯分裂不太可能發(fā)生种樱。可以通過(guò)配置文件或者配置服務(wù)來(lái)設(shè)置種子俊卤。典型的嫩挤，種子節(jié)點(diǎn)是哈希環(huán)中的全功能節(jié)點(diǎn)。

4.8.3 故障檢測(cè)

Dynamo的故障檢測(cè)是為了避免嘗試和不可訪問(wèn)的節(jié)點(diǎn)通信消恍，在讀寫操作岂昭，傳輸分片，暗示副本的過(guò)程中狠怨。一個(gè)純粹的本例故障檢測(cè)概念就完全足夠了：節(jié)點(diǎn)A可能認(rèn)為節(jié)點(diǎn)B是故障的约啊，在節(jié)點(diǎn)B沒有響應(yīng)節(jié)點(diǎn)A的消息的情況下(即使節(jié)點(diǎn)B響應(yīng)了節(jié)點(diǎn)C的消息)。在客戶端請(qǐng)求以一個(gè)穩(wěn)定的速率發(fā)送到Dynamo的情況下佣赖，Dynamo內(nèi)部節(jié)點(diǎn)會(huì)持續(xù)的互相通信恰矩，如果節(jié)點(diǎn)B沒有響應(yīng)節(jié)點(diǎn)A的消息，A會(huì)認(rèn)為B已經(jīng)故障憎蛤；節(jié)點(diǎn)A就會(huì)使用一個(gè)替代的節(jié)點(diǎn)來(lái)處理本應(yīng)該由節(jié)點(diǎn)B處理的請(qǐng)求外傅；同時(shí)節(jié)點(diǎn)A會(huì)周期性的嘗試與B通信，檢測(cè)它是否已經(jīng)恢復(fù)俩檬。如果沒有客戶端請(qǐng)求來(lái)產(chǎn)生節(jié)點(diǎn)間內(nèi)部通信萎胰，那么節(jié)點(diǎn)也就不需要了解哪個(gè)節(jié)點(diǎn)是否可以訪問(wèn)了。

去中心化的故障檢測(cè)協(xié)議使用一個(gè)簡(jiǎn)單的gossip風(fēng)格協(xié)議來(lái)使系統(tǒng)中的節(jié)點(diǎn)了解其他節(jié)點(diǎn)的進(jìn)入和退出棚辽。關(guān)于去中心化故障檢測(cè)的更多細(xì)節(jié)技竟，以及參數(shù)如何影響它的準(zhǔn)確性，可以參考^[25]晚胡。早期Dynamo的設(shè)計(jì)使用去中心化的故障檢測(cè)器來(lái)維護(hù)一個(gè)故障狀態(tài)的全局視圖。后來(lái)發(fā)現(xiàn)使用顯示的節(jié)點(diǎn)進(jìn)入和退出方法可以不需要使用全局故障視圖嚼沿，因?yàn)橥ㄟ^(guò)顯式調(diào)用方法的節(jié)點(diǎn)的進(jìn)入和退出估盘，其他節(jié)點(diǎn)會(huì)被通知。而暫時(shí)的節(jié)點(diǎn)故障也會(huì)在它們不再和其他節(jié)點(diǎn)通信時(shí)被檢測(cè)到骡尽。

4.9 添加/刪除 存儲(chǔ)節(jié)點(diǎn)

當(dāng)一個(gè)新節(jié)點(diǎn)(假設(shè)叫X)添加到系統(tǒng)中遣妥，它會(huì)被分配一些位置，這些位置隨機(jī)的分布在哈希環(huán)上攀细。對(duì)每個(gè)分配給X節(jié)點(diǎn)的key范圍箫踩，有一些其他節(jié)點(diǎn)(小于等于N個(gè))負(fù)責(zé)這些范圍里面的key爱态。由于這些key范圍被分配給了節(jié)點(diǎn)X，其他節(jié)點(diǎn)不用再存儲(chǔ)這些key境钟，它們將把這些key傳輸給節(jié)點(diǎn)X锦担。我們考慮一個(gè)簡(jiǎn)單的初始化場(chǎng)景，如圖2所示慨削，假設(shè)節(jié)點(diǎn)X被添加到節(jié)點(diǎn)A和節(jié)點(diǎn)B之間洞渔。當(dāng)節(jié)點(diǎn)X添加后，它將負(fù)責(zé)(F,G], (G,A] (A,X]范圍內(nèi)的有序key序列缚态。作為一個(gè)后果磁椒，節(jié)點(diǎn)B，節(jié)點(diǎn)C和節(jié)點(diǎn)D不在存儲(chǔ)這些key范圍玫芦。因此浆熔，節(jié)點(diǎn)B，C和D會(huì)將這些數(shù)據(jù)傳輸給節(jié)點(diǎn)X并確認(rèn)傳輸成功桥帆。當(dāng)一個(gè)節(jié)點(diǎn)從系統(tǒng)中退出時(shí)医增，相應(yīng)的key會(huì)按照相反的過(guò)程進(jìn)行重新分配。

操作經(jīng)驗(yàn)顯示這種方案會(huì)使得key在存儲(chǔ)節(jié)點(diǎn)上分布不均勻环葵，這對(duì)保證低延遲以及快速啟動(dòng)是非常重要的一個(gè)方面调窍。最終，通過(guò)在源和目的節(jié)點(diǎn)之間增加一個(gè)確認(rèn)過(guò)程张遭，保證了目的節(jié)點(diǎn)不會(huì)收到一個(gè)key范圍內(nèi)的重復(fù)傳輸數(shù)據(jù)邓萨。

5. 實(shí)現(xiàn)

Dynamo中每個(gè)存儲(chǔ)節(jié)點(diǎn)都有三個(gè)主要的組件：請(qǐng)求協(xié)調(diào)，成員關(guān)系和故障檢測(cè)菊卷，以及本地持久化存儲(chǔ)引擎缔恳。所有這些組件都是用Java實(shí)現(xiàn)。

Dynamo的本地存儲(chǔ)組件可以使用不同的存儲(chǔ)引擎插件洁闰。使用的存儲(chǔ)引擎包括Berkeley數(shù)據(jù)庫(kù)(BDB)事務(wù)數(shù)據(jù)存儲(chǔ)歉甚，BDB Java版本，MySQL扑眉，以及一個(gè)帶有持久化備份存儲(chǔ)的內(nèi)存緩存纸泄。設(shè)計(jì)一個(gè)可插件化存儲(chǔ)組件的主要目的是讓應(yīng)用程序可以根據(jù)各自的訪問(wèn)模型來(lái)選取最合適的存儲(chǔ)引擎。比如腰素，BDB可以處理典型的幾十K大小的對(duì)象聘裁，而MySQL則可以處理更大的對(duì)象。應(yīng)用程序根據(jù)他們的對(duì)象大小來(lái)選取Dynamo的本地存儲(chǔ)引擎弓千。大部分生產(chǎn)環(huán)境的Dynamo實(shí)例都使用BDB事務(wù)數(shù)據(jù)存儲(chǔ)衡便。

請(qǐng)求協(xié)調(diào)組件構(gòu)建在一個(gè)事件驅(qū)動(dòng)的模型之上，和SEDA架構(gòu)相似，其中消息處理過(guò)程被拆分為多個(gè)階段镣陕。所有的通信都使用Java NIO管道來(lái)實(shí)現(xiàn)谴餐。協(xié)調(diào)者作為客戶端的代表執(zhí)行讀和寫請(qǐng)求，從一個(gè)或多個(gè)節(jié)點(diǎn)收集數(shù)據(jù)或者將數(shù)據(jù)寫入到一個(gè)或多個(gè)節(jié)點(diǎn)呆抑。每個(gè)客戶端請(qǐng)求都會(huì)導(dǎo)致接收請(qǐng)求節(jié)點(diǎn)創(chuàng)建一個(gè)狀態(tài)機(jī)岂嗓。狀態(tài)機(jī)包括了如下過(guò)程的所有邏輯：確認(rèn)負(fù)責(zé)這個(gè)key的節(jié)點(diǎn)，發(fā)送請(qǐng)求理肺，等待回復(fù)摄闸，可能的重試，處理返回妹萨，打包結(jié)果返給客戶端年枕。每個(gè)狀態(tài)機(jī)實(shí)例處理一個(gè)客戶請(qǐng)求。舉例來(lái)說(shuō)乎完，一個(gè)讀操作實(shí)現(xiàn)了如下狀態(tài)機(jī)：(i)發(fā)送請(qǐng)求給相應(yīng)節(jié)點(diǎn), (ii)等待需要的最小數(shù)量的響應(yīng), (iii)如果在指定時(shí)間內(nèi)只有很少響應(yīng)熏兄，請(qǐng)求記為失敗, (iv)否則收集所有的數(shù)據(jù)版本并決定哪些需要返回的數(shù)據(jù)以及(v)如果開啟了版本功能，進(jìn)行沖突協(xié)調(diào)并生產(chǎn)一個(gè)寫操作的上下文树姨，其中包括了涵蓋所有版本的矢量鐘摩桶。為保持簡(jiǎn)潔性，略去了故障處理以及重試狀態(tài)帽揪。

在讀請(qǐng)求的響應(yīng)返回給客戶端后硝清，狀態(tài)機(jī)會(huì)等待一小段時(shí)間，用來(lái)接收未完成的響應(yīng)转晰。如果此時(shí)收到了舊版本數(shù)據(jù)的響應(yīng)芦拿，協(xié)調(diào)者會(huì)將這些節(jié)點(diǎn)的數(shù)據(jù)更新為最新版本。這個(gè)過(guò)程被稱為讀修復(fù)查邢，因?yàn)樗谝粋€(gè)機(jī)會(huì)時(shí)間內(nèi)修復(fù)了錯(cuò)過(guò)最近更新的副本蔗崎，同時(shí)也減低了逆熵協(xié)議的處理壓力。

如之前提到的扰藕，寫請(qǐng)求由首選列表前N個(gè)節(jié)點(diǎn)中的某個(gè)節(jié)點(diǎn)來(lái)協(xié)調(diào)缓苛。雖然很想總是使用前N個(gè)節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)來(lái)協(xié)調(diào)寫請(qǐng)求從而將所有寫請(qǐng)求在同一位置序列化，但是這種方案會(huì)導(dǎo)致數(shù)據(jù)分布的不均勻邓深，從而導(dǎo)致達(dá)不到SLA要求未桥。因?yàn)檎?qǐng)求壓力沒有均勻分布到所有的節(jié)點(diǎn)上。為了解決這個(gè)問(wèn)題芥备，首選列表的前N個(gè)節(jié)點(diǎn)中任意一個(gè)都可以協(xié)調(diào)寫請(qǐng)求冬耿。具體來(lái)說(shuō)，由于寫請(qǐng)求往往緊跟在一個(gè)讀請(qǐng)求之后门躯，寫請(qǐng)求的協(xié)調(diào)者可以選為之前響應(yīng)讀請(qǐng)求最快的節(jié)點(diǎn)淆党，這個(gè)請(qǐng)求記錄在寫請(qǐng)求的上下文信息中酷师。這個(gè)優(yōu)化使我們能夠選擇之前處理讀請(qǐng)求的節(jié)點(diǎn)讶凉，從而增加了"讀取你所寫"一致性的機(jī)會(huì)染乌。它同時(shí)也降低了請(qǐng)求處理性能的波動(dòng)，從而增加了99.9%水平的性能表現(xiàn)懂讯。

6. 經(jīng)驗(yàn) & 教訓(xùn)

多個(gè)服務(wù)使用Dynamo荷憋，并使用不同的配置。這些實(shí)例在版本協(xié)調(diào)邏輯褐望，讀寫仲裁特性方面有所不同勒庄。以下是Dynamo使用的主要模式:

• 業(yè)務(wù)邏輯指定沖突協(xié)調(diào)方案：這是Dyanmo較受歡迎的一種用法。每個(gè)數(shù)據(jù)對(duì)象都在多個(gè)節(jié)點(diǎn)上存儲(chǔ)有副本瘫里。當(dāng)遇到不同版本的情形实蔽，客戶端應(yīng)用程序進(jìn)行他們自己的沖突協(xié)調(diào)邏輯。前面討論的購(gòu)物車服務(wù)是一個(gè)這種類型的一個(gè)例子谨读。它的業(yè)務(wù)邏輯通過(guò)合并購(gòu)物車的不同版本來(lái)解決沖突局装。
• 基于時(shí)間戳的沖突協(xié)調(diào)方案：這個(gè)機(jī)制和上一個(gè)相比，只在協(xié)調(diào)機(jī)制上有所不同劳殖。當(dāng)遇到不同版本時(shí)铐尚，Dynamo進(jìn)行簡(jiǎn)單的基于時(shí)間戳的協(xié)調(diào)，即"最后一個(gè)寫有效"哆姻；比如宣增，帶有最大物理時(shí)間戳的對(duì)象被選擇為正確的版本。維護(hù)用戶會(huì)話信息的服務(wù)是使用這種機(jī)制的一個(gè)好例子矛缨。
• 高性能讀引擎：Dynamo旨在構(gòu)建一個(gè)"總是可寫"的數(shù)據(jù)存儲(chǔ)爹脾，然而一小部分服務(wù)通過(guò)調(diào)整它的仲裁特性，使它成為一個(gè)高性能讀引擎劳景。典型的誉简，這些服務(wù)有很高的讀請(qǐng)求速率，同時(shí)只有很少的更新請(qǐng)求盟广。在這個(gè)配置下闷串，R一般被設(shè)置為1，W設(shè)置為N筋量。對(duì)于這些服務(wù)烹吵，Dynamo提供了分布數(shù)據(jù)的能力，以及增量擴(kuò)容的能力桨武。這些實(shí)例中的一部分被當(dāng)作一致性cache來(lái)使用肋拔，其中數(shù)據(jù)存儲(chǔ)在更加重型的后端存儲(chǔ)中。維護(hù)商品類目以及促銷商品的服務(wù)很合適這種機(jī)制呀酸。

Dynamo的最大優(yōu)勢(shì)在于凉蜂，它的客戶應(yīng)用程序可以通過(guò)調(diào)整N,R,W的值來(lái)到他們所需要的性能，可用性，持久性水平窿吩。例如茎杂，N的值決定了每個(gè)對(duì)象的持久性。Dynamo用戶使用的N值典型為3纫雁。

W和R的值影響著對(duì)象的可用性煌往，持久性以及一致性。例如轧邪，如果W設(shè)置為1刽脖，那么只要有一個(gè)節(jié)點(diǎn)成功處理了寫操作，那么系統(tǒng)就不會(huì)拒絕寫請(qǐng)求忌愚。然而曲管，W和R設(shè)置的比較低，會(huì)增加不一致的風(fēng)險(xiǎn)硕糊，因?yàn)榧词箤懻?qǐng)求沒有被大部分副本處理翘地，也會(huì)認(rèn)為是成功并返回給客戶。這種設(shè)置也給持久性帶來(lái)了風(fēng)險(xiǎn)窗口癌幕，因?yàn)橐粋€(gè)寫請(qǐng)求在只有小部分節(jié)點(diǎn)完成持久化的情況下就返回成功給客戶端了衙耕。

傳統(tǒng)的觀點(diǎn)認(rèn)為持久性和可用性要同時(shí)存在。然而勺远，這并不是必需的橙喘。例如，可以通過(guò)增加W的值來(lái)降低持久化的風(fēng)險(xiǎn)胶逢。這可能會(huì)增加拒絕請(qǐng)求的概率厅瞎，因?yàn)樾枰嘣诰€的存儲(chǔ)節(jié)點(diǎn)來(lái)處理寫請(qǐng)求。

一些服務(wù)使用的最通用的(N,R,W)配置是(3,2,2)初坠。選擇這幾個(gè)值是為了達(dá)到需要的性能和簸，持久性，一致性水平碟刺，以及可用性SLA锁保。

本章所描述的測(cè)量都是在一個(gè)使用(3,2,2)配置的系統(tǒng)中進(jìn)行的，包括幾百個(gè)相同硬件配置的節(jié)點(diǎn)。如前面所提到的，Dynamo的每個(gè)實(shí)例都包含分布在不同數(shù)據(jù)中心的節(jié)點(diǎn)布讹。這些數(shù)據(jù)中心都通過(guò)高速網(wǎng)絡(luò)連接。為了產(chǎn)出一個(gè)成功的讀請(qǐng)求的響應(yīng)浩村，R個(gè)節(jié)點(diǎn)需要返回響應(yīng)給協(xié)調(diào)者。很明顯的占哟，數(shù)據(jù)中心之間的網(wǎng)絡(luò)延遲會(huì)影響到響應(yīng)時(shí)間心墅，因此需要刻意選擇節(jié)點(diǎn)以及他們?cè)谀膫€(gè)數(shù)據(jù)中心酿矢，來(lái)達(dá)到應(yīng)用程序的目標(biāo)SLA。

6.1 平衡性能和持久性

雖然Dynamo的首要設(shè)計(jì)目標(biāo)是建一個(gè)高可用的數(shù)據(jù)存儲(chǔ)系統(tǒng)怎燥，性能也是Amazon平臺(tái)一個(gè)同樣重要的標(biāo)準(zhǔn)棠涮。如前面提到的，為了達(dá)到一致的用戶體驗(yàn)刺覆，Amazon的服務(wù)將性能水平設(shè)置為比較高的百分比(比如99.9%或者99.99%)。一個(gè)典型的使用Dynamo的服務(wù)的SLA為99.9%的讀寫請(qǐng)求在300ms以內(nèi)完成史煎。

由于Dynamo是運(yùn)行在普通的廉價(jià)硬件上谦屑，I/O能力相比高端企業(yè)服務(wù)器要弱很多，因此篇梭，要提供讀寫請(qǐng)求的高性能是一個(gè)非凡的任務(wù)氢橙。在讀寫請(qǐng)求中多個(gè)節(jié)點(diǎn)的參與更使得這個(gè)任務(wù)具有挑戰(zhàn)性，因?yàn)檫@些操作的性能被R或W個(gè)副本里面最慢的一個(gè)的性能所限制恬偷。圖4展示了Dynamo在30天內(nèi)讀寫請(qǐng)求的平均延遲以及99.9%分位的延遲悍手。可以看到袍患，延遲的分布表現(xiàn)出明顯的晝夜周期性坦康，由于請(qǐng)求速率的晝夜模式(在白天和夜晚請(qǐng)求量有明顯不同)。此外诡延，寫請(qǐng)求的延遲明顯的比讀請(qǐng)求高滞欠，因?yàn)閷懻?qǐng)求總是要訪問(wèn)磁盤。99.9%分位的延遲都在200ms左右肆良，并且比平均水平要高一點(diǎn)筛璧。這是因?yàn)?9.9%分位水平延遲收到一些諸如請(qǐng)求壓力變化，對(duì)象大小惹恃，以及本地模式的影響夭谤。

latency.jpg

對(duì)于大多數(shù)服務(wù)來(lái)說(shuō)，這個(gè)水平的性能是可以接收的巫糙，然而有一小部分面向客戶的服務(wù)需要更高水平的性能采蚀。對(duì)這些服務(wù)，Dynamo提供了在犧牲持久性保證以換取性能的能力榆鼠。作為優(yōu)化，每個(gè)存儲(chǔ)節(jié)點(diǎn)都在內(nèi)存中維護(hù)一個(gè)對(duì)象的緩存亥鸠。寫操作也寫入到緩存中然后由一個(gè)寫線程周期性的寫入到磁盤中妆够。在這種方案中识啦，讀操作首選檢查請(qǐng)求的key是否在緩存中，如果在神妹，那么就直接從緩存中讀取而不是從存儲(chǔ)引擎中讀取颓哮。

這個(gè)優(yōu)化的結(jié)果是，高峰期時(shí)99.9%分位的延遲降低了5倍鸵荠，即使只使用了一個(gè)用于幾千個(gè)對(duì)象的很小的緩存(參見圖5)冕茅。此外，如如圖中所示蛹找，寫緩存機(jī)制使高分位的延遲變得比較平滑姨伤。很明顯的，這個(gè)方案犧牲了持久性來(lái)?yè)Q取高性能庸疾。使用這個(gè)方案乍楚，服務(wù)的崩潰會(huì)導(dǎo)致在緩存中排隊(duì)的寫操作丟失。為了減少持久性風(fēng)險(xiǎn)届慈，寫操作重新優(yōu)化為徒溪，協(xié)調(diào)者會(huì)選擇N個(gè)節(jié)點(diǎn)中的一個(gè)來(lái)完成"持久化寫"操作。由于協(xié)調(diào)者只需要等待W個(gè)響應(yīng)金顿，寫操作的性能不會(huì)被單個(gè)副本的持久化寫邪能所影響到臊泌。

buffer.jpg

6.2 確保壓力均勻分布

Dynamo使用一致性hash來(lái)將key空間分布到副本上，保證壓力均勻分布揍拆。假設(shè)key不是高度傾斜的缺虐，key均勻分布能夠幫助我們達(dá)到壓力均勻分布的目的。具體來(lái)說(shuō)礁凡，Dynamo在設(shè)計(jì)時(shí)假設(shè)高氮，即使訪問(wèn)請(qǐng)求分布有嚴(yán)重傾斜，也會(huì)有足夠多的key在分布尾端顷牌，因此處理大多數(shù)key的壓力能夠通過(guò)分片均勻的傳播到節(jié)點(diǎn)上(????)剪芍。本節(jié)討論壓力失調(diào)以及不同分片策略對(duì)壓力分布的影響。

為了研究壓力失調(diào)和請(qǐng)求壓力的關(guān)系窟蓝，測(cè)量了每個(gè)節(jié)點(diǎn)在24小時(shí)內(nèi)收到的請(qǐng)求數(shù)據(jù)罪裹，分為30分鐘一個(gè)周期。在給定的時(shí)間窗口內(nèi)运挫，如果一個(gè)節(jié)點(diǎn)的請(qǐng)求壓力和平均水平相差在15%以內(nèi)状共，那么認(rèn)為這個(gè)節(jié)點(diǎn)此時(shí)"在平衡狀態(tài)中"，否則認(rèn)為節(jié)點(diǎn)"不在平衡狀態(tài)"谁帕。圖6顯示了這段時(shí)間內(nèi)"不在平衡狀態(tài)"的比例峡继。作為參考，這段時(shí)間內(nèi)整個(gè)系統(tǒng)收到的請(qǐng)求壓力也繪制在圖中匈挖∧肱疲可以看到康愤，失衡比例隨著壓力的增加而減小。比如舶吗，在低負(fù)載情況下失衡比例達(dá)到20%征冷，而在高負(fù)載時(shí)失衡比例接近10%∈那恚可以很直觀的解釋這個(gè)現(xiàn)象检激，在高負(fù)載情況下，有大量的對(duì)多數(shù)key的請(qǐng)求腹侣，由于key的均勻分布叔收，壓力也被均勻的分布了。然而在低負(fù)載時(shí)(請(qǐng)求壓力是高峰期的1/8)筐带，更少的多數(shù)key被訪問(wèn)，導(dǎo)致了高比例的失衡狀態(tài)缤灵。

load.jpg

本節(jié)討論Dynamo的分片方案是如何隨著時(shí)間以及對(duì)壓力分布的影響演進(jìn)的伦籍。

策略1`: 每個(gè)節(jié)點(diǎn)T個(gè)隨機(jī)的token以及按token值來(lái)分片：這是最早在生產(chǎn)環(huán)境中使用的分片策略(4.2節(jié)中有描述)。在這個(gè)方案中腮出，每個(gè)節(jié)點(diǎn)被分配T個(gè)token(從hash空間中均勻的隨機(jī)選取)帖鸦。所有節(jié)點(diǎn)的token根據(jù)他們?cè)趆ash環(huán)中的值排好序。每?jī)蓚€(gè)連續(xù)的token定義了一個(gè)范圍胚嘲，最后一個(gè)token和第一個(gè)token組成了一個(gè)包括hash空間內(nèi)最大值到最小值的范圍作儿。因?yàn)閠oken是隨機(jī)選擇的，得到的范圍大小都是各不相同的馋劈。隨著節(jié)點(diǎn)的加入和退出攻锰，token都在變化，因而范圍也都在變化妓雾。需要注意到娶吞，在每個(gè)節(jié)點(diǎn)上維護(hù)成員關(guān)系所需的存儲(chǔ)空間是隨機(jī)節(jié)點(diǎn)的個(gè)數(shù)而線性增加的。

使用這種方案時(shí)械姻，遇到了以下問(wèn)題妒蛇。首選，當(dāng)一個(gè)新節(jié)點(diǎn)加入到系統(tǒng)中楷拳，它需要從其他節(jié)點(diǎn)中"偷取"key范圍绣夺。然而，那些把key范圍轉(zhuǎn)交給新節(jié)點(diǎn)的節(jié)點(diǎn)必須要掃描本地持久化存儲(chǔ)以找到相應(yīng)的數(shù)據(jù)欢揖。注意到在生產(chǎn)節(jié)點(diǎn)上進(jìn)行這樣的掃描操作是非常trick的陶耍，因?yàn)閽呙枋琴Y源密集型操作，并且需要在后臺(tái)完成她混，以及不影響用戶體驗(yàn)物臂。這導(dǎo)致運(yùn)行初始化的任務(wù)只有很低的優(yōu)先級(jí)旺拉，然而，這個(gè)機(jī)制導(dǎo)致了初始化進(jìn)行的非常緩慢棵磷。在繁忙的購(gòu)物季蛾狗，節(jié)點(diǎn)在一天內(nèi)處理上百萬(wàn)個(gè)請(qǐng)求，初始化幾乎需要一整天的時(shí)間來(lái)完成仪媒。第二沉桌，當(dāng)一個(gè)節(jié)點(diǎn)進(jìn)入或退出系統(tǒng)，許多節(jié)點(diǎn)的key范圍都發(fā)生變化算吩，Merkle樹需要重新計(jì)算留凭，這在生產(chǎn)環(huán)境中是一個(gè)比較麻煩的操作。最后偎巢， 由于key訪問(wèn)的隨機(jī)性蔼夜，很難對(duì)整個(gè)key空間做一個(gè)快照，這導(dǎo)致歸檔很困難压昼。這種方案中求冷，歸檔整個(gè)key空間需要單獨(dú)從每個(gè)節(jié)點(diǎn)中獲取數(shù)據(jù)，是非常低效的方式窍霞。

這種策略的根本問(wèn)題在于數(shù)據(jù)的分片和數(shù)據(jù)的分區(qū)布局交織在一起匠题。比如，在某些情形下但金，期望通過(guò)增加節(jié)點(diǎn)來(lái)應(yīng)對(duì)請(qǐng)求壓力的增長(zhǎng)韭山。然而，這種場(chǎng)景下冷溃，不可能添加節(jié)點(diǎn)而又不影響數(shù)據(jù)分布钱磅。理想情況中，可以使用單獨(dú)的方案來(lái)做分片和分區(qū)布局似枕。為了解決這個(gè)問(wèn)題续搀，演化出了以下策略：

策略2: 每個(gè)節(jié)點(diǎn)T個(gè)隨機(jī)token和相等大小的分區(qū)：這種策略中，hash空間被等分為Q個(gè)范圍菠净，每個(gè)節(jié)點(diǎn)被分配T個(gè)隨機(jī)token禁舷。Q一般被設(shè)置為Q >> N and Q >> S*T，其中S是系統(tǒng)中節(jié)點(diǎn)個(gè)數(shù)毅往。這種策略中牵咙，token只用于構(gòu)建一個(gè)將hash空間中的值映射到節(jié)點(diǎn)上的有序list的map，而不用于決定分片攀唯。圖7展示了N為3時(shí)這種策略的例子洁桌，其中，從包含k1的分片出發(fā)侯嘀，會(huì)遇到節(jié)點(diǎn)A,B,C另凌。這種策略的主要好處是: (i)解耦了分片和分區(qū)布局谱轨，(ii)使運(yùn)行時(shí)更改分區(qū)布局變得可能。

partition.jpg

策略3: 每個(gè)節(jié)點(diǎn)Q/S個(gè)token, 相等大小的分區(qū)：和策略2相似吠谢，這種策略將hash空間氛圍Q個(gè)大小相等的分區(qū)土童，分區(qū)的位置和分區(qū)方案是解耦的。此外工坊，每個(gè)節(jié)點(diǎn)都被分配了Q/S個(gè)token献汗，其中S是系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)。當(dāng)一個(gè)節(jié)點(diǎn)退出系統(tǒng)時(shí)王污，它所負(fù)責(zé)的token被隨機(jī)的分配給剩余的節(jié)點(diǎn)罢吃，這樣這些屬性都得意保留。類似的昭齐，當(dāng)一個(gè)節(jié)點(diǎn)加入到系統(tǒng)中時(shí)尿招，它以一種保留這些屬性的方式從其他節(jié)點(diǎn)"偷取"token。

在一個(gè)S=30和N=3的系統(tǒng)上評(píng)估了這三種策略的效率阱驾。然而就谜，以一個(gè)公平的方式來(lái)評(píng)估這些不同的策略是比較困難的，因?yàn)樗麄兏髯允褂貌煌呐渲脕?lái)調(diào)整效率啊易。比如吁伺，策略1的壓力分布屬性取決于token的個(gè)數(shù)(即T)饮睬，而策略3則取決于分片的個(gè)數(shù)(即Q)租谈。一個(gè)公平的比較方法是評(píng)估在使用相同存儲(chǔ)空間來(lái)維護(hù)成員關(guān)系時(shí)，系統(tǒng)壓力的傾斜狀況捆愁。比如割去，在策略1中每個(gè)節(jié)點(diǎn)需要維護(hù)哈希環(huán)中所有節(jié)點(diǎn)的token位置，在策略3中每個(gè)節(jié)點(diǎn)需求維護(hù)分配到每個(gè)節(jié)點(diǎn)的分區(qū)信息昼丑。
在我們的下一個(gè)實(shí)驗(yàn)中呻逆，通過(guò)改變相關(guān)參數(shù)(T和Q)來(lái)評(píng)估了這些策略。在節(jié)點(diǎn)維護(hù)的成員信息大小不同的情況下菩帝，測(cè)量了每個(gè)策略的壓力均衡效率咖城，其中壓力均衡效率被定義為每個(gè)節(jié)點(diǎn)處理請(qǐng)求的平均數(shù)和最忙節(jié)點(diǎn)的最高峰請(qǐng)求處理數(shù)的比例。

load_dis.jpg

圖8展示了實(shí)驗(yàn)結(jié)果呼奢。從圖中可以看到宜雀，策略3的壓力均衡效率是最好的，策略2的壓力均衡效率是最差的握础。在很短一段時(shí)間內(nèi)辐董，策略2作為將Dynamo實(shí)例從策略1遷移到策略3的一個(gè)臨時(shí)過(guò)渡策略來(lái)使用。相比于策略1禀综，策略3達(dá)到了更好的效率简烘，并且在每個(gè)節(jié)點(diǎn)需要維護(hù)成員關(guān)系信息大小上降低了3個(gè)數(shù)量級(jí)苔严。雖然存儲(chǔ)不是一個(gè)主要問(wèn)題，但是節(jié)點(diǎn)間會(huì)周期性的交換成員關(guān)系信息孤澎，因此保持信息盡可能緊湊也是需要的届氢。除此之外，策略3由于以下原因部署更加簡(jiǎn)單：(i)更快的初始化/恢復(fù)：由于分片范圍是固定的亥至，他們可以存儲(chǔ)在單獨(dú)的文件中悼沈，意味著一個(gè)分片可以作為一個(gè)單元通過(guò)簡(jiǎn)單的傳輸文件來(lái)進(jìn)行重新定位(避免了定位指定數(shù)據(jù)導(dǎo)致的隨機(jī)訪問(wèn))。這簡(jiǎn)化了初始化和恢復(fù)的過(guò)程姐扮。(ii)歸檔簡(jiǎn)單：周期性的對(duì)數(shù)據(jù)進(jìn)行歸檔是大多數(shù)Amazon存儲(chǔ)服務(wù)的強(qiáng)制要求絮供。在策略3下對(duì)Dynamo存儲(chǔ)的數(shù)據(jù)進(jìn)行歸檔更加簡(jiǎn)單，因?yàn)榉制募梢詥为?dú)獲取茶敏。作為對(duì)比壤靶，策略1中token是隨機(jī)選取的，歸檔數(shù)據(jù)需要從單個(gè)節(jié)點(diǎn)中獲取key惊搏，這是非常低效和慢速的贮乳。策略3的劣勢(shì)在于改變節(jié)點(diǎn)成員關(guān)系需要重新協(xié)調(diào)以保留分配所需的屬性(???)。

6.3 不同版本: 何時(shí)以及多少

如前面提到的恬惯，Dyanmo被設(shè)計(jì)為犧牲一致性來(lái)?yè)Q取可用性向拆。為了理解不同故障對(duì)一致性的影響，需要多個(gè)方面的詳細(xì)數(shù)據(jù)：故障時(shí)長(zhǎng)酪耳，故障類型浓恳，組件可靠性，工作壓力等碗暗。詳細(xì)展示這些數(shù)據(jù)不在本文討論范圍之內(nèi)颈将。然而，本節(jié)討論了一種摘要式的指標(biāo)：在生產(chǎn)環(huán)境中應(yīng)用程序可以看到的不同版本的數(shù)目言疗。

在兩種場(chǎng)景下晴圾，數(shù)據(jù)的不同版本數(shù)會(huì)增加。第一種場(chǎng)景是當(dāng)系統(tǒng)面臨故障噪奄，如節(jié)點(diǎn)故障死姚，數(shù)據(jù)中心故障，網(wǎng)絡(luò)斷開勤篮。第二種場(chǎng)景是系統(tǒng)處理大量對(duì)同一個(gè)對(duì)象的并發(fā)更新都毒，多個(gè)不通過(guò)節(jié)點(diǎn)同時(shí)處理更新操作。從可用性以及效率角度看叙谨，期望能夠保證不同版本數(shù)目盡可能少温鸽。如果不能通過(guò)基于矢量鐘的語(yǔ)法分析來(lái)解決不同版本的沖突，那么就必須將不同版本傳輸給業(yè)務(wù)邏輯來(lái)通過(guò)語(yǔ)義分析協(xié)調(diào)沖突。語(yǔ)義分析協(xié)調(diào)給服務(wù)帶來(lái)了額外的壓力涤垫，因此應(yīng)該盡量減少對(duì)它的需求姑尺。

在我們下一個(gè)實(shí)驗(yàn)中，分析了24小時(shí)內(nèi)返回給購(gòu)物車服務(wù)的版本數(shù)目蝠猬。在這段時(shí)間內(nèi)切蟋，99.94%的請(qǐng)求看到一個(gè)版本；0.00057%的請(qǐng)求看到了2個(gè)版本榆芦；0.00047%的請(qǐng)求看了的三個(gè)版本柄粹；0.00009%的請(qǐng)求看到了4個(gè)版本。這說(shuō)明不同版本很少被創(chuàng)建匆绣。

經(jīng)驗(yàn)顯示不同版本的數(shù)目增加不是由故障造成的驻右，而是由于并發(fā)寫的量增加而導(dǎo)致的。并發(fā)寫的量增加一般是由繁忙的機(jī)器人(自動(dòng)客戶程序)觸發(fā)的崎淳，很少是認(rèn)為產(chǎn)生堪夭。這個(gè)主題不會(huì)深入討論，因?yàn)楸疚牡拿舾行浴?/p>

6.4 客戶驅(qū)動(dòng)或服務(wù)驅(qū)動(dòng)的協(xié)調(diào)

第5章提到過(guò)拣凹，Dynamo有一個(gè)請(qǐng)求協(xié)調(diào)組件森爽，它使用一個(gè)狀態(tài)機(jī)來(lái)處理收到的請(qǐng)求∠担客戶請(qǐng)求通過(guò)一個(gè)負(fù)載均衡器均勻的分布到哈希環(huán)的節(jié)點(diǎn)上爬迟。任意Dynamo節(jié)點(diǎn)都可以作為協(xié)調(diào)者處理一個(gè)讀請(qǐng)求。另一方面菊匿，寫請(qǐng)求則會(huì)被key的首選列表中的一個(gè)節(jié)點(diǎn)協(xié)調(diào)處理付呕。存在這個(gè)限制是因?yàn)檫@些首選節(jié)點(diǎn)有一個(gè)額外職責(zé)，它們負(fù)責(zé)創(chuàng)建新的版本戳捧请，偶爾還要合并那些被寫請(qǐng)求更新的版本凡涩。注意到Dynamo的版本機(jī)制使基于物理時(shí)間戳實(shí)現(xiàn)的棒搜，任意節(jié)點(diǎn)偶可以協(xié)調(diào)一個(gè)寫請(qǐng)求疹蛉。

一個(gè)協(xié)調(diào)請(qǐng)求的替代方案是將狀態(tài)機(jī)轉(zhuǎn)移到客戶節(jié)點(diǎn)。這種方案中力麸，客戶應(yīng)用程序使用一個(gè)代碼庫(kù)在本地進(jìn)行請(qǐng)求協(xié)調(diào)可款。客戶程序周期性的隨機(jī)選擇一個(gè)Dynamo節(jié)點(diǎn)克蚂，從中下載它的Dynamo成員關(guān)系狀態(tài)視圖闺鲸。使用這個(gè)信息，客戶程序可以知道任意key的首選列表節(jié)點(diǎn)埃叭。讀請(qǐng)求可以在客戶端進(jìn)行協(xié)調(diào)摸恍，從而避免了一次網(wǎng)絡(luò)跳轉(zhuǎn)。寫請(qǐng)求要么被轉(zhuǎn)發(fā)給key的首選列表，或者在客戶端本地進(jìn)行協(xié)調(diào)(如果Dynamo使用基于時(shí)間戳的版本機(jī)制)立镶。

客戶驅(qū)動(dòng)的協(xié)調(diào)方案的一個(gè)重要優(yōu)勢(shì)是壁袄，不再需要一個(gè)負(fù)載均衡器來(lái)將客戶請(qǐng)求均勻分布到系統(tǒng)中。公平的負(fù)載分布由key在存儲(chǔ)節(jié)點(diǎn)上的均勻分布來(lái)隱式保證媚媒。很明顯的嗜逻，這種方案的效率取決于客戶端的成員關(guān)系信息是否足夠新。當(dāng)前客戶端每10秒詢問(wèn)一次Dynamo節(jié)點(diǎn)缭召，來(lái)更新成員關(guān)系信息栈顷。基于拉的方案替代了基于推的方案嵌巷，因?yàn)榍罢呖梢院芎玫臄U(kuò)展以適應(yīng)大量客戶端萄凤，同時(shí)只需在服務(wù)端維護(hù)很少的狀態(tài)信息。然而搪哪，在最壞的情況下蛙卤，客戶端有可能獲取到落后10s的成員關(guān)系信息。在這種情況下噩死，如果客戶端檢測(cè)到自己的成員關(guān)系是陳舊的(比如颤难，有些成功訪問(wèn)不到)，它會(huì)立即更新成員關(guān)系信息已维。

table.jpg

表2顯示了在24小時(shí)觀察周期內(nèi)行嗤，使用客戶驅(qū)動(dòng)方案相比于服務(wù)端驅(qū)動(dòng)方案，得到的99.9%分位延遲的改善情況垛耳。在表中可以看到栅屏，客戶驅(qū)動(dòng)的協(xié)調(diào)方案在99.9%分位延遲方面降低了30ms，在平均延遲上減低了3到4ms堂鲜。延遲的改善是因?yàn)榭蛻趄?qū)動(dòng)方案消除了負(fù)載均衡器栈雳，以及額外的網(wǎng)絡(luò)跳轉(zhuǎn)。同樣可以看到缔莲，平均延遲顯著低于99.9%分位延遲哥纫，這是因?yàn)镈ynamo存儲(chǔ)引擎的緩存以及寫緩存有較高的命中率。此外痴奏，由于負(fù)載均衡器以及網(wǎng)絡(luò)引入的額外響應(yīng)時(shí)間蛀骇，99.9%分位的響應(yīng)時(shí)間比平均水平要高。

6.5 平衡 后臺(tái)vs前臺(tái)任務(wù)

每個(gè)節(jié)點(diǎn)除了完成常規(guī)的前臺(tái)讀寫操作之外读拆，還要進(jìn)行不同種類的后臺(tái)任務(wù)擅憔，包括副本同步和數(shù)據(jù)轉(zhuǎn)移(由于暗示或者增刪節(jié)點(diǎn))。在早期的生產(chǎn)環(huán)境中檐晕，這些后臺(tái)任務(wù)導(dǎo)致了資源爭(zhēng)奪以及影響了正常的讀寫操作的性能暑诸。因此，需要確保后臺(tái)任務(wù)只能在不會(huì)顯著影響常規(guī)的關(guān)鍵操作時(shí)進(jìn)行。為此个榕，后臺(tái)任務(wù)被集成到一個(gè)入場(chǎng)控制機(jī)制中啦逆。每個(gè)后臺(tái)任務(wù)是要這個(gè)控制器來(lái)預(yù)留一部分運(yùn)行時(shí)資源(例如數(shù)據(jù)庫(kù))，并在所有后臺(tái)任務(wù)中共享笛洛。使用一個(gè)基于監(jiān)控前臺(tái)任務(wù)性能的反饋機(jī)制來(lái)調(diào)整用于后臺(tái)任務(wù)的資源數(shù)量夏志。

入場(chǎng)控制器持續(xù)監(jiān)控執(zhí)行前臺(tái)讀寫操作時(shí)資源使用狀況。監(jiān)視點(diǎn)包括磁盤操作延遲苛让，事務(wù)超時(shí)以及鎖導(dǎo)致的數(shù)據(jù)庫(kù)訪問(wèn)失敗沟蔑，請(qǐng)求隊(duì)列等待時(shí)間。這些信息用于檢測(cè)延遲或者故障的百分比是否接近一個(gè)臨界值狱杰。比如瘦材， 后臺(tái)控制器會(huì)查看99.9%分位的數(shù)據(jù)庫(kù)讀延遲和預(yù)先設(shè)置的閾值(假設(shè)50ms)相差多遠(yuǎn)》禄控制器使用這些比較來(lái)評(píng)估前臺(tái)任務(wù)的可用資源食棕。接著，它會(huì)決定可用于后臺(tái)任務(wù)的資源數(shù)量错沽，從而使用這種反饋循環(huán)來(lái)現(xiàn)在后臺(tái)活動(dòng)的侵略性簿晓。注意到一個(gè)相似的后臺(tái)任務(wù)管理問(wèn)題在^[26]中被研究過(guò)。

6.6 討論

本章總結(jié)了從實(shí)現(xiàn)和維護(hù)Dynamo的過(guò)程中獲取的經(jīng)驗(yàn)千埃。許多Amazon內(nèi)部服務(wù)在過(guò)去兩年使用了Dynamo憔儿，它給應(yīng)用程序提供了顯著的可用性水平。具體來(lái)說(shuō)放可，應(yīng)用程序99.9995%的請(qǐng)求都收到了成功的響應(yīng)谒臼，并且目前還沒有出現(xiàn)過(guò)數(shù)據(jù)丟失的情況。

此外耀里，Dynamo的主要優(yōu)勢(shì)是提供了一個(gè)必要的手段蜈缤，可以通過(guò)(N,R,W)參數(shù)來(lái)按照需求調(diào)整實(shí)例。和流行的商用存儲(chǔ)系統(tǒng)不同冯挎，Dynamo將數(shù)據(jù)一致性和協(xié)調(diào)邏輯暴露給開發(fā)者底哥。最開始的時(shí)候，很多人以為應(yīng)用程序會(huì)因此變得復(fù)雜织堂。然而叠艳，過(guò)去Amazon平臺(tái)被設(shè)計(jì)為高可用奶陈，很多應(yīng)用程序被設(shè)計(jì)為能處理不同故障情形以及不一致的情況易阳。因此，將這樣的應(yīng)用程序移植到使用Dynamo是一個(gè)相對(duì)簡(jiǎn)單的任務(wù)吃粒。對(duì)于少數(shù)使用Dynamo的應(yīng)用程序潦俺，需要在早期部署的時(shí)候選擇一個(gè)合適的沖突解決機(jī)制來(lái)滿足業(yè)務(wù)需求。最終Dynamo選擇了一個(gè)全量成員關(guān)系模型，其中每個(gè)節(jié)點(diǎn)都了解所有其他節(jié)點(diǎn)所管理的數(shù)據(jù)事示。為了做到這一點(diǎn)早像，每個(gè)節(jié)點(diǎn)主動(dòng)地和系統(tǒng)中其他節(jié)點(diǎn)交換全量路由表信息。在系統(tǒng)中只有幾百個(gè)節(jié)點(diǎn)的時(shí)候肖爵，這個(gè)模型工作的很好卢鹦。然而將這樣的設(shè)計(jì)擴(kuò)展到上萬(wàn)個(gè)節(jié)點(diǎn)是不容易的因?yàn)榫S護(hù)路由表的開銷隨著系統(tǒng)的規(guī)則增加而增大。通過(guò)引入分層擴(kuò)展到Dynamo中可能能夠克服這個(gè)限制劝堪。此外冀自，注意到這個(gè)問(wèn)題已經(jīng)被O(1)的分布式哈希表系統(tǒng)(例如^[27])解決了。

7. 總結(jié)

本文描述了Dynamo秒啦，一個(gè)高可用熬粗，可擴(kuò)展的存儲(chǔ)系統(tǒng)，被Amazon平臺(tái)的一些核心服務(wù)用于存儲(chǔ)狀態(tài)余境。Dynamo提供了期望的可用性及性能水平驻呐，并且能夠成功處理服務(wù)故障，數(shù)據(jù)中心故障和網(wǎng)絡(luò)斷開的情形芳来。Dynamo是增量可擴(kuò)展的含末，允許服務(wù)管理者根據(jù)當(dāng)前請(qǐng)求壓力來(lái)擴(kuò)容或縮容。Dynamo允許服務(wù)管理者通過(guò)調(diào)整N,R,W參數(shù)來(lái)達(dá)到他們的性能即舌，持久性以及一致性SLA要求答渔。

過(guò)去幾年Dynamo在生產(chǎn)環(huán)境中的使用說(shuō)明了去中心化技術(shù)可以用于提供一個(gè)高可用的系統(tǒng)。它在最具挑戰(zhàn)的應(yīng)用環(huán)境中取得的成功顯示了一個(gè)最終一致性存儲(chǔ)系統(tǒng)可以構(gòu)建高可用應(yīng)用程序的一個(gè)部分侥涵。

鳴謝

作者在此要感謝PatHelland沼撕，他貢獻(xiàn)了Dynamo的初步設(shè)計(jì)谢揪。我們還要感謝MarvinTheimer和RobertvanRenesse的評(píng)注徙缴。最后卸耘，我們要感謝我們的指路人斩祭，JeffMogul卵牍，在準(zhǔn)備最終版本時(shí)库北，他詳細(xì)的評(píng)注和輸入铣揉，大大提高了本文的質(zhì)量窜骄。

1. Karger,D.,Lehman, E.,Leighton, T.,Panigrahy,R., Levine,M., and Lewin,D. 1997. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. ?

2. Lamport,L. Time, clocks, and the ordering of events in a distributed system. ACM Communications, 21(7), pp.558-565, 1978. ?

3. Fox,A., Gribble, S.D., Chawathe, Y., Brewer, E. A., and Gauthier,P. 1997. Cluster-based scalable network services. In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles. ?

4. Bernstein, P.A., and Goodman, N. An algorithm for concurrency control and recovery in replicated distributed databases. ACM Trans. on Database Sysytems. ?

5. Gray,J.,Helland,P.,O'Neil,P., and Shasha, D. 1996. The dangers of replication and a solution. In Proceedings of the 1996 ACM SIGMOD international Conference on Management of Data. ?

6. Terry,D.B., Theimer, M. M., Petersen, K., Demers, A.J. Managin update conflicts in Bayou, a weakly connected replicated storage system. In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles. ?

7. http://freenetproject.org/, http://www.gnutella.org ?

8. Rowsron,A., and Druschel, P. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. ?

9. Stoica, I., Morris, R., Karger, D., Chord: A scalable peer-to-peer lookup service for internet applications. ?

10. Kubiatowicz, J., Bindel, D., Chen, Y. OceanStore: an architecture for global-scale persistent storage. ?

11. Rowstron, A., and Druschel, P.Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. ?

12. Terry, D.B., THEIMER, M.M., Petersen, K. Managin update conflicts in Bayou, a weakly connected replicated storage system. ?

13. Reiher, P., Heidemann, J., Ratner, D. Resolving file conficts in the Ficus file system. ?

14. Satyanarayanan, M., Kistler, J.J., Siegel, E.H. Coda: A Resilient Distributed File System. ?

15. Adya, A., Bolosky, W.J., Castro, M. Farsite: federated, available, and reliable storage for an incompletely trusted environment. ?

16. T erry,D.B., Theimer, M. M., Petersen, K., Demers, A.J. Managin update conflicts in Bayou, a weakly connected replicated storage system. ?

17. Saito, Y., Frolund, S., Veitch, A., Merchant, A. FAB: building distributed enterprise disk arrays from commodity components. ?

18. Weatherspoon, H., Eaton, P., Chun, B. Antiquity: exploiting a secure log for wide-aera distributed storage. ?

19. Bernstein, P.A., and Goodman, N. An algorithm for concurency control and recovery in relicated distributed databases. ?

20. Gray, J., Helland, P., O'Neil, P. The dangers of replication and a solution. ?

21. Karge, D., Lehman, E., Leighton, T., Panigraphy, R., Levine, M. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. ?

22. Stoica, I., Morris, R., Karger, J.J., Siegel, E.H. Coda: A Resilient Distributed File System. ?

23. Lamport, L. Time, clocks,and the ordering of events in a distributed system. ?

24. Merkle, R. A digital signature based on a conventional encryption function. ?

25. Gupta, I. Chandra, T. D. and Goldsmidt, G. S. On scalable and efficient distributed failure detectors. ?

26. Douceur, J.R. and Bolosky, W.J. 2000. Process-based regulation of low-importance process. ?

27. Ramasubramanian, v., AND Sirer, E.G. Beehive: O(1)
    lookup performance for power-law query distribution in peer-to-peer oveylays. ?