架构师训练营 1 期 -- 第五周作业

import math
import bisect
from abc import ABC
class ConsistentHashRing(ABC):
    """
    普通一致性Hash环，存储键值对，key是hash值，value是node IP或名称
    """
    def __init__(self, nodes=[]):
        """
        对传入的节点构建hash环
        :param nodes:
        """
        self.nodes = nodes
        # 节点的hash code数组
        self.node_array = []
        # 节点hash code和节点信息的mapping
        self.node_dict = {}
        self.ring_len = pow(2, 16) - 1
        # 创建节点
        for node in self.nodes:
            hash_code = self.get_hash_code(node)
            self.add_node(hash_code, node)
        pass
    def add_node(self, hash_code, node):
        """
        将节点有序添加到hash_code的位置
        :param hash_code:
        :param node:
        :return:
        """
        bisect.insort(self.node_array, hash_code)
        self.node_dict[hash_code] = node
        pass
    def get_node(self, key):
        """
        根据key的hash值获取距离最近的节点信息
        :param key:
        :return:
        """
        hash_code = self.get_hash_code(key)
        for node in self.node_array:
            if hash_code <= node:
                return self.node_dict[node]
        return self.node_dict[self.node_array[0]]
    def get_hash_code(self, key):
        """
        计算hash code
        :param key:
        :return:
        """
        return math.fabs(hash(key)) % self.ring_len
class AdvancedHashRing(ConsistentHashRing):
    """
    使用虚拟节点构建一致性hash环
    """
    def __init__(self, nodes, replicas):
        """
        构造函数，对每个节点创建replicas个虚拟节点，平均分配到hash环上。
        :param nodes: 节点列表
        :param replicas: 每隔节点创建的虚拟节点数目
        """
        super().__init__()
        self.nodes = nodes
        self.replicas = replicas
        self.generate_virtual_node()
    def generate_virtual_node(self):
        for node in self.nodes:
            for i in range(self.replicas):
                # 创建虚拟节点
                hash_code = self.get_hash_code(node + str(i))
                self.add_node(hash_code, node)

# -*- coding:utf-8 -*-
import math
import pytest
from consistent_hash_ring import AdvancedHashRing
@pytest.fixture
def input_data():
    node_list = ['node' + str(i) for i in range(10)]
    key_list = ('key' + str(j) for j in range(1000000))
    return node_list, key_list
@pytest.mark.parametrize('replicas', [10, 50, 100, 150, 200, 300, 500])
def test_hash_ring(input_data, replicas):
    ring = AdvancedHashRing(input_data[0], replicas)
    result = {}
    for key in input_data[1]:
        node = ring.get_node(key)
        if node in result:
            result[node] = result[node] + 1
        else:
            result[node] = 1
    print('使用 {} 个虚拟节点，测试结果如下:'.format(replicas))
    print(result)
    print('方差: {}'.format(calculate_standard_deviation(result, 100000)))
    print('**************************************')
    print()
def calculate_standard_deviation(result, average):
    my_sum = 0
    for item in result.values():
        my_sum = my_sum + math.pow(item - average, 2)
    return int(math.sqrt(my_sum / len(result)))
# 如果未安装pytest，使用如下代码测试
# test_hash_ring(input_data(), 10)
# test_hash_ring(input_data(), 100)
# test_hash_ring(input_data(), 150)
# test_hash_ring(input_data(), 300)
# test_hash_ring(input_data(), 1000)