《多核处理器下事务型数据库性能优化技术综述》由会员分享，可在线阅读，更多相关《多核处理器下事务型数据库性能优化技术综述（15页珍藏版）》请在金锄头文库上搜索。
1、书书书第 卷第期 年月计算机学报 收稿日期： ； 最终修改稿收到日期： 本课题得到国家自然科学基金（ ， ） 、 中央高校基本科研业务费专项资金（ ， ） 和中国人民大学研究生科学研究基金（ ） 资助朱阅岸， 男， 年生， 博士研究生， 主要研究方向为高性能数据库系统 ： 周?（ 通信作者） ， 男， 年生， 博士， 副教授， 主要研究方向为高性能数据库、 信息检索 ： 张延松， 男， 年生， 博士， 讲师， 主要研究方向为内存数据库、 周明， 男， 年生， 硕士， 主要研究方向为内存数据库牛嘉， 女， 年生， 硕士， 主要研究方向为高性能数据库王珊， 女， 年生， 教授，博士生导师， 中国计
2、算机学会（ ） 高级会员， 主要研究领域为高性能数据库、 知识工程、 数据仓库多核处理器下事务型数据库性能优化技术综述朱阅岸） ，）周?） ，）张延松） ，） ，）周明） ，）牛嘉） ，）王珊） ，）（ 中国人民大学信息学院北京 ）（ 数据工程与知识工程教育部重点实验室（ 中国人民大学）北京 ）（ 中国人民大学中国调查与数据中心北京 ）摘要传统数据库的设计假设磁盘为主要存储设备， 其性能取决于基于代价模型的优化然而， 当前数据库运行的平台已逐渐转移到由多核处理器、 大内存和以闪存为代表的低延迟存储所构成的新型硬件平台上在大多数情况下， 工作数据集能够全部加载到内存或者闪存等高速存储器中这样，
3、数据库的性能瓶颈由传统的转移到 上而传统数据库的加锁操作、 闩锁竞争、 日志管理以及缓冲区管理在设计时均未考虑到多核处理器的使用， 因而成为了限制 利用率的明显瓶颈改变传统数据库的优化重点以适应硬件的发展对应用而言是十分必要的该文针对当前新的应用背景， 主要围绕数据库系统中锁管理、 日志管理、 缓冲区管理以及树索引等核心模块在多核平台下已有的优化技术进行详细介绍和归纳总结同时介绍了中国人民大学在数据库系统的多核处理器优化方面所做的一些工作关键词数据库系统优化； 锁； 日志； 缓冲区管理；树中图法分类号 犇 犗 犐号 犃犛 狌 狉 狏 犲 狔狅 犳犗 狆 狋 犻 犿 犻 狕 犪 狋 犻 狅 狀犕
4、 犲 狋 犺 狅 犱 狊 犳 狅 狉犜 狉 犪 狀 狊 犪 犮 狋 犻 狅 狀 犪 犾犇 犪 狋 犪 犫 犪 狊 犲 犻 狀犕 狌 犾 狋 犻 犆 狅 狉 犲犈 狉 犪 ） ，） ） ，） ） ，） ，） ） ，） ） ，） ） ，）（犛 犮 犺 狅 狅 犾 狅 犳犐 狀 犳 狅 狉 犿 犪 狋 犻 狅 狀，犚 犲 狀 犿 犻 狀犝 狀 犻 狏 犲 狉 狊 犻 狋 狔狅 犳犆 犺 犻 狀 犪，犅 犲 犻 犼 犻 狀 犵 ）（犓 犲 狔犔 犪 犫 狅 狉 犪 狋 狅 狉 狔狅 犳犇 犪 狋 犪犈 狀 犵 犻 狀 犲 犲 狉 犻 狀 犵犪 狀 犱犓 狀 狅 狑 犾 犲 犱 犵 犲犈 狀 犵 犻 狀
5、 犲 犲 狉 犻 狀 犵狅 犳犕 犻 狀 犻 狊 狋 狉 狔狅 犳犈 犱 狌 犮 犪 狋 犻 狅 狀（犚 犲 狀 犿 犻 狀犝 狀 犻 狏 犲 狉 狊 犻 狋 狔狅 犳犆 犺 犻 狀 犪） ，犅 犲 犻 犼 犻 狀 犵 ）（犖 犪 狋 犻 狅 狀 犪 犾 犛 狌 狉 狏 犲 狔犚 犲 狊 犲 犪 狉 犮 犺犆 犲 狀 狋 犲 狉犪 狋犚 犲 狀 犿 犻 狀犝 狀 犻 狏 犲 狉 狊 犻 狋 狔狅 犳犆 犺 犻 狀 犪，犅 犲 犻 犼 犻 狀 犵 ）犃 犫 狊 狋 狉 犪 犮 狋 ， ， ， ， ， ， ， ， 犓 犲 狔 狑 狅 狉 犱 狊 ； ； ； ； 引言摩尔定律揭示了集成电路上晶体管集
6、成度的增长规律， 摩尔定律首先表现为 主频的持续增长， 然后又表现为 核心数量的持续增长 的频率持续逐年增长， 加上其指令执行的并行度也在增加， 使得单线程的工作性能不断提高，早在 年， 的频率就已经达到 然而， 高频率的 带来的是更多的能耗， 现实应用中不一定会带来高的性价比， 因而阻止 主频的进一步发展这个问题使得近年来 的发展方向产生了转变为了进一步优化 的性能， 生产商倾向于在单个 上增加更多的处理核心 开始转向使用并行多线程和片上多处理器技术， 以替代单处理流的高度复杂 技术生产商不再竞争速度而是转向提高并行度按照最近多核的发展趋势， 单个 上的核数基本每两年翻一倍大部分研究人员预测
7、， 的核数会继续增长一段时间为了更好地利用新 的并行处理能力， 工程师需要修改或重新设计软件系统而基础软件， 包括操作系统、 服务器和数据库等， 则会最先遇到复杂的多核架构带来的扩展性问题操作系统社区对 类型操作系统在共享内存多处理器上的扩展性研究已经进行了很长一段时间大家公认粗粒度的锁是导致系统扩展性差的主要原因现有的研究成果均建议将多核架构看作分布式系统， 利用共享内存进行快速消息传递， 而系统设计的主要思想集中在增加数据局部性和均衡处理核心之间的负载 诸多实用的研究成果， 如分布式内存管理、 可扩展的封锁技术、 避免等待的同步技术和针对多处理器调度技术， 都已经被工业界采纳， 并被植入了
8、新的 内核从一开始， 数据库存储引擎的研究就是定位在高负载下的高性能和可靠性一方面， 数据的可靠性和一致性大都通过在共享数据结构上的封锁机制实现； 另一方面， 在现代多核架构下， 性能的提升必须通过利用更高程度的并行性如何解决这两者之间的矛盾是一个很大的挑战现实中， 关系数据库系统大部分是基于优化和面向单处理器的陈旧设计思想， 并不适合多核处理器的架构以事务处理为主的数据库系统多数依赖并发取得高吞吐率并发是通过多线程或者多进程实现的理想情况下， 随着硬件上下文的增加， 他们应该具备良好的扩展性， 特别是针对以读为主工作负载实际上， 为了维护一致性和持久性， 数据库系统大量使用共享数据结构和同步
9、原语在高度并行的环境下， 对共享数据进行频繁的原子更新不得不由线程串行地执行因此， 用于保护共享数据结构的同步原语会导致很大的同步开销这些同步原语大量存在于共享内存缓冲区、 锁表、 索引与日志管理器中此外， 丰富的硬件上下文使得并行线程竞争硬件资源， 例如，高速缓存的争用将降低缓存命中率从而增加内存访问延迟另外， 传统的封锁方式例如阻塞和忙等待策略在多核环境下效率低下增加的并行度还会导致更大异构的工作负载， 这给索引数据结构里的读写同步控制原语也造成更大的压力总之， 所有这些原因导致了运行在多核架构上的数据库系统的性能瓶颈近年来， 学者们提出许多不同的思想和方法， 用于重新构建多核环境下的数据
10、库系统本文的目的是对已有的多核数据库优化技术进行总结和讨论同时介绍了中国人民大学在数据库多核优化所做的一些努力纵观整个数据库系统内核， 多核扩展的瓶颈突出表现于锁管理、 日志管理器、 缓冲区管理和索引（ 主要是 ） 四大部件本文依次对这四大部件的多核优化技术做整理归纳锁管理器的多核优化几乎所有的数据库都利用某种形式的多粒度封锁机制， 允许应用程序在并发度和系统开销之间进行一个折中多粒度锁机制将数据库视为嵌套的数据结构数据库中包含表， 表又由一系列页面组成，页面包含元组每个层次的数据结构都有一个锁与之相对应例如， 访问大量数据的请求可以申请大粒度的锁对表进行封锁， 牺牲并发度以减少系统开销对于访
11、问少量数据的请求可以只对它们需要访问的数据加锁， 以最大化系统并发度多粒度锁机制对于系统的扩展性至关重要， 因为它在逻辑层面上实现高效的细粒度并发控制这种多粒度的锁机制可以有效控制系统的并发度， 然而也给系统扩展性带来新的问题单节点的数据库系统在处理器数目较少的时候利用分时机制处理请求， 对资源的竞争不明显随着处理器上核数的不断增加， 硬件并发度的增大， 集中式的锁管理器遇到了瓶颈， 尤其是当多粒度锁强制许多线程不断地更新某些频繁访问的锁的状态时为了访问数据库系统的某个元素， 所有的事务都必须获得高层次上的意向锁， 使得这些意向锁的访问异常频繁对锁的访问必须具备原子性， 导致临界区资源竞争对于
12、具有良好扩展性的数据库程序计算机学报 年而言也会遇到与锁相关的瓶颈， 即使它们几乎不会引起逻辑上的冲突为了降低锁管理器的资源竞争， 要么降低加锁的次数， 要么减轻加锁过程中原子操作的排他性， 要么进一步分布化并行化锁管理器从而缓解对锁资源的争夺以下逐一介绍现有的种锁管理器多核优化策略 锁的传递与继承 利用投机锁继承机制减少网络传输代价在这个分布式数据库中， 系统的任意一个节点可将锁传递到请求该锁的另外一个节点上文献 简要地描述了“ 锁传递” 的思想： 只要没有冲突的锁请求到来， 可以将锁缓存在本地， 而不用在事务结束的时候将锁返回给主节点这种方式避免了将锁返回给主节点的开销如果锁可以被后面的事
13、务重用， 那么每一次锁传递可以省略一趟网络传输对于两节点的系统而言， 性能可以提高 以上 等人将锁传递思想应用在单节点的数据库系统上以解决锁状态上的竞争不同于 的高网络传输代价和较少的节点数目， 文献 在共享高速缓存和内存的多核平台上利用单节点 数据库系统 实现投机锁继承算法 （ ， ） 将锁管理器上的封锁请求分发到不同的线程， 以减少冲突 思想主要基于以下观察： 应用程序几乎总是以相容模式申请某些热锁； 否则， 若某一时刻系统的大部分事务被阻塞在某个排它锁上， 不会为更新锁的状态而造成竞争如果大部分事务以相容模式申请热锁， 那么事务可以较长时间持有该锁而不会降低系统并发度这个锁只需保证少数更
14、新事务可以正确地隔离其他事务 利用被频繁访问的共享锁无逻辑上的竞争， 消除在锁内部临界区的物理竞争 允许事务结束的时候将它所持有的锁传递给下一个事务这种策略避免了对每一个传递的锁申请和释放时都需要调用锁管理器在事务提交的时候， 事务的代理线程挑选候选传递锁， 然后将这些锁存放于线程的局部锁列表， 并用局部锁列表初始化下一个事务的锁列表 机制利用以下条准则选取锁作为候选继承锁： （） 这个锁是页面上或者是更高层次上的锁； （） 这个锁被频繁访问； （） 这个锁以共享模式（、 、 ） 为某个事务所持有； （） 没有别的事务等待这个锁； （） 如果该锁上存在更高层次上的锁， 上述条件仍然成立 通过以
15、下两个途径优化性能： （） 减少事务的锁申请和释放的次数， 从而取得较快的响应时间， 多个短事务可以分摊锁申请开销； （） 申请锁的其他事务面临较少的锁管理器内部临界区的竞争， 这种方法适用于短事务， 以便分摊锁申请和释放的开销另外， 投机锁继承也仅限于共享锁和页级以上的锁， 并且没有其他事务等待该锁文献 利用消除闩锁（ ） 的数据结构取代传统的锁和缓冲区哈希表， 降低了事务申请锁和释放锁的开销这种方法能够取得与投机锁继承方法接近的性能， 但是不会受到事务特性限制 数据库系统也提供了一个参数 ， 允许事务甚至是会话持有只读模式的表级锁， 直到必要才释放锁然而， 只有当事务不断地释放然后又重新申
16、请相同的锁的情况下， 这种策略才会有收益 文档提示在一个会话的生命周期内一直持有表级锁会导致较差的并发性能， 因为其他事务不能执行更新操作这个设置在 默认是禁用的 轻量级并发原语现代 提供多种并发控制原语， 其中在数据库常用的两种为： 原子读后写（ ，） 和写后读（ ， ）在中， 线程进程以原子操作的方式读取一个公共变量然后写回 的原子性是通过闩锁（ 例如旋转锁， ） 而获得的闩锁的实现依赖机器 的 原 子 指令 例 如 或 在基于探测方式保持高速缓存一致性的现代多处理器体系结构上， 会导致高速缓存失效， 占用系统总线带宽这是因为当某一个进程释放闩锁以后， 它需要将犳 犪 犾 狊 犲写入锁变量
17、这会使得其他竞争者的相应的高速缓存内的锁变量失效其他竞争者各承受一次高速缓存未命中， 重新读入新值，接着调用 指令获取锁第一个成功获得锁的进程又会使得其他竞争者的高速缓存的锁变量副本失效， 从而又需要再次读取内存导致总线拥挤另外一个可替代的编程方式是 具体的方式是进程 写某一公共变量犃， 接着该进程读取另外一个不同的公共变量犅若在这之间没有别的进程写公共变量犅， 可以保证并发进程看到共享变量的顺序一致性状态利用 编程方式必须确保并发进程只能看到共享变量的可串行化的一致性状态图（） 展示了可能出现的问题期朱阅岸等：多核处理器下事务型数据库性能优化技术综述 ： 进程和根据 模式访问公共变量犃和犅在
18、没有限制的情形下， 如图（） ， 数据的竞争可能导致进程看见犅和进程看见犃（ 由于高速缓存内容的改变没有及时反映到内存上）这违背了可串行化原则图（） 展示了利用内存栅障（ ） 协调进程访问内存的顺序以保证程序执行的正确性， 实现可串行化， 也就是保证进程和能够看到这些写操作虽然执行内存栅障会带来一定的开销， 但是每一个进程只需付出一次硬件代价相比而言，会导致高速缓存块在进程之 间 频 繁 切 换， 造 成 系 统 颠 簸 等 人认为在多核平台上 编程模式更具有扩展性利用 ， 他们将锁管理器修改为几乎不用闩锁的方式修改后的锁申请和释放的伪代码如表所示传统的锁管理器中， 事务首先在数项上创建一个锁
19、然后将这个锁插入这个数据项上的锁列表（ 这时候需要对锁表进行封锁）然后， 这个事务遍历该数据项上的锁列表， 检测是否存在不相容的锁如果存在， 则标记这个锁为等待状态， 接着进行死锁检测利用原子操作可以去除哈希表上的闩锁右侧是改写后去除闩锁的代码， 它用函数犪 狋 狅 犿 犻 犮犾 狅 犮 犽犻 狀 狊 犲 狉 狋（ ）将锁 以 原 子 操 作 的 方 式 加 入 哈 希 表与 安 全 的 一致， 每次写一个共享变量， 接着读另外一个不同的共享变量都要有内存栅障的保护修改后的代码中增加了一个新的锁状态犗 犅 犛 犈 犔 犈 犜 犈这个新的状态是为了批量回收锁的内存而设计的， 表示表犕 狔 犛 犙
20、 犔中锁的申请和释放的实现（ 左边的代表原来的实现， 右边的代表减少闩锁的实现犛 ，犛 ， ，犛 表示需要加犚 犃犠同步的地方）传统的锁管理器改进的锁管理器增长阶段的锁请求犿 狌 狋 犲 狓犲 狀 狋 犲 狉（ ） ；狀犾 狅 犮 犽犾 狅 犮 犽犮 狉 犲 犪 狋（） ；狀犾 狅 犮 犽 ； （狀犾 狅 犮 犽） ； （犾 狅 犮 犽） （犾 狅 犮 犽 狀犾 狅 犮 犽） 狀犾 狅 犮 犽 ； （犱 犲 犪 犱 犾 狅 犮 犽犮 犺 犲 犮 犽（ ） ） 犜 狓； ； ； 犿 狌 狋 犲 狓犲 狓 犻 狋（犾 狅 犮 犽狋 犪 犫 犾 犲 ） ； （狀犾 狅 犮 犽 ）犿 狌 狋 犲 狓犲
21、 狀 狋 犲 狉（犜 狓 ） ；犜 狓 ；犗 狊犮 狅 狀 犱狑 犪 犻 狋（犜 狓 ）犿 狌 狋 犲 狓犲 狓 犻 狋（犜 狓 ） 狀犾 狅 犮 犽犾 狅 犮 犽犮 狉 犲 犪 狋（ ） ；狀犾 狅 犮 犽 ；犪 狋 狅 犿 犻 犮犾 狅 犮 犽犻 狀 狊 犲 狉 狋（狀犾 狅 犮 犽） ； 犛 （犾 狅 犮 犽） （犾 狅 犮 犽 狀犾 狅 犮 犽）狀犾 狅 犮 犽狊 狋 犪 狋 犲 犠犃 犐 犜； 犛 犪 狋 狅 犿 犻 犮狊 狔 狀 犮 犺 狉 狅 狀 犻 狕 犲（ ） ； （ ） 狀犾 狅 犮 犽狊 狋 犪 狋 犲 犃 犆 犜 犐 犞 犈； 犛 犪 狋 狅 犿 犻 犮狊 狔 狀 犮
22、犺 狉 狅 狀 犻 狕 犲（ ） ； ； （狀 犲 狑犱 犲 犪 犱 犾 狅 犮 犽犮 犺 犲 犮 犽（ ） ） 犜 狓； ； ； （狀犾 狅 犮 犽 ）犿 狌 狋 犲 狓犲 狀 狋 犲 狉（犜 狓犿 狌 狋 犲 狓） ； 犛 犪 狋 狅 犿 犻 犮狊 狔 狀 犮 犺 狉 狅 狀 犻 狕 犲（ ） ； （狀犾 狅 犮 犽 ）犜 狓 ；犗 狊犮 狅 狀 犱狑 犪 犻 狋（犜 狓 ） 狀犾 狅 犮 犽狊 狋 犪 狋 犲 犃 犆 犜 犐 犞 犈； 犛 犪 狋 狅 犿 犻 犮狊 狔 狀 犮 犺 狉 狅 狀 犻 狕 犲（ ） ； 犿 狌 狋 犲 狓犲 狓 犻 狋（犜 狓 ） 收缩阶段的锁请求犿 狌 狋
23、犲 狓犲 狀 狋 犲 狉（ ） ； （犾 狅 犮 犽） 犜 狓 犾 狅 犮 犽狉 犲 犾 犲 犪 狊 犲（犾 狅 犮 犽） ； （犾 狅 犮 犽） 犾 狅 犮 犽 犾 狅 犮 犽 犾 狅 犮 犽犵 狉 犪 狀 狋（犾 狅 犮 犽）犾 狅 犮 犽 ； 犿 狌 狋 犲 狓犲 狓 犻 狋（ ） ； （犾 狅 犮 犽） 犜 狓 犾 狅 犮 犽狊 狋 犪 狋 犲 犗 犅 犛 犈 犔 犈 犜 犈； 犛 犪 狋 狅 犿 犻 犮狊 狔 狀 犮 犺 狉 狅 狀 犻 狕 犲（） （犾 狅 犮 犽） 犾 狅 犮 犽 犿 狌 狋 犲 狓犲 狀 狋 犲 狉（犾 狅 犮 犽犜 狓 ） （犾 狅 犮 犽犜 狓 犾 狅 犮
24、犽 ） 犾 狅 犮 犽犜 狓犿 狌 狋 犲 狓 犃 犆 犜 犐 犞 犈； 犛 犪 狋 狅 犿 犻 犮狊 狔 狀 犮 犺 狉 狅 狀 犻 狕 犲（） ；犗 狊犮 狅 狀 犱狊 犻 犵 狀 犪 犾（犾 狅 犮 犽犜 狓） ；犕 狌 狋 犲 狓犲 狓 犻 狋（ ） ； 计算机学报 年图安全的与不安全的 比较这个锁不再有效同时， 需要设计新的死锁检测算法， 以避免竞争修改后的锁释放代码也去除了闩锁， 根据安全的 模式增加内存栅障注意到修改后的锁管理器只是将锁标记为犗 犅 犛 犈 犔 犈 犜 犈而没有释放结构体的内存这个阶段不会产生悬挂指针实际的锁内存释放以批量的方式异步进行重要的是， 锁释放代码需要检
25、查在这个锁之后申请的其他锁， 唤醒因为申请与当前锁不相容的锁而被阻塞的事务文献 的核心思想是将锁数据结构的内存分配和释放与事务对锁的申请和释放解耦合对锁数据结构的内存分配和释放以批量的方式进行， 与事务处理异步批量方式进行锁分配和回收的方法的潜在问题是过时的锁存在于锁管理器的哈希链表中， 从而使得链表较长 分散锁管理器功能 等人 提出的技术彻底更改了传统的集中 式 锁 管 理 策 略一 是 （ ）该技术对锁管理器作了两点主要改变： 不再将锁信息集中存储， 而将锁的信息与数据一起存储， 例如行级锁， 在表的属性中增加一个隐藏属性，来记录每一行记录的锁信息， 这样数据和锁信息位于同一个高速缓存块里
26、， 可以提高高速缓存命中率； 另一点是用信号量（ 整数） 来取代请求列表， 并且给事务排序， 事务按照到达顺序请求锁， 且在事务开始执行前一次性请求全部锁另一种技术是 （ ） ， 该技术用来解决 并发性差、 利用率低的问题 技术取消了传统锁管理器使用的列表， 改而为每一个加锁对象维护一个整数对（犆 狓，犆 狊） ， 分别代表请求该对象的排它锁、 共享锁的事务数每个请求锁的操作， 只用简单地将对应的犆 狓或犆 狊加一， 与之相对应， 每个释放锁的操作， 只用简单地将对应的犆 狓或犆 狊减一显然， 当事务请求某个对象的排它锁时， 将该锁对应的犆 狓加一， 当且仅当此时犆 狓，犆 狊， 事务获得该排
27、它锁； 当事务请求某个对象的共享锁时， 将该锁对应的犆 狊加一， 当且仅当此时犆 狓， 事务获得该共享锁除此之外， 在每个 ， 都有一个事务请求序列 当新事务到达时， 它一次性请求所有锁（ 即将对应的犆 狓和犆 狊加一） 后加入请求队列在事务请求锁之后， 系统检查它请求的所有锁， 如果事务可以顺利获得请求的所有锁， 该事务加入请求队列 时被标记为 ， 且立即执行； 反之， 事务被标记为阻塞， 直到被系统判定为可以解除阻塞后再执行事务提交时， 释放所有锁（ 即将对应的犆 狓和犆 狊减一） ，然后从 移除在传统的锁管理器中， 当锁释放时， 通过遍历锁的请求列表来决定继承锁的事务， 而 里没有请求锁
28、的事务的信息， 它只是简单的根据以下的理由选择队列中排在最靠前的阻塞事务来解除阻塞然后执行： 排在队列头部的事务， 之前使得它阻塞的事务已经全部提交且从队列中移除了， 所以这个事务肯定可以获得所有锁这样一来，系统中每个时刻最多只有一个阻塞的事务可以被解除阻塞并执行随着事务的执行、 提交， 其他很多在传统锁管理情况下已经可以被解除阻塞（ 使它阻塞的事务已经提交了） 的事务， 也只能等待排在它前面所有的事务都提交才能被解除阻塞后执行， 这大大降低了竞争激烈时系统的并发性为了解决以上问题， 提高并发度， 提高系统的 利用率， 文献 提出了 技术 指在需要的时候（ 有空闲时， 例如队列满） 进行竞争分
29、析， 在 中寻找可以被提前唤醒的事务在 中， 排在第犻个位置的事务， 只有可能被前犻个事务阻塞， 所以越靠前的事务， 被唤醒提前执行的可能性就越大 维护两个大小为 的数组犇 狓和犇 狊， 从 头开始逐一扫描事务， 对于每个 事 务： 对 于的 中 所 有 ， 将犇 狊 （ ） 置， 对于的 中的所有 ， 将犇 狓 （ ） 置在扫描事务的同时， 如果事务是阻塞的， 将犇 狓和犇 狊置位之前， 检查的读集合的每一个 对应的犇 狓是否为， 检查的写集合的每一个 对应的犇 狊和犇 狓是否都为， 如果全部满足， 则代表与前面的事务所请求的期朱阅岸等：多核处理器下事务型数据库性能优化技术综述对象没有锁冲突
30、， 即可以被 并执行， 此时 返回这样在系统 空闲时， 算法能找到另外的不在队列头部但可以被解除阻塞并执行的事务 方法的缺点是为了提高系统并发度必须维护一个全局的读锁集合与写锁集合所有事务的读锁集合与写锁集合都会被映射到这两个集合确定在事务队列是否存在可以提前执行的事务需要在 空闲的时候不断扫描这两个集合如果某个事务持有的锁不会与事务队列中位于该事务之前的事务持有的锁冲突（ 通过扫描全局读锁集合与写集集合） 则该事务可以提前执行如果是计算密集型的事务类型， 退化为 当竞争因子小于 的时候（ 竞争因子热元组数目） ， 占据大约的系统执行时间， 而传统的锁管理器占系统执行时间的比重大约为 相比之下
31、， 性能提升很大； 当竞争因子大于 的时候， 的性能不如传统的集中式锁管理策略日志管理的多核优化日志管理器是数据库系统的一个重要部件几乎所有的数据库系统都使用集中式的预先写日志策略避免在系统崩溃的时候带来的数据的损坏和丢失已提交工作， 以保证事务的持久性 由于其集中式的设计和对的依赖使得它很容易成为性能瓶颈较长的日志刷新时间、 由日志带来的锁竞争、 日志缓冲区上的竞争都会影响系统的扩展性日志操作给系统带来的延迟主要是类 ： （） 系统必须保证事务提交之前日志必须写到非易失性存储介质； 因为磁盘的访问时间是毫秒级别的， 刷新日志通常为事务中执行时间最长的部分； 此外， 当很多小的请求使得记录日志
32、的设备例如 上达到饱和状态时， 记录日志的延迟变为串行； （） 在刷新日志的过程中， 事务一直持有写锁， 直到结束；在很多工作负载中， 这都会造成瓶颈， 特别是锁竞争激烈的场景； （） 刷新日志除了延迟以外还有其他开销； 在等待完成的过程中， 事务不能继续执行， 代理线程必须被挂起， 直到完成； 与延迟不同， 上下文切换和调度决策会消耗 时间， 不能重叠执行其他任务； 多核硬件环境下同时运行的线程很多， 这使得操作系统调度器会负载过重； （） 除了逻辑上锁的竞争和上下文切换的开销，许多线程同时想要执行日志插入操作； 集中式的日志缓冲区有明显的临界区， 其上的竞争显然也会影响系统的扩展性为了提高
33、日志管理器的扩展性， 必须设法提高日志的效率， 并且减少日志临界区的数量和缩短关键路径的长度成组提交技术 通过将许多小的刷新日志的请求组合到单个操作减缓磁盘的压力， 减少等待时间成组提交技术能够减少磁盘访问次数和增大读取的磁盘块， 进而减少磁头转动获得更好的响应时间但是成组提交技术不能消除不必要的上下文切换开销， 因为过多的事务会阻塞来自日志管理器的挂起通知异步提交技术结合了成组提交技术的优点， 将许多刷新日志的请求组合到一起， 并且允许事务结束而不用等待刷新日志操作完成这个优化将日志刷新操作从关键路径上完全移除， 但是牺牲了事务持久性这个特性， 也就是说， 已提交工作有可能由于系统崩溃而丢失
34、 等人 针对多核平台优化了的写日志操作他们重新审视了提前锁释放技术（ ， ） ， 并在个不同延迟的非易失性设备上测试了 的有效性 技术是指事务在 记录到达磁盘之前可以释放锁， 减少持有锁的时间在 技术下， 只有提交事务需要等待结束不存在其他事务需要等待提交事务的锁而与提交事务一起等待结束文献 的实验结果表明在越慢的设备上， 获得的收益越好即使是在像 上的快速磁盘设备， 也可以获得比较好的收益（ 短事务的执行时间比要短得多）另外， 数据的偏斜程度也对 造成影响如果数据偏斜度小， 对锁的竞争不激烈， 减缓锁的竞争效果不大如果数据的偏斜度大， 锁的竞争很激烈， 即使在没有等待日志刷新的情况下， 效果
35、也不好按照 的访问都是集中在 的数据上的原则， 对应数据的偏斜度为 左右， 这时候锁的竞争程度刚好是 的优化点针对多核平台上过多的调度而导致的系统瓶颈和上下文切换带来的开销， 文献 提出一种新的刷新日志的方法：流水线方式刷新日志（ ）流水线刷计算机学报 年 ： ： ： ： ： 新日志类似异步提交方式不用在等待的时候将线程挂起， 从而不会有上下文切换的开销但是不同于异步提交方式， 流水线刷新不将结果返回给客户端， 而是转而执行其他事务守护进程在完成刷新日志以后， 通知代理线程进程返回继续执行后续事务实验表明， 流水线刷新和 组合的效果能够达到异步提交的性能， 而且在系统崩溃的时候具有可恢复性图不
36、同的日志插入方式为减缓多核情况下日志缓冲区上的竞争， 文献 设计了种新的日志缓冲区管理方法传统的写日志缓冲区需要以下个步骤： （） 首先获取写日志缓冲区上的排它锁如果当时正好有其他的服务子线程在写日志缓冲区， 则此子线程必须等待直到获得写日志缓冲区上的写锁； （） 线程将日志记录复制到相应的日志缓冲区； （） 释放缓冲区上的锁由于它的简单性， 这种方法具有吸引力这个方法的缺点是： 即使是缓冲区从来不会重叠的情况下，填充日志缓冲区的操作也是串行化执行图（） 展示了由于单一的长日志记录会给后续的线程造成比较大的延迟日志记录由一个头部加上任意长度的值组成日志记录结构体空间的申请是可复合的， 也就是两
37、个连续的日志记录的缓冲区申请也可以由一个头部加上任意长度的属性值组成文献 利用这种空间的可复合性将线程对日志缓冲区的填充按组进行每一个组都有一个组织者一个组只有组织者才要竞争缓冲区上的锁， 且一个组只有最后离开的线程需要等待锁的释放组织者在等待互斥变量的时候， 后面到来的请求可以“ 回退” 到一个数组将他们的请求组合到一起如图（） 所示， 组内日志缓冲区的填充可以并行执行， 但组之间仍然串行执行由于日志缓冲的填充不具有串行特征， 只要满足以 的顺序将日志写回即可文献 修改了原来的日志缓冲区填充算法， 线程申请的锁可以在获得缓冲区以后马上释放因此将缓冲区填充与锁的持有解耦合缓冲区的填充可以按流水
38、线的方式进行： 下一个缓冲区的填充可以立刻开始， 只要线程获得日志缓冲区空间如图（） 所示， 将锁的持有与缓冲区的填充解耦合可以消除长日志记录对缓冲区填充的影响前面讨论的两张方法具有互补性， 因此将两种方法组合在一起， 把日志缓冲区上的竞争限制在某一个常数下， 同时也消除日志记录的大小对刷新日志的影响 犘 狅 狊 狋 犵 狉 犲 狊 犙 犔 犕犆的日志多核优化虽然相对传统的日志插入算法， 文献 提出将锁的持有与日志缓冲区的填充解耦合的方法具有很大优势， 但是计算日志记录在日志缓冲区所占长度的操作仍不可避免的需要串行化执行在竞争激烈的应用中， 这也会给系统的响应时间造成很大延迟中国人民大学开发的
39、 ， 即针对多核处理器优化的 ， 使用了并行化的日志填充方案 将日志缓冲区分成若干不相交区域， 日志填充分别在不同的区域并行执行每个日志记录在插入到某个日志缓冲区之前需要获取一个时间戳这个时间戳保证了日志重放顺序与对数据库操作的顺序一致 中系统日志检查点需遵循完整性原则现在给出完整系统检查点的定义定义 多路日志系统犛具有狀个日志缓冲区：犔，犔， ，犔狀，犮 犽狋狌犻对应第犻路日志缓冲区在狋狌时刻创建的检查点如果存在犮 犽狋狌，犮 犽狋狏， ，犮 犽狋狑狀， 其中，狋狌狋狏狋狑， 则称这是一个完整系统检查点图三路日志检查点创建如图所示， 由虚线包围的个检查点是同一逻辑时刻创建， 属于一个完整的系
40、统检查点系统在某时间点狋崩溃， 而第路日志缓冲的检查点没来得及创建， 那么这个系统检查点是不完整的故障恢复系统需要反向扫描日志文件寻找最近完整系统检查点犛 犆 犓 重做（ ） 例程从犛 犆 犓上每个日志检查点犮 犽犻开始挑选具有最小时间戳的日志记录进行重放为了避免日志空洞， 进行重放的期朱阅岸等：多核处理器下事务型数据库性能优化技术综述连续两个日志记录狉狋狌犻，狉狋狏犼的时间戳需要满足：狋狌狋狏我们将 与 、 开发版进行比较（ 还没有正式版， 之所以选择 是因为这个版本的 对日志系统进行了优化）实验所用的硬件平台参数如表所示实验平台的操作系统为 利用 以及我们开发的 对系统进行测试为了消除磁盘
41、的瓶颈， 数据集全部放入内存文件系统狋 犲 犿 狆 犳 狊 由一张表构成， 表模式为（犐 犱：犻 狀 狋 狆 狉 犻 犿 犪 狉 狔犽 犲 狔；犐 狀 犳 狅：狋 犲 狓 狋）为了增加日志子系统临界区的压力， 的测试语句为 更新类型数据库的连接数为 核数的两倍表实验所用硬件平台参数硬件名称参数 ? ? （ ） （ ） （ ） （ ） （ ） 的日志填充技术如图（） 所示日志记录的插入需要串行化进行本文测试所用 是开发版的 的日志填充技术如图（） 所示将日志的填充与获取临界区的锁并行化 将日志填充的临界区代码量从 的几百行缩减到只有行， 即获取临界区互斥变量以后只是简单地计算该日志记录所占的空间
42、， 然后即可释放互斥变量实验结果如图、 图所示在一个 核数的情况下，个系统的吞吐率差别不大在 个 核数的情况下， 的吞吐率在不同的测试标准上要比 的吞吐率分别高（ ） 与 （ ） ； 在 核的情况下 的吞吐率要比 的吞 吐 率 分 别 高 （ ） 与 （ ）在 的测试下， 的吞吐率在 核与 核的情况下比 的吞吐率分别高 与 ； 在 的测试下， 的吞吐率在 核与 核的情况下比 的吞吐率分别高 与 的优化效果比 开发版好图不同核数下， 利用 测试个系统的吞吐率图不同核数下， 利用 测试个系统的吞吐率值得一提的是随着像固态硬盘的新闪存产品开始进入主流的计算机市场， 闪存技术被认为是磁盘技术的替代最近
43、也有相关研究利用闪存技术提高数据库系统性能 文献 的研究表明固态硬盘可以显著提高事务写日志的性能 则主要关注以下点： （） 突破带宽限制， 利用多闪存设备， 并行化提高刷新日志操作性能； （） 解决由于设备擦除操作而引起的不同的写延迟； （） 高效的系统恢复处理； （） 将闪存设备与磁盘设备结合起来获得更好的日志操作和系统恢复性能文献 的目标是廉价、 高效和简单的日志处理方法利用闪存技术提升 日志的性能主要是加快刷新日志的性能， 而不是减缓日志模块临界区的竞争多核下的缓冲区管理在数据库系统的缓冲区管理器中， 存在缓冲块索引（ 通常由哈希表构成） 和 链等关键数据结构这些数据结构的访问具有排他性
44、即便在带宽无限大的情况下， 多核处理器对这些数据结构的访问也必须是串行的， 这造成了严重的扩展性瓶颈因此， 缓冲区管理器是多核扩展优化的重点对象已有的关于数据库系统缓冲区研究都集中在如何提高缓冲区命中率 等人 在对称多处理机上设计实验以探讨数据库大小、 缓冲区大小和计算机学报 年处理器数目对数据库性能造成的影响， 尤其是对缓冲区命中率和系统吞吐率的影响他们用 负载研究缓冲区大小与性能的关系， 发现比数据库稍小的缓冲区大小就已经足够同时， 他们也给出规则： 的数据库大小就已经贡献了 的缓冲区命中率实际上 的 和 测试数据集（ 分别由 和 演变而来） 在装备 缓冲区的 上可以产生 的缓冲区命中率为
45、了减少 链上的竞争， 将缓冲区池划分成几个物理区域， 每个物理区域都有自己的 链这种方法会减少缓冲区命中率， 尤其是数据偏斜比较严重的时候同时， 这种方法也不适合大规模多线程并发的环境因为在这种场景下， 它按照处理器数目细分缓冲区会造成缓冲区命中率下降， 同时竞争的减少却不明显另外， 文献 没有讨论缓冲区的划分与缓冲区命中率的变化的关系 在缓冲区管理上应用批量处理技术这种批量处理技术可以归类为延迟同步技术，即刻返回逻辑操作结果这种批量处理技术可以分摊申请锁而带来的开销 可以工作在任何置换算法中， 并且在缓冲命中的时候消除竞争但是， 根据文献 的实验结果， 的优点在 算法族不能充分发挥， 并且提
46、高 算法类的吞吐率上效果不明显， 因为 不能消除缓冲区未命中的时候锁的竞争如果其中一个并发访问线程遇到缓冲区未命中， 需要申请加锁， 必须对阻塞操作进行排序在缓冲区命中的情况下， 算法也不需要申请加锁因此， 不能改善当前 的缓冲区管理策略大部分缓冲区并发控制问题的解决都是依赖个人开发者的经验知识关于缓冲区的并发控制还没有被密集地讨论的一个原因是大规模的多处理器还未普及， 而且目前的主要关注点仍在如何提高缓冲区命中率以减少然而， 为请求的磁盘页面钉住缓冲区页面的 操作却不受限于 尽管 操作导致页面置换时将脏页写出会发生磁盘， 但是现代 通过预先刷新脏页面和选择非脏页面作为置换页来减少此类这就意味
47、着如果内存空间足够且有大量的缓冲区池可用， 那么就可以最大程度地减少由 操作带来的页面置换次数在这种情况下 操作就变成受限于 的任务因此， 缓冲区管理中针对 上的可扩展性就成为多核处理时代的主要问题实际上， 和 操作是数据库中调用最频繁的基本操作高效的 和 操作尤其重要，因为它们频繁导致临界区上的竞争 数据库每访问一次缓冲区管理器模块， 临界区上的操作都需要获得互斥变量， 在多处理器环境下有可能出现“ 互斥变量抖动” 现象 此外， 对锁的大量访问请求有可能导致护卫现象， 它出现在当持有锁的线程由于某种中断例如缺页而被挂起的时候然后， 申请锁的其他线程就会排队， 不能继续执行即使锁在后面被释放，
48、 清空队列也需要花费一定的时间 和 通过使用细粒度的锁来减缓在缓冲池上的锁竞争问题它们采用称为“ 锁分段” 的传统方法来提高哈希表上的并发 等人 采用更激进的方法在多核环境下进行同步他们利用现有的非阻塞哈希表设计非阻塞的置换算法 因此， 缓冲区页面的查找和分配都不需要申请锁因而也就避免了旋转锁带来的问题 置换算法是 置换算法的变种因此它具有 置换算法的以下优点： （） 低开销和高并发；（） 由并发访问共享变量而引起竞争的概率很低； 这些良好的性质和性能已经被规范地证明和确定 文献 的作者在 的开源数据系统 上实现了 算法在实验中， 的扩展性可以达到 核， 消除了由 操作时需要加锁而引起的扩展性
49、差等问题 犘 狅 狊 狋 犵 狉 犲 犛 犙 犔 犕犆的缓冲区多核优化探索为了消除其他模块， 例如锁管理器、 恢复子系统等对查找数据库缓冲区的瓶颈带来的干扰， 我们选取了只读事务对系统进行测试通过大量的实验分析以及源码的阅读， 我们发现缓冲区管理器的扩展瓶颈集中在缓冲区空闲链表（ ） 以及哈希表管理 的数据页访问算法如图所示： 每当事务需要访问一个数据页， 首先在哈希表中查找若找到， 说明要访问的数据块已经在缓冲池中， 直接返回； 若没有找到， 则需要从缓冲池中寻找一个空闲页面来装入要访问的数据块系统在缓冲区空闲链表中查找是否存在空闲页面； 如果存在， 那么直接返回该空闲页面即可； 若不存在，
50、 则需要采用时钟算法为需要访问的数据块淘汰页面这个过程期朱阅岸等：多核处理器下事务型数据库性能优化技术综述 ： ： 图 访问数据页流程图中有两个需要串行化执行的点： （） 缓冲区空闲链表的访问； （） 将新的数据块插入到哈希表过程中哈希表空闲结点的获取中国人民大学 研究团队探索了以下优化：（） 缓冲区空闲链表的访问通过去除缓冲区空闲链表上的轻量级锁， 减少事务获取空闲页面的等待时间， 增大系统并发度竞争空闲数据页的事务需要获得旋转锁， 第一个获得旋转锁的事务会标记空闲数据页的引用计数器， 防止其他事务使用该页面因此去除缓冲区空闲链表上的轻量级锁不会导致出现一个空闲页被多个事务使用情况此外， 通
51、过检测缓冲区空闲链表是否由于并发而遭受破坏， 我们保证每次测试不会受到缓冲区空闲链表的干扰（） 时钟置换算法的修改每个事务随机挑选起始位置开始时钟置换算法， 事务之间并行执行各自的时钟算法（） 哈希表空闲节点的获取虽然 以后采用称为“ 锁分段” 的方法来提高哈希表上的并发， 但是哈希表空闲结点的获取还是只有一个入口，从而成为系统的瓶颈我们采取与“ 锁分段” 类似的做法， 将哈希表的空闲结点的入口分为多个， 分别管理以下的实验依次采取这些优化实验的硬件配置见 节图给出不同核数下系统的吞吐率数据库的连接数固定在 ， 测试时间为 我们利用数据仓库星型模型测试基准 （ ） 生成测试数据（ 扩展因子犛
52、犉） ， 只保留事实表 的整型字段事实表 的大小约为 ， 的缓冲区为 查询语句为在事实表上简单的 点查询 系统吞吐率的最大值出现在核左右随着核数的增加数据库系统不能再利用多余的硬件资源不管在 的基础上去除缓冲区空闲链表的轻量级锁以及并行化时钟置换算法还是调节哈希表分段锁的个数， 系统的扩展性基本都停留在核左右随着核数的增加， 系统的性能反而有所下降利用 （ 公司一个性能分析软件） 观测， 此时系统的瓶颈出现在哈希表的插入以及删除上接着， 我们将哈希表空闲结点的获取入口由一个扩展为多个此时 系统的扩展性可以达到 核从以上实验结果可以得到如下结论： 缓冲区的瓶颈出现在缓冲池空闲页面的管理和哈希表上
53、 研究团队未来的工作方向是开发面向多核的生产者消费者算法管理缓冲池以及适合多核多 平台的哈希表图不同的缓冲区管理策略下， 系统的扩展性不同于 的缓冲区研究， 中内存管理的研究较早前就关注多核环境下的优化问题 文献 利用页面染色的方法划分高速缓存以解决高速缓存争用的问题， 从而更好地管理 缓冲区页面的分配文献 认为对内存控制器的竞争对系统的性能造成很大影响，改善内存子系统性能需要设计公平的内存器文献 则设计了高速缓存竞争敏感的调度器以最小化资源竞争以上关于 的缓冲区在多核环境下的研究仅仅局限于 缓冲区层面算法上的修改而现实 系统的缓冲区管理大多是在操作系统的缓冲区基础上进行定制因此， 研究多核处
54、理器下 的缓冲区的优化需要考虑操作系统的缓冲区修改， 例如文献 我们认为 可以借鉴这些思想结合硬件特性优化其缓冲区的设计， 提出更好的缓冲区管理算法计算机学报 年多核下索引并发控制树 作为数据库管理系统中的默认索引，广泛用于数据库应用在事务处理方面作出过杰出贡献的 曾经说： “树是迄今为止在数据库和文件系统中最重要的存取路径数据结构”与其他索引相同，树的功能是将搜索关键字映射到其相关信息除了提供精确匹配查找，树也支持范围查询， 并且为基于排序的查询执行算法， 例如合并连接算法， 省略了显式的排序操作然而，树上的并发控制在多核扩展上表现为明显的瓶颈 树利用两种不同形式锁， 也就是闩与锁， 分别保
55、护的物理结构和逻辑内容闩与锁的区别如表所示由于树节点与数据呈一对多的关系， 对树节点加锁往往是粗粒度的， 会导致并发度降低此外， 闩锁对应的临界区也是阻碍多核扩展的一个因素表闩锁与锁的区别锁闩隔离内容用户事务线程保护内容数据库数据内存数据结构存在方式整个事务临界区模式排它锁、 共享锁、 意向锁等读、 写、 更新死锁死锁检测消除避免死锁死锁处理终止事务通过编码原则避免死锁存放位置锁管理器的哈希表被保护的数据结构 犅树物理结构的保护 树是一种放宽树结构限制的访问方法它将结点分裂划分成两个独立的阶段每一个结点都可以有一个高位保护值和指向其右邻居的指针从根到叶子节点的遍历中， 每到达一个结点就必须将搜
56、索值和该结点的高位保护值相比较如果高位保护值小于搜索值， 必须沿着该结点指向右邻居的指针继续查找分裂节点的第步是创建结点的高位保护值和右邻居结点； 第步是独立的步骤， 将高位保护值放置在父节点第个步骤可以作为其后从根结点到叶子节点遍历的附加操作， 应该尽早完成这个操作也有可能被系统重启或系统崩溃所推迟， 但是它们不会造成 树出现数据丢失和不一致性情况 树的优点是结点的分配和引进是一个局部操作， 只对溢出结点有影响， 因此并发度高； 缺点是搜索不够高效， 并且 树的一致性验证会变得更复杂在值频繁插入的情况下， 需要措施保证指向邻居结点的链表不会过长 树结点的移除也可以借鉴这个方法以提高并发度 第
57、步是创建指向邻居结点的指针第步在父节点中将指向删除结点的指针擦除第步合并结点 等人 通对 做了进一步改进， 将分裂操作限制在由合适的父结点指向的结点避免了频繁插入带来的长链表文献 提出避免闩锁的一种树 针对多核和 硬盘的新硬件平台而设计的 利用 树的原子分裂技术， 结点分裂由两个独立部分组成 树中状态的改变都是利用原子交换指令完成， 因此可以避免闩锁， 而且不会阻塞唯一使得 阻塞的情况就是缺页由于 消除闩锁的特性， 因此一些事务不可避免地会遇到竞争而导致更新页面状态失败此外， 中页面的概念是虚拟的， 任何对页面的更新都首先必须创建一个记录， 然后附加在虚拟页面上过长的记录链表会降低搜索的性能，
58、 需要额外的开销处理这些链表 是针对多核平台和类似 等非易失存储器而提出的另一 变种 设计者们的目标是： （） 设计最小化并发控制需求的数据结构；（） 方便数据节点往新的存储上迁移； （） 支持连续和复杂的自我检测功能 在处理更新操作时采用类似 树的方法， 每次只需对两个索引节点加闩锁， 以最大化并发操作 与 树的不同在于为了方便数据的迁移 的索引节点最终只有一个指向它的指针， 也就是消除了同一层节点之间的指针， 只保留指向它的父节点指针 采用对称保护码允许在从根到叶子节点的遍历过程中进行有效性验证设计上， 集合了 树 、 对称保护码以及写优化 的特点， 最大程度地避免它们的缺点 犅树逻辑内容
59、的保护锁将读事务与写事务隔离开为了保证一致性，事务持有读锁直到结束为了保证事务终止时能够撤销所有对数据库的修改， 事务总是持有写锁直到结束此外， 可串行化不仅要求对存在的数据加锁，也要求对不存在的数据加锁例如对于一个 犽查询， 第二执行的相同的 犽查询必须得到相同的结果， 而且任何影响结果集的插入操作都应该被阻止对树而言， 这通常由关键字范围封锁来实现 的 直接区分了锁与闩的区别（ 见表） ， 采用一个关键字值锁（ ， ） 覆盖一个区间和区间上界的关键对非单一索引而言， 作用在某个关键字上的意向锁对期朱阅岸等：多核处理器下事务型数据库性能优化技术综述具有相同值的所有行都有效然而将行 包含在锁
60、上的 设 计 却 不 用 区 分 单 一 和 非 单 一 索 引 描述树上的行级锁就是基于关键字值锁 的关键字范围锁 尝试将层次锁与多粒度锁应用在值和半开闭区间， 但是需要额外的锁模式， 范围插入模式， 以获得满意的并发度 将传统的层次锁更严格地应用在关键字和关键字的区间， 并且在插入和删除操作上使用了伪删除记录这种设计可以减少特例情况， 取得更高并发度最近也有研究将增量锁与树上的关键字范围锁结合起来以取得最大并发度 锁的设计不仅考虑保护数据库一致性与隔离性， 还需要考虑锁协议的简单性与最大化系统的并发度相关的研究者一直在努力设计简单的锁协议，同时最大化系统并发度然而， 锁的维护、 申请和释放
61、都会给系统造成不小的开销随着虚拟技术的发展使得在多 核处理 器 部 署 无 共 享 系 统 成 为 了 可能 无共享系统从物理上划分数据库， 一个极端的例子 它通过嵌入多个单线程的执行引擎各个执行引擎之间并行执行， 互不干扰， 单个执行引擎的事务串行执行从而避免并发控制研究展望现在， 数据库研究社区已经开始重视多核架构对数据库系统产生的影响 为了克服当前数据库系统共同的弱点， 也就是系统随着处理器个数或核数的增长其性能难以提升， 许多学者提出了不同的解决方案针对上述多核环境下数据库中的锁管理器、 缓冲区管理器、 日志以及索引遇到的问题总结起来， 解决方案可以分成两类： 分布式与共享在分布式架构
62、下， 将多核与多处理器当做分布式系统对待；而共享系统下， 则需要解决通信和资源竞争的问题分布式系统解决方案对分布式数据库的研究在 世纪 年代末 年代初就已经开展 早期分布式数据库系统的许多技术可以用于改善集中式数据库系统在多核平台下的扩展性 等人 开 发 的 系 统 将 多 个 数 据 库 实 例（ 或者 ） 部署在多核平台上运行这些数据库实例的核不相交主节点负责接收并分发只读查询请求， 同时执行更新请求然后主节点将更新结果按异步方式分发到卫星节点 将数据在多个节点和核上水平划分， 然后事务在每个核上以单线程的方式串行执行因此， 每个数据划分上都不需要同步访问类似传统分布式数据库， 这些系统需
63、要工作负载感知的数据划分策略以减少划分间的通信数据偏斜或者是数据访问与数据划分的模式不对应都会造成此类系统性能上的问题共享系统一个共享系统的例子是由 等人 开发的 在分析了现有数据存储系统的瓶颈之后， 他们通过优化锁、 闩锁和同步机制从而减少竞争得到一个多线程的、 可扩展的系统物理逻辑组合划分是介于分布式系统和共享系统之间的一个解决方案 ： 数据仍然是共享的， 但是利用一个多根 划分数据， 避免昂贵的对数据页加闩锁的操作 系统 将各个线程绑定到不相交的数据集， 根据事务访问的数据把事务划分成更小的动作序列其中， 每个线程都拥有各自的锁机制来控制对所属数据的访问， 减轻集中式锁管理带来的弊端此外
64、， 近年来涌现的一些优秀的内存数据库例如微软的 和 的 也极力优化其查询处理引擎以及主要模块的临界区以便能充分利用多核平台的优势总结在这篇综述中， 我们主要讨论新的 架构下的数据库系统优化技术以及中国人民大学在开源数据库 上提出的多核处理器优化技术现在， 多核处理器提供的更高的并行性对数据库系统带来的挑战是明显的数据库系统必须经过彻底的改进， 才能利用不断增长的硬件上下文和可用的资源， 从而进一步改善性能参考文献 ， （ ） ： ， ， （） ： ， ， ， ： ， ， ： ， ， ， ？ ， ， ： ， ， ， ， ， ： 计算机学报 年 ， ， ， ： ， ， ， ， ， ： ， ， ，
65、， ，（） ： ， ， ： ， ， ， ，（） ： ， ， ， ： ， ， ： ， ， ， ， ： ， ， ， ， ， ： ， ， ， ，（） ： ， ， ， ： ， ， （） ： ， ： ： ， ， ， ， ， ， （） ： ， ， ， ， ， ， ： ， ， ， ， ， ： ， ， ： ， ， ， ， ： ， ， ， ： ， ， ， ： ， ， ，（） ： ， ： ， ， ： ， ， ， ， ， ： ： ， ， ： ， ， ， （） ： ， ： ， ， ： ， ， ， ， ： ， ， ： ， ， ： （ ） ， ， ： ， ， ， ： ， ， ： ， ， ， ， ， （） ： 期朱阅岸等：
66、多核处理器下事务型数据库性能优化技术综述 ， ， ， ， ， ： ， ， ， ， （） ： ， ，（） ： ， ， ： ， ， ： ， ， ， ： 犾 ， ， ： ， ， ， ， ： ， ， ， ： ， ， ， ： ， ： ， ， ： ， ， ， ， ： ， ， ， ， （） ： ， ， ， ， ： ， ，（） ： ， ， ，（） ： ： ， ， ： ， ， ：（） ： ， ， ， ： ， ， ， ， （） ： ， ， ： ， ， ： ， ， ， ， （） ： ， ， ： ： ， ， ： ， ， ， ： ， ， ， ： ， ： ， ， （） ： ， ， ， （ ） ， ， ： ， ， ， ：
67、？ ， ， ： ， ， ， ： ， ， ： ， ， ， ， ，（） ： ， ， ， ： ， ， ，（） ： ， ， ， ， ？ ， ， ： 计算机学报 年 ， ， ， ， ，（） ： ， ， ， ： ， ，（ ） ： ， ： ， ， ： ， ， ， ： 犣 犎 犝犢 狌 犲 犃 狀， ， 犣 犎 犗 犝犡 狌 犪 狀， ， 犣 犎 犃 犖 犌犢 犪 狀 犛 狅 狀 犵， ， ， 犣 犎 犗 犝 犕 犻 狀 犵， ， 犖 犐 犝犑 犻 犪， ， 犠 犃 犖 犌犛 犺 犪 狀， ， ， ， 犅 犪 犮 犽 犵 狉 狅 狌 狀 犱 ， ， ， ， ， ， ， ， ， ， ， （ ， ） ， （ ， ） ， （ ）期朱阅岸等：多核处理器下事务型数据库性能优化技术综述
