前言
當在需要将資料分發到多個資料庫/緩存,或将請求分發給多個服務節點時,不可避免的會遇到以下問題:
如何将資料均勻的分散到各個節點中,并且盡量的在加減節點時能使受影響的資料最少。
選擇節點的方法
随機放置
從多個節點中,随機挑選一個,實作簡單但不能做到資料均勻分布到每個節點
Hash
将資料的key按
index = hash(key) % N
選擇節點。N代表有N個節點。此方法能将資料均勻的分發給每個節點,但在添加或修改節點時,即N發生變換時,所有資料都需要重新計算,擴充性差
一緻性Hash
一緻性Hash算法通過一個叫一緻性Hash環的資料結構實作KEY到節點的映射。
将節點的唯一辨別(ip, hostname)計算節點的hash值,并根據hash值将節點放置到放置到Hash環上。
随後用同樣的hash函數計算key(資料)的hash值,将資料放置到Hash環,順時針找到離資料最近的節點,此節點即為資料的接受節點。如圖:key1所屬節點為Node2
容錯性
假設Node1當機,key3的所屬節點變為Node2,其他資料無需修改。當節點足夠多時,某個節點當機隻會影響小部分的資料,保證了較好的容錯性
擴充性
當加入新的節點Node4時,key3的所屬節點變為Node4,其他資料無需修改。同樣保證了隻修改小部分資料,有較好的擴充性
虛拟節點
上述描述的算法仍然存在問題,當節點較少時會出現資料分布不均勻的情況:
多數key都在Node1,隻有少部分在Node2
計算機領域有句話:計算機的任何問題都可以通過增加一個虛拟層來解決
解決上述一緻性Hash算法帶來的負載不均衡問題,可以通過虛拟層的手段:
将每個真實節點虛拟為一組虛拟節點,将虛拟節點放入Hash環,key在換上先找到虛拟節點,再得到真實節點資訊。
如圖,将每個節點虛拟為兩個虛拟節點:
- Node1: VNode10,VNode11
- Node2: VNode20,VNode21
在原有的基礎上多一步由虛拟節點映射到實際節點的步驟即可讓少量節點也能滿足均勻性。