分佈式基石算法一致性 hash

什麼是一致性 hash 算法

首先摘抄一段維基百科的定義

一致哈希是一種特殊的哈希算法。在使用一致哈希算法後，哈希表槽位數（大小）的改變平均只需要對𝐾/𝑛 個關鍵字重新映射，其中 𝐾 是關鍵字的數量，𝑛是槽位數量。然而在傳統的哈希表中，添加或刪除一個槽位的幾乎需要對所有關鍵字進行重新映射。 --- wikipedia

分佈式系統中, 一致性 hash 無處不在，CDN，KV，負載均衡等地方都有它的影子，是分佈式系統的基石算法之一。一致性 hash 有以下幾個優點。

均衡負載：

一致性哈希算法能夠將數據在節點上均勻分佈。
擴展性：

在一致性哈希算法中，當節點數量增加或減少時，只有部分數據需要重新映射，系統能夠進行水平擴展更容易，可以增加節點數量以應對更大的負載需求；
減少數據遷移：

相比傳統的哈希算法，一致性哈希算法在節點增減時需要重新映射的數據量較少，可以大幅降低數據遷移的開銷，減少系統的不穩定性和延遲；
本篇文章的目標就是學習一致性 hash 算法以及它的簡單實現。

This article is first published in the medium MPP plan. If you are a medium user, please follow me in medium[1]. Thank you very much.

一致性 hash 算法的原理

基本一致性 hash 算法

最基礎的一致性 hash 算法就是把節點直接分佈到環上，從而劃分出值域， key 經過 hash( x ) 之後，落到不同的值域，則由對應的節點處理。最常見的值域空間大小是：2^32 - 1，節點落到這個空間，來劃分不同節點所屬的值域。如圖所示。

Node A 存儲的 hash 範圍爲 [0,2^12) .
Node B 存儲的 hash 範圍爲 [2^12,2^28) .
Node C 存儲的 hash 範圍爲 [2^28,0) .
上述基本的一致性哈希算法有明顯的缺點：

隨機分佈節點的方式使得很難均勻的分佈哈希值域，從上面可以看出，三個節點存儲的數據不均勻。
在動態增加節點後，原先的分佈就算均勻也很難再繼續保證均勻；
增刪節點帶來的一個較爲嚴重的缺點是：
當一個節點異常時，該節點的壓力全部轉移到相鄰的一個節點；
當一個新節點加入時只能爲一個相鄰節點分攤壓力；

虛擬節點

Go 語言之父 rob pike 曾經說過 計算機領域裏，沒有什麼問題是加一層間接尋址解決不了的. 一致性 hash 也是一樣。
如果三個節點存在不均衡的問題，那麼我們就把他虛擬成 N 個節點。A[a1,a2....a1024], 然後將他們映射到 hash_ring 上，就是這樣樣子的。

每個虛擬節點都有對應的 hash 區間。負責一段 key，然後根據虛擬 node 的名字找到對應的物理 node 讀寫數據。
引入虛擬節點後，就完美的解決了上面的三個問題。
4. 只要我們的虛擬節點足夠多，各個節點的數據就能平衡，（⚠️：這個在工程上是有代價的）
5. 如果一個節點宕機了，它的數據會均衡的分佈到整個集羣所有節點，同理，新增的節點也能負擔所有節點的壓力。

Go 語言實現

完整的代碼：https://github.com/hxzhouh/blog-example/tree/main/Distributed/consistent_hashing[2]
首先定義一個 hash_ring, 使用 crc32.ChecksumIEEE 作爲默認的 hash function

type VirtualNode struct {   // 虛擬節點
    Hash uint32
    Node *Node  
}
type Node struct {   // 物理節點
    ID   string
    Addr string
}
type HashRing struct {
    Nodes        map[string]*Node
    VirtualNodes []VirtualNode. 
    mu           sync.Mutex
    hash         HashFunc
}
funcNewHashRing(hash HashFunc) *HashRing {  
if hash == nil {  
       hash = crc32.ChecksumIEEE  
    }  
return &HashRing{  
       Nodes:        make(map[string]*Node),  
       VirtualNodes: make([]VirtualNode, 0),  
       hash:         hash,  
    }  
}

我們來看一下怎麼添加節點：

func (hr *HashRing) AddNode(node *Node) {  
    hr.mu.Lock()  
defer hr.mu.Unlock()  

    hr.Nodes[node.ID] = node  
for i := 0; i < VirtualNodesPerNode; i++ {  
       virtualNodeID := fmt.Sprintf("%s-%d", node.ID, i)  
       hash := hr.hash([]byte(virtualNodeID))  
       hr.VirtualNodes = append(hr.VirtualNodes, VirtualNode{Hash: hash, Node: node})  
    }  
    sort.Slice(hr.VirtualNodes, func(i, j int)bool {  
return hr.VirtualNodes[i].Hash < hr.VirtualNodes[j].Hash  
    })  
}

我們每添加一個節點，就要創建對應數量的虛擬節點，並且要保證虛擬節點有序（這樣才能查找）
同樣，remove 的時候，也需要刪除虛擬節點

func (hr *HashRing) RemoveNode(nodeID string) {  
    hr.mu.Lock()  
defer hr.mu.Unlock()  

delete(hr.Nodes, nodeID)  
    virtualNodes := make([]VirtualNode, 0)  
for _, vn := range hr.VirtualNodes {  
if vn.Node.ID != nodeID {  
          virtualNodes = append(virtualNodes, vn)  
       }  
    }  
    hr.VirtualNodes = virtualNodes  
}

查詢的時候，我們先找到對應的虛擬節點，然後再根據虛擬節點找到對應的物理節點

func (hr *HashRing) GetNode(key string) *Node {  
    hr.mu.Lock()  
defer hr.mu.Unlock()  

iflen(hr.VirtualNodes) == 0 {  
returnnil
    }  

    hash := hr.hash([]byte(key))  
    idx := sort.Search(len(hr.VirtualNodes), func(i int)bool {  
return hr.VirtualNodes[i].Hash >= hash  
    })  
if idx == len(hr.VirtualNodes) {  
       idx = 0
    }  

return hr.VirtualNodes[idx].Node  
}

最後我們來看看，業務如何使用這個 hash_ring

type KVSystem struct {  
    hashRing *HashRing  
    kvStores map[string]*kvstorage.KVStore  
}  

funcNewKVSystem(nodes int) *KVSystem {  
    hashRing := NewHashRing(crc32.ChecksumIEEE)  
for i := 0; i < nodes; i++ {  // init node
       node := &Node{  
          ID:   fmt.Sprintf("Node%d", i),  
          Addr: fmt.Sprintf("192.168.1.%d", i+1),  
       }  
       hashRing.AddNode(node)  
    }  
    kvStores := make(map[string]*kvstorage.KVStore)   //init storage
for id := range hashRing.Nodes {  
       kvStores[id] = kvstorage.NewKVStore()  
    }  
return &KVSystem{  
       hashRing: hashRing,  
       kvStores: kvStores,  
    }  
}  

func(kv *KVSystem) Get(key string) (string, bool) {   //get value
    node := kv.hashRing.GetNode(key)  
return kv.kvStores[node.ID].Get(key)  
}  

func(kv *KVSystem) Set(key string, value string) {  // set value 
    node := kv.hashRing.GetNode(key)  
    kv.kvStores[node.ID].Set(key, value)  
}  

func(kv *KVSystem) Delete(key string) {  
    node := kv.hashRing.GetNode(key)  
    kv.kvStores[node.ID].Delete(key)  
}  
// DeleteNode 需要將存儲在節點上的數據重新分配。
func(kv *KVSystem) DeleteNode(nodeID string) {   
    allData := kv.kvStores[nodeID].GetAll()  
    kv.hashRing.RemoveNode(nodeID)  
delete(kv.kvStores, nodeID)  
for key, value := range allData {  
       kv.Set(key, value)  
    }  
}  

func(kv *KVSystem) AddNode() {  
    node := &Node{  
       ID:   fmt.Sprintf("Node%d", len(kv.hashRing.Nodes)),  
       Addr: fmt.Sprintf("192.168.1.%d", len(kv.hashRing.Nodes)+1),  
    }  
    kv.hashRing.AddNode(node)  
    kv.kvStores[node.ID] = kvstorage.NewKVStore()  
}

這樣我們就實現了一個最簡單的基於一致性 hash 的 kv 存儲，是不是特別簡單? 但是它卻支撐了我們整個網絡世界的運轉。

參考資料

Consistent_hashing[3]

引用鏈接

[1]medium: https://medium.huizhou92.com/

[2]https://github.com/hxzhouh/blog-example/tree/main/Distributed/consistent_hashing

[3]Consistent_hashing: https://en.wikipedia.org/wiki/Consistent_hashing

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/k1mspucGVwgS7c6w8d2Hgw

什麼是 一致性 hash 算法