写点什么

Consistent Hash

用户头像
韩向民
关注
发布于: 2020 年 10 月 24 日



# -*- coding: utf-8 -*-
import hashlib
import math
class YiZhiHash(object):
    def __init__(self, nodes=None, n_number=3):
        """
        :param nodes:           所有的节点
        :param n_number:        一个节点对应多少个虚拟节点
        :return:
        """
        self._n_number = n_number   #每一个节点对应多少个虚拟节点,这里默认是3个
        self._node_dict = dict()    #用于将虚拟节点的hash值与node的对应关系
        self._sort_list = []        #用于存放所有的虚拟节点的hash值,这里需要保持排序
        self._access_times = {}
        if nodes:
            for node in nodes:
                self.add_node(node)
    def add_node(self, node):
        """
        添加node,首先要根据虚拟节点的数目,创建所有的虚拟节点,并将其与对应的node对应起来
        当然还需要将虚拟节点的hash值放到排序的里面
        这里在添加了节点之后,需要保持虚拟节点hash值的顺序
        :param node:
        :return:
        """
        for i in range(self._n_number):
            node_str = "%s_%s" % (node, i)
            key = self._gen_key(node_str)
            self._node_dict[key] = node
            self._sort_list.append(key)
        self._sort_list.sort()
    def remove_node(self, node):
        """
        这里一个节点的退出,需要将这个节点的所有的虚拟节点都删除
        :param node:
        :return:
        """
        for i in range(self._n_number):
            node_str = "%s_%s" % (node, i)
            key = self._gen_key(node_str)
            del self._node_dict[key]
            self._sort_list.remove(key)
    def get_node(self, key_str):
        """
        返回这个字符串应该对应的node,这里先求出字符串的hash值,然后找到第一个小于等于的虚拟节点,然后返回node
        如果hash值大于所有的节点,那么用第一个虚拟节点
        :param :
        :return:
        """
        if self._sort_list:
            key = self._gen_key(key_str)
            for node_key in self._sort_list:
                if key <= node_key:
                    access_key = self._node_dict[node_key]
                    access_val = self._access_times.get(access_key, 0)
                    access_val += 1
                    self._access_times[access_key] = access_val
                    return self._node_dict[node_key]
            return self._node_dict[self._sort_list[0]]
        else:
            return None
        
    def print(self):
        print("show the server with hash")
        for k, v in self._access_times.items():
            print("The node {} access hit times: {}".format(k, v))
            
    def get_access_deviation(self):
        access_times_avg = 0
        access_times_sum = 0
        access_times_deviation = None
        len_access_times = len(self._access_times)
        for k, v in self._access_times.items():
            access_times_sum += v
        access_times_avg = access_times_sum / len_access_times
        
        total_square_substraction = 0
        for k, v in self._access_times.items():
            total_square_substraction += (v - access_times_avg)**2
            
        access_times_deviation = math.sqrt(total_square_substraction/len_access_times)
        return access_times_deviation
    @staticmethod
    def _gen_key(key_str):
        """
        通过key,返回当前key的hash值,这里采用md5
        :param key:
        :return:
        """
        md5_str = hashlib.md5(key_str.encode('utf-8')).hexdigest()
        return int(md5_str, 16)
yzhash = YiZhiHash(["192.168.1.1""192.168.1.2""192.168.1.3""192.168.1.4""192.168.1.5",
             "192.168.1.6""192.168.1.7""192.168.1.8""192.168.1.9""192.168.1.10"
             ])
if __name__ == "__main__":
    SERVER_NODES = [
        "192.168.1.1""192.168.1.2""192.168.1.3""192.168.1.4""192.168.1.5",
        "192.168.1.6""192.168.1.7""192.168.1.8""192.168.1.9""192.168.1.10"
    ]   
    server_nodes_with_hash = YiZhiHash(SERVER_NODES, n_number=100)
    # 访问1000000个不同的数据
    for k in range(1000000):
        print("Access {} from node {}".format(k, server_nodes_with_hash.get_node(str(k))))
    print("access deviation is {}".format(server_nodes_with_hash.get_access_deviation()))
# 访问1000000个不同的数据,测试访问的节点访问可能性的方差



一致性hash,为节点增加虚拟节点,记录访问时节点命中的次数,再对服务器节点进行数据统计得到访问的方差。

用户头像

韩向民

关注

还未添加个人签名 2018.11.15 加入

还未添加个人简介

评论

发布
暂无评论
Consistent Hash