HotRing——热点感知的哈希冲突解决方案

本文作者:Jiekun,授权转发 原文链接:https://jiekun.dev/posts/hotring/

在使用链表法解决哈希冲突时,由于多数场景下,热点数据异常集中,链表中多个item可能仅有一个是hot item。对于无特定排序规则的链表,其访问复杂度为O(n/2)。但如果能将hot item前置,理想情况下则能优化至O(1)。HotRing数据结构以此为思路,对链表法重新设计,针对热点集中的场景进行优化,并实现了高效的热点发现策略和无锁rehash,让哈希表的访问性能大幅提升。

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扩大哈希表,可以降低哈希冲突的概率。但是哈希冲突仍然存在,也需要有对应的方法在出现冲突时让数据仍能正确读取到。

HotRing——热点感知的哈希冲突解决方案

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——热点感知的哈希冲突解决方案

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也需要能够存储相关的统计信息,例如访问次数。通过额外的后台线程来分析统计值,可以在热点发生变化时及时对头指针进行调整。

HotRing——热点感知的哈希冲突解决方案

具体实现

数据查找

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

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

  • item存在,则满足:
item(k) = item(i)
  • item不存在,则不存在ii-1满足:
item(i-1) < item(k)   < item(i)    或
item(k)   < item(i)   < item(i-1)  或
item(i)   < item(i-1) < item(k) 

HotRing——热点感知的哈希冲突解决方案

而为了减少对字符串的字典序比较,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——热点感知的哈希冲突解决方案

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

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

HotRing——热点感知的哈希冲突解决方案

如上图公式所示,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,例如0range/2,后续可以作为两个新环的临时头节点(最后将被清理)。在rehash时,新哈希表的对应槽上的头指针指向这两个rehash item。同时rehash item上也有对应的标志位,表示其不包含键值对,只作为rehash过程中的头节点使用。

HotRing——热点感知的哈希冲突解决方案

分裂阶段,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——热点感知的哈希冲突解决方案



HotRing——热点感知的哈希冲突解决方案



上一篇:LeetCode Hot 100 No.53 最大子序和


下一篇:leetcode hot 100-42. 接雨水