Go 項(xiàng)目實(shí)戰(zhàn)：實(shí)現(xiàn)一個 Redis(7) 之集群與一致性 Hash

本文是使用 golang 實(shí)現(xiàn) redis 系列的第七篇，將介紹如何將單點(diǎn)的緩存服務(wù)器擴(kuò)展為分布式緩存。godis 集群的源碼在 https://github.com/HDT3213/godis/tree/master/src/cluster

單臺服務(wù)器的CPU和內(nèi)存等資源總是有限的，隨著數(shù)據(jù)量和訪問量的增加單臺服務(wù)器很容易遇到瓶頸。利用多臺機(jī)器建立分布式系統(tǒng)，分工處理是提高系統(tǒng)容量和吞吐量的常用方法。

使用更多機(jī)器來提高系統(tǒng)容量的方式稱為系統(tǒng)橫向擴(kuò)容。與之相對的，提高單臺機(jī)器性能被稱為縱向擴(kuò)容。由于無法在單臺機(jī)器上無限提高硬件配置且硬件價(jià)格與性能的關(guān)系并非線性的，所以建立分布式系統(tǒng)進(jìn)行橫向擴(kuò)容是更為經(jīng)濟(jì)實(shí)用的選擇。

我們采用一致性 hash 算法 key 分散到不同的服務(wù)器，客戶端可以連接到服務(wù)集群中任意一個節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)需要訪問的數(shù)據(jù)不在自己本地時，需要通過一致性 hash 算法計(jì)算出數(shù)據(jù)所在的節(jié)點(diǎn)并將指令轉(zhuǎn)發(fā)給它。

與分布式系統(tǒng)理論中的分區(qū)容錯性不同，我們僅將數(shù)據(jù)存在一個節(jié)點(diǎn)沒有保存副本。這種設(shè)計(jì)提高了系統(tǒng)吞吐量和容量，但是并沒有提高系統(tǒng)可用性，當(dāng)有一個節(jié)點(diǎn)崩潰時它保存的數(shù)據(jù)將無法訪問。

生產(chǎn)環(huán)境實(shí)用的 redis 集群通常也采取類似的分片存儲策略，并為每個節(jié)點(diǎn)配置從節(jié)點(diǎn)作為熱備節(jié)點(diǎn)，并使用 sentinel 機(jī)制監(jiān)控 master 節(jié)點(diǎn)狀態(tài)。在 master 節(jié)點(diǎn)崩潰后，sentinel 將備份節(jié)點(diǎn)提升為 master 節(jié)點(diǎn)以保證可用性。

一致性 hash 算法

為什么需要一致性 hash

在采用分片方式建立分布式緩存時，我們面臨的第一個問題是如何決定存儲數(shù)據(jù)的節(jié)點(diǎn)。最自然的方式是參考 hash 表的做法，假設(shè)集群中存在 n 個節(jié)點(diǎn)，我們用 node = hashCode(key) % n 來決定所屬的節(jié)點(diǎn)。

普通 hash 算法解決了如何選擇節(jié)點(diǎn)的問題，但在分布式系統(tǒng)中經(jīng)常出現(xiàn)增加節(jié)點(diǎn)或某個節(jié)點(diǎn)宕機(jī)的情況。若節(jié)點(diǎn)數(shù) n 發(fā)生變化, 大多數(shù) key 根據(jù) node = hashCode(key) % n 計(jì)算出的節(jié)點(diǎn)都會改變。這意味著若要在 n 變化后維持系統(tǒng)正常運(yùn)轉(zhuǎn)，需要將大多數(shù)數(shù)據(jù)在節(jié)點(diǎn)間進(jìn)行重新分布。這個操作會消耗大量的時間和帶寬等資源，這在生產(chǎn)環(huán)境下是不可接受的。

算法原理

一致性 hash 算法的目的是在節(jié)點(diǎn)數(shù)量 n 變化時, 使盡可能少的 key 需要進(jìn)行節(jié)點(diǎn)間重新分布。一致性 hash 算法將數(shù)據(jù) key 和服務(wù)器地址 addr 散列到 2^32 的空間中。

我們將 2^32 個整數(shù)首尾相連形成一個環(huán)，首先計(jì)算服務(wù)器地址 addr 的 hash 值放置在環(huán)上。然后計(jì)算 key 的 hash 值放置在環(huán)上，順時針查找，將數(shù)據(jù)放在找到的的第一個節(jié)點(diǎn)上。

key1, key2 和 key5 在 node2 上，key 3 在 node4 上，key4 在 node6 上

在增加或刪除節(jié)點(diǎn)時只有該節(jié)點(diǎn)附近的數(shù)據(jù)需要重新分布，從而解決了上述問題。

新增 node8 后，key 5 從 node2 轉(zhuǎn)移到 node8。其它 key 不變

如果服務(wù)器節(jié)點(diǎn)較少則比較容易出現(xiàn)數(shù)據(jù)分布不均勻的問題，一般來說環(huán)上的節(jié)點(diǎn)越多數(shù)據(jù)分布越均勻。我們不需要真的增加一臺服務(wù)器，只需要將實(shí)際的服務(wù)器節(jié)點(diǎn)映射為幾個虛擬節(jié)點(diǎn)放在環(huán)上即可。

Golang 實(shí)現(xiàn)一致性 Hash

我們使用 Golang 實(shí)現(xiàn)一致性 hash 算法, 源碼在 https://github.com/HDT3213/godis/blob/master/src/lib/consistenthash/consistenthash.go，大約 80 行代碼。

type?HashFunc?func(data?[]byte)?uint32

type?Map?struct?{
????hashFunc?HashFunc
????replicas?int
????keys?????[]int?//?sorted
????hashMap??map[int]string
}

func?New(replicas?int,?fn?HashFunc)?*Map?{
????m?:=?&Map{
????????replicas:?replicas,?//?每個物理節(jié)點(diǎn)會產(chǎn)生?replicas?個虛擬節(jié)點(diǎn)
????????hashFunc:?fn,
????????hashMap:??make(map[int]string),?//?虛擬節(jié)點(diǎn)?hash?值到物理節(jié)點(diǎn)地址的映射
????}
????if?m.hashFunc?==?nil?{
????????m.hashFunc?=?crc32.ChecksumIEEE
????}
????return?m
}

func?(m?*Map)?IsEmpty()?bool?{
????return?len(m.keys)?==?0
}

接下來實(shí)現(xiàn)添加物理節(jié)點(diǎn)的 Add 方法:

func?(m?*Map)?Add(keys?...string)?{
????for?_,?key?:=?range?keys?{
????????if?key?==?""?{
????????????continue
????????}
????????for?i?:=?0;?i?????????????//?使用?i?+?key?作為一個虛擬節(jié)點(diǎn)，計(jì)算虛擬節(jié)點(diǎn)的?hash?值
????????????hash?:=?int(m.hashFunc([]byte(strconv.Itoa(i)?+?key)))?
????????????//?將虛擬節(jié)點(diǎn)添加到環(huán)上
????????????m.keys?=?append(m.keys,?hash)?
????????????//?注冊虛擬節(jié)點(diǎn)到物理節(jié)點(diǎn)的映射
????????????m.hashMap[hash]?=?key
????????}
????}
????sort.Ints(m.keys)
}

接下來實(shí)現(xiàn)查找算法:

func?(m?*Map)?Get(key?string)?string?{
????if?m.IsEmpty()?{
????????return?""
????}

????//?支持根據(jù)?key?的?hashtag?來確定分布?
????partitionKey?:=?getPartitionKey(key)
????hash?:=?int(m.hashFunc([]byte(partitionKey)))

????//?sort.Search?會使用二分查找法搜索?keys?中滿足?m.keys[i]?>=?hash?的最小?i?值
????idx?:=?sort.Search(len(m.keys),?func(i?int)?bool?{?return?m.keys[i]?>=?hash?})

????//?若?key?的?hash?值大于最后一個虛擬節(jié)點(diǎn)的?hash?值，則?sort.Search?找不到目標(biāo)
????//?這種情況下選擇第一個虛擬節(jié)點(diǎn)
????if?idx?==?len(m.keys)?{
????????idx?=?0
????}

????//?將虛擬節(jié)點(diǎn)映射為實(shí)際地址
????return?m.hashMap[m.keys[idx]]
}

實(shí)現(xiàn)集群

實(shí)現(xiàn)了一致性 hash 算法后我們可以著手實(shí)現(xiàn)集群模式了，Godis 集群的代碼在 Github:Godis/cluster。

集群最核心的邏輯是找到 key 所在節(jié)點(diǎn)并將指令轉(zhuǎn)發(fā)過去:

//?集群模式下，除了?MSet、DEL?等特殊指令外，其它指令會交由?defaultFunc?處理
func?defaultFunc(cluster?*Cluster,?c?redis.Connection,?args?[][]byte)?redis.Reply?{
????key?:=?string(args[1])
????peer?:=?cluster.peerPicker.Get(key)?//?通過一致性?hash?找到節(jié)點(diǎn)
????return?cluster.Relay(peer,?c,?args)
}

func?(cluster?*Cluster)?Relay(peer?string,?c?redis.Connection,?args?[][]byte)?redis.Reply?{
????if?peer?==?cluster.self?{?//?若數(shù)據(jù)在本地則直接調(diào)用數(shù)據(jù)庫引擎
????????//?to?self?db
????????return?cluster.db.Exec(c,?args)
????}?else?{
????????//?從連接池取一個與目標(biāo)節(jié)點(diǎn)的連接
????????//?連接池使用?github.com/jolestar/go-commons-pool/v2?實(shí)現(xiàn)
????????peerClient,?err?:=?cluster.getPeerClient(peer)?
????????if?err?!=?nil?{
????????????return?reply.MakeErrReply(err.Error())
????????}
????????defer?func()?{
????????????_?=?cluster.returnPeerClient(peer,?peerClient)?//?處理完成后將連接放回連接池
????????}()
????????//?將指令發(fā)送到目標(biāo)節(jié)點(diǎn)
????????return?peerClient.Send(args)?
????}
}

func?(cluster?*Cluster)?getPeerClient(peer?string)?(*client.Client,?error)?{
????connectionFactory,?ok?:=?cluster.peerConnection[peer]
????if?!ok?{
????????return?nil,?errors.New("connection?factory?not?found")
????}
????raw,?err?:=?connectionFactory.BorrowObject(context.Background())
????if?err?!=?nil?{
????????return?nil,?err
????}
????conn,?ok?:=?raw.(*client.Client)
????if?!ok?{
????????return?nil,?errors.New("connection?factory?make?wrong?type")
????}
????return?conn,?nil
}

func?(cluster?*Cluster)?returnPeerClient(peer?string,?peerClient?*client.Client)?error?{
????connectionFactory,?ok?:=?cluster.peerConnection[peer]
????if?!ok?{
????????return?errors.New("connection?factory?not?found")
????}
????return?connectionFactory.ReturnObject(context.Background(),?peerClient)
}

作者：finley

出處：https://www.cnblogs.com/Finley/p/14038398.html

版權(quán)：本作品采用「署名-非商業(yè)性使用-相同方式共享 4.0 國際」許可協(xié)議進(jìn)行許可。