HotRing论文浅读与复现
本文最后更新于 2024年9月3日 下午
论文为:HotRing: A Hotspot-Aware In-Memory Key-Value Store
https://www.usenix.org/system/files/fast20-chen_jiqiang.pdf
1 HotRing 介绍
HotRing 是一种针对热点数据的内存键值存储系统设计方案,其修改链式哈希为有序环状,旨在有效处理数据访问的不均衡情况,同时采用无锁化设计来提供更好的并发支持。
常用的解决热点问题的方法有:
- 使用一致性哈希算法(目的是减少节点数量改变时的数据重映射)将数据映射到多个节点上,分摊热点访问
- 数据备份到多个节点上
- 在客户端层面进行热点数据缓存
而HotRing的目的为提升单节点处理热点数据的能力,相比于跳表、平衡树、哈希表,HotRing将解决热点感知和转移以及并发问题。
2 背景和动机
链式哈希表中,热点数据可能被添加在链表的后面,导致数据访问过慢。
常见的方法如利用CPU缓存、扩大哈希规模都不能完全解决热点问题,于是提出HotRing:
将key分为hash/tag来减少比较大小,head指针可以自由更换为指向热点数据,利用CAS和RCU技术进行无锁化设计
3 具体设计
3.1 有序环设计
利用<tag, key>构造字典序(减少排序开销),另外由于有序,不用遍历所有的数据项即可发现读不命中(平均访问$$n/2+1$$个即可发现):
3.2 热点感知
热点数据会被哈希到不同桶中,而此处我们只聚焦于同一个桶中的热点感知问题。实践中,发生冲突的数据一般很少,平均下来,通常一个桶中有一个热点数据(10%-20%的热点比例下),有两种评测指标:
- 热点感知准确率
- 热点感知延迟
提出两种方法,随机移动、采样分析,前者有更低的延迟,后者有更高的准确率
3.2.1 随机移动
每R次访问,将head移动到当前访问的数据上,默认将R设为5。优点是不需要额外的元数据开销,响应速度快,缺点是当访问的负载倾斜程度较小时,效率会降低。
3.2.2 采样分析
首先讨论header和item的数据格式:
其中active标志是否启动采样,rehash标志是否需要重哈希,occupied用于并发。
系统将在R次访问后判断是否要进行(当前访问数据是否为header指向数据)。
若启动分析,则设置active标志位,并更新counter,为了减少采样时间,设置样本数量为当前环中的数据数量。
采样结束后,计算每个数据的收益(=访问频率*到该项的距离),选择最小收益项的数据为热点数据,更新head指针,这种采样方式同时考虑到了如果有多个热点的问题。
现考虑更新操作,如果小于八字节,则使用原子更新操作(机器支持),否则,使用RCU策略,这样会导致多个节点被访问,此处仅考虑增加前驱数据counter
另外对于删除操作,直接更改header为下一个数据
3.3 并发
首先读操作是无锁的,对于写操作利用CAS避免冲突,竞争失败的一方重新执行。
现考虑和RCU相关的三种并发情况:
对于前两种情况,两种冲突操作都会成功,为避免此种情况,利用occupied位侦测,对于删除操作,同样需要注意锁定被删除的数据
对于头指针的移动,需要将新的头节点的occupied位置1,避免头指针指向无效数据
3.4 Rehash
最后考虑当环上存在多个热点数据的数据重映射问题,使用访问目标数据的平均内存访问次数作为指标,若其超过R次则触发rehash
Rehash分为三步:
- 初始化:创建后台线程,翻倍当前哈希表(从tag借用一位过来),然后创建一个rehash node,包含两个rehash child item。
- 分割: 通过tag范围将环分割为两个子环,此时既可通过旧哈希表访问也可以通过新哈希表访问
- 删除:将rehash node删除,并将环首尾相接,回收旧哈希表,在完成此步之前需要确保所有对旧哈希表的访问已经结束