写点什么

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作业