一致性哈希算法分區(qū)
一致性Hash算法背景
　　一致性哈希算法在1997年由麻省理工學(xué)院中提出的，設(shè)計目標(biāo)是為了解決
分布式緩存數(shù)據(jù)變動和映射問題，某個機器宕機了，分母數(shù)量改變了，自然取余數(shù)不OK了。
  
   提出一致性Hash解決方案。 目的是當(dāng)服務(wù)器個數(shù)發(fā)生變動時，盡量減少影響客戶端到服務(wù)器的映射關(guān)系

1、算法構(gòu)建一致性哈希環(huán)
一致性哈希環(huán)
    一致性哈希算法必然有個hash函數(shù)并按照算法產(chǎn)生hash值，這個算法的所有可能哈希值會構(gòu)成一個全量集，這個集合可以成為一個hash空間[0,2^32-1]，這個是一個線性空間，但是在算法中，我們通過適當(dāng)?shù)倪壿嬁刂茖⑺孜蚕噙B(0 = 2^32),這樣讓它邏輯上形成了一個環(huán)形空間。
 
   它也是按照使用取模的方法，前面筆記介紹的節(jié)點取模法是對節(jié)點（服務(wù)器）的數(shù)量進行取模。而一致性Hash算法是對2^32取模，簡單來說，一致性Hash算法將整個哈希值空間組織成一個虛擬的圓環(huán)，如假設(shè)某哈希函數(shù)H的值空間為0-2^32-1（即哈希值是一個32位無符號整形），整個哈希環(huán)如下圖：整個空間按順時針方向組織，圓環(huán)的正上方的點代表0，0點右側(cè)的第一個點代表1，以此類推，2、3、4、……直到2^32-1，也就是說0點左側(cè)的第一個點代表2^32-1， 0和2^32-1在零點中方向重合，我們把這個由2^32個點組成的圓環(huán)稱為Hash環(huán)。

2、服務(wù)器IP節(jié)點映射

將集群中各個IP節(jié)點映射到環(huán)上的某一個位置。
   將各個服務(wù)器使用Hash進行一個哈希，具體可以選擇服務(wù)器的IP或主機名作為關(guān)鍵字進行哈希，這樣每臺機器就能確定其在哈希環(huán)上的位置。假如4個節(jié)點NodeA、B、C、D，經(jīng)過IP地址的哈希函數(shù)計算(hash(ip))，使用IP地址哈希后在環(huán)空間的位置如下：

3、key落到服務(wù)器的落鍵規(guī)則

當(dāng)我們需要存儲一個kv鍵值對時，首先計算key的hash值，hash(key)，將這個key使用相同的函數(shù)Hash計算出哈希值并確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán)順時針“行走”，第一臺遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器，并將該鍵值對存儲在該節(jié)點上。
如我們有Object A、Object B、Object C、Object D四個數(shù)據(jù)對象，經(jīng)過哈希計算后，在環(huán)空間上的位置如下：根據(jù)一致性Hash算法，數(shù)據(jù)A會被定為到Node A上，B被定為到Node B上，C被定為到Node C上，D被定為到Node D上。