架构师训练营第五周”技术选型一“作业

def get_hash(s):
    """
    hash函数，s -> 0 ~ 2^32-1
    """
    m = hashlib.md5(s.encode()).hexdigest()[:8]
    return int(m, 16)

class HashServer:
    """
    普通Hash
    """
    def __init__(self):
        # 存储节点IP的hash_code -> node_ip对应关系
        self._code_2_node_ip = {}
        # 存储node hash_code列表，按从小到大排序，表示hash环
        self._sorted_node_code_list = []
    def add_node(self, node_ip):
        """
        添加节点
        """
        hash_code = get_hash(node_ip)
        assert hash_code not in self._code_2_node_ip, "Hash Code冲突，可能是相同的服务器"
        self._sorted_node_code_list.append(hash_code)
        self._sorted_node_code_list.sort()  # 保证hash环有序
        self._code_2_node_ip[hash_code] = node_ip
    def remove_node(self, node_ip):
        """
        删除节点
        """
        hash_code = get_hash(node_ip)
        if hash_code not in self._sorted_node_code_list:
            return
        self._sorted_node_code_list.remove(hash_code)
        del self._code_2_node_ip[hash_code]
    def get_node_ip_by_key(self, key):
        """
        根据key获取应该存储到哪台服务器
        :param key:
        :return: node_ip
        """
        hash_code = get_hash(key)
        for code in self._sorted_node_code_list:
            if code > hash_code:
                return self._code_2_node_ip[code]
        return self._code_2_node_ip[self._sorted_node_code_list[0]]

class HashServerV2:
    """
    一致性Hash
    """
    def __init__(self):
        # 存储节点IP的hash_code -> node_ip对应关系
        self._code_2_node_ip = {}
        # 存储node hash_code列表，按从小到大排序，表示hash环
        self._sorted_node_code_list = []
        self.virtual_num_per_node = 10  # 每个真实服务器虚拟多少个虚拟节点
    def add_node(self, node_ip):
        """
        添加节点
        """
        for x in range(self.virtual_num_per_node):
            virtual_ip = "{}|{}".format(node_ip, x)
            hash_code = get_hash(virtual_ip)
            self._sorted_node_code_list.append(hash_code)
            self._sorted_node_code_list.sort()  # 保证hash环有序
            self._code_2_node_ip[hash_code] = node_ip
    def remove_node(self, node_ip):
        """
        删除节点
        """
        for x in range(self.virtual_num_per_node):
            virtual_ip = "{}|{}".format(node_ip, x)
            hash_code = get_hash(virtual_ip)
            self._sorted_node_code_list.remove(hash_code)
            del self._code_2_node_ip[hash_code]
    def get_node_ip_by_key(self, key):
        """
        根据key获取应该存储到哪台服务器
        :param key:
        :return: node_ip
        """
        hash_code = get_hash(key)
        for code in self._sorted_node_code_list:
            if code > hash_code:
                return self._code_2_node_ip[code]
        return self._code_2_node_ip[self._sorted_node_code_list[0]]

def random_key():
    return "{}".format(random.randint(0, 10 ** 10))
  
  if __name__ == '__main__':
    # 10台服务器
    node_num = 10
    ip_list = ["10.1.1.{}".format(x) for x in range(node_num)]
    # 存储每个服务器保存key数量，node_key_num[0]表示 10.1.1.0保存的key数量，node_key_num[5]表示10.1.1.5保存的key数量
    node_key_num = Counter()  # 普通hash算法
    node_key_num_v2 = Counter()  # 一致性hash算法
    hash_server = HashServer()
    hash_server_v2 = HashServerV2()
    for ip in ip_list:
        hash_server.add_node(ip)
        hash_server_v2.add_node(ip)
    for _ in range(1000000):
        key = random_key()
        # 普通hash
        node_ip = hash_server.get_node_ip_by_key(key)
        node_key_num.update({node_ip: 1})
        # 一致性hash
        node_ip = hash_server_v2.get_node_ip_by_key(key)
        node_key_num_v2.update({node_ip: 1})
    print(list(node_key_num.items()))
    print(list(node_key_num_v2.items()))
    print("普通Hash标准差：{}".format(numpy.std(list(node_key_num.values()), ddof=1)))
    print("一致性Hash标准差：{}".format(numpy.std(list(node_key_num_v2.values()), ddof=1)))
# 普通Hash各个节点key数量：
# ('10.1.1.2', 201918)
# ('10.1.1.7', 284492)
# ('10.1.1.8', 136197)
# ('10.1.1.6', 42034)
# ('10.1.1.5', 133386)
# ('10.1.1.4', 55464)
# ('10.1.1.1', 109787)
# ('10.1.1.0', 21179)
# ('10.1.1.9', 4383)
# ('10.1.1.3', 11160)
# 普通Hash标准差：91613.09267420969
# 一致性Hash各个节点key数量：
# ('10.1.1.6', 78907)
# ('10.1.1.3', 116272)
# ('10.1.1.9', 130904)
# ('10.1.1.2', 112032)
# ('10.1.1.8', 117422)
# ('10.1.1.7', 55216)
# ('10.1.1.1', 157035)
# ('10.1.1.5', 55659)
# ('10.1.1.4', 58239)
# ('10.1.1.0', 118314)
# 一致性Hash标准差：35617.022827731