hash一致性算法的Python实现

田田田

• 附上一段生动讲解hash一致性算法的小视频：
• http://m.v.qq.com/play/play.html?coverid=&vid=c05301hihcc&vuid24=OVAcOuIRZriOZ6Thl2Ge3Q%3D%3D&ptag=2_7.6.0.20170_wxf

实现思路

• 环，节点，虚拟节点，需要保存的数据
• 由节点计算出虚拟节点的哈希值，增加节点，删除节点
• 需要保存的数据落到环上顺时针向后寻找存储该数据的节点
• 增加节点：算出增加节点对应的虚拟节点，将每个增加的虚拟节点顺时针的后一个虚拟节点的部分数据存储到增加的虚拟节点上
• 删除节点：将删除的虚拟节点的数据存储到该虚拟节点顺时针的后一个虚拟节点上

代码实现

# coding=utf-8
import hashlib


class Hash_consistency():
    def __init__(self, nodes=None, virtual_node=4):
        """

        :param nodes: 一共有多少个节点
        :param virtual_node: 每个节点有多少个虚拟节点

        """
        self.virtual_node = virtual_node  # 每个节点有几个虚拟节点
        self.node_dict = dict()  # 用于将虚拟节点的hash值与node的对应关系
        self.virtual_ring = []  # 用于存放所有的虚拟节点的hash值，这里需要保持排序
        if nodes:
            for node in nodes:
                self.add_node(node)

    def add_node(self, node):
        """
        添加node节点，首先要根据虚拟节点的数目，计算出节点的虚拟节点，将node节点与4个虚拟节点对应
        将虚拟节点的hash值存在virtual_ring[]中，保持排序

        :param node:
        :return:
        """
        for i in xrange(0, self.virtual_node):
            key = self.get_key(node)
            self.node_dict['node'] = key
            self.virtual_ring.append(key)

        self.virtual_ring.sort()

    def remove_node(self, node):
        """
        删除node节点的所有虚拟节点
        首先根据node_dict中节点与虚拟节点的对应关系，找到虚拟节点
        将虚拟节点的所有数据根据virtual_ring，找到下一个虚拟节点，并存储在这个找到的虚拟节点上
        删除所有的虚拟节点
        :param node:
        :return:
        """
        for i in xrange(0, self.virtual_node):
            key = self.get_key(node)
            self.node_dict[node] = 0  #没有真正删除，只是把key对应的值替换了
            self.virtual_ring.remove(key)

    def get_node(self, str):
        """
        返回这个字符串对应的node，先求出字符串的hash值，然后找到第一个小于等于的虚拟节点，
        然后返回node
        如果hash值大于所有的节点，那么用第一个虚拟节点
        :param :
        :return:
        """

        if self.virtual_ring:
            key = self.get_key(str)
            for node_key in self.virtual_ring:
                if key <= node_key:
                    return self.node_dict[node_key]
                else:
                    return self.virtual_ring[0]
        else:
            return None



    @staticmethod
    def get_key(node):
        key = hashlib.md5(node).hexdigest()
        return long(key, 16)


def main():
    h = Hash_consistency()
    h.add_node("node1")
    print h.get_key("node1")
    print h.get_node("hello")
    print h.virtual_ring
    h.remove_node("node1")
    print h.virtual_ring



if __name__ == '__main__':
    main()

参考

• https://blog.csdn.net/qq_35462323/article/details/85091838

• https://blog.csdn.net/JackLiu16/article/details/83070760