简单讲述一致性hash算法。

大数据时代，单机数据库再也无法满足存储、访问需求。为满足需求，数据库往往会做分库分表处理。这就引申出一个问题：如何让存储的数据尽可能均匀地分散到各个节点，同时满足减少节点是数据的迁移较少。

一致性哈希算法

这个算法在Cache系统中的应用越来越广。最早出现在Consisten Hashing and Random Trees。

基本使用场景：

有N台cache服务器，如何将一个对象object映射到N台cache上？通常情况下会考虑这样的映射规则：hash(object)%N

再考虑如下三种情况：

  • cache集群中的服务器k宕机了，所有映射到k上的对象都失效了，这时需要把服务器k从集群中移去，这样集群中还有N-1台服务器，映射公式变成hash(object)%(N-1)

  • 由于cache的访问量加大，需要添加cache，如果添加一台，映射公式变成hash(object)%(N+1)

  • 后来添加上去的节点，如何把访问量从整体上平分开来？

这三种情况的解决方案需要一致性哈希算法。

hash算法和单调性

hash算法的一个衡量标准是单调性（Monotonicity），定义如下：

  • 单调性指如果已经有一些内容通过哈希分派到相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到旧的缓冲中，而不会被映射到新的缓冲集合中。上述简单的映射无法满足单调性。

一致性哈希算法的原理

基本眼里包括如下几点：

  • 环形hash空间
  • 把对象映射到hash空间
  • 把cache映射到hash空间
  • 把对象映射到cache
  • 考察cache的变动

虚拟结点的处理方法

引入虚拟节点就是为了处理当节点异常而引起的问题。

  • 虚拟结点的处理方法

Hash(“IPAddress”) | 没有虚拟结点的情况

Hash(“IPAddress#1”) | 有虚拟节点#1
Hash(“IPAddress#2”) | 有虚拟节点#2