import md5
class HashRing(object):
    def __init__(self, nodes=None, replicas=10):        """生成哈希环.
        `nodes` ：包含实现__str__ 方法的队列.        `replicas` 每个节点生成的虚拟节点, 用于改善分布的随机性        """        self.replicas = replicas
        self.ring = dict()        self._sorted_keys = []
        if nodes:            for node in nodes:                self.add_node(node)
    def add_node(self, node):        """增加一个节点(会按照配置生成虚拟节点数).        """        for i in xrange(0, self.replicas):            key = self.gen_key('%s:%s' % (node, i))            self.ring[key] = node            self._sorted_keys.append(key)
        self._sorted_keys.sort()
    def remove_node(self, node):        """从哈希环中移除节点和对应的虚拟节点.        """        for i in xrange(0, self.replicas):            key = self.gen_key('%s:%s' % (node, i))            del self.ring[key]            self._sorted_keys.remove(key)
    def get_node(self, string_key):        """按照键返回对应分配的节点
        哈希环为空,返回 `None`        """        return self.get_node_pos(string_key)[0]
    def get_node_pos(self, string_key):        """查询节点位置
        哈希环为空,返回 `None`        """        if not self.ring:            return None, None
        key = self.gen_key(string_key)
        nodes = self._sorted_keys        for i in xrange(0, len(nodes)):            node = nodes[i]            if key <= node:                return self.ring[node], i
        return self.ring[nodes[0]], 0
    def get_nodes(self, string_key):        """返回所有节点        """        if not self.ring:            yield None, None
        node, pos = self.get_node_pos(string_key)        for key in self._sorted_keys[pos:]:            yield self.ring[key]
        while True:            for key in self._sorted_keys:                yield self.ring[key]
    def gen_key(self, key):        """生成键        """        m = md5.new()        m.update(key)        return long(m.hexdigest(), 16)