冷热数据浅浅见_冷热数据识别原理

一、前言

这个星期看了关于目前数据存储中关于冷热数据的一些相关内容。 所谓冷数据，简单来说就是在一段时间内访问的比较少，接下来的一段时间访问的概率也不是很大。相反的是，热数据，就是在一段时间内访问的较多的数据，它们在接下来的时间内访问的概率也会非常大。

在互联网中，很多业务对数据的访问并不是均匀的，而是呈现相对的数据访问倾斜（skewed workloads），会出现相对的hotspot。例如，下图为阿里巴巴在一篇论文中提到的阿里的业务场景中对一些key-value的访问，可以看到正常情况下50%的访问都是集中在1%的key上，而一些特殊场景（如双11等）90%的访问都是集中在1%的key上（We observe that 50% (daily cases) to 90% (extreme cases) of accesses only touch 1% of total items, which shows that the hotspot issue becomes unprecedentedly serious in the Internet era.）。

因此对冷热数据的研究还是很有必要的。

二、冷热数据的标准（判断）

那如何判断冷热数据呢？

就我这段时间的研究发现，冷热数据的判断大都基于两个标准：
（1）、访问的频繁度。 即在一段时间内对一个数据访问的越多，常理上我们越把它当成hot data。这个标准非常符合我们在之前的定义，也非常好理解。
（2）、访问的时效性。 即访问的数据越接近当前时间点，我们也可以从某种程度上把其当成hot data。因为大多数应用场景，都具有时间和空间的局部性（尤其是对于计算机领域来说），当前访问的数据，接下来访问的概率相对要较大些。

以上就是基本的判别标准，一些具体的应用算法也大都是根据上面的两个标准来划分冷热数据的。

三、判断冷热数据的算法

在具体的系统中，有不同的算法来预测接下来的冷热数据。 就我目前的理解来看，大体上分为三类：
（1）、基于数据结构特点的判别算法
（2）、基于统计学上的判断算法
（3）、基于机器学习的判断算法

下面分别简要介绍。

3.1 基于数据结构特点的判断算法

按照我的划分，基于特定数据结构的判断算法分为传统的方法和现代改进的一些算法。分类如下

3.1.1 传统的方法

传统的、经典的用于判断冷热数据的方式就是我们在操作系统上学到的一些页面替换算法。如LRU、LFU、OPT等等。 基本的概念、性质啥的这儿就不说了，这里主要谈点涉及到本主题的内容。

（1）、LRU（最近最久未使用）。 这种方式主要利用里数据的时效性，认为最近访问的数据接下来访问的概率会大些，所以更倾向于在内存中存放那些最近刚访问的数据（或者说是页面），同时淘汰那些已经很久没访问的数据。 但是这种算法没有考虑数据访问的频繁程度。
（2）、LFU（最近最少使用算法）。一字之差，意义可就完全不同了。 LFU算法考虑的是数据访问的频繁程度，访问越频繁的数据，系统会更倾向于把它当成热点数据保存。 同样，LFU只考虑了数据的频繁程度却没有考虑数据的时效性。

对于OPT,它是一种理想情况下的算法，这里不做讨论了。还有一些FIFO、CLOCK等页面淘汰算法和这里的主题不是很相关，暂且就不做讨论了。

3.1.2 改进的方法

传统的方法有一些缺点，在当前的数据架构上不是很合适，所以又出现了了改进的一些基于数据结构的算法，如LRU-k, 2Q、HotRing等等。同理基本的介绍部分，请参照文后参考的相关资料（我的水平估计没它们介绍的好）。

（1）、LRU-k。 这种算法算是前面LRU的改进版，从冷热数据的角度来看，它综合考虑了时效性和数据的频繁度。 冷热数据预测效果应该要比LRU要好，但是实现起来要稍微复杂些。

（2）、2Q。 这个算法本质上和上面的k取2差不多，都是多利用了一个队列来保护以前频繁访问但是最近未有访问的数据，也算是综合了数据的时效性和频繁程度。

（3）、HotRing.确切的说，这不是一种算法，而是一种新的数据结构。这是阿里在Tair（一种内存数据库）中使用的一种子组件。它本质上是一种改进的hash数据结构，把hash算法中的拉链变成了“拉环”。 在hash table中有一个head指针一直指向此环中（也就是冲突链中）最热的结点（确切的说是hotspot 附近的结点）如下图所示。

关于具体的实现过程可以学习参考【2】中论文。顺便说一点，我觉得这篇论文的精髓一个是在于采用了head 指针指向环中的热点，使得查找hash 冲突的结点所花费的时间缩减；另一个就是其统计采样策略，它并不是每隔一定时间进行采样，而是在hotspot失效的情况下重新进行一轮采样，从而确定新的热点，这种方式从一定程度上提高了系统的性能。

3.2 基于统计学上的判断算法

以上的几种算法都是利用特定的数据结构来进行热点数据的判别的。 我了解到的资料中还有一些是利用统计模型来判断冷热数据的。 这种方式，大都根据数据的访问特征提出了一个算法模型，然后利用这个模型来进行冷热数据判别。

如paper【5】中提出了一种基于指数平滑的冷热数据识别方法，通过指数平滑来预测一个数据未来被访问的可能性。

paper 【6】中，创新的把温度的冷热和数据的冷热结合关联在里一起，利用牛顿冷却定律推导出了一个温度数据模型。

具体的算法请参考相应的论文，这里就不阐述了。

3.3 基于机器学习的判断算法

对于这种方式，就是利用机器学习算法，来进行学习，从而来预测数据的在接下来访问。 这几年机器学习、深度学习这么火，应该对这点研究的也挺多的了。 无奈的是，这目前不是我的强项，这里也就不说了╮(╯▽╰)╭。

四、总结

冷热数据的研究，包括前面总结的负载均衡的研究本质上就是为了提高系统的性能。From a high level, 这都是资源的调度和配置，根据一定的规则和限制，把数据资源放到其该放的地方，从而达到效率、性能等的最大化。

对于此，任重而道远。。。。

五、参考

【1】、LRU-K和2Q缓存算法介绍
【2】、HotRing: A Hotspot-Aware In-Memory Key-Value Store
【3】、HotRing论文阅读笔记
【4】、深度 | HotRing: 阿里缓存系统Tair的自感知热点数据子组件
【5】、Identifying Hot and Cold Data in Main-Memory Databases
【6】、基于数据温度的冷热数据识别机制研究