海量存儲之十九--一緻性和高可用專題

--------dynamo and cassandra ----------

這兩套系統，其實是同源的，我其實不是很願意來說這兩套系統，因為他們用的技術比較學術化，是以比較複雜一些。。anyway ,i'll try my best !

提到這兩個系統，他們在核心思路上是非常類似的，但有一些細節性的東西又有所偏重，在分布式系統中也算是獨樹一幟了，很有代表性的一個系列，這些不一緻的地方，最明顯的地方就在于一緻性上。可見，哪怕是從追求簡單為上的工程化實作來說，各種不同的方式實作一緻性也都有很大的不同，不過他們也有一些共性和一些獨樹一幟的概念，下面來做一下分别解說。

先說共性：

w+r>n

相信這個大家都耳熟能詳了吧？呵呵，我從其他角度來說明這件事吧。

n表示這個複制叢集的總數【很多地方解釋的不是很準确造成了不少誤解】。

w表示寫入份數

r表示一次一緻性讀所需要的份數（這裡要注意，是随機從n中選擇的機器數量哦）

這個公式表示為：如果滿足w+r>n(w,r,n 屬于不為負數的整數且r,w<n），那麼叢集的讀寫是強一緻的。如果不滿足，那麼這個複制叢集的讀寫是非強一緻的。

這裡我強調一下，這裡的“叢集”，是指資料完全相同的多份拷貝。不涉及資料切分哦:)

這個公式的最常用的用法是求r，也就是說公式應該寫成n-w<r(w,r,n 屬于不為負數的整數且r,w<n）。

我們舉幾個常見的例子：

1. 簡單的主備強一緻複制。

因為是強一緻，是以資料一定是寫夠兩份的，w=2.

這個叢集的節點數呢？隻有兩台，是以n=2.

那麼r>(n-w = 2 - 1 = 0).

r> 0 是以r可以取 1， 2。 不能取三，因為機器數隻有2.。取不來3 

 .

2. 假定有三台機器，使用quorum的方式強一緻的寫入資料。

因為有三台機器，是以n=3.

因為是進行quorum寫入，隻要寫兩台就算成功了，是以w=2

這時候r>(n-w=3-2=1)

是以r的取值隻可能是2,3

r的取值意味着什麼？意味着你必須從n=3台機器中，最少随機選擇兩台進行讀取，才有可能讀取到資料的最新值。

3. 假定有三台機器，寫一台就算成功。

因為是進行quorum寫入，隻要寫一台就算成功，是以w=1.

這時候r>(n-w=3-1=2)

r的取值隻可能是3。

這意味着什麼？意味着如果你隻寫一台機器就算做成功，那麼你在讀取的時候需要讀取3台機器，才能取得資料的最新值。

具體證明我就不列了，感興趣自己去看一下:) . 枚舉一下很容易可以得出結論的。

gossip協定

gossip協定是這兩套存儲的基礎之一，說複雜也複雜，說不複雜也不複雜。。其實gossip就是p2p協定。他主要要做的事情是，去中心化。

怎麼做到的呢？我隻希望在這篇文章裡給大家留下幾個印象：gossip是幹什麼的？怎麼做到的？優勢劣勢是什麼？即可。對協定的細節感興趣的，可以自己去深入研究。

gossip的核心目标就是去中心。

做到的方式：

根據種子檔案，按照某種規則連接配接到一些機器，與他們建立聯系，不追求全局一緻性，隻是将對方機器中自己沒有的資料同步過來。這裡就設計到如何能夠快速的知道自己的資料和其他人的資料在哪些部分不一緻呢？這時候就要用到merkle tree了，它能夠快速感覺自己所持有的資料中哪裡發生了變更。

優勢：

去中心化，看看偉大的tor，隻要能連到一個seed，有一個口子能出長城，那麼你最終就能跳出長城。。

劣勢：

一緻性比較難以維持，

（這裡我們介紹很簡單，因為我也沒有實際的寫過。。。如果誰有這方面經驗歡迎補充）

不同選擇:

dynamo : vector clock vs. cassandratimestamp.

這兩個協定的目标都是解決一緻性的。也是我們要說的重點。

我們先來說說vector clock:

提到vector clock ，不能不提lamport的另一篇論文time clocks and the ordering of events in a distributed system(中文翻譯http://t.cn/zlewzin)

這篇文章核心講的是多程序之間的互斥和排隊問題。不過這不是我們主要的要吸收的，在這篇文章中，更多的能夠讓你意識到一個問題：原來你跑到了一個相對論的世界裡。也即，在程序之間沒有消息互相通知的時候，他們就是各自為政的，遵循着自己的時鐘的。隻有在當他們之間有了互相之間的消息傳遞的時候，才有可能創造一個全局時間序出來。

vector clock 給我的感覺，就正是沿着這條路子思考下去得出來的一種方式。如果要我一定有一個現實生活的類比的話，我想說，vector clock給我的感覺更像git .

讓我們從他與paxos的比較上面開始吧。

在paxos裡面，我們使用quorum和類三階段送出的方式來保證資料提議是順序的，一次隻會有一個提議被接受。

這樣在一個場景下效率不是最高的：如果我們假定，大部分場景更新的資料都不重複，那麼效率就不會高了。

比如，如果我們不斷地往一個kv裡面進行以下操作:

{檢視a夠不夠100塊？如果夠，減少100塊}

...

如果不斷地塞入這種資料，那麼實際上每次的寫入都依托了上一次資料的值。這種操作是必須排隊才會高效的，否則會出現超減的情況的。

但如果我們的操作隻是我們不斷地往一個kv裡面進行以下操作:

a登陸了

b登陸了

c登陸了

d登陸了

e登陸了

f登陸了

那麼可以認為，所有的資料之間都是“互相沒有關系的”， 這時候，再讓這些寫入全部排隊一次，代價明顯就高了。

我了解的dynamo和cassandra，他們的場景主要是适合後面的這種方式，也即資料之間沖突很小的情況。在這種情況下，維持一個全局有序的隊列的效率太低了，不如這種分散式的方式。

但沖突的機率小，并不意味着沒有沖突，是以，還是需要有一套機制，能夠幫你感覺哪些資料出現了沖突，允許你進行沖突處理的。

而在這個問題上dynamo和cassandra選擇了不同的道路。

dynamo選擇了vector clock .

他的主要方式是：在資料傳遞的資訊中，額外帶上這資料是從哪裡來的版本是多少。

我們來看看，用這種方式，如何能夠知道什麼時候發生了沖突：

我們假定有a,b,c三台機器。

初始的時候，a,b,c三台機器的資料sequence都是100.

這時候，我随機挑了一台機器,b寫了一行記錄[key=whisper , val=0]

這時候b生成的資料是議案[101 from b->[key=whisper , val=0]].

然後，又有另外一個人選擇c寫了另外一條記錄，比如[key=whisper , val=10000]

這時候c生成的資料議案是[101 from c->[key=whisper , val=10000]]

這時候，b的資料傳遞給c. 因為c也有個101的議案，是以【他會保持兩份議案】（請注意，這是和paxos不一緻的地方哦）

是以c接受的議案是

[101号議案

{fromb [key=whisper , val=0]}

{fromc [key=whisper , val=10000]}

]

然後怎麼辦？然後。。。。然後你在get("whisper")這個資料的時候，vector clock會把這兩條記錄都回報給你，告訴你，沖突，你自己選擇一條吧:)

那麼，這樣我們有幾種選擇，對于{count ++ 類}操作，應該将所有決議合并加到一起。

而對于其他資料，則應該按照時間戳，取時間戳最大的資料，這是最新的。

這就是vector clock的工作流程，在合并這段，讓我很容易就想到svn或git中的沖突解決。。

怎麼樣？是否覺得思路更開闊了？歡迎大家基于paxos和vector clock再進行其他思考，一緻性的研究遠遠沒有結束。

就我個人嘛。。我更喜歡能保證順序的一緻性模型，不喜歡這種各自為政按需合并的模型。

好，說完了vector clock 我們來說說cassandra 的timestamp.

其實，timestamp模型是vector clock的劣化和簡化版本。在vector clock裡面，沖突是由使用者處理的，系統隻是幫你檢查沖突，但cassandra做的更粗暴和簡單一些。他不檢測沖突，所有資料隻保留時間戳最大的那個。

這種模型可以應對80%場景了，模型得到了極大簡化，不過我估計應該是不能做count++操作了吧？我沒實際使用過。

好，回顧一下，我們在剛才講了三個新概念： w+r>n .用來決定一緻性級别。gossip協定和merkle tree，用來進行去中心化的節點間資料同步。vector clock或timestamp.

現在是拼裝時間。

dynamo : 資料同步使用了gossip+merkletree, 使用vector clock來标記沖突資料，沖突資料會交給使用者做出處理。允許通過配置，指定一組小叢集有幾個相同資料的equalty group(n).以及你要寫入并保證同時成功的份數(w),以及你要讀的份數(r)。

cassanra :與dynamo類似（因為同源）， 在選擇上，放棄了vectorclock，使用timestamp來進行沖突合并。其餘的類似。