week5 作业

发布于: 2020 年 07 月 08 日

作业一:

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

编程语言python3,代码示例如下:

# !/bin/usr/python
# -*- coding:utf-8 -*-
# 创建日期: 2020/7/8
# 文件名: consistentHash.py
# 文件描述
import md5hash
from hashlib import md5
class HashRing(object):
def __init__(self, nodes=None, replicas=2):
"""
初始构造一致性环
:param nodes: 物理节点列表
:param replicas: 每个物理节点虚拟的虚拟节点数量
"""
self.replicas = replicas
# key:虚拟节点位置 value:虚拟节点对应的物理节点名称
self.ring = {}
# 所有虚拟节点位置按升序排序列表
self._sorted_keys = []
# 初始化虚拟节点一致性环
if nodes:
for node in nodes:
self.add_node(node)
def add_node(self, node):
"""
在一致性环上增加一个物理节点,包括其虚拟节点
:param node:
:return:
"""
for i in range(0, self.replicas):
key = self.gen_key('%s:%s' % (node, i))
self.ring[key] = node
self._sorted_keys.append(key)
self._sorted_keys.sort()
def remove_node(self, node):
"""
从一致性环上删除一个物理节点,包括其虚拟节点
"""
for i in range(0, self.replicas):
key = self.gen_key('%s:%s' % (node, i))
del self.ring[key]
self._sorted_keys.remove(key)
def get_key_belong_node(self, string_key):
"""
查询某个key属于哪个节点
:param string_key:
:return: 如果环不存在,返回None,否则返回匹配的节点名称
"""
return self.get_node_pos(string_key)[0]
def get_node_all_virtual_pos(self, node):
"""
查询某个物流节点所有的虚拟节点位置
:param node: 物理节点名称
:return: 虚拟节点位置列表
"""
keys = []
for i in range(0, self.replicas):
key = self.gen_key("%s:%s" % (node, i))
keys.append(key)
return keys
def get_node_pos(self, string_key):
"""
获取某个key字符串在一致性环所属的环位置及对应的环索引
:param string_key:
:return: 空行,返回(None,None)
"""
if not self.ring:
return None, None
key = self.gen_key(string_key)
nodes = self._sorted_keys
for i in range(0, len(nodes)):
node = nodes[i]
if key <= node:
return self.ring[node], i
return self.ring[nodes[0]], 0
def get_nodes(self, string_key):
if not self.ring:
yield None, None
node, pos = self.get_node_pos(string_key)
for key in self._sorted_keys[pos:]:
yield self.ring[key]
while True:
for key in self._sorted_keys:
yield self.ring[key]
def gen_key(self, key):
"""
根据key值其在一致性环上的位置
:param key:
:return:
"""
m = md5()
m.update(key.encode(encoding='UTF-8'))
return int(m.hexdigest(), 16)
if __name__ == "__main__":
hr = HashRing()
hr.add_node("node1")
hr.get_key_belong_node("34546")

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

编程语言Python3

# !/bin/usr/python
# -*- coding:utf-8 -*-
# 创建日期: 2020/7/8
# 文件名: test_hash.py
# 文件描述
from unittest import TestCase, TestSuite, TextTestRunner
from consistentHash import HashRing
import random
import string
import numpy as np
class HaseTestCase(TestCase):
def setUp(self):
self.hash = HashRing(nodes=['node0', 'node1', 'node2', 'node3', 'node4', 'node5', 'node6', 'node7', 'node8', 'node9'],
replicas=2)
def tearDown(self):
self.hash = None
def testKeyString(self):
ran_str = ''.join(random.sample(string.ascii_letters + string.digits, 2))
print(ran_str)
def testKeyStringNum(self):
node_num_dict = {}
node_name_list = self.hash.ring.values()
for node_name in node_name_list:
node_num_dict[node_name] = 0
sample_str = ''.join(random.sample(string.ascii_letters + string.digits + string.punctuation, 32))
for i in range(0, 1000000):
ran_str = sample_str + str(i)
node_name = self.hash.get_key_belong_node(ran_str)
if node_name in node_num_dict.keys():
node_num_dict[node_name] += 1
num_list = np.array([list(node_num_dict.values())])
std_val = np.std(num_list, axis=1)
print(std_val[0])
def add_suite():
suite = TestSuite()
suite.addTest(HaseTestCase("testKeyString"))
suite.addTest(HaseTestCase("testKeyStringNum"))
return suite
if __name__ == "__main__":
suite = add_suite()
runner = TextTestRunner()
runner.run(suite)

输出结果为:66400.4802512753

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

关注

还未添加个人签名 2019.04.12 加入

还未添加个人简介

评论

发布
暂无评论
week5作业