（计算机应用技术专业论文）数据库索引并发控制协议实现与改进.pdf

浙江大学硕士学位论文 摘要 摘要 关系数据库在现实生活中的使用已经起到了越来越重要的作用，人们每天都 直接或间接地与数据库系统打交道。而为了满足数据库使用对性能、正确性的需 要，对数据库的并行性研究显得尤为重要。在使用数据库进行数据操作的过程中， 索引起到了一个很好的桥梁作用，它使得对数据的查询更为快捷，而在多用户并 发访问的场景之下，索引自然也就成了数据库系统数据访问的瓶颈所在。如何提 高索引并发访问的并发度并保证正确性正是本文讨论的主旨。 本文在结合数据库对索引并发实现的一般做法的基础上，针对索引的并发加 锁协议以及具体实现提出了几点改进和优化，实现了一套索引系统。在本文中涉 及的改进主要有如下几点： 1 ) 对数据项访问加锁协议进行了改进，增加了锁模式和优化了具体加锁的 模式，使得索引的并发访问能力得到了提高。 2 ) 对索引的结构修改操作进行了优化，使得结构修改具备了更高的可串行 性。 3 ) 对索引三个主要操作做了具体的优化，使得索引的访问在性能和并发性 上有所提高。 同时本文在介绍协议和进行优化的过程中，也进行了一些论证，阐述了优化 改进的可行性。最后本文还论述了在本文提出的协议和改进的基础上，索引在恢 复和死锁方面都是能保证正确性的。 关键词数据库，索引，并发控制，加锁，s m o ，恢复 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t r e l a t i o nd a t a b a s eb e c o m e sm o r ea n dm o r ei m p o r t a n ti no u rd a i l yl i f e e v e r ym a y c o n t a c tw i t hd a t a b a s ee v e r y d a y t of u l f i l lt h en e e do f d a t a b a s e sg o o dp e r f o r m a n c ea n d o o l t e c u i e s s ，i t si m p o r t a n tt os t u d yt h ec o n c u r r e n c yc o n t r o lo fd a t a b a s e i n d e xo f d a t a b a s em a k e sd a t a b a s ep e r f o r mb e t t e ri ns e a r c ht h ed a t aw h i c hu s e r sq u e r y0 1 1 s oi n m u l t i - u s c r $ e n v i r o n m e n t , t h ep e r f o r m a n c eo fi n d e xi st h eb e t t l e n e e ko ft h ed a t a b a s e q u e r y t t l i sp a p e rf o c u so nh o wt og e tab e t t e rp e r f o r m a n c eo fi n d e x sc o n c u r r e n c y c o n t r o la c c e s s f i r s tw es h o ws o m eo t h e r s m e t h o d s a n dt h e nw ed i s c b s so u rm e t h o dw h i c hh a sa i m p r o v e m e n ti ni n d e xc o n c u r r e n c yc o n t r o ll o c k i n gp r o t o c o la n dt h ei m p l e m e n to f i n d e x i nt h i sp a p e r , w et a l ka b o u ti m p r o v e m e n t sa sf o l l o w ： 曲w eb r i n gf o r w a r dal o c k i n gp r o t o c o lo fi n d e xa c c e 鼹，w h i c hh a sab e t t e r p e r f o r n l a n c ei ni n d e xc o n c u r r e n c yc o n t r 0 1 们w ei m p r o v et h ei n d e xs t r u c t u r em o d i f yp r o c e s s ，a n di t sm u c hm o r e c o n v e n i e n tt oi m p l e m e n tm o d i f y 西w ea l s oi m p r o v et h es e a r c h , i n s e r t , d e l e t eo p e r a t i o no f i n d e xa c c e s s w ea l s op r o v et h ec o r r e c t n e s so fo u ri m p r o v e m e n t a t1 a s tw et a l ka b o u tt h e r e c o v e t ya n dd e a d l o c ko f o u ri n d e xi m p l e m e n t a t i o n k e y w o r d sd a t a b a s e ，i n d e x ，c o n c u r r e n c yc o n t r o l ，l o c k ，s m o ，r e c o v e r y 浙江大学硕士学位论文 图目录 图目录 图3 一l 本文使用的索引结构一1 2 图3 - 2 键范围锁示例索引2 0 图3 - 3l a t c h 之间的死锁2 3 图3 - 4 查询操作示例索引2 6 图3 - 5 唯一查询示例索引2 7 图3 - 6 插入操作示例索引2 8 图3 7 插入操作中下一码加锁的使用2 9 图3 - 8 索引删除示例索引3 0 图3 - 9 索引改进示例一3 3 图3 一l o 索引改进示例二3 4 图3 - 1 1 改进二使用场景示例索引3 5 图3 1 2s m o _ b i t 使用示例 图4 - 1 查询操作对l a t c h 的优化示例 图4 2 索引范围查询流程图 图4 3 索引唯一查询流程图 图4 - 4 插入中存在的问题。 图4 - 5 改进后索引的插入状态 4 2 4 3 图4 - 6 索引插入操作流程图 图4 7 索引插入引起的s m o 流程图 图4 8 删除操作的优化 图4 9 索引删除操作流程图 4 7 4 8 5 1 5 2 图4 1 0 索引删除引起的s m o 流程图5 3 图5 1 插入导致的恢复问题5 5 图5 - 2 索引查询操作测试结果对比5 9 图5 - 3 索引插入操作测试结果对比6 0 图5 4 索引删除操作测试结果对比6 0 浙江大学硕士学位论文表目录 表目录 表2 - 1 隔离级别允许的操作9 表3 - 1l a t c h 的包容矩阵 表3 - 2 不同隔离级别对应的加锁方式 表3 - 3 键范围锁示例表 表3 _ 4 加锁模式包容矩阵 表3 - 5 改进后的锁包容矩阵 3 2 3 6 表5 1 索引扫描优化对比一5 9 v 浙江大学硕士学位论文 第1 章绪论 1 1 数据库系统的概念 第1 章绪论 1 1 1 关系数据库的产生 从人类社会发展以来，人类无时无刻不面对着各种各样繁多的数据。银行需 要管理客户的信息、存款；学校需要管理学生的课程和成绩等等。数据管理技术 随着应用进步而迅速发展，应用发展始终是数据管理技术进步的动力。在计算机 产生以后，人们对数据的管理是更加的方便快捷了。在五十年代后期普遍使用文 件系统进行存储。到了六十年代后期m m 开发了第一个数据库管理系统i m s ，数 据库管理系统【l 】( d a t a b a s em a n a g e m e n ts y s t e m ) 是由一个互相关联的数据的集合 和一组用以访问这些数据的程序组成。这个数据集合通常成为数据库 1 】，其中包 含了关于某个企业的信息。d b m s 的基本目标是要提供一个可以方便、有效地存 取数据库信息的环境。 数据库结构的基础是数据模型【l 】：一个用于描述数据，数据问关系、数据语 义和数据约束的概念工具的集合。七十年代初，e ec o d d 提出了关系数据库模 型的概念，以及关系代数和关系演算。在整个七十年代，关系数据库从理论到实 践上面都取得了辉煌的成果。在理论上确立了完整的关系理论，数据依赖理论以 及关系数据库的设计理论等等；在实践上，开发了许多著名的关系数据库系统， 如：s y s t e mr 、i n g r e s 、o r a c l e 等。 1 1 2 关系数据库的发展与使用 关系数据库系统管理的数据，其结构较为简单，数据本身以二进制表形式进 行存储；数据库的表之间的数据联系通过一个表的主键【1 】与另一个表的外键【1 l 的 连接来体现。关系数据库系统提供了强大的查询功能，提供了十分方便、易用的 非过程化的查询语言( 1 9 8 6 年美国国家标准协会( a n s i ) 通过了关系数据库查询语 言s q l 的文本标准 ，从而获得了极为广泛的应用，大大促进了商务数据处理应 用的飞速发展。现在已有大量的商业数据库系统投入我们日常的使用，主要有： 浙江大学硕士学位论文 第1 章绪论 i b m 的d b 2 、o r a c l e 、m i c r o s o f ts q ls e r v e r 、i n f o r m i x 、s y b a s e 等。数据库的使 用在所有企业中都有所增长，特别是2 0 世纪9 0 年代末的互联网革命急剧地增加 了用户对数据的直接访问。尽管应用的用户界面隐藏了访问数据库的细节，然而 今天访问数据库已经成了几乎每一个人生活中的基本部分。 1 2 数据库系统结构 数据库系统【l 化分为不同的模块，每个模块完成整个系统的一个功能。数据 库系统的功能大致可以分为存储管理器和查询处理器组件。 存储管理器是在数据库中存储的底层数据与应用程序及向系统提交的查询之 间提供接口的程序模块。存储管理器应负责与文件管理器进行交互。原始数据通 过文件系统存储在磁盘上，文件系统通常由传统的操作系统提供。存储管理器将 不同的数据操纵语言语句翻译为底层文件系统命令。因此，存储管理器负责数据 库中数据的存储、检索和更新。 存储管理组件主要包括： 权限及完整性管理器 事务管理器 文件管理器 缓冲区管理器 索引 数据文件和数据字典 1 3 数据库系统中的索引 数据库中的数据是以表的结构存储在数据库中。在使用数据库的过程当中， 最经常的是需要对数据进行查询。然而许多查询只涉及某些表中的少量记录，例 如有一张全校学生信息的表，我们需要获得2 0 0 7 年入学的新生名单，那么假设 系统的做法是读取所有的学生信息记录然后返回入学年份为2 0 0 7 的学生记录， 这样的操作方式是低效的。理想情况下，系统应能直接定位这些记录。索引的引 入正是要解决这么一个问题。 现在常用的索引结构主要有b + 树索引、位图索引等【l 】1 2 。当今主流的三大数 据库o r a c l e 、d b 2 、s q ls e r v e r 都支持b + 树索引，因此本文所讨论的索引主要 2 浙江大学硕士学位论文第1 章绪论 就是b + 树索引。 b + 树索引结构是使用最广泛的在数据插入和删除的情况下仍能保持其执行 效率的几种索引结构之一。b + 树索引采用平衡树结构，其中树根到树叶的每条 路径的长度相同。对于b + 树来说，这是一个必需的性质。正是b + 树的这个平 衡属性保证了b + 树索引有良好的查找、插入和修改的性能。因此b + 树索引也 被最广泛的采用，它为数据库的使用效率提供了一个质的飞跃。 1 4 本文讨论的内容 前面已经提到了当今越来越多的用户需要对数据库系统进行各种访问，而访 问的同时都不可避免的需要使用索引，来提高数据库获取和更新的效率。因此索 引结构设计的好坏直接影响到数据库性能的高低。特别是在大量访问的时候，如 何通过并发控制协议来保证在提高性能的同时也保证数据的正确性。本文所要讨 论的重点就是索引的并发控制协议的实现以及改进。 1 5 本章小结 本章首先介绍了关系数据库的发展以及现状，关系数据库在当今社会生活的 使用率是频繁的，使用量是巨大的。人们每天的生活当中都会直接或者间接的接 触到关系数据库。因此对关系数据库的研究是有意义而且必要的。 接着本章介绍了关系数据库的系统结构，并详细介绍了结构中索引的引入和 索引结构，引出了b + 树索引的概念。b + 树索引将是本文讨论的重点，作为数 据库系统结构中不可或缺的一部分，如何实现好索引的并发控制是十分重要的， 以下章节将围绕着b + 树索引的并发控制的实现和改进具体展开。 浙江大学硕士学位论文第2 章技术背景 第2 章技术背景 2 1 并发控制概述 从数据库用户的观点看，数据库中一些操作的集合通常被认为是一个独立的 单元。而事务( t r a n s a c t i o n ) 是构成单一逻辑工作单元的操作集合。不论有无故 障，数据库系统必须保证事务的正确执行执行整个事务或者属于该事务的操 作一个也不执行。 2 1 1 事务的概念 事务是访问并可能更新各种数据项的一个程序执行单元。事务由事务开始与 事务结束之间执行的全体操作组成。为了保证数据完整性，事务必须保证以下的 性质： 原子性：事务的所有操作在数据库中要么全部正确反映出来要么全部不 反映。 一致性：事务隔离执行时( 即在没有其它事务并发执行的情况下) 保持 数据库的一致性。 隔离性：尽管多个事务可以并发执行，但系统保证，对于任何一对事务 t i 和t j ，在t i 看来，t j 或者在t i 开始之前已经停止执行，或者在t i 完 成之后开始执行。这样，每个事务都感觉不到系统中有其它事务在并发 地执行。 持久性：一个事务成功完成后，它对数据库的改变必须是永久的，即使 系统出现故障也是如此。 在不出现故障的情况下，所有的事务能成功完成其执行，这样的事务称为已 提交事务。完成更新的已提交事务时数据库进入一个新的一致状态。一旦事务提 交，我们不能通过中止它来撤销其造成的影响。而当事务不能正常完成的时候， 它被称为中止事务，中止事务必须对数据库的状态不造成影响。所以中止事务所 做的任何改变必须撤销。这个过程称为事务的回滚。事务的回滚也是让数据库进 入一个一致状态。 对于一系列事务操作的调度，假设有某个调度s ，它和一个这些事务的串行 4 浙江大学硕士学位论文第2 章技术背景 调度s 是冲突等价的，也就是说调度s 可以经过一系列指令交换转换成s ，那么 我们称调度s 是冲突可串行化的。能满足冲突可串行化的事务调度可以很好的保 证事务的隔离性。 2 1 2 数据库的并发控制 前面我们知道了事务最基本的特性之一是隔离性。当数据库中有多个事务并 发执行时，隔离性不一定能保证。而为了保持事务的隔离性，系统必须对并发事 务之间的相互作用加以控制，这是通过称为并发控制机制的一系列机制中的一种 来实现的。 2 1 2 1 并发问题 如果没有通过并发控制机制来保证多个用户正确的访问数据库，则当他们的 事务同时使用相同的数据时可能会发生问题。并发问题【l g j 包括： 丢失更新：当两个或多个事务选择同一行，然后基于最初选定的值更新 该行时，会发生丢失更新问题。每个事务都不知道其它事务的存在。最 后的更新将重写由其它事务所做的更新，这将导致数据丢失。例如，两 个编辑人员制作了同一文档的电子复本。每个编辑人员独立地更改其复 本，然后保存更改后的复本，这样就覆盖了原始文档。最后保存其更改 复本的编辑人员覆盖了第一个编辑人员所做的更改。如果在第一个编辑 人员完成之后第二个编辑人员才能进行更改，则可以避免该问题。 未确认的相关性( 脏读) ：当第二个事务选择其它事务正在更新的行时， 会发生未确认的相关性问题。第二个事务正在读取的数据还没有确认并 且可能由更新此行的事务所更改。例如，一个编辑人员正在更改电子文 档。在更改过程中，另一个编辑人员复制了该文档( 该复本包含到目前 为止所做的全部更改) 并将其分发给预期的用户。此后，第一个编辑人 员认为目前所做的更改是错误的，于是删除了所做的编辑并保存了文档。 分发给用户的文档包含不再存在的编辑内容，并且这些编辑内容应认为 从未存在过。如果在第一个编辑人员确定最终更改前任何人都不能读取 更改的文档，则可以避免该问题。 不一致的分析( 非重复读) ：当第二个事务多次访问同一行而且每次读取 浙江大学硕十学位论文第2 章技术背景 不同的数据时，会发生不一致的分析问题。不一致的分析与未确认的相 关性类似，因为其它事务也是正在更改第二个事务正在读取的数据。然 而，在不一致的分析中，第二个事务读取的数据是由已进行了更改的事 务提交的。而且，不一致的分析涉及多次( 两次或更多) 读取同一行， 而且每次信息都由其它事务更改；因而该行被非重复读取。例如，一个 编辑人员两次读取同一文档，但在两次读取之间，作者重写了该文档。 当编辑人员第二次读取文档时，文档已更改。原始读取不可重复。如果 只有在作者全部完成编写后编辑人员才可以读取文档，则可以避免该问 题。 幻象读：当对某行执行插入或删除操作，而该行属于某个事务正在读取 的行的范围时，会发生幻象读问题。事务第一次读的行范围显示出其中 一行已不复存在于第二次读或后续读中，因为该行己被其它事务删除。 同样，由于其它事务的插入操作，事务的第二次或后续读显示有一行已 不存在于原始读中。例如，一个编辑人员更改作者提交的文档，但当生 产部门将其更改内容合并到该文档的主复本时，发现作者已将未编辑的 新材料添加到该文档中。如果在编辑人员和生产部门完成对原始文档的 处理之前，任何人都不能将新材料添加到文档中，则可以避免该问题。 2 1 2 2 加锁 确保可串行化的方法之一是要求对数据项的访问以互斥的方式进行；也就是 说，当一个事务访问某个数据项时，其它任何事务都不能修改该数据项。实现该 需求最常用的方法是只允许事务访问当前该事务持有锁的数据项。 加锁【i 】1 2 是一种保证事务访问权限的方法，最基本的锁有共享锁( s 锁) 和排 他锁( x 锁) 。共享锁保证的是如果事务t l 获得了数据项r 上的s 锁，那么t 1 能 读但不能写( 修改) r ；而排他锁保证的是如果事务t i 获得了数据项r 上的x 锁， 那么t 1 即可读又可写r 。要实现加锁机制，我们要求每个事务都要根据自己将对 数据项r 进行的操作类型去申请相关的锁，只有在数据库的并发控制管理器 在很多数据库系统中都由锁表模块负责处理授予了事务请求的锁之后，事务 才能对数据项进行相应的操作。 除了以上讲的两种对数据项所使用的锁之外，还有其它模式的针对数据项或 者针对数据表等结构使用的锁。例如在某些情况下我们需要把多个数据项聚为一 6 浙江大学硕士学位论文第2 章技术背景 组，将它们作为一个同步单元，因为这样效果可能吏好，可以避免过于频繁的对 每一个数据项加锁解锁，也可以一定程度避免死锁的产生。例如我们需要的对一 张表进行大量的删除操作，假设该表有1 万行数据，经过估算，我们删除的数据 量占了整个表的8 0 ，那么我们完全没有必要对这其中的8 0 0 0 行数据一一加锁， 而只要简单的对这张表加把锁，保证别的事务不会同时对表进行操作，那么就 可以很好的降低对锁表加锁解锁的请求，降低锁表的性能开销。所以我们需要的 是一种允许系统定义多级粒度的机制，允许用户( 事务) 对不同层次的数据进行 不同的加锁。在这种层次化加锁底下，引入了意向锁的概念，即如果一个结点上 加了意向锁，则意味着要在该结点的更低层次的数据上加锁。目前最常用的意向 锁有、i s 、s i x 锁三种，i s 和锁分别对应s 和x 锁，表示的是要对加了i s ( ) 意向锁的结点的子结点加s ( x ) 锁。而s i x 是共享排他型意向锁，表示 对某个结点加了共享锁，同时又要对它的子结点的数据显式的加排他锁。在实际 的应用中，意向锁并不一定是使用在某个高层次的结点( 例如：表、数据页面) 上，而是可以用来在数据项上进行加锁，这个做法在索引的并发控制当中得到了 体现。 2 1 2 3 锁的包容性 各种锁模式之问存在着包容与排斥的关系，正是这一约定好的关系保证了加 锁策略可以很好的保证数据库系统的并发控制。正如前面所描述的，共享锁( s 锁) 与共享锁是包容的，允许多个相同或不同的事务对同一个数据加s 锁。而x 锁之间则是排斥的，即同时只能有一个事务持有某个数据项的x 锁，这样保证了 同时只有一个事务可以对数据项进行修改。当然，s 锁与x 锁也是互斥的，因为 读取数据的事务与修改数据的事务执行的顺序不同，可能导致读取数据最终的结 果不同，这正是并发控制协议要避免的。意向锁之间、意向锁和非意向锁之间也 存在互斥关系，这样使得非意向锁在某些情况下如前面所描述的删除表中数 据的问题可以代替意向锁提高性能。 2 1 2 4 死锁 在加锁协议的使用当中，很容易出现的一个现象就是死锁【1 】o 如果存在一个 事务集，该集合中的每个事务在等待该集合中的另一个事务，那么我们说系统处 于死锁状态。更确切地说，存在一个等待事务集 t o ，t i ，t 札) ，其中t o 正在 7 浙江大学硕士学位论文第2 章技术背景 等待被t l 锁住的数据项，t l 正在等待t 2 锁住的数据项，t n 1 在等待t n 锁住 的数据项，而t n 在等待t 1 锁住的数据项。这种情况下，没有一个事务能取得进 展。发生死锁后，系统唯一的补救措施就是采取激烈的动作，如回滚某些陷于死 锁的事务。事务有可能只部分回滚，即事务回滚到得到锁的那一点之前，而释放 该锁就可以解决死锁。有些情况下我们是允许死锁的发生的，那样只有通过回滚 事务来解决死锁。然而在某些情况下死锁是必须要避免的，例如后面我们将详细 介绍的索引的并发控制当中，就有一种加锁机制是不允许死锁的，那样就要求并 发控制协议的实现要能够保证没有死锁产生。 2 1 2 5s o l 中的弱一致性级别 s q l 标准也允许一个事务这样规定：它可以以一种与其它事务不可串行化的 方式执行。例如，一个事务可能在未提交级别上操作，这里允许事务读取甚至还 未提交的记录。s q l 为那些不要求精确结果的长事务提供了这种特征。例如，对 于查询优化中的统计信息，近似信息就足够了。如果这些事务要在可串行化的方 式下执行，它们就会干涉其它事务，造成其它事务执行的延迟。 事务准备接受不一致数据的级别称为隔离级别【1 】。隔离级别是一个事务必须 与其它事务进行隔离的程度。较低的隔离级别可以增加并发，但代价是降低数据 的正确性。相反，较高的隔离级别可以确保数据的正确性，但可能对并发产生负 面影响。数据库用户要求的隔离级别确定了相关事务使用的锁定行为。在s q l 标准规定的隔离级别如下： 可串行化是默认级别。 可重复读只允许读取已提交记录，而且在一个事务两次读取一条记录期 间，其它事务不得更新该记录。但该事务不要求与其它事务可串行化。 例如，当一个事务在查找满足某些条件的记录时，它可能找到一些由一 个已提交事务插入的记录，但可能找不到其它记录。 已提交读只允许读取已提交的记录，但不要求可重复读。例如，在事务 两次读取一条记录期间，该记录可能以被另一个已提交事务更新了。 未提交读允许读取为提交记录。这是最低的一致性级别。 表2 - 1 结合了前面讨论的并发问题，列出了四种隔离级别所允许不同类型的 行为： 浙江大学硕士学位论文第2 章技术背景 表2 - l 隔离级别允许的操作 薅囊匦”= 冀遴篓= = = ：至黧熬熙缀豁= 二二 深麟：。一霪是 l 已_ ：| i 跤谱霪否 溪否 纛麓否 是 是 甭 否 是 孽 “一 是 一是 ! ”一 ” 一 否 事务必须运行于可重复读或更高的隔离级别以防止丢失更新。当两个事务检 索相同的行，然后基于原检索的值对行进行更新时，会发生丢失更新。如果两个 事务使用一个u p d a t e 语句更新行，并且不基于以前检索的值进行更新，则在 已提交读隔离级别不会发生丢失更新。 在实际的应用中，大部分数据库系统都支持这四种隔离级别，但是为了提高 并发性，都把己提交读作为默认的隔离级别，这样也减少了数据库各方面的开销。 可串行化作为最高隔离级别，所有的并发控制协议都要把它作为首要考虑的部 分，因为同时运行的不同事务可能隔离级别不一样，但是一旦有可串行化级别的 事务运行，并发控制协议必须保证该事务得到结果的正确性。 2 1 2 6 其它并发控制协议 除了采用加锁机制来实现并发控制，当前使用较多的还有多版本并发控制协 议。三大主流数据库当中，o r a c l e 既支持加锁协议也支持多版本协议。而d b 2 和 s q ls e r v e r 则只使用加锁协议。 2 2 索引并发控制研究现状 由于索引的频繁访问，它们将成为封锁竞争的集中点，导致并发度低。幸运 的是，索引不必像其它数据库结构那样处理。对事务而言，在一个索引上查找两 次，并且期间发现索引结构发生了变化，这是完全可以接受的，只要索引查找返 回正确的元组集。因此，只要维护索引的准确性，对索引进行非可串行化存取是 可接受的。 索引的访问可以分为两个步骤，首先是确定要操作的记录所在的索引页面， 其次是在该页面内对操作的记录进行操作。对于第一个阶段，目前使用的都是类 9 浙江大学硕士学位论文第2 章技术背景 似于蟹行协议的技术：当搜索一条记录时，首先对根结点加共享模式锁。然后向 下搜索，继续在子结点上获得共享锁，以便向更深层搜索，在子结点得到锁之后， 要释放父结点的锁。这一过程重复到找到目标叶结点。对于插入和删除记录，首 先还是采取前面所说的方法找到叶结点，之后对叶结点加排他锁，然后执行插入 或者删除。而如果某个结点需要进行分裂和合并的时候，首先用排他锁封锁父结 点。在完成操作之后，释放该结点和兄弟结点上的锁。如果父结点需要分裂合并， 那么以同样的方式往上分裂合并。否则父结点锁被释放。 定位到具体叶结点后，就需要对要操作的记录进行加锁以保证串行化。加锁 的对象主要分为两种，一种是对索引记录在其所在表中的一个特殊标识加锁；另 一种是对该记录在当前索引中对应的一个键值加锁i ，j ，称为k v i k e yv a l u e l o c k i n g 。这两种加锁方式均被采用并且有各自的优缺点，对特殊标识加锁保证了 当同一张表使用多个索引，加锁动作也只需要一次，但是这样却牺牲了并发性； 而k v l 方法在每次加锁的时候很可能需要对不同的键值加锁，而且也要对表中 的特殊标识加锁，但是它的优点就是提高了并发度。不管是哪一种加锁方式，加 锁的策略都是类似的，在可串行化隔离级别下，对于查询操作，要保证查询的记 录不被删除，两次查询之间需要保证有相同的结果。对于插入操作要保证不会被 插入到某一个别的事务的查询范围当中，造成幻象。对于删除操作也要保证不会 删除其它事务查询范围内的记录，也不会删除会导致幻象的记录。要防止幻象的 产生，当前的做法普遍采取了下一码封锁技术。这种技术中，每一个索引查找不 仅封锁查找范围内的多条记录，而且封锁下一条记录：并且，每一个插入必须不 仅封锁要被插入的值，而且包括下一条记录的。同样的做法在删除时也必须使用。 本文所论述的并发控制协议也是基于下一码封锁技术的。 为了支持索引的下一码加锁以及让索引有更好的并发访问能力，各种数据库 系统都引入了各种丰富的锁模式来对索引中的记录加锁，通过更多的锁模式，增 强了索引的并发性。 2 3 本文所要做的改进 前面论述了当前数据库系统对索引访问时使用的并发控制协议概况，由于索 引访问频率很高，其并发控制的好坏将直接影响索引使用的性能，进一步影响数 据库使用的性能。所以在索引的并发控制协议上进行研究改进，具有重大的现实 意义。 1 0 浙江大学硕士学位论文第2 章技术背景 在前面介绍的索引并发控制协议当中，主要分两部分介绍，一个是结点定位， 另一个是操作加锁。在实际的使用比较当中，我们发现在索引的访问当中，结点 的定位开销占的比重相当的大。因为结点的定位需要遍历多个父亲结点，而这样 的遍历都需要对父亲节点进行加锁，过多的加锁直接会导致访问的并行性降低。 同时也可能需要多次从磁盘上读取相关的页面。可见减少和优化叶结点的定位动 作是非常重要的。 其次加锁的协议也直接导致索引访问并行性的高低。由于使用了下一码加锁 协议，那么某一个操作所加的锁很可能由于多加了某种锁而对其它操作产生了影 响导致其它事务的等待。又或者由于某条记录加了某种锁导致一些可能可以进行 的操作不能进行了。因此设计一套好的加锁协议对于提高索引的并发访问也是非 常重要的。 索引有自身比较特殊的分裂和合并操作，这一操作是非常需要注意的，因为 它必须有很好的并发控制协议来保证操作的正确进行，否则有可能导致访问索引 的事务在回滚的时候发生各种错误。 本文主要从以上提出的三个方面着手，结合其它的各个方面，在提出一套完 整的索引并发控制协议的同时针对索引的并发瓶颈进行改进，并且分析最终协议 的正确性及改进的效果。 2 4 本章小结 本章首先介绍了数据库系统并发控制的概念。由于数据库中是以一个个操作 集合的方式来对数据进行访问的，由此产生了事务的概念。在数据库的使用中， 同一时刻经常存在着大量不同的事务进行同时访问，有必要制定一套协议规则保 证事务访问的顺序以及正确性，否则事务的访问就会的到错误的结果。这也就是 并发控制协议之所以重要的原因。目前采用的比较广泛的一个并发控制方式就是 采用加锁的方式。本章第一节具体介绍了加锁的概念、锁的包容性以及死锁的问 题。之后讨论了数据库中的四种隔离级别，不同的隔离级别对应不同的加锁策略。 本章第二节简单介绍了当前数据库索引的并发控制协议。该协议主要分两部 分组成，一个是定位叶结点的过程，一个是对记录加锁的过程。当然还有其它更 多的细节，留待后面章节中讨论。 最后介绍了本文要实现的并发控制协议将要在哪几个方面进行主要的研究 与改进。 浙江大学硕士学位论文第4 章索引并发控制协议 第3 章索引并发控制协议 3 1 本文中索引相关概念定义 3 1 1 索引结构定义 3 1 1 1 索引树结构 本文中所使用的是b + 树索引，它的结构和传统定义的b + 树略有不同，主 要表现在对于结点中的每一个项，它有唯一一个子结点，子结点中各项的键值总 是不大于该项的键值。如图3 1 所示： 图3 - 1 本文使用的索引结构 可以看到，在b + 树中，每一个非叶结点，都包含了若干个项和相同数量的 指向对应项的子结点的指针。而子结点的最大值不能超过父结点中指向该子节点 的项的值，唯一的一个例外就是最后一个叶结点可以包含大于它的父结点对应项 的值的项。同时叶结点间以双向指针链接在一起。 从图中还可以看出，并不是每个结点都要求其包含的项数要超过该结点所能 包含项数的1 2 ，例如第一个叶结点就只包含了一个项，而第三个叶结点包含了 三个项。这是因为，在我们的实现当中，项的删除并不会立即判断是否需要合并 结点或者调整相邻结点的内容。因为合并与调整操作可能需要涉及多个结点，这 样就要对多个结点进行加锁，从而影响了并发度。因此涉及结点问的变动的操作 浙江大学硕士学位论文第4 章索引并发控制协议 应该尽可能的减少，或者推迟到某个程度才执行。由于结点的合并和调整操作不 被立即执行，所以可能在很长的时间段里面，会出现一个页面只有很少的项，甚 至没有项的情况。这种做法虽然浪费了一定的空间，但是在并发上得到了提高。 在进一步介绍索引结构之前先明确一个行号的概念。对于任何的一条记录， 它最终是保存在某个数据文件当中的。根据记录在数据文件中的存放位置，可以 给每条记录关联一个在数据库中唯一的编号，用以区别其它的任何一条记录，同 时这个编号也是数据并发访问加锁的基础，并发控制协议当中加锁的对象就包括 这个唯一编号，该编号一般由数据文件的文件号，数据页面的页面号和数据项在 页面中的项号共同构成，保证了其唯一性，因为该编号是每一行记录所特有的， 我们把它称为行号( r o w l d ) ，简称为r i d 。 3 1 1 2 索引结点定义 下面介绍一下索引结点结构当中具体保存的信息在树中我们称为结点， 在实际操作过程中，我们将把结点称为页面，这两种名称表示是一样的。索引节 点根据b + 树的性质，有叶结点和非叶结点之分。它们之间主要存在两大差别： 首先同一层的非叶结点之间不存在任何链接关系，而位于底层的叶结点之间存在 着双向链接关系。其次对于保存在结点中的项，非叶结点和叶结点共同保存了数 据项的信息，但是非叶结点除了保存具体数据的值，以及r i d 之外，还需要保存 该数据项对应的叶结点的页面号p a g e l d ，而叶结点就不需要保存这一项信息。除 了以上两点区别，非叶结点和叶结点结构上是相同的，它们都有一个共同的页面 头部信息，里面保存了页面相关状态的信息，具体介绍如下： 页面表示信息( p a g e i n f o ) ：表示该页面是根结点、不是根结点的非叶结点、 叶结点或者既是根结点又是叶结点四种状态。根据页面代表的结点的不 同，来决定对该页面的操作采取什么样的方式进行。 页面状态信息( s m ob ) ：表示该页面是否处在分裂、合并状态当中， 因为对于处于该状态的页面，我们对它的操作都需要按照并发控制协议 来等待，直到该页面不处于分裂、合并状态为止，才可以正常的访问操 作。 页面的日志记录号( p a g e l s n ) ：该值变化表示了页面是否被修改过。我 们都知道l s n 表示的是每条日志的顺序号。对于对页面进行的修改操作， 我们把该修改操作的l s n 记录下来，并保存在页面当中。每次访问页面 浙江大学硕士学位论文第4 章索引并发拧制协议 的时候也把页面的l s n 记录下来，这样当连续两次访问同一个页面的时 候，我们就可以通过页面当前p a g e l s n 的值和之前保存的p a g e l s n 的值 进行比较，如果两个值相同，说明页面没有被修改，那么可以做各种优 化；否则说明页面被修改过了。 3 1 2 索引访问操作 假设我们定义了一张表a ，该表中存在 a ，b ，c ，d ，e 五个属性。而且在表a 上 面我们建了两个索引i n d e x a 和i n d e x b ，其中i n d e x a 是建立在a 、b 两个属性上面 的，而i n d e x b 是建立在a 、c 、d 三个属性上面的。那么我们这样来描述表中的任 意一条记录：( k ，x ) 。其中k 表示该记录存在于某个索引上的属性集，而x 表 示该记录不存在于同一个索引上的属性集。也就是说k 和x 的并集是记录的所有 属性集，当然，允许x 为空集，而k 由于是索引上的属性集，必须不为空，至少 有一个属性。根据该定义，分析表a 上面的两个索； i n d e x a 和i n d e x b 。对于i n d e x a ， k 。d e 。表示的是集合 a ，b ，x 1 。d e x a 表示的是集合 c ，d ，e ；而对于i n d e x b ，k 。d c x b 表示的是 a ，c ，d ) ，x 。d c x b 表示的是 b ，e 。可以看出对于同一张表，在不同的 索引上( k ，x ) 的表示是不同的，但是k 和x 的并集始终是相同的。在索引上， 由于需要对下一码加锁，所以除了表中的真实数据以外，还需要构造一个最大值 的键值对( k ，x ) 出来，我们用一个无穷大值来表示，也就是说每一个索引都默 认含有一个无穷大的记录，我们用( c o ，n u l l ) 来表示。当然这条记录不参与插 入和删除过程。 在前面的定义基础上，我们定义数据库索引的几个主要操作。 3 1 2 1 查询 查询，f e t c h k ，eu ，叩v ，x 】：表示的是从索引中获取第一个满足条件的( k ， x ) 。这个条件由eu 定义，其中u 是值表示一个比前面定义的一小的记录而0 表 示的是一个比较符号，包括“= ”、“ ”、“ - ”三种符号，而要满足的条件就是找 到第一个( k ，x ) 使得k 0u 。同理币v 表示的也是一个比较条件，v 的定义和u 相同，只不过q 所表示的是“ 1 0 ， 2 0 ， x 1 ，如果2 0 可以当作下一码键值来加锁，接下来t 又进行1 9 的插入，那么由于 2 0 本身是t 插入的，所以在对1 9 的下一码加锁的时候肯定能成功，于是1 9 被顺 利的插入。t 提交了。这时候t 1 如果还来做相同的查询，那么1 9 这一项将被作 为结果返回，幻象产生。 因此对于插入键值所使用的锁必须保证插入的键值不会被其它数据读取，不 会被作为范围键值来加锁。而对下一码加锁的锁必须保证这个锁能检测出当前的 插入是否在某个范围当中。对于插入键值我们使用x 锁，x 锁需要和s 、i r s 以 及i r ss 锁冲突。而对于下一码加的锁类型我们定义锁i in 来表示，_ n 锁需 浙江大学硕士学位论文第4 章索引并发控制协议 要具有的性质就是它必须跟范围锁相关的锁，如i r s 、i r ss 以及后面介绍的其 它范围锁都冲突。 3 3 3 索引的删除 按照前面的定义，索引的插入由d e l e t e 【k ，x 】表示。索引的删除实际上和索引 的查询有很类似的地方。因为删除的第一步同样是查找到所有满足删除条件的 项，然后再执行删除动作。两者所要区别的就是由于删除做的是修改操作，而查 询是不修改的，所以它们之间的加锁协议有所区别。由于索引很少全部所包含表 中的所有属性，因此可能出现如下图描述的情况： 图3 - 8 索引删除示例索g 假设存在上图描述的表和索引，该索引所在的表有两个属性 a ，b ，叶结点的 数据项的格式按照前面定义的( k ，x ) 来表示。现在有一个事务t l 执行包含如 下条件的删除操作：w h e r ea 2 0a n db = 5 。那么对应到索引上的操作则是首先通 过查询f e t c h k ，n u l l ， 2 0 ，x 1 定位出满足删除条件的项，然后再比较删除。对 于( 5 ，5 ) 这一项，索引上的属性a = 5 ，满足条件。但是属性b 是否满足条件需 要通过到表中访问比较才能判断。由于还不能判断该记录是否完全满足条件，不 能对记录加严格的删除锁，但是如果不加锁，那么该项可能会被其它并发的事务 删除。所以需要对该记录加锁，对有意向进行修改的数据项加锁必须加修改型的 u 锁( 1 ”，因为如果加s 锁，可能会产生死锁，这个是要避免的。当在表中的属性 也判断满足条件，说明该项确实满足条件并且是提交项，那么可以执行删除了， 这个时候就要加删除锁。可见删除操作的加锁是两阶段的，先加u 型的修改锁， 再加x 型的删除锁。 同时由于删除操作和查询操作很类似，删除操作的前提也是要先进行查询比 浙江大学硕士学位论文第4 章索引并发拧制协议 较。所以和查询操作一样，我们需要保证对于删除的查询。范围内的数据项也要 满足符合的项不被删除，而不符合的项不能被其它事务插入这两个性质。所以在 使用u 锁和x 锁的同时，还需要使用范围锁来保证可串行性。现在总结一下删除 操作涉及的锁类型： 1 1 首先删除是由两个阶段来完成的，第一阶段判断索引上的属性满足条件， 先加u 锁，第二阶段判断表上的属性是否满足，满足了加x 锁删除。 2 1 其次删除操作和查询操作一样，都需要加范围锁来保证操作的可串行性。 具体的范围锁方式和查询类似。 综合以上两点，和查询一样，我们把范围锁和数据项加锁结合在一起考虑， 对于索引上满足条件的范围内的数据项，由于既要加范围锁，也要加修改锁 即使该项在表上的属性不满足条件也是如此。所以我们定义一个范围修改锁 i r su 用来对范围内的项锁定并且锁定范围。当表上属性的判断结束之