改善缓存预取数据局部性的方法和系统及缓存访问方法

摘要

本发明提供了改善缓存预取数据局部性的方法和系统。该方法统计缓存中每个预取数据记录集合的预取命中次数，以及对于其预取命中次数小于设定的命中阈值的预取数据记录集合，在将该集合换出缓存时，将该集合中被访问的数据记录写入到新的存储区域，与该存储区域中的其他数据形成新的预取数据记录集。该方法能有效降低预取次数，提高缓存命中率。

说明书

技术领域

本发明涉及缓存技术，尤其涉及改善缓存命中率的预取数据局部性组 织方法。

背景技术

缓存是多级存储系统中非常重要的组成部分，缓存预取是一项重要的 提高缓存效率的技术。访问数据记录p_ij时首先查找其访问位置(索引查找 或元数据查找等)，当未能在缓存中命中时，缓存预取通过一次存储访问 将p_ij所在低级存储层次中的预取数据记录集合P_i：{p_i1，...，p_in}预取到缓存中，并 将p_i1p_in的访问位置修改为缓存中对应的位置，期望其后出现较多对p_i1～p_in的访问。其中，称P_i为p_i1，...，p_in的预取入口，p_ij为此次预取的预取首记录。所 访问的数据记录可以是定长数据记录，也可以是变长数据记录。缓存预取 数据内的空间局部性决定了预取机制是否有效：具有较好空间局部性的缓 存预取数据能够使一次预取带来较多的缓存命中，减少低层次存储的访问， 而空间局部性较差的缓存预取数据使预取机制得不到收益。为了使预取机 制发挥更大的作用，需要改善预取数据的空间局部性。

发明内容

因此，本发明的目的在于克服上述现有技术的缺陷，提供一种改善缓 存预取数据局部性的方法。

本发明的目的是通过以下技术方案实现的：

一方面，本发明提供了一种改善缓存预取数据局部性的方法，所述方 法包括：

统计缓存中每个预取数据记录集合的预取命中次数，所述预取命中次 数为该集合中被访问的数据记录的总数；

对于其预取命中次数小于设定的命中阈值的预取数据记录集合，在将 该集合换出缓存时，将该集合中被访问的数据记录写入到新的存储区域， 与该存储区域中的其他数据形成新的预取数据记录集合。

上述方法中，还可包括：

对于缓存中每个预取数据记录集合：

将该集合中首次被访问的数据记录标记为特殊记录；

计算该集合中当前被访问的数据记录与上次被访问的数据记录之间 的访问间隔，如果该访问间隔大于设定的间隔阈值，则将当前被访问的数 据记录标记为特殊记录；

对于其预取命中次数小于命中阈值的预取数据记录集合，在将该集合 换出缓存时，将被标记为特殊记录的数据记录的预取入口修改为所述新的 预取数据记录集合。

上述方法中，所述访问间隔可为时间间隔、访问次数间隔、自定义的 逻辑间隔或者上述间隔的组合。

上述方法中，还可包括对于其预取命中次数小于命中阈值的预取数据 记录集合，在将该集合换出缓存时，将该集合中被访问的数据记录预取入 口都修改为所述新的预取数据记录集合。

又一方面，本发明还提供了一种改善缓存预取数据局部性的系统，所 述系统包括：

用于统计缓存中每个预取数据记录集合的预取命中次数的装置，所述 预取命中次数为该集合中被访问的数据记录的总数；

用于对于其预取命中次数小于设定的命中阈值的预取数据记录集合， 在将该集合换出缓存时，将该集合中被访问的数据记录写入到新的存储区 域，与该存储区域中的其他数据形成新的预取数据记录集合的装置。

上述系统中，还可包括标记装置和修改装置，所述标记装置可用于对 于缓存中每个预取数据记录集合：

将该集合中首次被访问的数据记录标记为特殊记录；

计算该集合中当前被访问的数据记录与上次被访问的数据记录之间 的访问间隔，如果该访问间隔大于设定的间隔阈值，则将当前被访问的数 据记录标记为特殊记录；

所述修改装置可用于对于其预取命中次数小于命中阈值的预取数据 记录集合，在将该集合换出缓存时，将被标记为特殊记录的数据记录的预 取入口修改为所述新的预取数据记录集合。

在又一方面，本发明还提供了一种缓存访问方法，该方法包括：

对于待访问的数据记录，如果缓存命中，则将缓存中包含该待访问的 数据记录的预取数据记录集合的预取命中次数增加1；

如果缓存未命中且有空的缓存项，则将包含该待访问的数据记录的预 取数据记录集合预取到该缓存项中，并将该预取数据记录集合的预取命中 次数增加1；

如果缓存未命中且没有空的缓存项，则执行：

判断选定的缓存项中预取数据记录集合的预取命中次数是否小于设 定的命中阈值，如果小于，则将该集合中被访问的数据记录写入到新的存 储区域，与该存储区域中的其他数据形成新的预取数据记录集合；以及

将包含该待访问的数据记录的预取数据记录集合预取到该选定的缓 存项中，并将该预取数据记录集合的预取命中次数增加1。

上述缓存访问方法中，还可包括：

对于缓存中每个预取数据记录集合：

将该集合中首次被访问的数据记录标记为特殊记录；

计算该集合中当前被访问的数据记录与上次被访问的数据记录之间 的访问间隔，如果该访问间隔大于设定的间隔阈值，则将当前被访问的数 据记录标记为特殊记录；

在将其预取命中次数小于命中阈值的预取数据记录集合换出缓存时， 将被标记为特殊记录的数据记录的预取入口修改为所述新的预取数据记 录集合。

上述缓存访问方法中，还可包括在将其预取命中次数小于命中阈值的 预取数据记录集合换出缓存时，将该集合中被访问的数据记录预取入口都 修改为所述新的预取数据记录集合。

上述缓存访问方法，还可包括：

当所述新的预取数据记录集合中的数据记录个数达到设定的阈值时， 对于缓存中其预取命中次数小于设定的命中阈值的每个预取数据记录集 合，将该集合中被访问的数据记录写入到该新的预取数据记录集合中；

停止对该新的预取数据记录集合的写入，获取空闲的缓存空间用于存 储另一个新的预取数据记录集合。

与现有技术相比，本发明提供的改善缓存预取数据局部性的方法能有 效降低预取次数，提高缓存命中率。

附图说明

以下参照附图对本发明实施例作进一步说明，其中：

图1为根据本发明实施例的改善缓存预取数据局部性的方法的流程示 意图；

图2为根据本发明实施例的缓存访问方法的流程示意图。

具体实施方式

为了使本发明的目的，技术方案及优点更加清楚明白，以下结合附图 通过具体实施例对本发明进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。

要改善缓存预取数据局部性需要解决两个问题：确定哪些缓存预取数 据的局部性较差，需要对其进行改善；以及如何改善这些缓存预取数据的 局部性。从某个预取数据记录集合(例如，P_i)被预取到缓存中，到其被换 出缓存之前，该集合中将会有若干个数据记录被访问，这些被访问的数据 记录的集合(例如，H_i：{p_ij1，...，p_ijm}，)可称为此次预取的预取命中数据， 这些被访问的数据记录的个数(例如，m)可以被称为此次预取的预取命 中次数。例如，在将预取数据记录集合P_i预取到缓存中后，期望此次预取 的预取命中次数较快地超过一个阈值，如果未达到此要求，则说明预取P_i没 有发挥作用或者发挥了较少的作用，称此种情况为未达到预取效果，表明 此次预取数据内部的空间局部性较差，应当对这些预取数据进行适当的重 新布局从而改善局部性。

图1给出了根据本发明的一个实施例的改善缓存预取数据局部性的方 法的流程示意图。该方法统计缓存中每个预取数据记录集合的预取命中次 数，对于其预取命中次数小于设定的命中阈值的预取数据记录集合(例如 P_i)，在将该集合换出缓存时，将该集合中被访问的数据记录(即预取命中 数据，例如H_i)冗余写入到新的存储区域，与该存储区域中的其他数据形 成新的预取数据记录集合(例如为P)。

其中，所述命中阈值可以根据实际系统环境或用户需求来进行设置， 可以为静态阈值，也可以是动态阈值，例如可以将命中阈值设定为某个预 定的整数值，也可以将命中阈值设置为预取数据记录集合中元素个数的百 分比，例如10％×|P_i|，20％×|P_i|，30％×|P_i|等。所述预取命中次数为该 集合中被访问的数据记录的总数。在其他实施例中，所述预取命中次数也 可以是对该预取数据记录集合的访问次数。通过上述方法被冗余写入到该 新的预取数据记录集合中的预取命中数据与该集合中其他数据记录形成 一批新的空间局部性较好的预取数据；该集合中的其他数据记录可以是通 过同样的方法写入的冗余数据，也可以是写入的新产生的数据记录，该集 合中可以存在重复的数据记录，也可以通过某种方法去除重复的数据记录。 在其他实施例中，可以同时存在一个或多个这样的新的预取数据记录集合。 当存在多个时，将所确定的要改善局部性的预取数据记录集合中被访问的 数据记录按照某种分类写入到其中一个集合中。另外，不限定所形成的新 的预取数据记录集合所在的存储介质，可以在写缓存中，也可以在其他层 次的存储介质中，还可以从写缓存转入到其他层次的存储介质中；当访问 存在多个副本的数据记录时优先从缓存中访问，如不在缓存中，则通过预 取方式进入到缓存中后访问。

在冗余写入这些预取命中数据(例如H_i)之后，同一条数据记录可能 存在于多个预取数据记录集合中，此时被冗余的预取命中数据中每一条数 据记录的预取入口有多种选择，可以不做更改(例如，仍然为P_i)，也可 以定位到新的预取位置(例如P)，还可以根据访问的情况做出选择，不同 的预取入口定位策略所适用的环境不同。在本发明的一个优选实施例中， 该方法还包括下列步骤：对于缓存中每个预取数据记录集合：将该集合中 首次被访问的数据记录标记为特殊记录；以及计算该集合中当前被访问的 数据记录与上次被访问的数据记录之间的访问间隔，如果该访问间隔大于 设定的间隔阈值，则将当前被访问的数据记录标记为特殊记录。这样，对 于其预取命中次数小于命中阈值的预取数据记录集合，在将该集合换出缓 存时，将该集合中被访问的数据记录冗余写入到新的存储区域，与该存储 区域中的其他数据形成新的预取数据记录集合，同时还可以将该集合中被 标记为特殊记录的数据记录的预取入口修改为所述新的预取数据记录集 合。其中，访问间隔可以是时间间隔、访问次数间隔以及自定义的某种逻 辑间隔中的一种，也可以是多种间隔类型组合(其中一种间隔过长即可标 记为特殊记录)。间隔阈值可以根据访问间隔的类型来设置。在其他实施 例中，也可以将进行上述冗余写入的所有数据记录的预取入口都修改为所 述新的预取数据记录集合。或者也可以全部不修改。

从上文所述可以看出，该改善缓存预取数据局部性的方法可以伴随缓 存访问和缓存替换过程而运行。在本发明的又一个实施例中，还提供了一 种结合上述改善缓存预取数据局部性方法的缓存访问方法。该缓存访问方 法执行过程如下：当访问某个数据记录(假设为p_ij)时，分三种情况进 行处理：(1)当访问未能在缓存中命中时(即该数据记录p_ij不在缓存中)， 如果存在空的缓存项，例如缓存项C_k，则将p_ij所在预取数据记录集合 P_i：{p_i1，...，p_in}预取到缓存项C_k中，此时在预取完成后将p_ij加入到H_k中，递 增h_k，并标记p_ij为特殊记录；其中，H_k是与缓存项C_k对应的记录预取命中 数据的集合，其数据结构可以例如为队列，位图等，h_k用于记录预取命中 次数计数。如果没有空的缓存项，则执行缓存替换步骤(将在下文中介绍)， 用P_i替换所选的缓存项C_k中的原有内容。(2)访问在缓存中命中(例如， P_i已经被预取到缓存项C_k中)且h_k＜T_i时，此时如果p_ij还未在H_k中，则将 其加入到H_k中，递增h_k，并计算上次访问P_i中的元素和当前访问的间隔I， 如果I＞T_I，则标记p_ij为特殊记录；其中，T_i为命中阈值，T_I为间隔阈值， 其可根据访问间隔类型来确定，两者可以是静态阈值，也可以是动态阈值。 (3)访问在缓存中命中且预取命中次数h_k≥T_i时，此时递增h_k。其中， 将p_ij加入到H_k中例如可以指将p_ij在缓存中的逻辑或物理指针保存到记录 H_k的数据结构中(加入之前判断p_ij是否已经H_k中存在，不存在时加入)。

当要将缓存项C_k的内容将要从P_i替换为P_l时(例如，要访问的数据记 录在P_l中，需要将P_l预取到缓存项C_k中)，分两种情况处理：(1)如果h_k＜T_i， 则将H_k中的数据记录写入到冗余数据记录集合P_w中，同时更改H_k中标记为 特殊记录的预取入口为P_w，然后清空H_k并置h_k为0；(2)如果h_k≥T_i，则 清空H_k并置h_k为0。其中，P_w的存储位置可以在缓存中(例如，写缓存)， 也可以在其他层次的存储介质中，还可以从写缓存转入到其他层次的存储 介质中。P_w中除按上述方法冗余写入的数据记录外，还可以写入新产生的 数据记录；此时，冗余写入的数据记录可能存在两个副本(P_i和P_w中各一)， 访问存在多个副本的数据记录时优先从缓存中访问，如不在缓存中，则通 过预取方式进入到缓存中后访问。当冗余数据记录集合P_w中的存储空间耗 尽或者其中的数据记录个数达到上限要求，此时扫描所有缓存项C₁～C_n， 当扫描缓存项C_k(其中缓存集合为P_i)时，分两种情况处理：(1)如果h_k＜T_i， 则将H_k中的数据记录写入到P_w中，同时更改H_k中标记为特殊记录的预取入 口为P_w，最后清空H_k并置h_k为0；(2)如果h_k≥T_i，则不执行动作。然后， 停止向P_w中写入新的数据记录，继续获取空闲缓存存储空间使其成为新的 冗余数据记录集合P_w′。

为更好地理解上述的缓存访问方法，参照图2对该缓存访问方法的执 行过程进行举例说明。在该示例中假设缓存项个数为4，所用缓存替换算 法为最近最少使用(LRU)算法，用j作为p_ij在缓存项C_k中的逻辑指针(通 过记录数字j即可实现将p_ij加入到集合H_k中)，令命中阈值T_i＝10％×|P_i|， 设定间隔阈值T_I的值为4，可以写入的新的预取记录集合中记录个数上限 要求为10，该新的预取记录集合的存储空间位于写缓存中。初始状态时， 缓存全部为空，预取命中数据集合全部为空，预取命中次数为0。假设当 前系统中，已存在6个如表1所示预取数据记录集合P₁-P₆。表2给出了该 示例中要进行的访问序列1-20，其中访问序列1-7，12-20为读访问；访问 序列8-11为写访问。访问序列1表示读数据记录p_1，2，访问序列8表示写 数据记录p_7，1，以此类推。

表1

P₁P₂P₃P₄P₅P₆p_1，1～p_1，22p_2，1～p_2，18p_3，1～p_3，15p_4，1～p_4，12p_5，1～p_5，25p_6，1～p_6，21

表2

序号 1 2 3 4 5 6 7 8 9 10 类型 读 读 读 读 读 读 读 写 写 写 记录 p_1，2p_2，5p_3，1p_4，9p_2，6p_2，7p_1，3p_7，1p_7，2p_7，3序号 11 12 13 14 15 16 17 18 19 20 类型 写 读 读 读 读 读 读 读 读 读 记录 p_7，4p_5，10p_5，11p_5，10p_1，2p_6，3p_1，4p_3，2p_3，11p_4，12

继续参考图2，访问上述序列1-20的具体过程为：

1)执行步骤101，判断所访问数据p_1，2是否在缓存中；

例如，缓存系统可通过查找操作确定所访问数据记录是否在缓存中。 如果p_1，2不在缓存中，那么需要将p_1，2所在的预取数据记录集合P₁预期到缓 存中。假设系统选择将P₁预期到缓存项C₁中，转至步骤104继续执行。

2)执行步骤104，判断缓存项C₁中是否为空；

也就是说，缓存系统在将P₁预取到缓存项C₁之前，要判断C₁中是否有 数据。如果缓存项C₁为空，则转到步骤110继续执行。

3)执行步骤110，将P₁预取到缓存项C₁中；

4)执行步骤111，将p_1，2加入到C₁的预取命中集合H₁中；然后返回步骤 101，继续处理下一个访问序列。

具体地，在C₁对应的预取命中数据集合H₁中加入p_1，2的逻辑指针2，标 记p_1，2为特殊记录，递增预取命中次数h₁。

按照与过程1)～5)相同的方式，处理访问序列2～4，处理完毕后缓 存项中存储的预取数据记录集合，对应的预取命中数据集合，及对应预取 命中次数可如下表3所示(下划线表示特殊记录标记)：

表3

缓存项 预取数据记录集合 预取命中数据集合 预取命中次数 C₁P₁21 C₂P₂51 C₃P₃11 C₄P₄91

参考图2以及表2所示的访问序列，下面继续处理访问序列5：

5)执行步骤101，判断p_2，6是否在缓存中；这里p_2，6已经在缓存中，则 转至步骤102继续执行。

6)执行步骤102，判断预取命中次数h₂是否小于命中阈值；如果小于， 则转至步骤103继续执行，否则返回步骤101，处理下一个访问序列。

此时，h₂此时为1，小于阈值T₂＝10％×|P₂|＝10％×18。

7)执行步骤103，将p_2，6加入到C₂的预取命中集合H₂中；然后返回步骤 101，继续处理下一个访问序列。

在步骤103，还需要计算如上文所述的访问间隔I；这里与对C₂的前一 次的访问间隔I为3，小于间隔阈值T_I，因此在C₂对应的预取命中数据集 合H₂中记录p_2，6的逻辑指针6，递增预取命中次数h₂。

按照与过程5)～7)相同的方式，继续处理访问序列6～7，不同的是， 对于访问序列6，在执行102时h₂已经大于命中阈值T₂，因此不需执行步 骤103；对于访问序列7，在执行103时，与对C₁的前一次的访问间隔I 为6，大于间隔阈值T_I，因此除将p_1，3的逻辑指针3加入到H₁中并递增h₁以 外，还需要将其标记为特殊记录。

接着，继续处理访问序列8～11。对于写入序列8～11，缓存系统会生 成一个新的预取数据记录集合P₇，将p_7，1～p_7，4写入到P₇中(本示例中，假 设P₇的存储位置在写缓存P_w中)。此时，各缓存项中存储的预取数据记录 集合，对应的预取命中数据集合，及对应的预取命中次数如下表4所示(下 划线表示特殊记录标记，连字符表示信息为空)：

表4

接着处理访问序列12，即读数据记录p_5，10：

8)执行步骤101，判断p_5，10是否在缓存中；这里p_5，10不再缓存中，假 设系统选择p_5，10所在的预取数据访问记录集合P₅预取到缓存项C₁中，接 着转至步骤104执行。

9)执行步骤104，判断缓存项C₁是否为空；如果缓存项为空，则转至 步骤110；如果缓存项不为空，则需要将缓存项C₁中的内容换出缓存，此 时转至步骤105继续执行。

10)执行步骤105，判断预取命中次数h₁是否小于或等于命中阈值； 如果小于或等于命中阈值，则执行步骤106；如果大于命中阈值，则转至 步骤110继续执行。

具体地，此时h₁为2，小于命中阈值T₁＝10％×|P₁|＝10％×22。这 说明此时C₁中的预取数据访问记录集合P₁中的数据局部性较差，需要进 行改善。反之，如果大于命中阈值，则说明不需要改善这部分数据的局部 性，即不需要对现在缓存项C₁的数据进行额外处理，直接将P₅换入到C₁即可。

11)执行步骤106，将H₁中的数据记录写入集合P₇中；

具体地，从缓存项C₁对应的预取命中数据集合H₁中依次读出逻辑指针 2和3，并据此从C₁中读出第2和第3个记录p_1，2和p_1，3，将其写入到P₇中(成 为P₇中的p_7，5和p_7，6)，并更改p_1，2和p_1，3的预取入口为P₇(本实施例将这些冗 余的数据记录和新产生的记录写入同一预取数据记录集合)。此时p_1，2，p_1，3和p_7，5，p_7，6互为副本，由于后者在写缓存P_w中而P₁已经被换出缓存，所以 优先访问p_7，5，p_7，6。

12)执行步骤107，清空预取命中集合H₁，并置h₁为0；

13)执行步骤108，判断写入集合P₇是否已满；如果未满，则转至步 骤110继续执行；如果已满，则转至步骤109继续执行。

这里，P₇中数据记录个数为4，小于10，未达到个数上限。

14)执行步骤110，将P₅换入到缓存项C₁中；

15)执行步骤111，将p_5，10加入到C₁的预取命中集合H1中；

按照与过程5)～7)相同的方式，处理访问序列13，14，不同的是，对 于访问序列14，执行步骤103过程中向H₁中加入p_5，10的逻辑指针10时， 发现该数字已经被记录(与序列12访问相同数据记录)，因此，跳过步骤 103中其他操作。处理完成后，各缓存项中存储的预取数据记录集合，对 应的预取命中数据集合，及对应预取命中次数如下表5所示(下划线表示 特殊记录标记，连字符表示信息为空)：

表5

对于访问序列15，由于p_1，2和p_1，3在P₇中存在副本p_7，5和p_7，6(通过缓存 查找找到副本)，因此访问会从P₇中读取数据记录p_7，5，p_7，6，不执行其他操 作。

按照与过程8)～15)相同的方式，处理访问序列16～18，在处理过程 中，按照LRU缓存替换算法，P₃，P₄，P₂先后被换出缓存，在此过程中将 p_3，1，p_4，9写入P₇，由于p_3，1，p_4，9被标记为特殊记录其预取入口修改为P₇，换 出P2时由于预取命中次数大于阈值T₂，其中预取命中数据不写入P₇。

按照与过程5)～7)相同的方式，处理访问序列19，在处理过程中， p_3，11在缓存项C₂中命中，在C₂对应的预取命中数据集合H₂中加入p_3，11的逻 辑指针11，递增预取命中次数h₂。

按照与过程8)～15)相同的方式，处理访问序列20，在处理过程中， 按照LRU缓存替换算法，P₅被换出缓存，在此过程中将p_5，10，p_5，11写入P₇， 由于p_5，10被标记为特殊记录其预取入口修改为P₇。不同的是，在执行步骤 108时，P₇中的数据记录个数为10，达到了个数上限，需要执行步骤109， 具体地，扫描缓存项C₁～C₄，发现h₁，h₃，h₄不满足阈值要求，因此将 p_6，3，p_1，4，p_4，12写入P₇(h₂满足阈值要求，因此p_3，2，p_3，11不写入)，由于 p_6，3，p_1，4，p_4，12被标记为特殊记录，其预取入口修改为P₇，最后清空C₁，C₃，C₄对应的预取命中数据集合H，H₃，H₄，并置h₁，h₃，h₄为0。步骤109执行完毕 之后，新的预取数据记录集合P₇：{p_7，1，...，p_7，13}中包含13个数据记录，其 中四个为新写入记录，九个为副本记录。此时将停止对P7的写入操作， 当后续有新的数据产生或如上文所述需要冗余写入部分数据记录时，从新 空闲缓存存储空间分配新的存储区域，使其用于存储新的冗余数据记录集 合P₈等。

处理完表2给出的所有访问序列之后，各缓存项中存储的预取数据记 录集合，对应的预取命中数据集合，及对应预取命中次数如下表6所示(下 划线表示特殊记录标记，连字符表示信息为空，在P₇被换出写缓存之前将 其持久化到磁盘中)：

表6

发明人还在内容寻找存储中的索引系统中，利用真实环境下的备份负 载对上述的方法进行了测试。测试结果表明，该方法减少了17.8％～56％的 索引预取次数，提升了8％～24％的读取带宽和2％～6％的写入带宽；在同样 的索引系统中，利用为期两周的数据同步负载的测试结果表明，预取次数 下降了96％。

虽然本发明已经通过优选实施例进行了描述，然而本发明并非局限于 这里所描述的实施例，在不脱离本发明范围的情况下还包括所作出的各种 改变以及变化。