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