Fundamentals
Consistent Hashing

What is Consistent Hashing?

一致性哈希（Consistent Hashing）是一种分布式系统中常用的哈希算法，特别适用于在节点数量动态变化的情况下（如增加或减少服务器）的负载均衡问题。传统的哈希算法在节点数量变化时，可能导致大量的数据重新分配，而一致性哈希能够尽量减少数据的重新分布。

为什么使用一致性哈希？

  1. 动态扩展性：在分布式系统中，节点（例如缓存服务器、数据库分片）可能会增加或减少。传统的哈希算法（如取模）在节点数量变化时，会导致大量数据重新分配。而一致性哈希算法只会重分配一部分数据，大部分数据可以继续保留在原有节点上。

  2. 负载均衡：一致性哈希将数据均匀分布在哈希环上，并根据节点数量变化动态调整数据的分配，以达到更平衡的负载分布。

  3. 容错性：当某个节点失效时，一致性哈希只会将这个节点负责的部分数据重新分配给相邻的节点，其他节点不受影响。

一致性哈希的工作原理

  1. 构造哈希环：将哈希值空间组织成一个虚拟的环状结构（通常将哈希值对一个大数取模形成环，比如 [0, 2^32-1]）。

  2. 节点映射到哈希环：对每个节点进行哈希，将节点的哈希值映射到环上的某个位置。

  3. 数据映射到哈希环：对每个数据（比如缓存的键、存储的对象）进行哈希，找到其在环上的位置。将该数据分配到“顺时针方向”遇到的第一个节点。

  4. 增加/减少节点时的调整：当一个节点加入或移除时，只需要调整该节点和其前后节点上的数据分配，不需要全局重新分配数据。

伪代码实现

以下是一个简单的一致性哈希算法的伪代码实现：

class ConsistentHashing:
    def __init__(self, num_replicas=3):
        self.num_replicas = num_replicas  # 虚拟节点数量
        self.ring = {}  # 哈希环
        self.sorted_keys = []  # 排序后的节点哈希值列表
 
    # 将节点加入哈希环
    def add_node(self, node):
        for i in range(self.num_replicas):
            key = self.hash_function(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.num_replicas):
            key = self.hash_function(f"{node}-{i}")
            del self.ring[key]
            self.sorted_keys.remove(key)
 
    # 查找数据的节点
    def get_node(self, data):
        if not self.ring:
            return None
 
        key = self.hash_function(data)
        # 顺时针找到第一个大于或等于数据哈希值的节点
        for node_key in self.sorted_keys:
            if key <= node_key:
                return self.ring[node_key]
 
        # 如果没有找到，返回第一个节点（因为是环状的）
        return self.ring[self.sorted_keys[0]]
 
    # 简单的哈希函数（可以替换为更复杂的哈希函数）
    def hash_function(self, key):
        return hash(key) % (2 ** 32)
 
# 使用示例
ch = ConsistentHashing()
ch.add_node("NodeA")
ch.add_node("NodeB")
ch.add_node("NodeC")
 
data = "some_data"
node = ch.get_node(data)
print(f"Data '{data}' is mapped to node '{node}'")

伪代码说明：

  1. num_replicas：表示虚拟节点的数量，增加虚拟节点可以减少负载不均的问题。

  2. add_node(node)：将一个节点映射到哈希环上，并创建虚拟节点。每个虚拟节点的位置由 node 和一个索引通过哈希函数计算得到。

  3. remove_node(node)：从哈希环中移除一个节点及其对应的虚拟节点。

  4. get_node(data)：根据数据的哈希值，顺时针查找负责存储该数据的第一个节点。如果没有找到，则返回哈希环上的第一个节点（环状结构）。

  5. hash_function(key)：哈希函数用于生成节点和数据的哈希值，可以根据实际需求使用更复杂的哈希算法。

通过一致性哈希，节点的增加或移除只会影响环上相邻的部分节点，而不会影响其他部分的分布，大大减少了数据重新分配的范围。

OLTP vs OLAPStorage and Retrieval