一致性哈希的基本概念及其 Golang 實現

在大規模分佈式系統的世界中，高效地管理和分配數據是一個關鍵挑戰。一種廣泛使用的技術是一致性哈希。這種方法確保數據在多個服務器之間均勻分佈，即使服務器的數量隨時間變化也是如此。本文將探討水平擴展、簡單哈希和一致性哈希的概念，並提供一個 Go 語言的示例實現。

水平擴展

在分佈式系統中，數據通常無法容納在單個服務器上。爲了處理大規模數據，數據被分佈在多臺機器上，這個過程稱爲水平擴展或分片。

爲了確保可預測的性能，將數據均勻分佈在服務器之間是至關重要的。一個常見的方法是簡單哈希。

Simple Hashing

簡單哈希涉及使用哈希函數將對象鍵映射到已知的數值範圍。然後使用取模運算將這些數值分佈到固定數量的服務器上。

serverIndex = hash(key) % N

其中，N 是服務器池的大小。

這種方法在服務器數量固定時效果很好。然而，當服務器數量發生變化時，取模運算會導致不同的分佈，導致大多數鍵被重新分配到不同的服務器上。這會導致大量的數據遷移，並可能擾亂系統。

一致性哈希

一致性哈希旨在最小化服務器數量變化時鍵的重新分配。除了對對象鍵進行哈希處理，一致性哈希還對服務器名稱進行哈希處理。

哈希空間和哈希環

哈希空間是存儲對象鍵和服務器名稱的數值範圍。這個空間可以被可視化爲一個環。

服務器和對象鍵被哈希到環上的某個點。要找到某個對象對應的服務器，你從對象在環上的位置順時針移動，直到找到一個服務器爲止。

添加和移除服務器

當添加新服務器時，只需要重新分配一小部分鍵。同樣，當移除服務器時也是如此。

使用虛擬節點平衡

爲了解決分區大小和鍵分佈可能出現的不平衡問題，使用了虛擬節點（或副本）。每個服務器在環上由多個點表示，從而改善了鍵的分佈。

一致性哈希的應用

一致性哈希廣泛應用於數據庫分區，以最小化重新平衡期間的數據移動，在內容分發網絡（CDN）中用於在邊緣服務器之間均勻分發內容，並在負載均衡器中用於在後端服務器之間均勻分發持久連接。

Example Implementation in Go

import (
    "crypto/sha1"
    "fmt"
    "sort"
    "strconv"
)
// HashRing represents the consistent hash ring
type HashRing struct {
    nodes       []int
    nodeMap     map[int]string
    virtualNode int
}
// NewHashRing creates a new HashRing
func NewHashRing(virtualNode int) *HashRing {
    return &HashRing{
        nodeMap:     make(map[int]string),
        virtualNode: virtualNode,
    }
}
// AddNode adds a node to the hash ring
func (h *HashRing) AddNode(node string) {
    for i := 0; i < h.virtualNode; i++ {
        virtualNodeKey := node + "#" + strconv.Itoa(i)
        hash := int(sha1Hash(virtualNodeKey))
        h.nodes = append(h.nodes, hash)
        h.nodeMap[hash] = node
    }
    sort.Ints(h.nodes)
}
// RemoveNode removes a node from the hash ring
func (h *HashRing) RemoveNode(node string) {
    for i := 0; i < h.virtualNode; i++ {
        virtualNodeKey := node + "#" + strconv.Itoa(i)
        hash := int(sha1Hash(virtualNodeKey))
        index := sort.SearchInts(h.nodes, hash)
        h.nodes = append(h.nodes[:index], h.nodes[index+1:]...)
        delete(h.nodeMap, hash)
    }
}
// GetNode returns the closest node in the hash ring for the given key
func (h *HashRing) GetNode(key string) string {
    hash := int(sha1Hash(key))
    index := sort.SearchInts(h.nodes, hash)
    if index >= len(h.nodes) {
        index = 0
    }
    return h.nodeMap[h.nodes[index]]
}
// sha1Hash returns a sha1 hash of a string
func sha1Hash(key string) uint32 {
    h := sha1.New()
    h.Write([]byte(key))
    bs := h.Sum(nil)
    return uint32((int(bs[0]) << 24) + (int(bs[1]) << 16) + (int(bs[2]) << 8) + int(bs[3]))
}
func main() {
    ring := NewHashRing(3)
    ring.AddNode("ServerA")
    ring.AddNode("ServerB")
    ring.AddNode("ServerC")
    keys := []string{"Key1", "Key2", "Key3", "Key4"}
    for _, key := range keys {
        fmt.Printf("Key %s is assigned to %s\n", key, ring.GetNode(key))
    }
    ring.RemoveNode("ServerB")
    fmt.Println("After removing ServerB")
    for _, key := range keys {
        fmt.Printf("Key %s is assigned to %s\n", key, ring.GetNode(key))
    }
}

在這個例子中，我們創建了一個帶有虛擬節點的一致性哈希環，添加了服務器並分配了鍵。當一個服務器被移除時，只需要重新分配一小部分的鍵，展示了一致性哈希的高效性。

Conclusion

一致性哈希是在分佈式系統中實現數據均勻分佈的強大技術。它最小化了數據的移動，確保了高效的擴展性，使其成爲構建大規模、高性能系統的重要工具。通過理解和實現一致性哈希，您可以實現更好的負載分配和系統彈性。

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

猜你喜歡