天天看點

對一緻性hash算法的了解

首先說明其用途,目前主要用在分布式緩存中。

為什麼使用一緻性hash:

假設有N個緩存伺服器,普通的緩存政策是hash(obj)%N,當其中一個伺服器挂掉,或者伺服器不夠而需要添加伺服器時,緩存政策需要改變成hash(onj)%(N-1)或(N+1),這也就意味着所有的緩存全部失效,那所有的通路都會到背景伺服器,是不是想到了鹿晗和關曉彤,恐怖!程式員結婚還得中途暫停,去修複伺服器。

是以就有了一緻性hash,那一緻性hash怎麼就解決了上述的問題了呢?我們希望的是,當删除或者添加伺服器節點時,盡量少的影響已經緩存的内容。如下圖所示,想象出一個環,通過相同的hash算法,将伺服器和緩存内容hash到環上的某一個位置,然後緩存内容隻需順時針找到離它最近的伺服器進行緩存即可。這就是一緻性hash。

對一緻性hash算法的了解

那這麼做有什麼優點呢?剛才說一緻性hash算法當删除或添加伺服器時能夠減少緩存失效的數量,還是如上圖,當圖中紅色緩存内容對應的伺服器挂掉後,隻有它自己緩存失效,其他對象均沒有影響。同理,增加伺服器也隻會影響到部分内容。

當然,這樣做存在一定問題,就是在極端情況下,如下圖所示,伺服器“紮堆了”,所有緩存或者說很大一部分内容都被緩存到了同一台伺服器上,這樣的一緻性hash跟普通hash還有什麼差別!

對一緻性hash算法的了解

然後就有了虛拟節點的概念,首先看下圖,其中每種顔色對應兩個伺服器(當然,也可以有多個),其實他們都是某個真實的伺服器虛拟出來的,我的了解是給某個伺服器起了多個名字,這樣它就能存在多個地方(當然不是真的存在,可以把虛拟節點想象成一個類似代理的東西,多個代理,最後緩存當然還是放在真實的伺服器上),這樣就比較均衡了。

對一緻性hash算法的了解

以上。個人了解,有錯誤和不當之處,還請多多批評。圍笑。

繼續閱讀