Author: jiekun.zhu@shopee.com / Supply Chain Group / 后端工程师
Blog: https://jiekun.dev/posts/hotring/

Paper Reading 系列旨在分享著名 Conference 上发表的论文。FAST （ USENIX Conference on File and Storage Technologies ）是存储领域的顶会之一，第 18 届 FAST于美国 Santa Clara 举行。

关于 Paper

《HotRing: A Hotsport-Aware In-Memory Key-Value Store》发表于 2020 年，主要研究的是使用链表结构解决哈希冲突时，访问热点数据存在一定额外开销的问题。论文提出的 HotRing 结构支持热点数据发现，并且可通过使环状链表的头部指针指向 hot item，减少读取所需遍历的路径，达到提升访问效率的目的。

Hash Collision 简介

当我们使用哈希表时，不可避免地会存在哈希冲突。我们将大量数据通过计算哈希值的方式放入相对较小的哈希表中，不同 item 得到的哈希值可能会是一致的。通常通过 rehash 扩大哈希表，可以降低哈希冲突的概率。但是哈希冲突仍然存在，也需要有对应的方法在出现冲突时让数据仍能正确读取到。

Collision 解决方案

当出现不同的 item 具有相同哈希值时，需要有合适的位置来存放多个 item 。这些 item 可以被安插在同一张哈希表的不同位置，也可以被放到哈希表之外的空间，而让哈希表保存外部空间的地址值。

Open Addressing

开放地址法是将冲突的 item 放在哈希表内的方案。使用开放地址法时，查找对应 item 的操作称为探测（ Probing ）。当期望写入的哈希位置已经存在其他 item B 时，可以将 item A 放至：

相邻的空位——线性探测
间隔 1 、4 、9 、16 的空位——平方探测
另一个的 Hash 方法计算的空位——二次哈希

开放地址法的查询终止条件为：探测到对应 item 或探测到空位。当探测到非目标 item 时，目标 item 可能在下一个位置，也可能不存在，因此需要继续探测。开放地址法要求哈希表比数据集更大，当负载因子处于高位时，对于冲突 item 的查询，遍历路径则会变得相对长，性能也会因此下降。因此开放地址法需要相当大的空间来存放哈希表。

Collision Chain

链表法将 item 存储在哈希表之外，每个哈希桶存放有指向链表头部的指针，通过顺序遍历链表确认查找的 item 是否存在。

与开放地址法相比，链表法可以允许 item 数量大于哈希表。在负载因子增长的情况下，开放地址法的探测速度会显著变慢，而链表法仍能保持查询效率与长度挂钩地线性增长。

HotRing

在实际使用场景中，经常会有大量 item 被放入哈希表，而其中只有极少数是热点数据。

对于链表法的热点数据的访问，简化模型下需要查找的次数为：

T = 1 + L / 2 
  = 1 + (N / B) / 2

其中L 代表哈希桶对应的链表长度，N 为总 item 数，B 为哈希桶数量。

如果可以让热点数据长期位于链表头部，访问的复杂度就可以贴近O(1)。但是对单链表的 item 位置调整，也就是类似于 LRU/LFU 的实现，操作上开销不低，并且实际上除了极少数 hot item 的位置，其余 item 的顺序其实并没有那么重要。设计一种代替链表的、贴合缓存使用场景的数据结构，通常会期望：

能加速热点 item 的访问
- 能及时发现热点
- 能以较低的额外开销将热点移至便于访问的位置
能支持并发场景下操作
高效率 Rehash
...

针对这类场景和需求，HotRing 结构应运而生。

设计概览

HotRing 是一个环状的链表结构。在加速热点数据的访问上，HotRing 让哈希表中的头指针始终指向 hot item 或能高效访问多个 hot item 的位置。比起调整链表中 item 位置，修改头指针更加高效简洁。为了能够发现热点数据，每个 item 也需要能够存储相关的统计信息，例如访问次数。通过额外的后台线程来分析统计值，可以在热点发生变化时及时对头指针进行调整。

具体实现

数据查找

从大家熟悉的《 Linked List Cycle 》解法中可见，无序的环状链表要么使用额外的哈希表存储已经遍历过的 item，要么使用双指针增加遍历范围直至指针重合而退出，从空间或时间效率上看都不太合适。因此 HotRing 选择在写入时略微增加开销，让环状链表保持顺序性，从而查找时就能更快定位或结束遍历。

对于目标元素item(k)结束查找的标志可以是：

item 存在，则满足：

item(k) = item(i)

item 不存在，则不存在i和i-1满足：

item(i-1) < item(k)   < item(i)    或
item(k)   < item(i)   < item(i-1)  或
item(i)   < item(i-1) < item(k)

而为了减少对字符串的字典序比较，HotRing 为每个 item 都增加了一个 tag，即item(k) = (tag(k), key(k))。

通过这种设计，无需遍历链表中所有元素即可提前终止遍历，平均情况下查找 item 数可以达到(n/2) + 1。实际上，因为头部指针位置的优化，大多数查找能够更早定位到 hot item 而结束。

热点发现

实际场景中，由于 hot item 一直在变，因此需要能准确、及时发现 hot item 的机制，我们也可以从这两个方面来定性评定发现算法的优劣：

准确性：头指针指向 hot item 的比例
及时性：多少延迟之后头指针可以指向 hot item

HotRing 设计了两种方案来实现热点发现，分别是随机策略和统计样本策略。

随机策略非常简单，HotRing 周期性地将头指针指向本次查询到的 item 。默认周期为 5，即每 5 次查询到 item 时，若头指针已经指向该 item，则不发生调整；否则将头指针指向 item 。这个方案巧妙之处在于，hot item 的访问概率远大于 cold item，利用这点,无需任何统计信息即可实现热点发现。

当然，这个方案在环中存在多个 hot item 时表现并不好，同时准确率也比另一种策略要低。另外，当整体系统压力较小、热点分散的情景下，随机策略的准确性也会进一步降低，头指针需要频繁发生变更。因此我们还需要另一种能够对多热点优化、准确率更高的方案。

统计样本策略，顾名思义需要一定的数据样本。HotRing 的头指针带有 15bit 的 Total Counter，而环中每个 item 带有 14bit 的 Counter，Total Counter 表示对该环的总命中次数，item 的 Counter 则代表该 item 的命中次数。

HotRing 周期性地进行样本分析，每次分析起始时，Total Counter 和 Counter 均为 0，在一定时间后，根据 Total Counter 和每个 item 的 Counter 值决定使用哪个 item 作为头节点。

如上图公式所示，ni表示item(i)采样期间的的访问次数，N代表总访问次数，(i-t) mod k代表从头节点item(t)出发访问到item(i)所需遍历的长度，因此Wt即为该环状链表遍历长度的加权平均值，该值越小说明头节点的选择越优异。

统计样本策略更加准确，同时也能使用于多个 hot item 的场景，但是经常进行分析也会有一定的开销。因此，优化的周期策略是每隔 R 次查询时先判断本次 fetch 到的 item 是否为头指针指向的 item，若是，则 hot item 很可能没有发生变化；反之则有必要发起新的一轮样本统计。

热点继承是指 hot item 发生变更时应该如何处理。HotRing 使用的思路也非常简单，如果头节点发生了更新，最近更新的 item 理应有更大可能性被读取到，因此头指针直接指向这个新的 item ；而当头节点被删除时，头指针直接指向下一个 item，后续依赖热点发现的策略作进一步调整。

无锁 Rehash

当哈希表需要扩容时，由于哈希槽的增加，环状链表也需要将 item 分配到新的环中。和传统的 rehash 不同，HotRing 决定 rehash 的条件是查找所需的平均内存访问次数，而非哈希表负载因子，这种方案能够和 hot item 分布情况相结合，减少 rehash 次数。HotRing 的 rehash 分为 3 个阶段：初始化、分裂、清理。

在初始化阶段，HotRing 创建一个后台线程，这个线程会新建一个原有哈希表2 倍大小的新哈希表。这里重新描述一下哈希表和 tag 的关系，在计算一个 item 的哈希值时，值的前 k 位用作哈希表定位，后 t 位作为 tag 。因此，当哈希表扩容 2 倍，需要多占用 k+1 位哈希值，tag 值则缩小为 t-1 位。通过这个关系，环状链表在扩容时可根据 tag 值一分为二：原有 tag 值 t 位，因此范围为range = 2^t，扩容后范围为2^(t-1)，因此正好可以按[0, range/2)和[range/2, range)划分为两个新的环，对应新哈希表上两个 slot 。

初始化线程还会创建一个 rehash 节点，其中包含两个子 rehash item 。每个 rehash item 有不同的 tag，例如0和range/2，后续可以作为两个新环的临时头节点（最后将被清理）。在 rehash 时，新哈希表的对应槽上的头指针指向这两个 rehash item 。同时 rehash item 上也有对应的标志位，表示其不包含键值对，只作为 rehash 过程中的头节点使用。

在分裂阶段，rehash 线程将两个 rehash item 放入环中，它们将会作为 tag 范围和遍历的边界，当 Insert 操作完成，新的哈希表就会生效。由于没有 item 的复制和迁移，整个过程大部分操作都是通过无锁的 CAS 完成的，开销会相对较低。在清理阶段之前，查找操作以新的 rehash item 为起点，最多需要遍历半个环。

最后清理阶段，在这个阶段，rehash 线程需要确认所有的旧哈希表访问都已经结束，进而先删除旧哈希表，然后清理所有的 rehash 节点。要注意这个阶段，旧哈希表的访问会阻塞 rehash 线程进入下一步操作，但是不影响主线程进行读写。

总结

HotRing 适应的场景是热点高度集中的哈希表访问。在此情形下，HotRing 的设计有如下特点：

将热点数据排列在链表最靠前位置，缩短访问路径
环状链表设计，实现上一特点只需要头指针变更，无需 item 移动
结合场景特点，实现简单有效的随机策略和适应性强、路径优化更好的统计样本策略来处理热点数据、热点漂移
使用原子的 CAS 操作避免引入锁机制
巧妙的环状链表 rehash 思路，无数据迁移成本，rehash 过程中不阻塞读写

HotRing 和其他的哈希冲突解决方案相比，有多个特点是结合特定场景和数据分布而落地的，在一定条件下的测试结果表明其提升非常明显，并且热点数据大都能够在两次内存访问内检索到。其中对环状数据结构的设计及其配套的随机、采样思路对高性能的业务场景设计都有不少参考价值。

References

[1] J Chen, HotRing: A Hotspot-Aware In-Memory Key-Value Store. In FAST '20.

HotRing: 代替拉链法的哈希冲突高效读取方案 / 热点感知 / 无锁 rehash