什么是一致性哈希算法

什么是一致性哈希算法目錄一致性哈希算法的提出哈希算法滿足的4個(gè)適應(yīng)條件一致性哈希算法工作原理2一致性哈希算法不足一致性哈希算法作用一致性哈希算法的提出一致性哈希算法在1997年由麻省理工學(xué)院提出，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡(jiǎn)單哈希算法帶來的問題，使得DHT可以在P2P環(huán)境中真正得到應(yīng)用。34一致性哈希算法工作原理在移除/添加一個(gè)cache時(shí)，它能夠盡可能小的改變已存在key映射關(guān)系，盡可能的滿足單調(diào)性的要求。環(huán)形哈希空間把需要緩存的內(nèi)容(對(duì)象)映射到哈?？臻g把服務(wù)器(節(jié)點(diǎn))映射到哈希空間把對(duì)象映射到cache考察cache的變動(dòng)虛擬節(jié)點(diǎn)5哈希算法滿足的4個(gè)適應(yīng)條件均衡性：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。單調(diào)性：?jiǎn)握{(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中，又有新的緩沖區(qū)加入到系統(tǒng)中，那么哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖區(qū)中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。6哈希算法滿足的4個(gè)適應(yīng)條件分散性：當(dāng)終端希望通過哈希過程將內(nèi)容映射到緩沖上時(shí)，由于不同終端所見的緩沖范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。負(fù)載：負(fù)載問題實(shí)際上是從另一個(gè)角度看待分散性問題。7一致性哈希算法作用一致性哈?；窘鉀Q了在P2P環(huán)境中最為關(guān)鍵的問題——如何在動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)渲蟹植即鎯?chǔ)和路由。每個(gè)節(jié)點(diǎn)僅需維護(hù)少量相鄰節(jié)點(diǎn)的信息，并且在節(jié)點(diǎn)加入/退出系統(tǒng)時(shí)，僅有相關(guān)的少量節(jié)點(diǎn)參與到拓?fù)涞木S護(hù)中。所有這一切使得一致性哈希成為第一個(gè)實(shí)用的DHT算法。8一致性哈希算法不足在查詢過程中，查詢消息要經(jīng)過O(N)步(O(N)表示與N成正比關(guān)系，N代表系統(tǒng)內(nèi)的節(jié)點(diǎn)總數(shù))才能到達(dá)被查詢的節(jié)點(diǎn)。當(dāng)系統(tǒng)規(guī)模非常大時(shí)，節(jié)點(diǎn)數(shù)量可能超過百萬，這樣的查詢效率顯然難以滿足使用的需要。換個(gè)角度來看，即使用戶能夠忍受漫長(zhǎng)的時(shí)延，查詢過程中產(chǎn)生的大量消息也會(huì)給網(wǎng)絡(luò)帶來不必要的負(fù)荷。9總結(jié)一致性哈希算法通過減少影響范圍的方式解決了增減服務(wù)器導(dǎo)致的數(shù)據(jù)散列問題，從而解決了分布式環(huán)境下負(fù)載均衡問題，如果存在熱點(diǎn)數(shù)據(jù)，那么通過增添節(jié)點(diǎn)的方式，對(duì)熱點(diǎn)區(qū)間進(jìn)行劃分，將壓力分配至其他服務(wù)器。重新達(dá)到負(fù)載均衡的狀態(tài)。一致性哈