程序员小灰-漫画：什么是一致性哈希？
一年之前——
未来两年内，系统预估的总订单数量可达一亿条左右。
按Mysql单表存储500万条记录来算，暂时不必分库，单库30个分表是比较合适的水平分表方案。
于是小灰设计了这样的分表逻辑：
- 订单表创建单库30个分表
- 对用户ID和30进行取模，取模结果决定了记录存于第几个分表
- 查询时需要以用户ID作为条件，根据取模结果确定查询哪一个分表
分表方式如下图（为了便于描述，简化为5个分表）：
过了两个月——
又过了半年多——
小灰的回忆告一段落——
1.首先，我们把全量的缓存空间当做一个环形存储结构。环形空间总共分成2^32个缓存区，在Redis中则是把缓存key分配到16384个slot。
2.每一个缓存key都可以通过Hash算法转化为一个32位的二进制数，也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。
3.我们的每一个缓存节点（Shard）也遵循同样的Hash算法，比如利用IP做Hash，映射到环形空间当中。
4.如何让key和节点对应起来呢？很简单，每一个key的顺时针方向最近节点，就是key所归属的存储节点。所以图中key1存储于node1，key2，key3存储于node2，key4存储于node3。
1.增加节点
当缓存集群的节点有所增加的时候，整个环形空间的映射仍然会保持一致性哈希的顺时针规则，所以有一小部分key的归属会受到影响。
有哪些key会受到影响呢？图中加入了新节点node4，处于node1和node2之间，按照顺时针规则，从node1到node4之间的缓存不再归属于node2，而是归属于新节点node4。因此受影响的key只有key2。
最终把key2的缓存数据从node2迁移到node4，就形成了新的符合一致性哈希规则的缓存结构。
2.删除节点
当缓存集群的节点需要删除的时候（比如节点挂掉），整个环形空间的映射同样会保持一致性哈希的顺时针规则，同样有一小部分key的归属会受到影响。
有哪些key会受到影响呢？图中删除了原节点node3，按照顺时针规则，原本node3所拥有的缓存数据就需要“托付”给node3的顺时针后继节点node1。因此受影响的key只有key4。
最终把key4的缓存数据从node3迁移到node1，就形成了新的符合一致性哈希规则的缓存结构。
如上图所示，假如node1的ip是192.168.1.109，那么原node1节点在环形空间的位置就是hash（“192.168.1.109”）。
我们基于node1构建两个虚拟节点，node1-1 和 node1-2，虚拟节点在环形空间的位置可以利用（IP+后缀）计算，例如：
hash（“192.168.1.109#1”），hash（“192.168.1.109#2”）
此时，环形空间中不再有物理节点node1，node2，只有虚拟节点node1-1，node1-2，node2-1，node2-2。由于虚拟节点数量较多，缓存key与虚拟节点的映射关系也变得相对均衡了。
实例讲解
一致性哈希算法，作为分布式计算的数据分配参考，比传统的取模，划段都好很多。
在电信计费中，可以作为多台消息接口机和在线计费主机的分配算法，根据session_id来分配，这样当计费主机动态伸缩的时候，因为session_id缓存缺失而需要放通的会话，会明显减少。
传统的取模方式
例如10条数据，3个节点，如果按照取模的方式，那就是
node a: 0,3,6,9
node b: 1,4,7
node c: 2,5,8
当增加一个节点的时候，数据分布就变更为
node a:0,4,8
node b:1,5,9
node c: 2,6
node d: 3,7
总结：数据3,4,5,6,7,8,9在增加节点的时候，都需要做搬迁，成本太高
一致性哈希方式
最关键的区别就是，对节点和数据，都做一次哈希运算，然后比较节点和数据的哈希值，数据取和节点最相近的节点做为存放节点。这样就保证当节点增加或者减少的时候，影响的数据最少。
还是拿刚刚的例子，（用简单的字符串的ascii码做哈希key）：
十条数据，算出各自的哈希值
0：192
1：196
2：200
3：204
4：208
5：212
6：216
7：220
8：224
9：228
有三个节点，算出各自的哈希值
node a: 203
node g: 209
node z: 228
这个时候比较两者的哈希值，如果大于228，就归到前面的203，相当于整个哈希值就是一个环，对应的映射结果：
node a: 0,1,2
node g: 3,4
node z: 5,6,7,8,9
这个时候加入node n, 就可以算出node n的哈希值：
node n: 216
这个时候对应的数据就会做迁移：
node a: 0,1,2
node g: 3,4
node n: 5,6
node z: 7,8,9
这个时候只有5和6需要做迁移
另外，这个时候如果只算出三个哈希值，那再跟数据的哈希值比较的时候，很容易分得不均衡，因此就引入了虚拟节点的概念，通过把三个节点加上ID后缀等方式，每个节点算出n个哈希值，均匀的放在哈希环上，这样对于数据算出的哈希值，能够比较散列的分布（详见下面代码中的replica）
通过这种算法做数据分布，在增减节点的时候，可以大大减少数据的迁移规模。
下面转载的哈希代码，已经将gen_key改成上述描述的用字符串ascii相加的方式，便于测试验证。
import md5
class HashRing(object):
def __init__(self, nodes=None, replicas=3):
"""Manages a hash ring.
`nodes` is a list of objects that have a proper __str__ representation.
`replicas` indicates how many virtual points should be used pr. node,
replicas are required to improve the distribution.
"""
self.replicas = replicas
self.ring = dict()
self._sorted_keys = []
if nodes:
for node in nodes:
self.add_node(node)
def add_node(self, node):
"""Adds a `node` to the hash ring (including a number of replicas).
"""
for i in xrange(0, self.replicas):
key = self.gen_key('%s:%s' % (node, i))
print "node %s-%s key is %ld" % (node, i, key)
self.ring[key] = node
self._sorted_keys.append(key)
self._sorted_keys.sort()
def remove_node(self, node):
"""Removes `node` from the hash ring and its replicas.
"""
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):
"""Given a string key a corresponding node in the hash ring is returned.
If the hash ring is empty, `None` is returned.
"""
return self.get_node_pos(string_key)[0]
def get_node_pos(self, string_key):
"""Given a string key a corresponding node in the hash ring is returned
along with it's position in the ring.
If the hash ring is empty, (`None`, `None`) is returned.
"""
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:
print "string_key %s key %ld" % (string_key, key)
print "get node %s-%d " % (self.ring[node], i)
return self.ring[node], i
return self.ring[nodes[0]], 0
def print_ring(self):
if not self.ring:
return None, None
nodes = self._sorted_keys
for i in xrange(0, len(nodes)):
node = nodes[i]
print "ring slot %d is node %s, hash vale is %s" % (i, self.ring[node], node)
def get_nodes(self, string_key):
"""Given a string key it returns the nodes as a generator that can hold the key.
The generator is never ending and iterates through the ring
starting at the correct position.
"""
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):
"""Given a string key it returns a long value,
this long value represents a place on the hash ring.
md5 is currently used because it mixes well.
"""
m = md5.new()
m.update(key)
return long(m.hexdigest(), 16)
"""
hash = 0
for i in xrange(0, len(key)):
hash += ord(key[i])
return hash
"""
memcache_servers = ['a',
'g',
'z']
ring = HashRing(memcache_servers,1)
ring.print_ring()
server = ring.get_node('0000')
server = ring.get_node('1111')
server = ring.get_node('2222')
server = ring.get_node('3333')
server = ring.get_node('4444')
server = ring.get_node('5555')
server = ring.get_node('6666')
server = ring.get_node('7777')
server = ring.get_node('8888')
server = ring.get_node('9999')
print '----------------------------------------------------------'
memcache_servers = ['a',
'g',
'n',
'z']
ring = HashRing(memcache_servers,1)
ring.print_ring()
server = ring.get_node('0000')
server = ring.get_node('1111')
server = ring.get_node('2222')
server = ring.get_node('3333')
server = ring.get_node('4444')
server = ring.get_node('5555')
server = ring.get_node('6666')
server = ring.get_node('7777')
server = ring.get_node('8888')
server = ring.get_node('9999')