写点什么

wee5 技术选型(一) 作业

用户头像
杨斌
关注
发布于: 2020 年 11 月 22 日

5.6 第五周课后练习

作业一(2 选 1):

  1. 用你熟悉的编程语言实现一致性 hash 算法。

  2. 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

作业二:

根据当周学习情况,完成一篇学习总结


"""对一致性hash进行学习,构造没有vnode的hash,增加和删除节点以进行观察,会产生对应的雪崩效应"""from zlib import crc32 class conhashnorep(object):    def __init__(self,nodes=None,replicas=5):        """此处nodes代表需要初始化的node列表,为进行对比先提供虚拟节点副本数,ring是存储hash-node的字典,key是存储所有hash值的列表"""        self.nodes=nodes        self.replicas=replicas        self.ring={}        self._sorted_keys=[]        self.add_nodes(nodes)     def _add_node(self,node):        for i in range(self.replicas):            bnode="%s_vnode%s" % (node,i)            bnode = bytes(bnode, encoding="utf8")            nodehash = abs(crc32(bnode))            self.ring[nodehash] = node            self._sorted_keys.append(nodehash)        self._sorted_keys.sort()     def add_nodes(self,nodes):        if nodes:            for node in nodes:                self._add_node(node)     def remove_nodes(self,nodes):        """对于remove的操作,如果直接操作已经产生的ring字典,会比较麻烦,因为ring是{hashnode:node}的键值对形式,        直接处理涉及到字典直接查找值ring.values()/ring.keys(),以及通过值来remove(key)的操作,太麻烦"""        if nodes:            for node in nodes:                for i in range(self.replicas):                    bnode = "%s_vnode%s" % (node, i)                    bnode = bytes(bnode, encoding="utf8")                    nodehash = abs(crc32(bnode))                    del self.ring[nodehash]                    self._sorted_keys.remove(nodehash)     def get_node(self,key):        bkey=bytes(key,encoding="utf8")        keyhash=abs(crc32(bkey))        i=0        for nodehash in self._sorted_keys:            i += 1            if keyhash < nodehash:                #print("%d Keyhash:%s Nodehash:%s" % (i,keyhash,nodehash))                return self.ring[nodehash]            else:                continue        if i==len(self._sorted_keys):            #print("None Keyhash:%s Nodehash:%s" % (keyhash,self._sorted_keys[0]))            return  self.ring[self._sorted_keys[0]]     def count_server(self,number):        '''server_list用于存放重复出现的server,server_counnt用于统计出现频数'''        server_list = []        server_count = {}        for i in range(number):            kei = "key_%s" % i            server = self.get_node(kei)            server_list.append(server)        for m in set(server_list):            server_count[m] = server_list.count(m)        '''根据字典的键进行排序,如果需要逆序则添加 reverse=True'''        server_count=dict(sorted(server_count.items(), key=lambda e: e[1],reverse=True))        print("ServerCount:", server_count)  ini_servers = [    '127.0.0.1:1',    '127.0.0.1:2',    '127.0.0.1:3',    '127.0.0.1:4',    #'127.0.0.1:7005',]h=conhashnorep(ini_servers)print(h.ring) """构建一些object来观察会分配到哪一个节点"""#for i in range(20):part_servers=['127.0.0.2:1','127.0.0.2:2']h.count_server(200)h.add_nodes(part_servers)h.count_server(200)h.remove_nodes(['127.0.0.1:1','127.0.0.1:2'])h.count_server(200)
复制代码

由于代码功底不深厚,本周作业暂时为复制网络代码进行研究。(python 版本)

"""对一致性hash进行学习,构造没有vnode的hash,增加和删除节点以进行观察,会产生对应的雪崩效应"""from zlib import crc32# import memcached class conhashnorep(object):    def __init__(self,nodes=None):        """此处nodes代表需要初始化的node列表,为进行对比先提供虚拟节点副本数,ring是存储hash-node的字典,key是存储所有hash值的列表"""        self.nodes=nodes        self.ring={}        self._sorted_keys=[]        self.add_nodes(nodes)     def _add_node(self,node):        bnode=bytes(node,encoding="utf8")        nodehash=abs(crc32(bnode))        self.ring[nodehash]=node        self._sorted_keys.append(nodehash)        self._sorted_keys.sort()     def add_nodes(self,nodes):        if nodes:            for node in nodes:                self._add_node(node)     def remove_nodes(self,nodes):        """对于remove的操作,如果直接操作已经产生的ring字典,会比较麻烦,因为ring是{hashnode:node}的键值对形式,        直接处理涉及到字典直接查找值ring.values()/ring.keys(),以及通过值来remove(key)的操作,太麻烦"""        if nodes:            for node in nodes:                bnode = bytes(node, encoding="utf8")                nodehash = abs(crc32(bnode))                del self.ring[nodehash]                self._sorted_keys.remove(nodehash)     def get_node(self,key):        bkey=bytes(key,encoding="utf8")        keyhash=abs(crc32(bkey))        i=0        for nodehash in self._sorted_keys:            i += 1            if keyhash < nodehash:                #print("%d Keyhash:%s Nodehash:%s" % (i,keyhash,nodehash))                return self.ring[nodehash]            else:                continue        if i==len(self._sorted_keys):            #print("None Keyhash:%s Nodehash:%s" % (keyhash,self._sorted_keys[0]))            return  self.ring[self._sorted_keys[0]]     def count_server(self,number):        '''server_list用于存放重复出现的server,server_counnt用于统计出现频数'''        server_list = []        server_count = {}        for i in range(number):            kei = "key_%s" % i            server = self.get_node(kei)            server_list.append(server)        for m in set(server_list):            server_count[m] = server_list.count(m)        '''根据字典的键进行排序,如果需要逆序则添加 reverse=True'''        server_count=dict(sorted(server_count.items(), key=lambda e: e[0]))        print("ServerCount:", server_count)  ini_servers = [    '127.0.0.1:1',    '127.0.0.1:2',    '127.0.0.1:3',    '127.0.0.1:4',    #'127.0.0.1:7005',]h=conhashnorep(ini_servers)print(h.ring) """构建一些object来观察会分配到哪一个节点"""#for i in range(20):part_servers=['127.0.0.2:1','127.0.0.2:2']h.count_server(200)h.add_nodes(part_servers)h.count_server(200)h.remove_nodes(['127.0.0.1:1','127.0.0.1:2'])h.count_server(200)
复制代码


用户头像

杨斌

关注

还未添加个人签名 2020.03.17 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
实际测试的结果可以看看偏差,参数调整就有基础了
2020 年 11 月 29 日 10:37
回复
没有更多了
wee5 技术选型(一) 作业