論文筆記:Dynamo: Amazon’s Highly Available Key-value Store (上)

BLSxiaopanlaile 2022-01-07 12:03:55 阅读数:931

dynamo amazon highly available key-value

前言

這個月的博客打算記錄一篇論文,Dynamo:Amazon’s Highly Available Key-value Store 。這是亞馬遜2007年發錶的一篇論文,講的是其dynamo數據庫的一些設計原理。

做筆記如下,希望可以便人便己。

ps:這篇筆記以論文敘述為的大體框架

在這裏插入圖片描述

一、Abstract

由於大規模的基礎設施組件可能會不斷發生failure(和google gfs論文中的假想差不多),dynamo的主要設計初衷是為了滿足在這種情况下可以保持一定的可靠性(reliability)和擴展性(scalability)。為了提供這種"always-on"的高的可用性(highly availability),dynamo 犧牲了了一定程度的一致性(consistency)。它的一致性解决方案主要是靠版本控制(object version)和上層的應用輔助(application-assisted)來實現的.

總的來說,dynamo是一個為了提高可用性而犧牲一定程度的一致性的這樣一個KV存儲系統。

二、Introduction

這個部分介紹了在現實場景下確實有些應用需要一些高可用的KV存儲系統(這也是為什麼要設計dynamo的原因),比如說購物車購物的相關邏輯需要保證隨時能讀寫數據。

之後簡要介紹了了dynamo使用的一些技術要點:
在這裏插入圖片描述
圖一 dynamo中用到的一些問題和采取的技術


注:對於一個分布式存儲系統來說,其研究的重點主要也就是這些,分區、副本、一致性、故障檢測等等。

三、Background

為什麼需要dynamo這樣高可用性的KV存儲系統?文章中的觀點是對於很多應用來說,它們需要更多的是KV服務(以一個primary-key作為CURD的標識),這樣的服務雖然也可以用通用的mysql服務來實現,但是有點大材小用,或者說,不够完全的match。 因為mysql提供的是更結構化化的查詢存儲服務,同時提供了較高的事務特性,這些特點使得其在處理kv這樣的服務時,性能不够高。同時可用性和可擴展性也不够完善。

時代呼喚一個新的存儲系統,dynamo應運而生。

3.1 System Assumptions and Requirements

這裏說明了dynamo設計的一些基本假設和前提,主要包括查詢模型(Query Model)、事務特性(ACID)、系統效率(Efficiency)以及一些其他的假設。

  • 查詢模型: 系統的設計主要是針對於簡單的KV查詢(典型的no sql 模式),並且基本沒有跨多個key的join查詢方式,因此對於關系型數據庫中的那種schema是不需要的。

  • 事務特性:還是上文中敘述的,為了保證high-availablity ,系統放弃了强一致性,只保證了一種弱的一致性(consistency)。同時系統不提供隔離性(isolation)的保證,對於原子性(atomicity)來說,也只提供單key 更新操作。(對於持久性(Durability)來說,文章中沒有給出明確說明,但我覺得這個崩潰恢複這個特性是系統必須要提供的吧。)

  • 效率: 系統要能保證一定的服務等級,即對於請求來說,需要保證一定的延時範圍和吞吐量

  • 其他特性: dynamo 的目標是在企業內部使用,所以在設計時沒有考慮過多的安全性(比如說網絡認證等)。還有,dynamo對可擴展性(scale up)也有一定的需求。

3.2 Service Level Agreement (SLA)

這部分其實沒說什麼實質性的內容。討論的是在一個系統中為了保證服務質量,每個組件都應該保證一定的服務等級,這樣整個系統才可以給client提供一個最終的服務保證。 文中還敘述了amazon采用SLA的標准不是通常的平均數、中比特數或者期望這種,它采用的是個叫做99.9th的標准(具體是啥,我也不太清楚。(* / ω\*))

3.3 Design Considerations

這個部分講的是系統副本之(replication)間的一致性。對於多副本來說,其之間的數據複制是一個大問題。一般來說,有同步的方式和异步的方式。對於同步的方式來說,系統往往需要等到所有的(或者大多數或者指定多個,如quorum)副本都持有相同的數據之後才能向client返回。這樣的系統一般是强一致性的,根據CAP定理,這種系統往往犧牲了一定程度的可用性(即存在分區的時候,系統可能會unavailable)。
為了獲得高可用性,一些系統采用了异步複制(也叫做樂觀複制技術,optimistic replication techniques)的方式。數據的更改可以在後臺中慢慢進行,系統依舊可以提供服務。只不過這時可能會有數據不一致性情况。為了獲得高可靠性,dynamo采用的就是這種方式。
對於這種异步複制的系統來說,會遇到數據沖突的情况。這時何時解决沖突以及由誰來解决沖突就是個認真要考慮的問題了。
(1). 何時解决沖突: 文章中說有兩種解决方式,一種是read期間解决(在read的時候讀到了不同版本的數據進行沖突處理),一種是在write期間解决(在write的時候寫入到指定數量(所有的或者大多數結點)的replication中去以此來保證read操作的簡單)。dynamo為了保證“always writeable”,采用的是前者。

注:這裏所說的兩種沖突解决方式有點類似於quorum機制,需要做一個treadoff, 是保證write 簡單,還是read簡單。文中所說的在write期間解决的方式,好像和數據沖突沒啥大關系。╮(╯▽╰)╭

(2). 由誰來解决沖突:對於整個應用來說,應用邏輯一致性要求存儲系統和上層應用的(還有其他的組件)協調。某些時候可以把一致性要求放在下層的存儲系統中,也有些時候可以由應用邏輯來保證,還有的時候需要它們統一協作來保證系統的邏輯正確。對於dynamo來說,在read期間發生數據沖突的時候,它是由上層的應用程序來决定該如何處理


注:對於一般由存儲系統來解决數據沖突的情况,有一個選擇是“last write win”.

除了上面說的一致性要點,還有包括一些可擴展性、去中心化和對稱性以及不均勻性(heterogeneity)也是系統要考慮的點。

四、Related Work

這一節的內容相對來說不是很重要,下面只做簡單介紹。

4.1 Peer to Peer System

這裏簡單介紹了去中心化的p2p協議的相關系統,如pastry 和chord等。

4.2 Distributed FIle Systems and Databases

這一部分的主要內容有:

  • 不同於P2P網絡提供的是一種扁平化的命名空間(flat namespaces),分布式存儲系統大都提供的是一種層次化的命名空間(hierarchical namespaces)。

  • 分布式的多副本存儲雖然可以提高可用性(highly availability),但也帶來了一致性(consistency)方面的問題(因為各副本之間需要保持一致性)。這往往需要進行一定的權衡(trade off),高的可用性的系統一般就意味著一致性要弱些,比如說最終一致性。

  • Dynamo提供的是最終一致性,也就是說,它允許發生網絡分區(network partitions)的時候還可以進行讀寫操作。這就引起了一個問題,就是對於發生數據沖突(比如說updated confilcts)的時候,需要進行額外的措施解决(resolves)這個問題,以達到最終一致性的要求。

  • Dynamo 是Amazon內部使用的一個最終一致性存儲系統,所以它的設計更多的關注是高可用性,對於數據的完整性(data integrity)和安全性(security) 它倒是沒有關注太多。(Dynamo does not focus on the problem of data integrity and security and is built for a trusted environment.)

4.3 Discussion

這一段主要討論了dynamo 和其他非中心化存儲系統不同的幾點:

  • 它服務的上層是那些需要“always writeable”的應用,所以即使發生failure 或者concurrent writes的時候,系統也不能拒絕update操作。

  • dynamo建立在可信任的網絡之中。

  • 上層應用不需要支持層次命名空間或者複雜的關系schema.(applications that use Dynamo do not require support for hierarchical namespaces (anorm in many file systems) or complex relational schema (supported by traditional databases))

  • dynamo的設計目標是提供對延時敏感的應用(latency sensitive ),它可以在99.9%的情况下提供少於幾百ms的讀寫延時


在這裏插入圖片描述

五、System Architecture

一個存儲系統的設計包括很多方面,對於這篇論文來說主要討論的有數據分區(partition),副本處理(replication),版本控制(versioning),成員管理(membership),failure handing 和scaling。 概要如上圖一所示。

5.1 System Interface

dynamo 主要對外界提供了兩種接口:

  • get(key) 返回的是key所對應的object 或者一組有沖突的不同版本的object(a list of objects with conflictiong versions)
  • put(key,context,object): 向存儲系統內部寫入key-object值,context用來攜帶系統的metadat和版本的相關信息(The context encodes system metadata about the object that is opaque to the caller and includes information such as the version of the object.)

5.2 Partitioning Algorithm

dynamo 對於數據存儲分布或者說data partition法采用的是一致性hash算法,更確切的說采用的是改進版的一致性hash算法。
對於基本的一致性hash算法,簡要來說就是把數據空間看成一個環(ring),每個node 在其中占據一個比特置(hash成ring中的一個比特置),然後每個node只負責在兩個node之間的範圍內的數據(key經過hash映射後的比特置)如下圖所示。

在這裏插入圖片描述
對於一致性hash來說,其最大的優點就是:在node的加入或者移除的時候只影響其臨近的其他node結點(需要進行數據遷移)。

對於普通的一致性hash算法來說,文章中還說明了其兩個缺點:
(1) node的hash 比特置可能導致數據的不均勻分配,進而導致每個結點的負載不均衡。
(2) 這種算法沒有考慮到node性能的差异性。也就是說,對於性能較高的node,可以讓其負責更多的數據。

為了解决這個問題,文章中采取了優化後的一致性hash算法,即在hash換中引入了虛擬節點(virtual node),每個物理node對應多個虛擬節點,然後虛擬節點映射到ring中。這 從某種程度上來說算是加了一個分層,從key->node 變成了 key->virtual node-> physical node。

采用了優化後的一致性hash具有以下優點:
(1) 當添加或者删除node之時,數據的變動變得更為平均。即添加nodeA時,nodeA能够從其他多個node中較為均勻的獲取數據; 删除nodeA時,nodeA的數據也能較為平均的轉移給其他的結點。
(2) 可以根據每個node的capacity 來進行區別對待,比如說性能高的node分配更多的virtual node,這樣其就可以負責更多的數據。


注:

  1. partition算法還有很多,如按照時間、按照範圍、按照數據size進行分區; 系統的論述可以參見【2】

5.3 Replication

副本的作用在分布式存儲中主要是用來備份和提高系統性能(主要是讀性能)。在dynamo中為了獲得high availability 和 durability, 也采用了replication的機制。即每個key-value在整個分布式系統中要有N個副本,而且這N個副本要保存在N個獨立的physical node上,這樣一個node 宕機了,其他的N-1 個node才可以繼續提供服務。如下圖二所示。

在這裏插入圖片描述
圖二 數據分區示意圖

5.4 Data Versioning

因為提供了“always writable”的保證,dynamo 允許存在網絡分區的時候進行數據update操作。這個時候如果出現了數據更新沖突怎麼辦? dynamo采用的機制是使用數據多版本控制,即每個object維護一個一個向量時鐘(version clock),根據這個向量時鐘來進行沖突的解决,主要有syntactic reconciliation(主要是新版本正常覆蓋老版本,由系統自動覆蓋) 和 semantic reconciliation (同一個狀態由於並發更新引發的多沖突分支)。如下圖三所示。

在這裏插入圖片描述
圖三 版本並發控制示意圖

注:

  1. 按照我的理解,這裏dynamo系統使用的其實是一種樂觀的多版本並發控制技術-MVCC,通過保存數據的多個版本(只需要保存在並發過程中的版本,非並發過程的數據可以保存一份,也就是paper中說的synatactic reconciliation )來進行分布式的並發沖突處理,這有點類似於SVN或者git這種版本控制系統。

  2. 具體的判斷版本之間的因果關系(causality),即一個版本是否從另一個版本中演化而來。不同的系統可能使用不同的方案。這裏dynamo使用的的版本向量(version version),這是分布式的開山鼻祖Lamport的一篇paper。具體的內容可以參見【3】

5.5 Execution of get() and put() operations

這部分主要說了dynamo正常的讀寫操作。 其中重點有如下內容:

(1) 在client進行路由尋址的時候主要有兩種方式,一種是使用一個負載均衡器進行request分發;第二種是client端程序鏈接到一個partition-aware的庫程序(一般由開發者提供),通過調用庫程序來選擇request的請求node.

(2) 為了保持副本間的一致性要求,系統采用了類似quorum 協議。在寫入保證寫入W個副本才算寫入成功,在讀取時需要讀取R個副本。其中R+W>N 。(實際實現的時候並沒有采取這樣嚴格的quorum機制,而是使用的一種類似a sloppy quorum機制)

(3) 在put()時,系統會為新數據產生一個vector clock ,然後將新數據和其相關的vector clock同步到N個結點中。 只有至少W個結點正確write,put操作才算成功。

(4)在read()操作時,系統會從N個結點中讀取至少R個reolication的數據, 然後把數據返回給client。當然,這些數據有可能是有沖突的,需要client端來reconcile。

5.6 Handling Failures: Hinted Handoff

上面所說的a sloppy quorum機制就是使用基礎的quorum加上hinted handoff 實現的。也就是說如果待寫入的W個副本中有一個(或者一個以上)node(假設一個node中存儲一個replication) 發生宕機或者其他的failure, 那麼就會采用hinted handoff的機制。

所謂hinted handoff 也就是采用一個緩沖隊列,如果一開始向目標node發送數據時發生錯誤,那麼就會把待發送的replication 緩存在這個隊列中,然後在後臺的任務中周期的向目標結點進行重試,直到發送成功(或者超期删除)。在這個過程中可以執行此節點已經成功寫入(實際上不一定能够成功寫入)的相關邏輯(比如說如果凑齊了W個副本,則向client端成功返回)。

本質上是把一個同步傳輸的任務變成了异步傳輸的任務。

注:
有一個疑問點,如下圖所示,根據論文中所述,如果一個副本本該寫入A,B,C三個node,但是如果A fail 了,那麼系統會把本該發送給A的數據副本順延到D,由D來進行將數據周期發送給A的任務執行? 我的疑問是,為什麼不直接把數據放在B的緩存隊列中,由B進行周期傳送呢?難道是D 接受了本該由A的數據後還可以進行提供這個副本數據的讀取服務?

在這裏插入圖片描述
圖四 數據分區示意圖

5.7 Handling permanent failures:Replica synchronization

對於暫時性的網絡分區或者結點故障,使用上面的hinted handoff 可以取得較好的效果。但是如果遇到長時間的網絡分區或者結點完全宕機,那麼這會造成hinted handoff的緩沖隊列溢出(或者超出設定的最大時限),進而導致無法把數據异步發送到最終的node上去。

這個時候往往就需要進行額外的數據同步操作。dynamo為了處理這種情况采取了一種叫做反熵(anti-entropy)的副本同步機制
。為了快速對比replication之間的數據不一致(减少傳輸的數據量),dynamo采用了merkle tree(也叫做hash 樹)的一種數據結構。這種hash樹簡單來說就是構造一個hash樹,這棵樹的葉子結點是所有的數據塊,然後根據數據塊算出一個hash值,每兩個(或多個)hash值在共同算出一個hash值,一直向上遞推,直到根結點。如下圖所示。
在這裏插入圖片描述
圖五 hash tree 示意圖

在進行具體的比較時只需要從不同node的根結點進行比較,如果根結點相同,則說明兩棵hash樹是相同的,進而錶明tree所對應的數據塊是相同的;如果根結點不相同,則進行遞歸比較其左右子樹,知道確定最後不同的數據塊。如下圖六所示。
在這裏插入圖片描述
圖六 不同node上的hash 樹


具體的有關hash tree的原理可以參照【4】。

關於具體dynamo的實施細節,小生還不是非常理解,從相關資料【5】裏找到了以下一段文字。
在這裏插入圖片描述
圖七 dynamo有關hash tree的一段文字


注:

  1. 對於anti-entropy,也就是反熵來說,其更像一種概念。熵代錶的是系統的混亂程度,反熵說的是降低系統的混亂程度,使其變得更有秩序。在這裏也就是讓兩個replication之間的數據變得更加一致。從這種概念上來說,實現數據的一致有很多種方式,dynamo使用了hash樹加數據同步。【6】中也介紹了一些其他的方式。

  2. 對於dynamo使用hash樹來檢測replication的數據不一致還有一些小疑問: 如果兩個待比較的node之間的key數目不一樣怎麼辦?又或者說key1在node1中存在,但是在node2中不存在(本來應該存在),這樣怎麼構造hash樹呢?

5.8 Membership and Failure Detection

這個部分主要講的是成員變更和成員的failure 檢測。 由於dynamo采用的是去中心化的架構。所以在添加成員node時,其他的結點在開始的一段時間內是無法了解這個信息的。dynamo為了快速把消息傳遞給其他node結點,采用了gossip(謠言) 算法來吧消息傳遞出去。在dynamo系統中,gossip不僅用來傳遞成員變更的信息,還用來傳遞哪些node負責哪些key range 等元數據信息。 關於成員peer的failure detection, 系統也是使用gossip來傳遞的,其基本原理就是發送心跳消息,如果對方在指定的時間內沒有回複,則判斷其為failure, 然後當前結點把這個消息傳遞出去。

具體的gossip協議,網上有很多資料,在此就不贅述了(其實我也沒學過,^ _ ^)。


注:

  1. 對於成員信息、數據分區等這些元數據信息一般的系統是有一個中心化的結點(或者集群)來管理的。比如說gfs、bigtable等。這裏采用非中心化的架構,不能說其好壞,馬克思告訴我們,各有利弊而已。**( /ω\ *)
  2. gossip是一種簡單高效的peer to peer 信息交換系統, 它在DynamoDB裏面起到很重要的作用。

5.9 Adding/Removing Storage Nodes

這一部分沒講什麼太多的內容,主要具體介紹了一個結點加入(或者移除)member ring 中時,會對周圍的node造成一些影響,比如說數據的Rebalance、遷移等。

後記

論文內容比較多,這裏先介紹到這兒,剩下的部分不是重點,放在【下】中介紹了。


參考

【1】、通俗易懂 强一致性、弱一致性、最終一致性、讀寫一致性、單調讀、因果一致性 的區別與聯系
【2】、《分布式系統原理介紹》,劉傑
【3】、time-clocks
【4】、Merkle Tree概念
【5】、Dynamo基礎之Merkle Tree
【6】、Gossip協議:流言蜚語,原來也可以實現一致性
【7】、Dynamo: Amazon’s Highly Available Key-value Store

版权声明:本文为[BLSxiaopanlaile]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071203554043.html