Alibaba HotRing

[levy5307]

https://levy5307.github.io/blog/HotRing/

从阿里巴巴内部观察来看，50%~90%的请求只访问1%的数据。热点现象越来越严重，有如下几个原因：

线上活跃用户数越来越多。一个实时时间（例如降价促销、爆炸性新闻）会在短时间内对少量数据带来大量的访问。


应用所依赖的底层架构越来越复杂，一个小的bug有可能导致重复访问同一个数据。

当前有许多数据结构用于实现KV存储服务，例如：skip list、Masstree及hash。但是没有大多数的数据结构没有意识到热点，其对于热点的访问和其他数据一样，需要同样的访问次数，这会严重影响系统的性能。例如，Hash是KV存储中使用最多的场景，下图中有一个hash table，另外对每个hash entry都有一个collision chain。上面讲到hash是对热点无意识的，所以热点会散落在collision chain上，如果一个热点数据存放在链的最末尾，那么每次都热点数据的操作都需要很多次内存访问，从而降低整体性能。

针对这种情况，目前有两种方法：

CPU缓存。CPU缓存可以提高对热点数据的访问，然而CPU缓存量很小的，只能保存很少量的数据。


Rehash。通过扩大该hash的容量，并进行rehash来减少collision的长度。但是当该hash占据内存空间已经很大时，则不可以采用该方法了。

因此目前的解决方法都很局限，所以一种hotspot-aware的数据结构是很有必要的。当然，要实现它有几个挑战：

Hotspot Shift

访问模式会随着时间不断变化，因此我们需要一种轻量级的方法来跟踪热度的变化。

针对这一点，该论文中避免了对collision chain的重排序，而是通过移动头指着的方式来实现。为了确保头指针移动后，桶中的所有项都是可访问的，其将collision chain替换为有序环结构，即HotRing

Concurrent Access

每个热点都被大量并发请求访问。因此为了保持令人满意的性能，对读/写操作都支持高并发是至关重要的。

对于这一点，无锁结构是一个经典的解决方案，其避免了锁和同步操作带来的开销。HotRing对hotspot shift、头指针移动以及rehash都采用了无锁方案。

HotRing设计