架构师训练营(第 5 周作业)

用户头像
李德政
关注
发布于: 2020 年 07 月 08 日
架构师训练营(第 5 周作业)



作业描述:

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

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

1. 代码

关键点:

  • Hash操作:计算的是虚拟节点的hash值,然后放到环上

  • 统计方差个数时:是数据对应虚拟节点的物理节点



#!/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()



2. 图:标准差-虚拟节点数



3. 数据明细:

物理节点=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



发布于: 2020 年 07 月 08 日 阅读数: 34
用户头像

李德政

关注

还未添加个人签名 2017.11.30 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营(第 5 周作业)