问题背景
数据热点：热点问题在in-memory KVS中被忽视了。从阿里巴巴生产环境的in-memory KVS中，本文发现50%～90%的请求只访问了1%的items。
为了解决热点问题，有以下的思路：
文章提出了一种HotRing的热点感知KV数据结构，它具有以下特性：
- ordered-ring hash。把热点数据靠近头节点以快速访问
- 提供轻量级、运行态的热点迁移检测策略
- Lock-free设计
- read 565M ops，2.58X性能提升
解决方案
Ordered-ring hash index
关键设计点：
- 顺序 - ring：为了在查询ring时，可以及时找到 key ，或及时退出（找不到key）
hash(key) 的值，被分为两个部分，前 k 位被用于定位这个 key 所在的 hash 桶，后(n-k) 位被认为是 key 的 tag。这样是为了避免比较两个比较大的 Key。
并且作者定位了一个顺序：order_k = (tag_k, key_k)，就是先比较 tag，然后才是 key。并且给出找到 key 和没有找到 key 的判断标准：
其中 （5） 的后面两个不等式，考虑的是一个环上，首尾相接的位置。因为一般来说，环上的后一个 order 总是大于前一个 key 的 order，但在环的首尾相接的位置，会发生一个“突变”，例如下图中，F 的后续是 I，但是 I 的 order < F 的 order
Hotspot Shift Identification
热点可能会发生变化，论文提出两种更新热点的方式。
Random Movement Strategy
这种方案比较简单，每 R 次访问，尝试更新一下 head 指针，指向第 R 次访问的”热点“。
这种方式带有一定随机性，如果数据访问足够倾斜的话，效果不错，否则可能准确率不高。
Statistical Sampling Strategy
从名称可以看出来，这种方案下，需要利用一定的统计数据来做出判断。
由于每个环中，既保留了环的整体访问次数，又保留了每个 item 的访问次数，由此我们可以计算出每个 item 的访问比例，并且定义一个 imcome 值，代表将头指针指向位置 t 的平均内存访问次数：
最终选择能让 W_t 最小的头指针位置。
并发控制
具体见论文，主要是一些lock free的技巧，这里不再详细展开。
参考资料
https://www.usenix.org/system/files/fast20-chen_jiqiang.pdf
https://developer.aliyun.com/article/746727
