隨筆檔案

DHT全稱Distributed Hash Table (en.wikipedia.org/wiki/Distributed_hash_table)，在P2P系統中經常用來定位數據所屬機器。這就涉及到一致哈希(consistent hashing)思想，分布式系統中經常出現機器上下線，如果采用通常的Hash方法來查找數據所屬機器，機器上下線將導致整個集群的數據分布被打亂。這是因為，機器上下線將導致機器序號及Hash函數的改變，一致哈希做了簡單調整：每臺機器存儲哈希值和它最為接近的數據。在Chord系統中，順時針到達的第一臺機器即為最近的機器。
外部的數據可能首先傳輸至集群中的任意一臺機器，為了找到數據所屬機器，要求每臺機器維護一定的集群機器信息用于定位。最直觀的想法當然是每臺機器分別維護它的前一臺及后一臺機器的信息，機器的編號可以為機器IP的Hash值，定位機器最壞情況下復雜度為O(N)?？梢圆捎闷胶饣枷雭韮灮ㄈ缤胶舛鏄鋬灮瘮到M/鏈表），使每一臺機器存儲O(logN)的集群機器信息，定位機器最壞情況下復雜度為O(logN)。
首先考慮每臺機器維護前一臺及后一臺機器信息的情況，這里的問題是機器上下線導致緩存信息的不一致，我們需要設計協議使得在確定一段比較短的時間內能夠糾正這種錯誤。對于新機器加入，首先進行一次查找操作找到該機器的下一臺機器，并記錄下一臺機器的信息。機器內的每臺機器都定時向它的后繼發送心跳信息，如果后繼記錄的前一臺機器編號在二者之間，說明有新機器加入，這時需要更新后一臺機器編號為新加入編號；收到心跳信息的后繼也需要檢查，如果發送心跳的機器編號較為接近則更新為前一臺機器。機器下線將導致機器循環鏈表斷開，所以，每臺機器都維護了R個(一般取R值為3)最近的后繼信息，發現后繼節點下線時將通知其它后繼節點并加入新的替換節點。如果R個后繼節點同時下線，需要操作人員手工介入修復循環鏈。
Chord中的每臺機器維護O(logN)的機器信息是一種空間換時間的做法，實現時需要引入額外的消息交換協議。這種做法依賴于如下前提：每臺機器維護的前一臺機器及后一臺機器除了短時間不一致外總是正確的。

問題1：機器緩存短時間不一致有什么影響？數據正確性依靠什么保證？
短時間可能出現緩存的機器信息不正確的情況。比如有A, C, D, E四臺機器，再加入一臺機器B，機器加入的過程中，原本屬于B的數據可能寫入到B或者C，這都是允許的。又如刪除機器C，訪問機器C的節點得不到數據。數據的可用性及一致性還需要通過額外的replication及沖突處理協議解決。
問題2：DHT能否處理網絡分區問題？
DHT不能處理網絡分區問題，理論上存在整個DHT被分成多個子集的情況。我想，這時侯需要外部的機制介入，如維護一臺外部機器保存所有機器列表等。 閱讀全文
類別：默認分類 查看評論
文章來源:http://hi.baidu.com/knuthocean/blog/item/cca1e711221dcfcca6ef3f1d.html