HotRing论文浅读与复现
本文最后更新于 2024年9月26日 凌晨
论文为：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删除，并将环首尾相接，回收旧哈希表，在完成此步之前需要确保所有对旧哈希表的访问已经结束