簡(jiǎn)述一致性哈希算法
cc 哈希算法有很多變體，使其可以在不同的場(chǎng)景下應(yīng)用。下面我們就來了解一種可以有效解決分布式緩存問題的哈希算法——一致性哈希算法。
一致性哈希算法簡(jiǎn)介
一致性哈希算法是麻省理工學(xué)院在1997年提出的一種特殊的哈希算法，在分布式系統(tǒng)中有著廣泛的應(yīng)用。
簡(jiǎn)單來說就是在移除或者添加一個(gè)服務(wù)器時(shí)，此算法能夠盡可能小地改變已存在的服務(wù)請(qǐng)求與處理請(qǐng)求服務(wù)器之間的映射關(guān)系，盡可能滿足單調(diào)性的要求。
一致性哈希算法的原理
一致性哈希算法將整個(gè)哈希值空間按照順時(shí)針方向組織成一個(gè)虛擬的圓環(huán)，稱為Hash環(huán)；
接著將各個(gè)服務(wù)器使用Hash函數(shù)進(jìn)行哈希，具體可以選擇服務(wù)器的IP或主機(jī)名作為關(guān)鍵字進(jìn)行哈希，從而確定每臺(tái)機(jī)器在哈希環(huán)上的位置；
最后使用算法定位數(shù)據(jù)訪問到相應(yīng)服務(wù)器，將數(shù)據(jù)key使用相同的函數(shù)Hash計(jì)算出哈希值，并確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán)順時(shí)針尋找，第一臺(tái)遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器。
一致性哈希算法的具體流程
一致性哈希算法是對(duì) 2^32 取模，具體步驟如下：
步驟一：哈希環(huán)的組織
我們將 2^32 想象成一個(gè)圓，像鐘表一樣，鐘表的圓可以理解成由60個(gè)點(diǎn)組成的圓，而此處我們把這個(gè)圓想象成由2^32個(gè)點(diǎn)組成的圓。
圓環(huán)的正上方的點(diǎn)代表0，0點(diǎn)右側(cè)的第一個(gè)點(diǎn)代表1，以此類推，2、3、4、5、6……直到2^32-1,也就是說0點(diǎn)左側(cè)的第一個(gè)點(diǎn)代表2^32-1，我們把這個(gè)由 2^32 個(gè)點(diǎn)組成的圓環(huán)稱為hash環(huán)。
步驟二：確定服務(wù)器在哈希環(huán)的位置
哈希算法為：hash（服務(wù)器的IP）% 2^32
上述公式的計(jì)算結(jié)果一定是 0 到 2^32-1 之間的整數(shù)，那么上圖中的 hash 環(huán)上必定有一個(gè)點(diǎn)與這個(gè)整數(shù)對(duì)應(yīng)，所以我們可以使用這個(gè)整數(shù)代表服務(wù)器，也就是服務(wù)器就可以映射到這個(gè)環(huán)上，假設(shè)我們有 ABC 三臺(tái)服務(wù)器，那么它們?cè)诠－h(huán)上的示意圖如下：
步驟三：將數(shù)據(jù)映射到哈希環(huán)上
我們還是使用圖片的名稱作為 key，所以我們使用下面算法將圖片映射在哈希環(huán)上：hash（圖片名稱）% 2^32，假設(shè)我們有4張圖片，映射后的示意圖如下，其中橘黃色的點(diǎn)表示圖片：
只要從圖片的位置開始，沿順時(shí)針方向遇到的第一個(gè)服務(wù)器就是圖片存放的服務(wù)器了。最終，1號(hào)、2號(hào)圖片將會(huì)被緩存到服務(wù)器A上，3號(hào)圖片將會(huì)被緩存到服務(wù)器B上，4號(hào)圖片將會(huì)被緩存到服務(wù)器C上。
一致性哈希算法的特
- 平衡性：不同key通過算法映射后，可以比較均衡地分布到所有的后端節(jié)點(diǎn)上。
- 單調(diào)性：當(dāng)有新的節(jié)點(diǎn)上線后，系統(tǒng)中原有的key要么還是映射到原來的節(jié)點(diǎn)上，要么映射到新加入的節(jié)點(diǎn)上，不會(huì)出現(xiàn)從一個(gè)老節(jié)點(diǎn)重新映射到另一個(gè)老節(jié)點(diǎn)。
- 穩(wěn)定性：當(dāng)服務(wù)發(fā)生擴(kuò)縮容的時(shí)候，發(fā)生遷移的數(shù)據(jù)量盡可能少。
免責(zé)聲明：素材源于網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系刪稿。
