|
Merkle Tree是Dynamo論文中用到的一個(gè)算法，讀這篇論文前，我并不知道這個(gè)算法，所以找了相關(guān)資料了解了解，以便我對論文有更進(jìn)一步的了解。
什么是Merkle Tree
Merkle Tree，是一種樹（數(shù)據(jù)結(jié)構(gòu)中所說的樹），網(wǎng)上大都稱為Merkle Hash Tree,這是因?yàn)?它所構(gòu)造的Merkle Tree的所有節(jié)點(diǎn)都是Hash值。Merkle Tree具有以下特點(diǎn)：
1. 它是一種樹，可以是二叉樹，也可以多叉樹，無論是幾叉樹，它都具有樹結(jié)構(gòu)的所有特點(diǎn)；
2. Merkle樹的葉子節(jié)點(diǎn)上的value，是由你指定的，這主要看你的設(shè)計(jì)了，如Merkle Hash Tree會將數(shù)據(jù)的Hash值作為葉子節(jié)點(diǎn)的值；
3 非葉子節(jié)點(diǎn)的value是根據(jù)它下面所有的葉子節(jié)點(diǎn)值，然后按照一定的算法計(jì)算而得出的。如Merkle Hash Tree的非葉子節(jié)點(diǎn)value的計(jì)算方法是將該節(jié)點(diǎn)的所有子節(jié)點(diǎn)進(jìn)行組合，然后對組合結(jié)果進(jìn)行hash計(jì)算所得出的hash value。
例如，下圖就是一個(gè)Merkle Hash Tree形狀，如果它是Merkle Hash Tree，則節(jié)點(diǎn)7的hash value必須是通過節(jié)點(diǎn)15、16上的value計(jì)算而得到.
圖一 Merkle Hash Tree
為什么要使用Merkle Tree
目前， 在計(jì)算機(jī)領(lǐng)域，Merkle Tree大多用來進(jìn)行比對以及驗(yàn)證處理。在處理比對或驗(yàn)證的應(yīng)用場景中時(shí)，特別是在分布式環(huán)境下進(jìn)行比對或驗(yàn)證時(shí)，Merkle Tree會大大減少數(shù)據(jù)的傳輸量以及計(jì)算的復(fù)雜度。例如，就拿圖一舉例，假如是 15,16.......30是一個(gè)個(gè)數(shù)據(jù)塊的hash值，我把這些數(shù)據(jù)從A傳輸?shù)紹，數(shù)據(jù)傳輸?shù)紹后，我想驗(yàn)證下傳輸?shù)紹上的數(shù)據(jù)的有效性型（驗(yàn)證數(shù)據(jù)是否在傳輸過程中發(fā)生變化），只需要驗(yàn)證A 和 B上所構(gòu)造的Merkle
Tree的root節(jié)點(diǎn)值是否一致即可，如果一致，表示數(shù)據(jù)是有效的，傳輸過程中沒有發(fā)生改變。假如在傳輸過程中，15對應(yīng)的數(shù)據(jù)被人篡改，通過Merkle Tree很容易定位找到（因?yàn)榇藭r(shí)，節(jié)點(diǎn)0,1,3,7,15對應(yīng)的hash值都發(fā)生了變化），定位的時(shí)間復(fù)雜度為O（log(n））.
Merkle Tree的應(yīng)用場景
BT下,載少BitTorrent文件的大小
Amazon Dynamo 副本同步
Amazon Dynamo 論文描述的副本同步技術(shù)是比較復(fù)雜的，在這，只是簡單的描述下 Dynamo是怎樣使用 Merkle Tree來對副本進(jìn)行同步的。而至于為什么要同步、同步詳細(xì)過程，容我在后面章節(jié)描述。
在Dynamo的數(shù)據(jù)劃分算法的章節(jié)里，我們描述了，Dynamo 集群的所有機(jī)器都分布在一致性Hash環(huán)上，每臺機(jī)器保存了Hash到機(jī)器區(qū)間（hash環(huán)上，兩個(gè)機(jī)器節(jié)點(diǎn)之間，稱機(jī)器區(qū)間）里的所有數(shù)據(jù)，同時(shí)，為了保證數(shù)據(jù)存儲的持久性，一臺機(jī)器上的數(shù)據(jù)會在其它機(jī)器上有備份，也就是所謂的副本。由于某些原因，副本需要同步，保持一致，既然要同步，就先要對副本數(shù)據(jù)進(jìn)行比對，找出不一致的地方，然后合并成統(tǒng)一的一個(gè)副本。而目前，我們所關(guān)心的是比對，需要牽涉到跨網(wǎng)絡(luò)傳輸，如果對機(jī)器上所有數(shù)據(jù)都進(jìn)行比對的話，數(shù)據(jù)傳輸量就會很大，從而造成“網(wǎng)絡(luò)擁擠”。為了解決這個(gè)問題，可以在每臺機(jī)器上針對每個(gè)區(qū)間里的數(shù)據(jù)構(gòu)造一棵Merkle
Tree，這樣，在兩臺機(jī)器間進(jìn)行數(shù)據(jù)比對時(shí)，從Merkle Tree的根節(jié)點(diǎn)開始進(jìn)行比對，如果根節(jié)點(diǎn)一樣，則表示兩個(gè)副本目前是一致的，不再需要任何處理；如果不一樣，則遍歷Merkle Tree，定位到不一致的節(jié)點(diǎn)也非?？焖伲蟠蠊?jié)省了比對時(shí)間以及數(shù)據(jù)的傳輸量。
在Git中的使用
Git的作用類似于SVN和CVS，但功能比它們都要強(qiáng)大，是個(gè)分布式處理資源協(xié)同使用的工具，具體我也不是很熟悉。但據(jù)說，在Git里對集群里的機(jī)器間的文件同步也是采用Merkle Tree來進(jìn)行比對的。具體技術(shù)細(xì)節(jié)，我猜可能是這樣： 為Git 工作目錄下的所有文件構(gòu)造一個(gè)Merkle Tree，因?yàn)槲募膶哟谓Y(jié)構(gòu)天生就適合構(gòu)造一棵樹， 機(jī)器間文件的同步也是采用Merkle Tree的比對原理來實(shí)現(xiàn)的，和在Dynamo中使用的一樣，只是葉子節(jié)點(diǎn)的值有點(diǎn)差異，一個(gè)是文件，一個(gè)鍵值對(key-value)。
注意，這個(gè)只是我個(gè)人猜測啊，如果我設(shè)計(jì)的話，就這么搞，應(yīng)該不是胡搞瞎搞吧， 呵呵！
參考文章： http:///merkle-hash-tree/
|
|
|
