分布式系统（如 memcached 服务器集群）的一个最重要的内容是要保证同一个 key 每次都必须命中同一个服务器，本文介绍两种分布方式：
- 简单hash分布(simple hashing)
- 一致性hash分布(Consistent hashing)
简单hash分布
这个算法很简单：
server = serverlist[hash(key) % len(serverlist)]
python3-memcached 模块就是利用了这种算法。
一致性hash分布
简单 hash 分布算法有一个致命的缺点，就是扩展性和容错性， 当系统加入或减少服务器后， 因为服务器数量被改变，所有 key 值将会被重新映射， 造成整个系统不能高效运行。
一致性 hash 分布通过建立环形 hash 空间和服务器虚拟节点解决了上面的问题，提高了系统的扩展性和容错性。
环形 hash 空间是一个具有一定大小（比如 2^32 次方个值）的空间，其头尾相连，就像一个闭合的环形，如下图：
我们可以通过某种 hash 算法将 key 映射到这个 hash 空间中：
将分布式服务器通过 hash 算法映射到这个 hash 空间中， 此后索引服务器时，根据 key 值绕着这个 hash 空间顺时针方向查询，第一个找到的服务器即为该 key 值对应的服务器：
当删除一个服务器节点时，不会影响其它 key：
当添加一个服务器节点时，只会重定向一段 key：
通过 hash 算法并不能保证服务器均匀的分布在 hash 空间上，然后通过为一个服务器建立多个虚拟节点，进而减少这种不均匀性：
python一致性hash分布算法实现
#!/usr/bin/python
import hashlib
class HashRing(object):
def __init__(self, nodes=None, replicas=3):
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 range(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 range(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):
return self.get_node_pos(string_key)[0]
def get_node_pos(self, string_key):
if not self.ring:
return None, None
key = self.gen_key(string_key)
nodes = self._sorted_keys
for i in range(0, len(nodes)):
node = nodes[i]
if key <= node:
return self.ring[node], i
return self.ring[nodes[0]], 0
def gen_key(self, key):
m = hashlib.md5()
m.update(key.encode())
return int(m.hexdigest(), 16)
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]
if __name__ == '__main__':
memcache_servers = ['192.168.0.246:11212',
'192.168.0.247:11212',
'192.168.0.249:11212']
ring = HashRing(memcache_servers)
server = ring.get_node('node_key')
print(server)
参考：