1.一致性哈希是什么
一致性哈希算法就很好地解決了分布式系統(tǒng)在擴(kuò)容或者縮容時(shí)，發(fā)生過多的數(shù)據(jù)遷移的問題。
一致哈希算法也用了取模運(yùn)算，但與哈希算法不同的是，哈希算法是對(duì)節(jié)點(diǎn)的數(shù)量進(jìn)行取模運(yùn)算，而一致哈希算法是對(duì) 2^32 進(jìn)行取模運(yùn)算，是一個(gè)固定的值。
一致性哈希要進(jìn)行兩步哈希：
第一步：對(duì)存儲(chǔ)節(jié)點(diǎn)進(jìn)行哈希計(jì)算，也就是對(duì)存儲(chǔ)節(jié)點(diǎn)做哈希映射，比如根據(jù)節(jié)點(diǎn)的 IP 地址進(jìn)行哈希；
第二步：當(dāng)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)或訪問時(shí)，對(duì)數(shù)據(jù)進(jìn)行哈希映射；
一致性哈希是指將【存儲(chǔ)節(jié)點(diǎn)】和【數(shù)據(jù)】都映射到一個(gè)首尾相連的哈希環(huán)上。
- 首先，對(duì)key進(jìn)行哈希計(jì)算，確定此key在換上的位置
- 然后，從這個(gè)位置沿著順時(shí)針方向走，遇到的第一節(jié)點(diǎn)就上存儲(chǔ)key的節(jié)點(diǎn)
2. 使用的場(chǎng)景是什么
在負(fù)載均衡問題中，不同的負(fù)載均衡算法，對(duì)應(yīng)的就是不同的分配策略，適應(yīng)的業(yè)務(wù)場(chǎng)景也不同。
- 最簡(jiǎn)單的方式，引入一個(gè)中間的負(fù)載均衡層，讓它將外界的請(qǐng)求「輪流」的轉(zhuǎn)發(fā)給內(nèi)部的集群。
- 考慮到每個(gè)節(jié)點(diǎn)的硬件配置有所區(qū)別，我們可以引入權(quán)重值，將硬件配置更好的節(jié)點(diǎn)的權(quán)重值設(shè)高，然后根據(jù)各個(gè)節(jié)點(diǎn)的權(quán)重值，按照一定比重分配在不同的節(jié)點(diǎn)上，讓硬件配置更好的節(jié)點(diǎn)承擔(dān)更多的請(qǐng)求，這種算法叫做加權(quán)輪詢。
但是，加權(quán)輪詢算法是無法應(yīng)對(duì)「分布式系統(tǒng)（數(shù)據(jù)分片的系統(tǒng)）」的，因?yàn)榉植际较到y(tǒng)中，每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)是不同的。
比如一個(gè)分布式 KV（key-valu） 緩存系統(tǒng)，某個(gè) key 應(yīng)該到哪個(gè)或者哪些節(jié)點(diǎn)上獲得，應(yīng)該是確定的，不是說任意訪問一個(gè)節(jié)點(diǎn)都可以得到緩存結(jié)果的。
3. 使用哈希算法的問題
哈希算法能夠?qū)ν粋€(gè)關(guān)鍵字進(jìn)行哈希計(jì)算，每次計(jì)算都是相同的值，這樣就可以將某個(gè)key確定到一個(gè)節(jié)點(diǎn)了，可以滿足分布式系統(tǒng)的負(fù)載均衡需求。
存在的致命問題：如果節(jié)點(diǎn)數(shù)量發(fā)生了變化，也就是在對(duì)系統(tǒng)做擴(kuò)容或者縮容時(shí)，必須遷移改變了映射關(guān)系的數(shù)據(jù)，否則會(huì)出現(xiàn)查詢不到數(shù)據(jù)的問題。
要解決這個(gè)問題的辦法，就需要我們進(jìn)行遷移數(shù)據(jù)，比如節(jié)點(diǎn)的數(shù)量從 3 變化為 4 時(shí)，要基于新的計(jì)算公式 hash(key) % 4 ，重新對(duì)數(shù)據(jù)和節(jié)點(diǎn)做映射。
假設(shè)總數(shù)據(jù)條數(shù)為 M，哈希算法在面對(duì)節(jié)點(diǎn)數(shù)量變化時(shí)，最壞情況下所有數(shù)據(jù)都需要遷移，所以它的數(shù)據(jù)遷移規(guī)模是 O(M)，這樣數(shù)據(jù)的遷移成本太高了。
4.一致性哈希算法進(jìn)階
4.1 一致性哈希算法存在的問題
一致性哈希算法并不保證節(jié)點(diǎn)能夠在哈希環(huán)上分布均勻，這樣就會(huì)帶來一個(gè)問題，會(huì)有大量的請(qǐng)求集中在一個(gè)節(jié)點(diǎn)上。
上圖中如果節(jié)點(diǎn) A 被移除了，當(dāng)節(jié)點(diǎn) A 宕機(jī)后，根據(jù)一致性哈希算法的規(guī)則，其上數(shù)據(jù)應(yīng)該全部遷移到相鄰的節(jié)點(diǎn) B 上，這樣，節(jié)點(diǎn) B 的數(shù)據(jù)量、訪問量都會(huì)迅速增加很多倍，一旦新增的壓力超過了節(jié)點(diǎn) B 的處理能力上限，就會(huì)導(dǎo)致節(jié)點(diǎn) B 崩潰，進(jìn)而形成雪崩式的連鎖反應(yīng)。
所以，一致性哈希算法雖然減少了數(shù)據(jù)遷移量，但是存在節(jié)點(diǎn)分布不均勻的問題。
4.2 通過虛擬節(jié)點(diǎn)提高均衡度
要想解決節(jié)點(diǎn)能在哈希環(huán)上分配不均勻的問題，就是要有大量的節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)越多，哈希環(huán)上的節(jié)點(diǎn)分布的就越均勻。
但問題是，實(shí)際中我們沒有那么多節(jié)點(diǎn)。所以這個(gè)時(shí)候我們就加入虛擬節(jié)點(diǎn)，也就是對(duì)一個(gè)真實(shí)節(jié)點(diǎn)做多個(gè)副本。
具體做法是，不再將真實(shí)節(jié)點(diǎn)映射到哈希環(huán)上，而是將虛擬節(jié)點(diǎn)映射到哈希環(huán)上，并將虛擬節(jié)點(diǎn)映射到實(shí)際節(jié)點(diǎn)，所以這里有「兩層」映射關(guān)系。
比如對(duì)每個(gè)節(jié)點(diǎn)分別設(shè)置 3 個(gè)虛擬節(jié)點(diǎn)：
對(duì)節(jié)點(diǎn) A 加上編號(hào)來作為虛擬節(jié)點(diǎn)：A-01、A-02、A-03
對(duì)節(jié)點(diǎn) B 加上編號(hào)來作為虛擬節(jié)點(diǎn)：B-01、B-02、B-03
對(duì)節(jié)點(diǎn) C 加上編號(hào)來作為虛擬節(jié)點(diǎn)：C-01、C-02、C-03
引入虛擬節(jié)點(diǎn)后，原本哈希環(huán)上只有 3 個(gè)節(jié)點(diǎn)的情況，就會(huì)變成有 9 個(gè)虛擬節(jié)點(diǎn)映射到哈希環(huán)上，哈希環(huán)上的節(jié)點(diǎn)數(shù)量多了 3 倍。
節(jié)點(diǎn)數(shù)量多了后，節(jié)點(diǎn)在哈希環(huán)上的分布就相對(duì)均勻了。這時(shí)候，如果有訪問請(qǐng)求尋址到「A-01」這個(gè)虛擬節(jié)點(diǎn)，接著再通過「A-01」虛擬節(jié)點(diǎn)找到真實(shí)節(jié)點(diǎn) A，這樣請(qǐng)求就能訪問到真實(shí)節(jié)點(diǎn) A 了。
總結(jié)：
- 一個(gè)真實(shí)節(jié)點(diǎn)對(duì)應(yīng)N個(gè)虛擬節(jié)點(diǎn)
- 一個(gè)虛擬節(jié)點(diǎn)對(duì)應(yīng)N個(gè)key
5. 代碼實(shí)現(xiàn)
下面是用go實(shí)現(xiàn)的代碼：
import (
"hash/crc32"
"sort"
"strconv"
)
// Hash map bytes to uint32
type Hash func(data []byte) uint32
// 包含所有的hashed keys
type Map struct {
hash Hash //Hash 函數(shù)
replicas int //虛擬節(jié)點(diǎn)倍數(shù)
keys []int //虛擬節(jié)點(diǎn)的哈希環(huán)
hashMap map[int]string //虛擬節(jié)點(diǎn)與真實(shí)節(jié)點(diǎn)的映射表,鍵是虛擬節(jié)點(diǎn)的哈希值，值是真實(shí)節(jié)點(diǎn)的名稱。
}
// New create a Map instance
func New(replicas int, fn Hash) *Map {
m := &Map{
replicas: replicas,
hash: fn,
hashMap: make(map[int]string),
}
if m.hash == nil {
m.hash = crc32.ChecksumIEEE
}
return m
}
func (m *Map) Add(keys ...string) {
for _, key := range keys {
for i := 0; i < m.replicas; i++ {
// 虛擬節(jié)點(diǎn)在哈希環(huán)上的hash值
hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
m.keys = append(m.keys, hash)
// 虛擬節(jié)點(diǎn)和真實(shí)節(jié)點(diǎn)的映射
m.hashMap[hash] = key
}
}
sort.Ints(m.keys)
}
func (m *Map) Get(key string) string {
if len(m.keys) == 0 {
return ""
}
// 要查詢的key的hash
hash := int(m.hash([]byte(key)))
// 找到最近的虛擬節(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)idx
idx := sort.Search(len(m.keys), func(i int) bool {
return m.keys[i] >= hash
})
//順時(shí)針找到第一個(gè)匹配的虛擬節(jié)點(diǎn)的下標(biāo) idx，從 m.keys 中獲取到對(duì)應(yīng)的哈希值。如果 idx == len(m.keys)，說明應(yīng)選擇 m.keys[0]，因?yàn)?m.keys 是一個(gè)環(huán)狀結(jié)構(gòu)，所以用取余數(shù)的方式來處理這種情況。
//m.keys[idx%len(m.keys)]獲得虛擬節(jié)點(diǎn)的hash
//根據(jù)虛擬節(jié)點(diǎn)的hash值獲取真實(shí)節(jié)點(diǎn)
return m.hashMap[m.keys[idx%len(m.keys)]]
}
6.總結(jié)
一致性哈希是指將「存儲(chǔ)節(jié)點(diǎn)」和「數(shù)據(jù)」都映射到一個(gè)首尾相連的哈希環(huán)上，如果增加或者移除一個(gè)節(jié)點(diǎn)，僅影響該節(jié)點(diǎn)在哈希環(huán)上順時(shí)針相鄰的后繼節(jié)點(diǎn)，其它數(shù)據(jù)也不會(huì)受到影響。
但是一致性哈希算法不能夠均勻的分布節(jié)點(diǎn)，會(huì)出現(xiàn)大量請(qǐng)求都集中在一個(gè)節(jié)點(diǎn)的情況，在這種情況下進(jìn)行容災(zāi)與擴(kuò)容時(shí)，容易出現(xiàn)雪崩的連鎖反應(yīng)。
為了解決一致性哈希算法不能夠均勻的分布節(jié)點(diǎn)的問題，就需要引入虛擬節(jié)點(diǎn)，對(duì)一個(gè)真實(shí)節(jié)點(diǎn)做多個(gè)副本。不再將真實(shí)節(jié)點(diǎn)映射到哈希環(huán)上，而是將虛擬節(jié)點(diǎn)映射到哈希環(huán)上，并將虛擬節(jié)點(diǎn)映射到實(shí)際節(jié)點(diǎn)，所以這里有「兩層」映射關(guān)系。文章來源：http://www.zghlxwxcb.cn/news/detail-847043.html
引入虛擬節(jié)點(diǎn)后，可以會(huì)提高節(jié)點(diǎn)的均衡度，還會(huì)提高系統(tǒng)的穩(wěn)定性。所以，帶虛擬節(jié)點(diǎn)的一致性哈希方法不僅適合硬件配置不同的節(jié)點(diǎn)的場(chǎng)景，而且適合節(jié)點(diǎn)規(guī)模會(huì)發(fā)生變化的場(chǎng)景。文章來源地址http://www.zghlxwxcb.cn/news/detail-847043.html
到了這里，關(guān)于【負(fù)載均衡——一致性哈希算法】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
