hash_ring 源码分析(Python)

2011-12-30

consistent hash 算法论文: <http://www8.org/w8-papers/2a- webserver/caching/paper2.html> 源代码下载: hash_ring-1.2.tar.gz 了解 hash_ring 的源代码, 主要是想用到 redis 上去. 可能开源的已经有实现, 不过自己还是想深入学习下. 而且也没几行代码, 就搞定他把. 哈哈 看 python 主要语法简介, c/c++ 可能 看的类死, 最后 算法一样. 构造方法,主要定义 ring 字典, nodes 和 nodes 的权值

    def __init__(self, nodes=None, weights=None):
        self.ring = dict()
        self._sorted_keys = []
        self.nodes = nodes
        if not weights:
            weights = {}
        self.weights = weights
        self._generate_circle()

_generate_circle 方法 生成一个 ring:

    def _generate_circle(self):
        total_weight = 0 #默认 total_weight 为 0 

        for node in self.nodes:  计算 total_weight,
            total_weight += self.weights.get(node, 1)

        for node in self.nodes:  #为每个 node 设置默认 weight, (个人感觉这段代码有点多余)
            weight = 1

            if node in self.weights: #给每个 node 设置 weight
                weight = self.weights.get(node)

            #得到 node factor 的具体算法 
            factor = math.floor((40*len(self.nodes)*weight) / total_weight);

            获得每个 node key. 这里用 xrang 而不用 rang 主要是 xrang 返回是一个 String, rang 返回一个 list. 并且, xrange 性能比 range 高很多 
            for j in xrange(0, int(factor)):
                b_key = self._hash_digest( '%s-%s' % (node, j) )

                for i in xrange(0, 3):
                    key = self._hash_val(b_key, lambda x: x+i*4)
                    self.ring[key] = node
                    self._sorted_keys.append(key)

        self._sorted_keys.sort()

get_node 获得 node

    def get_node(self, string_key):
        pos = self.get_node_pos(string_key) #获得 node position
        if pos is None:
            return None
        return self.ring[ self._sorted_keys[pos] ]

get_node_pos 获得 node pos

    def get_node_pos(self, string_key):
        if not self.ring:
            return None
        key = self.gen_key(string_key) # 生成 key
        nodes = self._sorted_keys  
        pos = bisect(nodes, key)  # 使用 bisect 对 nodes 排序
        if pos == len(nodes):
            return 0
        else:
            return pos

iterate_nodes 方法迭代 nodes

    def iterate_nodes(self, string_key, distinct=True):
        if not self.ring:
            yield None, None

        returned_values = set()
        def distinct_filter(value):  #对 node key 去重, (我到觉得可以使用 reduce 函数去做)
            if str(value) not in returned_values:
                returned_values.add(str(value))
                return value

        pos = self.get_node_pos(string_key)  #获得 node position
        for key in self._sorted_keys[pos:]:  #通过 distinct_filter 对 ring 中的 node 去重复. 并通过 生成器迭代
            val = distinct_filter(self.ring[key])
            if val:
                yield val

        for i, key in enumerate(self._sorted_keys): #通过 enumerate 枚举迭代出 index, 和 vlaue 
            if i < pos:
                val = distinct_filter(self.ring[key])
                if val:
                    yield val

生成 hash_key , 下面就是 一些 hash md5 的生成方法 不详细说了.

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

    def _hash_val(self, b_key, entry_fn):
        return (( b_key[entry_fn(3)] << 24)
                |(b_key[entry_fn(2)] << 16)
                |(b_key[entry_fn(1)] << 8)
                | b_key[entry_fn(0)] )

    def _hash_digest(self, key):
        m = md5.new()
        m.update(key)
        return map(ord, m.digest())