深入理解哈希&一致性哈希

发表于 更新于 分类于 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

前言

在实际开发中，随着业务的发展，经常会遇到单服务的性能瓶颈问题，比如：Redis 服务、MySQL 服务。那么对于单服务的性能瓶颈导致的诸如服务过载或者服务不可用的问题，该如何解决呢？

答案：分集群，突破单集群的性能限制

开发经验丰富一些的小伙伴肯定马上会想到增加一个 Proxy 层，由 Proxy 层处理来自客户端的读写请求，然后由Proxy对 Key 做哈希把请求路由到对应的集群。比如Codis就是基于这种Proxy方式，下文就介绍2种经典的hash路由算法。

Hash算法

Hash，一般翻译为“散列或者哈希”，就是把任意长度的输入(又叫做预映射， pre-image)，通过散列算法，变换成固定长度的输出，该输出就是散列值。

假设有 A、B、C 三个节点组成的KV服务，每个节点存放不同的数据，当用户的请求过来时，可以在Proxy代理层，对某个设定的key进行hash计算，然后用hash(key)对节点总数做取模操作，这样相同key的请求总是能路由到相同的节点上，如下图：

img.png

假如，随着业务的发展，用户量越来越大，原来的A，B，C3个节点无法承受用户端的流量压力，这时需要增加一个节点，如下图：

img.png

扩容

从上图我们可以看出，当增加一个节点D时，原来的路由算法需要从 hash(key)%3 变成 hash(key)%4，那么会出现什么问题？

假如 hash(key) = 100，hash(key)%3 = 1， hash(key)%4=0，此时 计算的结果值就发生了变化，对于同一个请求，扩容前路由到序号1节点(节点B)，扩容后路由到序号0节点(A节点)，寻址发生变化，请求在节点B能获取数据，在A节点获取失败，则这种扩容方式降导致请求获取数据失败，带来的问题将是灾难性的。

缩容

同理：比如因为疫情，用户量越来越少，原本需要3个节点，现在2个节点就能满足需求，需要进行缩容，如下图：

img.png

缩容，同样会出现扩容时寻址失败的问题，可以采取迁移数据的方式来解决：

比如：

扩容操作，扩容前路由到A节点，扩容后路由到B节点，可以把数据从A节点迁移到B节点，满足新的路由方式；

缩容操作，同理。

但是当数据量比较大的时候迁移数据的也是需要代价的，有没有更好的方式来降低这种数据迁移？

** 答案：一致性hash

一致性hash算法

一致性hash算法也是采用取模运算，但与hash不同的是，哈希算法是对节点的总数进行取模运算，当节点的数量发生变化时，取模的结果会发生变化，而一致哈希算法是对 2^32 这个固定的数值进行取模运算，所以hash(key)算法不变，取模的结果就不变。

实际上，一致性hash是将整个哈希值空间组织成一个虚拟的圆环，也就是哈希环，如下图：

img.png

假如有A，B，C3个节点，当需要对 key 的值进行读写操作时，可以按照下面 2 步进行寻址：

  • 对key 进行 c-hash() 计算，并确定此 key 在环上的位置；
  • 从key所在的这个位置沿着哈希环顺时针”行走”，遇到的第一节点就是 key 对应的节点；

如下图： hash(keyA)%2^32寻址到节点A，hash(keyB)%2^32寻址到节点B，hash(keyC)%2^32寻址到节点C

img_1.png

扩容

当增加一个集群D，keyC原本是寻址路由到节点C，现在寻址路由到节点D，因此受影响的key是节点B到节点D之间的所有请求，其他的key不受影响。

img.png

缩容

当缩容节点C时，keyC 原本寻址路由到节点C，按照一致性hash的原理，顺时针寻找到最近的一个节点A，所以节点B到节点C之间的key将受到影响，寻址路由到新的节点A。

img.png

通过上面对一致性hash扩缩容的分析可以知道，当对节点进行扩缩容时，受影响的key是局部的，需要迁移的数据也可控，而且可以推到出随着节点的增多，受影响的key会成反比下降。

公平性

如下图，当hash换上的节点分布不均匀时，节点A承受了70%的流量，而节点B，C只承受了30%的流量，这样就会导致数据访问的冷热不均，造成不公平，如何解决？

答案： 虚拟节点

如下图：在节点C和节点A中增加了一个虚拟节点X，真实指向节点B，这样keyD原本路由到节点A，现在路由到节点B，这样就解决了数据访问的冷热不均造成的不公平问题。
img.png

总结

  • hash 算法是对节点总数取模后进行寻址路由，因此，对于扩缩容频繁导致大量数据迁移的场景不太适用；
  • 一致性 hash 是一种特殊的 hash 算法，节点增减变化只影响到部分数据的路由寻址，因此只需要迁移部分数据，就能实现集群的稳定；
  • 一致性 hash 算法，当节点数较少时，可能会出现节点在哈希环上分布不均匀的情况，最终导致业务对节点的访问冷热不均，可以通过引入更多的虚拟节点来解决；
  • 一致性 hash 算法具有较好的容错性和可扩展性；
  • 一致性 hash通过增多虚拟节点提升均衡性，但也会消耗更多的内存与计算力；
  • 关键字到节点位置的映射，hash 算法的时间复杂度是O(1) ，一致性 hash 的时间复杂度是O(logN)；

学习交流

如果你觉得文章有帮助，请帮忙转发给更多的好友，或关注公众号：猿java，持续输出硬核文章。

drawing