HotRing 热点感知 KV 索引 有序环哈希

论文浏览笔记

【FAST’20】HotRing: A Hotspot-Aware In-Memory Key-Value Store

https://www.usenix.org/system…

huazhong

简介

背景、动机

• 热点问题很广泛。如：阿里生产环境中，50%~90% 的拜访，只波及 1% 的数据。
• 内存 KV 构造的热点问题不被器重，大多数 KV 构造不能感知热点。
• 目前内存 KV 构造缩小热点访存的办法有局限：CPU cache 太小；rehash（为缩小抵触）不适宜自身微小的表，且性能晋升无限。

次要思维

设计热点感知的内存 KV 构造——有序环哈希 构造。

次要挑战及应答办法：

• 热点转移：把抵触链改为环。头节点挪动到热点项；两种策略检测热点转移。
• 高并发拜访：应用 无锁 构造，实现插删，并扩大到热点特定操作（热点转移检测、头指针挪动、有序环 rehash）。

奉献

• 反对快速访问热点数据。
• 有轻量的运行时热点转移检测策略。
• 无锁机制，反对高并发拜访，贯通热点特定操作（热点转移检测、头指针挪动、有序化 rehash）。
• 实在环境测试，高度不均衡的负载试验，2.58x。

有序环

把抵触链改为有序环构造。

$order_k = (tag_k, key_k) $。对抵触环以 tag-key 形式排序。

查找。不命中：

不命中，均匀只须要查找一半的元素（抵触链则须要遍历整条）。

热点转移辨认

两种掂量：accurancy、反馈提早。

把头指针挪动到热点项。

随机挪动

每隔 R 个申请，若第 R 个申请不是拜访热点项（指头指针所指元素），则将头指针指向以后拜访项。不需历史统计数据，挪动到潜在热点项。

实现简略，反应时间较快。

R 小，反馈提早可能小，但会造成频繁的指针挪动，低效。试验表明，R = 5 较好。

毛病：

• 辨认精度低。
• 负载歪斜不显著时，该办法低效。
• 若抵触环有多个热点，无奈应答，频繁的挪动反而影响其余操作

统计采样

辨认精度更高，反馈提早稍长。能够应答环上多个热点的状况。

索引格局

利用头指针、item 的残余 16bit 空间。

active：管制统计采样。total count：统计采样时环的总拜访次数。

rehash：管制 rehash。occupied：管制并发，保障并发拜访的正确性。counter：某一项的拜访次数。

address：下一项的地址。

统计采样：每 R 个申请，若第 R 个申请不是拜访热点项（指头指针所指元素），则触发采样：active 地位 1（需 CAS 原语），之后对该环的拜访都会被计数（total counter 和 counter），采样的次数等于该环 item 的个数。

热点挑整

计算每一项 $t$ 的 income：$ W_t = \sum \limits_{i=1}^N \frac{n_i}{N} \cdot [(i-t)mod k ] $. ($n_i$：项 $i$ 的计数，$N$：总计数 $k$：环长)

$W_t$ 掂量的是：将头指针指向 $t$ 后，该环的均匀访存。

抉择 $W_t$ 最小的项 $t$，作为新热点。应用 CAS 原语来挪动头指针。最初重置计数器。

可解决多个热点。

RCU

RCU：read-copy-update。小于 8B 的 value，可用 CAS 原地更新。大于 8B 的，需用 RCU 更新。这时需遍历整个环来获取前驱结点，因此，写密集热点会让它的前驱变热。因而，需批改统计采样法。

对 RCU 更新，减少其前驱的 counter，而非其自身 counter。这可助头指针指向写密集热点的前驱，减速 RCU 批改。

热点继承

头节点产生 RCU 更新或删除。

• 若环只有一项，用 CAS 更新头指针即可。
• 若环有多项：若头节点 RCU 更新，将头指针指向新版的头（因为它被再次拜访的概率高）；若头节点删除，则头指针移到下一项，

并发

1. 读：不须要额定机制，无锁。
2. 插入：创立新节点，批改前驱的 next 指针。应用 CAS 操作，避免两个线程同时批改同一个 next item address，一个胜利一个失败，失败的需从新执行操作。
3. 更新：

• 小于 8B，CAS 更新。

• RCU 更新则须要创立新节点，替换旧节点，有并发问题。（图 8）

  • 过程 1 在 B 后插入 C，过程 2 将 RCU 更新 B。若用 CAS，则会胜利，因为它们批改的是不同的指针。出错。
  • 过程 1RCU 更新 B，过程 2RCU 更新 D。若用 CAS，则两个操作都会胜利，而 D‘将无法访问，出错。
  • 过程 1RCU 更新 D，过程 2 删除 B。将导致 D’无法访问，出错。
• RCU 更新，更新项 occupied 地位 1。如插入 & 更新，要 RCU 更新 B，需将 B 的 occupied 置 1，此时 C 插入会失败，稍后，A 的 next 指针指向 B‘，B’的 occupied 为 0。

1. 删除。被批改项的 occupied 置 1，改完其前驱的 next 后再置回 0。如，删除 B，B 的 occupied 置 1，此时找 D 的前驱会不命中，D 更新失败，需重来。

2. 头指针挪动。挪动头指针时，需查看其余操作，避免头指针指向有效项；删除或更新时，须要查看头指针是否指向它。

   • 将头指针移到一项时，将该项的 occupied 置 1，避免该项更新、删除。
   • 头节点更新，将新头的 occupied 置 1，再挪动头节点。
   • 头节点删除，将头、头的后续的 occpuied 置 1，再挪动头节点。

无锁 rehash

传统 rehash，由负载因子触发。这不适用于热点解决。HotRing 应用拜访开销（检索一个 item 的均匀访存次数）来触发 rehash。（怎么计算 采样还是？）

初始化

创立 rehash 线程，初始化一个两倍大小的哈希表，共用 tag 的最高位。用来 hash 的局部从 k 位变为 k+ 1 位，tag 则缩小一位。设 hash value 有 n bit，旧表的 tag 范畴[0, T)，T = 2^(n-k)，则两个新头指针别离对应[0, T/2)，[T/2, T)。

同时，创立一个 rehash node，蕴含两个子哈希项，其 tag 别离为 0、T/2，rehash 位均为 1，外面不存无效 KV 对。

宰割

rehash 线程将两个 rehash item 插入到环中，插入后，新表被激活。如图，别离插入到 B 前、E 前。

这样，此时通过 old head 拜访，能够通过查看 rehash 位跳过 rehash item，后续的通过 new head 拜访新表也能失常。

删除

过渡期：期待所有通过 old head 拜访的操作完结。而后就能够删除旧表和 rehash node，真正拆成两个环。

留神，过渡期只会阻塞 rehash 线程，不会阻塞 access 线程。

（new head1 指向 old head，new head2 指向 tag > T/ 2 的下一项吗？）

试验

baseline：chaining hash（用 HotRing 的无锁机制），FASTER，Masstree，Memcached。

HotRing-r（用随机采样），HotRing-s（用统计采样）。

• 单线程、64 线程下，比拟吞吐量。
• 不同抵触链长度（key-bucket 率从 2 到 16），比拟吞吐量。
• 负载歪斜率（不同 zipfian 散布参数，记为 $\theta$），比拟吞吐量。
• 用 YCSB 产生写密集负载，进行 RCU 试验，测吞吐量。
• 测 break-down cost。

其余：（用两种 HotRing，chaining hash）

• 扭转负载，即产生热点转移，通过测吞吐量，剖析反馈提早。
• 用 read miss 负载，测吞吐量，以剖析三种机制解决 read miss 的性能。HotRing 更好，因为它们均匀只须要查找一半的元素，而抵触链须要遍历整条。
• 不同 R 下，测吞吐量，以找最优的 R。
• 尾提早。统计采样周期最初一个线程须要计算，会有尾提早。不同 $\theta$ 下，测 access 提早随 acess ratio 的变动。
• 测验 rehash。250 百万 key，key-bucket ratio = 8。YCSB 产生 50% 读、50% 插入的负载，模仿哈希表增长。这里，I、T、S 散布示意 rehash 的初始化、过渡期、宰割。可知，rehash 操作，能使得吞吐量复原到增长前的程度。短期的陡降是因为新哈希表短期的热点感知匮乏。

后续工作

随机挪动针对只能应答抵触环上单个热点的状况，随机采样可解决多个热点。很多状况下，能够通过 rehash 拆分热点。然而极其状况下，这会生效。作者称将持续摸索。

集体领会

链改环，采样，设置几个 flag 管制并发，本文的设计思路很清晰天然，尽管是惯例的想法，但整合成了丑陋的零碎设计。

试验做得很充沛，通过各种对照，剖析各项设计带来的性能晋升，值得学习。

一些困惑：

• 这种构造有没有更好的热点转移识别方法？
• RCU 更新，须要遍历环来取得前驱，实践上来看对于高并发的 RCU 写密集的负载不敌对吧（试验后果倒好），然而设置前向指针又节约空间得失相当。
• Rehash 过渡期（即插入 rehash node 之后，宰割前），产生 RCU 更新须要阻塞吗？
• 是否能够把统计采样周期开端的额定计算交给专门的线程，以缩小尾提早？
• 这种热点感知办法能够迁徙到关系数据库、或者 LSM 构造上吗？