Week05 作业

发布于: 2020 年 07 月 08 日

一致性哈希Python实现:

10.10.1.9=9.64%

10.10.1.8=9.93%

10.10.1.3=9.66%

10.10.1.7=10.13%

10.10.1.6=9.44%

10.10.1.2=9.93%

10.10.1.10=9.72%

10.10.1.1=10.42%

10.10.1.4=10.19%

10.10.1.5=10.94%

标准差:13247.916892855268

负载的不均衡性在可接收的范围之内,可以优化哈希算法。

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))
for node, vnode in vnode_info.items():
print("{}={}%".format(node, len(vnode) / case_num * 100))
if __name__ == '__main__':
test_consistent_hash(1000000, 200)

用户头像

熊威

关注

还未添加个人签名 2019.06.12 加入

还未添加个人简介

评论

发布
暂无评论
Week05作业