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())