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构造上吗？