（计算机应用技术专业论文）分布式数据库资源高可用性的研究.pdf

河海凡学坝1 论正 摘要 摘要 随着分布式数据库系统在业务领域中日益广泛的应用，提供高可用性的服务 也就越来越重要。数据库资源高可用性是指，尽可能地保证数据服务的正常运行， 并在数据服务出现故障时，由备用数据源在极短的时间内继续提供服务，转换过 程相对用户是透明的。 并发控制领域的死锁是分布式系统所要解决的一个重要问题，也是导致数据 库资源不可用的一个重要因素。现有的分布式数据库通常采用加锁实现并发控 制，通过撤销事务来打破死锁环路，但是仍然存在基于多粒度锁模式下的粒度转 换引起的死锁可能性。 在本文提出的基于日志的高可用模型设计中，包括有数据通信层、数据源配 置层、监视层、数据库状态控制层、命令转换层、目志层等多个模块结构。本文 的对日志层进行了研究，包括异构数据库环境下的日志类型、日志格式、日志空 间、f t 志同步和日志恢复等问题。 基于数据冗余的日志恢复机制是实现分布式数据库系统资源高可用性的重 要方式。系统中的所有共享数据资源，将根据用户的需求存在一个或多个副本， 并且由系统自动保证这些副本的一致性。当系统中某个数据源出现故障后，对该 数据源的访问将自动转移到作为副本的备用数据源。当故障数据源恢复服务后， 日志系统将恢复其故障期间未完成的操作，以保证数据的致性。因此，当系统 中一个或几个节点的失效，不会影响系统的正常服务。而当系统正常运行时，日 志系统通过l s n 包动维护日志记录的一致性。 【关键词】分布式数据库，高可用，并发控制，死锁，日志恢复 a b s t r a c t a b s t r a c t w i t ht h ep o p u l a ra p p l i c a t i o no fd i s t r i b u t e dd a t a b a s es y s t e m si nb u s i n e s s s e c t i o n s ， p r o v i d i n g t h e h i g ha v a i l a b i l i t y ( h a ) s e r v i c e b e c a m e v e r yi m p o r t a n t d a t a b a s e r e s o u r c e sh ac o u l db ed e f i n e dt h a tam a i nd a t ar e s o u r c ep r o v i d ed u r a t i v es e r v i c ea n d a b a c k u pd a t ar e s o u r c ec o u l dt a k eo v e ra l lt a s k sa n ds e r v i c e si nas h o r tt i m ew h e nt h e m a i nr e s o u r c ef a i l e d t h e r e f o r e ，t h ee n t i r es y s t e mm a ys t i l lb ea v a i l a b l ea n du s e r s w o u l dn o tb ea w a r e o f s w i t c h i n g o f n o d e s d e a d l o c ki nc o n c u r r e n c yc o n t r o lw a sa ni m p o r t a n tp r o b l e mw h i c hs h o u l db e r e s o l v e db yd i s t r i b u t e ds y s t e m s ，m o r e o v e gi tw a sa l s oa ni m p o r t a n tf a c t o ro f c a u s i n g u n a v a i l a b i l i t y d i s t r i b u t e d d a t a b a s e si ne x i s t e n c e u s u a l l ya d o p t l o c km o d et o i m p l e m e n tc o n c u r r e n c yc o n t r o l ，i n v i ao fc a n c e l i n gt r a n s a c t i o nt ob r e a kt h r o u g h d e a d l o c k l o o p h o w e v e r , s o m e k i n do fd e a d l o c k m a ys t i l la p p e a rd u e t o t h e g r a n u l a r i t ys w i t c hb a s e d o n m u l t i g r a r t u l a r i t ym o d e i nt h eh am o d ed e s i g n ，i n c l u d i n gd a t ac o m m u n i c a t i o n sl a y e r , d a t er e s o u r c e c o n f i g u r el a y e r ，s c o u tl a y e r ，d a t a b a s es t a t ec o n t r o ll a y e r , c o m m a n ds w i t c hl a y e r , l o gl a y e r , e r e i nt h i sd i s s e r t a t i o n ，i tf o c u s e so n t h er e s e a r c ho f l o gs t y l e ，l o gf o r m a t ， l o gs p a c e ，l o gs y n c h r o n i z a t i o na n dl o gr e c o v e r yi nh e t e r o g e n e o u sd a t a b a s es y s t e m t h el o gr e c o v e r ym e c h a n i s m sb a s e do nd a t ar e d u n d a n ti sai m p o r t a n tq u o m o d o t oi m p l e m e n td i s t r i b u t e dd a t a b a s er e s o u r c e sh a i ns u c ha s y s t e m a l lo fs h a r ed a t a r e s o u r c e sw i l lb u i l do n eo rm o r ed u p l i c a t e sa c c o r d i n gt ou s e r sn e e d l o gc o u l db e u s e dt om a i n t a i nc o n s i s t e n c ya m o n g d u p l i c a t e s s o ，l o gb e c a m et h em o s tp o p u l a r a n d r e l i a b l et e c h n i q u et om a i n t a i ns y s t e m h i g ha v a i l a b i l i t y 【k e y w o r d s 】d i s t r i b u t e dd a t a b a s e ，h i 【曲a v a i l a b i l i t y , c o n c u r r e n c yc o n t r o l ， d e a d l o c k ，l o gr e c o v e r y i i 河海大学硕 论文第一章绪论 1 1 研究意义与目的 第一章绪论 随着电子业务在世界范围内的迅猛发展，提供2 4 7 不间断服务的高可用性 已成为大多数计算机系统的一个必需特性。包括在线交易处理系统、电子商务、 i n t e r n e t w w w 、数据仓库、决策支持、电信交换、在线分析处理系统( o n l i n e a n a l y t i c a lp r o c e s s i n g ) 、控制系统等等。这些系统的服务器需要连续地向客户提 供服务，因此高可用性也就成为必需，在这种要求下，任何服务的中断都可能是 致命的，并将以诸多形式表现，比如丧失机会、信誉受损或失去客户等等。随着 各企业、组织对关键系统应用的要求极度地增加，特殊的用于保护系统服务正常 的h a 系统的购置总成本( t o t a lc o s to w n e r s h i p ) 一般会小于意外情况所带来的 损失。 高可用系统的研究目前主要集中在两个方向，即网络资源的高可用和数据库 资源的高可用。数据库资源的高可用性在整个系统高可用中占有极其重要的地 位，对于一般的事务庇务关键( b u s i n e s s m i s s i o nc r i t i c a l ) 应用而言，绝大多数 是基于数据库的，繁重的任务需要往往会导致不可预见的问题出现。伴随着网络 技术的不断成熟，商业应用系统逐步发展为分布式体系结构，这种体系结构的底 层数据库最初采用的仍然是集中式数据库系统。为了提高数据本地访问能力，降 低网络通讯量，人们发现必须对应用的共享数据资源进行分布式管理，这就是分 布式数据库系统。因此，实现分布式数据库资源的高可用具有重要的现实意义。 我们研究的目的就是为了通过分布式数据库资源的高可用实现分布式系统 的高可用，最终满足2 4 x 7 不间断服务的需要。 1 2 研究现状 最初，高可用的研究基本是基于计算机群集系统的研究，群集系统的最初模 型分化为两个不同的领域即高性能( h p ) 和高可用( h a ) 。群集系统大体上可 以定义为：“互相连接的并行或分布的计算机集合，它们使用统一的计算资源。 并行计算机系统侧重群集系统的高性能以及延展方面的性能，一般被称作w s c s ( w o r k s t a t i o nc l u s t e r s ) 或n o w s ( n e t w o r ko fw o r k s t a t i o n s ) ，而事务任务关 键系统则侧重于群集系统的高可用性，即被称作h a 群集系统【2 j 。 目前，人们关注的焦点转移至基于分布式系统的商可用性研究。群集系统和 分布式系统有着许多明显的不同。群集计算机是典型的同质系统，其节点机具有 紧密耦合的特点，更为重要的是，节点之间相互信任( 分布系统必须处理那些不 河她大学坝七论文第一章绪论 被信任的h j 点) ，这使得自者的实现更容易一些。 正是由于分布式系统节点的运行环境各不相同、运行状态难以控制，因此也 就更容易出现各种意想不到的问题。正如l e s l i el a m p o r t ( 分布式系统的创始者 之一) 所说：“分布式系统中的错误使你根本不知道是什么原因造成计算机无法 正常使用。” 虽然高性能和高可用性的发展并非是同步的，但事实上，高性能并行计算机 和高可用性的发展可谓是相辅相呈的。并行处理是将多个处理单元整合以达到高 性能的目的，而只有具有一定的容错性才能形成有效的并行计算，这是因为容错 性使得应用程序运行的连续性得以保证；另外一方面，由于并行处理技术从本质 上提供给了高可用系统一种重要的因素即整体架构的冗余，因此高性能技术又促 进了高可用技术的发展p j 。 目前，各个数据库系统一般均包含有实现数据库离可用性的实现模块，如 m i c r o s o f fs q l s e r v e r2 0 0 0e n t e r p r i s ee d i t i o n 、i b md b 2 、o r a c l e9 i 等，但它们通 常要么是基于群集模块之上的，要么必须有特殊的功能集合予以支撑的，在跨平 台实现上均做的不尽如人意。而目前分布式系统中的数据库系统通常包含若干种 数据库系统，因此，分布式系统中的数据库资源的高可用性研究还有很长的路要 走【“。 1 , 3 研究内容 论文主要研究分布式数据库资源的高可用问题，经常导致数据库资源不可用 的原因主要包括并发事务导致的死锁和系统故障或人为因素造成的数据丢失，因 此，研究的具体内容为检测死锁和通过日志系统保障数据的完整性、一致性。 1 3 1 死锁检测 由于分布式数据库系统强大的事务处理能力和数据管理能力，越来越多的企 业采用分布式数据库系统实现企业管理数据化。随着企业规模的不断发展，分布 式数据库系统变得相当庞大，需要支持大量的并发事务处理。目前各种大型分布 式数据库系统在并发控制策略上普遍采用了加锁技术。由于大量用户频繁地、并 行地访问数据，对同一资源的操作冲突普遍存在，这就可能导致分布式死锁的产 生。如果系统中存在死锁而不能被及时检测到并加以解决，那么处于死锁的那些 事务将永远处于阻塞状态，应用将无法正常结束，甚至，随着死锁存在时间的延 长，将导致更多事务的阻塞，最终导致系统陷于瘫痪，这就产生了数据库资源的 不可用。因此及时检测出死锁对于保障分布式数据库资源高可用具有重要意义。 由于分布式死锁检测方法比集中式和层次式检测方法具有更高的灵活性和 # 6 勰人学顺i ：论文第一章绪论 有效性。我们嬲望在前人研究的基础上，继续深入对分布式死锁检测方法的研究。 目前，分布式死锁检测研究中的主要问题有：根据应用的不同需求，应用所发出 的资源请求方式不尽相同。现有的资源请求模型包括了：单一资源模型、a n d 模型、o r 模型、a n d o r 模型及k o u t - o f n 模型。针对不同的资源请求模型， 相应的死锁条件各有区别。尽管很多算法的作者指出研究的算法是应用于分布式 数据库系统的，但实际上是针对某种资源请求模型而提出的。我们有必要深入分 析分布式数据库系统特有的资源请求模型和死锁条件，提出具有代表性和通用性 的死锁检测算法。由于分布式数据库系统是由物理上分布于不同节点的数据库集 合而成的，不同节点之间通讯是通过发送消息的方式来实现的，为了提高死锁检 测算法的效率，我们需要尽量降低网络中的消息传送量。 为了提高算法整体性能，分布式死锁检测算法通常允许在多个节点上启动， 并行进行各自的死锁检测，如果处理不当，很可能造成同一个死锁被多次重复地 检测和解决，这就是所谓的“幻像死锁”。对幻象死锁的检测实际上是多余的， 这是我们需要避免的。现有的分布式死锁检测算法通常由于死锁解决处理不当， 造成后续检测中出现“假死锁”，这样的死锁实际上是不存在的，假死锁的最大 问题是将造成不必要的事务撤销。这也是我们需要解决的 5 1 。 1 3 2 数据库恢复机制 既然计算机操作系统和数据库系统都可能因为某些不可预测的软硬件因素 而失败，那么在失败恢复后保证数据库状态的一致性，是任何一个数据库管理系 统都应该具备的基本功能。在数据库管理系统中，这个任务由恢复管理系统承担。 当发生了一次使数据库状态不一致或者可能使数据库状态不致的失败后，恢复 管理机制负责将数据库恢复到致的状态。 事务- 足恢复处理的基本单元，恢复管理机制保证事务的永久性和原子性免受 不可知的失败对其的破坏。事务的其余两种特性一致性和隔离性则由并发控 制模块来维护。 当系统从失败中恢复以后，恢复管理机制必须保证：一个事务的所有执行结 果要么全部都永久记录在数据库中，要么全部都不作永久记录。由于数据库的写 操作不是一个原子过程，情况就显得复杂了。有可能一个事务己提交，但其相关 的执行结果尚未到达数据库，如果此时发生了失败，执行结果就不能永久的记录 在数据库中。 当事务执行一个对数据库的写操作是，数据首先写入数据库缓冲区。数据库 缓冲区在内存中占特定的区域，数据经此再回写n - - 级存储器。数据库缓冲区的 数据保存在易失性存储器中，都是临时的。只有当缓冲区的数据被回写到二级存 储器后，才能被视为永久的。数据由数据库缓冲区回写n - - 级存储器的操作可由 河姆入学颤j 一论文 第一章绪论 特定的d b m s 引发，或者在数据库缓冲区满时，由d b m s 自动执行。有时会将 所有的数据库缓冲区一次性全部导入二级存储器，称为强制写。当一个失败发生 在写数据库缓冲区或者由数据库缓冲区回写到二级存储器时，恢复管理机制必须 能够确认引起数据库写操作的事务此时所处的；状态。如果事务已经提交，为保证 数据库的一致性，需要通过读取日志文件让恢复管理机制对数据库执行一次r e d o 操作t 6 1 。 1 4 章节介绍 第一章：分析了分布式数据库系统资源高可用性研究的意义与目的以及本文 的主要研究内容： 第二章：对分布式数据库系统的组成结构和事务的a c i d 特性进行了分析， 并从数据分布和和数据分片两个层次研究了数据资源的组织方式； 第三章：为了满足高可用性的需要，讨论了分布式并发控制的几种方法和分 布式死锁的几种分析方法以及死锁检测与解决策略： 第四章：提出了基于日志的分布式数据库资源高可用模型的设计，对如何建 立主从数据源、如何建立统一的日志格式并利用其实现数据同步和数据恢复等高 可用技术进行了一定的探讨； 第五章：对本文研究工作进行总结，并提出了今后需要解决的问题和主要的 研究方向。 4 州薅人学硕一h 论文第二章分布式数据库系统的技术研究 第二章分布式数据库系统的技术研究 2 1 分布式数据库系统概述 分柿式数据库系1 ( d i s t r i b u t e dd a t a b a s es y s t e m ，简称d d b s ) 是数据库系统和 计算机网络相结合的产物。通俗地讲，就是物理上分散而逻辑上集中的数据库系 统。分布式数据库系统使用计算机网将地理位置分散而管理控制又需要不同程度 的集中的多个逻辑单位连接起来，共同组成一个统一的数据库系统。其组成结构 如图21 所示： 图2 1d d b s 组成结构图 ( g d d ：全局分布式数据库：l d d ：局部分布式数据库；g d b ：全局数据 库；l d b ：局部数据库：g d b m s ：全局数据库管理系统；l d b m s ：局部数据库 管理系统) 随着计算机应用需求的拓展和计算机硬件特别是网络技术的同趋成熟，分布 式数据库系统迅速发展起来。分布式数据库系统既能达到对数据的集中管理与共 享，又能使地域的分散性被系统隐蔽起来。可以把分布式数据库系统看成是“数 据库系统+ 计算机网络”，但它决不是将数据库技术和计算机网络技术的简单结 合，而是两种技术的互为渗透与融合。它要管理的不是单个数据库系统，丽是分 布在许多不同地域上的多个数据库系统。因此，分布式数据库系统的严格定义是： 分布式数掘库是一组数据库集，逻辑上它们属于同一系统，而物理上它们分散在 用计算机网络连接的多个场地上，并统一由个分布式数据库管理系统管理 淘人 帧l 论文 第一章 分布式数据库系统的技术研究 1 7 。 在分布式数据库系统中，被计算机网络联结的每个逻辑单位称为节点 f n o d e ) ，各节点在物理上分散在不同的地方，而逻辑上是一个整体，并由一个统 一的数据库管理系统进行管理，这个数据库管理系统称为分布式数据库管理系统 f d i s t r i b u t e dd a t a b a s em a n a g e m e n ts y s t e m ，简称d d b m s ) 。 分匆式数据库的分布特性对用户来说是透明的，不同的分布式数据库系统有 小| j _ i 的表现形式，根据分白式数据库系统建立的原则，可以将分布式数据库系统 分为两类：同构分布式数据库系统和异构分布式数据库系统。同构分布式数据库 类似于一个集中式数据库，只不过同构分布式数据库将数据存放在网络中分布的 不同节点内。而不是同一个节点。异构系统是另一类型的数据共享系统，它的特 点是在各节点上运行着不同的数据库管理系统怫】。 2 2 数据分布与数据分片 在分布式数据库系统中，数据的分片和分布是两个重要的概念。事实上，分 布式数据库大部分问题是由数据的分片与分布引起的。它对整个系统的可用性、 可靠性有极大的影响，同时也与分布式数据库系统的其他问题密切相关。 2 2 1 数据分布 数据分布( d a t a d i s t r i b u t i o n ) 是指分布式数据库中的数据不是存储在一个节 点的计算机存储设备上，而是根据需要将数据划分成逻辑片段，按某种策略将这 些片段分散地存储在各个节点上。 2 2 1 1 数据分布的目的 在构成分布式数据库系统的运行环境时，必须考虑构成分布式数据库系统所 应用的各个组成部分各自如何使用数据的问题，所以，分布式数据库系统同样存 在着分布式数据库d d b 的设计问题。它包括了分布式数据库的逻辑划分和物理 分配，以及用户对分布式数据库的划分或分配的感知程度( 透明度) 。 数据分布的主要目的是提高访问的局部性。即通过数据的合理分布，尽可能 地使更多的数据能够就地存放，以减少远距离的数据访问，但在任何分布式数据 库中，达到所有数据的访问都局部化是不可能的。即使多复本也只能达到读的完 全局部化，对于数据的更新则需要各个复本同步更新，因此仍然需要进行远程访 问。一个成功的分布式数据库的设计应使访问的局部性能更好。数据的分布的目 的是为了就地访问，而不是分布访问。 6 箱_ 二章分布j 数据库系统的技术研究 2 2 1 2 数据分布的策略 数据分布的策略有四种： 1 ) 集中式：所有数据片段存储在同一节点上。这种策略，数据的控制和管 理都比较容易，数据的一致性和完整性能够得到保证。但由于对数据的检索和修 改都必须通过这个节点，使其负担过重，系统对其依赖性过多。一旦出现访问瓶 颈或者尾软、硬件故障，将会使系统完全瘫痪，系统的可靠性、可用性得不到保 障。 2 ) 分割式：所有数据只有一份，它被分割成若干个逻辑片段，每个逻辑片 段被指派在某个特定的节点上。这种分配策略可充分利用各个节点上的存储设 备，数据的存储量大。在存放数据的各个节点上可自行检索和修改数据，发挥系 统的并发操作能力。同时，由于数据是分布在多节点上，当某些节点出现故障时， 系统仍可运行，提高了系统的可用性和可靠性。但对于全局查询和修改，所需时 间会比集中式长些，因为数据不在同一节点，节点之间需要进行通信。 3 ) 复制式：全局数据有多个副本，每个节点上都有一个完整的数据副本。 采用这种策略的系统可靠性高，响应速度快，数据的恢复也较容易，可从任一节 点得到数据副本。但系统的数据冗余量很大，代价高昂。 4 ) 混合式：全部数据被分为若干子集，每个子集安置在不同的节点上，但 任一节点都没有保存全部数据，根据数据的重要性决定各个子集的副本的多少。 这种分配策略，兼顾了分割式和复制式的做法，也获得了二者的优点，灵活性好， 效率高。但也具有相当的复杂性。 2 2 1 - 3 数据分布方案 对于关系的c o n c e p t u a ls c h e m a 的分布，在理论上要求每个处理节点s j 维持 一个d i r e c t o r y ( 1 庀作d ( d ) 用来描述系统中关系的分布及关系各副本的更新状态： 每个s i 上各t r a n s a c t i o n 对任一关系的访问都必须先访问d i r e c t o r y 。 当s i 上新生成( 进人) 一关系时，在d ( i ) 里作适当的登记，特别标明该关系在 本地s i 的副本为“新，然后向系统所有其它节点发送信息，通知这一情况。处 理节点s j 收到此信息后，在当前t r a n s a c t i o n 执行( 如果有的话) ，完成后即对d ( j ) 作适当登记，特别标明该关系在本地s j 的副本为“旧( 实际上此时s j 处尚无该 关系的一个副本) 并记下该关系当前新副本的所在地( 即s i ) 。 当s j 执行一个只读t r a n s a c t i o n 时，先查看所涉及的关系的本地副本是否为 “新”，如为为“新”则执行该仃a n s a c t i o m 否则访问新副本的驻在地s i ，如果 s i 处的写锁w l o c k i = l ，则在s i 的传送等待队列排队；否则将新副本传送到s j 。并 标s i 处的该副本为“新”，然后执行该t r a n s a c t i o n 。 “海人学顺i 。论文第二章分布式数据库系统的技术研究 当s i 执行一个写操作的t r a n s a c t i o n 时，如所涉关系的该处副本为“新”，则 执行垓t r a n s a c t i o n ，将写( 修改) 的结果暂存于一工作区( 0 里，在该t r a n s a c t i o n 执 行完成后将该内容写回本地副本里( 如果传送标志为1 ，则应等待传送完毕后 再写回) ，此时要先罱写锁标志w l o c k _ - 1 。修改完本地副本后通知其它节点当前 新副本在本地s j ( 其它节点将当前t r a n s a c t i o n 执行完后将有关的副本标为“旧”， 并记下当前新副本在s j ) ，然后释放写锁标志w l o c k j = 0 。如果有的话，执行传送 等待队列所有传送请求( 执行前置传送标志，完成后清除) 。 s i 执行一个含写t r a n s a c t i o n 时，如果所涉关系的本地副本为“旧”，则访问 新副本驻在地s i ，将该新副本从s i 传至s j 。执行此t r a n s a c t i o n ，将写( 修改) 的结 果暂存于工作区0 ) 里，下面的处理同上。下面我们给出算法的非确定性伪码描 述，其中每个节点的算法是相同的，构成分布式算法，为了说明简单，每个 t r a n s a c t i o n ( 简记t r a n s ) 只列出个关系吲。 s i t r e a d o n l y - t r a n s ( r x ) i fs t a t e ( s i r x ) = n e w e x e c u t e ( r e a d 旬n l y - t r a n s ( r x ) 1 e l s eb e g i n f i n d s j s u c ht h a t s t a t e ( s j - t l x ) = n e w ； g e t ( s j - r x ，s i ) ； e x e c u t e ( r e a d - - o n l y - t r a n s ( r x ) ) e n d p r o c e d u r eg e t ( s j - r x ，s i ) i f w l o c k j 2 1 w a i tu n t i lw l o c n 2 0 ： t r a n s f j = 1 ； t r a n s f e r s j h ，s i ) ； t r a n s 0 = o ： s t a t e ( s j r x l 2 n e w ； r e t u r n s i t w r i t e - t r a n s ( r x ) ： i fs t a t e ( s i - r x ) = n e w b e g i n 第二章分布式数据库系统的技术研究 e x e c u t e ( w r i t e - t r a n s ( r x ) ) ； p u tu p d a t e si nw ； i ft r a n s f i = 1 w a i tu n t i lt r a n s f i = o ； w l o c k i = l ： c o m m i ( w _ r x ) ； s e n d ( r e n e w , r x ) ； w l o c k i = o e n d e l s e b e g i n f i n ds js u c ht h a t s t a t e ( s j - r x ) = n e w ； g e t ( s j r x ，s i ) ； e x e c u t e ( w r i t e - t r a n s ( r x ) ) ； p u tu p d a t e s i nw ； i f t r a n s f i= 1 w a i tu n t i lt r a n s f i = 0 ： w l o c k i = 1 ； c o m m i t ( w , r x ) ； s e n d ( r e n e w , r x ) ； w l o c k i = 0 e n d s j ： r e c e i v e ( s e n d ( r e n e w , r x ) a n df i n i s h e d ( c u r r e n tt r a n s 、斗s t a t e ( s j - r x ) = o l d 2 2 2 数据分片 数据分片( d a t a f r a g m e n t a t i o n ) 也称数据分割，分布式数据库的各个局部数 据库是由全局数据库的某种逻辑分割而得。在分布式数据库系统中，由于不同节 点的用户只关心某些数据，因此从应用出发，需要将数据按照逻辑相关性进行分 割，并将分割后的各部分元组成为逻辑片段( f r a g m e n t a t i o n ) ，存放在相应的节 点上。 9 第- 二帚分布式数据库系统的技术研咒 2 2 2 1 数据分片的基本方法 数据分片有以下四种基本方法： 1 水平分害6 定义：组合关系r ( u ，q ，s ) 上的水平分割( h ) 是一操作，它将r 按照一组给 定的谓词p 1 ，p n 划分成一组关系模式r l ( u 1 ，q l ，s 1 ) r n ( u n ，q n ， s n ) ，满足： 1 ) u 1 ；u 2 = = u n = u 2 、k 1 2 k 2 2 = k n = k 3 ) q i = q 八p i 4 ) s 1 = ( d 其中，r 是关系名；u 是组成r 的有限属性集；q 是关系所满足的限定条件， 是一谓词；s 是关系的分布结构；k 是主键：i ，j i n ，p i a p j = 甲，v p i = t r u e ， 记为r ( h ) = r l ，r n ，式中p = p i ，p n ) 。 由定义可以看出，水平分割实际上是关系的选择操作。 2 垂直分割 定义：组合关系r ( u ，q ，s ) 上的垂直分割( v ) 是一操作，它将r 按照组给 定的属性a i ，a n 划分成一组关系模式r i ( u 1 ，q 1 ，s 1 ) ，r n ( u n ， q n ，s n ) ，满足： 1 1k i = k 2 2 2 k n 。k 2 、u 仁a i 3 ) q i = q 八p i 4 ) s 1 = ( d 其中，i ，j l n ) ，a i u ，a i na j - - 1 4 ，u a i = u ，记为r ( v ) = r l ， r n ，式中a = a 1 ，a n 。 由定义可以看出，垂直分割实际上是指对属性集上的投影操作。 3 混合分割 定义：组合关系r ( u ，q ，s ) 上的混合分割( m ) 是一操作，它将r 按照一组给 定的属性a l ，a n 和一组谓词p 1 ，p n 划分成r i ( u 1 ，q l ，s t ) ， 1 0 河海火学顺i 。论文第二章分布式数据库系统的技术研究 r n ( u n ，q n ，s n ) ，满足： 1 1k i = k 2 一= k a l = k 2 ) u i = a i 3 ) q l = q 2 2 。q n = q 4 ) nk i ( r i ) = = k 2 ( r 2 ) = = n k n ( r n ) 。兀k ( r ) 5 ) s 1 = ( d 其中，i ，j 1 ，n ) ，a i u ，a i n a j = k ，u a i = u ，p i 八p j = 叩，v p i = t r u e ， 记为r ( v ) = 础，r n ，式中a p = l i = l ，1 2 。 上述定义说明混合分割是水平分割和垂直分割的混合操作，即对关系的选择 和投影，视应用需要进行操作。 4 诱导分割 定义：组合关系r ( u ，q ，s ) 按另一个组合关系t ，它是由个已经水平分 割成t 1 ( u 1 ，q 1 ，s t ) ，t n ( u n ，o n ，s n ) ，在公共属性a 上的诱导分割( d h ) 是一操作，它将r 划分为r i ( u 1 ，q l ，s 1 ) ，r n ( u n ，q n ，s n ，) ，满 足： i ) k 1 = k 2 = = k n 爿k 2 ) u 1 = u 2 = = u n = u 3 、a ( r i ) a ( t i ) 4 ) q i = q i 5 ) s i = ( d 记r ( d h ) 町 = r l ，r n ) ，式中t = t 1 ，t n 。 诱导分割是一种相关分割操作，它是一种半联结操作。 2 2 2 2 数据分片的原则 对分布式数据库分割后，仍应保持d d b 原有的特质，所以分割后的各逻辑 关系之恻应遵循下列原则： 1 ) 完整性原则：全局关系的所有数据项必须包括在片断集合中，不允许出 现某个数据项属于全局关系，但却不属于任何片断。 2 ) 重构性原则：必须保证能够由同一个全局关系的各个片段来重构该全局 m 淘人学砸i ，论史第二章分布式数据库系统的技术研究 关系。对于水平分片可用并操作重构：对于垂直分片可用连接操作重构。 3 ) 不相交原则：全局关系被分割后所得的各数据片段互不重叠( 对水平分 片) 或只包含主键重叠( 对垂直分片) 。不相交原则不是必须的，但有这条原则 可以使分割不致引起太复杂。分割时不相交，则分配时的冗余可以得到控制。 2 3 事务处理的a c i d 特性 在分布式数据库系统中，事务( t r a n s a c t i o n ) 通常是指一个或一段描述数据 库系统一致态转换的应用操作序列。事务是数据库访问的原子单位，不可再分， 必须完整执行。它具有集中式事务的a c i d 性，即事务的原子一 生( a t o m i c i t y ) 、一 致。t 生( c o n s i s t e n c y ) 、隔离性( i s o l a t i o n ) ； l l 持久性( d u r a b i l i v y ) 1 ： 1 ) 原子性：事务的a l l 及n o t h i n g 属性。一个事务的操作要么全部成功执 行，要么全部不执行。当事务非正常终止时，其中间结果将被取消。事务的原子 性保证数据库的状态总是从一个一致的状态变化到另一个一致的状态，而不会出 现不一致的中间状态。 2 ) 一致性：并发执行的几个事务，其操作的结果应与以某种顺序串行执行这 几个事务所得出的结果相同，通常也称为可串行性。这种可串行化的并行调度是 由数据库系统的并发控制机制来完成，以保证并发事务执行时的数掂库状态的一 致性。所以这种性质也称为事务的一致性。 3 ) 隔离性：一个未执行完的事务不能在其提交之前把自己的中间结果提供给 其它的事务使用。因为未提交事务的结果不是最终结果，它有可能在以后的执行 种被迫取消，如果其它的事务用到了它的中闻结果，那么该事务也要撤销。如果 这些事务已经提交，则其结果也必须被取消，以免与事务的持久性相违背，所以 隔离性对事务的有效实现是非常重要的。 4 ) 持久性：当一个事务正常结束并提交后，其操作的结果将永久化，而与提 交后发生的故障无关。即使发生了故障，系统应该能够保证可以把事务的操作结 果恢复过来。 2 4 存在的主要技术问题 分布式数据库系统向用户提供了一个自治的、可扩展的数据集合，同时相较 于集中式数据库系统，也产生了一系列更复杂、更高难度的技术问题，给数据的 管理带来了麻烦，主要表现在以下几个方面 i 2 1 ： 1 ) 提高局部数据的高可用性 由于数据是存放于分布式系统的多个节点中，用户可能要访问同一节点的局 部数据，也可能访问不同节点的全局数据，这就要求在选择数据分布、数据分片 弼海大学硕| 论义 藉二蕈分布，数据库系统的技术研究 和数掘冗余存储的策略和方式时，要综合考虑，以减少节点间通信次数和传输量， 提高局部数据的可用度。 2 ) 保持冗余数据的同步更新 为保证分布式数据库系统数据的可靠性，常用的做法是将重要数据保持多个 副本，当主数据源的数据更新对，副本的冗余数据保持同步更新就成为一大难题。 3 ) 异构数据库的透明化访问 在异构分布式数据库系统中，各节点的数据库可能各不相同，它们由各自的 d b m s 管理，但对于用户来说，应当提供一个统一的、透明化的视图操作。 4 ) 分布式事务的并发控制 相对于集中式数据库系统而言，分布式数据库系统中多个事务同时读写相同 的数据单元的几率更大，因为这些事务不仅可能是来自个节点，同时也可能是 来自多个节点。系统的并发控制机制必须作出协调，提高事务处理的并行性和数 据库资源的高可用性。 5 ) 保证数据可恢复性 当分佰式数据库中某节点出现故障导致数据丢失或数据不可用时。应该能 够由其它节点上的冗余数据恢复本节点的数据。 ? i i 海人学颂i 论文 第三章高可用系统的并发挎制与死锁检测 第三章高可用系统的并发控制与死锁检测 3 1 分布式并发控制 分布式数据库中经常会出现多个节点的多个事务在同一时间对相同的数据 进行查询、读、写等操作，这就产生了并发问题并有可能导致死锁的出现。因此， 有效实现并发控制、解决死锁，就成为分布式数据库资源高可用的关键之 1 3 1 。 3 1 1 事务可串行化 事务可串行性的定义是：若干个事务并发执行的结果与按某种顺序排列执行 的结果相同时，就称这若干个事务具有可串行性。如果事务的并发执行能够通过 以一定顺序的串行操作来等同实现，那么诸如丢失更新、多副本数据不一致等问 题就可能有解决的途径。事务的可串行性通常作为多个事务执行的正确性准则。 分向式并发控制的目的是保证分布式数据库系统中多个事务的高效正确执 行。为了讨论分布式事务并发控制的正确性，引入两种事务调度模型，一种是以 加锁技术为基础的形式模型，一种是以时戳技术为基础的时间模型【1 4 。 在数据库系统中，事务是以发出读操作和写操作原语的方式来存取数据库 的，任一事务t i 的读操作记为r i ( x ) ，写操作记为w i ( x ) ，x 是一数据项。负 责控制事务请求的数据库操作的执行顺序的部件叫调度器，它是数据管理器 ( d m ) 的一部分。调度器确定数据库操作的穿插执行，确保数据库状态保持一 致。数据库操作的一次穿插执行称为一个调度，如： r i ( x ) ，r j ( x ) ，w i ( x ) ，r k ( x ) ，w j ( x ) 表示事务t i ，t j ，t k 对数据对象x 的读写操作，这几个事务可以串行执 行，也可并行执行。当它们并行读写数据对象x 时，就可能造成数据对象x 的 不一致性，因此必须对这些并发操作进行控制。事务的并发控制就是保护事务的 并发操作正确执行。在实现过程中，可以采用加锁技术及时戳技术来实现事务的 可串行化调度 1 5 1 。 3 1 2 基于时戳技术的并发控制 用时戳技术实现事务的并发控制时，给每个事务赋予一个唯一的时戳，事务 的执行等价于按时戳的先后次序串行执行，即事务的冲突操作按时间的次序进行 调度。 基于时戳技术的并发机制思想是，只有当某一数据项上由一较年长的事务写 入以后才允许另一较年轻的事务对该数据项进行读写，否则它拒绝这个操作并重 4 海人学硕：l 论文第三覃高可用系统的并发控制与死锁检测 新启动该事务，即一个事务只能读写它以前的事务写入的数据而不能读写它以后 的事务写入的数据。当出现年长的事务读写年轻事务写入的数据时，该年长事务 遭拒绝且重新启动被赋予一个新的时戳，直到该时戳大于原来年轻事务，即它变 得比年轻事务更年轻时才可以读写原年轻事务写入的数据。 基于时戳技术的并发控制包含了保守的时戳方式和基本时戳方式。保守的时 戳方式由于有等待状态，因此有可能出现死锁。避免死锁的有效方法是超时以后 发送一空操作。基本时戳方式中无死锁的问题，因此不需要死锁检测及解决，但 事务重启的次数较多。 3 1 3 基于加锁的并发控制方法 1 加锁技术介绍 基于加锁技术的并发控制思想是，事务在对数据项操作之前必须先申请该数 据项的锁，只有申请到锁以后，即加锁成功以后，才可以对数据项进行操作。通 过锁的共享及排斥的特性，实现事务的可串行化调度。锁的类型一般有两种类型： 读锁( 也称为共享锁s l o c k ) 和写锁( 也称为排它锁x l o c k ) 。来自不同事 务的对同一数据资源的加锁请求是相容的，当且仅当，它们可以同时被授予。共 享排它锁模式的相容矩阵如图3 1 所示： 表3 i共享排它锁模式的相容矩阵表 i xs |xnny i snyy yyy ( 其中：y 表示相容，n 表示不相容，一表示不申请锁。) 2 多粒度( g r a n u l a r i t y r ) 锁模型与多锁模式 为了提高数据资源的可用性，同时保证事务执行的安全性，现有的数据库系 统通常采用了多粒度锁模型。最为常见的多粒度锁模型由行级锁和表级锁组成。 行级锁通常采用共享排它锁模式或排它锁模式。 表级锁将封锁表中的所有行，比行级锁的范围更广，数据并发度较低，但表 级锁完整地控制了全表的可操作性，可以保证事务的正常执行。表级锁采用的是 多锁模式，按其由低到高的封锁效果，依次为：r s 、r x 、s 、s r x 、x 。 ( 1 ) 行共享( r s ) ：表上的行共享锁用于让事务封锁表中的部分行，以便于 数据修改，但在建立封锁时并不立即修改数据。在所有表级锁中它的限制级别最 低，数据并发程度最高。 ( 2 ) 行排它(