数据库系统中，数据访问特征直接影响到索引、冷热数据分离机制的效率。如果能根据历史SQL访问特征，准确预测出接下来哪些数据会被访问，便可提前将数据从低速介质(SSD/HHD)迁移至高速介质(Memory/CPUCache)，从而缩短数据访问时延。同时识别出数据冷热特征之后后，可以根据数据的冷热特点来构建索引，进一步提高整体性能。
前言
阿里巴巴集团业务的数据访问具有典型的冷热特征。以交易场景为例，数据访问的热点分布十分明显并随时间推移。对于一条新插入的记录，在接下来7天内被访问到的概率高达99%，而在7天之后的访问概率非常低。对于热点数据，现有的机制是通过LRU或者Clock等策略在内存中维护一块缓冲区，所有的读操作都会首先访问缓冲区，没有命中的话再去磁盘中读取，然后将数据缓存在缓冲区中。这种策略的缺点在于无法捕捉到更为复杂的数据访问特征，数据访问特征的记忆窗口等于缓冲区的大小，因此当数据的访问特征较为复杂，需要更长的窗口才能捕捉到特征时，就会造成较多的cachemiss，从而使数据库性能产生抖动。
《LearningMemoryAccessPatterns》提出了使用深度学习训练得到prefetcher，通过对内存访问的物理地址进行建模，使用RNN来捕捉内存访问的较为复杂的时序特征。LearnedPrefetcher和传统的硬件Prefetcher相比具有更高的准确率和召回率。虽然论文中的LearnedPrefetcher基于静态数据进行训练，而且对动态更新RNN模型给系统正常事务带来的资源竞争也没有给出很好的解决方案，要在工业界落地还有很长的路要走，但是本文提出的使用深度学习训练的模型来替代传统模型的思想和近期的《TheCaseforLearnedIndexStructures》不谋而合，对人工智能和数据库结合这一新兴领域具有重要的启发意义。这篇文章对于X-Engine后续的智能冷热数据识别以及分离机制的设计也有很大的借鉴意义。
Prefetcher
Prefetcher是一种能够根据历史内存访问的特点来预测未来内存访问的硬件结构，主要分为以下两种类别：
1.Striderprefetcher，记录访问地址的差别(deltatable)来发现简单的访问规律，给定四个时间点程序访问的物理地址(0,4,8,12)，那么Striderprefetcher会预测接下来可能访问的物理地址为(16,20,24)，并将其prefetch到内存中；
2.Correlationprefetcher，相比于Striderprefetcher只能捕捉到简单的内存访问特征，Correlationprefetcher则会通过保存长时间的历史访问记录来分析得到更加复杂的内存访问特征，代表性的实现有Markovprefetchers，GHBprefetchers等，由于这种prefetcher需要较大的内存的空间来存储访存记录表，一般的现代处理器不会采用这种prefetcher实现。
RNN(RecurrentNeuralNetwork)
适用于序列预测的问题（sequentialprediction），诸如语音识别、自然语言处理等依赖较长历史维度数据来进行特征抽取的问题都比较适合RNN来处理。
LSTM（Long-ShortTermMemory）是RNN的一种变种实现，LSTM通过增加了遗忘单元和使用加法替代乘法进行中间状态的传输，解决了原始RNN中梯度消失的问题。
Prefetch模型
定义Prefetch对应的ML模型：根据历史的内存访问记录，预测未来哪些内存访问会命中cache，又有哪些访问会造成cachemiss。一个程序编译后包含很多机器指令，其中的访存指令（load/store）会导致内存访问。
特征，PC(PCCounters)(64-bit)，cachemiss地址(64-bit)
回归问题，直接预测下一个cachemiss的物理地址。巨大的物理地址空间带来稀疏性问题，在实验中出现O(10M)blockcachemiss，然而物理地址空间为2^64，对于NN而言，首先会对输入的特征进行归一化，然而浮点数的表示精度会导致信息损失。
多分类问题，预测每一个地址成为下一次cachemiss的概率，从中选取topK作为prefetch的对象。
稀疏性问题，即使在pagelevel进行预测也会有2^52个概率值(softmaxtargets)
程序的运行具有局部性的特点，根据trainingdata中程序经常访问的物理地址作为目标预测值，忽略其他的物理空间地址-EmbeddingLSTM
首先对cachemiss的地址进行聚类，然后对于每一个类别分别训练LSTM，使用LSTMID作为bias将所有的训练器关联起来-Clustering+LSTM
地址空间布局的随机性（ASLR），相同的代码段运行多次会产生不同的物理地址访问
预测cachemiss地址的变化值（delta）而不是实际地址
LearnedPrefetcher
1.EmbeddingLSTM
多次出现的delta子集（vocabulary）作为feature，训练集的大小为O()。
在第N时刻，PC和cachemiss的detla作为feature输入
embedding后concatenate起来作为input，传入2-layerLSTM
LSTM预测出来TopK个delta作为prefetching的候选集
Tradeoff：预取多个预测值会增加下个时刻的cache命中概率，但由于cache大小有限，有可能把有用的page置换出去论文中设置为prefetchtop10的物理地址
Limitations：vocabulary大小决定了模型的复杂度对于vocabulary进行剪枝损害了模型的效果对于较少出现的delta值的处理是一个难点。
2.Clustering+LSTM可行性：对于一段程序而言，大部分地址空间的访问都存在局部性（结构体、数组都被存放在连续的地址空间），因此对于局部地址空间进行建模可能会取得较好的prefetch效果。
聚类可视化，在omnetppbenchmark上对于（PC,address）进行聚类，聚类之后delta变小。
Clustering+LSTM的架构如下图所示，所有特征进行聚类后经过localLSTM的训练得到最后的预测结果，这里仍然采用分类问题的解决方案，如果使用回归算法，denomarlization后会造成预测地址的精度损失。
两种模型的比较
Clustering+LSTM模型将整个LSTM拆分成几个较小的localmodel，在每一个region的delta都在一个量级，可以normalize后直接作为LSTM的输入，大大降低了embeddingmatrix的维度。
Clustering+LSTM模型着重localLSTM的建模，然后通过ClusterID作为bias将所有的localmodel松耦合起来进行训练，和EmbeddingLSTM相比，对于整体的模型建模（程序对于不同region的动态访问）表达能力不足。
实验
实验准备
Pin工具提供了对于指定进程生成（PC,VirtualAddress）的功能；
我们