概念

一致性哈希是指将数据分散到多个节点上进行存储的方法。在一致性哈希中，数据通常用数字编码，并使用哈希函数将它们映射到一个固定的哈希环上。在这种情况下，哈希环的大小通常是 2 的某个次方。选择 2 的 32 次方作为哈希环的大小是因为这是一个较大的数字，能够在哈希环上映射到许多不同的点，从而提高数据的分散性。此外，使用 32 位整数作为哈希值可以有效地使用现有的计算机硬件，并且它们通常在存储和传输方面是非常有效的。

不过，哈希环的大小不是固定的，也不一定必须为 2 的 32 次方。它可以是任何大小，只要满足某些特定的要求，例如能够平均分布数据，或者有足够的空间来存储数据等。

解决什么问题

分布式系统中扩容/缩容问题，减少数据迁移，或减少扩/缩容后对各节点的压力

已有车轮

Go 语言提供了一些库和工具，其中最受欢迎的是 hashring 和 consistent

重复造车轮

为加深对 一致性哈希 的理解，我们亲自实现个简单的

package main

import (
	"fmt"
	"hash/crc32"
	"sort"
	"strconv"
)

// HashRing 结构表示一致性哈希环
type HashRing struct {
	virtualNodes int              // 虚拟节点数
	nodes        []string         // 实际节点列表
	hashMap      map[uint32]string // 节点哈希映射
}

// NewHashRing 创建一个新的一致性哈希环
func NewHashRing(virtualNodes int, nodes []string) *HashRing {
	hashRing := &HashRing{
		virtualNodes: virtualNodes,
		nodes:        nodes,
		hashMap:      make(map[uint32]string),
	}

	hashRing.generateHashRing()

	return hashRing
}

// 生成哈希环
func (hr *HashRing) generateHashRing() {
	for _, node := range hr.nodes {
		for i := 0; i < hr.virtualNodes; i++ {
			virtualKey := hr.getVirtualKey(node, i)
			hash := crc32.ChecksumIEEE([]byte(virtualKey))
			hr.hashMap[hash] = node
		}
	}
}

// 获取虚拟节点键
func (hr *HashRing) getVirtualKey(node string, index int) string {
	return node + strconv.Itoa(index)
}

// 添加节点
func (hr *HashRing) AddNode(node string) {
	hr.nodes = append(hr.nodes, node)
	hr.generateHashRing()
}

// 删除节点
func (hr *HashRing) RemoveNode(node string) {
	for i := len(hr.nodes) - 1; i >= 0; i-- {
		if hr.nodes[i] == node {
			hr.nodes = append(hr.nodes[:i], hr.nodes[i+1:]...)
		}
	}
	hr.generateHashRing()
}

// 根据键获取节点
func (hr *HashRing) GetNode(key string) (string, error) {
	if len(hr.nodes) == 0 {
		return "", fmt.Errorf("no nodes available in the hash ring")
	}

	hash := crc32.ChecksumIEEE([]byte(key))
	// 查找大于等于哈希值的最小哈希
	for k := range hr.hashMap {
		if k >= hash {
			return hr.hashMap[k], nil
		}
	}

	// 如果没有找到大于等于哈希值的最小哈希，则返回环的第一个节点
	return hr.nodes[0], nil
}

func main() {
	// 创建一致性哈希环并添加节点
	hashRing := NewHashRing(3, []string{"node1", "node2", "node3"})

	// 添加更多节点
	hashRing.AddNode("node4")

	// 删除节点
	hashRing.RemoveNode("node3")

	// 获取指定键的节点
	key := "mykey"
	node, err := hashRing.GetNode(key)
	if err != nil {
		fmt.Println("Error:", err)
		return
	}

	fmt.Printf("Key %s maps to node %s\n", key, node)
}

注意，此示例代码只是一个基本的实现，可能不具备完整的容错和平衡性。

总结

在这个实现中，我们创建了一个HashRing结构来表示一致性哈希环。我们使用 CRC32 哈希算法计算节点的哈希值，并使用虚拟节点在哈希环上进行分布。generateHashRing函数用于生成哈希环，AddNode和RemoveNode函数用于动态添加和删除节点，GetNode函数用于根据键获取相应的节点。

在main函数中，我们使用示例数据创建了一个一致性哈希环，并演示了添加、删除和获取节点的操作。