哈希环

哈希环（Hash Ring）是一种常见的数据分片方案，用于将数据均匀地分布在多个节点上。哈希环通常用于实现分布式缓存、负载均衡、分布式数据库等系统中。

哈希环的基本原理是将所有节点和数据都映射到一个环上，每个节点和数据在环上都有一个对应的哈希值。当需要访问某个数据时，将该数据的哈希值映射到环上，然后沿着环顺时针方向找到第一个比该哈希值大的节点，该节点即为该数据所在的节点。如果需要增加或删除节点，只需要重新计算节点和数据的哈希值，并在环上重新分配。

算法哈希环的实现通常包括以下步骤：

• 定义哈希函数，将节点和数据映射到一个哈希值。

def hash_fnv1(key):
    """
    FNV1 hash function
    """
    FNV_OFFSET = 2166136261
    FNV_PRIME = 16777619
    hash_value = FNV_OFFSET
    for byte in key.encode('utf-8'):
        hash_value = (hash_value * FNV_PRIME) % (2 ** 32)
        hash_value = hash_value ^ byte
    return hash_value

• 将所有节点和数据的哈希值映射到一个环上，按照哈希值从小到大排列。
• 当需要访问某个数据时，将该数据的哈希值映射到环上，并沿着环顺时针方向查找第一个比该哈希值大的节点，该节点即为该数据所在的节点。
• 如果需要增加或删除节点，只需要重新计算节点和数据的哈希值，并在环上重新分配。

常见的哈希函数包括MD5、SHA-1、SHA-256等，具体选择哪种哈希函数取决于应用的需求和性能要求。哈希环的优点是可以很好地实现数据均衡和容错，但缺点是当节点数量较少时可能会出现数据倾斜的情况。

import bisect

class HashRing:
    """
    哈希环类
    """
    def __init__(self, nodes, replicas=3, hash_func=hash):
        """
        初始化哈希环
        :param nodes: 节点列表
        :param replicas: 每个节点的虚拟节点数量
        :param hash_func: 哈希函数，默认使用内置的哈希函数
        """
        self.nodes = nodes
        self.replicas = replicas
        self.hash_func = hash_func
        self.ring = dict()
        for node in self.nodes:
            for i in range(self.replicas):
                # 使用节点名和虚拟节点编号生成哈希值
                key = '{}:{}'.format(node, i)
                # 计算哈希值，并将哈希值和节点映射关系加入哈希环中
                self.ring[self.hash_func(key)] = node
        # 将哈希环上的哈希值排序
        self.keys = sorted(self.ring.keys())

    def get_node(self, key):
        """
        获取存储 key 的节点
        :param key: 要存储的键值
        :return: 存储 key 的节点
        """
        if not self.nodes:
            return None
        # 计算 key 的哈希值
        key_hash = self.hash_func(key)
        # 在哈希环上查找距离 key_hash 最近的节点
        pos = bisect.bisect(self.keys, key_hash)
        if pos == len(self.keys):
            # 如果 key_hash 大于哈希环上所有的哈希值，那么返回第一个节点
            return self.ring[self.keys[0]]
        else:
            # 否则返回距离 key_hash 最近的节点
            return self.ring[self.keys[pos]]
        

# 测试代码
nodes = ['node1', 'node2', 'node3']
ring = HashRing(nodes)

ip = '192.23.3.1'
node = ring.get_node(ip)
print('IP {} 存储在节点 {}'.format(ip, node))