架构师训练营第五周作业
算法实现:用python实现了一致性 hash 算法,hash算法用的md5,程序中使用了虚拟节点来均衡节点的分布,
测试:测试 100 万 KV 数据,10 个服务器节点的情况下,虚拟节点分别选50,100,150,200的标准差。结果显示200个虚拟节点分布更均衡。
import hashlib
import numpy as np
class ConsistentHash():
def init(self, virtualnodenum):
self.virtualnodenum = virtualnodenum
self.key_list = []
self.keynodemap = {}
def generate_key(self, value):
m = hashlib.md5(value.encode("utf-8"))
return np.long(m.hexdigest(), 16)
def add_node(self, node):
for i in range(0, self.virtualnodenum):
key = self.generate_key(node+':'+str(i))
self.key_list.append(key)
self.keynodemap[key] = node
self.key_list.sort()
def remove_node(self, node):
for key in self.keynodemap.keys():
if self.keynodemap[key] == node:
self.keynodemap.pop(key)
self.key_list.remove(key)
def get_node(self, value):
mykey = self.generatekey(value)
for key in self.key_list:
if my_key <= key:
return self.keynodemap[key]
return self.keynodemap[self.key_list[0]]
class Test():
def init(self):
self.CH = None
self.nodeclientscount = {}
self.clients = []
self.servers = []
self.get_servers()
self.get_clients()
def get_servers(self):
serveriptemplate = "10.198.{}.1"
for i in range(0,10):
self.servers.append(serveriptemplate.format(str(i)))
def get_clients(self):
clientiptemplate = "202.{}.{}.{}"
for i in range(1,155):
for j in range(1,255):
for k in range(1,255):
self.clients.append(clientiptemplate.format(str(i),str(j),str(k)))
def run(self,virtualnodecount):
self.CH = ConsistentHash(virtualnodecount)
for server in self.servers:
self.CH.add_node(server)
self.nodeclientscount[server] = 0
for client in self.clients:
node = self.CH.get_node(client)
self.nodeclientscount[node] = self.nodeclientscount[node]+1
for server in self.servers:
print("{} : {}".format(server, self.nodeclientscount[server]))
print(np.std([x for x in self.nodeclientscount.values()]))
if name == 'main':
test = Test()
print("50 virtual nodes")
test.run(50)
print("100 virtual nodes")
test.run(100)
print("150 virtual nodes")
test.run(150)
print("200 virtual nodes")
test.run(200)
****************output************************
50 virtual nodes
10.198.0.1 : 1202855
10.198.1.1 : 1082121
10.198.2.1 : 1047370
10.198.3.1 : 681923
10.198.4.1 : 963204
10.198.5.1 : 934948
10.198.6.1 : 891166
10.198.7.1 : 1009331
10.198.8.1 : 795448
10.198.9.1 : 1327098
178114.1916609679
100 virtual nodes
10.198.0.1 : 1160338
10.198.1.1 : 958051
10.198.2.1 : 947587
10.198.3.1 : 1027764
10.198.4.1 : 1028677
10.198.5.1 : 968278
10.198.6.1 : 772139
10.198.7.1 : 1112422
10.198.8.1 : 917847
10.198.9.1 : 1042361
102713.69544924377
150 virtual nodes
10.198.0.1 : 1205982
10.198.1.1 : 1045739
10.198.2.1 : 957861
10.198.3.1 : 1074543
10.198.4.1 : 878840
10.198.5.1 : 1022815
10.198.6.1 : 857838
10.198.7.1 : 1055701
10.198.8.1 : 968668
10.198.9.1 : 867477
104160.18927997394
200 virtual nodes
10.198.0.1 : 1027243
10.198.1.1 : 1068310
10.198.2.1 : 1013460
10.198.3.1 : 1043600
10.198.4.1 : 907492
10.198.5.1 : 981665
10.198.6.1 : 887041
10.198.7.1 : 1028074
10.198.8.1 : 975594
10.198.9.1 : 1002985
54882.08243716705
评论