架构师训练营 -W05H- 技术选型

 关注
发布于: 2020 年 07 月 08 日
一、用你熟悉的编程语言实现一致性 hash 算法。二、编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。0 综述一致性哈希算法可以解决取模哈希算法存在的节点扩容、节点宕机所带来的问题。而在一致性哈希中引入虚拟节点则可以进一步解决一致性哈希数据分布不均所带来的平衡性问题。
1 代码
# -*- coding: utf-8 -*-
import hashlib, random, string
import numpy as np
content_list = []
# 随机生成1000000个四位字符串用于模拟key值进行测试
for i in range(10**7):
    ran_str = ''.join(random.sample(string.ascii_letters + string.digits, 4))
    content_list.append(ran_str)
# 设置10个服务器节点
servers = [
    "10.10.1.1",
    "10.10.2.2",
    "10.10.3.3",
    "10.10.4.4",
    "10.10.5.5",
    "10.10.6.6",
    "10.10.7.7",
    "10.10.8.8",
    "10.10.9.9",
    "10.10.10.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
        for i in range(len(nodes)):
            node = nodes[i]
            if key < node:
                return self.ring[node], i
        # 如果key > node，那么让这些key落在第一个node上就形成了闭环
        return self.ring[nodes[0]], 0
    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 consistent_hash(replicas):
    hr = HashRing(servers, replicas)
    database = {s: [] for s in servers}
    for w in content_list:
        database[hr.get_node(w)].append(w)
        
    # print(f"words={len(words)}\n")
    arr = []
    # 输出每个节点分配的数量
    for node, result in database.items():
        print(f"{node}={len(result)}")
        arr.append(len(result))
    # 输出标准差
    print("标准差为："+str(np.std(arr)))
if __name__ == '__main__':
    consistent_hash(100)
2 虚拟节点数量取值为10虚拟节点数量取值为10
if __name__ == '__main__':
    consistent_hash(10)
各个节点分布数量及方差为：
10.10.1.1=778754
10.10.2.2=1252246
10.10.3.3=779964
10.10.4.4=859953
10.10.5.5=497710
10.10.6.6=1169519
10.10.7.7=1183569
10.10.8.8=934595
10.10.9.9=1903379
10.10.10.10=640311
标准差为：400705.483719513
3 虚拟节点数量取值为50虚拟节点数量取值为50
if __name__ == '__main__':
    consistent_hash(50)
各个节点分布数量及方差为：
10.10.1.1=1079221
10.10.2.2=887621
10.10.3.3=886714
10.10.4.4=1163828
10.10.5.5=965582
10.10.6.6=905657
10.10.7.7=926407
10.10.8.8=1103610
10.10.9.9=916214
10.10.10.10=1165146
标准差为：109136.51776376228
4 虚拟节点数量取值为100虚拟节点数量为100
if __name__ == '__main__':
    consistent_hash(100)
各个节点分布数量及方差为：
10.10.1.1=849611
10.10.2.2=1001792
10.10.3.3=1070862
10.10.4.4=1045488
10.10.5.5=960455
10.10.6.6=1019524
10.10.7.7=1084869
10.10.8.8=1079950
10.10.9.9=925496
10.10.10.10=961953
标准差为：72283.33643378672
5 虚拟节点数量取值为150虚拟节点数量为150
if __name__ == '__main__':
    consistent_hash(150)
各个节点分布数量及方差为：
10.10.1.1=1021580
10.10.2.2=979081
10.10.3.3=1051096
10.10.4.4=1068364
10.10.5.5=879120
10.10.6.6=1020055
10.10.7.7=1053379
10.10.8.8=926859
10.10.9.9=1023711
10.10.10.10=976755
标准差为：57011.73665658677
6 虚拟节点数量取值为200虚拟节点数量为150
if __name__ == '__main__':
    consistent_hash(200)
各个节点分布数量及方差为：
10.10.1.1=1049361
10.10.2.2=1016194
10.10.3.3=1091307
10.10.4.4=1047162
10.10.5.5=999778
10.10.6.6=936990
10.10.7.7=915324
10.10.8.8=1003240
10.10.9.9=966132
10.10.10.10=974512
标准差为：51193.249533507835
﻿
7 结论随着虚拟节点数量的不断增加，标准方差逐渐递减，且虚拟节点取到150和200的时候标准方差基本相同。
8 参考https://reishin.me/python-consistent-hash/#取模-hash
﻿
发布于: 2020 年 07 月 08 日阅读数: 34
BlazeLuLu

 关注
还未添加个人签名 2018.05.30 加入
还未添加个人简介
发布
暂无评论