【week05 作业】

 关注
发布于: 2020 年 07 月 06 日
﻿
from hashlib import md5
from math import sqrt
 
class HashRing(object):
    def __init__(self, nodes=None, replicas=150):
        """
        管理hash环
        :nodes 
            节点
        :replicas
            虚拟节点数
        """
        self.replicas = replicas
        self.ring = {}
        self._sorted_keys = []
        if nodes:
            for node in nodes:
                self.add_node(node)
 
    def add_node(self, node):
        """
        增加节点
        """
        for i in range(0, self.replicas):
            key = self.gen_key(f"{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(f"{node}:{i}")
            del self.ring[key]
            self._sorted_keys.remove(key)
 
    def get_node_keys(self, node):
        """
        获取虚拟节点键值
        """
        keys = []
        for i in range(0, self.replicas):
            key = self.gen_key(f"{node}:{i}")
            keys.append(key)
        return keys
 
    def get_node(self, string_key):
        """
        根据键值获取节点
        """
        return self.get_node_pos(string_key)[0]
 
    def get_node_pos(self, string_key):
        """
        根据传入的键值在hash环上查找节点
        """
        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
 
        node, pos = self.get_node_pos(string_key)
        for key in self._sorted_keys:
            yield self.ring[key]
 
    def gen_key(self, key):
        """
        计算hash值
        """
        m = md5()
        m.update(key.encode('utf-8'))
        return int(m.hexdigest(),16)
﻿
python语言实现的一致性hash实现。
实现一个hash环类HashRing，构造时根据输入参数确定虚拟节点数。
增加节点是，根据虚拟节点数，生成虚拟节点的hash值并放入hash环。
查找时，根据输入的键值生成hash值，并在hash环上寻找大于此hash值的第一个虚拟节点
﻿
测试用例：
#节点数
for repl_num in range(100, 410, 10):
    #服务器数
    server_num = 10
    #键值数
    key_num = 1000000
    countTable = {}
    hr = HashRing(replicas=repl_num)
    for i in range(0,server_num):
        server = f"10.1.1.{i+1}"
        hr.add_node(server)
        countTable[server] = 0
    for i in range(0, key_num):
        key = f'stringkey{i}'
        server = hr.get_node(key)
        countTable[server] = countTable[server] + 1
    print(countTable)
    x = key_num/server_num
    s2 = 0
    for i in range(0,server_num):
        server = f"10.1.1.{i+1}"
        s2 = s2 + (countTable[server]-x)*(countTable[server]-x)
    s = sqrt(s2/server_num)
    print(f'repls:{repl_num} s:{s}')
输出结果
{'10.1.1.1': 106497, '10.1.1.2': 101200, '10.1.1.3': 104267, '10.1.1.4': 101208, '10.1.1.5': 104813, '10.1.1.6': 94808, '10.1.1.7': 109991, '10.1.1.8': 99603, '10.1.1.9': 87847, '10.1.1.10': 89766}
repls:100 s:6825.300359691139
{'10.1.1.1': 106355, '10.1.1.2': 98519, '10.1.1.3': 103141, '10.1.1.4': 94973, '10.1.1.5': 111278, '10.1.1.6': 96765, '10.1.1.7': 112456, '10.1.1.8': 93823, '10.1.1.9': 87878, '10.1.1.10': 94812}
repls:110 s:7632.430792349184
{'10.1.1.1': 94466, '10.1.1.2': 102538, '10.1.1.3': 110266, '10.1.1.4': 102362, '10.1.1.5': 111169, '10.1.1.6': 97092, '10.1.1.7': 111564, '10.1.1.8': 86338, '10.1.1.9': 85035, '10.1.1.10': 99170}
repls:120 s:9089.861880138773
{'10.1.1.1': 92894, '10.1.1.2': 96431, '10.1.1.3': 114066, '10.1.1.4': 110266, '10.1.1.5': 112072, '10.1.1.6': 95192, '10.1.1.7': 108764, '10.1.1.8': 91157, '10.1.1.9': 82751, '10.1.1.10': 96407}
repls:130 s:10003.850018867735
{'10.1.1.1': 90858, '10.1.1.2': 92065, '10.1.1.3': 119506, '10.1.1.4': 108892, '10.1.1.5': 112296, '10.1.1.6': 95875, '10.1.1.7': 111127, '10.1.1.8': 89645, '10.1.1.9': 84174, '10.1.1.10': 95562}
repls:140 s:11293.7752943823
{'10.1.1.1': 92283, '10.1.1.2': 91058, '10.1.1.3': 113011, '10.1.1.4': 110522, '10.1.1.5': 116011, '10.1.1.6': 95122, '10.1.1.7': 112178, '10.1.1.8': 90400, '10.1.1.9': 84424, '10.1.1.10': 94991}
repls:150 s:10990.098288914436
{'10.1.1.1': 90950, '10.1.1.2': 94887, '10.1.1.3': 108981, '10.1.1.4': 107152, '10.1.1.5': 110638, '10.1.1.6': 95478, '10.1.1.7': 114368, '10.1.1.8': 94463, '10.1.1.9': 86884, '10.1.1.10': 96199}
repls:160 s:8927.738302616179
{'10.1.1.1': 90550, '10.1.1.2': 98143, '10.1.1.3': 101904, '10.1.1.4': 111191, '10.1.1.5': 106610, '10.1.1.6': 99433, '10.1.1.7': 111487, '10.1.1.8': 95113, '10.1.1.9': 84698, '10.1.1.10': 100871}
repls:170 s:8101.678949452391
{'10.1.1.1': 87740, '10.1.1.2': 99516, '10.1.1.3': 104017, '10.1.1.4': 111749, '10.1.1.5': 102064, '10.1.1.6': 99504, '10.1.1.7': 113481, '10.1.1.8': 92604, '10.1.1.9': 89092, '10.1.1.10': 100233}
repls:180 s:8152.914742593595
{'10.1.1.1': 89798, '10.1.1.2': 102824, '10.1.1.3': 106469, '10.1.1.4': 109968, '10.1.1.5': 102730, '10.1.1.6': 97682, '10.1.1.7': 109282, '10.1.1.8': 89975, '10.1.1.9': 91959, '10.1.1.10': 99313}
repls:190 s:7196.364276494069
{'10.1.1.1': 90230, '10.1.1.2': 102888, '10.1.1.3': 103218, '10.1.1.4': 108327, '10.1.1.5': 106066, '10.1.1.6': 98406, '10.1.1.7': 109300, '10.1.1.8': 89672, '10.1.1.9': 94761, '10.1.1.10': 97132}
repls:200 s:6720.529874942898
{'10.1.1.1': 88783, '10.1.1.2': 101227, '10.1.1.3': 108627, '10.1.1.4': 108440, '10.1.1.5': 109989, '10.1.1.6': 97889, '10.1.1.7': 107953, '10.1.1.8': 88987, '10.1.1.9': 91711, '10.1.1.10': 96394}
repls:210 s:8021.651475849596
{'10.1.1.1': 88060, '10.1.1.2': 100883, '10.1.1.3': 112140, '10.1.1.4': 106016, '10.1.1.5': 109863, '10.1.1.6': 95733, '10.1.1.7': 106590, '10.1.1.8': 90449, '10.1.1.9': 93294, '10.1.1.10': 96972}
repls:220 s:7944.747472387024
{'10.1.1.1': 87107, '10.1.1.2': 101884, '10.1.1.3': 109795, '10.1.1.4': 107034, '10.1.1.5': 111907, '10.1.1.6': 95074, '10.1.1.7': 102667, '10.1.1.8': 92717, '10.1.1.9': 96867, '10.1.1.10': 94948}
repls:230 s:7594.297742385401
{'10.1.1.1': 88651, '10.1.1.2': 101163, '10.1.1.3': 111115, '10.1.1.4': 107329, '10.1.1.5': 111013, '10.1.1.6': 94798, '10.1.1.7': 102190, '10.1.1.8': 92515, '10.1.1.9': 94313, '10.1.1.10': 96913}
repls:240 s:7472.949029666936
{'10.1.1.1': 88753, '10.1.1.2': 101837, '10.1.1.3': 111291, '10.1.1.4': 107898, '10.1.1.5': 107261, '10.1.1.6': 94112, '10.1.1.7': 100073, '10.1.1.8': 94151, '10.1.1.9': 95524, '10.1.1.10': 99100}
repls:250 s:6798.426538545518
{'10.1.1.1': 91360, '10.1.1.2': 101759, '10.1.1.3': 108332, '10.1.1.4': 108535, '10.1.1.5': 106954, '10.1.1.6': 91781, '10.1.1.7': 97927, '10.1.1.8': 97599, '10.1.1.9': 96718, '10.1.1.10': 99035}
repls:260 s:5980.694658649612
{'10.1.1.1': 94335, '10.1.1.2': 101111, '10.1.1.3': 107718, '10.1.1.4': 108192, '10.1.1.5': 102771, '10.1.1.6': 95312, '10.1.1.7': 97253, '10.1.1.8': 100455, '10.1.1.9': 96858, '10.1.1.10': 95995}
repls:270 s:4725.716263171118
{'10.1.1.1': 92362, '10.1.1.2': 104268, '10.1.1.3': 110370, '10.1.1.4': 104433, '10.1.1.5': 102467, '10.1.1.6': 99100, '10.1.1.7': 97174, '10.1.1.8': 98333, '10.1.1.9': 96784, '10.1.1.10': 94709}
repls:280 s:5096.487496305666
{'10.1.1.1': 93287, '10.1.1.2': 102882, '10.1.1.3': 111219, '10.1.1.4': 104439, '10.1.1.5': 98836, '10.1.1.6': 96338, '10.1.1.7': 99413, '10.1.1.8': 102122, '10.1.1.9': 95564, '10.1.1.10': 95900}    
repls:290 s:5050.164987403877
{'10.1.1.1': 94586, '10.1.1.2': 99228, '10.1.1.3': 111053, '10.1.1.4': 104231, '10.1.1.5': 97920, '10.1.1.6': 98168, '10.1.1.7': 100665, '10.1.1.8': 102873, '10.1.1.9': 96447, '10.1.1.10': 94829}    
repls:300 s:4750.995453586543
{'10.1.1.1': 95274, '10.1.1.2': 101512, '10.1.1.3': 111071, '10.1.1.4': 102185, '10.1.1.5': 96639, '10.1.1.6': 99231, '10.1.1.7': 99691, '10.1.1.8': 102446, '10.1.1.9': 98180, '10.1.1.10': 93771}    
repls:310 s:4604.795391762809
{'10.1.1.1': 97880, '10.1.1.2': 104291, '10.1.1.3': 106787, '10.1.1.4': 100839, '10.1.1.5': 96088, '10.1.1.6': 99459, '10.1.1.7': 101433, '10.1.1.8': 100446, '10.1.1.9': 98111, '10.1.1.10': 94666}   
repls:320 s:3457.5002241503907
{'10.1.1.1': 98267, '10.1.1.2': 104615, '10.1.1.3': 107422, '10.1.1.4': 100355, '10.1.1.5': 96200, '10.1.1.6': 99013, '10.1.1.7': 100644, '10.1.1.8': 101803, '10.1.1.9': 97974, '10.1.1.10': 93707}   
repls:330 s:3772.2653936328497
{'10.1.1.1': 99585, '10.1.1.2': 102525, '10.1.1.3': 107589, '10.1.1.4': 99486, '10.1.1.5': 96681, '10.1.1.6': 98887, '10.1.1.7': 101709, '10.1.1.8': 100174, '10.1.1.9': 98145, '10.1.1.10': 95219}    
repls:340 s:3254.3730579022435
{'10.1.1.1': 96699, '10.1.1.2': 102481, '10.1.1.3': 108301, '10.1.1.4': 101180, '10.1.1.5': 99057, '10.1.1.6': 97453, '10.1.1.7': 100970, '10.1.1.8': 99747, '10.1.1.9': 97993, '10.1.1.10': 96119}    
repls:350 s:3388.547476427031
{'10.1.1.1': 96450, '10.1.1.2': 102574, '10.1.1.3': 105087, '10.1.1.4': 102911, '10.1.1.5': 98838, '10.1.1.6': 97023, '10.1.1.7': 100424, '10.1.1.8': 100164, '10.1.1.9': 99243, '10.1.1.10': 97286}   
repls:360 s:2682.1214737591586
{'10.1.1.1': 94082, '10.1.1.2': 103012, '10.1.1.3': 105869, '10.1.1.4': 101738, '10.1.1.5': 98465, '10.1.1.6': 99058, '10.1.1.7': 101929, '10.1.1.8': 96982, '10.1.1.9': 100143, '10.1.1.10': 98722}   
repls:370 s:3150.9896857971466
{'10.1.1.1': 94393, '10.1.1.2': 103231, '10.1.1.3': 106797, '10.1.1.4': 102009, '10.1.1.5': 100109, '10.1.1.6': 99183, '10.1.1.7': 100898, '10.1.1.8': 96818, '10.1.1.9': 97981, '10.1.1.10': 98581}   
repls:380 s:3313.8183414303203
{'10.1.1.1': 94732, '10.1.1.2': 102332, '10.1.1.3': 105133, '10.1.1.4': 101220, '10.1.1.5': 98638, '10.1.1.6': 101655, '10.1.1.7': 103341, '10.1.1.8': 96690, '10.1.1.9': 97637, '10.1.1.10': 98622}   
repls:390 s:3085.793901089313
{'10.1.1.1': 93613, '10.1.1.2': 100909, '10.1.1.3': 104684, '10.1.1.4': 101282, '10.1.1.5': 99522, '10.1.1.6': 101392, '10.1.1.7': 104469, '10.1.1.8': 97123, '10.1.1.9': 98060, '10.1.1.10': 98946}   
repls:400 s:3170.065993003931
﻿
﻿
标准差最小的虚拟节点数是360
结果和老师的150到200之间不一样，不知道是否为hash算法不同导致
发布于: 2020 年 07 月 06 日阅读数: 36
chengjing

 关注
程靖 2018.06.06 加入
还未添加个人简介
发布
暂无评论