程序员小灰-漫画：什么是一致性哈希？

川长思鸟来 2023-10-18 09:38 94阅读 0赞

##  ##

![程序员小灰-漫画：什么是一致性哈希？][-]

![程序员小灰-漫画：什么是一致性哈希？][- 1]

![程序员小灰-漫画：什么是一致性哈希？][- 2]

![程序员小灰-漫画：什么是一致性哈希？][- 3]

一年之前——

![程序员小灰-漫画：什么是一致性哈希？][- 4]

![程序员小灰-漫画：什么是一致性哈希？][- 5]

未来两年内，系统预估的总订单数量可达一亿条左右。

按Mysql单表存储500万条记录来算，暂时不必分库，单库30个分表是比较合适的水平分表方案。

于是小灰设计了这样的分表逻辑：

1.  订单表创建单库30个分表
2.  对用户ID和30进行取模，取模结果决定了记录存于第几个分表
3.  查询时需要以用户ID作为条件，根据取模结果确定查询哪一个分表

分表方式如下图（为了便于描述，简化为5个分表）：

![程序员小灰-漫画：什么是一致性哈希？][- 6]

过了两个月——

![程序员小灰-漫画：什么是一致性哈希？][- 7]

![程序员小灰-漫画：什么是一致性哈希？][- 8]

又过了半年多——

![程序员小灰-漫画：什么是一致性哈希？][- 9]

![程序员小灰-漫画：什么是一致性哈希？][- 10]

![程序员小灰-漫画：什么是一致性哈希？][- 11]

![程序员小灰-漫画：什么是一致性哈希？][- 12]

![程序员小灰-漫画：什么是一致性哈希？][- 13]

![程序员小灰-漫画：什么是一致性哈希？][- 14]

![程序员小灰-漫画：什么是一致性哈希？][- 15]

小灰的回忆告一段落——

![程序员小灰-漫画：什么是一致性哈希？][- 16]

![程序员小灰-漫画：什么是一致性哈希？][- 17]

![程序员小灰-漫画：什么是一致性哈希？][- 18]

![程序员小灰-漫画：什么是一致性哈希？][- 19]

![程序员小灰-漫画：什么是一致性哈希？][- 20]

![程序员小灰-漫画：什么是一致性哈希？][- 21]

1.首先，我们把全量的缓存空间当做一个环形存储结构。环形空间总共分成2^32个缓存区，在Redis中则是把缓存key分配到16384个**slot**。

![程序员小灰-漫画：什么是一致性哈希？][- 22]

2.每一个缓存key都可以通过Hash算法转化为一个32位的二进制数，也就对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。

![程序员小灰-漫画：什么是一致性哈希？][- 23]

3.我们的每一个缓存节点（Shard）也遵循同样的Hash算法，比如利用IP做Hash，映射到环形空间当中。

![程序员小灰-漫画：什么是一致性哈希？][- 24]

4.如何让key和节点对应起来呢？很简单，每一个key的顺时针方向最近节点，就是key所归属的存储节点。所以图中key1存储于node1，key2，key3存储于node2，key4存储于node3。

![程序员小灰-漫画：什么是一致性哈希？][- 25]

![程序员小灰-漫画：什么是一致性哈希？][- 26]

![程序员小灰-漫画：什么是一致性哈希？][- 27]

**1.增加节点**

当缓存集群的节点有所增加的时候，整个环形空间的映射仍然会保持一致性哈希的顺时针规则，所以有一小部分key的归属会受到影响。

![程序员小灰-漫画：什么是一致性哈希？][- 28]

有哪些key会受到影响呢？图中加入了新节点node4，处于node1和node2之间，按照顺时针规则，从node1到node4之间的缓存不再归属于node2，而是归属于新节点node4。因此受影响的key只有key2。

![程序员小灰-漫画：什么是一致性哈希？][- 29]

最终把key2的缓存数据从node2迁移到node4，就形成了新的符合一致性哈希规则的缓存结构。

**2.删除节点**

当缓存集群的节点需要删除的时候（比如节点挂掉），整个环形空间的映射同样会保持一致性哈希的顺时针规则，同样有一小部分key的归属会受到影响。

![程序员小灰-漫画：什么是一致性哈希？][- 30]

有哪些key会受到影响呢？图中删除了原节点node3，按照顺时针规则，原本node3所拥有的缓存数据就需要“托付”给node3的顺时针后继节点node1。因此受影响的key只有key4。

![程序员小灰-漫画：什么是一致性哈希？][- 31]

最终把key4的缓存数据从node3迁移到node1，就形成了新的符合一致性哈希规则的缓存结构。

![程序员小灰-漫画：什么是一致性哈希？][- 32]

![程序员小灰-漫画：什么是一致性哈希？][- 33]

![程序员小灰-漫画：什么是一致性哈希？][- 34]

![程序员小灰-漫画：什么是一致性哈希？][- 35]

![程序员小灰-漫画：什么是一致性哈希？][- 36]

![程序员小灰-漫画：什么是一致性哈希？][- 37]

![程序员小灰-漫画：什么是一致性哈希？][- 38]

![程序员小灰-漫画：什么是一致性哈希？][- 39]

如上图所示，假如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与虚拟节点的映射关系也变得相对均衡了。

![程序员小灰-漫画：什么是一致性哈希？][- 40]

![程序员小灰-漫画：什么是一致性哈希？][- 41]

![程序员小灰-漫画：什么是一致性哈希？][- 42]

![程序员小灰-漫画：什么是一致性哈希？][- 43]

![程序员小灰-漫画：什么是一致性哈希？][- 44]

**实例讲解**

**一致性哈希算法，作为分布式计算的数据分配参考，比传统的取模，划段都好很多。**

在电信计费中，可以作为多台消息接口机和在线计费主机的分配算法，根据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')

[-]: http://p98.pstatp.com/large/pgc-image/1538967043950de5c729e3e
[- 1]: http://p98.pstatp.com/large/pgc-image/15389670439632b7838cc48
[- 2]: http://p1.pstatp.com/large/pgc-image/1538967043941fa5a10822a
[- 3]: http://p98.pstatp.com/large/pgc-image/1538967044097f9a75d3cb4
[- 4]: http://p98.pstatp.com/large/pgc-image/1538967044117b8ddfeaddf
[- 5]: http://p9.pstatp.com/large/pgc-image/1538967044090a9f1a5663c
[- 6]: http://p3.pstatp.com/large/pgc-image/15389670442672f018bb9c5
[- 7]: http://p98.pstatp.com/large/pgc-image/1538967044301522a019645
[- 8]: http://p1.pstatp.com/large/pgc-image/15389670444205009e8a4c4
[- 9]: http://p3.pstatp.com/large/pgc-image/1538967044437c82a55988d
[- 10]: http://p3.pstatp.com/large/pgc-image/153896704445041184752e3
[- 11]: http://p1.pstatp.com/large/pgc-image/1538967044582d82fe3010d
[- 12]: http://p3.pstatp.com/large/pgc-image/1538967044718af53e01086
[- 13]: http://p3.pstatp.com/large/pgc-image/15389670447305c0b78afde
[- 14]: http://p3.pstatp.com/large/pgc-image/1538967044757bb569ecdaf
[- 15]: http://p3.pstatp.com/large/pgc-image/153896704488863a2571bd3
[- 16]: http://p98.pstatp.com/large/pgc-image/15389670449990282b09ada
[- 17]: http://p98.pstatp.com/large/pgc-image/15389670450683b67843bef
[- 18]: http://p98.pstatp.com/large/pgc-image/15389670450984a37e1dcc8
[- 19]: http://p98.pstatp.com/large/pgc-image/15389670451066d97210dcf
[- 20]: http://p98.pstatp.com/large/pgc-image/1538967045224dd7db961c3
[- 21]: http://p9.pstatp.com/large/pgc-image/1538967045303ee260faae0
[- 22]: http://p1.pstatp.com/large/pgc-image/1538967045461cc5d54326e
[- 23]: http://p98.pstatp.com/large/pgc-image/1538967045546543d725a40
[- 24]: http://p3.pstatp.com/large/pgc-image/1538967045503615b3d063b
[- 25]: http://p9.pstatp.com/large/pgc-image/1538967045667851227d6d8
[- 26]: http://p3.pstatp.com/large/pgc-image/1538967045637476c8989f6
[- 27]: http://p3.pstatp.com/large/pgc-image/15389670457245ed1e5f64d
[- 28]: http://p3.pstatp.com/large/pgc-image/153896704590619e23dde7e
[- 29]: http://p98.pstatp.com/large/pgc-image/15389670459377d7b25eef6
[- 30]: http://p98.pstatp.com/large/pgc-image/153896704604341e3292b11
[- 31]: http://p98.pstatp.com/large/pgc-image/153896704604316942a6748
[- 32]: http://p1.pstatp.com/large/pgc-image/153896704608493fb70fb9c
[- 33]: http://p98.pstatp.com/large/pgc-image/1538967046308aa4a8d0d89
[- 34]: http://p3.pstatp.com/large/pgc-image/153896704629104ba04a841
[- 35]: http://p98.pstatp.com/large/pgc-image/15389670463088c91d71c15
[- 36]: http://p1.pstatp.com/large/pgc-image/1538967046491741ed067c8
[- 37]: http://p98.pstatp.com/large/pgc-image/1538967046461dfd1d7afbd
[- 38]: http://p3.pstatp.com/large/pgc-image/1538967046633b48c677cbb
[- 39]: http://p9.pstatp.com/large/pgc-image/1538967046741b3475496d2
[- 40]: http://p3.pstatp.com/large/pgc-image/153896704672871204a2a93
[- 41]: http://p1.pstatp.com/large/pgc-image/1538967046828f737ba009d
[- 42]: http://p98.pstatp.com/large/pgc-image/1538967046810cb0810dc44
[- 43]: http://p3.pstatp.com/large/pgc-image/1538967051278621928d115
[- 44]: http://p3.pstatp.com/large/pgc-image/1538967046988379eb5d07e