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

用户头像
stardust20
关注
发布于: 2020 年 07 月 07 日



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

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



使用python实现 :

import hashlib
import random
import numpy as np


# 获取到经过MD5加密的字符串并返回
def md5_encode(str):
str = str.encode('utf-8')
m = hashlib.md5()
m.update(str)
return m.hexdigest()


class NodeInfo(object):
def __init__(self, hash_key, node, virtual_node):
self.hash_key = hash_key
self.node = node
self.virtual_node = virtual_node


class ConsistencyHash(object):
def __init__(self):
self.nodes = []
self.key_nodes = []
# 每个节点虚拟出多少节点
self.virtual_node_num = 185

@staticmethod
def get_hash_key(key):
md5 = md5_encode(key)
# 将md5值当成16进制解析,转成10进制,除进2的32次方,计算hash值
return int(md5, 16) % (2 ** 32)

# 获取某个key值对应的node
def get_node(self, str):
hash_key = self.get_hash_key(str)
for i, val in enumerate(self.key_nodes):
if hash_key < val.hash_key:
return val.node
return self.key_nodes[-1].node

# 添加服务器
def add_node(self, node):
self.nodes.append(node)
for num in range(0, self.virtual_node_num):
virtual_node = node + '#' + str(num)
virtual_node_key = self.get_hash_key(virtual_node)
node_info = NodeInfo(virtual_node_key, node, virtual_node)
self.key_nodes.append(node_info)

# 按hash key 从小到大排序
self.key_nodes.sort(key=lambda n: n.hash_key)


# 生成随机字符串
def random_str(slen=10):
seed = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_+=-"
sa = []
for i in range(slen):
sa.append(random.choice(seed))
return ''.join(sa)


if __name__ == '__main__':
consistency_hash = ConsistencyHash()
nodes = [
"192.168.1.1",
"192.168.1.2",
"192.168.1.3",
"192.168.1.4",
"192.168.1.5",
"192.168.1.6",
"192.168.1.7",
"192.168.1.8",
"192.168.1.9",
"192.168.1.10",
]
map_node_count = {}
for node in nodes:
consistency_hash.add_node(node)
map_node_count[node] = 0

for i in range(0, 1000000):
slen = random.randint(1, 50)
str = random_str(slen)
node = consistency_hash.get_node(str)
map_node_count[node] += 1
print(map_node_count)
print(np.std(list(map_node_count.values()), ddof=1))


每台服务器虚拟185个节点,各个节点的分布情况:

{'192.168.1.1': 91610,

'192.168.1.2': 99209,

'192.168.1.3': 102805,

'192.168.1.4': 101124,

'192.168.1.5': 99019,

'192.168.1.6': 97357,

'192.168.1.7': 103388,

'192.168.1.8': 99186,

'192.168.1.9': 109138,

'192.168.1.10': 97164}

标准差:

4714.296035582737



用户头像

stardust20

关注

还未添加个人签名 2019.11.18 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 -- 第五周作业