学术论坛
基于CMP的内存数据库索引性能优化
欧阳炜昊李灿辉
(湖南大众传媒职业技术学院湖南长沙410100)
敬事我专真
摘要：本文面向提供强大计算能力的CMP，采用流水线式多线程执行模式，对CSB+-Trees进行了优化，采用多线程访问模块提高索引访问索引时的时间局部性和空间局部性，从而改善素引访问线程的执行效率。
关键调:内存数据库CSB+-Trees索引
文献标识码：A
中图法分类号：TP311 1、背最知识
文章编号：10079416（2011)050096~02
单的同时多线程处理器，所以它就可以拥有单片多处理器主频
内存数据库(MMDB，MainMemoryDataBase）是一种将数据完全加载到内存并在内存中实现对数据进行管理的数据库。MMDB 对数据库的体系结构进行重新设计，没有采用传统的磁盘数据管理，对数据组织结构、索引技术、并行操作等方面进行了相应改进，有效地解决了基于磁盘的数据库中CPU和磁盘I/O之间的主要矛盾，和传统基于磁盘的数据库相比，数据读写速度高出几个数量级，能够极大地提高应用的性能。MMDB具备基于磁盘数据库的所有特性，如数据库的定义、存储、维护等数据的持久化管理，数据增副查改及完整性检查等操作，事务调度与并发控制，数据存取的控制和安全性检验，数据的可靠性恢复机制。
索引影响着数据库的执行效率，同样，索引结构在很大程度上决定访问内存数据库的效率等各方面的性能。最常见的B+树由于受节点远大于CacheLine和节点中需存储大量的指针数据等因素的影响，其Cache访间性能较差。针对此种情况，一些学者提出了Caehe数感的紧引树结构，比较常见的有CSS树、CSB+树和 T树。Cache访间性能是影响MMDB性能的重要因素之一，而在共享Cache多核处理器条件下，如果只采用单线程模式执行索引访问，势必不能充分发挥CMP的并行计算资源；而传统的多线程执行方式，即每个索引访问线程都需要执行自顶向下的索引遍历，则会由于CSB+-Tree的根节点层及其子节点层中的节点被重复访间的概率要远大于其它节点层中的节点，导致紫引访问时的时间局部性和空间局部性较差，而且底层节点数据更容易将项层节点数据替换出共享Cache，造成共享Cache访间冲突。同时，由于 CSB+树节点较小树高较大，更降低了线程访间索引数据时的局部性。因此，以传统的多线程执行方式访问索引，线程的Cache访间性能不佳，影响了索引访间的性能。
随着集成电路CMOS制造工艺的持续提高，单个门电路的尺寸都在不断变小，基于半导体的微电子技术的物理极限问题成为一个重要的设计所关心的间题。物理极限的影响造成了散热及数据同步问题。对于更复杂、处理能力更强的处理器的需求促使处理器设计人员利用各种各样的可行方案提高处理器的性能。处理器主频、内存访问速度和I/0速度发展不同步已经成为很大的瓶颈，单纯依靠提高处理器主频来提升整个系统的性能已经不可行，并行计算技术成为解决之道。线程级并行TLP计算技术对于很多应用场合都是合适的，它通过利用多个独立的CPU来提高系统的性能。时至今日，集成电路技术的发展及减少系统占用面积的要求最终促使了多核处理器的出现。多核多线程处理器是通过支持单片多处理器（CMP）和同时多线程（SMT）的组合来实现的。多核多线程处理器由多个简单的同时多线程处理器核构成，它提供了一种更加简单有效的方法去提高集成度。它不同于超标量处理器通过硬件来提取指令级的并行，是通过编译器的支持多核多线程处理器可以提供一种线程级的并行。由于它由多个简
96
方方数据
高、设计和验证时间短的优势，又拥有同时多线程资源利用率高的优势，从而大大提高程序的运行效率。目前，越来越多的芯片生产商和研究机构都将注意力放在了多核多线程处理器的研究上。正是因为多核与多线程技术的大量使用，使得处理器处理能
力能跟上时代发展。 2、相关研究"
索引影响着数据库的执行效率，同样，索引结构在很大程度上决定访问内存数据库的效率等各方面的性能。由于等值查询最为常用，所以缓存敏感的索引结构通常用来加速查询的速度。以下是常见的3种缓存敏感索引结构。
T树：T树在较早的时候提出，改善了B+树浪费内存空间的间题，由于高度过大，没有做缓存优化，T树的缓存性能还不如 B+树。
CSS树：它是Array索引的一种改进，通过连续存储方式，去除了节点和数据项的指针，提高了对缓存的利用率。但树的连续存储方式限制了其动态更新的能力，因此，CSS树比较适合于数据相对静态的OLAP领域，
CSB+树：它是在B+树的基础上对缓存做优化，只在节点头部保存了一个指向下层节点组的指针。同时，兄弟节点之间建立组的概念并连续存储，通过指针和偏移量定位子节点。这样的设计提高了缓存的利用率，减少了查询过程中缓存失效的次数。然而，CSB+树的不足在于节点大小都控制在一个缓存块左右，一般为64Byte和128Byte，当索引项数很大时，CSB+树的深度很大，在
查询路径上会带来更多的TLB失效问题。 3、相关工作
3.1基于CMP的CSB+-Trees访问性能优化
基于CMP进行优化，充分利用多核处理器的并发能力，需要对原有的索引进行并发改进。首先，改进索引结构，将单路查询转为多路查询，每一路查询用独立的线程处理。然后，分解每个查询或更新任务，如并行处理二分查找过程等。最后，对于批量查找或者更新的任务，将任务分组，并行处理每个任务组。
任务池是MSI编程模型的基本组成部分，同一个任务池中的多个任务可以由不同的线程并行执行。多个任务池可以相互连接，以描述流水线或其他拓扑结构的任务池依赖关系。如一个包含3个任务池的流水线结构，当任务池1中的子任务执行完成以后，得到的中间结果便会传给任务池2，并由任务池2执行再产生中间结果，如此类推，直到最后一个任务池执行完任务并输出最终结果，由此把任务变成流水线式地执行，在此过程中，MSI中的线程调度器将根据各个任务池的负载情况动态调度每个任务池
**·下转第95页