偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

韓信大招:一致性哈希

開發(fā) 前端
韓信點兵的成語來源淮安民間傳說。常與多多益善搭配。寓意越多越好。我們來看下主公劉邦和韓信大將軍的對話。

 [[380000]]

韓信點兵的成語來源淮安民間傳說。常與多多益善搭配。寓意越多越好。我們來看下主公劉邦和韓信大將軍的對話。

劉邦:“你覺得我可以帶兵多少?”

韓信:“最多十萬。”

劉邦不解的問:“那你呢?”

韓信自豪地說:“越多越好,多多益善嘛!

假如劉邦現(xiàn)在給了韓信一千個士兵,需要大致均勻分成三組。士兵的編號是六位數(shù),從 1-100000 隨機分配。比如第一個士兵的值是 245,第二個士兵的編號是 82593,其他士兵類似。那么如何對士兵進(jìn)行分配呢?

劉邦:韓將軍,你看這些士兵怎么分配好呢?

韓信:這還不簡單,我的一技能就能搞定。

一技能:哈希算法

分組

韓信的一技能哈希算法:將士兵的編號 num 值當(dāng)做一個哈希值,再和總做小組數(shù) N 做取余操作,得出的結(jié)果在 0 到 N - 1 之間,這個士兵就屬于那個組。

如下圖所示,每來一個士兵都有一個六位的 hash 值(也可以稱作編號),然后被韓信用除以 3 取余數(shù)的方式分配到三個組。比如第一組中的編號為 123456 的士兵,除以 3 之后,整除,余數(shù)為 0,所以分配到第一組。

 

 


哈希算法

 

 

查找士兵

現(xiàn)在已經(jīng)分好組了,假如想找到編號為 666666 的士兵該怎么找?首先將 666666 除以 3,得到余數(shù) 0,說明在第一個組,然后去第一個組里面找就可以了。

這里有小伙伴可能會問,為什么不是把所有士兵放到一個組?

因為一個組太大了,影響行軍速度。映射到互聯(lián)網(wǎng)架構(gòu)中,就是通過增加節(jié)點從而減小單節(jié)點的負(fù)載壓力。

哈希分組弊端

劉邦看了這個一技能后,大呼:

韓將軍真是厲害。

哈希算法看起來很完美,那我再給你五百士兵,需要分成四個組怎么辦?

這時,韓信的副將說話了:

這還不簡單,再用 4 取余不就好了嗎?

劉邦摸著下巴思索片刻后,對副將說:

這個方案可行,但很多士兵都被重新分組了,剛剛建立的團(tuán)隊友情就被分解了。

我們來看下劉邦為什么覺得方案不可行。

比如原來分配到一組的編號為 3 的士兵,當(dāng)分成四組的時候,通過公式計算:3%4=3,所以會分配到到第四組。

依次類推,會發(fā)現(xiàn)很多士兵進(jìn)行了重新分配,只有小部分不會變換分組,比如 1,2,12 不會被重新分組。

韓信對著劉邦點點頭,對著主公說道:

主公,您說得沒錯,這就是我的一技能的弱點所在。

不過我還有一個技能:一致性哈希。

二技能:一致性哈希哈希環(huán)

一致性哈希算法也用了取模運算,但是它與哈希算法不同的地方:

  • 哈希算法:對節(jié)點的數(shù)量進(jìn)行取模運算。
  • 一致性哈希算法:對 2^32 進(jìn)行取模運算。

可以想象一下,一致性哈希算法,是將整個哈希值空間組成了一個虛擬的圓環(huán),也就是哈希環(huán)。

如下圖,把 3 個組映射到固定大小為 2^32 的哈希環(huán)中。三個組一共將整個環(huán)分成了三個區(qū)域,C-A(第一組)、A-B(第二組)、B-C(第三組)。如下圖所示:

 

 


分成三組

 

 

  • 第一組負(fù)責(zé)存儲落在 C-A 區(qū)間內(nèi)的數(shù)據(jù)。
  • 第二組負(fù)責(zé)存儲落在 A-B 區(qū)間內(nèi)的數(shù)據(jù)。
  • 第三組負(fù)責(zé)存儲落在 B-C 區(qū)間內(nèi)的數(shù)據(jù)。

士兵分配

假定編號為 9527 的士兵,進(jìn)行哈希運算后,落到 C-A 區(qū)域。如下圖所示:

士兵所站位置

 

第二步,讓這個士兵順時針往前走,遇到的第一個節(jié)點 A 就是他所在的組了。如下圖所示:

順時針遇到第一個節(jié)點

 

增加分組

目前三個節(jié)點的時候,假定編號為 89757 的士兵經(jīng)過哈希運算后,分配到了 B-C 區(qū)域(第三組),也就是屬于 C 節(jié)點管控。如下圖所示:

屬于 C 節(jié)點

 

回到劉邦剛問的問題,如果分組變成四組,該怎么進(jìn)行士兵分配。

如下圖所示,增加一個節(jié)點 D,原來的區(qū)域 B-C 變成了區(qū)域 B-D(第三組) 和 D-C(第四組)。

 

 


增加 D 節(jié)點

 

 

那么這名士兵屬于哪個節(jié)點管控呢?如下圖所示,士兵順時針往前走,先走到了 D 節(jié)點,所以屬于 D 節(jié)點管控。雖然還是屬于第三組,但是這名士兵的領(lǐng)導(dǎo)者已經(jīng)變了:由 C 變成了 D。

 

 


領(lǐng)導(dǎo)者變了

 

 

從上面的變化來看,只有 B-C 區(qū)域中的部分?jǐn)?shù)據(jù)會進(jìn)行遷移:B-D 之間的數(shù)據(jù)會由 C 節(jié)點遷移到 D 節(jié)點。

而其他數(shù)據(jù)不受影響,也不用進(jìn)行遷移。而且節(jié)點越多,需要遷移的數(shù)據(jù)就越少。這就是多多益善了~

劉邦看了后,大贊韓信:

不虧是大將軍,蕭何當(dāng)時月下追你,值了!

哈希環(huán)缺陷

蕭何看了韓信畫的哈希環(huán)后,覺得有些不對勁,思索片刻后,對韓信說:

將軍,你這個哈希環(huán)上的節(jié)點分布不太均勻啊,你看第三組和第四組的的區(qū)域好小啊。

蕭何說得沒錯,確實存在這個問題,放到互聯(lián)網(wǎng)架構(gòu)中,就存在如下問題:

節(jié)點分布不均勻,導(dǎo)致業(yè)務(wù)對節(jié)點的訪問冷熱不均。

韓信眼中充滿著贊賞,知我者莫若蕭何。然后胸有成竹地說道:

你說得沒錯,不過我還有一個技能,虛擬節(jié)點映射。

三技能:虛擬節(jié)點

一般虛擬節(jié)點比物理節(jié)點要多,并相對均勻地分布在哈希環(huán)上。如下圖所示,12 個虛擬節(jié)點 N1~N12,相對均勻地分布在虛擬節(jié)點上。如果有士兵屬于 N2/N3/N4 中的某一個,都會重新映射到 A 節(jié)點,依次類推,N5/N6/N7 屬于 B 節(jié)點的虛擬節(jié)點映射。

 

 


虛擬節(jié)點

 

 

我們來看下蕭何的提出的問題,真實的 B-D 區(qū)域比較小,用虛擬節(jié)點后,N5/N6/N7 屬于 B 節(jié)點,N8/N9/N10 屬于 D 節(jié)點,他們分到的虛擬節(jié)點一樣多,而且區(qū)域大致相等。所以士兵的分配也比較均勻。

蕭何看了韓信的三技能后,直呼:妙哉妙哉!

總結(jié)

本篇通過韓信點兵的故事,然后從故事中衍生出劉邦、韓信、蕭何的對話,來講解士兵的分組的問題?,F(xiàn)在對故事中的知識點做一個總結(jié):

  • 哈希算法會帶來增加或刪除節(jié)點時,數(shù)據(jù)遷移量太大的問題。
  • 一致性哈希算法降低了數(shù)據(jù)遷移量。
  • 節(jié)點較少,哈希環(huán)上每個節(jié)點實際占據(jù)的區(qū)間大小不一,最終導(dǎo)致業(yè)務(wù)對節(jié)點的訪問冷熱不均。
  • 引入虛擬節(jié)點映射解決了分布不均問題。
  • 節(jié)點越多時,使用哈希算法時,需要遷移的數(shù)據(jù)就越多,而使用一致性哈希算法,遷移的數(shù)據(jù)就越少。
  • 一致性哈希算法本質(zhì)上是一種路由尋址算法,適合簡單的路由尋址場景。
  • 一致性哈希算法常用在負(fù)載均衡的架構(gòu)設(shè)計中。

本文轉(zhuǎn)載自微信公眾號「 悟空聊架構(gòu)」,可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 悟空聊架構(gòu)公眾號。

 

責(zé)任編輯:武曉燕 來源: 悟空聊架構(gòu)
相關(guān)推薦

2021-02-05 08:00:48

哈希算法?機器

2020-07-20 08:30:37

算法哈希分布式系統(tǒng)

2021-09-15 07:46:42

哈希一致性哈希算法

2021-07-27 08:57:10

算法一致性哈希哈希算法

2016-12-19 18:41:09

哈希算法Java數(shù)據(jù)

2023-06-25 09:44:00

一致性哈希數(shù)據(jù)庫

2023-06-26 07:17:48

負(fù)載均衡策略Dubbo

2023-12-20 08:11:02

Redis節(jié)點通信

2017-07-25 14:38:56

數(shù)據(jù)庫一致性非鎖定讀一致性鎖定讀

2019-11-01 09:13:37

算法哈希緩存

2021-11-12 08:38:26

一致性哈希算法數(shù)據(jù)結(jié)構(gòu)

2018-07-05 09:41:08

一致性哈希算法

2023-12-12 08:00:50

節(jié)點哈希算法

2023-12-05 14:44:01

2022-01-27 08:31:20

一致性哈希

2022-12-14 08:23:30

2023-12-09 14:30:29

哈希數(shù)據(jù)分片

2020-11-24 09:03:41

一致性MySQLMVCC

2020-05-12 10:43:22

Redis緩存數(shù)據(jù)庫

2021-06-30 21:13:49

CPUCache數(shù)據(jù)
點贊
收藏

51CTO技術(shù)棧公眾號