（计算机科学与技术专业论文）数据库离线并发控制技术研究.pdf

硕i j 学位论文 第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 b m s 资源利用的最大化。然而， 当多个用户程序并发存取同一个数据元素时，如果不加以控制就可能破坏整个数 据库的一致性。因此，d b m s 的并发控制机制非常重要。随着数据库技术在现代 组织中得到广泛应用，数据库应用开发在软件开发的比重逐步提高，随之而来的 问题也越来越突出。由于不合规范的设计和不良的编码风格，人们在编写事务的 时候经常将不合理的查询操作组合到一个事务中去，更糟糕的是可能将一个完整 的事务拆分成两个或多个事务，这种隐含的错误将直接导致并发失败，d b m s 的 并发控制机制不能解决这类问题。我们以前往往重视对数据库并发控制的研究， 锁方法、时戳方法和乐观方法等并发控制技术都可以保征事务并发安全地执行。 但数据库离线并发方面的测试和控制仍然处于空白。我们从来没有真正对数据库 应用系统中事务的业务逻辑进行考虑，而是简单地将事务提交给d b m s 进行处理。 d b m s 以不同的顺序串行执行事务可能会产生不同的结果，但通常不会导致数据 库处于不一致状态，所以被认为都是正确的。然而在实际应用中，即使所有的事 务都以串行化的方式运行，得到的结果往往与所期望的不符，即串行执行事务产 生的结果可能是错误的，这就产生了离线并发问题。随着对数据的安全性和精准 性r 益升温，离线并发冲突的测试和控制也需要独立出来进行符合自身特点的处 理工作。 1 2 国内外研究发展现状 并发控制在多用户的模式下是十分重要的，目前国内外对数据库并发控制的 研究有很多，但基本上都停留在以下两个方面：一是封锁机制，另一是可串行化 调度，但是关于离线并发的事务处理还处于起步阶段。数据库同步的问题使得检 测离线并发变得非常困难。对一个存在并发冲突的数据库应用程序，即使执行的 是同一个测试用例，每次生成的数据库状态可能都不致。离线并发通常都与业 务逻辑有关，本质原因是数据不一致，通常的并发解决方法一般都从两方面入手： 数据库离线并发控制技术研究 1 禁止出现数据不一致的情况。 用户访问数据库时，数据库系统采用加锁机制，把数据库中相关数据锁起来， 不允许其它进程修改，当业务事务完成后再释放锁。把资源变成独占式的，从而 保证数据一致性【i 】。系统事务也就是这个原理，其锁是数据库底层维护的。这种 方式会造成不灵活，降低并发性，因为当一个进程执行某个业务事务时，其他进 程都不能进行相关的操作。 2 允许数据不致，但数据更新时要进行一致性检查。 从数据库中读出一批初始数据，依据这些数据做了一系列的操作，当把操作 结果更新到数据库时，先检查数据库中那“同一批一初始数据是否已经发生了变 化，如果发生了变化，根据业务需要，进行一定的处理。这种方式并发性强，比 较灵活，而且是不加锁的，这就避免了不少麻烦问题，实现起来要简单一些。简 单考虑，检查数据致性时，可以检查数据库中数据和内存中数据的值是否相同。 但如果数据量较大，这种检查恐怕效率很低，其次一致性检查要考虑粒度问题【2 3 】。 这种方式的缺点是，当提交更新时才会发现不一致，以至于提交之前的所有 操作可能都变得无效。例如，用户先从数据库中读出一些初始数据，然后做了大 量的修改或录入工作，最后提交时系统检查到数据不一致问题，结果提交失败。 第一类方法被称为悲观并发控制方法，第二类方法被称为乐观并发控制方法。 这两种方法都有着各自的缺点，而且对测试人员的要求很高，处理效率低下。 y d e n g 深入研究探讨了离线并发问题，指出离线并发问题的产生是因为不 同的事务可能直接或间接对同资源进行了访问，如果数据库事务管理器按照某 一调度表去执行事务，那么就有可能发生离线并发问题【4 1 。他依据上述思想，结 合数据流分析方法，设计并实现了t c f g 算法来检测数据库是否存在离线并发的 风险。 1 3 本文的研究工作 在详细分析了数据库应用程序的测试流程基础上，研究了数据库系统基于锁 的并发控制实现机制，包括锁的类型、模式、转换以及基本操作等。并在此基础 上，熟悉掌握程序的控制流图，分析事务内部的数据流图，了解离线并发冲突的本 质原因，本文研究主要内容有以下几点： ( 1 ) 研究现有的事务调度策略及冲突解决方法 并发控制是在多用户的环境下，对数据库并发操作进行规范的机制。本文分 析了三种并发控制的实现方法，即封锁、时间戳和乐观控制方法。并重点分析了 基于锁的并发控制的基本思想。 ( 2 ) 熟悉掌握t c f g 算法 了解数据库应用程序测试的流程，熟悉它的适用范围、工作机制，灵活应用 2 硕i j 学位论文 它来进行实际的测试，充分利用它的生成结果为离线并发控制做好前提准备。 ( 3 ) 设计并实现离线并发冲突控制器 建立离线并发冲突控制器的体系结构，离线并发冲突控制器由客户代理、请 求响应、队列管理、数据管理、事务访问等五个模块组成。通过模块问的协调合 作，有效地处理系统可能出现的离线并发冲突。 本文的创新点如下： ( 1 ) 提出了一种数据库离线并发冲突预防算法 在离线并发冲突控制器中置入一个冲突预防算法，该算法主要是系统在运行 状态下正确地判断事务是否会引发离线并发冲突，并能决定是否对系统的事务调 度策略做出调整。 ( 2 ) 设计与实现了数据库离线并发冲突控制器 通过分析离线并发冲突的特点，设计并实现了离线并发冲突控制器。该离线 并发冲突控制器运行在应用程序客户端及数据库服务器之间，所有的事务访问请 求都通过对离线并发冲突控制器的访问代理来实现，将并发和共享的问题解决转 移为事务调度处理，通过访问调遣，合理地安排事务调度运行，通过避免冲突调 度表的执行来降低离线并发的风险。由于每个事务都经过离线并发冲突控制器的 预处理，事务在提交f i 进行冲突判断，避免了因离线冲突而引发的事务撤消，有 效地降低了数据库离线并发冲突的风险。 1 4 小结 本章对本文研究背景以及对现代社会的重要意义做了说明，接着阐述了数据 库离线并发控制技术的国内外研究现状以及相关的研究中存在的一些问题，最后 论述了本文的主要研究内容及创新点。 3 数据席离线并发控制技术研究 第2 章数据库并发控制 2 1 数据库事务概论 事务是数据库并发控制的单位。所谓“事务 是指一系列由单个用户或应用 程序提交的数据库操作，这些操作是一个不可分割的整体。事务通常由高级数据操 纵语或编程语言( 如s q l 、c o b o l 、c 、c + + 或j a v a ) 书写的用户程序的执行所引 起，并用形如b e g i nt r a n s a c t i o n 和e n dt r a n s a c t i o n 的语句( 或函数调用) 来界定。事务 由事务开始( b e 西nt r a n s a c t i o n ) 与事务结束( e n dt r a n s a c t i o n ) 之间执行的全体操作组 成【5 1 。 2 1 1 事务的特点 事务具有4 个基本特性：原子性( a t o m i c i t y ) 、一致性( c o n s i s t e n c y ) 、隔离性 ( i n d e p e n d e n c e ) 、永久性( d u r a b i l i t y ) ，简称a c i d 特性1 6 】。 ( 1 ) 原子性：即事务要么全部执行，要么全部不执行。 ( 2 ) 持久性：即一旦一个事务执行后，即使以后出现故障，系统也必须保证其结 果不丢失。 ( 3 ) 串行性：若干个事务并行执行，其结果必然与它们以某个顺序串行地执行 的相同。 ( 4 ) 隔离性：一个尚未完成的事务在提交前不能向其它事务提供其结果。 2 1 2 事务的隔离级别 事务准备接受不一致数据的级别称为隔离级别。数据库引擎支持4 种隔离级 别【7 ，8 】： ( 1 ) 未提交读( r e a du n c o m m i t t e d ) ：执行脏读或o 级隔离锁定，这表示不发出 共享锁，也不接受排它锁。 ( 2 ) 提交读( r e a dc o m m i t t e d ) ：指定在读取数据时控制共享锁以避免脏读，但 数据可在事务结束前更改，从而产生不可重复读取或幻象数据。 ( 3 ) 可重复读( r e p e a t a b l er e a d ) ：锁定查询中使用的所有数据以防止其他用户 更新数据，但是其他用户可以将新的幻象行插入数据集，且幻象行包括在 当前事务的后续读取中。 ( 4 ) 可串行读( s e r i a l i z a b l e ) ：在数据集上放置一个范围锁，以防止其他用户在 事务完成之前更新数据集或将行插入数据集内。 隔离级别与并发性是互为矛盾的：隔离程度越高，数据库的并发性越差；隔 4 硕。 ：学位论文 离程度越低，数据库的并发性越好。一般说来，在高隔离级别下发生的并发问题 同样会在低隔离级别下出现。可串行化( s e r i a l i z a b l e ) 级别提供最严格的事务隔离， 通常作为多个事务执行的正确性准则【9 1 。更精确地说，多个事务的某个执行过程 是正确的，当且仅当其是可串行化的( 如果多个事务的某个执行过程与同样的这些 事务的某个串行执行过程产生的结果相同，则称其为可串行化的) 。 2 1 3 事务和调度器 即使各个事务都能保持状态的正确性，而且也没有发生任何故障，并发事务 之间的互相影响还是可能导致数据库状态的不一致。不同事务中各个步骤的执行 顺序必须以某种方式来进行规范。控制这些步骤的功能是由d b m s 的调度器模块 实现的，保证并发执行的事务能保持一致性的整个机制称为并发控制机制。 当事务请求对数据库中的元素进行读写时，这些请求被传递给调度器。在大 多数情况下，调度器将直接允许执行读写操作。( 如果所需数据库元素不在缓冲区 中就首先调用缓冲区管理器) 。但是在某些情况下，立即执行请求是不安全的。调 度器必须推迟请求的执行；有的并发控制机制中，调度器甚至可能回滚发出该请 求的事务。调度器的作用如图2 1 所示。 事务管理器 1 r f 调度器 1r 2 2 数据库并发控制 图2 1 事务调度器 缓冲区 所谓并发控制就是要用正确的方式调度并发操作，避免造成数据的不一致性， 使一个用户事务的执行不受其它事务的干扰，其主要目标是保证数据库数据的一 致性，它解决的主要问题是：当多用户同时读写相同数据时，系统必须做出协调， 保证结果的正确性和数据库的完整性，并尽可能地提高并行性。对于多用户系统， 数据库操作的并发问题很常见，造成的错误如数据丢失、读取错误数据等。究其 本质原因其实是数据不一致：一个进程读入内存中的数据和数据库中的“同一批 数据库离线并发控制技术研究 数据在某一时刻已经不一样了( 可能数据库中的数据被另外一个进程修改了) ， 但程序并不知道，于是造成各种错误。因此对于多个用户同时使用数据库的多用 户系统，必须存在一个并发控制机制来协调并发存取数据的活动。有3 种并发控制 技术可以保征事务并发、安全地执行，它们是封锁技术、时间戳排序方法、乐观 控制方法。其中封锁技术和时间戳排序是保守的方法，它们一旦发现某事务与其 他事务发生冲突，便延迟该任务的执行。而乐观控制方法仅在事务提交时才检查 冲突。 2 2 1 锁式并发控制 1 基本策略 传统的锁式并发控制协议通过互斥地访问数据项来保证可串行化。其基本思 想是，当一个事务需要对某个数据项进行存取之前，它必须先获得相应的锁。当 一个数据项被一个事务t j 锁住时，另一个事务t i 在随后的某时刻请求加一个冲突 的锁时，t i 就必须等待t ；释放锁，或者天折t i 或t j 。 锁的种类很多，可以分为共享锁、排它锁、谓词锁以及粒度锁等等【1 0 】。基于 锁式并发控制的一个最通用的协议是两阶段锁协议【1 1 ，12 1 。 2 主要缺陷 显然，基于锁的协议是不适合于长寿事务的并发控制的。在基于锁的协议下， 一个长寿事务可能长时间( 几个小时甚至几天) 的保持一个锁，若采用等待技术， 这将导致等待这个锁的事务产生不可容忍的延迟。若采用夭折的技术，又会导致 大量的工作丢失。因此纯粹采用锁式的并发控制方法不适合于长寿事务系统。 2 2 2 时间戳排序 1 基本策略 时间戳排序是一种事先规定好事务执行顺序的并发控制协议【1 3 】。其基本思想 是，对每一个事务t 按事务开始的顺序依次从小到大赋予一个时间戳t s ( t ) ，时间 戳可以用系统内部时钟或一个逻辑计数器来实现。每个数据项有两个与时间戳相 关的属性m r t s 和m w t s 。分别表示成功读取该数据项的所有事务中的最大的时间 戳和成功写入该数据项的所有事务中的最大的时间戳。在事务进行读写操作时按 以下规则进行处理： 1 ) 事务t i 发出r e a d ( x ) 请求时： 若t s ( t i ) m w t s ( x ) 则t i 读取x 的值，并以t s ( t i ) 和m r - t s ( x ) 两者间较大的值更新 m r t s ( x ) 。 2 ) 事务t i 发出w r i t e ( x ) 请求时： 若t s ( t i ) m r t s ( x ) 或者t s ( t i ) 的所有数据元素满足偏序。如果d i _ d j ，则任 何既访问d i 又访问d i 的事务必须首先访问d i ，然后才访问d j 。这为不同于2 p l 来管理 锁提供了重要条件。 在树形协议事务中必须遵从以下规则： ( 1 ) 事务的第一个锁可以在树的任何结点上； ( 2 ) 只有事务当前在父结点上持有锁时才能获得后续的锁； ( 3 ) 结点可以在任何时候解锁； ( 4 ) 事务不能对一个它已经解锁的结点重新上锁，即使它在该结点的父结点上 仍持有锁。 2 5 小结 本章主要对本课题研究所需要的相关知识，以及相关技术细节进行了概述。 首先介绍了数据库的事务及其特点，接着分析了常见的并发控制技术中使用的基 本策略及其存在的缺陷，通过对可串行化调度及死锁处理的学习为数据库离线并 发冲突的处理打下基础。 1 0 顶十学位论文 第3 章数据库离线并发的测试 3 1 软件测试技术 软件测试是随着软件工程的建立而产生的一个软件活动，软件测试的概念发 展比较迅速，目前，国际上已对软件测试形成一个共识：软件测试就是在软件投 入使用前，对软件的需求分析、设计规格、说明和系统编码的最终复审。由此可 见，软件测试的对象不仅仅是程序，需求规格说明、概要设计、详细设计、源程 序等都是软件测试的对象【18 1 。 软件测试应该是贯穿整个软件开发生命周期的测试。测试用以保证对需求和 设计理解的正确性、表达的正确性、实现的j 下确性以及运行的正确性，任何环节 出现了问题都极可能对软件产生致命的影响，我们要突破原来对测试的理解，着 眼于软件整个生存期，特别是着眼予软件需求分析、设计规格说明和编码阶段， 重视其测试工作，以确保软件的质量。 3 1 1 软件测试的类型 黑盒测试和白盒测试是广泛使用的两种测试类型。 ( 1 ) 黑盒测试 黑盒测试又称功能测试。黑盒测试的基本观点是：任何程序都可以看作是从 定义域映射到值域的函数。该观点将被测程序看作一个关闭的黑盒子，里面的内 容对测试人员而言是未知的。在用黑盒测试方法设计测试用例时，测试人员所使 用的唯一信息就是软件的需求说明书，在完全不考虑程序内部结构和内部特性的 情况下，只依靠被测程序输入和输出之间的关系或程序的功能来设计测试用例， 推断测试结果的正确性，即所依据的只是程序的外部特性。 ( 2 ) 白盒测试 白盒测试又称结构测试，或者又叫基于程序的测试。白盒测试将被测程序看 作一个打开的盒子，测试人员可以看到被测的源程序，可以分析被测程序的内部 构造。此时测试人员可以完全不考虑程序的功能，只根据其内部构造设计测试用 例。 ( 3 ) 黑盒测试与白盒测试的比较 黑盒测试和白盒测试是两种完全不同的测试方法，它们的出发点不同，反映 了事物的两个极端。它们各有侧重，都有峰定的理论拥护者。r o b e r tp o s t o n 【1 9 1 认 为：“白盒测试自2 0 世纪7 0 年代以来一直在浪费测试人员的时间一它不支持良好 的软件测试实践，应该从测试人员的工具包中剔除 ，而e d w a l dm i l l e r 【2 0 】贝0 认为： 数据库离线并发控制技术研究 “如果能达到8 5 或更好的分支覆盖率，那么白盒测试能识别出的软件故障，一 般是黑盒测试能找出的故障的两倍 。事实上，黑盒测试和白盒测试在测试实践 中都非常有效而且都很实用，两者互相补充。 黑盒测试基于外部规格说明，它根据需求说明书设计测试用例，不涉及程序 的内部结构。因此，黑盒测试有两个显著的优点：第一，黑盒测试与软件具体实 现无关，所以如果软件实现发生了变化，测试用例仍然可以使用。第二，设计黑 盒测试用例可以和软件实现同时进行，因此可以压缩项目总的开发时间。然而， 黑盒测试的缺点是需求说明书无法保证其完全正确。如果程序的外部特性本身有 问题或者需求说明书的规定有误，例如说明书中规定了多余的功能或是漏掉了某 些功能，黑盒测试则无法进行判断。另一方面，白盒测试只根据程序的内部结构 进行测试，而不考虑其外部特性。白盒测试要求对被测程序的代码实现一定程度 的覆盖。测试人员可以严格定义要测试的确切内容，明确提出要达到的测试覆盖 率，以减少测试的盲目性。如果要求被测软件“做了所有它该做的事，而没有做 一点它不该做的事【2 1 1 ，就需要把黑盒测试与自盒测试结合起来使用。 3 1 2 测试用例设计 测试用例是软件测试的核心。每个项目都需要一套优秀的测试方案和测试设 计方法，来保证以最少的人力和资源投入，在最短的时间内完成测试并发现软件 系统的缺陷，保证软件的优良品质，因此它是测试工作的指导，是软件测试的必 须遵守的准则，更是软件测试质量稳定的根本保障。 测试用例是指对一项特定的软件产品进行测试任务的描述，体现测试方案、 方法、技术和策略，其内容包括测试目标、测试环境、输入数据、测试步骤、预 期结果、测试脚本等，并形成文档【2 2 1 。编制测试用例需要遵循以下具体做法： ( 1 ) 测试用例文档模板 编写测试用例文档时应有文档模板，须符合内部的规范要求。测试用例文档 将受制于测试用例管理软件的约束。软件产品或软件开发项目的测试用例一般以 该产品的软件模块或子系统为单位，形成一个测试用例文档。 ( 2 ) 测试用例的设置 早期的测试用例类似功能清单，是按功能设置用例。后来逐步演变为按功能、 路径混合模式设计测试用例。按功能测试是最简捷的，按用例规约遍历测试每一 功能。而路径分析最大的优点是在于可以避免漏测试。但路径分析法也有局限性， 比如一个稍微复杂的模块常常会有几十到上百条路径，因此需要根据实际情况进 行选择。 ( 3 ) 设计测试用例 测试用例可以分为基本事件、备选事件和异常事件。基本事件的测试用例应 1 2 硕l ：学位论文 包含所有需要实现的需求功能，覆盖率达1 0 0 。设计备选事件和异常事件的用例， 则可以采用常用的基本方法：等价类划分法、边界值分析法、错误推测法、因果 图法、逻辑覆盖法等。在实际工作中，需要灵活运用各种基本方法来设计完整的 测试用例。 3 1 3 软件测试覆盖准则 软件测试覆盖准则是用来判定测试用例是否充分的重要依据。测试覆盖分为 逻辑覆盖、功能覆盖和需求覆盖等，其中，逻辑覆盖准则是以程序内部的逻辑结 构为基础设计的白盒测试用例，要求对被测程序的逻辑结构有清楚的了解。逻辑 覆盖又可分为语句覆盖、判定覆盖、条件覆盖、判定条件覆盖及路径覆盖等。 语句覆盖要求设计若干测试用例，运行被测程序，使程序中的每个可执行语 句至少被执行一次。与其他几种逻辑覆盖相比较，语句覆盖是比较弱的覆盖准则。 判定覆盖要求设计若干测试用例，运行被测程序，使得程序中每个判断的取 真分支和取假分支至少执行一次，即判断的真假值均要被检测。判定覆盖又称为 分支覆盖。 条件覆盖要求设计若干测试用例，执行被测程序，使得程序中每个判断的每 个条件的可能取值至少被执行一次。 判定条件覆盖要求设计足够的测试用例，执行被测程序，使得判断中每个条 件的所有可能取值至少被执行一次，同时每个判断的所有可能判断结果也至少被 执行一次。 路径覆盖要求设计足够多的测试用例，覆盖程序中所有可能的路径。在实际 问题中，要在测试中覆盖所有的路径是不可能实现的，只能把覆盖的路径数压缩 到一定限度内，有选择地测试程序中有代表性的路径。 此外，还有数据流测试覆盖准则，包括定义覆盖、引用覆盖、定义引用覆 盖准则等；面向对象的类覆盖和方法覆盖准则【2 3 】；以及针对黑盒测试的功能覆盖、 需求覆盖和场景覆盖准则等。 3 2 数据库测试概述 我们知道，关系数据库应用m i s 系统的最大特点就是管理和处理数据库表中 的大规模数据。当我们为用户开发出一个信息管理系统交付用户使用之前，通常 测试人员要对数据库信息管理系统进行测试。在测试时，首先要给应用数据库中 的一些表构造符合一定条件的测试用例。“关系数据库表测试用例 的构造与生 成在整个关系数据库应用系统测试中占据重要和特殊的地位，它是进行整个关系 数据库应用系统测试的基础和前提，是整个数据库应用系统测试用例构成的重要 组成部分。下面简要叙述数据库的一些测试标准、工具及相关测试技术。目前这 1 3 数据库离线并发控制技术研究 些测试基本都是确认性、标准符合性测试，基本上是黑盒测试。 3 2 1 功能确认测试 采用黑盒测试方法，依据数据库管理系统的用户手册、系统管理员使用手册、 程序员参考手册等对数据库管理系统的产品化进行测试。可以通过使用图形化管 理工具、交互式s q l 工具等对数据库管理系统的功能和产品化程度进行测试。 测试项目可以分为可扩展性、可靠性、安全性、大数据量、管理工具、用户 文档等各个方面的测试。 具体来说，可扩展性考察对数据库跨平台的支持等；可靠性考察数据库备份、 故障恢复、系统运行稳定性、数据库复制等方面；安全性包含了用户及口令管理、 授权和审计管理；大数据量包含了对复杂数据的支持，以及数据量( 元组最大长度、 单表最大容量、支持单表数据跨磁盘存储等) 的测试；对管理工具的测试包含了图 形化管理工具的安装配置、数据库存储管理工具、模式对象( 表、索引、视图、约 束、存储过程、触发器) 管理、非模式对象( 用户、角色、权限、审计选项等) 的管 理、交互式查询工具的易用性和稳定性、性能监测与调优、数据迁移工具、作业 管理等；同时对用户文档的检查也是测试必不可少的部分，包括用户手册是否 全面，内容是否完整、内容与软件实际功能的一致性程度、用户手册对关键操作 的图例说明及易理解程度，是否提供了联机手册等。这也就是验证数据库管理系 统对其所声明的功能的确认性测试。 3 2 2o d b c ，j d b c ，o l ed b 测试 随着客户服务器模式成为数据库应用开发的主流，数据库调用级接口得到了 很大的发展，出现了新的标准o d b c ( o p e nd a t a b a s ec o n n e c t i o n ) ，j d b c ( j a v a d a t a b a s ec o n n e c t i o n ) 和o l ed b 。这些标准规定了数据库客户端基于s q l 访问数据 库服务的接口，目前已经得到数据库应用集成开发环境和数据库管理系统广泛支 持。依照相应的标准，进行标准符合性测试。 l 、o d b c 参照测试标准有：m i c r o s o f to d b c 3 os d k 和m i c r o s o rd a t a a c c e s s c o m p o n e n t 2 6s d k 。需要进行的测试包括：a p i 函数和数据类型支持性测试、数 据库连接功能测试、基本功能测试、元数据功能测试、诊断函数功能及错误状态 码测试、游标功能测试、事务功能测试、表量函数测试、o d b cs q l 语法测试等。 2 、j d b c 参照j d b c 规范3 o ，测试工具可采用s u n 公司提供的j d b ca p it e s t s u i t e l 3 1 作为基本测试工具和测试用例。它包括四种运行环境下的5 2 8 8 个测试用例。 3 、o l ed b 标准为m s d n 2 0 0 1 ( o c t ) 中的o l ed b 2 7 。测试工具采用m d a cs d k 2 7 中附带 1 4 硕1 ：学位论文 符合性测试工具。o l ed b 标准符合性测试包括了o l ed b 接口测试和o l ed b c u s u m e r 测试( a d o ) 。 3 2 3 数据库性能评价标准 性能一直是数据库管理系统研究的核心问题之一，2 0 世纪8 0 年代开始人们曾 提出许多不同的性能评价标准。 1 9 8 3 年提出的w i s c o n s i n 性能测试标准是最早的一个全面测试数据库管理系 统性能的标准。它使用的是单一用户单一服务器模式，通过3 2 种查询( 包括查询、 连接、映射、集合以及更新操作) 来测量一个数据库管理系统性能。在此基础上， 19 8 9 年提出了a s 3 a p ( a n s is q ls t a n d a r ds c a l a b l ea n dp o r t a b l eb e n c h m a r k ) 性能 测试标准。 2 0 世纪8 0 年代中后期，为了统一数据库管理系统性能评价标准，成立了t p c ( t r a n s a c t i o np r o c e s s i n gp e r f o m a n c ec o u n c i l ) 组织来规范数据库管理系统的性能评 价标准，目前成为评价数据库性能的事实标准。 作为一个非盈利性的国际数据库性能测试组织，t p c 制定并维护了四个标准： t p c c 数据库在线事务处理标准：t p c h ，决策支持中自由查询标准；t p c w ， 基于w e b 的电子商务标准；t p c r ，决策支持中业务报表标准。 经过多年发展，t p c 。c 版本5 3 【2 4 】己趋于完善，并被广泛接受，目前已成为数 据库供应商向用户展示产品技术进展的重要指标。t p g c 模拟了一个大型批发销 售公司的业务过程。该公司拥有多个地理上分布的仓库，每个仓库向l o 个街区供 货，每个街区有3 0 0 1 个用户。该公司的每个仓库维护1 0 万条公司销售的商品记录。 t p c c 标准要求在被测数据库管理系统中，根据仓库数量( 即数据规模) 按照一 定的比例完成5 种事务( 包括新订单处理、支付、订单查询、发货和库存查询) 。被 测系统平稳运行2 小时后，取其平均每分钟处理的新订单数( 即t p m c 值) 作为被测 系统的性能指标。 t p c c 还提供了a c i d 测试。该测试独立于性能测试，但是采用和性能测试相 同的数据发生机制，相同的调用函数。 3 2 4 数据库应用程序测试 d c h a v s 提出了一个测试数据库应用程序的框架【25 1 。该文通过分析在测试数 据库系统时会出现的问题，提出了一个测试数据库应用程序的方法。它认为，在 数据库中，除了用户输入和系统输出，用户操作执行前后的数据库状态起了很大 的作用。基于这个框架，介绍了一个测试工具a g e n d a 【2 引，a g e n d a 中包含五 个组件：解析器、状态生成器、输入生成器、状态验证器、输出验证器。它自动 生成满足约束的有意义的数据来填充数据库，通过分析应用程序结构来生成测试 用例，能够自动检查操作后的数据库状态，验证数据库的输出是否正确。 1 5 数据库离线并发控制技术研究 3 3 数据库事务测试 通过上一节的概述，我们了解到，数据库测试有功能确认测试、s q l 标准符 合性测试、o d b c j d b c o l ed b 测试、数据库性能测试、事务的a c i d 属性测试 等。事务处理是数据库管理系统的一个基本功能。它主要用于维护数据的一致性， 支持多用户的并发访问，使用户可以可靠地查询和更新数据库。一般来说，用户 对数据库系统的访问都是通过事务来完成的。保证事务a c i d 特性是事务处理的重 要任务。a c i d 属性是相互关联的，测试其中的任意一个属性都可能会揭露出其他 属性的某些问题。 3 3 1 数据库事务测试基准 比较完整的提出了事务a c i d 测试的基准是t p c c 【2 7 1 。 在3 2 5 节中，我们提到，t p c c 除了性能测试，还提供了a c i d 测试。该测试 独立于性能测试，但是采用和性能测试相同的数据发生机制，相同的调用函数。 我们在这里进行进一步的介绍。 t p c c 是衡量在线事务处理( o l t po n l i n et r a n s a c t i o np r o c e s s i n g ) 系统性能和 性能价格比的工业标准。它测试广泛的数据库功能，包括查询、更新和排队 m i n i _ b a t c h ( 袖珍型批处理) 事务。这一规范在关键领域十分严格，如数据库透明性 和事务处理隔离性。许多i t 专家把t p c c 作为“真实世界 o l t p 系统性能的一个 很好的指示器。 t p c c 测试标准的主要设计目标是： ( 1 ) 模拟包括更新操作和只读操作的多类型事务； ( 2 ) 模拟不同特征的事务处理； ( 3 ) 所有事务必须严格符合a c i d 特性； ( 4 ) 拥有复杂的数据结构和联系； ( 5 ) 采用多样的数据访问方式； ( 6 ) 模拟重负载下大数据库上的多用户并发操作。 t p c c 模拟一个批发商的货物管理环境。该批发公司有n 个仓库，每个仓库 供应10 个地区，其中每个地区为3 0 0 0 名顾客服务。在每个仓库中有10 个终端，每 个终端用于一个地区。在运行时，lo 宰n 个终端操作员向公司的数据库发出5 类 请求。由于一个仓库中不可能存储公司所有的货物，有一些请求必须发往其它仓 库，因此，数据库在逻辑上是分布的。n 是一个可变参数，测试者可以随意改变n ， 以获得最佳测试效果。 t p c c 测试标准还定义了5 种事务：订购( n e w o r d e r ) 、付款( p a y m e n t ) 、订购情 况( o r d e r - s t a t u s ) 、发货( d e l i v e r y ) 、库存情况( s t o c k l e v e l ) 。其中订购、付款、发货 等3 种事务为更新型事务，订购情况和库存情况是只读型事务，这5 种事务代表了 1 6 硕i j 学位论文 由订货、付款、发货到查询顾客订购情况和查询库存情况等组成的一个完整的商 业处理过程。 3 3 2 数据库事务测试方法 t p c c 认为，没有一种有限的测试能够证明a c i d 特性是被数据库管理系统充 分的支持的。然而，为了公正的做出报告，基于以上设计模型和5 种事务，t p c c 设计了一套对事务a c i d 特性的测试。它设置了一系列的测试，以观察数据库是否 满足事务的这些特性。它尽可能的测试a c i d 特性的各种情况。 具体测试方法是，它通过设置一些条件来测试每一种特性。 对于原子性特性测试，结合上述事务，设计了2 种测试方案来测试。 对于一致性特性测试，设定一个前提，假定初始状态的数据库处于一个致 性的状态。然后定义了1 2 种测试条件来指定t p c c 事务需要的数据库致性级别。 它认为一个数据库，必须满足所有的测试条件才能达到一致性。如果数据库是复 制的，那么每个副本都必须满足这些测试条件。测试步骤是：首先在初始状态下 通过验证这些测试条件是否满足来验证数据库的初始状态是否是一致的。然后执 行一些给定的事务操作，通过各种正常、异常的执行，最后验证一致性是否得到 满足。 对于隔离性特性测试，首先给出当前数据库事务通用的执行过程中各种异常 现象的术语定义，并据此确定隔离级别。然后为t p c c 中的每种事务定隔离需求， 并提出，必须在系统和应用程序级别都能够确保所需的隔离需求。这样需要定义 充分的条件来进行测试。t p c c 设计了9 种隔离性测试来验证事务的隔离性。 对于持久性特性测试，t p c c 认为，没有一个系统能提供完全的持久性。它 列举了可能会影响持久性的一些单一的错误情况，设计了持久性测试对各种错误 情况进行一一验证系统在这种情况是否提供了持久性的保证，并且在数据库得到 恢复之后还要使得所有的一致性条件仍然能够维持。 3 4 离线并发的检测 3 4 1 数据流分析 在执行程序时，数据信息沿控制路径流动。因此，理解数据流分析的一个预 备概念是程序控制流图( p r o g r a mc o n t r o l1 f l o wg r a p h ，p c f g ) 。一个程序的p c f g 是 一个具有单入口的有向图，其节点表示程序的一条或多条指令代码组成的一个程 序块，在一个程序块里代码是顺序执行的。有向边表示程序块之间的执行顺序或 控制路径。 通常一个p c f g 被表示成一个三元组【2 8 ，2 9 1 ，g = ( n ，e ，n o ) ，其中，n 表示节点 集合，e 表示有向边的集合，n o 表示p c f g 的入口节点。为了处理的方便，用自然数 1 7 数据库离线并发控制技术研究 作为这些节点的编号，即n = 1 ，2 ，n ) ，n o = l 。x i 】表示节点i 的数据流信息，记为 x io 在p c f g 中，如果( i ，j ) e ，则i 称为j 的直接前驱，j 为i 的直接后继。记这些直接 前驱和直接后继节点组成的集合分别为p r e d ( j ) 和s u c c ( i ) 。 在代码优化阶段，数据流分析主要关注的是这样两个集合，即i n 和o u t 集合。 这两个集合分别表示在基本块i 入口处和出口处所需数据流信息的集合。数据流分 析就是根据这两个集合在控制流经历基本块前后所含信息之差异来进行。这两个 集合并非完全独立，而是相互关联的。集合i n 和o u t 的函数关系因数据信息流向的 不同而不同。 3 4 1 1 控制流图 控制流图( c f g ) 【3 0 】是流图概念在程序语句级别的一个扩展，程序中每条语句 在控制流图中有相应的结点对应，在控制流图中用语句行号来代表。通常假设一 行只有一条语句，在控制流图对应的数据结构中通常为每个结点分配唯一的结点 号，以便区分一行有多条语句的情况，控制流图中的边通常表示程序中语句问的 控制流程。 控制流图是这样的一个有向图g ，它有唯一的入口结点s t a r t 和唯一的出口 结点s t o p ，每个结点至多有两个后继。通常假设有两个后继的控制流图结点有属 性“t ”( 真) 和“f ( 假) ，并且这些属性和结点的出边关联。进一步假设对于g 中的任意结点n ，分别存在一条从s t a r t 到n 的路径和从n 到s t o p 的路径。图3 1 中给出了程序片断及其对应的控制流图。因为是程序片断，这里省略了控制流图 的结点s t a r t 和结点s t o p 。 d 1 ：i = 锕+ 1 ： 艘j = 细： d 3 ：a = 5 ： 1 1d o d 4 ：- i + 1 ： d 5 ：j - j 1 ： c 1 ：i f ( a ，3 ) d 6 ：a = 6 ： d 7 ：i = 2 ： c 2 ：w h i i e ( i 1 0 ) ： ( a ) f b 图3 1 程序片断及其控制流图 1 8 数据库离线并发控制技术研究 ( a ) 前向流( b ) 后同沉 图3 2 前向流和后向流控制流图 ( 实线标识控制流虚线表示信息流) 3 4 1 4 数据流方程 上述( 3 1 ) 、( 3 2 ) 两式不仅反映了任意路径数据流分析中的聚合运算，还反映了 数据信息在基本块之间的传播方向。在数据流分析时，不仅要知道数据信息在基本 块之间的传播及使用，还必须知道数据信息在基本块内的传播及使用情况。下面对 任意数据流分析问题p 进行讨论。对某个基本块i ，i n i 】表示在i 的入口处问题p 的数 据信息，o u t 【i 】表示在i 的出口处问题p 的数据信息。在程序的运行过程中，在j l ，j 2 ， j m 内可能产生问题p 的新的数据信息和注销问题p 的部分数据信息，分别记为g e n i 】 和k i l l i 】。则这些集合之间有如下关系： d 甜力= g ，z f 】u ( 加 f 卜肪刀 枷 ( 3 3 ) 由( 3 1 ) 、( 3 2 ) 和( 3 3 ) 联立组成一个集合方程组( 3 4 ) ，这个方程组就是任意路径 的前向流数据流分析问题的数据流方程。关于数据流方程的解法，通常是采用迭代 法【3 2 ，3 3 1 ，迭代算法的时间复杂度在最坏情况下为o ( i n l 2 ) 3 4 1 ，其中in l 表示p c f g 中 的节点数。也存在效率比较高的数据流算法，基于流图结构的消去法，属于这类算 法有很多，如区间分析和t 1 t 2 分析法。这些算法要求程序流图是可归约的，虽然 对不可约流图施行节点分裂，可以将不可约流图化为可约流图。对此要付出很大的 代价，节点的分裂可能导致所有区域的节点总数呈指数增长。因此，对不可约流 图，不适宜用这种方法进行数据流分析。 r所 垆卜g 俐月( 3 4 )li = i、，。， id 甜f f 】= 舻，z 妇u ( 砌 力一肪研m 3 4 2 离线并发的定义 多个用户同时对某个数据库属性进行修改会违犯数据库一致性约束。为了使 单个用户在使用的时候不受其他用户的影响，相应的数据库操作应该被组合到一 数据库离线并发挡制技术研究 个客户a 和b 同时运行c h o o s e s e a t ( ) ，可能会发生如下的串形事务调度：a 运行 t l ，b 运行t 1 ，a 运行t 2 ，b 运行t 2 。程序预期的结果是将a v a i l 的值减2 ，但 实际上在执行完这个调度后a v a i l 的值仅仅减1 ，这就意味着在并发时出现了丢失 更新，从而导致程序出错。 例2 为仓库管理系统的一个片段，在事务t 3 中将客户ci d 订购的商品总值保存 在变量o lt o t a l 中。事务t 4 将o lt o t a l 追加到cb a l a n c e 上。事务t 5 向o r d e rl i n e 表插 入一个定单。如果两个客户a 和b 以同样的ci d 访问数据库，a 运行d e l i v e r y ( ) ，b 运行n e wo r d e r ( ) ，那么可能会发生如下的串形事务调度：a 运行t 3 ，b 运行t 5 ，a 运行t 4 ，这同样会导致并发时出现丢失更新。 由上面的例子我们可以看出，尽管所有的事务都是以串行化的方式运行，但 是数据库在并发的过程中仍然发生了错误，这是因为数据库管理系统只是简单地 进行事务处理，并没有考虑到事务内部的业务逻辑。在数据库应用程序开发中， 为了提高事务的并发度，人们往往喜欢将长寿事务拆分成许多短事务，这种做法 虽然提高了事务处理的吞吐量，但是却忽视了潜在的离线并发问题。数据库应用 程序是否存在离线并发问题? 串行事务以怎样的执行序列运行会导致离线并发? 怎样对离线并发问题进行处理? 这些问题都是本文所要讨论和解决的重点。 3 4 3t c f g 冲突检测算法 数据库同步的问题使得检测数据库并发变得非常困难，对一个存在并发冲突 的数据库应用程序，即使执行的是同一个测试用例，每次生成的数据库状态可能 都不一致。在一个数据库应用程序中，用户之间通常不存在直接的同步，当两个 用户同时读取或修改同一个数据元素时就有可能发生并发冲突。 一个最简单的可能会引发离线并发冲突的事务调度表可表示为 。其中t a 、t k a 代表a 应用程序实体中的事务t 。和t k ，t j b 代表b 应用程序实体 的事务t j ( t i 、t j 和t k 可以是相同的事务，每一个事务都可以通过进程i d 号以及事 务名称唯一标志) 。如果一个应用实体中的两个顺序事务t 1 和t 。能够访问同一属 性，并且在另一个应用实体中存在能够访问该属性的事务t j ，那么就存在冲突的 可能【4 1 。同样的，如果一个应用实体中的两个顺序事务t 1 和t k 定义或使用了同一 变量，并且在另一个应用实体中存在能够访问该变量对应属性的事务t j ，那么就 有可能存在并发冲突。两个事务能够直接或间接的访问同一属性，那么这两个事 务是相关的。 事务 和t j b 交替执行，t 1 、t k 、t j 为对同一属性进行读取或写入的相 关事务，所有组合以及冲突判定如表3 1 所示。 数据库离线并发控制技术研究 结点之间添加一条边，每个事务结点对应两个信息表g e n t k 】及k i l l 【t k 】，在表 中以 的形式记录了该事务所访问的属性( o p 代表操作类型，e l m 代表 数据库元素或者数据库变量) ，其中事务中所包含的s q l 语句被a g e n d a 的解析器 所解析，事务所访问的所有数据元素被保存在表x a c t _ r e a o w r i t e ，事务所定义和访 问的所有数据库标量被保存在表x a c u a