（计算机应用技术专业论文）基于mysql的数据库系统并发控制及自优化研究.pdf

摘要 基于m y s q l 的数据库系统并发 控制及自优化研究 作者简介：李学强，男，1 9 8 0 年1 1 月出生，2 0 0 4 年9 月师从于成都理工大学罗 省贤教授，于2 0 0 7 年7 月获硕士学位。 摘要 数据库系统是当前最复杂的软件系统之一，为保证各个并发事务的a c i d ( a t o m i c i t y 、c o n s i s t e n c y 、i s o l a t i o n 、d u r a b i l i t y ) 特性，并且保证高并发度和高性 能，数据库系统必须采用某种并发控制机制来保证事务的可行性调度。负责并发 控制的d b m s 部件是调度器。一般来说，有三种调度器，分别为基于锁、时间戮 和有效性检查。作为一个完全支持事务的关系型数据库管理系统，m y s q l 的 i n n o d b 引擎采用了基于锁的调度器。i n n o d b 的锁系统是拥有非常完善的可以进 行行级读写锁的两阶段封锁协议的系统。本文深入研究、分析了m y s q l 引擎 i n n o d b 基于锁的并发控制机制，包括锁的类型、模式以及锁的结构等，这为m y s q l 的自优化实现，特别是并发控制的自优化实现奠定了良好基础。 自主管理是目前数据库系统亟待解决的重要问题之，解决数据库系统自主 管理的核心是使得系统能够自动调度资源，以达到系统运行的目标。本文分别实 现了数据库系统并发控制的自主优化模型和数据库内存资源配置的自主优化模 型。数据库系统并发控制的自主优化模型能够准确预测运行时系统的数据冲突率， 并对数据访问进行控制，从而有效地提高资源利用率，增强系统的稳定性。内存 资源配置白优化模型在确定系统瓶颈后自动找到适合提高系统运行效率的配置参 数，达到优化的目的。通过实验，两个模型均取得了较为明显的优化效果。 关键词：数据库：并发控制；锁；自优化；m y s q l 成都理r 大学硕十学位论文 ar e s e a r c ho fd a t a b a s es y s t e mc o n c u r r e n c yc o n t r o l a n ds e l f - o p t i m i z a t i o nb a s e do nm y s q l a bs t r a c t d a t a b a s em a n a g e m e n ts y s t e mi so n eo ft h em o s tc o m p l e xs o f t w a r es y s t e m s i n o r d e rt o s u p p o r tt h ea c i d ( a t o m i c i t y 、c o n s i s t e n c y 、i s o l a t i o n 、d u r a b i l i t y lo f c o n e k l f r c n c yt r a n s a c t i o n s 。h i g hc o n c u r r e n c ya n dh i g hp e r f o r m a n c e ，d b m sm u s t m a i n t a i nt h es e r i a l i z a b i l i t yo ft r a n s a c t i o n sb yu s i n gak i n do fc o n c u r r e n c yc o n t m l t h e d i s p a t c h e ri si nc h a r g eo fi t g e n e r a l l ys p e a k i n g ，t h e r ea r et h r e ed i s p a t c h e r sa n dt h e ya r e l o c kb a s e d t i m e a t m n pb a s e da n dv a l i d a t i o nb a s e dr e s p e c t i v e l y a sar e l a t i o nd b m s s u p p o r t i n gt r a n s a c t i o nc o m p l e t e l y , i r m o d bd a t ae n g i n eo fm y s q l u s e st h ed i s p a t c h e r b a s e do nl o c k i n n o d bl o c ks y s t e mh a st h et r a d i t i o n a lt w o d h a s el o c k i n gp o l i c ys y s t e m a n dc a r lm a k er o wl e v e lr e a d w r i t el o c k t h i sp a d e rm a k e sa l li n d e p t hs t u a yo nt h e l o c k b a s e dc o n c u r r e n c ye o n t r o lm e c h a n i s mo fi r m o d bd a t ae n g i n eo fm y s q l i n c l u d i n gl o c kt y p e 1 0 c km o d e la n dl o c ks t u c t u r e w h i c hl a y sg o o df o u n d a t i o nf o rt 1 1 e r e a l i z a t i o no fm y s q ls e l f - o p t i m i z a t i o n ，e s p e c i a l l yf o rt h er e a l i z a t i o no fc o n c u r r e n c y c o n t r o ls e l f - o p t i m i z a t i o n a b s t r a c ts e l f m a n a g e m e n ti sac u r r e n t l yc r i t i c a lp r o b l e mo fd a t a b a s em a n a g e m e n t s y s t e m t h ek e ys o l u t i o nt os e l f m a n a g e m e n ti st om a k ed a t a b a s es y s t e mm a n a g ei t s e l f a n du s ei t sr e s o u r c e se f f e c t i v e l y t h i sp a d e rr e a l i z e st w os e l f - o p t i m i z a t i o nd b m s m o d e l si nt h ep e r s p e c t i v e so fc o n c u r r e n c yc o n t r 0 1a n dm e m o r yr e s o u r c er e s p e c t i v e l y 7 i q a e f o r m e rw i l im a k ey o u rd a t a b a s es y s t e mm o r ei n t e l l i g e n tp o w e r f u la n dc o s t l e s sb y p r e d i c t i n ga n dc o n t r o l l i n gt h ed a mc o n f l i c tr a t i o t h el a t e rc a na d j u s ts y s t e mp a r a m e t e r s a u t o m a t i c a l l yt oa c h i e v eg o o dp e r f o f i n a n c e 。i na d d i t i o n b o t ht h et w om o d e l sh a v e r e a l i z e do b v i o u so p t i m i z i n ge f f e c t sb ym e a n so f e x p e r i m e n tt e s t i n g ， k e yw o r d s ：d a t a b a s e ；c o n c u r r e n c yc o n t r o l ；l o c k ；s e l f - t u n i n g ：m y s q l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得成都理工大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者导师签名：誓7 省赁 学位论文作者签名：乡耋 孳 鲡、 7 ，刁年 j 7 月么j 同 学位论文版权使用授权书 本学位论文作者完全了解丛壑理王盔堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阂。本人授权盛壑翌至盔堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者魏考亏鳋 2 。， 年歹月1 j 只 第1 章引言 1 1 研究背景 第1 章引言 随着企业信息化建设的不断深入，数据库管理系统( d a t a b a s em a n a g e m e n t s y s t e m ) 越来越成为公司和大型企业的核心i t 系统，从民用的管理系统到军队 的指挥自动化系统都离不开数据库管理系统，它已成为支持应用系统的核心软 件。数据库性能的好坏直接影响着整个应用系统的正常运行。 数据库技术发展至今已经有了很多成熟的商品化的数据库管理系统( d b m s ， d a t a b a s em a n a g e m e n ts y s t e m ) ，例如：o r a c l e 、l n f o r m i x 、s y b a s e 、s q ls e r v e r 等。然而，目前国产数据库产品基本处于空白状态。为了今后开发具有自主知识 产权的国产数据库，必须要有一定的技术积累。技术积累最快的方法就是研究现 有数据库的实现技术。这样就可以直接应用到新开发的数据库产品中。在众多开 源数据库产品中，m y s q l 是其中非常出色的一个，m y s q l 的i n n o d b 引擎完 全支持事务，性能很优越，并且支持行级锁。而i n n o d b 引擎部分的代码结构 化好，非常适合进行研究和分析。另外，m y s q l 实用性也非常好，有广泛的用 户群。 计算机技术的不断进步使得计算机硬件和软件本身的价格逐渐降低，同时数 据库管理系统的规模越来越大，复杂度越来越高，能够操作管理这些系统的专业 人员越来越少，价格也越来越高，花在人力资源上的费用逐渐成为部署电子商务 应用的主要支出。为了更好地增强数据库系统的稳定性，减少数据库系统的维护 费用，实现数据库系统的自我管理能力成为解决这个问题的关键。 1 2 国内外研究发展现状 目前，各大数据库商业巨头以及研究所等科研单位都在致力于数据库自主管 理的研究。 i b m 在数据库自优化方面做了大量研究工作，很多理论成果都已经应用到它 的数据库产品d b 2 中。例如，d b 2 的u d b sq u e r yo p t i m i z e r 组件使用了两 种自调节方法来进行查询优化。一个是把用户查询转化成标准的易于优化的查 询；另一个是使用一套代价模型来评价一个查询的众多查询计划，这个模型可以 根据机器的硬件环境自动进行调整。另外，d b 2 的c o n f i g u r a t i o na d v i s o r 可以 自动配置数据库系统的内存，服务器的数目，日志刷新频率等参数。除此之外， 成都理工大学硕七学位论文 d b 2 的a u t o m a t i ci n d e xr e o r g a n i z a t i o n 、u d bd e s i g na d v i s o r 、u d bq u e r y p a t r o l l e r 、a u t o m a t i cq u e r yp a r a l l e l i s ms e l e c t i o n 、l o a du t i l i t ya u t o m a t i ct u n i n g 、 a u t o m a t i ci n c r e m e n t a lr e s t o r e 和a u t o m a t i cc o n s i s t e n c y c h e c k i n gas e c t o rf o rp a g e i 0 等组件都使用了自调节的技术。 o r a c l e 也一直致力于数据库自优化技术的研究，其最新产品o r a c l e1 0 9 已经 能够动态的调整系统的配置。在这之前的o r a c l e 版本当中，系统管理员只能实时 监测系统的性能，以便及时发现问题，但是并不允许系统管理员实时地改动这些 参数，除非停止或重新启动数据库系统。这对负载不断变化的系统是非常不利的。 新产品则允许系统管理员动态调整系统配置。例如，当系统缓冲区的命中率大大 下降时，数据库管理员可以立即动态增加缓冲区的大小去改善这个问题，而不会 影响数据库的正常运行，这为o r a c l e 的自优化实现奠定了基础。 o r a e l e l o g 在数据库服务器上引入了一套复杂的自管理系统，这套系统允许 数据库自我收集数据，分析数据，并利用这些分析结果调节环境参数或者自动修 复潜在的问题。o r a c l e l o g 自调节系统由4 个部分组成：自动化的w o r k l o a d r e p o s i t o r y ( a w r ) 、自动化的m a i n t e n a n c et a s ki n f r a s t r u c t u r e ( m t l ) 、s e r v e r g e n e r a t e da l e r t s ( s g a ) 和a d v i s o r yf r a m e w o r k ( a p ) 。 同时，还提供了一些附属工具实现数据库的自管理。例如，引入了一个自我 诊断的数据库引擎，称为数据库自动诊断监视器( a u t o m a t i cd a t a b a s ed i a g n o s t i c m o n i t o r ，a d d m ) 。a d d m 使得数据库能够诊断自己的性能，并确定问题所在。 在每一次a w r 收集到统计数据之后，a d d m 会自动运行，对a w r 捕获的数 据进行分析，并对系统性能进行预测。如果发现潜在的问题可以给出推荐的解决 方案，并对方案可能带来的好处进行评估。a d d m 采用历史比较的方法对系统 性能进行分析，其目标就是识别消耗d b t i m e 最多的部件。 除了a d d m 工具之外，o r a c l e l o g 还提供了自动s q l 调节工具，用于自动 优化应用程序s q l ；自动共享内存管理工具，用来自动管理内存，这个工具可 以自动配置共享缓冲池、j a v a 缓冲池以及内存缓冲池的大小，即管理员不需要 事先预设上述几个缓冲池的大小( 默认情况下，上述几个参数的大小都为o ) ， 无论何时哪个部件需要内存，它都可以通过内部的自动调节机制得到，这些对管 理员而言是透明的，不需要人为的干预。如果服务器端的参数文件s p f i l e 使 用的话，那么上述经过自动调节的各个部件的大小会在服务器关机的时候自动写 入s p f i l e 文件中，当服务器下次启动时就不需要再次学习应用的特性而重新 配置合理的参数了。 空间管理也是非常耗费管理员的工作。但是在o r a c l e l o g 中，可以自动管理 它的空间消耗，提醒管理员潜在的空间问题，并推荐合适的解决方案。 2 第1 章引言 除了上述的提到一些部件之外，o r a c l e l o g 还实现下面这些方面的自动化操 作，包括：自动空间管理、自动存储管理、自动备份与恢复和自动配置管理等等。 s q ls e r v e r 数据库管理系统也在一定程度上实现了自调节能力【l 】。在s q l s e l v e r 中提供了两个重要的自调谐工具，一个是i n d e xt u n i n gw i z a r d 可以帮助 用户自动选择索引；另一个是s q ls e r v e rs t o r a g e e n g i n e ，提供了1 6 个服务器 方面的调谐节点。 1 3 本文的研究工作 本文以开源数据库新管理系统m y s q l 的i n n o d b 引擎为研究对象，分析了 源码当中基于锁的并发控制的实现机制，包括锁的类型、模式、转换以及基本操 作等，并在此基础上，实现两个数据库系统的自主优化模型。本文研究主要内容 有以下几点： ( 1 ) 并发控制的基本方式 并发控制是在多用户的环境下，对数据库进行并发操作进行规范的机制。本 文分析了三种并发控制的实现方法，即封锁、时间戳和有效性确认。并重点分析 了基于锁的并发控制的基本思想。 ( 2 ) i n n o d b 的锁的实现方式 作为一个完全支持事务的关系型数据库管理系统，m y s q l 的i n n o d b 引擎采 用了基于锁的调度器。i n n o d b 的锁系统是拥有非常完善的可以进行行级读写锁 的两阶段封锁协议的系统。i n n o d b 锁定数据资源( 1 0 c k ) 的方式有共享锁、排 它锁、意向排它锁、意向共享锁、自增锁五种形式。从锁的类型上看，l n n o d b 的锁实现了表级锁和行级锁。l n n o d b 拥有了一般数据库锁定的锁定资源、死锁 检测、并发使用等基本操作。 ( 3 ) 并发控制的自主优化模型 并发控制的自主优化模型是在数据库系统原有并发控制模型的基础上增加一 个反馈环路，在该环路中置入一个冲突控制器，负责收集系统的运行参数，并根 据这些参数决定是否对系统的并发控制策略作出调整。该模型能够准确预测运行 时系统的数据冲突率，并对数据访问进行控制，从而有效地提高资源利用率，增 强系统的稳定性。 ( 4 ) 内存资源配置自优化模型 数据库系统内存资源配置的自优化模型利用反馈环路，不断检测系统资源的 负载，根据资源利用情况分析数据库系统的性能瓶颈。在确定系统瓶颈后自动找 到适合提高系统运行效率的配置参数，根据配置参数值来调整系统的内存资源配 成都理工大学硕士学位论文 置，达到优化的目的。 本文的创新点如下： ( 1 ) 在m y s q l 上实现并发控制自优化模型 本文根据m y s q l 源码所提供的数据结构，实现了并发控制自优化模型。并 发控制自优化模型是在原有调度器之上增加了一个数据冲突管理器，冲突管理器 是该模型的核心组件。事务请求经系统入口进入事务管理器，首先被传递给冲突 管理器，经分析后交给调度器。例如，一个新的事务请求到达事务管理器。事务 管理器将该请求交给冲突管理器，冲突管理器检查当前系统的d c r 值：如果 d r c = i 3 ，则将事务请求置于等 待队列等待处理。当循环检测到d r c 值再次小于1 3 时，事务管理器可以接收新 的事务请求。 ( 2 ) 利用单独模块实现内存资源配置自优化模型 内存资源配置自优化模型是利用m y s q l 提供的接口实现与d b m s 交互的模 型。该模型完全独立于m y s q l 系统本身。系统的总体设计框架是反馈回路。在 本系统中诊断模块发现d b m s 资源瓶颈，根据状态参数进行内存优化配置。 4 第2 章并发控制与锁 2 1 并发控制综述 第2 章并发控制与锁 数据库管理系统( d b m s ) 由一个相关数据的集合和用以操作这些数据的程序组 成，这些相关数据的集合被称为数据库。d b m s 的目标就是要提供一个可以方便地、 有效地管理数据库信息的环境。数据库是一个共享资源，可以由多个用户使用。为 了充分利用数据库资源，必须允许尽可能多的用户程序并发地存取数据库，来达到 d b m s 资源利用的最大化。然而，当多个用户程序并发存取同一个数据元素时，如 果不加以控制就可能破坏整个数据库的一致性。所以，d b m s 的并发控制机制非常 重要。 2 1 1 事务和调度器 事务是数据库操作的逻辑单元，正确执行的事务符合“a c i d 准则”，即原子性、 持久性、一致性和隔离性： ( 1 ) 原子性( a t o m i c i t y ) ：事务要么全部执行，要么全部不执行； ( 2 ) 持久性( c o n s i s t e n c y ) ：已提交的事务所做的修改能长久保存； ( 3 ) 一致性( i s o l a t i o n ) ：任何数据库事务的执行都将数据库从一个一致的状态转变 到另一个一致的状态； ( 4 ) 隔离性( d u r a b i l i t y ) ：表面看起来每个事务都是在没有其他事务同时执行的的情 况下执行的。 图2 1 调度器 缓冲区 成都理工大学硕士学位论文 然而，即使各个事务都能保持状态的正确性，而且也没有发生任何故障，并发 事务之间的互相影响还是可能导致数据库状态的不一致。不同事务中各个步骤的执 行顺序必须以某种方式来进行规范。控制这些步骤的功能是由d b m s 的调度器部件 实现的，而保证并发执行的事务能保持一致性的整个机制称为并发控制机制。调度 器的作用如图2 1 所示。 当事务请求对数据库中的元素进行读写时，这些请求被传递给调度器。在大多 数情况下，调度器将直接允许执行读写操作。( 如果所需数据库元素不在缓冲区中就 首先调用缓冲区管理器) 。但是在某些情况下，立即执行请求是不安全的。调度器必 须推迟请求的执行；有的并发控制机制中，调度器甚至可能回滚发出该请求的事务。 事务的可串行性通常作为多个事务执行的正确性准则。更精确地说，多个事务 的某个执行过程是正确的，当且仅当其是可串行化的( 如果多个事务的某个执行过 程与同样的这些事务的某个串行执行过程产生的结果相同，则称其为可串行化的) 。 2 1 2 并发控制分类 在并发控制技术中，通常采用三种可串行化方法，即封锁、时间戳和有效性确 认。 1 ) 封锁技术 基于封锁技术的并发控制思想是，事务在对数据项操作之前必须先申请该数据 项的锁，只有申请到锁以后，才可以对数据项进行操作。通过锁的共享及排斥的特 性，实现事务的可串行化调度。有许多锁模式( 排它锁、共享排它锁、语义锁) ， 但它们实现并发控制的原理是一样的，即对事务问出现的冲突操作，通过加锁的原 则及锁的相容机制实现冲突操作的可串行化调度，当锁类型相容时，事务并行执行， 当锁类型不相容时，事务串行执行。使用锁模式的典型算法是两阶段锁协议( 2 p l 协 议) ，它要求任何事务对数据项的操作先加锁，如果一个事务一旦释放了一个封锁， 它将不再获得其他封锁。因此两段锁协议分为两个阶段：第一阶段是获得锁阶段， 第二阶段释放锁阶段。 封锁技术是数据库系统最常用的并发控制方式，m y s q l 的i n n o d b 即用了封锁 技术。 2 ) 时间戳技术 用时间戳技术实现事务的并发控制时，给每个事务赋予一个惟一的时间戳，事 务的执行等价于按时间戳的先后次序串行执行，即事务的冲突操作按时间的次序进 行调度。基于时间戳技术的并发机制思想是，只有当某一数据项上由一较年长的事 务写入以后才允许另一较年轻的事务对该数据项进行读写，否则它拒绝这个操作并 重新启动该事务，即一个事务只能读写它以前的事务写入的数据而不能读写它以后 6 第2 章并发控制与锁 的事务写入的数据。当出现年长的事务读写年轻事务写入的数据时，该年长事务遭 拒绝且重新启动被赋予一个新的时间戳，直到该时间戳大于原来年轻事务的时间戳， 即它变得比年轻事务更年轻时才可以读写原年轻事务写入的数据。 3 ) 有效性确认 有效性确认是另一种优化的并发控制类型，允许事务不经封锁访问数据，并在 适当的时候检查事务是否以一种可串行化的方式运转。有效性确认与时间戳的主要 区别在于调度器维护关于活跃事务正在做什么的一个记录，而不是为所有数据库元 素保存读时间和写时间。事务开始为数据库元素写入值前的刹那，它经过一个“有 效性确认阶段”，这时它已经读的和将写的元素集合被用来与其他活跃事务的写集合 做比较，如果存在物理上不可实现的风险，该事务就回滚。 当有效性确认被用作并发控制机制时，对每个事务t ，调度器必须被告知t 所 读的数据库元素集合与t 所写的数据库元素集合。这些集合分别被叫做读集合和写 集合。事务按两个或三个阶段执行，这取决于该事务是一个只读事务还是一个更新 事务( 只读事务为两个阶段，更新事务为三个阶段) ，三个阶段的操作如下： ( 1 ) 在第一阶段：读。各数据元素值被读入并保存在事务的局部变量中。事务还在 其局部地址空间中计算它将要写的所有值； ( 2 ) 在第二阶段：有效性确认。调度器通过比较该事务与其它事务的读写集合来确 认该事务的有效性。有效性确认的目的，就是判定是否可以将读阶段进行的操 作所更新的局部变量值写入数据库的同时又不违反可串行性。如果有效性确认 失败，则事务回滚；如果事务是更新事务，则继续进入第三阶段； ( 3 ) 在第三阶段：写。事务往数据库中写入其写集合中元素的值。有效性检查机制 自动预防级联回滚，因为只有发出写操作的事务提交后实际的写才发生。 2 2 可串行性实现 在申请对其它数据元素加锁之前如果不对当前锁住的数据元素解锁，则可能会 发生死锁。然而，如果不使用封锁，或者如果对数据元素进行读写之后立即解锁， 就可能会进入不一致状态。死锁可以通过回滚事务加以解决，而不一致状态可能引 起的现实中的问题是数据库系统所不能处理的。为维持数据的一致性，系统规定了 一系列每一个事务都遵从规则封锁协议，这些规则规定事务何时对数据元素加 锁、解锁。封锁协议限制了可能的调度数目，这些调度组成的集合是所有可能的可 串行化调度的一个真子集。 有两种可以实现可串行化调度的封锁协议，分别是两阶段封锁协议和树协议。 7 成都理工大学硕士学位论文 2 2 1 两阶段封锁协议 两阶段封锁协议( 2 p l ) 规定；在所有的事务中，所有封锁请求先于所有解锁请 求。该协议分为两个阶段，增长阶段和缩减阶段。其中增长阶段事务只能封锁，不 能解锁；而缩减阶段事务只能解锁，不能封锁。 两阶段封锁协议可以保证一致事务的合法高度是冲突可串行化的。对于任何事 务，调度中该事务获得其最后加锁的时刻( 增长阶段结束点) 称为事务的封锁点。这样， 多个事务可以根据它们的封锁点进行排序实际上，这个顺序就是事务的一个可串 行性次序。但是，两阶段封锁协议并不保证不会发生死锁和级联回滚。所以，又出 现了改进了的两阶段封锁协议版本，叫做严格两阶段封锁协议。这个协议除了要求 封锁是两阶段的之外，还要求事务持有的所有排它锁必须在事务提交后方可释放。 这个要求保证未提交事务所写的任何数据在该事务提交之前均以排它方式加锁，防 止了其它事务能读取到这些数据。 另一个两阶段封锁的变体是强两阶段封锁协议，它要求事务提交之前不彳导释放 任何锁。在这种情况下，事务可以按其提交的顺序串行化。大部分商用数据库系统 要么采用严格两阶段封锁协议要么采用强两阶段封锁协议。 2 2 2 树协议 对于访问像b 树这样的树结构数据时，原则上任何插入或删除的事务可能最终重 写b 树的根，因此，任何时刻都只有一个非读的事务能访问b 树，在这种情况下如果 严格遵从2 p l ，数据库的运行效率将会低得非常可怕。不过由于在这种结构中，达到 结点的惟一方式是通过其父结点，即必须沿着通向元素的特定路径。例如，数据元 素集合d = d l ，d 2 ，d n 的所有数据元素满足偏序。如果d i d j ，则任何既访闯d i 又访 问d j 的事务必须首先访问d i ，然后才访问d j 。这为不同于2 p l 来管理锁提供了重要条 件。 在树形协议事务中必须遵从以下规则： ( 1 ) 事务的第一个锁可以在树的任何结点上； ( 2 ) 只有事务当前在父结点上持有锁时才能获得后续的锁； ( 3 ) 结点可以在任何时候解锁： ( 4 ) 事务不能对一个它已经解锁的结点重新上锁，即使它在该结点的父结点上仍持有 锁。 2 3 锁的模式 数据库中的锁是一种保证共享数据资源一致性的控制方式。对数据上锁表示某 个用户进程已经占用了本资源，从而防止其它用户作出影响本用户的数据修改或导 8 第2 章并发控制与锁 致数据库数据的不完整性和不一致性的行为。 2 3 1 锁的类型 大多d b m s 都支持以下4 种类型的锁： ( 1 ) 共享锁( s h a r el o c k ) ：数据元素可被一个或多个事务加上共享锁，其它要求写该 数据元素的事务在对该数据元素提出写操作时必须被推迟； ( 2 ) 排它锁( e x c l u s i v el o c k ) 又称独占锁：一个数据元素只能被一个事务加上排它锁， 当数据元素己被一个事务加上排它锁时，其它的事务不能再对该数据元素进行 读操作和写操作； ( 3 ) 更新锁( u p d a t el o c k ) ：当事务对某一数据元素拥有更新锁时，表示该事务可能要 更新该数据元素。当更新确实发生时，再把此更新锁上升为排它锁。更新锁与共 享锁是相容的，故使用更新锁可获得更大的并发性，这也正是提出更新锁的原因 所在；更新锁与排它锁和其它更新锁是不相容的。当两个事务企图更新同一目标 时，其中一个事务将为获得更新锁而处于等待状态，等待另一事务更新结束，这 样就避免了死锁的发生。更新锁常用于较小粒度。d b 2 ， s y b a s e 等都支持更新 锁； ( 4 ) 意向锁【4 ( i n t e n tl o c k ) ：意向封锁是粗粒度的封锁，常作用于表和表空间( t a b l e s p a c e ) 级别，一个事务可同时得到一个粗粒度的意向封锁和一个细粒度的共享、 更新或排它性封锁。当事务处理某一基本集中的记录时，要求基本集中的记录不 被其它事务更新，为了减少封锁次数，提高并发性，可对基本集加意向封锁。 d b 2 ，s y b a s e 都支持意向封锁，不同的d b m s 提供的意向封锁不完全相同。意向 封锁包括以下3 种： 意向共享( 1 s ) ：常用于读基本集中的页或个别记录； 意向排它0 x ) ：常用于事务要对某基本集中的个别记录进行更新的情况下，对 基本集加意向排它锁； 共享意向排它( s i x ) ：它为在事务允许其它并发事务读取基本集中的一记录， 但不允许更新，同时该事务可能要更新基本集中个别一记录时加的锁。它可 被看成对整个表或表空间加共享锁及一个意向排它封锁。 2 3 2 锁粒度 用户可以操作的数据包括记录、索引以及数据表等。因此对数据上锁也有不同 粒度( m u l t i g r a n u l a r ) 之分，也就是指可以锁定的资源有不同的层次。一般系统中，锁 的粒度从粗到细包括数据库( d b 级) ，表( t a b l e 级) ，页( p a g e 级) ，记录( r e c o r d 级) 等。因 为单个封锁级别不可能在任何情况下都合适，故关系数据库系统大都支持多粒度的 封锁。适当选定封锁的粒度是非常重要的，封锁的粒度越细，锁表空间中的封锁条 9 成都理工大学硕十学位论文 目越多，封锁管理系统使用的资源( 包括存储空间和处理时间) 也就越多，而数据库发 生死锁的可能性则越低，并发性能也越高；反之则刚好相反。 当一个事务持有大量的细粒度的锁又试图获得更多的细粒度锁时，常进行锁粒度 升级( 例如把对众多记录级的封锁提升为对表或表空间级的封锁) ，它能减少为获得较 多封锁及跟踪大量的细粒度封锁而产生的开销。s y b a s e 和s q l s e r v e r 都支持锁粒度逐 步升级，有些系统还允许用户控制升级的界限点，例盎i d b 2 ，m v s 的管理员可用命令 l o c k m a x 参数设定升级的界限点。另外，有些系统还允许人为设定最细的封锁粒度， 如d b 2 m v s 可通过在c r e a t et a b l e s p a c e 语句中加上l o c k s i z e 参数设定最小封锁粒度。 2 3 3 手动加锁 一般情况下，数据库系统对锁进行自动管理。用户操作数据库时，系统会分析用 户的s q l 语句请求，自动为该请求加上合适的锁( 包括合适的锁模式和合适的锁粒度 级别) ，并且在锁数目太多时，自动进行锁升级。如前所述，升级的阀值由系统自动 配置，不需要用户( 或者d b a ) 干预。有时为了保证特殊应用程序正确运行和保持数据 的一致性，可以手动地给数据库的某个表加锁。例如，在某应用程序的一个事务操 作中，需要根据一编号对几个数据表做统计操作，为保证统计数据的( 时间) 一致性和 正确性，在从统计第一个表开始到全部表统计结束，其它应用程序或事务不能再对 这几个表执行写操作，此时，该应用程序希望在从统计第一个数据表开始或在整个 事务开始时能够由程序手动地( 显式地) 锁定这几个表，这就需要用到手动加锁( 也称 显式加锁) 技术。d b 2 和m ss q ls e r v e r 2 0 0 0 都提供此支持。 2 3 4 锁表空间管理 数据库的加锁信息包括被加锁的数据元素以及所加锁的模式等，在内存中的存 放空间叫做锁表空间。大多数据库系统都对锁表空间进行统一管理，即它在整个系 统中是惟一的。由于每个进行数据库操作的事务都要访问锁表空间，因此，锁表空 间本身的并发性问题必须仔细考虑。 可以将锁机制粗分为排它性锁机制与非排它性锁机制两大类。排它性锁机制保 证一段共享数据在任问时刻只被一个工作线程访问；而非排它性锁机制允许多个工 作线程同时访问一个共享的数据结构。以下介绍的循环等待锁( s p i n l o e k ) 与带计数器 的信号灯锁( c a u n t e r s e m a p h o r e ) 属于排它性锁机制范畴，而读写锁属于非排它性锁机 制范畴。 1 ) 循环等待锁( s p i n l o c k ，也称自旋锁) s p i n l o e k 锁机制也称为简单性锁机制，它主要通过循环等待锁释放来实现。 s p i n l o c k 的主要特点是调用s p i n l o e k 的工作线程一直占据着c p u 的计算能力，它循环 测试该锁是否开放。 1 0 第2 章并发控制与锁 s p i n l o c k - - 般用于加锁那些共享数据结构，而且访问这些数据结构的程序只需要 执行少数将几条机器指令，或者称占有锁的时间较短，也称关键节( c r i t i c a ls e c t i o n ) 较短。使用s p i n l o c k 必须注意以下两点： ( 1 ) s p i n l o e k 必, 须使用在c r i t i c a ls e c t i o n 较短的场合( 几条到儿十条机器指令) 。应该绝 对避免在需要长时间持有锁的情况下使用； ( 2 ) 使用在锁机制竞争出现的概率较低的数据结构中。 s p i n l o c k - - 般使用硬件提供的保证原子性操作的指令或者软件( 比如操作系统) 提 供的保证原子性操作的系统调用来实现。比如在w i n d o w s 系统下可使用 i n t e r l o c k e d l n c r e m e n t 系列的a p i ，在某些支持t e s t a n d s e t 机器指令的机器上可以利用 t a s 指令。 2 ) 带计数器的信号灯锁( c o u n t e r s e m p h o r e ) 通过一个计数器来标识锁的状态。当计数器的值小于某一阀值则表示锁开放，否 则表示锁已经关闭。当一个线程申请某一个c o u n t e r s e m a p h a r e 失败后将进入到睡眠状 态，当前线程被挂入到一个睡眠队列。该线程最终将被释放该c o u n t e r s e m a p h o r e 的其 它线程唤醒，并重新申请该锁。c o u n t e r s e m a p h o r e 与s p i n l o c k - - 样属于排它性的锁机 制，可用于上述讨论的s p i n l o c k 不适合使用的场所。 c o u n t e r s e m a p h o r e 机制由一个计数器，一个s p i n l o e k 以及定义在该数据结构上的p 和v 操作组成。s p i n l o e k 用于保护对c o u n t e r s e m a p h o r e 本身的排它性操作，p 操作用于 申请锁，v 操作用于释放锁。 3 ) 读写锁( r e a d w r i t el o c k ) r e a d w r i t el o c k 是一种非排它性的锁机制。这种锁机制适于保护下述的共享数 据结构：对这种数据结构的存取形式包括一个w r i t e r 以及多个r e a d e r s 。r e a d ，w r i t e l o c k 保证w r i t e r 只有在没有其它r e a d e r 和w r i t e r 占有该锁时才可修改由该读写锁保护 的共享数据；同时也保证当有一个w r i t e r 占有该锁并且修改共享数据时，其它所有的 r e a d e r s 都必须排队等待。u n i x 核心并行化过程中，文件系统代码涉及到的共享数据 结构有很好的多r e a d e r 少w r i t e r 性质，因此u n i x 核心并行化过程大量地使用了r e a d w r i t e rl a c k 机制。 r e a d w r i t el o c k , - j 基于s p i n l o c k 以及c o u n t e r s e m a p h o r e 两种方式进行实现，有时 也称为u n b l o e k 与b l o c k 实现。前者在申请锁操作失败后当前线程并不进入睡眠状态， 而是通过循环测试方式一直等待；而后者在申请失败后，当前线程进入睡眠状态， 进行线程的切换工作。 成都理工大学硕士学位论文 第3 章m y s q l 并发控制的实现 m y s q l 软件提供了十分快速的多线程、多用户、牢靠的s q l ( 结构化查询 语言) 数据库服务器，是最流行的开放源码s q l 数据库管理系统。本文以m y s q l 源码为例分析锁的实现机制。 3 1m y s q l 的基本结构 m y s q l 采用插件式存储引擎体系结构，目前m y s q l 的最新版本m y s q l 5 1 中允许将存储引擎加载到正在运新的m y s q l 服务器中。在图3 1 中，以图形方 式介绍了m y s q l 插件式存储引擎体系结构。 图3 1m y s q l 的体系结构 使用m y s q l 插件式存储引擎体系结构，允许数据库专业人员为特定的应用 需求选择专门的存储引擎，完全不需要管理任何特殊的应用编码要求。采用 m y s q l 服务器体系结构，由于在存储级别上提供了一致和简单的应用模型和 a p i ，应用程序编程人员和d b a 可不再考虑所有的底层实施细节。因此，尽管 不同的存储引擎具有不同的能力，应用程序是与之分离的。较为常用的存储引擎 第3 章m y s q l 并发控制的实现 是m y s i a m 、b d b 、m e m o r y 、i n n o d b 、a r c h i v e 、n d b ，这种引擎都有自己的特 点，见表3 1 。 表3 1 存储引擎特点 f e a t u r em y i s a mb d bm e m e o r yi n n o d ba r c h i v en d b s t o r a g el i m i t s n on oy e s6 4 t bn 0y e s t r a n s a c t i o n ( c o m m i t ，e c t ) ， l o c k i n gg r a n u l a r i t y t a b l e p a g e t a b l er o wr o wr o w g e o s p a t i a ls u p p o r t b t r e ei n d e x e s h a s hi n d e x f u l lt e x ts e a r c hi n d e x c l u s t e r e di n d e x d a t ac a c h e s i n d e xc a c h e s ( 注：表不支持) 可以看出，i n n o d b 给m y s q l 提供了具有提交，回滚和崩溃恢复能力的事务 a c i d ( a t o m i c i t y 、c o n s i s t e n c y 、i s o l a t i o n 、d u r a b i l i t y ) 等特征，是功能最强大的存 储引擎。另外，i n n o d b 还支持行级锁。l n n o d b 的结构如图3 2 所示。 本文以i n n o d b 为例来分析并发控制的实现机制。并发控制部分的源代码的 主要包含在文件夹l o c k 、r e a d 和r o w 中，通过分析这几个文件可以详细了解了 i n n o d b 的基于锁机制的并发控制的实现，为基于并发控制的自优化模型的实现 奠定了基础。 3 2 锁的模式 通过分析源码中l o c k 文件夹下的l o c