1. 问题背景

目前，很多分布式存储系统以磁盘作为存储介质，严重降低了运行在分布式存储系统上层大数据应用的数据访问效率。因此，有研究者提出了以内存为中心的分布式存储系统，充分利用内存来加速数据访问，并采用基于MEM-SSD-HDD的分层式存储结构来扩展总体存储空间。其中较为典型的便是Alluxio分布式存储系统。但是，Alluxio并没有进一步研究更多高效的缓存策略以便针对不同应用场景提升数据在内存中的访问命中率。

鉴于上述研究工作的不足，我们基于分层式大数据存储系统进一步研究高效的缓存调度策略和综合调度算法来提升大数据应用在内存中的数据访问命中率，从而有效提升大数据应用的I/O效率。

2. 系统总体架构

面向分层式大数据存储系统，我们提出一种通用化缓存调度框架。该框架自上而下包含五层结构，分别为大数据应用层、数据访问模式层、缓存策略自适应调度层、缓存策略层以及分层式大数据存储系统层。

图 1 基于分层式大数据存储系统的通用化缓存调度框架

3. 技术实现方案与优化

3.1 缓存策略

我们研究提出了一种缓存替换策略的通用化调度框架，并在此基础上设计实现了一组覆盖多种数据访问模式的缓存替换策略，包括LRU、LRFU、LIRS以及ARC。

图 2 缓存替换策略的通用化调度框架

我们研究提出了一种缓存提升策略的通用化调度框架，并在此基础上设计实现了一种高效的缓存提升策略WLFU，可以自适应将低性能存储设备上的热数据块提升到内存。

图 3 缓存提升策略的通用化调度框架

3.2 基于命中率的自适应调度算法

基于命中率的自适应调度算法主要包含Trace收集、Trace分析以及策略切换三个阶段。

图 4 基于命中率的自适应调度框架

1. Trace收集阶段：采用基于滑动窗口的方式收集大数据应用的数据块访问记录，滑动窗口每向后滑动K次，进行一次命中率分析和策略切换判断。
2. Trace分析阶段：主要分析不同缓存策略在当前窗口中的命中率。系统为每个策略模拟单独的执行环境，动态监测各个策略命中率的变化。
3. 策略切换阶段：负责将当前运行的缓存策略切换为具有最高命中率的候选策略。

3.3 基于数据访问模式的自适应调度算法

基于数据访问模式的自适应调度算法采用机器学习的方法进行缓存策略自适应调度，包括线下模型训练和线上模型预测两阶段。

图 5 机器学习方法进行自适应调度的总体工作流程

1. 线下模型训练：线下模型训练阶段，首先采用滑动窗口的方式扫描大数据应用的离线日志文件，窗口每向后滑动K次，抽取一次窗口内的特征，特征标签为在窗口内取得较高命中率的一个或者多个缓存策略。窗口扫描完成后，便可得到一系列的特征和特征标签。使用Softmax回归模型可以训练出一个多分类器，将训练完成的模型参数写入本地文件系统。
2. 线上模型预测：线上模型预测阶段，首先在系统启动时从本地文件系统加载训练完成的模型参数，初始化Softmax多分类器的假设函数。然后，系统运行时依然采用滑动窗口的方式在线收集数据块访问记录，并抽取特征。根据Softmax多分类器的假设函数预测使用哪种缓存策略取得效果最好，在下一窗口开始之前将运行策略切换为预测概率最高的候选策略。

4. 性能评估分析

4.1 缓存替换策略实验性能评估

我们研究设计出一组覆盖多种数据访问模式的缓存替换策略，包括LRU、LRFU、LIRS以及ARC。通过评估缓存替换策略在各个数据访问模式以及KMeans、PageRank、SQL等大数据应用的命中率和执行时间，可以发现每个缓存替换策略都能够在特定场景加速大数据应用的数据访问。

图 6 缓存替换策略在各个数据访问模式的命中率和执行时间

图 7 缓存替换策略在各个大数据应用的命中率和执行时间

4.2 缓存提升策略实验性能评估

我们提出了一种高效的缓存提升策略WLFU，自适应将低层存储设备的热数据块提升到内存。CACHE方式表示不提升任何数据块到内存，而CACHE_PROMOTE方式表示提升任何读取到的数据块到内存。通过循环读文件、WordCount以及SQL应用这几组测试用例，我们可以发现WLFU提升策略相比于其他数据块提升方式具有明显的优势。

4.3 缓存策略自适应调度算法实验性能评估

我们通过KMeans、Bayes、WordCount与SQL（trace1）的混合应用、WordCount与SQL（trace2）的混合应用这几组实验对比LRU、LRFU、LIRS、ARC、基于命中率的自适应调度算法（图中的Hit Rate）以及基于数据访问模式的自适应调度算法（图中的Model）的性能。

（1）KMeans应用：基于数据访问模式的自适应调度算法最优，基于命中率的自适应调度算法性能次之。

图 11 KMeans应用的命中率和执行时间

（2）Bayes应用： LIRS性能最优，基于数据访问模式和基于命中率的自适应调度算法性能次之，主要因为它们初始策略为LRU，需要经过一段时间的自适应调整。

图 12 Bayes应用的命中率和执行时间

（3）WordCount与SQL（trace1）的混合应用：基于命中率和数据访问模式的自适应调度算法性能相当，都明显优于其他单个缓存策略。

图 13 WordCount与SQL（trace1）混合应用的命中率和执行时间

（4）WordCount与SQL（trace2）的混合应用： LIRS性能最优，基于命中率和数据访问模式的自适应调度算法性能次之，主要是因为它们需要经过一段时间的自适应调整。

图 14 WordCount与SQL（trace2）混合应用的命中率和执行时间

5. 总结

我们针对分层式分布式存储系统进行研究，设计了高效的缓存调度策略和综合调度算法，提升了复杂应用的数据访问性能。主要贡献点包括：

1. 研究提出了一种可扩展的通用化缓存替换策略调度框架，并在此基础上设计实现了一组覆盖多种数据访问模式的缓存替换策略，以适应更多复杂的大数据应用场景。
2. 研究提出了一种可扩展的通用化缓存提升策略调度框架，并在此基础上设计实现了一种高效的缓存提升策略，自适应将低性能存储设备上的热数据块提升到内存。
3. 针对单个缓存策略难以适应所有大数据应用场景的情况，研究设计了两种缓存策略的自适应调度算法，即基于命中率的自适应调度和基于数据访问模式的自适应调度。
4. 以分布式内存文件系统Alluxio为基础，设计实现了包含上述通用化缓存调度框架、缓存调度策略以及缓存策略自适应调度算法的原型系统。