CoCache:基于文件关联性的协同缓存策略

孟 子 潇

(复旦大学计算机科学技术学院，上海市智能信息处理重点实验室 上海 200433)

0 引 言

在大数据时代，对数据进行存储及处理所需要的资源往往会远远超出单台机器的存储容量和处理能力，因而采用分布式平台对数据进行存储和处理成为人们不二的选择。分布式环境中数据会被分散到多台机器存储，对数据的处理也会由多台机器并发地进行，但是出于对数据存储持久性以及经济性的考虑，通常将数据存储分散到不同机器的磁盘中，并在对数据进行处理的时候从磁盘中读取数据，这样就导致了数据读取与处理之间的性能鸿沟。随着内存技术的发展，购置单位内存资源所需要花费的成本大幅降低，机器所配置的内存容量也随之大幅提升，人们也逐步通过对数据进行缓存的方式来提高对大数据集的处理效率，因而人们逐渐开展了针对大数据集在分布式环境中的缓存问题的研究。

然而，人们往往需要同时对多个数据集进行处理才能完成某一项任务，也就是说数据集与数据集之间是存在关联性的。但是现有的缓存框架及算法都较少地考虑数据集之间关联性，而是把每个数据集当作独立的缓存单元进行考虑，这样就会导致多个相互关联的数据集只有一部分被缓存，使对多个关联数据集进行处理的一个计算任务在处理数据的时候仍然需要从磁盘读取没有被缓存的数据集，从而引起数据缓存效果的下降，导致数据读取与处理之间的性能鸿沟依然存在，使得对数据进行缓存的意义大大降低。因此，分布式环境对数据进行缓存的时候需要把数据的关联性考虑在内，而不能只把每个数据集作为单独的缓存对象进行考虑。

文献[1-2]使用类似HDFS[3]的管理方式来管理缓存，在底层分布式文件系统的基础上，实现了一个额外的缓存层。文献[4]进一步实现了一个基于内存的分布式文件系统，在HDFS和上层应用间增加一层文件缓存机制，同时为了保证数据一致性和可用性，引入Lineage和Checkpoint机制，是一个专门为大规模数据处理而设计的系统。文献[5]提出了一种动态放置数据文件的策略，可以在HDFS实现联合定位。文献[6]提出可以将所有数据放在内存中提供服务，以获得更优的效率。在文献[7]发现了并行计算All-or-Nothing的特性，即在进行并行计算时，部分缓存对计算效率没有帮助，要么都进行缓存，要么都不进行缓存，为本文提供了重要思路。文献[8-11]是针对基本缓存策略LRU、LFU、FIFO等的分析和一些改进优化。

本文提出一种基于文件关联性的协同缓存策略，称为CoCache。主要工作包含：1) 提出数据集关联性的量化计算方式；2) 根据数据集关联性的元信息，提出了协同缓存策略；3) 实现CoCache的原型，并在其上进行实验验证方案的有效性。

1 系统框架与算法设计

在同时处理有关联的两个数据集时，首先需要考虑关联性的定义，然后基于数据集之间的关联性，CoCache实现了一种协同缓存方案，即在缓存数据集的时候，不单是考虑该数据集本身的元信息，而是结合和它相关的其他数据集。

本节将首先介绍CoCache的总体框架设计，然后提出关联性的定义方法和在缓存替换过程中的具体算法。

1.1 系统框架设计

CoCache是一个块式存储系统，整体框架如图1所示，虚线框内是核心部分，系统由一个中心的Master节点和多个位于存储节点上的Worker节点以及底层文件系统(UFS)组成，其他部分由用户管理。Master节点负责进行缓存控制，根据预处理模块提供的分块和索引的基本信息，将元数据信息存储到自己的工作内存中，并且在计算过程中，根据任务管理器提供的查询需求，进行缓存调度控制；Worker节点负责将数据块返回给用户以及从底层文件系统读取数据，并且由Master节点调度，进行缓存控制；底层文件系统负责存储数据集。

图1 系统架构图

整个工作流程分为以下几个部分：1) 底层文件系统获取到数据集，并且由预处理模块进行分块，建立索引，并将预处理结果通知Master节点。2) 任务管理器发起查询，Master节点接收到查询请求，在索引中查找对应的数据块，并向Worker节点请求该数据块，与此同时，告知Worker节点缓存调度信息。3) Worker节点接收到Master节点的元信息后，将尝试从缓存中读数据块，如果读到，则将数据块返回任务管理器；如果缓存中不存在该数据块，则从底层文件系统中读取并返回给任务管理器，同时根据缓存调度信息，决定缓存内容和方式，该部分会在1.3节中详细描述。4) 任务管理器接受到数据块后，计算出结果。当再次执行查询任务时，重复以上2至4步骤。

1.2 数据集的关联性

CoCache的第一步，就是要定义数据集之间的关联性。在这里，本文先考虑两个数据集之间的关联性。表1列出了在此过程中用到的参数及其定义。

表1 参数定义

数据集Da和Db都是数据库表，它们在某一列上有相同的属性Sab，关联性针对Sab定义。将Da和Db按照Sab排序后，把Da和Db按照每块大小M分成多块，分别是A1，A2，…，Am和B1，B2，…，Bn，对每一块，可以得到该块在S属性上的范围AiS(xai,yai)和BjS(xbj,ybj)。对此，数据集A第i块和数据集B的第j块的关联系数通过如下方式计算：

1) 当[xai,yai]∩[xbj,ybj]=Ø时，F(Ai,Bj)=0。

2) 当[xai,yai]∩[xbj,ybj]≠Ø时，令[xai,yai]∩[xbj,ybj]=[x,y]，可计算出Mai(x,y)和Mbj(x,y)，则：

根据上述定义，由于数据集A和数据集B都要进行排序，有如下优化方式来计算出各块之间的关联系数。

从头开始，对数据集A和B同时扫描，Sab字段较小的指针往下扫描，直到一个块结束。可以计算出当前对应块之间的关联系数，然后标记当前位置，作为下一个迭代的起始位置，继续扫描，直到文件结束。未计算的块之间的关联系数均为0。通过这种方式可以不必计算所有块，使得寻找关联系数的复杂度从O(n2)变为O(n)。

1.3 协同缓存策略

协同缓存策略是基于数据集关联性的缓存策略，是在基于已有的缓存策略上，对部分有关联性的块进行绑定缓存，因此在协同缓存之上有一个基本的缓存策略，如LRU、FIFO等。

查询任务的执行过程和缓存替换策略如图2所示。任务管理器发起读请求，Master节点根据索引，找到要读取的块集合I，然后查看其是否全部在缓存中，如果是，直接从缓存中读取并返回；如果不是，则从底层文件系统中查找I以及与其相关的块集合P，将其存在缓存中并返回。在此，本文定义一个List，用于保存即将被替换的块的元信息。当涉及到缓存替换时，首先检查List里的块数量是否充足，如果不足，则通过总体缓存策略选出第一个被替换的块，然后将该块及与其相关的块，也加入List中，再次检查List的块数量，直到满足替换要求。

2 实验分析

本文基于Tachyon实现CoCache的原型，使用HDFS作为底层文件系统。Master节点和Worker节点均是Amazon EC2 m4.2xlarge型号机器，其中一台Master节点，四台Worker节点。每个节点的配置为32 GB内存，其中工作内存占用12 GB，剩下20 GB作为缓存资源；总共分配80 GB作为缓存数据的资源。

图2 协同缓存流程图

实验主要通过执行多次查询操作，来对比使用和不使用CoCache时，查询操作的总时间，缓存命中率。

每次测试的查询操作混合了若干个单表查询和多表join查询。在实验中对比了不同参数对结果的影响，包括数据集大小，关联性阈值T，块大小M。

2.1 数据集预处理

由于CoCache是对有关联性的数据集进行处理，所以使用的两个数据集为形式，且它们的key为同一字段。按照如下方式进行预处理。1) 将数据集按照key进行排序；2) 将数据集按照数据块大小分成若干块，并取出该数据块的第一个key作为标识，为数据块建立索引；3) 根据数据块key的范围，计算出关联系数F(Ai，Bj)，显然关联系数F矩阵是一个稀疏矩阵，所以采用邻接表的形式存储；4) 把排好序的两个数据集存入底层文件系统，同时把数据块的索引信息和关联系数邻接表存入Master节点。

本实验所采用的数据集为日志信息，以时间为key，日志内容为value，且已排序。使用索引能够快速地定位到查询所需要的数据块，避免过多的磁盘扫描。通过关联系数邻接表，可以在进行缓存的过程中，快速准确地找出与目标块相关联的块。为了更好地对比缓存对实验结果的影响，实验预先把数据集前部分数据存入缓存中。

2.2 总体运行时间和缓存命中率的对比

实验分别设置了几组不同大小的数据集(数据集A和B大小相同)，将阈值T设置为0.5，块大小设置为128 MB，然后比较了使用Tachyon和使用CoCache时的总体运行时间和缓存命中率，得到的结果如图3和图4。可以发现当数据集大小小于缓存资源大小时，两者并无区别，但是一旦超过这个数值，CoCache在运行时间和缓存命中率上的表现都优于Tachyon。因为CoCache能够减少出现有关联的块一部分在缓存，一部分不在缓存的现象，使得下一次查询更大几率全部命中。

阈值和块大小的设置对整个查询也是有影响的，所以接下来将通过设置不同参数，来对比CoCache和Tachyon的性能。

图3 数据集大小对运行时间的影响

图4 数据集大小对缓存命中率的影响

2.3 阈值T对运行时间和缓存命中率的影响

为了比较不同阈值下CoCache的性能，实验从0.05到1设置7组不同的阈值(0.05、0.1、0.2、0.4、0.6、0.8、1)，通过分析可以知道，当阈值为1时，几乎没有两个块是具有关联性的，因此CoCache等同于Tachyon。在此使用两个100 GB的数据集，设置块大小为128 MB，在此环境下，对比了不同阈值的运行时间和缓存命中率，实验结果如图5。可以发现，随着阈值增加，缓存命中率越来越小，这说明了CoCache能够进行有效的缓存，使得更多的块命中。但是，运行时间并不是如此乐观，当阈值很小的时候，过多的块具有关联性，使得每次在替换块时，同时有很多块需要并行处理，造成了一定的IO阻塞，增加了运行时间。

图5 阈值T的影响

2.4 块大小的影响

在这一部分，实验将对比不同块大小对CoCache和Tachyon性能的影响。由上一部分可以看出，当阈值为0.2左右时，能够在运行时间上取得比较好的效果，所以在这一部分中，阈值设置为0.2，两个数据集大小也为100 GB，实验结果如图6所示。可以发现，不管采用何种大小的块，CoCache的运行时间都优于Tachyon。同时还发现，当每块越小时，运行时间越快，因为每次查询时，索引能够更准确地找到相应的块，以及与此同时被缓存的“无用信息”会变少。但是这一部分还是受到上层查询的范围的影响，如果每次查询覆盖的范围是抖动的，会导致查询读取的块个数也是抖动的，块大小的影响就会逐渐消失。

图6 块大小的影响

3 结 语

随着大数据查询应用的增加，利用分布式缓存来对运算进行加速已成为共识，而多数据集的查询任务越来越多，为了更好地利用缓存资源，本文提出的基于文件关联性的协同缓存策略，已经开始解决这一部分问题，并且取得了一定的成果。对比实验表明，CoCache可以提高数据缓存效率，减少查询时间。