写在前面：本文参考阿里发表的关于HotRing的英文论文，论文地址：https://www.usenix.org/system/files/fast20-chen_jiqiang.pdf。

首先需要说明的是，HotRing是阿里核心缓存系统Tair的一个子组件。Tair是阿里一个NoSQL内存数据库（Tair在阿里云上称为企业版Redis）。HotRing是Tair用来解决冲突链表长度导致性能衰减问题的一个子组件。

为什么需要HotRing

HotRing不是要解决缓存集群服务中单节点的并发能力上限，这一点一定要注意。它要解决的问题是缓存核心数据结构Hash中链表冲突导致性能衰减的问题。所以，阿里工程师测试出来的带有HotRing的Tair，其性能相比目前其他最快的KV系统，是它们的2.58倍。根据压力测试可知，HotRing对于缓存集群的每个节点处理热点数据，是一个非常有用的数据结构。

题外话：Tair也有解决单个节点性能瓶颈的能力。假设双十一淘宝首页上的一件商品，我们可知，这件商品信息的TPS起码是几百万甚至千万级别的。这样的热点KEY，无论你的集群有多大，这个KEY只会路由到其中的一台服务器上，那么并发能力就受到单节点限制，原生的memcache和Redis是完全搞不定的（Redis单节点TPS大概是10w级别，memcache可以达到几十万）。有一种办法就是自己处理本地缓存，这样代价比较大。阿里Tair的做法是热点散列，如下图所示，在每一个DataServer上开辟一个HotZone，统计到的热点KEY就保存到集群每一个节点上的HotZone中，客户端把热点数据KEY的请求随机打到任意一台DataServer的HotZone区域（热点KEY并不是Hash取模，这一点很重要），这样的话热点KEY请求就会被散列到多个节点乃至整个集群。那么整个Tair集群就不会因为某个热点KEY而发生过载的情况。本文不作过多的发散，有兴趣的同学请戳链接了解更多，非常值得一看：2017双11技术揭秘—分布式缓存服务Tair的热点数据散列机制：https://yq.aliyun.com/articles/316466。

背景和动机

这一段落，我们首先介绍Hash索引和KV系统中存在的热点问题。然而，我们会给出热点感应理论的潜在好处。最后，我们讨论感应热点的挑战以及我们的设计原则。

Hash索引和热点问题

Hash索引是KV存储中最流行的数据结构，尤其当上游系统不需要范围查询的时候。下图是典型的hash索引结构，其包含一张全局的Hash表，并且每个Entry都有一个冲突的链表。当我们访问一个元素时，首先计算它的hash值h，这样就能定位到Entry，然后在冲突链表上寻找我们要找的KEY。我们假设hash值h有n位，我们将其分为两部分，前面 k位用来作为hash表部分，后面n-k位用来作为tag部分，如下图所示：

这样的数据结构有一个很明显的问题，如下图所示。冲突的链表越长，需要访问的内存次数就越多。因为在链表上查找某个KEY的时间复杂度是O(n)：

这样的数据结构还带来一个问题，我们再看上面的（Figure 2），因为它无法感知热点数据，那么热点数据很可能在链表的头部，也可能在链表的尾部，也可能均匀分散在链表上。热点数据越接近尾部，访问内存的次数就越高，性能就会越差，而且会随着并发的提升，表现会更差。所以，这样的数据结构对热点数据是非常不友好的。

也有一些方法减少热点数据访问代价，但是，效果非常有限。首先，比如CPU缓存可以加速访问热点数据块。但是对大部分的服务器来说，CPU缓存只有32M左右。对于一个256G的Redis缓存集群来说，它只能缓存0.012%的数据。

0.012%的比例肯定是不够用的。阿里团队分析了他们的业务数据分布，得到如下图所示的结论。即对于一个Redis集群来说，50%～90%的情况下会访问集群中1%的KEY。：

CPU缓存这种方案行不通。还有另一种办法：Rehash。通过Rehash来减少冲突链表的长度。冲突链表长度越短，热点数据访问的代价就越小，性能就会越高。但是。当Hash表已经非常大的时候，非常不建议Rehash。因为Rehash可能仅带来一半的功效（就减少链长而言）。总而言之，所有现有方法都只能在较小程度上缓解热点问题。

当我们论证HotRing的价值后，就剩下挑战需要我们去解决了，我们的设计主要面对以下两个问题：

1. 热点转移（Hotspot Shift）。真实系统的缓存中热点数据是会随着时间发生变化的，比如今天是IQOO3，明天是Mate30，后台是iPhone。所以，我们需要一个轻量的方案来跟踪这些热点切换问题。
2. 并发访问（Concurrent Access）。每个热点数据的并发都会非常高，所以支持高并发的读写，才能达到令人满意的性能。

HotRing简介

让我们看看阿里的HotRing是如何设计来优化冲突链表访问性能问题的。如下图所示，由冲突环取代之前的冲突链表，并且有一个Head指针，它会指向或者接近最热的KEY，并且这个环是有序的。Head指针非常有用，当热点数据发生转移时，只需要更改这个Head指针，让其指向环上最热的数据，或者一个更好的位置。热点数据转移策略有两种，后面会细讲：

至于并发问题，无锁（LOCK-FREE）设计是最权威的解决方案，而且很多研究表明无锁设计能显著提升性能（JDK8中JUC大量采用CAS尽可能的不加锁解决并发，也是一样的原理）！而在HotRing中引入无锁设计，可以非常优雅的解决并发写入与删除问题，并且设计团队还将其应用到所有需要的地方，比如：热点转移探测，Head指针移动，rehash等。

HotRing设计

接下来，让我们更深入的了解HotRing的设计细节，包括索引结构，特点转移探测策略，无锁操作（包括读写，插入删除，Head指针移动，Rehash等）。

有序环索引结构

如上面的（Figure 4）图描述了HotRing的索引结构，它主要改进了传统Hash索引冲突链表结构。阿里HotRing的设计将最后一个KEY和第一个KEY连起来，并称之为冲突环。这样的话，Head指针可以指向任意一个元素，并不一定是固定在链表的第一个元素。这样的设计，就可以将Head指向热点数据。需要注意的是，当冲突环上只有一个数据时，Head的next指向它本身。

但是环形设计有一个很严重的问题，就是如果KEY不存在的话，就会导致死循环。因此，需要一个很好的方案解决这个问题，这非常重要。看到这里，你可能会有疑问，为什么不把Head指针当作起点，也当作终点呢？不可以，因为由于并发问题，Head指针可能会被修改。因此，HotRing的设计是让冲突环有序，并且根据KEY进行排序。这样的话，当我们在冲突环上查找某个KEY时，如果连续碰到两个KEY且一个比目标KEY大，一个比目标KEY小，就表示找不到目标KEY，那么就可以安全的停止查找了。

下图对比了冲突链表和HotRing两种数据结构访问方式。在HotRing中，Head指向A(3, 25)，假设我们要查询B(4，35)，那么从Head开始，访问到C(5，65)就可以结束了。而在冲突链表中，我们需要遍历A，C，D，E，F，I后才能停止访问：

热点转移识别

如刚才讲到，在HotRing中，无论是查找一个存在的KEY还是不存在的KEY，都非常容易。那么还有一个很棘手的问题，就是当热点发生转移的时候，如何识别并调整Head指针。比如热点本来在A(3，25)上，随着时间的推移，当热点转移到D(5, 68)时，如何感知，并将Head移到D(5, 68)上。

由于Hash值分布非常均匀，所以热点KEY均匀分布在所有桶中。因此，我们只需要关注每个Bucket中如何识别热点问题即可。实际上，每个桶中冲突的元素是很少的（可能只有5～10个），并且由于热点数据比例一般只有10～20%，这就意味着每个桶上可能只有一个热点KEY。因此，我们要做的就是，把这个Head指针指向这个热点元素。为了获得很好的性能，我们需要考虑两个指标：识别精准度和反应灵敏度（鱼与熊掌不可兼得）。

1. 随机移动策略

我们首先介绍的是随机移动策略，这种策略的特点是反应灵敏，但是精准度不及后面介绍的统计采样策略。这个策略的基本思路就是周期性的将Head指针移到一个潜在的热点KEY上，不需要记录任何历史数据。每个线程会有一个ThreadLocal变量记录它执行的请求数，每满R次请求，线程决定是否需要移动Head指针。假设第R次访问刚好是热点访问，那么不需要移动Head指针。反之，将指针移动到访问的这个元素上，这个元素变为新的热点数据。

这个参数R会影响反应灵敏度和识别精确度，如果R的值比较小，反应灵敏度会变高，但是就会带来频繁的，无效的Head指针移动。在我们的使用场景中，访问的数据高度倾斜，因此Head指针移动应该不会频繁。根据经验，这个R值默认设置为5。

需要注意的是，如果数据倾斜不明显的话，这个随机策略的效果就不是很理想。更重要的是，这个策略不能处理一个环上有多个热点KEY的场景。因为在这种场景下，Head指针会频繁的在这些热点KEY之间移动。如此一来，不但不能加速热点数据访问，可能还会影响常规操作。

2. 统计采样策略

为了访问热点数据的性能最高，因为我们设计了统计采样策略。它提供了更精准的特点识别能力，但是相比随机策略反应会迟钝一些。接下来首先介绍每个KEY的详细格式，以及HotRing上的Head指针，讲解如何利用这些数据格式在没有额外空间消耗的前提下维护统计信息，然后我们详细阐述采样策略预估访问频率。最终，我们要找到一个方法，当热点数据转移时，能让Head指针移动到最佳位置，并且支持多个热点KEY存在一个HotRing上的情况。

并发操作

Head指针无锁（lock-free）设计会比较复杂，主要反映在几个方面：一方面，Head指针可能被多个线程并发执行移动操作。因为要考虑Head指针的并发情况，防止Head指针移动到无效的KEY上。另一方面，当我们删除或者更新KEY时，我们需要检查Head指针是否在这些KEY上。如果是，那我我们要保证移动Head的准确性。接下来我们从增删改查这4个维度详细讲述HotRing上的并发操作。

1. 查询

在HotRing上查找一个目标KEY就是从Head开始查找，前面已经提到过，不需要任何额外的动作，读操作本身就是无锁的。

2. 新增

新增操作如下图所示，假设创建一个C，同时并发修改B为B'。假如没有并发保护，插入C后，链路就是B->C->D。同时将B修改为B'，链路就是A->B'->D。这样的话，从A遍历，就会发现C已经丢失了。

3. 修改

修改操作如下图所示，假设有一个线程将B修改为B‘，同时另一个线程将D修改为D‘，如果没有并发保护，就会导致最终的链路变成：A->B'->D->E，即D'会丢失：

4. 删除

删除操作如下图所示，假设有一个线程将D修改为D‘，同时另一个线程将B线程。如果没有并发保护，可能导致最终的链路变成A->D->E，即D'会丢失：

为了解决上面这几种并发导致的问题，HotRing用了一个Occupied位来解决这个问题。例如，在[2. 新增]即更新和被插入并发操作时，更新B时它的Next被更新，这时候它的Occupied就会设置为true。一旦Occupied设置为true，接下来的并发新增C就会失败，因为B的Occupied为true，所以必须重试，直到更新操作完成才行。原理非常类似于CAS，即你任何操作涉及的KEY的Occupied都不能是true，是true表示其他并发操作正在进行中。

5. Head指针移动

为了确保Head指针操作的准确性，尤其在更新和删除的时候。HotRing分不同情况解决这个问题。如果是识别策略导致Head指针移动时，也用Occupied这个占位符来解决并发问题。比如识别策略达到满足Head指针移动的条件，首先将Head指针指向的元素的Occupied置为true。确保它不被更新和删除（因为这时候如果有并发更新和删除，发现它们要操作的KEY的Occupied为true，就会重试）。然后将Head指针移到新的KEY上，移动之前，需要确保新的KEY没有被其他线程更新或者删除，因此移动Head之前，还需要将新的KEY的Occupied置为true，当Head指针移动完成后，再将这两个KEY的Occupied重置。然后其他线程就能操作这两个KEY了。

无锁Rehash

传统的Rehash策略一般由负载因子触发，例如冲突链表平均长度等。然后这种策略没有考虑热点数据，所以对HotRing不适合。取而代之的是，HotRing用访问成本来触发Rehash（获取数据时平均内存访问次数）。如下图所示，HotRing的无锁Rehash分为如下3个主要步骤：

1. 初始化

首先HotRing创建一个rehash的后台线程，这个线程初始化一个size是旧hash表两倍的新hash表。通过复用tag的最高一位来进行索引。因此，新表中将会有两个Head指针与旧表中的一个Head指针对应。HotRing根据tag范围对数据进行划分。假设tag最大值为T，tag范围为[0,T)，则两个新的Head指针对应tag范围为[0,T/2)和[T/2,T)。同时，rehash线程创建一个rehash节点（如下右图中间节点所示，包含两个空数据的子元素节点），子元素节点分别对应两个新Head指针（Head1和Head2）。HotRing利用元素中的Rehash标志位识别rehash节点的子元素节点：

2. 分裂

在分裂阶段，rehash线程通过将rehash节点的两个子元素节点插入冲突环中完成环的分裂。如图（Split）所示，因为B和E是tag的范围边界，所以子元素节点分别插入到B和E之前。完成两个插入操作后，新hash表将激活，所有的访问都将通过新hash表进行访问。到目前为止，已经在逻辑上将冲突环一分为二。接下来当我们查找数据时，最多需要扫描相比旧hash表一半的元素：

3. 删除

删除阶段需要做一些收尾性的工作，包括旧hash表的回收。以及rehash节点的删除回收。这里需要强调，分裂阶段和删除阶段间，必须有一个RCU静默期(transition period)。该静默期保证所有从旧哈希表进入的访问均已经返回。否则，直接回收旧哈希表可能导致并发错误。

4. 总结

接下来简单总结一下HotRing是如何rehash的。首先会有一个size为旧表2倍的新的hash表，并且会有两个Head指针：Head1和Head2。分裂时，原冲突环中一半的元素跟着Head1，另一半的元素跟着Head2，从而组成两个新的冲突环。最后是一些收尾性的工作，简单吧^^

总结

最后，我们通过YCSB对HotRing方案进行了压力测试，并对比了行业有名的Memcached等。压测结果如下图所示，我们可以看到HotRing方案的吞吐量远超其他方案：

此外，压测了链表长度对性能的影响，如下图所示，我们可以发现当链表长度从2一直递增到16的过程中。HotRing方案的性能几乎是恒定的。而一致性Hash和FASTER方案的性能很明显梯度递减了：