如何使用 Ketama 算法实现一致性哈希？

推荐答案

// www.javascriptcn.com code example
import hashlib

class KetamaHash:
    def __init__(self, nodes=None, replicas=160):
        self.replicas = replicas
        self.ring = {}
        self.sorted_keys = []

        if nodes:
            for node in nodes:
                self.add_node(node)

    def add_node(self, node):
        for i in range(self.replicas):
            key = self._hash(f"{node}:{i}")
            self.ring[key] = node
            self.sorted_keys.append(key)
        self.sorted_keys.sort()

    def remove_node(self, node):
        for i in range(self.replicas):
            key = self._hash(f"{node}:{i}")
            del self.ring[key]
            self.sorted_keys.remove(key)

    def get_node(self, key):
        if not self.ring:
            return None

        hash_key = self._hash(key)
        for key in self.sorted_keys:
            if hash_key <= key:
                return self.ring[key]
        return self.ring[self.sorted_keys[0]]

    def _hash(self, key):
        return int(hashlib.md5(key.encode('utf-8')).hexdigest(), 16)

# 使用示例
nodes = ["node1", "node2", "node3"]
ketama = KetamaHash(nodes)
print(ketama.get_node("some_key"))

本题详细解读

一致性哈希简介

一致性哈希是一种特殊的哈希技术，主要用于分布式缓存系统中。它通过将缓存节点和数据映射到一个虚拟的环上，使得在节点增减时，只有少量的数据需要重新映射，从而减少数据迁移的成本。

Ketama 算法

Ketama 算法是一种基于一致性哈希的算法，广泛应用于 Memcached 等分布式缓存系统中。它的核心思想是通过虚拟节点（replicas）来平衡负载，避免数据倾斜问题。

实现步骤

1. 初始化：创建一个 KetamaHash 类，初始化时传入节点列表和虚拟节点数量（默认为 160）。
2. 添加节点：为每个节点生成多个虚拟节点，并将这些虚拟节点映射到哈希环上。
3. 删除节点：从哈希环上移除指定节点的所有虚拟节点。
4. 获取节点：根据给定的键值计算哈希值，然后在哈希环上找到最近的节点。

关键点

• 虚拟节点：通过增加虚拟节点的数量，可以更均匀地分布数据，避免热点问题。
• 哈希函数：使用 MD5 哈希函数将节点和键值映射到哈希环上。
• 排序：为了快速查找最近的节点，哈希环上的键值需要保持有序。

应用场景

Ketama 算法广泛应用于分布式缓存系统（如 Memcached）中，用于在多个缓存节点之间分配数据，确保在节点增减时，数据迁移的成本最小化。