哈希算法常用的有哪些（一文講透一致性哈希的原理和實現）

2023-10-18 18:22:03 4

首先介紹一下什麼是哈希

Hash，一般翻譯做散列，或音譯為哈希，是把任意長度的輸入（又叫做預映射pre-image）通過散列算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

在分布式緩存服務中，經常需要對服務進行節點添加和刪除操作，我們希望的是節點添加和刪除操作儘量減少數據-節點之間的映射關係更新。

假如我們使用的是哈希取模( hash(key)%nodes ) 算法作為路由策略:

哈希取模的缺點在於如果有節點的刪除和添加操作，對 hash(key)%nodes 結果影響範圍太大了，造成大量的請求無法命中從而導致緩存數據被重新加載。

基於上面的缺點提出了一種新的算法：一致性哈希。一致性哈希可以實現節點刪除和添加只會影響一小部分數據的映射關係，由於這個特性哈希算法也常常用於各種均衡器中實現系統流量的平滑遷移。

首先對節點進行哈希計算，哈希值通常在 2^32-1 範圍內。然後將 2^32-1 這個區間首尾連接抽象成一個環並將節點的哈希值映射到環上，當我們要查詢 key 的目標節點時，同樣的我們對 key 進行哈希計算，然後順時針查找到的第一個節點就是目標節點。

根據原理我們分析一下節點添加和刪除對數據範圍的影響。

這樣就完了嗎？還沒有，試想一下假如環上的節點數量非常少，那麼非常有可能造成數據分布不平衡，本質上是環上的區間分布粒度太粗。

怎麼解決呢？不是粒度太粗嗎？那就加入更多的節點，這就引出了一致性哈希的虛擬節點概念，虛擬節點的作用在於讓環上的節點區間分布粒度變細。

一個真實節點對應多個虛擬節點，將虛擬節點的哈希值映射到環上，查詢 key 的目標節點我們先查詢虛擬節點再找到真實節點即可。

基於上面的一致性哈希原理，我們可以提煉出一致性哈希的核心功能：

我們來定義一下接口：

ConsistentHash interface { Add(node Node) Get(key Node) Node Remove(node Node)}

現實中不同的節點服務能力因硬體差異可能各不相同，於是我們希望在添加節點時可以指定權重。反應到一致性哈希當中所謂的權重意思就是我們希望 key 的目標節點命中概率比例，一個真實節點的虛擬節點數量多則意味著被命中概率高。

在接口定義中我們可以增加兩個方法：支持指定虛擬節點數量添加節點，支持按權重添加。本質上最終都會反應到虛擬節點的數量不同導致概率分布差異。

指定權重時：實際虛擬節點數量 = 配置的虛擬節點 * weight/100

ConsistentHash interface { Add(node Node) AddWithReplicas(node Node, replicas int) AddWithWeight(node Node, weight int) Get(key Node) Node Remove(node Node)}

接下來考慮幾個工程實現的問題：

core/hash/consistenthash.go

詳細注釋可查看：https://github.com/Ouyangan/go-zero-annotation/blob/84ae351e4ebce558e082d54f4605acf750f5d285/core/hash/consistenthash.go

花了一天時間把 go-zero 源碼一致性哈希源碼看完，寫的真好啊，各種細節都考慮到了。

go-zero 使用的哈希函數是 MurmurHash3，GitHub：https://github.com/spaolacci/murmur3

go-zero 並沒有進行接口定義，沒啥關係，直接看結構體 ConsistentHash：

// Func defines the hash method.// 哈希函數Func func(data []byte) uint64// A ConsistentHash is a ring hash implementation.// 一致性哈希ConsistentHash struct { // 哈希函數 hashFunc Func // 確定node的虛擬節點數量 replicas int // 虛擬節點列表 keys []uint64 // 虛擬節點到物理節點的映射 ring map[uint64][]interface{} // 物理節點映射，快速判斷是否存在node nodes map[string]lang.PlaceholderType // 讀寫鎖 lock sync.RWMutex}

在進行哈希前要先將 key 轉換成 string

// 可以理解為確定node字符串值的序列化方法// 在遇到哈希衝突時需要重新對key進行哈希計算// 為了減少衝突的概率前面追加了一個質數prime來減小衝突的概率func innerRepr(v interface{}) string { return fmt.Sprintf("%d:%v", prime, v)}// 可以理解為確定node字符串值的序列化方法// 如果讓node強制實現String會不會更好一些？func repr(node interface{}) string { return mapping.Repr(node)}

這裡 mapping.Repr 裡會判斷 fmt.Stringer 接口，如果符合，就會調用其 String 方法。go-zero 代碼如下：

// Repr returns the string representation of v.func Repr(v interface{}) string { if v == nil { return "" } // if func (v *Type) String string, we can't use Elem switch vt := v.(type) { case fmt.Stringer: return vt.String } val := reflect.ValueOf(v) if val.Kind == reflect.Ptr && !val.IsNil { val = val.Elem } return reprOfValue(val)}

最終調用的是 指定虛擬節點添加節點方法

// 擴容操作，增加物理節點func (h *ConsistentHash) Add(node interface{}) { h.AddWithReplicas(node, h.replicas)}

最終調用的同樣是 指定虛擬節點添加節點方法

// 按權重添加節點// 通過權重來計算方法因子，最終控制虛擬節點的數量// 權重越高，虛擬節點數量越多func (h *ConsistentHash) AddWithWeight(node interface{}, weight int) { replicas := h.replicas * weight / TopWeight h.AddWithReplicas(node, replicas)}

// 擴容操作，增加物理節點func (h *ConsistentHash) AddWithReplicas(node interface{}, replicas int) { // 支持可重複添加 // 先執行刪除操作 h.Remove(node) // 不能超過放大因子上限 if replicas > h.replicas { replicas = h.replicas } // node key nodeRepr := repr(node) h.lock.Lock defer h.lock.Unlock // 添加node map映射 h.addNode(nodeRepr) for i := 0; i < replicas; i { // 創建虛擬節點 hash := h.hashFunc([]byte(nodeRepr strconv.Itoa(i))) // 添加虛擬節點 h.keys = append(h.keys, hash) // 映射虛擬節點-真實節點 // 注意hashFunc可能會出現哈希衝突，所以採用的是追加操作 // 虛擬節點-真實節點的映射對應的其實是個數組 // 一個虛擬節點可能對應多個真實節點，當然概率非常小 h.ring[hash] = append(h.ring[hash], node) } // 排序 // 後面會使用二分查找虛擬節點 sort.Slice(h.keys, func(i, j int) bool { return h.keys[i] < h.keys[j] })}

// 刪除物理節點func (h *ConsistentHash) Remove(node interface{}) { // 節點的string nodeRepr := repr(node) // 並發安全 h.lock.Lock defer h.lock.Unlock // 節點不存在 if !h.containsNode(nodeRepr) { return } // 移除虛擬節點映射 for i := 0; i = hash }) // 切片刪除對應的元素 if index < len(h.keys) && h.keys[index] == hash { // 定位到切片index之前的元素 // 將index之後的元素（index 1）前移覆蓋index h.keys = append(h.keys[:index], h.keys[index 1:]...) } // 虛擬節點刪除映射 h.removeRingNode(hash, nodeRepr) } // 刪除真實節點 h.removeNode(nodeRepr)}// 刪除虛擬-真實節點映射關係// hash - 虛擬節點// nodeRepr - 真實節點func (h *ConsistentHash) removeRingNode(hash uint64, nodeRepr string) { // map使用時應該校驗一下 if nodes, ok := h.ring[hash]; ok { // 新建一個空的切片,容量與nodes保持一致 newNodes := nodes[:0] // 遍歷nodes for _, x := range nodes { // 如果序列化值不相同，x是其他節點 // 不能刪除 if repr(x) != nodeRepr { newNodes = append(newNodes, x) } } // 剩餘節點不為空則重新綁定映射關係 if len(newNodes) > 0 { h.ring[hash] = newNodes } else { // 否則刪除即可 delete(h.ring, hash) } }}

// 根據v順時針找到最近的虛擬節點// 再通過虛擬節點映射找到真實節點func (h *ConsistentHash) Get(v interface{}) (interface{}, bool) { h.lock.RLock defer h.lock.RUnlock // 當前沒有物理節點 if len(h.ring) == 0 { return nil, false } // 計算哈希值 hash := h.hashFunc([]byte(repr(v))) // 二分查找 // 因為每次添加節點後虛擬節點都會重新排序 // 所以查詢到的第一個節點就是我們的目標節點 // 取餘則可以實現環形列表效果，順時針查找節點 index := sort.Search(len(h.keys), func(i int) bool { return h.keys[i] >= hash }) % len(h.keys) // 虛擬節點->物理節點映射 nodes := h.ring[h.keys[index]] switch len(nodes) { // 不存在真實節點 case 0: return nil, false // 只有一個真實節點，直接返回 case 1: return nodes[0], true // 存在多個真實節點意味這出現哈希衝突 default: // 此時我們對v重新進行哈希計算 // 對nodes長度取餘得到一個新的index innerIndex := h.hashFunc([]byte(innerRepr(v))) pos := int(innerIndex % uint64(len(nodes))) return nodes[pos], true }}

https://github.com/zeromicro/go-zero

歡迎使用 go-zero 並 star 支持我們！

關注『微服務實踐』公眾號並點擊 交流群 獲取社區群二維碼。