FAST'20

Jiqiang Chen, Liang Chen, Sheng Wang, Guoyun Zhu, Yuanyuan Sun, Huan Liu, and Feifei Li, Alibaba Group

背景

• 热点问题是现实世界中的一个很普遍的问题
• 内存KV Store的热点问题没有被重视，在阿里的生产环境中观察到50%-90%的访问，只涉及到了1%的数据，主要原因：
  • 互联网用户数量增加，一个热点事件往往吸引大量用户访问
  • 应用底层变得更加复杂，一个小错误可能导致数据被重复访问
• 传统Hash表（最简单的Chain Hash）的问题：没有热度感知

传统hash table

• 现有的对热点数据访问的优化作用有限：
  • CPU有cache，但是CPU cache大小与数据集相比实在太小
  • rehash不太适合本身已经很大的hash表

Hot-Ring

基本思想

使访问item需要的次数与其热度相关

主要设计

Hot-ring shift

Ordered-Ring Hash Index

HotRing将原来哈希表的冲突链表改成一个环状链表，将最后一个元素指向第一个元素，HashTable中有个head pointer指向环状链表的一个元素。

HotRing的环状链表

这样的结构带来一个问题：查找的时候怎么知道查找结束了？为了解决这个问题，本文提出了Ordered-ring的方法，本质就是对这个链表以tag-key(称为一个Order)的方式进行排序（对于一个key，计算其n位的hash值，取前k位作为hash表的索引，后n-k位为tag）。排序之后的结构如下图：

Ordered-Ring

进行查找的时候根据tag和key的大小判断是否结束：

查找结束的判断条件

以上图作为例子，查找B(4, 35)的时候，查到C(5, 65)不命中，而下一个元素一定比C大，所以这个时候就知道B不在表里，结束查找，其他同理。

Hotspot Identification

HotRing通过head pointer指向hot元素以减少hot元素的查找开销，接下来本文需要解决如何判断热点数据的问题，判断热点需要考虑两个因素，分别是判断精度以及反应时间，针对这个问题提出了两种热点数据判断的策略：1）Random Movement Strategy；2）Statistical Sampling Strategy。

• Random Movement Strategy

主要思想：没有历史数据统计，每R个请求之后，如果第R个请求访问的不是当前的热数据（head pointer指向的元素），则将head pointer指向当前访问的元素。

缺点：需要workload有很好的热点，以及只能单一热点，不能都会造成head pointer的频繁切换

• Statistical Sampling Strategy

主要思想：通过记录历史访问信息来计算热度

因为需要记录历史访问信息，为了能够不引入额外的空间，HotRing中利用了head pointer / next pointer的剩余空间，因为指示地址用48位就够了，这样还有16位剩下来，对于head pointer，HotRing将这16位分成1 bit的active位以及15位的total counter位，total counter用于记录当前这个bucket的访问次数，对于next pointer， HotRing将这16位分成了1 bit Rehash位，1bit Occupied位以及14 bit的counter位，Rehash和Counter分别用于并发的Rehash和update操作。

HotRing Index结构

Statistical Sample：每个线程维护一个请求计数R，当第R个请求结束的时候判断是否触发Sample，如果访问的不是当前的热点数据则触发。然后设置Active位为1，这之后的每个请求都会在Total counter以及Counter中被计数。sample的次数等于bucket内item个数。

热点计算：最后一个访问的线程负责根据统计的热度信息，计算income，这个income代表了当某个item被选为head pointer之后访问该ring的平均内存访问次数，ni为第i个item的访问次数，N为总的访问次数，Wt为income值，计算公式如下：

income计算公式

RCU写热点的计算：RCU是指Read-Modify-Update操作，对于小于8B的value，可以通过CAS原子就地更新，但是对于超过8B的value，就需要先新建一个节点，然后替换旧的节点，这个时候就需要遍历整个链表来获取head pointer的前一个元素。为了减少内存访问，HotRing增加的是head pointer的上一个元素的counter，这样head就是热点数据的前一个元素，加速了热点数据的修改。

写热点的更新

• 热点继承

当更新或者删除head pointer的时候，需要将head pointer进行移动。对于更新，将head point指向最新被更新的元素，因为本文认为这样的元素再被访问的概率会更大；对于删除，将head point移到下一个元素。

Lock-Free concurrency

• Read：不需要额外的机制
• Insert：通过CAS修改next指针
• Update：
  • 小于8B的update可以通过CAS原子修改
• Read-Modify-Update：

RCU需要创建新的节点，然后替换旧的节点，这种情况如果有别的线程也在进行操作，则可能出错：

并发更新可能出现的错误

（a）中插入C同时更新B，因为C修改的是B，所以C将无法访问；（b）中同时update B和D，D'将无法访问；（c）中删除B，D’将无法访问。

为了解决上面的这些情况，本文通过前面指针中的Occupied位来进行并发控制（有点像锁），当需要修改一个节点的时候，将这个节点的next指针中的Occupied位设置为1，然后再更新这个节点，此时对需要修改当前next指针的操作就会失败，等这次操作完成之后再reset Occupied位另一个线程才能继续操作。例如（a）中更新B首先设置B的next中Occupied为1，然后原子更新A的next，此时插入C的线程因为B的Occupied为1不能操作，等A更新完，这个时候C的插入才能继续。

• Head pointer movement

对于head pointer的移动，这里分成两种情况，一是update，这就只需要Occupied新的节点；对于delete，需要Occupied当前节点以及next节点，因为如果next节点被修改，那么head可能指向一个无效数据。

Lock-Free Rehash

• 触发条件

因为原来根据load factor触发rehash的方式没有考虑热度，所以HotRing采用的是access overhead（读取一个item平均的内存访问次数）来触发rehash

• 初始化：

创建一个rehash线程，并初始化一个二倍于旧空间的hash表，每一个旧表的head pointer对应两个新表的head pointer。旧表采用hash值的k位作为hash地址，新表取k+1位，同时取T = 2^(n-k)作为链表的分界点。同时，创建两个rehash item，tag分别为0和2^(n-k)，设置rehash位为1，同时两个新的head分别指向两个rehash item

• 拆分

插入rehash item到链表，插入之后新表就可以active，并且不影响数据访问

• 删除

在确保旧表没有访问之后删除旧表，然后删除rehash node，完成rehash

无锁的Rehash

唔。。。因为这篇文章跟研究方向不太相关，测试部分就不详细看了