（计算机应用技术专业论文）dbms锁机制研究.pdf

捐簧 浙江丈举鲠士学位论文 恭要 作为计算机软件的一个重要分支，数据库镣理系统是当前最复杂舱软件系统 之一。数据库管理系绕( d b i s ) 是一个强有力的工具，用于商效她管琏大量的数 据，并使德数据能够安全地长期保存，并且向爝户提供缡程接鞠以及饔务管理豹 能力。 为保证务个势发事务静a c i d 特靛，劳且绦 丕蹇并发度霹楚蛙裁，鼗据瘁系 统必颁采用某种并发控制机制来保诋事务的可串行性调度。负责弗发控制的 d b m s 帮串是巍凄器。一觳寒滋，有三耱调蹙嚣，分鬟凳基手锬、爵阙觳农鸯散 性检谶。作为种大型的对象关系型数据库管理系统，o s c a r 采用了旗于锁的调 度嚣。 本文主要介绍了o s c a r 数攒库管理系统的锁管理横块的设计和实现方法。零 镄管理系统是针对实现二阶段锁协议和树协议瓶设计淇现的。艇体实现了三层锁 粒度，支持各个锬粒度熟自动嬲锬算法，支持餐能兹镁靛度秀级算法。该模块麓 时提供死锁检测线程按照可动态调整的时间间隔来执行死锁检测。 关键词：数据露管理系统势发控裁镁瓠裁铰表察麓 a b s t r a c t浙江大学l f i ! 上学位论文 a b s t r a c t a sa ni m p o r t a n tb r a n c ho fc o m p u t e rs o f t w a r e s d a t a b a s em a n a g e m e n t s y s t e m i sac o m p l e xo n e d b m si sap o w e r f u lt o o lt om a n a g em a s sd a t av e r y e f f i c i e n t l y d a t a b a s em a n a g e m e n ts y s t e m i su s e dt op r o v i d ed u r a t i o ns t o r a g e ， p r o g r a m m i n gi n t e r f a c e sa n d t h ea b i l i t yt om a n a g et m n s a c l i o n i no r d e rt o s u p p o r t t h ea c i do f c o n c u r r e n c yt r a n s a c t i o n s ，h i g h c 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 tm a i n t a i nt h es e r i a l i z a b i l i t yo f t 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 r 0 1 t h ed i s p a t c h e ri si nc h a r g e o fi t t h e r ea r et h e r et e c h n i c sf o rd i s p a t c h e r - - l o c kb a s e d ，t i m e s t a m pb a s e d a n dv a l i d a t i o nb a s e d o s c a ru s e st h e d i s p a t c h e rb a s e do nl o c k t h i sd i s s e r t a t i o nf o c u s e so nt h ed e s i g na n di m p l e m e n t a t i o no fo s c a r 。s l o c km a n a g e m e n tm o d u l e t w o - p h a s el o c k i n gp r o t o c o la n dt r e e l o c k i n g p r o t o c o lc a nb ei m p l e m e n t e do nt h i ss y s t e m 。t h i sm o d u l e i m p l e m e n t sm u l t i p l e g r a n u l a r i t yl o c k ( t h r e el e v e l s ) ，a u t o m a t i cl o c ka n da u t o m a t i cl o c ke s c a l a t i o n a n di ts u p p or t sd e a d l o c kd e t e c t i o n k e y w o r d s ：d b m s ，c o n c u r r e n c y c o n t r o l ，l o c k m a n a g e m e n t ，l o c k t a b l e 第1 章绪论浙江大学硕上学位论文 1 1 背景介绍 第1 章绪论 随着计算机科学与应用几十年的发展，数据库管理系统取得了长足的进步。 数据库系统是对数据进行存储、管理、处理和维护的软件系统，是现代计算环境 中一个核心部分。随着计算机硬件、软件技术的飞速发展和计算机系统在各个行 业的广泛应用，数据库技术的发展尤其迅速，引人注目。d b m s 目前已经在国民 经济中产生了不可替代的作用了。比如银行，航空等部门就大量地使用了d b m s 。 当今占据主导地位的d b m s 产品包括有o r a c l e ，s q ls e r v e r ，d b 2 ，s y b a s e ， i n f o r m i x 等。 这些国外产品比如o r a c l e ，d b 2 已经占据了大部分份额的数据库市场。然而， 这些数据库是从传统的关系模式发展起来的，针对的是通用的情况。这样它们对 于大型的类型复杂的工程数据的支持并不是很好。而一些设计过程如航天设计则 经常会使用到一些具有相当复杂和庞大结构的数据，直接使用依赖于纯关系模式 的数据库无法做到高效的数据存取，它们需要一些专用的工程数据库来存储。 此外，在比如航天这类涉及到国家机密的部门中，在数据库中存放的通常都 是一些非常机密的信息，使用无法获得其源代码的国外数据库系统，将很难保证 数据的完全的完整性、可靠性和安全性。以操作系统为例，w i n d o w s 平台已经发 生多起所谓的“后门”事件，在国外商用数据库产品中，也很难排除外国政府在 数据库系统中插入一些对其有利的恶意代码。只有具有自主版权的国产数据库管 理系统，才能够控制其源代码，进而才能完成安全可靠等方面的要求。 1 1 1o s c a r 总体介绍 神舟o s c a r 数据库，是拥有完全自主知识产权的企业级大型、通用对象关 系型数据库管理系统。它是北京神舟航天软件技术有限公司集多年的数据库研发 经验，在国家科技部和中国航天科技集团的大力支持下研制成功的，是“十五” 8 6 3 重大软件专项“大型通用数据库管理系统及其应用”的研制成果，是一个在 功能、性能、实用性、稳定性、安全性以及可扩展性等方面能够满足电子政务、 电子商务、企业信息化以及国防工业等敏感部门信息化建设需求的大型通用数据 第1 章绪论 浙江大学硕士学位论文 库产品。神舟o s c a r 数据库系统性能稳定、功能完善，可广泛应用于各类企事 业单位、政府机关，尤其是国防、军工等事关国家政治、军事、经济安全的各要 害单位的信息化建设。 作为一个较为成熟的对象关系型数据库管理系统，o s c a r 数据库具有如下 的特点： 神舟o s c a r 数据库管理系统支持w i n d o w s 、l i n u x 以及s o l a r i s 等多种主 流操作系统平台，应用j a v a 技术定制各种数据库管理工具，具有很好的跨平台 支持能力；系统采用成熟的关系数据模型作为核心的数据模型，支持通用数据查 询语言s q l ，因此可以在各行业中广泛应用。 神舟o s c a r 支持包括集中式结构、客户朋鼹务器结构、w e b 浏览器w e b 应 用服务器，数据库服务器多层结构等多种应用体系结构，能满足i n t e r n e t i n t r a n e t 环境下的各种应用要求。 神舟o s c a r 所提供的数据查询语言s q l ，符合s q l 9 2 入门级标准，并部 分支持s q l9 9 标准。 神舟o s c a r 实现了可扩展的逻辑和物理双层存储结构管理，因此具有管理 海量数据存储的能力。神舟o s c a r 支持的数据库最大容量达到t b 级别，支持 的单表最大容量也达到t b 级别，同时支持的单个大对象的最大容量达到4 g b ， 并实现了对数据库内表数目的无限制和表中记录数目的无限制支持。 神舟o s c a r 实现完整的查询优化策略，支持高效的查询执行方案，具备稳 定高效的数据处理能力。同时支持大对象数据管理；支持图形、图像、声音、文 字、视频等多媒体数据管理；实现复杂对象数据和关系数据的统一管理；并支持 用户自定义数据类型和用户自定义操作方法的扩展，适于应用于工程数据领域。 神舟o s c a r 提供完备的日志和故障恢复机制，支持容错机制，通过实现数 据库及日志数据的完整备份、增量备份和联机备份，确保系统在出现系统崩溃、 服务器掉电、存储介质错误等各种软硬件故障的时候实现数据恢复。 1 1 1 1 0 s c a r 体系结构 o s c a r 数据库管理系统采用模块化的设计方法，分为管理工具、应用程序 接口、数据库内核三个主要的层次。 2 第1 章绪论 浙江人学硕士学位论立 管理工具提供备份恢复、性能优化、作业调度、数据转换、d b a 管理、交互 查询等多种工具。主要提供给数据库管理和操作人员，使他们能够通过图形化的 工具方便地管理o s c a r 系统。 应用程序接口部分主要提供给程序员使用。包括通用的o d b c ，j d b c 接口以 及嵌入式s q l 等。对于想基于o s c a r 数据库系统作数据库应用程序开发的程 序员，应用程序接口部分和其它数据库管理系统能够提供的一样完备。 在数据库内核部分，其上层包括数据字典、查询分析、查询优化、公共模块、 执行管理和命令管理几个部分；下层包括日志管理、索引管理、文件管理和事务 管理几个部分。其中和事务管理密切相关的有锁管理系统，事务相关的管理从根 本上来说正是通过锁来实现的。 整个o s c a r 系统的框架结构如图1 1 所示。 图表1 - 1 0 s c a r 系统框架结构 3 弟1 章绪论 浙江大学顺士学位论立 1 1 。2 事务、并发控制和调度器 1 1 2 1 事务和隔离级别 数据库管理系统( d b m s ) 由一个互相关联的数据的集合和一组用以访问这些 数据的程序组成，这个数据的集合被称为数据库，例如其中包含了某个企业的信 息。d b m s 的基本目标就是要提供一个可以方便地，有效地存取数据库信息的环 境。 数据库是一个共享资源，可以由多个用户使用。这些用户程序如果一个一个 地串行执行，则在每个时刻只有一个用户程序可以执行对数据库的存取：其它用 户程序必须等到这个用户程序结束以后才能对数据库存取。如果一个用户程序涉 及大量数据的输入，输出交换，则数据库系统的大部分时间将处于空闲状态。这 样就使得d b m s 的效用最小化了，也违背了最初开发d b m s 的初衷了。所以， 为了充分利用数据库资源，必须允许多个用户程序并发地存取数据库，来达到 d b m s 效用最大化。然而，此时产生了多个用户程序并发地存取同一个数据元 素的情况。若对并发执行不加以控制就会出现存取不正确的数据，破坏整个数据 库的完整性( 一致性) 。所以，d b m s 的事务及并发控制机制极其重要。 在数据库中，事务是一个十分重要的概念。从数据库用户的观点来看，事务 是构成单一逻辑工作单元的操作集合；从数据库的观点来看，事务是访问并可能 更新各种数据元素的一个程序执行单元，是并发控制的单位，是一个操作序列， 它是一个不可分割的工作单位。不论有无故障，数据库系统必须保证事务的正确 执行一一或者执行整个事务或者属于该事务的操作一个也不执行。此外，数据库 系统必须以一种能避免引入不一致性的方式来管理事务的并发执行，这个处理方 式正是通过并发控制机制来实现的。 为了保证数据完整性( 一致性) ，数据库系统必须保证以下所列的事务特性 ( a c i d ) ： 一 原子性。事务的所有操作在数据库中要么全部正确反映要么全部不反映。 一致性。事务的隔离执行要保证数据库的一致性。 隔离性。尽管多个事务可以并发执行，但系统必须保证对于任何事务， 它运行时感觉不到别的事务在并发地运行。例如当事务t 1 和t 2 ，在t 1 4 第1 章绪论 浙江大学硕士学位论文 看来，t 2 躐者在t 1 开始之前己缀停止执行，或者在t 1 宪成之麓才开 始执行。这样，每个事务都感觉不到系统申有其它事务在势发地执幸亍。 持久性。一个事务成功完成后，它对数据库的改变必须是永久的，即使 系统出现故障踺也必须徽裂这一点。 其中，确保单个事务的一致性怒对该事务编码的应用稷序员魄舞任，d b m s 的党整性约束提供的自动梭查给i 塞颈工作掇供了便利；保诚原子性耀数据库系统 本蹙的责任，具体采说，这颂工作痰事务蛰理部传处理；璇保拷久悭是数援痒系 统中恢复管理部件的责任；确保隔离性是数据库系统中并发控制部件的责任，事 务蠛赛链帮终确绦事务势发撬牙爱豹系绞浚态与这些事务按照菜耱凌痔个菝 一个地执行( 就是串行调度，详见1 1 2 2 ) 后的状态是等价的。 隔离毪会对一致经造成影确：如果死个事务并发执行，且它们的搡干筝阻我们 不希望出现的某种方式交叉执彳亍，将可能导致数据库的不一致。 事务串行执行阐然能保证一致饿以及鞴离性，假是考虑到效率问题，事务必 须并发执行。这就嚣要是势发控卷枧制来保证事务泌一致。陡和隔裹瞧。 确保事务并发执行后的系统状态与这螺事务按照某种次序一个接一个地执 行麓魏状态是等侩瓣，逮撵豹疆离缀剐是最窝懿隔离级嶷，胃事行洼隔离缀剐。 但怒基于数据库的成用并不一定都要求这么严格的隔离级别。比如，当要统计当 翦数据痒串表的菜个字段静总帮薅，可醴允许有一定的误麓。所阻，如果严格地 实行可串行性隔离级别的话，则会极大地牺牲并发性。所以，a n s i 标准为s q l 定义了4 个隔离级剐( 见表1 1 ) ，以满足不同应朋程序的各种隔离要求需臻 i 级别名称说明 1 0r e a du n c o m m i t t e d 允许读脏数据 h r e a dc o m m i t t e d读取琵提交麓数据 【2 r e p e a t a b l er e a d 可重复读 l 3s e r i a f i z a b l e可串行性 表穰l 一1 蹙离缎翘 不同的薅务隔离级别，需要采用不同的并发控制协议。以下主要讲述在 s e r i a l i z a b l e 隔离缀掰下豹势发控案褥谈，箕它隔离缀麓都簧鲍s e r i a l i z a b l e 这一 隔离级别的隔离性器低，黼且在实现方法上也是和藤者类似的。 5 第1 章绪论 浙江大学硕士学位论文 1 1 。2 2 串行调度和可串行化调度 当今大型商用d b m s 都用来处理大数据量的数据管理，而且在同一时刻会 有大量的用户并发地操作数据库。当数据库中有多个事务并发执行时，事务的隔 离性不一定能够保持。系统必须对并发事务之间的相互作用加以控制，这是通过 称为并发控制的各种机制来实现的。 为了研究各种调度算法，我们需要一种记法来描述事务中所有使数据在地址 空间之间移动的操作。有以下原语： r e a d ( x ，t ) ：将数据库元素x 拷贝到事务的局部变量t 中。更正确地 说，如果包含数据库员徐x 的块不在内存缓冲区中，则首先将包含x 的 磁盘块拷贝到内存缓冲区，接着将x 的值赋给局部变量t 。 w r i t e ( x ，t ) ：将局部变量t 的值拷贝到内存缓冲区中的数据库元素x 中。更正确地说，如果包含数据库元素x 的块不在内存缓冲区中，则首 先将包含数据库元素x 的磁盘块拷贝到内存缓冲区，接着将t 的值拷贝 到缓冲区中的x 。 这样，事务中影响事务调度的操作就可以用r e a d ( x ，t ) 和w rl t e ( x ，t ) 来 表达了。用r e a d 和w r i t e 表达的事务操作也叫做事务的重要操作。所有涉及 的事务调度都可以用这两个重要操作来表达。 调度是一个或多个事务的重要操作按时间排序的一个序列。因为数据库状态 必须保证一致性，所以，并发执行的一组事务的调度序列必须保证数据库状态的 一致性。 如果一个调度的动作组成首先是一个事务的所有动作，然后是另一个事务的 所有动作，依次类推，而没有动作的混合，那么我们称这一调度是串行的，这样 的调度就叫做串行调度。更精确地讲，如果有任意两个事务t 1 和t 2 ，若t 1 的 某个动作在t 2 的某个动作前，则t 1 的所有动作必在t 2 的所有动作之前，那么 该调度是串行的。 虽然，串行调度显然可以保持数据库状态的一致性和隔离性。但是，如果 d b m s 严格按照串行调度来实施，系统的并发性是极其低下的。当前，实用的 d b m s 都是按照可串行化调度来实旄的。- - j m 行化调度指的是：不管数据库初 试状态如何，对数据库状态的影响都和其所有可能出现的串行调度中的某个串行 6 第1 章绪论 浙江大学硕士学位论文 调度相同的调度。 在可串行性的基础上，还出现了两个条件更加严格的可串行性条件。一个是 冲突可串行性14 1 ，还有一个是视图可串行性【14 1 。其中就严格程度来说，冲突可 串行性大于视图可串行性，视图可串行性大于普通的可串行性。商用系统中的并 发控制机制通常保证冲突可串行性。 1 1 2 3 并发控制和调度器 即使各个事务能保持状态的正确性，而且也没有发生任何故障，并发事务之 间的互相影响还是可能导致数据库状态的不一致。因此，不同事务中各个步骤( 即 上述的重要操作) 的执行顺序必须以某种方式来进行规范。控制这些步骤的功能 就是由d b m s 的调度器部件实现的，而保证并发执行的事务能保持一致性的整 个机制称为并发控制机制。调度器的作用如图1 2 所示。 缓冲区 事务管理器 上 调度器 读，写请求 读和写 图表1 2 调度器示意图 当事务请求对数据库中的元素进行读写时，这些请求被传递给调度器。在大 多数情况下，调度器将直接允许执行读写操作。( 当然了，如果所需数据库元素 不在缓冲区中就首先调用缓冲区管理器) 。但是在某些情况下，立即执行请求是 不安全的。调度器必须推迟请求的执行；有的并发控制机制中，调度器甚至可能 回滚发出该请求的事务。 数据库系统中用于实现调度器的常用机制有以下几种： 基于锁的调度器 基于锁的调度器是确保可串行性最常用的调度器，这种调度器就是在访问数 7 第 章绪谂 辨锺失掌硬举斑论文 据库元素豁，先在元豢上维护“锁”，以防止菲可审行化奇勺杼为。童观地说，事 务获褥凌它所访瓣故数撼瘴元素上瓣镁，戳臻止其它事务曩警在瓣释瓣谤潞这 些元素并潮而引入非可串行性的可能。 最镄馨瓣拦述霹以为：当一个攀务要访闺某令数握元素翼尊，嚣宠对其擦麓零孛 模蕊静镂，然蓐才粪谚阂该数据元素。毙熟事务下l ；l 圣数援元素a 艇了菜耱模式 赘谈，楚辩事务琵磁褥簧诱超a 辩，砭稔铡戮澄蠢其京事务( t 1 ) 对箕搬铰 了，并且融烃加上的锁的模式与自融强加的模式不相容( 冲突) ，则必须等待t 1 释簸该锬滋蜃，耋己成臻获取a 数镀后，君能游阚该数蠢嚣豢。要详罨熬内容 见第二章。 基予时间戳剃的调度糕 对于系绞孛每个攀务下，挺一个唯一鹣霹鬻毅鹈宅联系越来，劳显记蒙最居 读和写每个数据库茹索的攀务的时间戳。事务并发执行时，撤据事务之间的时间 戳戳及数掇疼元素瓣读譬嚣趣戳滚拣铡诱发，戳德证按照攀务鹣辩阕戳瓣痔豹 辜行谖瘦簿蹬予事务貔实鬻谖度。 为了镁糯薅窝戳寐搀为并发控涮方式，谲澄器需要斌缭每个事务一个维一的 数假( 即时间戳) 。时间戳必须在事努首次通知调艘器自己将开始聪棱丹序发堪。 产囊对鞠戮骞两耱方法，一耱是襞嗣系统辩镑，运蠢一耱是傻藤诗数器。不繁使 用什么对蝴戳产生方法，调度器都必须维护当懿勰劝事务及冀辩阉戳戆一搬表。 同时，需舞将每个数据库元索与两个时间戳以及个附加的位联系起来，谜两个 露麓戳分秘兔读褒a 翁搴务中最褒靛辩麓戮 。 关键字的长度。 蹬荣表豹撩长。 关键字的分布情况( 均匀性和随机性) 。 记录的查找频率。 3 。2 。3 处理冲突的方法 因为晗希方法中的冲突不能避免，只能尽可能豫减少。所以，如何处瑗冲突 是喻希方法的不可缺少的一个重要方厦。 假设哈希表的地址集合为【o ，n 一1 】，冲突是指由关键字得到的嗡希地址为j ( 0 j n 一1 ) 姻位置上己存鸯谗录，粼“处理洚突”羧是戈该关键字戆记录拨瑙要 个“空“的哈希地址。通常用的处理冲突的方法有下列几种： 3 2 3 1 开方定址法 h i = ( h ( k e y ) + d i ) m o dm ( 其中l = 1 ，2 ，k ( k m 一1 ) ) 其中：h ( k e y ) 黼希嚣数；m 为啥希表袭长；d i 为灌鳖序列，可有下翔三种 取法： d i 一1 ，2 ，3 ， ，m 卅，此法称为线骸探测再数列。 第3 章关键技术 浙江大学硕士学位论文 d i = 1 2 ，一1 2 ，2 2 ，一2 2 ，3 2 ，十铲，一k 2 ，( k m 艨) ，此法称为 二次探测掰数列。 d i 一伪随机数序列，此滋称为伪随机探测再散列。 3 2 3 2 苒哈希法 h i = r h i ( k e y ) c i = 1 ，2 ，k ) r h i 均楚不同懿黪希爨数，鼙在曩义谖产生圭| 煞皴磅突瓣计算舅一令蹬参函数 地址，直到冲突不褥发生。这种方法不易产生“聚熊“，假增加了计算的时间。 3 2 3 3 链地址法 将所有茨键字为同义词的记录存储在同一个线性链表中。假设菜哈希函数产 生豹猞希戆缝在嚣阕猃，m 一 】上，帮设立一个猎铮嫠向量c h a i nc h a i n h a s h 印五 其每个向量的初始状态都悬空指针。凡哈希地址为k 的记录都插入到头指针为 c h i n a h a s h k 的镳表中。在链表中的插入位置可以在表头或表尾，也可以在中 间，以保持同义词在愿一个线性链袭中按关键字寄廖，这种有序的线性链表骞助 于在冲突链中的查找效率。这个方法是用于处理峙希表中冲突现象最常用的方 法。 3 。2 。3 。4 公共滋爨区 这也是处理冷突懿一秘方法。骰设哙攀悉数产囊靛啥蘑遮蛙必f o ，m - 1 ，嶷 设向量h a s h t a b l e 0 m 一1 1 为基本表，每个向量存放一个记录，另设立向量 o v e r t a b l e 0 一叼秀滋密表。j 舞有关键字移鏊本表串笑键字兔同义谲豹记录，不管 它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。 3 2 。4 其它类型的哈希寝 以上讲述的都怒静态哈希表，它们的桶数是固定的。假如啥希表中存放的记 录数目在哈希表的嫩命周期内变化范围极大，则使用静态蜍希表就不太合邋了。 辩3 帮关键披术 浙江 学顺士学位论文 因为如果一开始就设置极大桶长的静态晗希表，剡对于内存资源来说，是较大的 浪费：如鬃使用桶长较小鲍游态哈希表，则随着记缳的不断插入， 申突概率姆变 得极大。所以，必须采用种动态哈希表投术。初始化哈希表时设耀桶长为较小 毂馕，夔饕记录豹不叛捶入，冲突概率不翳溪大，鼗黠动态缝增热哈簿表熬蟪长 来降低冲突概率。于是，在静态哈希表的基础上提出了可扩展哈希寝和线+ 陡哈希 表逡两耱动态晗希嶷菠本。 3 2 。4 。 蜀扩展哈希表( e x t e n d i b l eh a s h i n g ) 在燕擎静静态狯希表缭稳上溪嬲： 1 ) 为桶引入一个间接层，即用一个指向块的搬针数组来表示桶，而不是用 数箍块本囊组戒的数缀来表示稀。 2 ) 指针数组( 即桶) 能增长，它的长度总是2 的幂，因而数缎每增长一次， 桶的数目就翻倍。 当啥希表嚣要被扩充踺，可扩惩晗薏表通过撵鸵分裂求实现。霹扩展哈希表 尽锗由桶地址表带来了额外的空间开销，但该表相对于整个哈希袭来说往往极 小，菠戳，这个空阁嚣锩凌裁可强忽疆不诗了。 3 2 。4 。2 线性啥藜表( 1 i n e a rh a s h i n g ) 虽然胃扩震跨蘩表宥众多霞燕，毽是巍有一些簌焘： 1 ) 当桶数组需要翻倍时，要做大量的工作。这些工作会使得某些插入看来 需耗费很长的对间。 2 ) 当桶数连续翻倍后，使褥容纳桶数组本身的空间变褥极大。 3 ) 有可能使得桶数翻倍的时间比逻辑上讲需瑟翻倍的时间提前许多。 予是，又提出了一秽嘲傲线性滁零表戆动态啥棼技拳。这静技寒数霹缝豢 来熙多的溢出链表为代价，避免了与可扩展哈希袭相关联的额外的庞大的桶数 缝。运释授寒是有警狳希寝实际骞缝懿记添鼗器鸯橇数霜豹毙篷夫予菜个润擅 时，才使得哈希表的桶数目自增一，这样一来，使得桶数目增长的更加平滑，并 置穗使得捅数茸秘倍豹对阍眈可扩瞩冶希表推迟了狠多。 第3 章关键技术 浙疆大学硕士学位论文 3 2 4 3 动态哈希表的性能优势 动态哈希表与静态哈希表技术相比，主腰的空间节省魁不必为讲来的记录数 嚣增长保磐捅，焉慧德鼓分配是动态匏。动态啥零麴一个袋轰在予粪我涉及一个 附加的间接层，因为系统农访问桶本身之前必须先访问桶地址表。但是，对于整 个动态晗希表中众多的实繇记录稳魄，这一额井的空闯及稻应豹谤润对性筑只是 一个极小的影响。尽管静态哈希结构可以没有这一额外的间接层，但当它变满后 就失去了这个微小的性能优势。此外，对予动态哈希表来说，由于每次分裂时重 组操作仅馋用于一个桶上，困恧所繁来的开销也比较低。 3 。3 死锁 如果存在一个事务集，该集合中静每个事务鸯等待该事务集中躲男一个事 务，那么我们说系统处于死锁状态。更确切地说，襻在一个等待事务集 丁0 ，t 1 ， 1 2 ，t n ，其审秘正等德被t l 镂隹懿数摆元素，t 1 聂等德被琵镂黢靛数 据元素。，t n 一1 正等待t n 锁往的数据元素，且t n 又磁等待被t 0 锁健的数 据元素。这耪情琵下，没有一个事务麓取褥送震，楚于死镄狡态了。随着今后系 统贾倾向于异步并行操作、更倾向于资源分配动态化、更倾向于分布式处理，死 锁处理必然越加成为d b m s 必须娶考虑的核心问题之一。 发生死锁时，系统唯一的补救攒施是采取激烈的动 乍，如回滚綮些陷入死锁 状态的事务。事务有可能只需要部分回滚，即事务回滚到得到锁的那一点之前， 嚣释藏该镂藏可爨瓣决瑟镂。 3 3 。1 产生死镂憋条律 c o f f m a n 等撂礁产生繇锬戆下裂霆令爨爨条移： 1 ) 进糨要求相斥的资源控制( 相互排斥条件，m u t u a le x c l u s i o nc o n d i t i o n ) 。 2 ) 送襁持有嚣分配给它稍酶资源，辩等待舅矫资源( 等待条件，w a i tf o r c o n d i t i o n ) 。 3 ) 持有资源的进程不允许其摄源在使用到完成释放之前移刘另外进程( 不 捻蠢条件，n op m e m p t i o n c o n d i t i o n ) 。 一 2 8 第3 章关键技术浙江大学硕士学位论文 4 ) 存在一个进程的循环链其中每个进程持有一个或多个链中的其它进程 要求的资源( 循环等待条件，c i r c u l a r w a i tc o n d i t i o n ) 。 3 3 2 尽量减少死锁的方法 数据库应用程序员在编程中应注意事务中s q l 语句的组织形式，否则极易 增加多用户访问同一数据元素的冲突概率，进而增加发生死锁的概率，降低系统 效率。为了尽量减少死锁的发生，一般需注意以下几点： 1 ) 不要在事务内使用数据定义语言( d d l ) 的语句，知c r e a t et a b l e ；c r e a t e i n d e x 等；也不要使用所有的d r o p 命令以及a l t e rd a t a b a s e 、 t r u n c a t et a b l e 等命令；某些系统过程也最好不要在事务内部使用。 2 ) 一个事务内不要写太多的s q l 语句，这不但增加发生死锁的概率，而且 可能引起长时间的回滚，降低系统的性能。 3 ) 合理安排表的访问顺序。 合理安排表访问顺序包括两方面的意义，是在各事务中对表尽量用同 - - j l l 页序进行访问，防止死锁；二是在同一事务中，对关键表的访问尽量放在 事务快结束时进行，减少对此关键表的锁定时间，从而减少锁冲突的机率。 4 ) 在事务中尽量避免用户交互。 因为在一个事务中，没有用户交互的批处理的速度极快。若一个事务中 需要等待用户输入或与用户交互，这个事务的处理时间将大增，这必然会影 响其它事务的处理，也就极可能速成死锁了。 5 ) 使用尽可能低的隔离性级别。 如果能够满足应用需要的话，尽可能使用较低的隔离性级别。隔离性级 别是指为保证数据库数据的完整性和一致性丽使多用户事务相互隔离的程 度。如果选择过高的隔离性级别，如可串行性隔离级别，虽然系统可以因实 现更好隔离性而更大程度上保证数据的完整性和一致性，但各事务间发生冲 突而死锁的机会大大增加，反而大大的影响了系统性能。 6 ) 使用b o u n dc o n n e c t i o n s 。 b o u n d c o n n e c t i o n 允许两个或多个事务连接共享数据元素和锁，而且任 何一个事务连接要申请锁，就如同另外一个事务要申请锁，因此可以允许这 第3 章关键技术浙江大学硕士学位论文 些事务共享数据而不会有加锁的冲突。 7 ) 将多阶段提交事务改为多个单一事务。 比如系统在发售地区中心中其它车站的客票申请客票席位时，分别要在 地区中心和车站两个服务器上完成各自的任务，是一个多阶段提交的事务。 一般而言，对地区中心的操作相对较慢，这样势必造成地区中心的席位表加 锁时间过长而影响交易性能。 通过把多阶段提交事务分解成多个单一事务的方法，减少了锁的冲突概 率。注意：此处增加了数据不一致性问题的解决困难，但是系统可以通过对 两阶段提交事务中第一个事务进行补偿处理的办法，来解决该问题。 8 ) 采用脏读技术。 脏读由于不对被访问的表加锁，而避免了锁冲突。事实上在客户服务器 应用环境中，有些事务往往不允许读脏的数据，但在特定的条件下，我们可 以用脏读。一般情况下，粗略统计应使用脏读，精确统计不应该用脏读，而 且当访问那些绝对不会被其它用户同时修改的记录时也可以使用脏读。 9 ) 数据访问时域离散法。 数据访问时域离散法是指在客户服务器结构中，采取各种控制手段控 制对数据库或数据库中的元素访问时间段。可以通过以下方式实现： 合理安排后台事务的执行时间。 比如采用工作流对后台事务进行统一管理。工作流在管理任务时，一方 面限制同一类任务的线索数( 往往限制为1 个，以防止资源过多地占用) ；另 一方面合理安排不同任务执行时序、时间，尽量避免多个后台任务同时执行； 还有，避免在前台交易高峰时间运行后台任务。 1 0 ) 数据存储空间离散法。 数据存储空间离散法是指采取各种手段，将逻辑上在一个表中的数据分 散到若干离散的空间上去，以便改善对表的访问性能。比如可以采用： 将大表按行或列分解为若干小表 将访问频繁的大表按照插入时间或者空间分为若干个小表，降低发生冲 突访问的可能性。 按不同的用户群体分解为若干小表 辩3 章美键技术 辑汪走学琰士学位论文 终访翊频繁豹大表按照搡传她袋翡曩户群分类分藏若予令小表，降 氐发 生冲突访问的可能性。 减，l 、填充霞子 减小填充因子，可以减少数据表中一页w 存储的记录数翻。极限情况下， 每页可l 鬟只脊一个记录。餐怒对于大表由于填充因子太拳造成浪费大量存麓 空间时，此法就不太合适了。 建立聚族索弓l 在需要大量捶入豹页不霭要更巍浆表上建立聚旗索引，改善搔入性能。 因为插入时，由于聚族索引的作用将插入的记录分散到各个不同的页面中。 翟袭实嚣佼翔辩还怒嚣要考懑到聚羧索孳l 怼袭懿受嚣影穗。 11 ) 优化事务处理速度。 优铯事务处理邃度磊，攀务楚理速度翻狭，宠藏辩闻缭矮，事务并发可 能蚀降低，因而不易导致过多的死锁。 3 3 。3 死锁的解法 尽管有以上种种减少死锁发生的方法，如果不采取避一步其它的措施，死锁 还是不可能完全避免的。 处理死锁的方法大致分为弱类，一炎搜月死锁预防( d e a d l o c k p r e v e n t i o n ) 协议保证系统永不进入死锁状态；还有一类是允许系统进入死锁状态，然后试蓿 麓死镁检测( d e a d l o c kd e t e c t i o n ) 窝瑟镂滚复( d e a d l o c kr e c o v e r y ) 壤隶l 送行 处理。两种方法都会引起事务回滚。如果系统谶入死锁状态的概率相对较高，则 遂鬻谴糟死铰琰防橇隶l ；否嗣，使雳死锾检测和死锾恢笈梳翩会更有效。 3 3 。3 死锁预防( d e a d l o c kp r e v e n t i o n ) h a v e n d e r 穰旱鞋箭就得出结论：辩架否定产生瑟镁的西个必需条件中静任 个，死锁就不可能再出现了。他建议下列避免死锁的策略： 每一个进程须一次性地鬟求它所需要的资源，如不能满足就不能进行。 若一个持有某些资源的遴程，遴步要求剽约资源豹请求被否定时，该 第3 章关键技术 浙江大学硕士学位论文 进程必须释放它原先已占有的所有资源：如果必需，与另外资源一起再 次要求它们。 将所有进程要求的资源类型排成一个线性次序，若一个进程已分配了一 个给定类型的资源，以后它可以要求的仅是排在这一给定类型之后的资 源。 值得注意的是，上面提出的是三个而不是四个策略。它们分别对应否定产生 死锁发生的必要条件中的( 2 ) 、( 3 ) 、( 4 ) 。因为我们必须允许专用型资源，不能否 定相互排斥这个锁的根本特性。 在具体实施时，死锁预防有两种方法。第一种方法，通过对加锁请求进行排 序或要求同时获得所有的锁来保证不会发生循环等待；另一种方法比较接近死锁 恢复，每当等待有可能导致死锁时，进行事务回滚而不是等待加锁。 如果一个死锁出现的必需条件已经在位，我们可以在资源分配时小心从事， 避免死锁仍是可能的。它的目标是比死锁预防附加较弱的限制条件，企图获得较 好的资源利用。避免不是以系统移去所有死锁可能性为前提，避免方法是允许死 锁可能性陷现，但每当死锁逼近时小心回避。其中著名的死锁避免算法有 d i j k s t r a 的银行家( b a n k e r ) 【2 6 1 算法和下面要讲述的时间戮死锁避免算法。 3 3 3 1 1 时间戳死锁避免 将每个事务与一个时间戳关联起来。该时间戳： 只用于死锁检测；它与本文前述的用于并发控制的时间戳不同。 特别地，用于并发控制的时间戳，如果事务回滚，那么它会以一个新的， 较晚的并发时间戳重新开始，但其用于死锁检测的时间戳从不改变。 时间戳在事务t 必须等待另一个事务u 持有的锁时使用。根据是t 还是u 更老一些( 时间戳更早) ，可能发生两种不同的情况。这两种策略管理事务调度 的方法不同。 1 ) 等待- 死亡方案( w a i t - d i e ，非抢占技术) ： ( a ) 如果t 比u 老( 即t 的时间戳比u 的时间戳小) ，那么允许t 等待u 持有的锁。 ( b ) 如果u 比t 老，那么t “死亡”：t 将回滚。 第3 章关键技术 浙江大学倾上学位论文 2 ) 伤害等待方案( w o u n d w a i t ，抢占技术) ： ( a ) 如果t 比u 老，它将“伤害”u ：u 必须回滚并放弃t 需要从u 得到的所有锁。一个例外是在“伤害”生效前u 已经完成事务 操作并释放自己的锁。在这种情况下，u 得以存活并且不需要回 滚。 ( b ) 如果u 比t 老，那么t 等待u 持有的锁。 在采用基于时间戳的死锁避免的作用下，事务的等待图中其实不可能发生 环，因而不存在死锁。假设不是这样：即存在一个环，例如t 1 一t 2 一t 3 一t 1 。 有一个事务最老，假设是t 2 。在等待一死亡方案中只会等待比较新的事务，因 此，t 1 不可能等待比较老的事务t 2 ；在伤害一等待方案中只会等待比较老的事 务，因此，t 2 不可能等待比较新的事务t 3 。所以，可以断定死锁环不可能存在， 因此死锁被避免了。 - 3 3 3 2 基于超时的机制 另一种处理死锁的简单方法基于锁超时( 1 0 c kt i m e o u t ) 。这种方法中，申请 锁的事务至多等待一个给定的时间。若在此期间内锁未被授予该事务，则该事务 超时，此时该事务自己回滚并重启。如果确实存在死锁，卷入死锁的一个或多个 事务将超时并回滚，以允许其它事务继续。该机制介于死锁预防( 不会发生死锁) 与死锁检测及恢复之间。 超时机制的实现极其容易，并且如果事务是短事务或长时间等待很可能由死 锁引起时该机制运作良好。但是，一般而言很难确定一个事务超时之前应等待多 长时间。如果已发生死锁，等待时间太长导致不必要的延迟。如果等待时间太短， 即便没有死锁，也可能引起事务回滚，造成资源浪费。该机制也可能会发生饿死 ( 也叫活锁) 。故此，基于超时的机制应用不多。 第3 章兼键技术 浙江大学硕士学位论文 3 3 3 3 死锁检测和恢复 3 3 3 3 1 死锁检测 如果系统没有采用能保证不产生死锁的协议，则死锁就不可能避免，那么系 统必须采用死锁检测与恢复机制。检查系统状态的算法周期性地被激活，以判断 有无死锁发生。如果发生死锁，则系统必须试着从死锁中恢复。为实现这一点， 系统必须做到以下几点： 维护当前分配给事务的数据元素的有关信息以及所有尚未解决的数据元 素加锁请求信息。 提供一个使用这些信息判断系统是否进入了死锁状态的算法。 如果检测算法判定存在死锁，则从死锁中恢复。 尽管死锁检测与恢复机制带来了各种开销，它不仅包括在运行时维护必要信 息及执行检测算法的代价，而且包括从死锁中恢复所固有的潜在损失。但是，用 这些小的代价和系统处于死锁状态停止不前相比，还是很值得的。 死锁检测算法的目标是确定死锁是否出现和死锁所牵涉到的进程和资源。通 常死锁检测算法使用在必定可能出现死锁的系统中，因丽检测算法通常就只是用 来确定“循环等待现象”是否存在。 图表3 1 w f g 图( 含死锁环) 为有助于死锁的检测，通常用图形来指出资源的分配和要求。如在一个有向 图中方框表示进程，大图表示等同的资源类型，在大圆内碗的小圆指出每类等同 资源的实例。图3 - 1 说明一个小的死锁系统。r 1 类型2 个资源都已分配进程p 1 ， 3 4 第3 章关键技术 浙江大学硕士学位论文 进程p 1 迸一步要求r 2 类型资源，r 2 类型1 个资源已分配给进程p 2 ，p 2 又要 求r 3 类资源，它已分给进程p 3 ，p 3 又要求r 1 类型资源。这是一个明显的循 环等待的例子。在检测系统是否死锁时可以对图作简化。如果可以允诺一个进程 的资源要求，那我们说图可以被那个进程简化。简化就是从图上把那个进程的输 入输出线移走。若一个图能被它的所有进程简化，系统就不存在死锁。若不能全 被简化，那些不能再被简化的进程就构成死锁的进程集。 3 3 3 。3 2 典型的死锁检测方法 等待图( w a i t s - f o rg r a p h ，简称w f g ) 模型常用于数据库系统和操作系统 的死锁检测。一个系统的w f g 是一个简单有向图w f g = ( v ，e ) ，其中v 是这 个系统的事务( 进程) 的集合，e 是边的集合，对于任意v 1 ，v 2e v ，( v l ，v 2 ) e 当且仅当事务( 进程) v l 等待事务( 进程) v 2 释放v 1 所需要的资源。一个系统存在 死锁当且仅当它的w f g 至少包含一条回路。这样，系统的死锁检测问题就等同 于在简单有向图中寻找回路的问题了。 3 3 3 3 3 死锁的恢复 死锁的恢复方法用来从系统中清除死锁，使系统能继续运行。大部分系统从 死锁中恢复是通过冲刷一个或多个死锁的事务( 即从上面检测的死锁事务集中选 出) ，释放出它们占有的资源，而使其它事务能够继续操作直到完成。通常被冲 刷掉的事务重新从起点开始，失去原来它们已完成的工作但这总比让死锁留在 系统中相对来说是一种很小的代价。 为了使系统从死锁中得以恢复，应该移去哪个或哪些事务呢? 显然移去的事 务应是死锁的事务。首先我们说明什么是死锁的个解法。死锁的一个解法是死 锁的事务之一个最小子集，将这子集中的事务回滚，系统就能从死锁中得以恢复， 即死锁得解。同时应该指出，当死锁出现时总是存在着多个解法。如当有4 个事 务t 1 、t 2 ，t 3 、t 4 落入死锁环( 用检测算法检测得到) 。用某个方法确认同时废 弃t 1 和t 2 死锁就可解。若只废弃t 1 或t 2 死锁不可解，于是f r l ，t 2 ) 是死锁 的一个解。若除了废弃f r l ，t 2 # f 再废弃t 3 ，显然死锁也可解，但这个解明显 第3 章关键技术 浙大学硕士学位论文 已经不是最小解了。 总而言之，当死锁检测算法判定存在死锁时，系统必须从死锁中恢复。解除 死锁最通常的做法是回滚一个至多个事务。需采取的行动如下： 1 ) 选择牺牲者。给定处于死锁状态的事务集，为解除死锁，必须决定回滚 哪一个或哪一些事务以打破死锁。我们应使事务回滚带来的代价最小。 “最小代价”这个词并不准确。很多因素影响事务回滚代价，其中包括： a ) 事务已计算了多久，在完成其指定任务之前该事务还将计算多久时 间。 b ) 该事务已使用了多少数据元素。 c ) 为完成事务还需使用多少数据元素。 d ) 回滚时将牵涉多少事务接连回滚等等。 2 ) 回滚。一旦决定了要回滚哪个事务，就必须