本文为阿里缓存系统Tair中关于HotRing的论文学习

HotRing: 阿里缓存系统Tair的自感知热点数据子组件

本文参考阿里发表的关于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对于缓存集群的每个节点处理热点数据,是一个非常有用的数据结构。

背景和动机

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

现有的Hash索引和热点问题

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

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

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

也有一些方法减少热点数据访问代价,但是,效果非常有限。首先,比如CPU缓存可以加速访问热点数据块。但是对大部分的服务器来说,CPU缓存只有32M左右。对于一个256G的Redis缓存集群来说,它只能缓存0.012%的数据。0.012%的比例肯定是不够用的。阿里团队分析了他们的业务数据分布,得到如下图所示的结论。即对于一个Redis集群来说,50%~90%的情况下会访问集群中1%的KEY。img

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

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

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

HotRing简介

让我们看看阿里的HotRing是如何设计来优化冲突链表访问性能问题的。

数据结构需要对热点感知,以降低内存读取的次数。

此外,还需要:

  • 感知热点的转移
    • 用于解决冲突的链表被替换成环,即HotRing
    • 访问时,头指针会移动到最近访问项/热点项(热点访问时可显著降低内存读取次数)
    • 有轻量的策略在运行时检测热点的转移(本文有2个)
  • 支持并发
    • 无锁化处理:基于CAS,以及read-copy-update (RCU), Hazard Pointers等
    • 支持其它的并发操作:如热点转移检测、头指针移动、rehash等

如下图所示,由冲突环取代之前的冲突链表,并且有一个Head指针,它会指向或者接近最热的KEY,并且这个环是有序的。Head指针非常有用,当热点数据发生转移时,只需要更改这个Head指针,让其指向环上最热的数据,或者一个更好的位置。热点数据转移策略有两种,后面会细讲:img

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

HotRing设计

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

有序环索引结构

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

但是环形设计有一个很严重的问题:就是如果KEY不存在的话,就会导致死循环。因此,需要一个很好的方案解决这个问题,这非常重要。看到这里,你可能会有疑问,为什么不把Head指针当作起点,也当作终点呢?不可以,因为由于并发问题,Head指针可能会被修改。

因此,HotRing的设计是让冲突环有序,并且根据KEY进行排序。这样的话,当我们在冲突环上查找某个KEY时,如果连续碰到两个KEY且一个比目标KEY大,一个比目标KEY小,就表示找不到目标KEY,那么就可以安全的停止查找了。

下图对比了冲突链表和HotRing两种数据结构访问方式。

  1. 在HotRing中,Head指向A(3, 25),假设我们要查询B(4,35),那么从Head开始,访问到C(5,65)就可以结束了。

  2. 而在冲突链表中,我们需要遍历A,C,D,E,F,I后才能停止访问:img

热点转移识别

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

因此,我们要做的就是,把这个Head指针指向这个热点元素。为了获得很好的性能,我们需要考虑两个指标:识别精准度和反应灵敏度(鱼与熊掌不可兼得)。现如今有两种方案:

  1. 随机移动策略
  2. 统计采样策略

随机移动

我们首先介绍的是随机移动策略,这种策略的特点是反应灵敏,且不依赖于任何的元数据,但是精准度不及后面介绍的统计采样策略。

基本思路:周期性的将Head指针移到一个潜在的热点KEY上,不需要记录任何历史数据。

具体实现:

  1. 每个线程会有一个ThreadLocal变量记录它执行的请求数
  2. 每满R次请求,线程决定是否需要移动Head指针。
    1. 假设第R次访问刚好是热点访问,那么不需要移动Head指针。
    2. 反之,将指针移动到访问的这个元素上,这个元素变为新的热点数据。

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

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

统计采样

为了访问热点数据的性能最高,因为我们设计了统计采样策略。它提供了更精准的特点识别能力,但是相比随机策略反应会迟钝一些。

关于索引格式

头指针Head包括:

  1. active 1bit,作为控制统计采样的标识。
  2. total_counter 15bit,当前环总共的访问次数
  3. address 48bit ,环的头地址

环上的next包括:

  1. rehash 1bit,作为控制rehash的标识
  2. occupied 1bit,用于并发控制,保证并发访问的正确性
  3. counter 14bit,该项的访问次数
  4. address 48bit,下一项的地址

统计采样的具体实现:

统计采样也是需要开销的,为了降低开销,且保证识别的准确性,和随机移动一样,周期性地调整:

  • 每个线程维护一个变量,记录执行了多少次请求
  • 每隔R个请求,线程决定是否要移动头指针
    • 若第R个请求是hot access,头指针不移动,且不开启采样
    • 否则,则需要移动头指针,开启统计采样,采样个数也是R
      • 打开head.active(CAS)
      • 后续的请求会被记录到head.total_count和对应的next.count(CAS)

热点调整

基于上一步的统计采样,就可以决定哪一个是头节点,步骤如下:

  • 关闭head.active(CAS)
  • 遍历环,计算每一项的访问频率nk/N
  • 计算每个节点的收益,取最小的收益min(Wt),将项tt作为新的hot item
  • 使用CAS设置新的头指针
  • 重置所有的计数器

写入密集型的热点:RCU场景下

对于更新操作,HotRing可以对不超过8字节的数据进行in-place原子更新操作,这种情况下,读取和更新被视作一样的操作。

但对于大量数据的更新,则使用read-copy-update协议,并且需要修改前一项的next指针。特别的,修改一个hot item,需要遍历整个环来获取前一项——也就是说,修改一个hot item,也会让前一项hot。因此,RCU下,更新的是前一项的计数器。

由于在RCU下,更新的是前一项的计数器,头指针就会趋向于指向写入项的前一项,在写密集型的热点时,可以直接定位到热点的前一项,更新时就不需要遍历链表。

1.png

例如上图,热点是A,RCU下,修改A需要前一项F,这需要遍历整个环。

所以RCU下,更新的是F的计数器,从而让头指针指向F(写入热点依旧是A),之后写入A时,不需要遍历环了。

热点继承

当对头节点执行更新或删除时,头节点需要指向其它项。但是不能随便指向其它项,因为很可能新的一项是cold item,然后频繁触发热点识别,降低性能。

解决方式如下:

  • 若环只有一项,直接CAS更新头指针即可
  • 若环有多个项,利用已有的热点信息(即头指针的位置)处理:
    • RCU更新:指向新版本的头(因为很可能会被再次访问,比如读取)
    • 删除:指向被删除项的下一个节点

并发操作

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

查询

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

插入

插入需要:

  • 创建新项
  • 连接新项的next指针
  • 修改前一项的next指向新项(CAS)

第三步可通过CAS保证线程安全。若前一项next字段发生竞争,CAS会失败,此时操作需要重试(重试后2步)。

更新

当更新的数据不超过8字节:使用in-place CAS,不需要其它操作。

当更新的数据超过8字节:使用RCU更新,这时候需要分3种情况

  • RCU-update & Insert

    如下图,2个线程分别更新B和插入C,修改前一项的next需要CAS,两个操作都会成功,但是结果不能成环了:

    1.png

  • RCU-update & RCU-update

    如下图,2个线程分别更新B和D,和第一种情况一样,CAS都会成功,但是最后结果也会导致无法成环,且B’的next是一个野指针:

    2.png

  • RCU-update & Delete

    如下图,2个线程分别删除B和更新D,也有类似的问题,CAS也都会成功,但是最后结果也会导致无法成环,且A的next是一个野指针:

    3.png

可见只有CAS设置next指针是不够的。

这时候需要额外的字段以保证正确性,这就是next指针的occupy字段,例如:

  • RCU-update & Insert
    • RCU-update前,尝试CAS修改B.next值,置B.next.occupy = 1
    • Insert时,使用CAS连接前一个节点,发现B.next.occupy = 1,操作会失败,重试
    • 操作完成后,新版本项的occupy为0
  • RCU-update & Delete
    • Delete前,尝试CAS修改待删除项B.next值,置B.next.occupy = 1
    • RCU-update时,使用CAS连接前一个节点,发现B.next.occupy = 1,操作会失败,重试
    • 操作完成后,新版本项的occupy为0
  • RCU-update & RCU-update:个人认为和RCU-update & Delete类似

总结:

  • RCU-update和删除会CAS置待更新/删除的节点occupy从0到1
  • 所有操作利用CAS连接前一个节点
  • 任何的CAS失败,以及前一个节点的next.occupy = 1,操作都会失败,需要重试

其实论文只是一笔带过了,最后还是得看无锁链表的论文(先挖一个坑)。

论文先上:

  • Valois J D. Lock-free linked lists using compare-and-swap[C]//Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. 1995: 214-222.

删除

RCU-update & Delete的情况上面也说了。

而Delete & Delete的情况,和RCU-update & Delete情况类似;而Delete & Insert情况,和RCU-update & Insert情况类似。

Head指针移动

需要解决2个问题:

  • 处理正常操作和头指针移动的并发
  • 处理更新/删除头节点之后的头指针移动

这里依旧使用occupy字段:

  • 当要移动头指针时,CAS设置新的头节点的occupy为1,保证其不被更新/删除
  • 当头节点被更新时:
    • 移动前,更新时会设置新版本的头节点occupy为1
    • 移动完成,重置occupy为0
  • 当头节点被删除时:
    • 除了设置当前被删除的头节点occupy为1,还得设置下一项的occupy为1,因为下一项是新的头节点,需要保证其不被更新/删除
    • 移动完成,重置occupy为0

无锁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)。

1.png

同时,rehash线程创建一个rehash节点(如下右图中间节点所示,包含两个空数据的子元素节点),子元素节点分别对应两个新Head指针(Head1和Head2)。HotRing利用元素中的Rehash标志位识别rehash节点的子元素节点:

2.png

  1. 分裂

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

  1. 删除

最后一步,线程将a)中创建的rehash node删除。

但在此之前,需要保证旧表上的访问要终止(类似于RCU的grace period同步原语,RCU也要挖一个坑)。所有旧表访问结束后,线程会删除旧表和rehash node。

可知,只有rehash线程会阻塞,其它线程是不会阻塞的。

4.png