成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

強(qiáng)一致性hash實(shí)現(xiàn)java版本及強(qiáng)一致性hash原理

hzc / 2481人閱讀

摘要：好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。一致性哈希算法的基本實(shí)現(xiàn)原理是將機(jī)器節(jié)點(diǎn)和值都按照一樣的算法映射到一個(gè)的圓環(huán)上。

一致性 hash

分布式過(guò)程中我們將服務(wù)分散到若干的節(jié)點(diǎn)上，以此通過(guò)集體的力量提升服務(wù)的目的。然而，對(duì)于一個(gè)客戶端來(lái)說(shuō)，該由哪個(gè)節(jié)點(diǎn)服務(wù)呢？或者說(shuō)對(duì)某個(gè)節(jié)點(diǎn)來(lái)說(shuō)他分配到哪些任務(wù)呢？

強(qiáng)哈希

考慮到單服務(wù)器不能承載，因此使用了分布式架構(gòu)，最初的算法為 hash() mod n, hash()通常取用戶ID，n為節(jié)點(diǎn)數(shù)。此方法容易實(shí)現(xiàn)且能夠滿足運(yùn)營(yíng)要求。缺點(diǎn)是當(dāng)單點(diǎn)發(fā)生故障時(shí)，系統(tǒng)無(wú)法自動(dòng)恢復(fù)。同樣不也不能進(jìn)行動(dòng)態(tài)增加節(jié)點(diǎn)。

弱哈希

為了解決單點(diǎn)故障，使用 hash() mod (n/m),

這樣任意一個(gè)用戶都有 m 個(gè)服務(wù)器備選，可由 client 隨機(jī)選取。

由于不同服務(wù)器之間的用戶需要彼此交互，所以所有的服務(wù)器需要確切的知道用戶所在的位置。

因此用戶位置被保存到 memcached 中。當(dāng)一臺(tái)發(fā)生故障，client 可以自動(dòng)切換到對(duì)應(yīng) backup，由于切換前另外 1 臺(tái)沒(méi)有用戶的 session，因此需要 client 自行重新登錄。

好處

他比強(qiáng)哈希的好處是：解決了單點(diǎn)問(wèn)題。

缺點(diǎn)

但存在以下問(wèn)題：負(fù)載不均衡，尤其是單臺(tái)發(fā)生故障后剩下一臺(tái)會(huì)壓力過(guò)大；不能動(dòng)態(tài)增刪節(jié)點(diǎn)；節(jié)點(diǎn)發(fā)生故障時(shí)需要 client 重新登錄

一致性 hash 算法

一致性 hash 算法提出了在動(dòng)態(tài)變化的 Cache 環(huán)境中，判定哈希算法好壞的四個(gè)定義：

平衡性(Balance)

平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。

單調(diào)性(Monotonicity)

單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。

分散性(Spread)

在分布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。

當(dāng)終端希望通過(guò)哈希過(guò)程將內(nèi)容映射到緩沖上時(shí)，由于不同終端所見(jiàn)的緩沖范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。

這種情況顯然是應(yīng)該避免的，因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲(chǔ)到不同緩沖中去，降低了系統(tǒng)存儲(chǔ)的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。

負(fù)載(Load)

負(fù)載問(wèn)題實(shí)際上是從另一個(gè)角度看待分散性問(wèn)題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對(duì)于一個(gè)特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同的內(nèi)容。

與分散性一樣，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。

普通的哈希算法（也稱(chēng)硬哈希）采用簡(jiǎn)單取模的方式，將機(jī)器進(jìn)行散列，這在cache環(huán)境不變的情況下能取得讓人滿意的結(jié)果，但是當(dāng)cache環(huán)境動(dòng)態(tài)變化時(shí)，
這種靜態(tài)取模的方式顯然就不滿足單調(diào)性的要求（當(dāng)增加或減少一臺(tái)機(jī)子時(shí)，幾乎所有的存儲(chǔ)內(nèi)容都要被重新散列到別的緩沖區(qū)中）。

代碼實(shí)現(xiàn) 實(shí)現(xiàn)邏輯

一致性哈希算法有多種具體的實(shí)現(xiàn)，包括 Chord 算法)，KAD 算法等實(shí)現(xiàn)，以上的算法的實(shí)現(xiàn)都比較復(fù)雜。

這里介紹一種網(wǎng)上廣為流傳的一致性哈希算法的基本實(shí)現(xiàn)原理，感興趣的同學(xué)可以根據(jù)上面的鏈接或者去網(wǎng)上查詢(xún)更詳細(xì)的資料。

一致性哈希算法的基本實(shí)現(xiàn)原理是將機(jī)器節(jié)點(diǎn)和key值都按照一樣的hash算法映射到一個(gè)0~2^32的圓環(huán)上。

當(dāng)有一個(gè)寫(xiě)入緩存的請(qǐng)求到來(lái)時(shí)，計(jì)算 Key 值 k 對(duì)應(yīng)的哈希值 Hash(k)，如果該值正好對(duì)應(yīng)之前某個(gè)機(jī)器節(jié)點(diǎn)的 Hash 值，則直接寫(xiě)入該機(jī)器節(jié)點(diǎn)，
如果沒(méi)有對(duì)應(yīng)的機(jī)器節(jié)點(diǎn)，則順時(shí)針查找下一個(gè)節(jié)點(diǎn)，進(jìn)行寫(xiě)入，如果超過(guò) 2^32 還沒(méi)找到對(duì)應(yīng)節(jié)點(diǎn)，則從0開(kāi)始查找(因?yàn)槭黔h(huán)狀結(jié)構(gòu))。

如圖 1 所示:

圖 1 中 Key K 的哈希值在 A 與 B 之間，于是 K 就由節(jié)點(diǎn)B來(lái)處理。

另外具體機(jī)器映射時(shí)，還可以根據(jù)處理能力不同，將一個(gè)實(shí)體節(jié)點(diǎn)映射到多個(gè)虛擬節(jié)點(diǎn)。

經(jīng)過(guò)一致性哈希算法散列之后，當(dāng)有新的機(jī)器加入時(shí)，將只影響一臺(tái)機(jī)器的存儲(chǔ)情況，

例如新加入的節(jié)點(diǎn)H的散列在 B 與 C 之間，則原先由 C 處理的一些數(shù)據(jù)可能將移至 H 處理，
而其他所有節(jié)點(diǎn)的處理情況都將保持不變，因此表現(xiàn)出很好的單調(diào)性。

而如果刪除一臺(tái)機(jī)器，例如刪除 C 節(jié)點(diǎn)，此時(shí)原來(lái)由 C 處理的數(shù)據(jù)將移至 D 節(jié)點(diǎn)，而其它節(jié)點(diǎn)的處理情況仍然不變。

而由于在機(jī)器節(jié)點(diǎn)散列和緩沖內(nèi)容散列時(shí)都采用了同一種散列算法，因此也很好得降低了分散性和負(fù)載。

而通過(guò)引入虛擬節(jié)點(diǎn)的方式，也大大提高了平衡性。

實(shí)現(xiàn)代碼 
consitent-hashing
原文地址 
consitent-hashing

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76734.html

相關(guān)文章

  • 分布式數(shù)據(jù)緩存中的一致性哈希算法

    摘要：一致性哈希算法能盡可能減少了服務(wù)器數(shù)量變化所導(dǎo)致的緩存遷移。哈希算法首先，一致性哈希算法依賴(lài)于普通的哈希算法。我們以下面四個(gè)量化的指標(biāo)對(duì)基于不同哈希函數(shù)的一致性哈希算法進(jìn)行評(píng)測(cè)。 一致性哈希算法在分布式緩存領(lǐng)域的 MemCached，負(fù)載均衡領(lǐng)域的 Nginx 以及各類(lèi) RPC 框架中都有廣泛的應(yīng)用，它主要是為了解決傳統(tǒng)哈希函數(shù)添加哈希表槽位數(shù)后要將關(guān)鍵字重新映射的問(wèn)題。 本文會(huì)介紹一...

    Towers 評(píng)論0 收藏0

  • 為什么ConcurrentHashMap是弱一致的

    摘要：是我們一直擁有的，即我們有，。中的迭代器中的迭代器主要包括方法。在遍歷過(guò)程中，如果已經(jīng)遍歷的數(shù)組上的內(nèi)容變化了，迭代器不會(huì)拋出異常。這就是迭代器弱一致的表現(xiàn)?？偨Y(jié)的弱一致性主要是為了提升效率，是一致性與效率之間的一種權(quán)衡。 本文將用到Java內(nèi)存模型的happens-before偏序關(guān)系（下文將簡(jiǎn)稱(chēng)為hb）以及ConcurrentHashMap的底層模型相關(guān)的知識(shí)。happens-be...

    CarterLi 評(píng)論0 收藏0

  • 通俗的方式理解動(dòng)態(tài)類(lèi)型，靜態(tài)類(lèi)型；強(qiáng)類(lèi)型，弱類(lèi)型

    摘要：不允許隱式轉(zhuǎn)換的是強(qiáng)類(lèi)型，允許隱式轉(zhuǎn)換的是弱類(lèi)型。拿一段代碼舉例在使用調(diào)用函數(shù)的時(shí)候會(huì)先生成一個(gè)類(lèi)模板運(yùn)行時(shí)生成，執(zhí)行的時(shí)候會(huì)生成類(lèi)模板，執(zhí)行的時(shí)候會(huì)生成類(lèi)模板。 0 x 01 引言 今天和一個(gè)朋友討論 C++ 是強(qiáng)類(lèi)型還是弱類(lèi)型的時(shí)候，他告訴我 C++ 是強(qiáng)類(lèi)型的，他和我說(shuō)因?yàn)?C++ 在寫(xiě)的時(shí)候需要 int，float 等等關(guān)鍵字去定義變量，因此 C++ 是強(qiáng)類(lèi)型的，我告訴他 C+...

    周?chē)?guó)輝 評(píng)論0 收藏0

  • 一個(gè)兩年Java的面試總結(jié)

    摘要：數(shù)據(jù)結(jié)構(gòu)和算法樹(shù)快速排序，堆排序，插入排序其實(shí)八大排序算法都應(yīng)該了解一致性算法，一致性算法的應(yīng)用的內(nèi)存結(jié)構(gòu)。如何存儲(chǔ)一個(gè)的。八大排序算法一定要手敲一遍快排，堆排尤其重要。面試是一個(gè)雙向選擇的過(guò)程，不要抱著畏懼的心態(tài)去面試，不利于自己的發(fā)揮。 前言 16年畢業(yè)到現(xiàn)在也近兩年了，最近面試了阿里集團(tuán)（菜鳥(niǎo)網(wǎng)絡(luò)，螞蟻金服），網(wǎng)易，滴滴，點(diǎn)我達(dá)，最終收到點(diǎn)我達(dá)，網(wǎng)易o(hù)ffer，螞蟻金服二面掛掉，...

    anRui 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<