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

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

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

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

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

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

　　3、spread：同一份數(shù)據(jù)，存儲到不同的節(jié)點上，換言之就是系統(tǒng)冗余。一致性哈希致力于降低系統(tǒng)冗度。

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

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

　　chord算是最為經(jīng)典的實現(xiàn)。cassandra中的DHT，基本是chord的簡化版。

　　網(wǎng)絡中每個節(jié)點分配一個唯一id，可以通過機器的mac地址做sha1，是網(wǎng)絡發(fā)現(xiàn)的基礎。

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

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

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

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

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

　　下圖簡單展示了從N0節(jié)點查找N21節(jié)點的一個數(shù)據(jù)的過程，通過finger表經(jīng)過2跳到達目的地。

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

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

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

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

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

“分布式哈希”和“一致性哈希”的概念與算法實現(xiàn)