HotRing

Paper Reading：HotRing——哈希冲突中热点数据高效读取方案 (jiekun.dev)

关于paper

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

简介

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

open Addressing

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

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

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

CollisionChain

链表法将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让哈希表中的头指针始终指向hot item或能搞笑访问多个hot item的位置。比起调整链表中item的位置。修改头指针更加简洁高效。为了能够发现热点数据，每个item也需要能够存储相关的统计信息，例如访问次数。通过后台线程来分析统计值，可以再热点发生变化时，对头指针进行调整。

具体实现

数据查找

若环状链表没有任何顺序，确认item不存在的复杂度为O(n)，从时间效率上看可以再优化。hotRing选择在写入时略微增加开销，让环状链表保持顺序性，从而查找时就能更快定位或结束遍历。

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

• item存在，则满足：

item(k) = item(i)

• 若不满足上式，且满足下列任一条件时，说明item不存在：

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，而每个环中带有14bit的Counter，Total Counter表示对该环的总命中次数，item的Count则代表item的命中次数。

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

如上图公式所示，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线程将俩个rehashitem放入环中，它们将会作为tag范围和遍历的边界，当insert操作完成，新的哈希表就会生效。由于没有item的复制和迁移，整个大部分操作都是通过无锁的CAS完成的，开销会相对较低。在清理阶段之前，查找操作新的rehash item为起点，最多需要遍历半个环。

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

总结

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

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

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