架构师训练营（第 5 周作业）

#!/usr/bin/python
# coding=utf-8
"""
作业一：
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
"""
import hashlib
from collections import defaultdict
class Node(object):
    def __init__(self, node_no, virtual_no):
        self.name = 'node-{}'.format(node_no)
        self.virtual_no = virtual_no
        self.virtual_name = self.name + '#' + str(self.virtual_no)
        self.hash_code = ConsistentHash.cal_hash(self.virtual_name)  # hash值要以虚拟节点的名称计算
class ConsistentHash(object):
    REMAINDER = 2 ** 32 - 1
    def __init__(self, physical_node_cnt, virtual_node_cnt):
        self.physical_node_cnt = physical_node_cnt
        self.virtual_node_cnt = virtual_node_cnt
        # 生成虚拟节点
        self.virtual_nodes = \
            [Node(i, j) for i in range(physical_node_cnt) for j in range(virtual_node_cnt)]
        self.virtual_nodes.sort(key=lambda v: v.hash_code)
    @classmethod
    def cal_hash(cls, i):
        """计算hash"""
        md5_str = hashlib.md5(i.encode(encoding='UTF-8')).hexdigest()
        return int(md5_str, 16) % cls.REMAINDER
    def find_node(self, hash_code):
        """查找数据应该插入的节点(二分法)"""
        i, j = 0, len(self.virtual_nodes)
        while i < j:
            mid = (i + j) // 2
            if self.virtual_nodes[mid].hash_code < hash_code:
                i = mid + 1
            else:
                j = mid
        # 如果是最后一个位置，则选第0个节点
        node = self.virtual_nodes[0] if i == len(self.virtual_nodes) else self.virtual_nodes[i]
        return node
    def get_standard_deviation(self, total_num=10 ** 6):
        """获取标准差"""
        # 计算数据落在物理节点的个数
        node_item_cnt = defaultdict(int)
        for i in range(total_num):
            hash_code = self.cal_hash('user-test-hello-' + str(i))
            insert_node = self.find_node(hash_code)
            node_item_cnt[insert_node.name] += 1
        # 计算标准差
        average = total_num // self.physical_node_cnt
        physical_names = list(set([v.name for v in self.virtual_nodes]))
        s = sum([(node_item_cnt[node_name] - average) ** 2 for node_name in physical_names])
        return int((s // self.physical_node_cnt) ** 0.5)
def main():
    """获取不同虚拟节点情况下的标准差"""
    xs, ys = [], []
    physical_node_cnt = 10
    for virtual_node_cnt in range(1, 400, 5):
        obj = ConsistentHash(physical_node_cnt=physical_node_cnt, virtual_node_cnt=virtual_node_cnt)
        deviation = obj.get_standard_deviation()
        print('物理节点={} 虚拟节点={} 方差={}'.format(physical_node_cnt, virtual_node_cnt, deviation))
        xs.append(virtual_node_cnt)
        ys.append(deviation)
    print(xs)
    print(ys)
if __name__ == '__main__':
    main()

物理节点=10 虚拟节点=1 方差=110131
物理节点=10 虚拟节点=6 方差=37941
物理节点=10 虚拟节点=11 方差=28188
物理节点=10 虚拟节点=16 方差=26214
物理节点=10 虚拟节点=21 方差=21782
物理节点=10 虚拟节点=26 方差=22998
物理节点=10 虚拟节点=31 方差=17548
物理节点=10 虚拟节点=36 方差=15407
物理节点=10 虚拟节点=41 方差=15036
物理节点=10 虚拟节点=46 方差=14707
物理节点=10 虚拟节点=51 方差=16123
物理节点=10 虚拟节点=56 方差=14757
物理节点=10 虚拟节点=61 方差=12980
物理节点=10 虚拟节点=66 方差=13959
物理节点=10 虚拟节点=71 方差=10295
物理节点=10 虚拟节点=76 方差=9850
物理节点=10 虚拟节点=81 方差=10152
物理节点=10 虚拟节点=86 方差=10999
物理节点=10 虚拟节点=91 方差=11221
物理节点=10 虚拟节点=96 方差=10412
物理节点=10 虚拟节点=101 方差=9842
物理节点=10 虚拟节点=106 方差=13037
物理节点=10 虚拟节点=111 方差=10198
物理节点=10 虚拟节点=116 方差=10424
物理节点=10 虚拟节点=121 方差=9063
物理节点=10 虚拟节点=126 方差=8513
物理节点=10 虚拟节点=131 方差=9474
物理节点=10 虚拟节点=136 方差=8285
物理节点=10 虚拟节点=141 方差=7341
物理节点=10 虚拟节点=146 方差=7484
物理节点=10 虚拟节点=151 方差=8705
物理节点=10 虚拟节点=156 方差=7974
物理节点=10 虚拟节点=161 方差=7630
物理节点=10 虚拟节点=166 方差=6686
物理节点=10 虚拟节点=171 方差=4738
物理节点=10 虚拟节点=176 方差=4977
物理节点=10 虚拟节点=181 方差=5199
物理节点=10 虚拟节点=186 方差=5953
物理节点=10 虚拟节点=191 方差=5285
物理节点=10 虚拟节点=196 方差=5351
物理节点=10 虚拟节点=201 方差=5926
物理节点=10 虚拟节点=206 方差=6431
物理节点=10 虚拟节点=211 方差=6488
物理节点=10 虚拟节点=216 方差=5167
物理节点=10 虚拟节点=221 方差=5781
物理节点=10 虚拟节点=226 方差=5836
物理节点=10 虚拟节点=231 方差=6032
物理节点=10 虚拟节点=236 方差=6255
物理节点=10 虚拟节点=241 方差=6136
物理节点=10 虚拟节点=246 方差=5547
物理节点=10 虚拟节点=251 方差=5262
物理节点=10 虚拟节点=256 方差=5371
物理节点=10 虚拟节点=261 方差=5922
物理节点=10 虚拟节点=266 方差=6471
物理节点=10 虚拟节点=271 方差=6287
物理节点=10 虚拟节点=276 方差=5788
物理节点=10 虚拟节点=281 方差=5273
物理节点=10 虚拟节点=286 方差=5126
物理节点=10 虚拟节点=291 方差=4842
物理节点=10 虚拟节点=296 方差=4977
物理节点=10 虚拟节点=301 方差=4799
物理节点=10 虚拟节点=306 方差=4364
物理节点=10 虚拟节点=311 方差=4349
物理节点=10 虚拟节点=316 方差=3856
物理节点=10 虚拟节点=321 方差=3959
物理节点=10 虚拟节点=326 方差=4293
物理节点=10 虚拟节点=331 方差=4052
物理节点=10 虚拟节点=336 方差=3978
物理节点=10 虚拟节点=341 方差=3973
物理节点=10 虚拟节点=346 方差=4551
物理节点=10 虚拟节点=351 方差=4218
物理节点=10 虚拟节点=356 方差=3886
物理节点=10 虚拟节点=361 方差=3350
物理节点=10 虚拟节点=366 方差=3790
物理节点=10 虚拟节点=371 方差=3465
物理节点=10 虚拟节点=376 方差=3491
物理节点=10 虚拟节点=381 方差=3398
物理节点=10 虚拟节点=386 方差=3478
物理节点=10 虚拟节点=391 方差=3573
物理节点=10 虚拟节点=396 方差=3358