【架构师训练营】第五期作业

发布于: 2020 年 07 月 08 日

  • 用你熟悉的编程语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

import hashlib
from collections import defaultdict
REMAINDER = 2 ** 32 - 1
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 = cal_hash(self.virtual_name)
def cal_hash(i):
md5_str = hashlib.md5(i.encode(encoding='UTF-8')).hexdigest()
return int(md5_str, 16) % REMAINDER
def find_node(hash_code, nodes):
i, j = 0, len(nodes)
while i < j:
mid = (i + j) // 2
if nodes[mid].hash_code < hash_code:
i = mid + 1
else:
j = mid
node = nodes[0] if i == len(nodes) else nodes[i]
return node
def gen_virtual_nodes(physical_node_cnt, virtual_node_cnt):
virtual_nodes = [Node(i, j) for i in range(physical_node_cnt) for j in range(virtual_node_cnt)]
virtual_nodes.sort(key=lambda v: v.hash_code)
return virtual_nodes
def get_standard_deviation(physical_node_cnt, virtual_node_cnt, total_num=10 ** 6):
virtual_nodes = gen_virtual_nodes(physical_node_cnt, virtual_node_cnt)
node_item_cnt = defaultdict(int)
for i in range(total_num):
hash_code = cal_hash(str(i))
insert_node = find_node(hash_code, virtual_nodes)
node_item_cnt[insert_node.name] += 1
average = total_num // physical_node_cnt
s = 0
for node_name in list(set([v.name for v in virtual_nodes])):
s += ((node_item_cnt[node_name] - average) ** 2)
return s ** 0.5
if __name__ == '__main__':
for i in range(15):
virtual_node = 2 ** i
print("virtual node:%d && physical node:%d ====> %.3f"%(virtual_node, 10, get_standard_deviation(10, virtual_node)))

用户头像

云064

关注

还未添加个人签名 2018.05.24 加入

还未添加个人简介

评论

发布
暂无评论
【架构师训练营】第五期作业