（计算机科学与技术专业论文）clientserver数据库模型下并发控制和恢复技术研究.pdf

里堕型竺丝兰查兰竺至尘堕! ! ：生笙耋 图i 1 图1 2 图2 ，1 图3 1 图3 2 图3 3 图3 4 图3 , 5 图3 , 6 图3 7 图3 8 图3 , 9 图3 1 0 图3 1 1 图3 ，1 2 图3 1 3 图4 1 图4 2 图4 3 圈4 a 图4 5 图4 6 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图58 图5 9 图目录 o b i e c t s e r v e r 结构3 p a g e s e r v e r 结构3 e s m c s 的结构1 7 使用p 2 p b c c 的c s 结构2 2 客户状态转换关系2 3 服务器的状态转换关系2 4 情况一2 8 情二2 8 情况三2 9 情况网2 9 冲突检测一，3 0 情况五3 0 情况六3 1 情况七3 l 情况八3 2 情况九一3 2 事务回滚3 8 重启恢复过程3 9 分析过程4 0 r e d o 过程4 2 u n d o 过程一4 3 重启恢复示例4 3 系统模型一5 l 吞吐量( u n l f o r m ) 5 5 撤销率( u n i f o r m ) ，5 5 每次提交的发送信息量( u n i f o r m ) 5 6 吞吐量( h o t c o l d ) ，5 6 撤销率( h o t c o l d ) 5 7 吞吐量( h i c o n ) 5 7 撤销率( i i i c o n ) 一5 8 吞1 哇量( p r i v a t e )5 8 国防科学技术人学研究生院。学位论文 表目录 表2l 缓存一致控制算法分类 表31与a a c c 及c b l 比较， 表41缓存管理方法与重启恢复， 表5l 系统配置参数 袁5 2 操作刀= 销参数 表5 1 31 二作量模型参数 ，1 2 1 ，1 6 一5 1 5 2 5 3 国防科学技术人学研究生院学位沧文 第一章绪论 1 1 研究背景 随着计算机技术的发展、网络的普及以及应用的需求，d b m s 已经由早期的单一集中 模型发展成现在的c l i e n t s e r v e r 结构模型。现在绝大部分的商用和实验d b m s 都采用 c l i e n t s e r v e r 结构，c 1 l e n t s e r v e r 数据库系统已经成为现在数据库管理系统的主流。 数据库的安全保护是数据库管理系统的一个重要研究课题口”，它关系着数据库的安全 性、完整性、并发性以及出现故障后的数据库恢复问题。而并发控制和恢复技术的研究正 是为了实现后两个目标。并且数据库管理系统的设计要能够保证事务的a c i d 属性( 见2 i 节 。并发控制技术主要用于保证事务的一致性和隔离性而恢复技术主要用于保证事务 的原子性和持久性。并发控制技术可以保证多个事务访问同一数据时的正确执行，维持数 据的一致，而恢复技术能够保证在数据库出现故障或崩溃威胁到数据的安全性和完整性时 对数据库进行恢复，使其恢复正确一致的状态。总之，并发控制和恢复技术是数据库管理 系统设计中必须要涉及的两项相当重要的内容。过去国内外学者对集中式数据库系统的并 发控制和恢复技术研究已经进行了相当长时间的研究，对共享磁盘和分布式事务处理等系 统的研究也进行了相当的研究，而对c l i e n t s e r v e r 结构数据库系统的研究虽然也取得了 一些成果，但相对于其他系统较少。本文主要研究c 1 i e n t s e r v e r 数据库系统的并发控制 和恢复技术。 由于结构上的差别，c l i e n t s e r v e r 数据库的恢复技术与传统的集中式、分布式以及其 他( 如共享磁盘、共享内存等) 数据库系统的恢复技术还是存在很大的差别。 根据客户端向服务器发送请求的内容可将c l i e n t s e r v e r 数据库管理系统分为两种： q u e r y s h i p p i n g 系统和d a t a - s h i p p i n g 系统【9 】。q u e r y s h i p p i n g 系统是指客户端向服务器端发送 查询消息( 如s q l 命令) ，由服务器接受命令并进行相关处理后将结果返回给客户，客户 端主要负责与用户进行交互、显示结果，其他工作都由服务器来完成。般关系数据库都 是属于这种结构的。这种结构的优点就是设计相对简单，不需要复杂的并发控制。缺点是 服务器承担的任务过多，导致负载太大，不利于多任务的并行。还有就是客户只请求有用 的数据，与服务器间的通信量较小。q u e r y s h i p p i n g 结构系统的数据库组织类似于单一集中 式数据库【嘲。 d a t a s h i p p i n g 系统是指客户向服务器请求数据，得到数据后将其缓存于本地，在本地 进行相关处理后再将结果传回给服务器，服务器主要负责并发控制和恢复的工作，其他应 用的处理都由客户来完成。此结构充分利用了客户机的资源，减少了客户事务的响应时间。 在现今个人计算机功能同渐强大的环境下，这是一个非常好的趋势，能有效地减缓服务器 带来的瓶颈。现在的而向对象数据库系统( o o d b m s ) 一般都是采用此种结构。虽然相对 第1 页 困防科学技术人学研究生院学位论文 于q u e r y - s h i p p i n g ，d a t a - s h i p p i n g 的通信量要大，但在网络带宽日趋增强的情况下，这个问 题也显得没那么突出i j j 。 q u e r y s h i p p i n g 结构数据库系统的恢复技术相对于传统的数据库系统没有太大的区别， 因为二者的结构差别本来就不大【1 0 】。而d a t a - s h i p p i n g 结构的数据库系统在恢复和日志子系 统以及并发控制上就存在一些很大的差别。这是由其与传统的集中式和分布式以及其他结 构d b m s 所不同的几点结构特征所决定的： n 数据的修改主要在客户端完成，而其稳定拷贝却要保存在服务器上： 2 ) 每个客户端管理自己的缓存池； 3 1 客户端与服务器间的通信比较奢侈( 相对于其他结构访问本地主存) ； 4 1 客户端相对于服务器具有不同的硬件特性以及执行和可靠性特征。 将数据缓存于客户本地可以大大减少客户与服务器的交互次数，因而可以提高客户事 务的响应速度。本地缓存可允许每个数据项在多个客户缓存中存在拷贝，并且还可能在事 务完成后仍然存在客户缓存中。当一个客户需要修改数据页时，网络中的其他客户也可能 拥有该数据页的拷贝。这样就引出了一个问题，怎样保证多个客户缓存中的数据的一致性。 在第二章我们将分析c l i e n t s e r v e r 系统的并发控制技术，比较几个客户缓存一致性控制算 法。 为了更好地了解d a t a - s h i p p i n g 结构的数据库系统，下面我们将简要介绍d a t a s h i p p i n g 结构系统的具体分类，并比较各种不同结构的优缺点。 根据客户与服务器间传送数据的组织不同，d a t a - s h i p p i n g 结构的d b m s 可以有三种不 周的结构 9 1 ：o b j e c t - s e r v e r ，p a g e - s e r v e r 和f i l e - s e r v e r 。 1 1 1 o b j e e t - s e r v e r 结构 o b j e c t - s e r v e r 的客户与服务器的绝大部分功能模块都如图1 1 所示1 9 】。当客户需要访问 对象时，首先访问本地缓存；如果未找到，就向服务器发送请求。客户与服务器问传送的 单位是单个对象。 这种结构存在几个主要优点。首先，服务器和客户都可以运行方法( m e t h o d s ) 。在服 务器上先进行选择( 如从大集合中选出所需的小子集) ，避免了将整个集合移动。在没有 为对象建立索引的情况下，这种能力尤其有用。其次，这种结构简化了并发控制和恢复子 系统的设计，因为服务器确切地知道哪个应用程序访问了哪个对象。因此，并发控制可以 几乎完全集中在服务器上；另外，面向对象的锁的实现也是非常直接的。 o b j e c t s e r v e r 还是存在一些严重的问题。首先，在较坏的情况下可能会出现每个对象引 用部需要一个r p c ，尽管客户端对象缓存的命中率高到可以命中大部分请求。但对服务器 来说，每次传输超过一个对象，它必须能够指出哪些对象相近，能够将相近的对象放到一 起。另一个主要的问题是这种结构将服务器的设计复杂化了。服务器除了承担恢复与并发 控制外，还必须能够执行用户所指定的方法。 第2 页 国防科学技术人学研究生院学位论文 s e r ：v e r 图1 1 o b j e c t s e r v e r 结构 个人计算机功能的日趋强大，网络带宽、速度的发展，客户应该要承担更多的任务 尽量减轻服务器的负担。因此纯粹的o b j e c t s e r v e r 结构的d b m s 会越来越少用。 1 1 2 p a g e - s e r v e r 结构 图1 2 是p a g e - s e r v e r 的一种可能结构9 1 。服务器主要由一个大的缓存池、用于管理页 和文件的存储系统的i o 层以及并发控制和恢复服务器。应用程序只运行于客户端，客户 与服务器间通信的单位是磁盘页。当服务器收到请求时，先对所请求页加上合适的锁，如 果页不在服务器缓存，就先从磁盘获得后再返回给客户。 w o r k s t a t i o n i s e r v e r 圈1 2p a g e s e r v e r 结构 客户端缓存的组织可以是以页为单位或以对象为咀位，也可以二者共存。使用对象缓 存的话，可以节省客户缓存空间，不用缓存应用程序未引用的对象。但从新进的数据页中 拷贝对象到缓存带来一定的耗费。并且如果客户对某个对象进行了修改的话，可能需要重 新从服务器获得这个对象所在的页，糟糕的是还有可能引发一次i 0 操作。 第3 页 国防科学技术人学研究生院学位论文 象o b j e c t s e r v e r 一样，这种结构有其优点也有缺点。主要优点是将数据库管理的大部 分功能都在客户端实现，充分利用了客户端的资源，留给服务器实现其最基本的功能：并 发控制和恢复。因为服务器与客户端之间以整页传递，服务器的开销被减到最小。这样一 个服务器可以负责更多的客户。 虽然这种简化使得浚结构有很大的吸引力，但它也不是没有缺点。首先，只能在客户 端执行方法，这样导致客户与服务器问的通信数据量较大。其次，面向对象的锁可能较难 以实现，考虑两个不同的客户同时修改同一页中不同的对象，如果在修改过的页写入服务 器前不采取有效的措施将两个修改合并，就会丢失其中一个修改。 1 1 3 f i l e - s e r v e r 结构 f i l e s e r v e r 结构算是p a g e s e r v e r 的一个变种【9 】o 它在客户软件上加入了象n f s ( n e t w o r k f i l es y s t e m ) 【4 卅的远程文件服务，以此来直接读写远程数据库。如图1 3 所示。 w o r k s t a t i o n l - s e r v e r 1 s 图1 3f i l e s e r v e r 结构 这种结构还是很有吸引力的。首先，它有p a g e s e r v e r 结构的许多优点，比如由客户来 分担服务器的负载。其次，由于n f s 是运行在操作系统内核上的，用它来读写数据库，用 户层上下文交换可以完全避免，直接从远程数据库中读取。最后，n f s 技术还是不断发展 提高的。 除了与p a g e s e r v e r 有类似的缺点外，它本身还有一些其它问题存在。首先，n f s 的传 输速度较慢，它是建立在u d p 上的无状态协议，在写操作请求确认前就需将建立的n f s 文件写到磁盘，这样每次写操作需两次i o 操作。其次，由于读操作完全绕过了服务器软 件，不可能将读数据与对数据加锁合并成一条消息。 由于p a g e s e r v e r 是简单、效率高，并且能够很好地利用客户端资源来降低服务器的负 载，本文的研究主要针对此结构。本文后面涉及的相关技术和算法主要基于p a g e s e r v e r 结 构的系统。 第4 页 訇型 一 e 网防科学技术人学研究生院学俺沦文 1 2 课题研究的主要内容 本文的研究主要基于p a g e - s e r v e r 结构，分析并研究了基于此结构的c 1 i e n t s e r v e r 数据 库系统的并发控制和恢复技术。p a g e s e f v e r 结构允许客户在本地缓存数据，客户事务可直 接在本地数据上进行读写，减少与服务器的交互次数。但这样带来了一个问题，即如何保 持各客户缓存数据的一致性。文献 1 】【2 4 2 5 】 2 8 】( 3 2 】【3 9 】已对该问题进行了相应的研究， 提出了一些解决办法，例如算法c b l 2 8 j 、a 0 c c 和a a c c 等。这些算法各有优缺点， 实现的方便程度和算法的性能也各有不同，其中有些算法还得到了较为广泛的应用。但这 些算法都存在一个共同的缺点，就是服务器一直处于并发控制的关键路径，影响了客户事 务检测冲突的时间，导致冲突率较高，从而增加了事务的撤销率。并且服务器是唯一有权 进行并发控制的单位，使得服务器负载较高，影响了整个系统的事务吞吐量。现在的客户 机的性能都比较高，可以用来分担服务器的负载。为了解决上述问题，充分利用客户端资 源，降低服务器的负载，本文提出了一种新的维持客户缓存一致性的并发控制算法一 p 2 p b c c 算法。 本文的主要的工作有： 1 对c l i e 耐s e r v e r 数据库管理系统的体系结构进行了分析和研究，描述了各种不同的结构 分类，并对它们进行了分析和比较。分析研究了c 1 i e n 俗e r v e r 数据库管理系统中维持客 户缓存一致性的各种算法，讨论了每种算法的适用范围及优点，分析了存在的缺陷和 问题。分析并研究了c l i e 州s e r v e r 数据库管理系统的几种不同的恢复技术，比较了它们 的优缺点。 2 在深入研究现有的c l i e n t s e n ，e r 数据库管理系统的并发控制算法及其恢复技术的基础 上，提出了一种新的维持客户缓存一致性的并发控制算法p 2 p b c c 算法。分别给出了 它的客户端和服务器端的状态和协议，描述了它在正常情况下的处理过程，并针对若 干具有代表性的情况，将它与其他主要算法进行了初步的性能分析和比较。 3 针对采用p 2 p b c c 算法进行并发控制的c l i e n t s e r v e r 系统设计恢复策略。讨论了事务回 滚、系统重启、介质失效、进程失效等情况下系统的处理方法，并给出了一种c o r 砌i l l s n 优化方法。 4 建立模型，对c b l 、a a c c 以及p 2 p b c c 进行模拟测试，比较它们在不同的工作量模 型下的性能，分析各种指标对系统性能的影响，结果表明本文所提出的缓存一致性控 制算法在系统吞吐量、事务撤销率等性能指标方面有了很大的改进。 1 3 论文结构 本文共分六章。 第一章绪论，介绍了课题的研究背景和意义，提出了课题的研究目标，说明了研究 的内容。 第5 页 国防科学技术人学研究生院学位沦文 丢失该事务的执行结果。 2 1 2 并发控制 并发控制负责正确协调并发事务的执行，保证并发的存取操作不致破坏数据库的完整 性和一致性，确保并发执行韵多个事务能够正确地运行并获得正确的结果。事务的个操 作序列称为一个调度( 也称历史，h i s t o r y ) 3 5 1 o 定义2 2 并发事务的一个调度：设t = ( t i ，t 2 ，t 。) 是一组并发执行事务，其中 t 。= ( i ， ) ，则称s = ( t ，t ) 是它的一个调度。其中： e t = 怩l i ， t2 叱l i 。 对任意两个冲突操作o u o k i t ，则有0 u t 0 k i 或0 k l t 0 i 。 并发控制第一法则；并发执行不应导致程序的失效【i ”。 这是事务a c i d 特性中的i ( 隔离性) 的含义。系统要保证提供给每个事务如同隔离 运行的环境。最简单的实现隔离方式就是一次只运行一个程序，但这种情况基本是不太可 能的。一般的情况是：有很多程序，具有不同的响应时间，分布执行在许多具有各自存储 器豹处理器上。另外，数据可髓分布在或快或馒的存储器中，这样计算和i o 会相互重叠。 在这种情况下，并发是不可免的、必不可少的。因而，要以某种方式控制并发，提供隔离 性，使之满足并发的第一法则。 并发控制第二法则：相比于串行执行，并发执行不应有更低的吞吐量和更长的响应时 间i 。 2 2c l i e n t s e r v e r 系统的缓存一致性控制算法的分类 定义2 3 废弃数据：客户缓存中的数据版本比该数据最新提交的版本老就称客户缓 存中的此项数据是废弃的。 c l i e n t s e r v e r 系统中，事务缓存一致性维持算法应能保证访问过废弃数据的事务无法 完成提交。我们根据是否允许事务访问废弃数据将缓存算法分成两种：a v o i d a n c e b a s e d 类 和d e t e c t i o n b a s e d 类算法【2 6 】【2 7 l 【2 9 】。这两种算法的区别就是d e t e c t i o 一b a s e d 类算法是惰性的 ( 1 a z y ) ，需要事务来检查所访问事务的有效性；而a v o i d a n c e b a s e d 类算法则是热心的 ( e a g e r ) ，他们保证废弃数据会很快且自动从客户端缓存移除，事务没机会访问废弃数据。 d e t e c t i o n b a s e d 类算法允许废弃数据在客户缓存保留一段时间，因此事务在被允许提 交前必须检查它所访问的缓存数据是否有效。服务器负责维持相关信息来保证客户完成此 类检查。d e t e c t i o n b a s e d 类算法之所以如此命名是因为对废弃数据的访问会被明确地检查 并检测出来。不同钓是，在a v o i d a n c e b a s e d 类算法下，事务永远没有机会访问废弃数据。 a v o i d a n c e b a s e d 类算法使用r e a d o n e w r i t e a l l ( r o w a ) 1 2 9 方法来管理各缓存副本。r o w a 方法保汪当事务提交时修改过的数据项的所有现存拷贝都具有相同的值。r o w a 下，事 国防利学技术人学研究生院学位沦文 务允许读取所需要的数据的任何一个拷贝( 如果本地存在就读本地) ，而当事务对数据项 进行修改后，就需要将修改结果反映到所有拷贝。下面对d e t e c t i o n - b a s e d 和a v o i d 孤c e - b a s e d 算法进行稍具体的分析【3 6 】。 2 2 1d e t e c t i o n _ b a s e d 类算法 此类算法的一个优点就是简单，他们的一致性动作只包含服务器和一个客户端，客户 端的缓存管理软件可以大大简化。d e t e c t i o n b a s e d 类算法的一个缺点就是过于依赖服务器， 这样加大了服务器的负载。他们的执行过程可以分为三级：初始有效性检查、变化通知提 示和远程修改动作j 。 f 1 1 初始有效性检查 在事务提交前必须确定其所访问的数据的有效性，对事务所涉及的所有数据的有效性 检查必须在事务结束前完成。主要三神不同的检查策略： 一同步，每次事务对页初始访问时发送检查请求，等待同步消息； 一异步，也是对页初始访问时发送检查请求，但不需等待； 一延迟，等到事务提交时才进行检查。 这三种策略都保证一旦数据被确定有效后，在事务生存期间都保证数据拷贝一直有 效。因此，在得到有效性保证的事务结束前( 撤销或终止) ，服务器不允许其它事务对该 数据项提交新的修改。也就是，事务在进行修改前必须得到服务器的许可。 同步有效性检查是三种中最简单的，在事务初次对缓存数据进行访问时就必须检查其 有效性。这种有效性是按同步的方法进行的，也就是事务在有效性得到确保后才允许访问 浚缓存数据。异步有效性检查也类似，但不同的是事务不需要等待检查的结果，它是假设 检查的结果是成功而对本地缓存数据进行访问，一旦结果为失败，事务就必须撤销。延迟 有效性检查比异步检查还乐观，直到事务执行完进入提交阶段后才会向服务器发送有效性 检查信息，将其读写的所有数据信息全部发送到服务器，由服务器来决定事务是否可以提 交。 这三种方法是从悲观到乐观的，体现了对检查开销和可能的事务撤销不同的权衡。延 迟检查有两个主要优点：一，也是最有意义的，它将多次一致性检查捆绑到一起，降低了 检查的开销；二，对最后要撤销的事务进行一致性检查是浪费，延迟检查就可以避免这种 浪费。延迟检查还存在潜在的缺点，就是如果存在数据冲突的话事务就需要撤销，导致撤 销率较高。异步方法是折衷的，将与服务器的交互从事务执行的关键路径中移除，来减轻 其产生的作用，同样还通过较早检测数据有效性降低了撤销率。 f 2 ) 变化通知提示 与服务器的通信耗费是昂贵的，因此d e t e c t i o n _ b a s e d 算法的设计者都选择乐观方法来 降低这种耗费。选择乐观方法主要是着眼于冲突是罕见的，而检测冲突的耗费则是非常高 的。有两种方法可供选择来降低乐观算法的撤销率：一种是，区别对待热门数据，可以用 第9 页 国防科学技术人学i i 】 究生院学位论文 更加悲观的访问对待此类数据；另一种就是使用a v o i d a n c e b a s e d 算法的技术( r o w a ) 来 减少废弃数据的数量，这种方法就称为变化通知提示。该通知就是由修改而引发的一个动 作，来影响远程客户缓存数据的有效性。 通知可在修改事务的生命期的任何阶段以异步的方式发出，也可以等到修改事务提交 后。事实上，如果发送的通知确实修改了远程缓存数据而不是简单移除它，在事务提交前 发送通知就可能是危险的；如果发送通知的事务撤销了，则在远程进行修改的事务也必须 回退，这带来了很大的复杂性和开销。如果仅仅是通知将远程拷贝清除，带来的问题就较 小，但如果那里的活跃事务已经访问了废弃数据，也会造成不必要的撤销。因此，一般都 采取提交后才发送修改通知。 ( 3 ) 远程修改动作 当修改通知到达远程站点后，可有三种选择：传播( p r o p a g a t i o n ) 、作废( i n v a l i d a t i o n ) 或从二者之间动态选择。传播的结果是新的值取代废弃数据；作废就是简单地将废弃数据 从缓存中清除。一旦作废后，客户要想再访问此数据就需要重新从服务器获取。动态选择 是为了对不同的工作量达到较好的执行效果。 2 2 2 a v o i d a n c e - b a s e d 类算法 a v o i d a n c e b a s e d 算法通过让事务不可能访问到废弃数据来保证一致性。根据客户修改 结果来操作远程客户缓存数据，这就要求客户端软件必须有额外的机制来支持这些动作。 除了需要额外的客户端软件支持，还要求服务器必须维持额外的信息，也就是服务器必须 维持所有拷贝所在地信息。 a v o i d a n c e b a s e d 类算法的实现分四步：写意图声明、写许可阶段、远程冲突优先权确 定和远程修改动作1 2 9 。 ( 1 ) 写意图声明 跟d e t e c t i o n b a s e d 类算法一样，a v o i d a n c e b a s e d 类算法也可根据事务何时进行一致性 动作来分类。但它的一致性动作的本质却与d e t e c t i o n b a s e d 类算法有些许区别。因为r o w a 协议，执行于a v o i d a n c e b a s e d 模式下的事务总是可以读取他们缓存的数据。只有在所请求 数据不在本地或进行了修改，客户端与服务器才发生相互作用。如果客户向服务器请求数 据，服务器在回应客户的同时，还隐含向客户保证在该数据被修改后能够立即通知客户。 虽然所有的a v o i d a n c e b a s e d 类算法使用相同的原则来处理读，但他们在写动作初始化 方法还是有区别的。当事务要修改缓存页拷贝时，必须在事务提交前向服务器发送写意图 声明以能够执行r o w a 。一旦服务器授予客户对某页的写许可，它就保证在写许可存在期 n 1 i j ，客户可以任意修改浚页而不需询问服务器。 客户向服务器声明写意图也存在三种方式： 一同步，写动作要开始前，等待服务器回应； 一异步，写动作要开始前，不等待服务器回应； 第1 0 页 国防科学技术人学研究生院学何论文 一延迟，等到修改事务进入提交阶段。 对同步、异步和延迟三种方式的权衡类似于d e t e c t i o n b a s e d 模式，同步方式是悲观的， 延迟方式是乐观的，而异步方式是二者的折衷。但这种权衡的重要性对a v o i d a n c e b a s e d 来 说却是不同的，由于此类算法的本质( r o w a ) ，在服务器能够授予客户写许可之前，可能 还会影响一个或多个其它客户，因此这里面还包含相当大量的工作。另外，远程一致性操 作在事务提交的关键路径上，在远程一致性操作完成前事务无法提交。 ( 2 ) 写许可阶段 根据写许可存在时间，也可将a v o i d a n c e b a s e d 类算法分类。一般有两种：写许可只存 活于一个事务的生命期内；或者写许可可以在一个客户端横跨多个事务。第一种情况下， 事务开始不具有写许可，想进行写时必须向服务器请求写许可；事务结束后，所有写许可 都由服务器自动撤回。第二种情况下，写许可一直保留在客户直到客户丢弃它或服务器要 求客户交回许可。 f 3 ) 远程冲突优先权确定 当一致性动作到达远程客户时，赋予他们优先权有两种方式：等待( w a i t ) 或取代 ( p r e e m p t ) 。等待方法就是一致性动作必须等到与其冲突的正在执行事务结束后才能进行； 而取代方法就是正在执行的事务可被新进来的一致性动作事务撤销。在等待方法下，远程 修改者必须排在本地读事务后按顺序执行；而在取代方法中，写肯定优先于读，可以直接 将与其冲突的读撤销。 ( 4 ) 远程修改动作 此模式下的远程修改动作实现与d e t e c t i o n b a s e d 下面类似：传播、作废或动态选择二 者之一。如同前面所讲，传播方法下，在事务执行期问发送修改通知也会存在些许问题。 a v o i d a n c e b a s e d 类算法与d e t e c t i o n - b a s e d 类算法的远程修改动作的最大不同就是在 a v o i d a n c e b a s e d 模式下，远程修改完成后才允许事务提交。这是为了维持r o w a 的语义， 以保证a v o i d a n c e b a s e d 算法能够正确执行。因此，如果选择传播方法，所有收到修改通知 的远程客户站点都必须与服务器及事务正执行的客户进行两阶段提交3 】【2 9 】：而如果选用作 废，就不用进行两阶段提交，只要简单地将远程数据移除即可。 2 2 3 相关研究成果 近十年来，对缓存一致性控制算法的研究已取得了重要进展，并且其中的某些算法还 得到了广泛的应用，比如m f r a n k l i n 的c b l 算法【2 8 1 。a o v i d a n c e b a s e d 和d e t e c t i o n b a s e d 类 算法都出现了些具有代表性的算法，并且不管是属于同步、异步还是延迟方式，都有相应 的算法研究。表21 列出了一些较为常见的算法。 前面已经初步介绍了a o v i d a n c e b a s e d 和d e t e c t i o n b a s e d 类算法，并对其进行了比较。 接下来，我们将对其中几个具有代表性的算法( c 2 p l 、c b l 、a o c c 以及a a c c ) 进行分 析、比较。 第1 1 页 国防科学技术人学研究生院学位论文 表2 ，1缓存一致控制算法分类 s y n c h r o n o u sa s y n c h r o n o u s d e f e f r e d a v o i d a n c e b a s e dc b l 2 8 1a a c c 3 2 10 2 p l 2 4 1 a c b l 2 5 】 d e t e c t i o n b a s e d c 2 p l 2 4 n w l 3 9 1a o c c i l 】 2 2 4c 2 p l 算法 c 2 p l 2 4 】是最简单的一种内部事务缓存算法。早期的一些系统如o r i o n i s x 原型【州、 e x d o u s 存储系统【30 j 等都使用类似于此算法的缓存策略。 c 2 p l 中，缓存一致性通过使用“c h e c k o n a c c e s s ”方法来维持。所有页拷贝都标注版 本号，来唯一标识页状态。当客户事务需访问它未获得适当锁的页时，向服务器发送请求 并等待回应。如果该页在客户缓存中，就将页版本号附加到锁请求消息中。如果其它客户 有相冲突的锁，锁请求就需在服务器等待直到锁释放。如果是请求的写锁，服务器还需判 断客户的缓存拷贝是否是最新的，如果不是，需在授权消息上附加上有效的页拷贝一起发 送给客户。 c 2 p l 使用严格的两阶段锁，所有的锁都是在事务提交或撤销后才释放。死锁都是由 服务器集中处理的，一般的解决方法是杀掉最新加入的事务。 这种方法虽然简单，但开销较大，客户事务的阻塞时间较长。由于要对照版本号等处 理操作，客户端与服务器之间的通信量较大。 2 2 5 c a l l b a c k l o c k i n g ( c b l ) 算法 c b l 【2 驯属于同步的a v o i d a n c e - b a s e d 类算法。客户缓存数据和读锁，在进行写操作之前 要从服务器获得写许可。c b l 是商业系统中应用最多的一种缓存并发控制算法。 c b l 中，总可保证本地缓存数据是有效的，事务可以在不与服务器联系的情况下读本 地数据。如果在本地缓存无法找到所需页，客户就向服务器发送请求；服务器在确定无其 它活跃客户对该页拥有写许可后，向它返回所请求页的一个有效拷贝。写意图是以同步方 式声明的，客户在授予事务本地写锁之前必须获得写许可。由于事务在其生命期内获得了 写许可，因此当其完成所有操作后不需任何一致性维持动作就可以提交。 服务器维持整个系统中缓存拷贝所在地信息。当客户从缓存池中丢掉页后，通过在它 与服务器的下一个交互信息上附加消息的方式通知服务器。服务器根据消息来重新组织拷 贝信息表。事务从执行它的客户的本地锁管理器获得锁，读锁请求以及已经得到写许可的 写锁请求部可以在不通知服务器的情况下得到满足。如果没有写许可，请求写锁就会引起 写许可错误，客户必须向服务器声明其写意图，并等待服务器授权后才能继续。当写意图 到达服务器后，服务器向所有拥有所请求页的缓存拷贝的客户站点发一耵回调命令。客户将 国防科学技术人学研究生院学位论文 当客户想访问不在本地缓存的页时，需向服务器发送请求：服务器收到请求后，检查 其它客户是否也缓存了该页。 一如果该页没有在其它地方出现，则服务器返回p r i v a t e - r e a d 锁给客户； 一如果有其它客户以p r i v a t e r e a d 缓存该页，则返回s h a r e d r e a d 锁给请求客户，并且 以附加消息的方式通知另一客户将锁改为s h a r e d r e a d 。消息延迟将使得对同一页同 时有p r i v a t e r e a d 和s h a r e d r e a d 存在的情况； 一如果有客户以s h a r e d r e a d 方式缓存该页，则直接返回s h a r e d - r e a d 给请求客户； 一如果有客户以w r i t e 方式持有该页，服务器就向该客户发送回调信息并指出所请求 的页和对象；远程客户在收到回调信息后，检查自己是否在操作指定的对象，如 果没有，就将自己的锁模式更改为s h a r e d r e a d ( 这意味着可以接受对象级锁) ，并 将自己已修改的对象标识符返回给服务器：否则如果正在修改所请求对象，就通 知服务器请求无法得到满足。服务器收到肯定回答的话，则标记远程客户已修改 的对象并将该页发送给请求客户；否则阻塞客户请求直到拥有写锁的客户事务提 交。 ( 2 ) 在p r i v a t e r e a d 锁的页上进行修改 当客户要在p r i v a t e r e a d 页上执行修改操作时，客户要将锁模式改为w r i t e ，并在随后的 消息中通知服务器。收到消息后，服务器的工作如下： 一如果该页在其它客户以s h a r e d r e a d 模式存在，服务器就需发送作废通知给这些相 关客户。作废通知要求客户将所涉及的页或对象从其缓存中清除。如果还有其它 客户同样在使用该页但不是所请求的对象，服务器还要通知发送消息的客户将锁 模式改为s h a r e d r e a d 。 一如果没有客户缓存该页或所有的作废过程都已完成，服务器就修改它的锁表，标 明此页己被客户写锁。 f 3 ) 在s h a r e d 。r e a d 锁的页上进行修改 当客户要在s h a r e d - r e a d 的页上进行修改，客户发送一条异步锁升级消息并继续进行处 理。服务器在收到消息后，发送回调消息给所有涉及该页或对象到的其它客户： 一如果客户没有在使用该页，则将其清除，并返回给服务器成功消息； 一如果客户在使用该页但没有使用指定的对象，则将指定对象作废，并通知服务器； 一如果客户恰好在使用指定对象，则回应服务器，通知存在冲突。 ( 4 ) 回调( c a l l b a c k ) 处理 当服务器收到显示存在冲突的回调响应时，执行死锁处理。如果不存在死锁，要进行 修改的事务不能在读事务之前提交；这旱的死锁处理包括检查是否存在修改其它客户在读 的对象。例如客户a 在修改客户b 正在读的数掘，而客户b 突挛穸嘉薹峤弧绻衿魇盏剿械淖鞣铣晒赜则 向初始请求的客户发送消息，允许其将锁模式由sharedread改为write。f5 ) 提交处理第 围防科学技术人学研究生院学伉论文 提交时，客户将日志发送给服务器，并将锁模式改为p f i v m e r e a d ，还要将此变化通知 服务器。提交时，服务器判断客户是否可以继续完成其提交过程，还是因为修改了其它客 户所读对象要阻塞。服务器还要将锁表里的锁信息改为p r i v a t e r e a d 。如果客户是修改了 p r i v a t e 。r e a d 页，则服务器检查是否还有其它客户以s h a r e d r e a d 模式缓存该页，如果有则向 其发送回调消息。客户只要在服务器收到了所有的回调消息回应后才允许提交。最后服务 器将日志写到稳定存储器，并通知其它等待事务继续。 a a c c 是这集中算法中性能最好的一种，由于采用异步方式，它的阻塞时间较短，而 它的撤销率相比a o c c 却要低，与c b l 相当。 2 3c l i e n t s e r v e r 系统下的恢复技术 在c l i e n t s e r v e r 结构数据库管理系统中，日志是在客户端生成的。但是如果服务器不 统一存储客户生成的日志，在恢复时就需要依赖客户。虽然将日志存储在客户的本地磁盘 中可以减少服务器的工作量，但是在绝大多数c l i e n t s e r v e r 结构d b m s 中，这样做都是不 可接受的，因为这要求安全性相对较高、可信赖的服务器在进行服务器失效恢复时要依赖 不可靠的客户【1 2 j 。 如果服务器管理日志磁盘，则客户可以仅返回已修改页( w h o l e p a g el o g g i n g ”】) 。返回 已修改页和日志记录( a r i e s c s a l 6 方法) 或只返回日志记录和已修改的页中一个 ( r e d o a t - s e r v e r 【3 7 1 ) 。这几种方法都各有优缺点。目前应用比较广泛的是r e d o a t - s e r v e r 和 a r i e s c s a 方法。 下面我们首先介绍一些在设计c l i e n t s e r v e r 数据库系统的恢复策略时需要用到的相关 技术。 2 3 1 缓存管理及日志写方法 1 服务器缓存管理 服务器缓存是客户端与服务器进行数据交互的地方，关系着正常的事务处理。服务器 缓存管理器所使用的管理缓存的方法直接关系到整个c l i e n t s e r v e r 系统的恢复和执行。主 要存在以下方法( 见文献 6 】) ： s t e a l 方法：服务器缓存管理器允许将未提交事务所修改的页写到稳定存储器中； n o s t e a l ：与上面相反： f o r c e 方法：缓存管理器在提交事务时强制将事务所修改的页写到稳定存储器中： 毒 n o f o r c c ：与f o r c e 相反； 一一般缓存管理器都是选用前两者之一与后两者之一相结合的方法来管理缓存。 并发控制i 办议负责保持a c i d 事务的一致性利隔离性，而恢复协议负责维持事务的原 子性和持久性。在重启恢复阶段，。为保留原子性而将已撤销事务所造成的影1 9 自去除的过程 第1 5 页 国防科学技术人学训f 究生院学位论文 就是u n d o ，而为保持持久性而重新设置将已提交事务的影响的过程则成为r e d o 。 如果服务器缓存管理器使用s t e a l 方法，在重启恢复过程中就需要进行u n d o 过程：否 则u n d o 仅在事务回滚时才用到。如果服务器使用n o f o r c e 方法，在重启恢复时就需要进行 r e d o ，否则是不需要的。因此，我们可以判定缓存管理器所使用的方法可以决定使用何种 重启恢复协议。表2 2 列出了在何种缓存方法下使用何种重启恢复协议。s t e a l 和n o f o r c e 相结合的方法对缓存管理器无任何限制，非常适合于平常进程，a r i e s 就是采用此种方法。 客户和服务器的缓存管理器都使用l r u ( 1 e a s t r e c e n t l y u s e d ) 方法来进行页替换。当 缓存满或对缓存页有特殊需求时，替换最近最少使用的页。 为了能够保证c l i e n t s e r v e r 数据库系统的正确恢复，客户和服务器缓存管理方法的选 择需要慎重。 表2 2 缓存管理方法与重启恢复 b u 虢rp o l i c yn e e d e dr e s t a r tr e c o v e r yp r o t o c o l s t e a la n dn o f o r c e u n d oa n dr e d o s t e a la n df o r c eu n d oa n dn o r e d o n o s t e a la n dn o f o r c e n o u n d oa n dr e d o 2 w a i l 协议 恢复协议负责维持a c i d 事务的原予性和持久性。因此，为了能够正确恢复，服务器 使用w a l ( w r i t e a h e a d l o g g i n g ) 协议【5 】f 4 5 1 。这样是为了保证在系统崩溃时