一致性hash算法

# -*-coding:utf8 -*-

import sys
import math
from bisect import bisect

if sys.version_info >= (2, 5):
    import hashlib
    md5_constructor = hashlib.md5
else:
    import md5
    md5_constructor = md5.new


class HashRing(object):

    def __init__(self, nodes=None):

        # 最终生成的环 格式为: {key:node}
        self._ring = dict()
        # 最终生成的keys
        self._sorted_keys = []
        self.nodes = []

        total_weight = 0
        for node, weight in nodes.items():
            self.nodes.append(node)
            total_weight += weight

        # 给node生成对应的key
        for node in self.nodes:
            weight = nodes.get(node, 1)

            # 权重因子，意味着某个node会有些虚拟节点
            factor = math.floor(40 * len(self.nodes) * weight / total_weight)

            for i in range(int(factor)):
                # 拿到了key为'%s-%s' % (node, i)的种子数据
                hash_seed = self._hash_digest('%s-%s' % (node, i))
                has_key = self._hash_val(hash_seed)
                self._ring[has_key] = node
                self._sorted_keys.append(has_key)

        # 排序
        self._sorted_keys.sort()

    def get_node(self, key):

        if not self._ring:
            return None

        pos = self.get_node_pos(key)

        if pos is None:
            return None

        return self._ring[self._sorted_keys[pos]]

    def get_node_pos(self, key):
        key = self.gen_key(key)

        pos = bisect(self._sorted_keys, key)

        # 如果是最大的值，那么则落到第一位
        if len(self._sorted_keys) == pos:
            return 0

        return pos

    def gen_key(self, key):
        b_key = self._hash_digest(key)
        return self._hash_val(b_key)

    def _hash_val(self, b_key):

        """
            左移动是地位补0 例如 10 左移2位后 1000
            当一个数左移24数，这个数肯定在 2^24 到z^32之间
            当一个数左移16数，这个数肯定在 2^32 到z^24之间
            求 "|"运算后，最终这个数字就是在0 - 2^32之间
        """
        return ((b_key[3] << 24) | (b_key[2] << 16) | (b_key[1] << 8) | b_key[0]) # noqa

    def _hash_digest(self, key):
        """
            使用md5生成一个数组，长度为16，取数组里面的数字用于计算2^32位的值
        """
        m = md5_constructor()
        m.update(str(key))
        return list(map(ord, str(m.digest())))

if __name__ == "__main__":
    memcache_servers = {'192.168.0.246:11212': 1,
                        '192.168.0.247:11212': 2,
                        '192.168.0.249:11212': 3}

    ring = HashRing(memcache_servers)
    server = ring.get_node('my_key')

    print server