高速缓存替换策略的动态选择方法

1.高速缓存替换策略的动态选择方法，其特征在于：所述方法是在高速缓存存储器系统内的一个数字集成电路上依次按以下步骤实现的：
步骤(1).初始化，设置以下模块：
高速缓存替换策略模块，高速缓存服务模块，访问记录采集器模块以及访问记录分析器模块，其中：
1)高速缓存替换策略模块，设立以下接口描述命中和替换时的逻辑：
a.初始化接口，为用户指定的或第一次运行时确定的或切换后的当前高速缓存策略模块分配内存，初始化数据结构；
b.释放用接口，释放即将被替换的高速缓存替换策略模块，包括释放数据结构和内存，供被替换的高速缓存替换策略模块卸载时使用；
c.更新用接口，当高速缓存数据块被命中时，更新该块的优先级；
d.插入用接口，当插入新的高速缓存数据块时，设置该块的优先级；
e.替换用接口，取优先级最低的高速缓存数据块为被替换块时使用；
所述高速缓存替换策略模块共有以下五种：最近被使用，双队列，多队列，自适应低负载和低最近相关度，各有一个固定的入口函数register，以便把自己的接口实现注册给所述高速缓存服务模块，
在各高速缓存替换策略模块中，处于运行状态的为当前高速缓存替换策略模块，其余则为候选高速缓存替换策略模块；
2)高速缓存服务模块，把包括磁盘在内的低速存储设备的数据缓存在内存中，当用户访问数据时直接进行内存访问，该高速缓存服务模块设有：高速缓存数据、高速缓存元数据以及哈希表，其中
a.高速缓存数据，是缓存好的磁盘数据，被分成多个固定大小的高速缓存数据块，块的大小为4KB，
b.高速缓存元数据，用于维护和管理所述高速缓存数据，其中包括：
1)每个高速缓存数据块的物理地址；
2)每个高速缓存数据块符号位用于标志该块是否已被写入磁盘；
3)一个最近被使用队列，用于记录所述高速缓存数据块的优先级顺序；
c.哈希表，以所述高速缓存数据块的地址作为关键字，对应的高速缓存元数据为数据，构成一个数据查找表，用于确定一个高速缓存数据块是否在所述高速缓存存储器中；
所述高速缓存服务模块依次按以下顺序实现高速缓存服务：
a.当用户访问数据时，该高速缓存服务模块首先根据其中数据给定的高速缓存数据块的地址查找哈希表；
b.若所述地址已在哈希表中，则高速缓存命中，通过更新用接口，调用所述当前高速缓存替换策略模块的命中功能，直接访问高速缓存，读出数据返回给用户；
c.若地址不存在于哈希表中，则为高速缓存缺失，判断高速缓存数据块是否已全部被占用：
若未全部被占用，则取出一个未占用的高速缓存数据块，通过所述插入用接口，调用所述当前高速缓存替换策略模块的插入功能，把数据调入所述未占用的高速缓存数据块，
若高速缓存数据块已用完，则通过替换用接口，调用所述当前高速缓存替换策略模块的替换功能，找到一个在所述高速缓存数据块中优先级最低的高速缓存数据块作被替换块，把数据读入替换出的高速缓存数据块，再返回给用户；
3)访问记录采集器模块，记录从所述高速缓存服务模块输入的访问信息，其中包括：磁盘号、访问地址和大小，先存储在内存缓冲区中，当存满时，把这些访问信息写入到磁盘文件中；
4)访问记录分析器模块，从所述访问记录采集器模块收到已采集到设定的n条访问记录的信息后，把各访问记录依次导入各候选高速缓存替换策略模块，记录所述各候选高速缓存替换策略模块的命中次数，取命中次数最多的候选高速缓存替换策略模块为最优策略模块，把结果通知所述高速缓存服务模块；
步骤(2).依次按以下步骤执行高速缓存替换策略的动态选择方法：
步骤(2.1).初始化高速缓存服务模块：
分配和初始化所有高速缓存数据块；
分配和初始化所有的通用高速缓存数据块描述符，所述高速缓存数据块用于记录该高速缓存数据块的地址和符号位，“通用”两字是指各高速缓存替换策略模块都需用到的；
初始化哈希表和最近被使用队列；
步骤(2.2).当前高速缓存替换策略模块的初始化：
步骤(2.2.1).确定一个高速缓存替换策略模块为当前高速缓存替换策略模块：
当由用户指定时，默认取上次运行结束时所用的高速缓存替换策略模块；
当第一次运行时取最近被使用高速缓存替换策略模块；
步骤(2.2.2).高速缓存服务模块调用所述register函数注册该当前高速缓存替换策略模块，再通过初始化接口初始化所述当前高速缓存替换策略模块；
步骤(2.3).在用户访问数据时，高速缓存服务模块按步骤(1)所述方法插入用户访问数据为高速缓存数据块；
步骤(2.4).访问记录采集器采集用户访问记录；
步骤(2.5).访问记录分析
当访问记录采集器采集到所述n条访问记录后，由访问记录分析器模块通过自己设定的一个虚拟的高速缓存服务模块来记录当访问记录依次访问各候选高速缓存替换策略模块时的记录命中次数，挑选命中次数最高的候选高速缓存替换策略模块为最优策略模块；
步骤(2.6).切换高速缓存替换策略模块，
首先高速缓存服务模块通过当前正处于运行状态的高速缓存替换策略模块的释放用接口释放策略元数据，所述策略元数据是指各高速缓存替换策略模块所特有的元数据；
然后，高速缓存服务模块通过访问记录命中次数最高的那个新的高速缓存替换策略模块的初始化接口分配新的策略元数据空间；
最后，高速缓存服务模块通过新的高速缓存替换策略模块的插入用接口把高速缓存中已有的高速缓存数据块依次导入新的高速缓存替换策略模块以重建新的策略元数据。
2.根据权利要求1所述的高速缓存替换策略的动态选择方法，其特征在于，所述的访问记录采集次数n＝1,000,000。
3.根据权利要求1所述的高速缓存替换策略的动态选择方法，其特征在于，在执行完步骤(2.6)后，若本轮为第一轮，则返回步骤(2.4)。
4.根据权利要求1所述的高速缓存替换策略的动态选择方法，其特征在于，在执行完步骤(2.6)后，若本轮策略选择得出的与上一轮相同，则结束，否则，转步骤(2.4)。
5.根据权利要求1所述的高速缓存替换策略的动态选择方法，其特征在于，在执行完步骤(2.6)后，卸载高速缓存服务模块。

技术领域\n高速缓存替换策略的动态选择方法属于存储系统领域，尤其涉及其中的高速缓存领域。\n背景技术\n高速缓存替换策略的动态选择方法是指：目前已有的高速缓存替换策略很多，不同的策略在不同的负载上有不同的效果；本方法根据负载的变化动态地选择最适合当前负载的高速缓存替换策略，并进行在线切换，从而提高存储系统高速缓存的命中率，最终提高存储系统的整体性能。传统的高速缓存替换策略有的专门针对某些特征的负载或环境，如智能写(WOW)策略针对写操作比较昂贵的RAID5等设备，而双局部性策略(DULO)在顺序写为主的负载上有较好的效果。对于未知的或变化的负载来说，很难从这些策略中进行选择。另外一些高速缓存替换策略可以根据负载的变化自适应地调整自身，如自适应低负载策略(ARC)，多队列策略(MQ)等，这些策略可以取得普遍比较好的效果，但在特定负载上无法得到最好的效果。于是有人提出了从多个高速缓存替换策略中选择的思想，自适应多专家策略(ACME)提出了多专家系统用于高速缓存替换策略的选择，但它的CPU和内存开销都比较大，且缺少实现验证。\n本发明提出了一种新的高速缓存替换策略的动态选择方法，通过异步策略选择将策略选择的过程和普通的高速缓存访问流程分离开来，从而降低了CPU和内存开销，通过在线策略切换将选择结果立即投入使用，以尽快提高性能。\n发明内容\n本发明的目的在于提供一种能适用于多种高速缓存系统的替换策略选择方法，能够从多个候选高速缓存替换策略中选择最适合当前负载的策略并进行在线切换，从而提高系统的性能。同时尽量减小选择过程带来的CPU和内存开销。本发明的重点在于高速缓存替换策略的模块化设计和在线切换，以及最优高速缓存替换策略的动态选择过程。\n本发明的特征在于：所述方法是在高速缓存存储器系统内的一个数字集成电路上依次按以下步骤实现的：\n步骤(1).初始化，设置以下模块：\n高速缓存替换策略模块，高速缓存服务模块，访问记录采集器模块以及访问记录分析器模块，其中：\n1)高速缓存替换策略模块，设立以下接口描述命中和替换时的逻辑：\na.初始化接口，为用户指定的或第一次运行时确定的或切换后的当前高速缓存策略模块分配内存，初始化数据结构；\nb.释放用接口，释放即将被替换的高速缓存替换策略模块，包括释放数据结构和内存，供被替换的高速缓存替换策略模块卸载时使用；\nc.更新用接口，当高速缓存数据块被命中时，更新该块的优先级；\nd.插入用接口，当插入新的高速缓存数据块时，设置该块的优先级；\ne.替换用接口，取优先级最低的高速缓存数据块为被替换块时使用；\n所述高速缓存替换策略模块共有以下五种：最近被使用，双队列，多队列，自适应低负载和低最近相关度，各有一个固定的入口函数register，以便把自己的接口实现注册给所述高速缓存服务模块，\n在各高速缓存替换策略模块中，处于运行状态的为当前高速缓存替换策略模块，其余则为候选高速缓存替换策略模块；\n2)高速缓存服务模块，把包括磁盘在内的低速存储设备的数据缓存在内存中，当用户访问数据时直接进行内存访问，该高速缓存服务模块设有：高速缓存数据、高速缓存元数据以及哈希表，其中\na.高速缓存数据，是缓存好的磁盘数据，被分成多个固定大小的高速缓存数据块，块的大小为4KB，\nb.高速缓存元数据，用于维护和管理所述高速缓存数据，其中包括：\n1)每个高速缓存数据块的物理地址；\n2)每个高速缓存数据块符号位用于标志该块是否已被写入磁盘；\n3)一个最近被使用队列，用于记录所述高速缓存数据块的优先级顺序；\nc.哈希表，以所述高速缓存数据块的地址作为关键字，对应的高速缓存元数据为数据，构成一个数据查找表，用于确定一个高速缓存数据块是否在所述高速缓存存储器中；\n所述高速缓存服务模块依次按以下顺序实现高速缓存服务：\na.当用户访问数据时，该高速缓存服务模块首先根据其中数据给定的高速缓存数据块的地址查找哈希表；\nb.若所述地址已在哈希表中，则高速缓存命中，通过更新用接口，调用所述当前高速缓存替换策略模块的命中功能，直接访问高速缓存，读出数据返回给用户；\nc.若地址不存在于哈希表中，则为高速缓存缺失，判断高速缓存数据块是否已全部被占用：\n若未全部被占用，则取出一个未占用的高速缓存数据块，通过所述插入用接口，调用所述当前高速缓存替换策略模块的插入功能，把数据调入所述未占用的高速缓存数据块，\n若高速缓存数据块已用完，则通过替换用接口，调用所述当前高速缓存替换策略模块的替换功能，找到一个在所述高速缓存数据块中优先级最低的高速缓存数据块作被替换块，把数据读入替换出的高速缓存数据块，再返回给用户；\n3)访问记录采集器模块，记录从所述高速缓存服务模块输入的访问信息，其中包括：磁盘号、访问地址和大小，先存储在内存缓冲区中，当存满时，把这些访问信息写入到磁盘文件中；\n4)访问记录分析器模块，从所述访问记录采集器模块收到已采集到设定的n条访问记录的信息后，把各访问记录依次导入各候选高速缓存替换策略模块，记录所述各候选高速缓存替换策略模块的命中次数，取命中次数最多的候选高速缓存替换策略模块为最优策略模块，把结果通知所述高速缓存服务模块；\n步骤(2).依次按以下步骤执行高速缓存替换策略的动态选择方法：\n步骤(2.1).初始化高速缓存服务模块：\n分配和初始化所有高速缓存数据块；\n分配和初始化所有的通用高速缓存数据块描述符，所述高速缓存数据块用于记录该高速缓存数据块的地址和符号位，“通用”两字是指各高速缓存替换策略模块都需用到的；\n初始化哈希表和最近被使用队列；\n步骤(2.2).当前高速缓存替换策略模块的初始化：\n步骤(2.2.1).确定一个高速缓存替换策略模块为当前高速缓存替换策略模块：\n当由用户指定时，默认取上次运行结束时所用的模块；\n当第一次运行时取最近被使用高速缓存替换策略模块；\n步骤(2.2.2).高速缓存服务模块调用所述register函数注册该当前高速缓存替换策略模块，再通过初始化接口初始化所述当前高速缓存替换策略模块；\n步骤(2.3).在用户访问数据时，高速缓存服务模块按步骤(1)所述方法插入用户访问数据为高速缓存数据块；\n步骤(2.4).访问记录采集器采集用户访问记录；\n步骤(2.5).访问记录分析\n当访问记录采集器采集到所述n条访问记录后，由访问记录分析器模块通过自己设定的一个虚拟的高速缓存服务模块来记录当访问记录依次访问各候选高速缓存替换策略模块时的记录命中次数，挑选命中次数最高的候选高速缓存替换策略模块为最优策略模块；\n步骤(2.6).切换高速缓存替换策略模块，\n首先高速缓存服务模块通过当前正处于运行状态的高速缓存替换策略模块的释放用接口释放策略元数据，所述策略元数据是指各高速缓存替换策略模块所特有的元数据；\n然后，高速缓存服务模块通过访问记录命中次数最高的那个新的高速缓存替换策略模块的初始化接口分配新的策略元数据空间；\n最后，高速缓存服务模块通过新的高速缓存替换策略模块的插入用接口把高速缓存中已有的高速缓存数据块依次导入新的高速缓存替换策略模块以重建新的策略元数据。\n所述的访问记录采集次数n＝1,000,000。在执行完步骤(2.6)后，若本轮为第一轮，则返回步骤(2.4)。若本轮策略选择得出的与上一轮相同，则结束，否则，转步骤(2.4)。在执行完步骤(2.6)后，卸载高速缓存替换策略模块。\n本发明的优点如下：\n(1)高速缓存服务模块通过固定接口使用高速缓存替换策略模块，可以在任意两个高速缓存替换策略模块之间进行切换，也可以部署新出现的高速缓存替换策略模块，从而可以尽快利用最新的科研成果。\n(2)通过异步策略选择，将访问记录采集与分析过程和普通的高速缓存访问流程分离开来，减小策略选择过程带来的CPU和内存开销，从而降低高速缓存访问的平均响应时间。\n(3)通过多轮策略选择，平衡策略选择过程的时间和准确度，在保证选择准确度的前提下减少访问记录分析所需的时间，最终减小策略选择过程的开销，并尽快将结果投入使用。\n本发明在清华大学计算机系高性能计算技术研究所进行了测试。结果表明，高速缓存替换策略的动态选择方法可以根据负载情况选出最优的高速缓存替换策略，有效提高了高速缓存系统I/O访问的命中率，降低了平均响应时间。\n对海量数据分级存储方法的测试分成模拟测试和实际系统测试两部分，模拟测试的环境为Xeon 700MHz*4，1GB内存，我们使用了Cello，SPC-1 Websearch，SPC-1 Financial和TPCC四种trace进行了模拟，测试结果见表1，可以看出本方法可以选出命中率最高的策略。图5和图6描述了两种情况下的命中率变化情况，可以看出通过策略选择，本方法选出了最优的策略，命中率高于其他的自适应策略。\n实际系统测试的环境为：一台机器作为iSCSI的目标器端，在上面架设了我们的高速缓存系统，它的配置为Xeon 2.8GHz CPU，4GB内存和6块IBM磁盘。一台机器作为iSCSI前端，安装了Windows 2000和Microsoft iSCSI Initiator。在前端使用我们开发的trace播放器播放SPC-1 Websearch和TPCC两种负载，测试结果见表2，表3和图7，图8。表2给出了Websearch负载上测到的平均响应时间，可以看出本方法的平均响应时间低于其他的自适应算法，图7给出了一种情况下的平均响应时间变化情况，可以看出通过策略选择，本方法可以降低高速缓存系统的平均响应时间。表3给出了TPCC负载上测到的平均响应时间，图8出了一种情况下的平均响应时间变化情况，可以看出类似的趋势。\n附图说明\n图1.整体体系结构。\n图2.接口和数据结构设计。\n图3.高速缓存访问基本流程。\n图4.策略选择过程。\n图5.(W3，4G)下的命中率变化情况：\n-■-最近被使用(LRU)；\n自适应低负载(ARC)；\n多队列(MQ)；\n-★-低最近相关度(LIRS)；\n-◇-本方法。\n图6.(T2，256M)下的命中率变化情况：\n-■-最近被使用(LRU)；\n自适应低负载(ARC)；\n多队列(MQ)；\n-★-低最近相关度(LIRS)；\n-◇-本方法。\n图7.(W3，3G)的平均响应时间：\n-■-最近被使用(LRU)；\n自适应低负载(ARC)；\n多队列(MQ)；\n-◇-本方法；\n图8.(T1，512M)的平均响应时间：\n-■-最近被使用(LRU)；\n自适应低负载(ARC)；\n多队列(MQ)；\n-◇-本方法；\n具体实施方式\n本发明可以在由任意高速和低速存储设备组成的二级存储体系结构中实现。高速存储设备一般为内存，或者固态磁盘，具有速度快，价格高，容量小，断电易失的特点。根据数据访问局部性的原则，它们缓存最近访问的数据，从而提高整个系统的性能。低速存储设备一般为普通磁盘，具有速度慢，价格低，容量大，非易失的特点。它们存储了所有的数据。\n高速缓存替换策略的动态选择方法主要由高速缓存服务模块，高速缓存替换策略模块，访问记录采集模块和访问记录分析模块组成。本方法的体系结构如图1所示。\n模块(1).高速缓存替换策略模块\n高速缓存替换策略模块描述了高速缓存系统命中和替换时的逻辑。高速缓存服务模块通过一统一接口访问高速缓存替换策略模块的逻辑功能。高速缓存替换策略模块的接口和数据结构设计如图2所示。高速缓存替换策略模块有一固定入口函数register，它通过该函数把自己的接口实现注册给高速缓存服务模块。\n它提供了五种功能供高速缓存服务模块使用\n1)初始化，当高速缓存系统初始化时此功能被调用；\n2)卸载，当高速缓存模块卸载时此功能被调用；\n3)高速缓存数据块插入，当新的高速缓存数据块加入时此功能被调用；\n4)高速缓存数据块命中，当高速缓存数据块命中时此功能被调用；\n5)高速缓存数据块替换，当新的高速缓存数据块替换旧的高速缓存数据块的时候此功能被调用。\n用来管理高速缓存的数据称为高速缓存元数据，包括高速缓存数据块描述符用来记录数据块对应的地址和符号位；哈希表用来记录一个数据块是否在高速缓存中；最近被使用队列用来表示数据块的优先级顺序。本方法将高速缓存数据块描述符分为通用高速缓存数据块描述符和策略高速缓存数据块描述符，分别组合成通用元数据和策略元数据。通用元数据指基本所有策略都要用到的元数据，而策略元数据指各策略特有的元数据。通用元数据由高速缓存服务模块分配和维护，而策略元数据由高速缓存替换策略模块自行维护和使用。\n本方法实现了最近被使用(LRU)，双队列(2Q)，低最近相关度(LIRS)，自适应低负载(ARC)和多队列(MQ)五种高速缓存替换策略模块，其中处于运行状态的为当前高速缓存替换策略模块，其他的为候选高速缓存替换策略模块，本方法可以将一个候选高速缓存替换策略模块动态切换成当前高速缓存替换策略模块，\n策略切换的过程如下：首先高速缓存服务模块调用旧高速缓存替换策略的卸载函数释放策略元数据，然后高速缓存服务模块调用新高速缓存替换策略的初始化函数分配新的策略元数据，最后高速缓存服务模块调用新高速缓存替换策略的插入函数将高速缓存中已有的数据块依次导入新的高速缓存替换策略模块并建立策略元数据。\n模块(2).高速缓存服务模块\n高速缓存服务模块为用户提供高速缓存服务，它将磁盘等低速设备的数据缓存在内存中，当数据再次访问时就直接进行内存访问，从而大大提高访问速度。高速缓存服务模块利用当前高速缓存替换策略模块的高速缓存数据块替换功能确定哪些数据块可以被放置在高速缓存中。高速缓存服务模块可以根据访问记录分析器模块的分析结果在候选高速缓存替换策略模块中选择命中率最高的高速缓存替换策略模切换为当前高速缓存替换策略模块。高速缓存服务模块主要有以下组成部分和逻辑：\n高速缓存数据：缓存的磁盘数据，被分成多个固定大小的高速缓存数据块。块的大小可以由用户指定，默认为4KB。\n高速缓存元数据：用于维护和管理高速缓存的数据，包括每个高速缓存数据块的物理地址，每个高速缓存数据块的符号位标志该块是否已被写入磁盘，一个最近被使用队列用于记录高速缓存数据块的优先级。\n哈希表：用高速缓存数据块的地址作为关键字，对应的高速缓存元数据作为数据的数据查找表，用于确定一个数据块是否在高速缓存中。\n高速缓存服务模块的基本流程如图3所示，当应用访问数据时，首先通过访问地址检查对应的数据块是否已经在高速缓存中，如果是的话为高速缓存命中，直接从高速缓存中访问即可，如果不是的话为高速缓存缺失，这时检查是否还有空余的高速缓存数据块，如果有的话直接将被访问的块读入该高速缓存数据块，如果没有的话从高速缓存的所有数据块中选出一被替换块，然后将被访问的块读入该替换块，这时再从高速缓存中访问数据块。\n模块(3).访问记录采集器模块\n当用户访问高速缓存服务模块时，访问记录采集器模块记录这次访问的信息，包括磁盘号，访问地址和大小。访问记录采集器模块首先将这些信息记录在内存缓冲区中，当缓冲区满时，将这些信息写入到磁盘文件中。\n模块(4).访问记录分析器模块\n当访问记录采集器模块采集到1,000,000条记录后，访问记录分析器模块即开始工作，整个过程如图4所示。访问记录分析器模块首先建立一虚拟的高速缓存服务模块，它除了不存高速缓存数据外，其他都同高速缓存服务模块相同。接着访问记录分析器模块为虚拟高速缓存服务模块指定一高速缓存策略模块，然后根据访问记录依次访问虚拟高速缓存服务模块，记录命中次数。通过对所有候选高速缓存策略模块重复上述过程，访问记录分析器模块可以得到所有候选高速缓存策略模块的命中次数，挑选命中次数最高的策略为最优策略并进行策略切换。如果本次挑选出的策略和上一轮相同，则策略选择过程结束，否则访问记录采集器再采集1,000,000条访问记录，再由访问记录分析器模块进行分析。这样的多轮策略选择过程既可以保证分析的准确性，也可以避免过多的访问记录采集和分析过程。\n当多轮策略选择结束后，高速缓存系统进入正常运行阶段，该阶段没有访问记录采集和分析的过程，几乎没有附加的CPU和内存开销。访问记录分析的时间Ta，访问记录采集的时间Tc和正常运行阶段的时间Tr有如下关系：Ta＜＜Tc＜＜Tr，这说明正常运行阶段占了大部分时间，保证了整个系统的CPU和内存开销比较小。\n所述的高速缓存替换策略的动态选择方法依次含有以下步骤：\n步骤1：高速缓存服务模块初始化\n高速缓存服务模块的初始化包括：\n1)分配和初始化所有高速缓存数据块；\n2)分配和初始化所有的通用高速缓存数据块描述符；\n3)初始化哈希表\n4)初始化最近被使用队列\n步骤2：当前高速缓存替换策略模块初始化\n高速缓存服务模块首先确定一高速缓存替换策略模块为当前策略模块，这可以由用户指定，默认取上次运行结束时使用的模块，如果第一次运行的话取最近被使用策略模块。然后高速缓存服务模块调用高速缓存替换策略模块的register函数注册该模块，最后调用该策略模块的初始化接口函数初始化该策略模块。\n步骤3：应用访问\n高速缓存服务模块首先检查哈希表，如果对应数据块的地址已经在高速缓存中，则直接访问高速缓存。如果不在高速缓存中，检查高速缓存是否已满，如果未满则直接将其调入高速缓存并访问，如果已满则先选出被替换块，然后将被访问块调入并访问。\n步骤4：访问记录采集\n访问记录采集模块记录应用访问的信息，包括访问的盘号，起始地址和大小。访问记录采集模块首先将信息记录在内存缓冲区中，当内存缓冲区满的时候再将其写入磁盘文件。\n步骤5：访问记录分析\n当访问记录采集器模块采集到1,000,000条记录后，访问记录分析器模块首先建立一虚拟高速缓存服务模块。接着访问记录分析器模块为虚拟高速缓存服务模块指定一高速缓存策略模块，然后根据访问记录依次访问虚拟高速缓存服务模块，记录命中次数。通过对所有候选高速缓存策略模块重复上述过程，访问记录分析器模块可以得到所有候选高速缓存策略模块的命中次数，挑选命中次数最高的策略为最优策略。\n步骤6：策略切换\n高速缓存服务模块调用卸载接口函数释放旧的策略模块，然后调用最优策略模块的register和初始化接口函数，最后将高速缓存中已有的数据块通过插入接口函数导入新的高速缓存替换策略模块，完成切换过程。\n步骤7：多轮策略选择\n如果本轮策略选择得到的最优策略同上一轮相同，则结束，否则跳转步骤4，进行下一轮访问记录采集和分析。如果本轮就是第一轮的话一定跳转步骤4。\n步骤8：策略选择重启\n当高速缓存服务模块发现策略的命中率显著下降时，重新启动策略选择过程，即重新进行步骤4-7。\n步骤9：高速缓存服务模块卸载\n1)将所有未写入磁盘的数据块写入磁盘\n2)释放策略模块，释放其内存和数据结构\n3)释放所有的通用元数据，包括通用高速缓存数据块描述符，哈希表和最近被使用队列\n4)释放所有的高速缓存数据块\n表1各种策略和负载下的命中率情况\n\n\n表2Websearch负载上的平均响应时间(毫秒)\n    LRU   ARC   MQ   本方法   W3，1G   9.5   9.4   8.5   8.3   W3，2G   8.3   6.9   6.6   6.6   W3，3G   6.1   5.4   5.4   5.0\n表3TPCC负载上的平均响应时间(毫秒)\n    LRU   ARC   MQ   本方法   T1，256M   6.5   6.3   6.5   6.1   T1，512M   6.4   6.3   6.2   5.5