本发明公开了一种基于页面染色技术的内存数据库访问优化方法。该方法首先将弱局部性数据集的所有数据页面的访问顺序按页面颜色进行排序，并将所有数据页面按页面颜色进行分组，然后按页面颜色分组的顺序扫描弱局部性数据集的所有数据页面。进一步地，预设若干具有相同页面颜色的内存页面作为页面颜色队列，该页面颜色队列用作内存页面被加载入CPU缓存之前的内存缓存；弱局部性数据集的数据页面首先通过异步方式进入页面颜色队列，然后再被加载到CPU缓存中完成数据处理。本发明能够解决内存数据库应用中无法依赖页面颜色为进程、线程或数据集优化分配缓存地址空间的问题，有效减少数据局部性强度不同的数据集之间的缓存冲突。

技术领域

本发明涉及一种内存数据库访问优化方法， 尤其涉及一种基于页面染色技术（Page-coloring)对不同数据局部性强度的数据集进行访问控制， 从而对内存数据库使用的 CPU缓存 （cache?) 访问进行优化的方法， 属于数据库管理技术领域。

背景技术

内存数据库是一种将全部数据驻留在内存中， 而非传统数据库那样存放在外部存储器中的数据库。 它的显著特点在于所有的数据访问控制都在内存中进行， 因此数据读写速度相对于磁盘数据库要高出几个数量级， 从而能够极大地提高数据库应用的性能。 与磁盘数据库相比，内存数据库重新设计了体系结构， 并且在数据缓存、 查询优化、 并行操作方面也进行了相应的改进。

另一方面， 现有的微处理器（CPU) 已经进入多核时代。 多核微处理器通常采用共享 CPU缓存的体系结构， CPU缓存采用硬件级的类 LRU (最近最少访问）替换算法。当查询处理包括一个较小的强局部性（频繁访问） 数据集和一个较大的弱局部性 （一次性访问或重复访问周期较长） 数据集时， 弱局部性数据集上的顺序访问将与强局部性数据集产生缓存冲突， 导致强局部性数据集被驱逐出 CPU缓存， 只能在随后的操作中再重新加载到 CPU缓存， 从而因为缓存颠簸产生大量的缓存丢失 （miss ) 冲突， 增加数据访问的延迟。这种现象被称为缓存污染（cache?pollutions）。在实践中， 宏观的缓存污染是指不同的查询处理进程或线程在共享 CPU缓存中的缓存访问冲突， 例如哈希连接查询处理线程与索引连接查询处理线程在共享 CPU缓存上的访问冲突等； 微观的缓存污染是指查询处理进程内部不同访问特性数据集之间的缓存访问冲突， 例如哈希连接中顺序扫描的外表和哈希表之间的缓存访问冲突等。

页面染色技术 （Page-coloring) 是内存与 CPU缓存之间的高速地址转换技术， 即通过物理内存地址的低位映像来控制内存页面调入到 CPU缓 存中指定的区域中。 现有的页面染色技术通过改变具有不同局部性特性的内存页面颜色 （page-color ) 的方式将数据调入到指定的不冲突缓存区域中， 从而实现隔离弱局部性数据对强局部性数据的缓存污染。 当前比较成熟的缓存访问优化方法是扩展操作系统内核模块， 支持以页面颜色队列方式管理内存资源， 并为并发的查询处理进程提供按页面颜色分配内存的 功能， 从而控制不同进程的内存地址空间在 CPU缓存中没有交叉， 减少具有不同数据访问特性的进程之间的缓存冲突。 该类技术路线适用于磁盘数据库的缓冲区管理功能。 由于磁盘数据库的数据驻留于磁盘， 在查询处理时需要首先加载到内存缓冲区后才能进行处理， 而弱局部性数据没有重用性或重用的周期很长， 因此可以通过内存缓冲区的内存地址分配技术将数据量大的弱局部性数据集交换到少量内存页面颜色队列对应的缓冲区内存中， 从而能够为强局部性数据集分配更多的内存页面颜色队列来保证其充足的可用内存资源。 但是， 磁盘数据库中的页面颜色优化技术是面向进程粒度的，无法为进程内具有不同数据访问特性的数据集访问进行细粒度的优化。

页面染色技术在内存数据库的应用中面临两个技术挑战： 一是内存数据库的数据常驻内存， 内存数据库采用直接访问内存的方式而不是像磁盘数据库那样通过缓冲区来间接地访问数据。 较大的弱局部性数据集往往占据较大的内存地址空间， 而其弱局部性的特点需要将较大的内存地址空间映像到最少的缓存地址空间中， 也就是说需要为巨大的内存地址空间分配最少的页面颜色。 而每一个页面颜色代表最大 1/n (n 为页面颜色数量） 可用的内存地址空间。 内存数据库无法为弱局部性的大数据集分配较少的页面颜色。 第二个挑战是如果采用动态页面染色技术， 在内存数据访问前通过内存复制的方法改变弱局部性数据页面的页面颜色， 虽然可以解决弱局部性数据集无法分配较少页面颜色的问题， 但内存复制的延迟严重地影响了数据访问的整体性能。

因此， 内存数据库面临的缓存优化技术挑战是内存中没有缓冲区机制来支持通过缓存访问的方式动态改变地址空间大的弱局部性数据集的页面颜色再分配机制。 如果按页面颜色为强局部性数据集和弱局部性数据集分配常驻内存地址空间， 则内存地址空间的利用率较低。 分配较多的页面颜色意味着获得较大的地址空间， 而强局部性数据集只需要有较大的页面颜色范围而并不需要实际的大量内存地址空间来存储较小的数据集。 同时，弱局部性数据集只需要较小的页面颜色范围但实际需要大量内存地址空间来存储较大的数据集。 内存地址空间与页面颜色范围的配额矛盾难以同时满足。

发明内容

本发明所要解决的技术问题在于提供一种基于页面染色技术的内存数据库访问优化方法。 该方法基于页面染色技术对不同数据局部性强度的数据集进行访问控制， 从而降低不同访问特征的数据集在 CPU缓存中的冲突， 降低缓存丢失率， 提高内存数据库的整体性能。

为解决上述的技术问题， 本发明采用下述的技术方案：

一种基于页面染色技术的内存数据库访问优化方法， 其特征在于： 在内存数据库的缓存访问过程中， 将弱局部性数据集的所有数据页面的访问顺序按页面颜色进行排序， 并将所有数据页面按页面颜色进行分组， 然后按页面颜色分组的顺序扫描弱局部性数据集的所有数据页面；

预设若干具有相同页面颜色的内存页面作为页面颜色队列， 该页面颜色队列用作内存页面被加载入 CPU缓存之前的内存缓存； 弱局部性数据集的数据页面首先通过异步方式进入页面颜色队列， 然后再被加载到 CPU缓存中完成数据处理。

其中较优地，所述页面颜色分组的顺序为按页面颜色递增的 W-order 顺序。

其中较优地， 在按 W-order顺序的扫描过程中， 以缓存大小 /组关联数的倍数为单位向操作系统申请物理地址连续的大内存块以存储弱局部性数据集。

其中较优地， 当弱局部性数据集所分配的虚拟内存在物理地址上不连续时， 首先为虚拟地址空间建立页面颜色索引， 将每一个页面的入口地址与页面颜色记录在二元数据结构的索引中， 然后将所述索引按页面颜色排序， 将相同页面颜色的页面入口地址聚集成组， 在按 W-order顺序的扫描过程中按所述索引的页面地址顺序扫描。

其中较优地， 所述页面颜色队列采用循环队列方式， 某个队列页面被访问后即成为交换页面被后续待访问页面覆盖。

其中较优地， 所述页面颜色队列中， 第 i块的缓存加载操作与第 i-1 块的页面复制流水并行， 其中 i为自然数。

其中较优地， 所述数据页面采用 DMA memcpy模式复制到所述页面颜色队列中。

其中较优地， 所述页面颜色队列的长度由数据页面加载到 CPU缓存的延迟以及 DMA memcpy模式的延迟决定。

本发明具有如下的有益效果：

(1) 能够解决内存数据库应用中无法依赖页面颜色为进程或线程优化分配缓存地址空间的问题；

(2) 有效减少数据局部性强度不同的数据集之间的缓存冲突；

(3) W-order扫描只改变顺序扫描算法， 不需要为缓存优化而重新设 计查询处理算法， 不需要扩展操作系统内核功能。

附图说明

下面结合附图和具体实施方式对本发明做进一步的详细说明。

图 1为内存与缓存之间地址分配机制的示意图；

图 2为内存和缓存地址组成的地址矩阵示意图；

图 3为 W-order扫描的工作原理示意图；

图 4为物理地址连续内存块中的 W-order扫描示意图；

图 5为物理不连续的虚拟地址上的 W-order扫描示意图；

图 6为动态页面颜色队列优化技术的工作原理示意图；

图 7为现有技术中索引扫描的示意图；

图 8为本发明中索引扫描的缓存优化原理示意图；

图 9为多核处理器中并行哈希连接查询处理的工作原理示意图。

具体实施方式

在本发明中， 缓存 （cache?) 主要是指处理器硬件级的 CPU缓存。 它与数据库软件级的缓冲区（buffer)不同，其访问控制是硬件指令决定的， 数据库软件无法像对缓冲区一样进行主动管理。 缓存访问的最底层目标是优化具有不同访问特征的数据集的访问模式， 因此进程级的缓存优化技术仍然有较大的优化空间。 为此， 本发明提供了一种应用于内存数据库的缓存访问优化方法。 该方法以当前多核处理器共享 CPU缓存的主流缓存替换算法——多路组关联替换 （n-way set associative ) 算法为背景， 根据内存数据的页面颜色来优化数据页面访问顺序， 从而减少 OLAP 查询处理时的缓存访问冲突， 提高内存数据库的整体性能。

页面染色技术是现代微处理器所采用的一种高速地址映像技术， 用于将内存物理地址映像为 CPU缓存地址（进一步可参考 Xiao Zhang, Sandhya Dwarkadas和 Kai Shen的论文《Towards Practical?Page?Coloring-based Multi-core?Cache Management》， 发表于 European Conference on Computer Systems ‘ 09 )。 微处理器的共享缓存通常采用多路组关联替换算法， 以 4MB共享缓存上的 16路组关联为例， 内存与缓存通过统一的地址分配机制，如图 1所示，将 22位缓存地址（2²²bit = 4MB)的低 12位 ( 2¹²bit = 4KB) 作为页面地址， 高 6位 （2⁶=64) 作为页面颜色标志位 （页面颜色数量 =缓存大小 (4MB) /页面大小 (4KB) /缓存关联 (16 ) =64) , 最高 4 位 （2⁴= 16 ) 作为组关联号。 通过统一的编址方式， 内存和缓存地址可以表示为图 2所示的地址矩阵。 其中， 内存中的数据页面在访问时被调入到缓存中具有相同页面颜色的组关联缓存区域中， 即内存页面以页面颜色为 依据将数据页面调入到缓存中具有相同页面颜色的缓存区域中， 然后由通 过类 LRU (最近最少访问）替换算法将数据调入该缓存区域中的某一页面。

在通常情况下， 对数据的顺序扫描按页面地址的自然增序进行。 例如 从页面颜色的角度来看， 依次扫描页面颜色为 0的页面， 扫描页面颜色为 1的页面，直到页面颜色为 63的页面，然后继续扫描页面颜色为 0的页面…， 在页面颜色地址矩阵上看呈现 Z-order顺序的特征。 这种 Z-order顺序 并不利于实现数据级的缓存优化技术。

为此， 本发明人提出了一种被称为 W-order顺序的页面扫描方式。 W-order顺序是指对数据的扫描按页面颜色顺序进行。 当索引扫描的选择 率较高时， 在索引访问记录地址中抽取出页面颜色标志位， 对索引范围中 的记录按页面颜色顺序进行多趟访问。 即首先扫描全部页面颜色为 i ( i 为自然数） 的页面， 然后再扫描所有页面颜色为 i + 1 的页面， 直到扫描 完最后一个页面颜色对应的全部页面 （即页面颜色记录组）， 在内存地址 扫描顺序上呈现 W形状， 我们称这种按页面颜色顺序的扫描为 W-order 扫描（进一步可参考张延松等人的论文《￥-Order scan: minimizing?cache?pollution by application software level?cache?management for MMDB》， 发表于 WAIM‘ 11 Proceedings of the 12th international conference on Web-age information management )。 图 3为 W-order扫描的示意图。 W-order扫描是按页面颜色的顺序扫描页面， 首先扫描内存数据集中所有 页面颜色号为 0的页面， 然后扫描下一组所有页面颜色号为 1的页面， 直 到最后一组。 W-order扫描操作支持乱序访问， 尤其适用于关系数据库中 基于集合的数据组织和访问结构。

在上述技术手段的基础上， 本发明所提供的缓存访问优化方法主要包 括两个方面的技术内容： (1) 静态页面访问顺序优化； (2) 动态页面颜色 队列优化。 静态页面访问顺序优化是指在数据页面访问时不改变页面的物 理地址， 只优化对页面的访问顺序。 动态页面访问颜色队列优化是指通过 预设一个页面颜色缓冲区， 页面访问时先进入页面颜色缓冲区来改页面颜色， 从而减少页面被加载到 cache时的地址冲突。 静态页面优化适合于数 据访问顺序无关的弱局部性数据集扫描操作， 需要预知数据访问特征； 而 动态页面队列适合于通用的数据访问优化， 不需要预先了解数据访问特征。 下面对此展开详细具体的说明。

所谓静态页面访问顺序优化是指对顺序访问的弱局部性数据集的数 据页面访问顺序按页面颜色顺序进行优化， 即将访问频率很低的弱局部性 数据集的所有数据页面的访问顺序按页面颜色进行排序， 并将所有数据页 面按页面颜色进行分组， 然后按页面颜色分组的顺序扫描弱局部性数据集 的所有数据页面。 这样， 弱局部性数据集页面上的访问顺序不再按内存地址自然递增的 Z-order顺序， 而是按页面颜色递增的 W-order顺序。

为了满足静态页面访问顺序优化的要求， 本发明中首先采用了连续物 理内存空间分配技术。 具体而言， 首先采用例如 kmal loc ( ) 之类的函数 向操作系统申请一块较大的物理地址连续的存储空间存储弱局部性数据 集。 物理地址连续的存储空间申请遵循 4KB X页面颜色数量的整数倍 （如 64 个页面颜色的系统分配 4KB X 64 = 256KB整数倍的内存块， 例如 1MB)。 在物理地址连续的数据块内， 可以根据偏移地址计算访问指定页面颜色的 页面， 从而支持在物理地址连续的数据块内按页面颜色的顺序实现多趟扫 描。

另一方面， 本发明也采用了 Linux操作系统默认的虚拟内存空间分配 技术。 具体而言， 当采用 malloc ( ) 函数分配内存块时， 虚拟地址分配的 内存块在物理地址上可能并不连续， 无法按虚拟地址计算出页面的页面颜 色。 在这种情况下， 为虚拟地址空间建立页面颜色索引， 将每一个页面的 入口地址与页面颜色记录在一个二元数据结构的索引中， 然后将索引按页 面颜色排序， 将相同页面颜色的页面入口地址聚集成组， 表扫描时按页面 颜色索引的页面地址顺序扫描。

在本发明所提供的内存数据库缓存访问优化方法中， 将查询处理中的 顺序 （即 Z-order顺序） 表扫描操作替换为 W-order顺序扫描操作， 从 而将哈希连接中事实表与哈希表的缓存冲突在每组按页面颜色扫描的过 程中限制在一个页面颜色的缓存地址空间内， 降低整体的缓存冲突。

图 4 显示了在基于 kmalloc ( ) 函数的物理地址连续的内存块中， W-order扫描的实现步骤。 在 W-order扫描过程中， 以缓存大小 /组关联 数 （如 4MB/16 路组关联） 的倍数为单位向操作系统申请物理地址连续的 大内存块以存储弱局部性数据集。 对于图 4所示的内存块内按页面颜色组 织的页面矩阵， 可以通过动态的地址计算方式得到指定页面颜色队列的入 口地址， 从而实现按页面颜色顺序的 W-order扫描。

图 5显示了物理地址不连续的虚拟内存地址上， W-order扫描的实现 步骤。 当数据集所分配的虚拟内存在物理地址上不连续时， 首先建立一个 页面颜色索引存储每一个内存页面的入口地址（pg)和页面颜色（pc )号， 然后将索引按页面颜色号排序， 页面颜色索引中按页面颜色号自然分组。 当执行扫描操作时， 按页面颜色索引中的页面入口地址顺序访问数据集页 面， 实现在物理地址不连续的虚拟内存地址上的 W-order 扫描。 在这个 过程中， 页面颜色索引为每一个页面存储一个数据对， 存储空间的开销很小。

对于哈希连接类算法而言， 采用基于页面颜色的数据页面访问顺序 (即 W-order顺序） 优化可以降低一次性访问数据对频繁访问数据集的 缓存驱逐效应， 减少缓存的丢失。

接下来对本发明中的动态页面颜色队列优化技术进行说明。 所谓动态 页面颜色队列优化技术是指预设若干具有相同页面颜色的内存页面作为 页面颜色队列， 弱局部性数据集的数据页面首先通过异步方式进入页面颜 色队列， 然后再被加载到 CPU缓存中完成数据处理。 该技术可以将弱局部 性 （一次性访问或重复访问周期较长） 数据缓存于页面颜色队列后再进行 访问， 从而进一步降低缓存之间的冲突。

动态页面颜色队列优化技术的具体实施步骤如下： 首先在内存数据库 的内存中申请 n (n为自然数）个页面颜色相同的页面作为页面颜色队列， 该页面颜色队列用作内存页面被加载入 CPU缓存之前的内存缓存。 页面颜 色队列采用循环队列方式， 即在页面颜色队列中， 当第 i个队列页面被访 问后即可成为交换页面被后续待访问页面覆盖。 数据页面在访问时依次被 复制到页面颜色队列中， 然后再调入 CPU缓存， 即页面颜色队列作为弱局 部性数据集的内存缓存。 数据页面复制到页面颜色队列采用 DMA memcpy 模式。 DMA memcpy模式在进行内存块复制时通过 DMA通道而不经过 CPU处 理， 因此不产生额外的缓存污染。 页面颜色队列的长度由数据页面加载到 CPU缓存的延迟以及 DMA memcpy模式本身的延迟决定。 若加载到 CPU缓存 的延迟较小， 则增加页面颜色队列长度以提高缓存效率。

页面颜色队列采用流水更新模式， 即页面颜色队列中第 i ( i 为自然 数） 块的缓存加载操作与第 i-1块的页面复制流水并行， 例如当 B1块加 载到缓存后依次加载页面颜色队列中的 B2块，此时 n+ 1块可以复制到 B1 块中。 此时， 数据访问指针为 i mod n， 数据更新指针为 （i一 1 ) mod n (n代表页面颜色队列中的页面数）。

图 6显示了动态页面颜色队列优化技术的执行原理。其中， B1?B4为 页面颜色队列， Pl、 P2、 ……为数据集页面。 页面颜色队列为循环队列， 第 i个页面为访问指针， 第 i-1个页面为更新指针， 第 i个页面的访问 与第 i-1 个页面的更新同步执行。 数据页面向页面颜色队列的复制操作 采用 DMA通道支持的 memcpy模式， 直接在内存页面之间进行复制， 不经 过 CPU以便降低 CPU开销和所造成的额外缓存污染。

图 7为现有技术中索引扫描的示意图。 索引扫描按键值顺序扫描， 在 内存地址上体现为随机访问， 无法预先优化访问顺序， 不能直接使用静态 页面 W-order扫描技术。索引扫描时首先访问索引中的指定值的索引项， 当索引字段存在重复值时， 索引扫描首先转换为对索引中指定范围索引数据项的扫描， 在扫描过程根据索引项的地址信息实现对物理记录的实际访 问。 由于索引中的物理地址以记录为单位， 采用动态页面颜色队列优化技 术优化的是整个页面的访问顺序， 因此代价较高而效率较低。

图 8显示了应用于索引扫描中的缓存优化实现原理。在图 8中，用 oid 表示记录物理地址， contract 表示索引键值列， PC表示页面颜色号。 在 索引中通过动态地址翻译函数在记录地址中抽取出页面颜色号， 或者在生 成索引时产生记录地址页面颜色的辅助数据结构 （即在索引中增加一个页面颜色数据项来记录当前记录所在的页面颜色号）。 当执行索引扫描时， 如果选择率较低， 则直接执行随机访问， 不进行缓存优化； 如果索引扫描 的选择率高于某个阈值时， 则执行多趟页面颜色扫描。

例如我们通过物理页面起始地址 " 10FFEF", 根据页面颜色位解析出 其对应的页面颜色号为 62。在记录地址中抽取出页面颜色号。 当执行索引 扫描时， 如果选择率较低， 则直接执行随机访问， 不进行缓存优化。 在实 践中，通常根据索引字段的统计信息，如对"产品型号"字段进行索引时， 统计出各个不同产品型号的不同值的个数， 在进行索引扫描时， 根据查询 条件， 如 "产品型号 =‘ 平板电脑‘ "来估计可能满足条件的记录数量， 进而判断选择率的高低。 如果索引扫描的选择率高于某个阈值时， 则执行 多趟页面颜色扫描。 该阈值需要根据实验测试结果和经验值来确定， 如通 过实验测度得到选择率高于 30%时， 执行多趟页面颜色扫描会优化整体性 能等。 具体实现步骤包括图 8下半部分的两个虚线框中所示的处理流程。

左侧的虚线框表示对索引中特定范围记录的扫描采用多趟扫描的方 法， 每趟扫描时只访问指定页面颜色对应的记录， 即第一次访问页面颜色 为 0的记录， 以此类推。 为减少多趟扫描中对无效记录的访问， 我们在执 行多趟扫描时通过一个页面颜色矢量位图来记录已访问的记录位置， 随着 多趟记录访问的进行， 页面颜色矢量位图中 1 (页面颜色矢量位图记录已 扫描的页面颜色号， 如扫描完页面颜色为 0的所有页面后， 位图的第 1位 更改为 1， 扫描完颜色号为 1的所有页面的， 位图的第 2位置 1， 以此类 推） 的位置越来越多， 后续扫描时可跳过扫描的记录比例越大， 随机访问 效率越高。 在多趟扫描时采用 W-order 扫描顺序， 即先从上至下扫描页 面颜色为 i 的记录， 然后至下而上扫描页面颜色为 i + 1 的记录， 以此类 推。 多趟 W-order 扫描使序列首尾的数据重用路径变短， 可以提高缓存 中已缓存数据的利用率。 右侧的虚线框表示采用对索引中指定范围的记录 按页面颜色排序后再访问。 当索引查找的范围较大、 记录较多时， 排序代 价较高， 会影响缓存优化带来的性能收益。

上述 W-order扫描优化技术以数据集为粒度实现了对不同访问局部 性数据集的优化访问， 在一个数据库查询处理线程内部达到了最小缓存访 问冲突。 但对于多核处理器而言， 通常采用共享 CPU缓存的硬件结构， 因 此还需要进一步考虑在一个共享 CPU缓存中的多个并行处理线程之间的数 据访问优化问题， 减少并发处理线程对共享 CPU缓存的访问冲突。 图 9显示了利用本缓存访问优化方法在多核处理器中实现并行哈希连 接查询处理的工作原理。 对于多核处理器中的并行哈希连接， 每个哈希连 接处理线程独立执行基于 W-order扫描的哈希连接算法。 图 9中左半部 分表示两个处理线程共享 CPU缓存和内存地址空间， 右半部分表示通过缓 存分区技术将 CPU缓存划分为两个分区以服务于不同的处理线程。 图 9中 浅色块表示顺序访问数据集， 深色块表示哈希表。 从图 9中可以看出， 当 两个独立的哈希连接处理都采用 W-order扫描的处理技术时， 在每个页 面颜色地址区域内顺序访问数据集与哈希表冲突的页面数量相当， 冲突概 率相同。 即在多核处理器中并行哈希连接查询处理时， 每个查询可以使用 同构的 W-order扫描优化技术。

以上对本发明所提供的基于页面染色技术的内存数据库访问优化方 法进行了详细的说明。 该方法主要应用于内存数据库中数据预先驻留内存 的应用场景， 尤其适用于大数据集的内存 0LAP 查询处理优化。 该方法不 仅可以应用于现有内存数据库的哈希连接算法， 还可以应用于能够明确划分出弱局部性数据集和强局部性数据集的数据处理技术。

以上对本发明所提供的基于页面染色技术的内存数据库访问优化方 法进行了详细的说明。 对本领域的技术人员而言， 在不背离本发明实质精 神的前提下对它所做的任何显而易见的改动， 都将构成对本发明专利权的 侵犯， 将承担相应的法律责任。

SRC=https://www.google.com.hk/patents/WO2013155750A1

基于页面染色技术的内存数据库访问优化方法