分布式哈希和一致性哈希是分布式存儲和p2p網絡中說的比較多的兩個概念了。介紹的論文很多，這里做一個入門性質的介紹。

分布式哈希(DHT)
　　兩個key point：每個節點只維護一部分路由；每個節點只存儲一部分數據。從而實現整個網絡中的尋址和存儲。
DHT只是一個概念，提出了這樣一種網絡模型。并且說明它是對分布式存儲很有好處的。但具體怎么實現，并不是DHT的范疇。

一致性哈希：
　　DHT的一種實現。本質還是一個哈希算法。回想平時我們做負載均衡，按querystring簽名對后端節點取模是最簡單也是最常用的算法，但節點的增刪后所造成的問題顯而易見，原有的請求幾乎都落不到同一臺機器上。優化一點的是carp算法（用機器ip和querystring一起做hash，選取hash值最小的一臺），只讓1/n的數據受到影響。
一致性哈希，似乎最早提出是在分布式cache里面的，讓節點震蕩的時候，影響最小，以提高分布式cache的命中率。不過現在更多的應用在分布式存儲和p2p系統里面。

　　一致性哈希也只是提出四個概念和原則，并沒有提及具體實現：

　　1、balance：哈希結果盡可能的平均分散到各個節點上，使得每個節點都能得到充分利用。

　　2、Monotonicity：上面也說了，如果是用簽名取模算法，節點變更會使得整個網絡的映射關系更改。如果是carp，會使得1/n的映射關系更改。一致性哈希的目標，是節點變更，不會改變網絡的映射關系。

　　3、spread：同一份數據，存儲到不同的節點上，換言之就是系統冗余。一致性哈希致力于降低系統冗度。

　　4、load：負載分散，和balance其實是差不多的意思，不過這里更多是指數據存儲的均衡，balance是指訪的均衡。

Chord算法：
　　一致性哈希有多種實現算法，最關鍵的問題在于如何定義數據分割策略和節點快速查詢。

　　chord算是最為經典的實現。cassandra中的DHT，基本是chord的簡化版。

　　網絡中每個節點分配一個唯一id，可以通過機器的mac地址做sha1，是網絡發現的基礎。

　　假設整個網絡有N 個節點，并且網絡是呈環狀。兩個節點間的距離定義為節點間下標差。每個節點會存儲一張路由表(finger表)，表內順時針按照離本節點2、4、8、16、32.……2i的距離選定log2N個其他節點的ip信息來記錄，主要是為了查詢加速。

　　存儲：數據被按一定規則切割，每一份數據也有一個獨立id(查詢key)，并且和節點id的值域是一樣的。然后查找節點，如果存在和數據id一樣的節點id，則將這份數據存在該節點上；如果不存在，則存儲到離該數據id距離最近的節點上。同時，為了保證數 據的可靠性，會順時針往下找K個冗余節點，存儲這份數據。一般認為K=3是必須的。

　　下圖簡單描述了一個chord網絡的部署，綠色節點為機器，編碼為hash值。N0節點的finger表可以看出N0節點的路由規則，其他節點也有類似的finger表。藍色節點為數據，根據hash值找到最近的節點并存儲。虛線所指是表示冗余存儲。

　　查詢：先從自己的路由表中，找一個和數據id距離最近、并且存活在網絡中的節點next。如果該節點的 id巧合和數據id相等，那么恭喜你。如果不相等，則到next進行遞歸查找。一般或需要經過多次查詢才能找到數據所在的節點，而這個次數是可以被證明小于等于log2N的。

　　在這個查詢的過程中就體現了路由表的選取優勢了，其實是實現了一個二分查找，從每個節點來觀察網絡，都是將網絡分成了log2N塊，最大一塊里面有N/2個節點。路由表里面其實是記錄了每一塊的第一個節點。這樣每一次查詢，最少排除了一半的節點。保證在 log2N次內找到目標節點。

　　下圖簡單展示了從N0節點查找N21節點的一個數據的過程，通過finger表經過2跳到達目的地。

　　新增一個節點i：需要預先知道網絡中已經存活的一個節點j，然后通過和節點j交互，更新自己和其他節點的路由表。并且，需要將離自己距離最近的節點中的數據copy過來，以提供數據服務。

　　損失一個節點：路由算法會自動跳過這個節點，并且依靠數據的冗余來持續提供服務。

KAD算法(Kademlia)
　　kad算法其實是在chord上做的優化。主要是兩個點：
　　1、用二進制(32/64/128)表示一個節點的id，兩節點的id異或運算得到節點間的距離。
　　2、 每個節點保持的路由信息更豐富，同樣是將整個網絡按照劃分成log2N份，在chord中，是保持log2N個路由節點，但在kad里面，是保存了 log2N個隊列。每個隊列長度為配置值K，記錄網絡中對應節點區域的多個節點，并且根據活躍時間對這些節點進行換入換出。
　　第一點是方便進行網絡劃分，節點按照二進制中每一bit的0或1建成一棵二叉樹。

　　第二點是使得節點查詢更迅速。從分割情況我們就可以得知，最壞情況不會差于chord，但保存更多的節點使得命中概率更高。另外隊列中根據活躍時間進行換入換出，更有利于在p2p這種節點變更頻繁的網絡中快速找到有效的節點。

　　關于kad的介紹，這篇文章講的比較詳細 wenku.baidu.com/view/ee91580216fc700abb68fcae.html

“分布式哈希”和“一致性哈希”的概念與算法實現