分布式缓存存储算法与实践思考

最近遇到一个问题，可能很多人也遇到过：由于业务量的增长，缓存节点个数不够用了。现在的Redis-Cluster直接就加个节点就解决了，但是之前Redis-Cluster不稳定时，我们并不敢用这个，而是通过自己实现分布式缓存Redis实现，在遇到这个问题时，碰到不少麻烦。

由于我们分片算法很简单，直接用户id的哈希值对节点个数取余。假设原来是3，现在是4，那么至少有1-（3/4*3）=四分之三的数据不能命中缓存，使DB一下子会压力过载。这样显然是不可取的。那么怎么解决呢？

这篇文章会回忆下当初的解决思路，供大家参考，同时感叹下技术迭代之快速哈，当初那么麻烦的一个问题，现在redis-cluster直接搞定。

我们从为何需要分布式缓存开始说起：

分布式缓存解决的问题

随着业务的增长

目前，虚拟化技术已经很流行了，一般我们部署应用都部署在虚拟机上面，这样更能增加实体机器的利用效率：例如某些应用一般在上午繁忙，某些应用一般在下午繁忙，如果都单独部署在自己的机器上，那么上午繁忙的机器在下午就是空闲的状态，这样会造成资源浪费。

虚拟化带来的令一大优势就是让分布式应用更好部署了。缓存框架一般用Redis，当业务量增长到一定规模的时候，我们一般采用分布式Redis缓存部署。那为什么我们要分布式部署呢？

首先就是成本问题，我们可以把单个机器的CPU还有内存配置搞得很高，从阿里云的成本来看，貌似更高配置的价格相较于低配置的更实惠些。但是，某些应用由于程序限制，只能在保证效率的前提下利用一定的机器资源。例如我们这里说的缓存数据库Redis，Redis的主业务进程是单线程的，如果连接的客户端链接过多，势必会影响性能，并且理论上只有一个CPU会被业务线程跑满。还有就是硬件成本的问题，假设CPU还有内存都可以被程序充分利用，那么瓶颈就在IO上，例如硬盘IO，例如Redis打开RDB和AOF，如果硬盘IO不够，CPU是无法充分利用的，各种IO的成本就很难控制了。

然后还有高可用的问题，如果单机部署，那么就没有容错，一台挂了整个业务就没法跑了。这样显然是不行的。

所以，一般我们会分布式部署缓存来满足我们的业务需要。那么我们一般怎么写数据呢？

对于一致性要求比较高的，不能是最终一致性的缓存数据，一般流程是：

Q1. 为何ReadApi在缓存没有命中的时候，从数据库中将数据读取出来写入缓存？ 因为这样做需要考虑多线程的问题，在读取的时候需要上读锁：假设在读取时缓存没命中，正好有更新，更新先完成，之后缓存没命中导致的更新才完成，这样的话会导致缓存脏了。每个读取都要上读锁，比较影响效率

Q2. 如何写入的缓存？ 这里，我们假设缓存中的是用户信息，我们根据用户ID分片，不同用户存入不同的缓存实例。 如何分片，很简单的我们就会想到通过用户的哈希值对分片个数取模就好了。

业务增长后如何扩容的思考

首先，我们会考虑说，把每个原有Redis节点扩大内存，同时提高所在虚拟机的配置。这样短期来看是可行的，但是长期来看，考虑前文说的成本还有利用率，这显然不能长治久安。

然后，我们考虑水平扩容，那么之前的那种写入数据的方法就会出现问题

简单的对用户哈希值取模在扩容时会遇到的问题与解决思考

按照我们之前的存储读取数据的算法，假设我们目前有三个分片，如果要扩容成四个，那么要迁移的数据就是：1-（3除以3和4的最小公倍数），也就是四分之三的数据，否则四分之三的数据查询会直接压到数据库上把数据库压垮。 这显然太多了，我们即使多加节点，最少要迁移的数据也有二分之一（也就是扩容到6个节点）。

所以，我们只能采取另外一种方案，就是建立另一个缓存集群节点为4个，之后应用多写一份到这个缓存上，等到预热到一定程度之后，切换到这个新的缓存集群上。

但是这样也是太麻烦了，以后再加新的节点，预热时间会越来越长，成本越来越高（如果想迁移的数据少，就得多加一倍的节点，但实际上二分之一的数据也不少），显然这也不是长治久安的方案。

所以，我们的分片算法必须改进，最简单的办法就是一致性哈希。

一致性哈希算法

一致性哈希算法可以减少我们需要迁移的数据量，就是减少扩容之后缓存不命中。基本原理是：

1. 首先求出每个缓存节点的哈希值，并将其配置到0～2^32节点的圆上。

1. 然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。
2. 然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过2^32仍然找不到服务器，就会保存到第一台服务器上。

但是上面说的方法可能过于理想化，在实践过程中我们发现：第一步的时候我们遇到三个节点在圆上面的分布并不均匀，这样就可能出现三个节点数据分布不均匀的情况，如下图所示：

一致性哈希算法改进

导致上面分布不均匀的原因即节点太少，如果节点变多一些，那么就可以缓解。为了缓解上面说的节点分布不均匀的问题，我们引入虚节点的概念，即将原来的一个节点看做多个节点，比如我们将一个节点抽象为3个，原来的1变为1-1，1-2，1-3，以此类推，之后我们发现变成了这个样子：

这样看上去效果好多了。

哈希算法我们也可以改进写，例如采用Wang/Jenkins Hash哈希算法

实际应用后，我们发现效果还不错，新加入节点需要迁移的数据变少了不少。

但是后来，我们发现我们的思路有问题！！！

实际上，我们不能停留于减少缓存不命中的量，应该制定出一种平滑的方案，尽量避免缓存不命中，既能减少需要迁移的量，又能可控的知道哪些数据要迁移。

对于平滑迁移方案，虚拟节点一致性哈希算法

集群算法：

1. 每个实际节点抽象为3个虚拟节点，求出每个缓存节点的哈希值（WANG-JENKINS HASH算法），并将其配置到0～2^32节点的圆上

1. 然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。
2. 然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过2^32仍然找不到服务器，就会保存到第一台服务器上。

当集群中新加入一个节点时：

1. 新加入的节点抽象为3个虚拟节点，求出每个缓存节点的哈希值，并将其配置到0～2^32节点的圆上
2. 以下图为例，迁移现有数据：

那么也就是要迁移，哈希值在1-1到4-1之间的数据（数据3），哈希值在2-2到4-2之间的数据（没有数据），哈希值在2-3到4-3之间的数据（数据9），那么也就是说，我们最好对每个数据的哈希值做索引或者做记录。否则需要重新遍历计算所有数据的哈希值来迁移数据。

这样虽然看上去比较完美了，但是还是比较复杂，而且设计一致性哈希，对于新人交接工作并不友好，其实这里就没必要用一致性哈希了，于是我们采用了更朴实的方案。

更实际朴实的方案，分块哈希算法实现方案

集群建立方案

1. 我们将所有数据抽象为65536个slot（2的16次方，这个个数最好是2的n次方，因为对于2的n次方取模相当于对2的n次方减一取与运算，增加取模效率）
2. 根据集群现有节点个数，用总slot数除以节点个数，就是每个节点承载数据的slot量，例如初始我们有3个节点： 9699690/3=3233230 那么数据分布就是：

这就是我们的slot映射表

1. 利用WANG-JENKINS HASH计算数据哈希值，对于65535取与运算，根据slot映射表存入结果的对应节点

当新加入一个节点时： 从每个节点上分别复制当前节点个数分之1的总slot量除以原节点个数（即65536/4/3）的数据，即：

slot一个一个复制，每复制一个slot之前，需要上锁，阻塞住对于这个slot的更新，复制结束后，更新一下映射表，释放锁，更新后，删除原节点上面对应的slot数据。

采用这个方案后，我们对于缓存的扩容就很平滑了

后来，Redis-Cluster稳定了，那么Redis-Cluster是如何解决的？

发现Redis-Cluster利用的方案也是分块哈希，只不过哈希算法是CRC32，并且slot总数为16384 这里引用下这篇文章的图片