Gray's grind

(FAST '20) HotRing: A Hotspot-Aware In-Memory Key-Value Store

2020/04/20 System

FAST 20阿里的一个关于in-memory kv store的工作，优化基于hash的in-memory key-value store的热点访问问题。

Problem

image.png Hot spot热点问题也就是真实场景下访问的不平衡性，如zipf分布。
image.png 如上图所示，在memcached等key-value cache system中的设计思路很简单，维护一个大hash table，用collision chain拉链法来应对hash collision。当chain的末端为hot item的时候，read的过程需要重复读chain前面部分的item。除了造成不必要的mem read以外，也使得system cache（CPU cache）性能下降。

比较明显的几个Solution：

  • rehash（ememory footprint开销↑）
  • 给hot item加一层front end cache（过还需要应对hotspot shift的问题）

在LevelDB, RocksDB等kv store on disk里就是使用后者方案。因为memory快很多，用来做cache很自然。

Solution

image.png 把原来的线性chain改成了一个环形结构hot ring，保证hash bucket的head指针动态指向链中的hot item来提升read的速度。（那万一有好多个hotspot咋办？文章实验里说一条冲突链5-10个item，一般只有一个hotspot）

这样的设计引出几个新问题：

  • 环上数据会变化，怎么终止遍历
  • 热点的动态感知怎么实现，因为热点会不停变动
  • 对结构的改动影响并发，怎么实现无锁
  • 太热了，环上有语义上的多个热点怎么办

有序环

用环上的key做有序环，来判断miss（则不需要reach ring’s end）。
这里做一个trick，为了降低遍历的时候比较key的开销，先用一个短的tag值做预比较排序，相同再用key做排序。
image.png 把hash结果的前k位用来分bucket，后n-k位做tag。

热点感知策略 Hotspot Shift Identification

image.png

Random Movement Strategy

每个线程维护一个thread local的计数器，每当处理R个request后，会判断当前的访问的item是不是在collision chains head上，如果在，那么不做任何处理，如果不在，那么让head指向当前访问的item，也就相当于当前命中的item转变成了hotspot item。
依赖概率的一个高效操作，低R值会导致震荡，文章R设为5。

Statistical Sampling

每R次访问，尝试采样对应的chain，统计item的访问频率。
热点继承：若第R次访问的item已经是头指针指向的item，则不启动采样。
用了指针数据的末端来做counter等标记位，没有占用额外空间。
具体采样过程之后补充。。。

无锁并发访问

实现主要参照A Pragmatic Implementation of Non-blocking Linked-lists，Lock-free linked lists using compare-and-swap。主要是实现了对于索引链表的并发性操作的维护。
待补充…(*因为fatcache的索引操作是单线程，靠多实例来维护并发性，暂时不写这部分了……

适应热点数据量的无锁rehash

多个热点，那就增大hashtable，做rehash。设置一个平均每次访问所需内存访问次数的阈值（文章为2），触发就rehash。 image.png

initialization

先把用来分bucket的位数往后增加一位（复用tag的最高一位），即翻倍hashtable的大小，一个老head对两个新head。
然后根据剩下的tag，数据根据范围$[0,T)$切分两半$[0,\frac{T}{2}),[\frac{T}{2},T)$，分给两个新head。
具体的切分操作如下：
创建一个rehash node，包含两个空数据的item（被两个新head指向），一个tag=0，一个tag=T/2。

Split

把两个空item插入来完成分裂。如图所示，B和E作为边界的节点，他们的前面被插入。注意图上的指针变化。
完成了此步之后，就可以对新hashtable进行访问了。

Deletion

回收旧hashtable、俩空item（注意图上指针的变化）。

note: 感觉在做split的时候，要保证老访问全部返回了，再上锁split。
但原文说”Note that the transition period only blocks the rehash thread, but not access threads”，不太理解…

Refer

FAST ‘20 - HotRing: A Hotspot-Aware In-Memory Key-Value Store on Youtube
看了几篇FAST 2020 – 暗淡了乌云 知乎专栏
前沿 | 最快KV引擎！存储顶会FAST’20论文揭秘Tair创新性引擎

Search

    Table of Contents