Week 05 作业

发布于: 2020 年 07 月 08 日
Week 05 作业

测试结果:

10.10.1.9=9.6378%

10.10.1.8=9.927900000000001%

10.10.1.3=9.6637%

10.10.1.7=10.1255%

10.10.1.6=9.442%

10.10.1.2=9.9272%

10.10.1.10=9.7217%

10.10.1.1=10.4238%

10.10.1.4=10.1929%

10.10.1.5=10.9375%

std: 1.755073019999999

负载均衡优化hash算法

代码来自: https://xie.infoq.cn/article/1be59cc3152bc83c5662c293d

import hashlib
from collections import defaultdict
from bisect import bisect
servers = [
"10.10.1.1",
"10.10.1.2",
"10.10.1.3",
"10.10.1.4",
"10.10.1.5",
"10.10.1.6",
"10.10.1.7",
"10.10.1.8",
"10.10.1.9",
"10.10.1.10"
]
class HashRing:
def __init__(self, nodes=None, replicas=3):
self.replicas = replicas
self.ring = dict()
self._sorted_keys = []
if nodes:
for node in nodes:
self.add_node(node)
def add_node(self, node):
"""
Adds a `node` to the hash ring (including a number of replicas)
"""
for i in range(self.replicas):
virtual_node = f"{node}#{i}"
key = self.gen_key(virtual_node)
self.ring[key] = node
self._sorted_keys.append(key)
# print(f"{virtual_node} --> {key} --> {node}")
self._sorted_keys.sort()
# print([self.ring[key] for key in self._sorted_keys])
def remove_node(self, node):
"""
Removes `node` from the hash ring and its replicas
"""
for i in range(self.replicas):
key = self.gen_key(f"{node}#{i}")
del self.ring[key]
self._sorted_keys.remove(key)
def get_node(self, string_key):
"""
Given a string key a corresponding node in the hash ring is returned.
If the hash ring is empty, `None` is returned.
"""
return self.get_node_pos(string_key)[0]
def get_node_pos(self, string_key):
"""
Given a string key a corresponding node in the hash ring is returned
along with it's position in the ring.
If the hash ring is empty, (`None`, `None`) is returned.
"""
if not self.ring:
return None, None
key = self.gen_key(string_key)
nodes = self._sorted_keys
pos = bisect(nodes, key) % len(nodes)
return self.ring[nodes[pos]], pos
def gen_key(self, string_key):
"""
Given a string key it returns a long value, this long value represents
a place on the hash ring
"""
m = hashlib.md5()
m.update(string_key.encode('utf-8'))
return m.hexdigest()
def test_consistent_hash(case_num, replicas):
hr = HashRing(servers, replicas)
vnode_info = defaultdict(list)
for i in range(case_num):
node = hr.get_node(str(i))
vnode_info[node].append(i)
print("{}:{}".format(i, node))
node_list = []
for node, vnode in vnode_info.items():
print("{}={}%".format(node, len(vnode) / case_num * 100))
node_list.append(len(vnode) / case_num * 100)
print(node_list)
avg_node = sum(node_list) / len(node_list)
avg_node_list = [node - avg_node for node in node_list]
std = sum(map(lambda x: x ** 2, avg_node_list))
print("std:", std)
if __name__ == '__main__':
test_consistent_hash(1000000, 200)

用户头像

鱼_XueTr

关注

还未添加个人签名 2019.04.19 加入

还未添加个人简介

评论

发布
暂无评论
Week 05 作业