（计算机应用技术专业论文）内存数据库事务管理研究与实现.pdf

浙江大学硕士研究生毕业论文 摘要 删d b ( 内存数据库) 的研究近年来一直是国内外数据库领域研究的热点。内存 数据库在对实时性要求高的领域扮演了关键角色。但在删d b 研究方面还有许多 的难点需要攻克。本文对事务相关技术进行了研究，特别是对并发控制技术做了 深入的研究，对失败恢复机制也进行了一定的研究。并介绍了本项目组的删d b 事务管理的设计和实现。 本文首先回顾了内存数据库技术的发展，随着硬件的飞速发展，使用大容量 内存已经成为可能，使本来无法实现的设计成为可能，推动了内存数据库技术的 发展。由于内存数据库技术在处理实时事务方面相对传统磁盘数据库的性能优 势，内存数据库技术的研究成为了数据库研究领域的研究热点。 接着，本文设计了删d b 的总体架构，为了提高删d b 的性能在设计各个层次 进行了优化。在操作系统层对内存统一管理，加快了内存的分配和释放。然后介 绍了表管理设计和行管理的设计。经过充分的测试这种设计的性能能满足实际应 用的需要。 本文接着介绍了事务处理的相关概念和技术。由于数据贮存在内存中，在 删d b 中要保持数据的一致性和持久性相对磁盘数据库增加了不少难度。事务处 理主要包括并发控制和事务恢复这两个密切相关的技术。事务处理无论在传统磁 盘数据库中还是内存数据库中都是对性能起着决定作用的核心技术。 在研究了事务管理的相关技术后，对事务管理中核心的技术“并发控制”这 个专题进行了深入的研究。在并发控制方面的设计考虑的也主要是在对性能的影 响上。本文首先介绍了传统的并发控制技术，分别为基于锁、基于时间戳、基于 有效性检查三种并发控制技术，在综合考虑的效率和实现难度后，选择了删d b 的并发控制主要采取基于锁的并发控制技术。本文对锁表管理进行了深入研究并 提出了一些改进。 在前面研究的基础上，介绍了在项目实践中删d b 事务管理的设计与具体实 现本文对d b 事务相关的理论进行了系统的研究和总结，并探讨了今后的研究 方向。 关键词：内存数据库，事务管理，并发控制，同志管理 浙江大学硕士研究生毕业论文 a b s t r a c t i nr e c e n ty e a r s ，m m d b ( m a i nm e m o r yd a t a b a s e ) h a v eb e c o m em o r ea n dm o r e i m p o r t a n ti nt h ea r e ao fd a t a b a s er e s e a r c h m m d bp l a yak e yr 0 1 ei nt h e r e a l t i m es y s t e m sw h i c hn e e dh i g hp e r f o r 吣n c ea n dh i g hc o n c u r r e n c y t h e r e a r em a n yp r o b l e m st ob ei n v e s t i g a t e di nt h i sn e wa r e a i nt h i sp a p e rw e i n v e s t i g a t e di nt h et r a n s a c t i o nm a n a g e m e n tt e c h n o l o g y t h e nt h i sp a p e r d e e p l ya n a l y s e sc o n c u r r e n c yc o n t r 0 1t e c h n 0 1 0 9 y a n dw ea l s oi n t r o d u c e t h ed e s i g na n ds t r u c t u r eo fa 删d bs y s t e mw h i c hr e a l i z e ss o m eo ft h e s e t e c h n o l o g i e s f i r s t ，w el o o kb a c kt ot h ed e v e l o p m e n to f 狮d bt e c h n 0 1 0 9 y a sh a r d w a r e d e v e l o p e dr a p i d l y ，w ec a nu s eh i g h c a p a c i t yr 柚t or e a l i z et h ed e s i g n a t i o n o fm m d bw h i c hw a so n l yi np e o p l e sm i n d m m d bc a nb eu s e di nt h ea r e a w h i c hn e e d sc o p ew i t hr e a lt i m et r a n s a c t i o n sa n di nt h e s ea r e a sd i s k r e s i d e n td a t a b a s e sp e r f o r 朋a n e ec a nn o tm e e tt ot h en e e d so fa p p l i c a t i o n i nr e a l i t y s o 姗d bh a v eb e c o 嘴ah o ts p o ti nt h ea r e ao fd a t a b a s e r e s e a r c h t h e nw ei n t r o d u c et h eo v e r a l ld e s i g n a t i o no f l m d b f o rt h es a k eo f i m p r o v et h ep e r f o r m a n c eo f 舳b ， w eu s es o m et e c h n 0 1 0 9 yi na l m o s ta l l l e v e l so ft h ed e s i g 【1 a t i o n i nt h eo p e r a t i o ns y s t e m1 e v e l ，i no r d e rt o i 啊p r o v et h ep e r f o r m a n c eo fm a l l o ca n df r e em e m o r yt h es y s t e mm a n a g et h e m e m o r yo p e r a t i o nb yi t s e l f t h e nw ei n t r o d u c eh o wt od e s i g ni i l a n a g e m e n t o ft a b l e sa n dm a n a g e m e n to fr o 唧s a f t e rag r e a ta m o u n to ft e s t ，t h e p e r f o r 腿n c eo ft h i sm m d bs y s t e mc a nm e e tt h er e a l i t ya p p l i c a t i o n sn e e d s ab a s i cu n d e r s t a n d i n go ft h ei s s u e si n 哪d bs y s t e si sp r o v i d e da n d t h er e s e a r c he f f o r ti nt h i sa r e ai si n t r o d u c e d t h e nw ep r o v i d et h e o v e r v i e wo ft r a n s a c t i o ni i l a n a g e e n tw h i c hi n c l u d e sc o n c u r r e n c yc o n t r 0 1a n d r e c o v e r y 髓n a g e m e n t t r a n s a c t i o nm a n a g e m e n ti sak e yt e c h n 0 1 0 9 yw h i c h d o e sg r e a te f f e c ti nt h ep e r f o r m a n c eo fd a t a b a s es y s t e m 浙江大学硕士研究生毕业论文 目前，已有大量的对内存数据库的研究，研究包括：内存数据库并发控制技 术( c o n c u r r e n c yc o n t r 0 1 ) ，事务提交处理技术( t r a n s a c t i o np r o c e s s i n g ) ， 数据访问技术( d a t aa c c e s s ) ，查询处理和查询优化技术( q u e r yp r o c e s s i n g q u e r y0 p t i m i z a t i o n ) ，恢复处理技术( r e c o v e r y ) ，数据迁移技术( d a t a m i g r a t i o n ) ，负载均衡技术等各个方面。但是目前的理论比较丰富，但鲜有稳定 的适用性广的内存数据库产品，大多都还处于实验室研究阶段，工业化应用也只 局限于有献的几个领域，比如电信领域和金融领域。且多为平台相关的，应用相 关的数据库系统，无法适应广泛的应用需求。 本文的主要研究目标是：研究内存数据库的理论和体系，并将其应用到实际 产品开发中，同时经过大量的有效的测试来验证理论的可行性有效性。 1 2 论文组织 本文主要介绍了在项目实践中删d b 的设计与具体实现，对删d b 相关的理论 进行了系统的研究。本文主要做了以下的工作。在项目开发过程中阅读了国内外 大量的文献，对现有的内存数据库产品进行了研究，并充分借鉴了这些系统的优 点，根据项目的实际应用环境将这些优秀的思想和设计应用于删d b 产品中。针 对事务、并发控制等决定内存数据库性能的关键因素进行了深入的研究。 本文分为六章，图1 1 给出了论文的组织结构，其中： 2 浙江大学硕士研究生毕业论文 第一章绪论 上上 第二章相关研究综述 l 上 第三章m m d b 总体设计 上土 图卜l 论文的组织结构 第一章是绪论，简要介绍了研究的背景和目的、本文的研究思路和内容，以 及组织结构。 第二章对相关研究进行了综述。首先阐述了内存数据库的定义，为什么需 要内存数据库，以及内存数据库与磁盘数据库的区别这样的基本问题；然后介绍 了内存数据库研究的发展脉络和各种实时数据库技术的研究；接着介绍了内存数 据库技术的应用；最后分析了已有研究的缺点和不足。 第三章介绍了删d b 的设计和实现。删d b 设计包括了总体设计以及各模块 的具体的设计与实现。在此过程中提出了一些设计的问题和难点以及相对的解决 方案。由于本项目是与实际应用密切相关的，其最重要的目的为满足实际应用需 求，所以在设计上会进行相应的优化，在遇到设计问题时也会尽量从实际需求方 面考虑来加以解决。 第四章讨论了事务管理方面的问题，主要介绍了并发控制，并涉及了数据 3 浙江大学硕士研究生毕业论文 第2 章相关研究综述 2 1 内存誊羹霎藿雾羹羹 酎孽f 剥剽融耻雾! ! 罐澎蚕目凇啊1 溢：晌器甚审南镬嘏幅鞠曛赫搿罐黼雨崤 辄丽籀瑶鬟淄猫猫瀣舞等溘磷国滚港? 蕊烈掣邑鬃强萎钐泌懿j 铡的萃本珲 露；鍪懂慝烈嗯萼上爨霹。蛀警菇尉黜幽刮鸯出辜置强；芦舢薯葡星萝彰酎 辱氇i 缎啦踊滞幛j 掣e 蓼l 鹫型睡虱引嫩举嚣鄹越醚孵孜骗墼鍪婴讨，然后 对事务管理，锁表管理的设计和实现作了详细的论述。本章是 对第四章的理论研究的实际应用。 第六章总结了本文对m m d b 的相关技术的研究成果，事务处理的两方面并发 控制和恢复在本文都进行了较深入的研究，尤其在并发控制方面。在这些研究的 过程中我们发现了嗟奈侍庑枰n 颐亲鼋徊降难芯俊 4 x 浙江大学硕士研究生毕业论文 r a m 图2 一l 磁盘数据库结构 6 d l s k 浙江大学硕士研究生毕业论文 r a m 图2 2 内存数据库结构 d i s k 假设主数据库全在内存中后，删d b 在关系与索引结构、恢复策略、并发控制 等方面与d r d b 产生了很大的差异。 在删d b 系统设计时，广泛使用了现代操作系统提供的共享内存机制，系统初 始化时将整个数据库装入一片共享内存区，运行时，应用进程可以把整个数据库 或一部分映射到自己的虚地址空间进行直接访问。针对关系和索引数据全在内存 中这一特点，指针在数据结构和数据访问中被广泛的使用。 应用进程可以通过指针，也可以通过位置独立的数据库偏移量访问数据，无需 像d r d b 那样与缓冲区管理器交互。另外，由于指针长度固定，因此变长字段问题 可以很好解决。其次，若一个大的数据对象在数据库中多次出现，则内存中只需存 储一次，其它地方使用指针来引用。 浙江大学硕士研究生毕业论文 2 2 内存数据库发展和现状 数据库的发展开始于本世纪6 0 年代中期，由最初层次和网络数据库系统发 展到关系数据库系统，随着数据库的应用领域的迅速发展，国内外又出现了大量 的新的数据库技术，比如面向对象数据库系统，x m l 数据库。传统的关系型磁盘 数据库市场一直为o r a c l e 、i 蹦、微软占据前三甲，而在另一方面又有许多的像 m y s q l 这样的优秀开源数据库。 删加是可以归入实时系统的范畴。姗加的诞生本身在于实时应用需求的需 要而产生的在技术上可行的数据管理方案。实时系统是指事务具有时效性，即如 果事务不能在期望的时限内完成，其结果可能是无用的甚至是有害的。相应地， r t d b 是支持实时数据库应用系统，其事务执行具有强的实时性和可预测性，并 具有事务控制能力以获得高事务吞吐率的数据库管理系统。 删d b 的研究始于1 9 8 0 年，最初的目标就是要解决在电信、金融领域的关键 应用系统中，大规模内存数据的有效管理问题，有影响的研究项目有：i b m 公司的 s t a r b u r s t 可扩展d b m s 研究项目；a t tb e l l 实验室进行的d a l i 项目；以及 h p 公司支持开展的t i m e s t e n 通用内存数据库管理系统研究项目等。到1 9 9 0 年 代中后期，由于软硬件技术的进步，出现了很多可以配置更多内存、运行6 4 位操 作系统的计算机，将整个数据库的数据和控制信息全部装入内存在技术上的限制 已不存在，d b 技术逐渐成熟并走向商用市场。如l u c e n t 公司开发的通用内存数 据库系统d a t a b l i t z 就在5 e s s 交换机和实时计费应用s u n r i s e 等系统中被广泛 使用。 在开源领域也有一些正在研究阶段的内存数据库产品，例如应用于移动计算 的m o n e t 内存数据库系统，f a s t d b 的改进版g i g a b a s e 等数据库系统。这些开源数据 库对于内存数据库的发展产生了积极的推动作用。 2 3 并发控制技术现状 并发控制技术是数据库事务管理中最核心的技术，在数据库几十年的发展 中，并发控制技术被不停的研究，创新。形成了现在的以锁技术为主导，时间戳 和有效性检查并存的三大类并发控制技术。这三类并发技术仍在不停的发展，并 8 浙江大学硕士研究生毕业论文 相互融合，出现了一些混合的并发技术。 分布式数据库采用的并发控制技术基本沿袭关系型数据库，分为如下四类： 一基于锁的并发控制 - 基于时间戳的并发控制 基于有效性检查的弗发控制 前面三种的混合 现在，大多数数据库采用的是基于锁的并发控制。其中使用最广泛的是动态 2 p l 及其它的一些变种【g r 9 3 1 。在商用领域，基于锁的并发控制占绝对地位，而 基于时间戳和有效性检查的并发控制由于实现难度大，一般只作为理论研究。 数据库是一组数据的集合，而这些数据的变化就形成了事务。所谓事务就是一组 作业的逻辑集合，通常这些作业就是一些数据库操作。如果个事务单独执行的 话，它必须是正确的。所谓正确，就是事务必须满足a c d 。a 指原子性，说明 一个事务要么全做，要么全不做。c 指一致性，说明事务必须从个一致数据库 状态转变到另一个数据库状态。i 指隔离性，说明事务在执行中仿佛感觉只有它 一个在执行，即不受其它事务执行的影响，同时不影响其他事务的执行。d 是永 久性，说明一旦事务结束，它所产生的效果将是持久性的。 数据库中，在有多个事务并发执行的情况下必须进行有效的调度和管理。这 些事务单独执行是正确的，但它们并发执行时，可能造成数据库的不一致。所以， 必须用并发控制保证事务并发执行时的正确性。数据库的并发控制是指协调多个 事务动作的活动。通过并发控制，事务能够并发进行，操作共享的数据，并潜在 的实现相互之间的交流。在并发控制中，串行化是个非常重要的概念。在衡量分 数据库事务的正确性方面，可串行化是使用最为广泛的。所谓串行化，是指在调 度中，多个事务按串行的顺序依次执行。所以，纯粹的串行化不允许并发，没有 什么意义。在并发中有意义的是可串行化。它是指某个调度产生的效果等价与串 行化调度，那个这个调度就是可串行化的。在并发控制中使用最多的可串行化是 冲突可串行化。 本文中研究的是内存数据库的并发控制问题，由于对内存数据库的访问非常 快，事务在内存中停留时间很短，如果是采用锁机制来进行并发控制，因为事务 对于锁的占用时间很短，则锁竞争的程度不如磁盘数据库那么严重。因此在锁的 9 浙江大学硕士研究生毕业论文 粒度等方面需要综合考虑锁的竞争程度和锁的开销。本文根据实际应用需要采用 基于锁的并发控制机制，取得了较好的实际效果。 2 4 本章总结 本章首先对内存数据库的基本概念加以阐述，在对内存数据库技术有了大致 了解后后介绍了内存数据库的发展和现状，使我们对这一种新兴数据库技术有了 更具体的认识，也从中了解了删d b 在实际应用中的广泛前景。最后着重的对并 发控制技术做了粗略介绍，为下一章的工作做了铺垫。 1 0 浙江大学硕士研究生毕业论文 第3 章m m d b 总体架构设计 3 1 设计思路 傩d b 应能主要完成以下功能： 能将特定数据先预存至s e r v e r 的m e m o r y 中使用。 具备t r a n s a c ti o nc o 哪it 与r o n - b a c k 的机制。 对数据需具备l o c k 机制( r e c o r dl o c k ) ，防止其它处理更新关联数据。 提供a p i ，对数据访问模块进行数据的i n s e r t 、u p d a t e 、d e l e t e 、s e l e c t ， 及对r e c o r d 的l o c k 机制。 对数据文件进行i n d e x 的维护。 由于姗d b 在性能上要求能够快速处理各种操作，并且实际应用中的并发度 会很高。基于这方面的考虑舯b 设计的各个层次都应该优先考虑如何提高性能 的问题，另方面则需要考虑如何在尽量不影响性能的情况下设计失败后的恢复 机制。 下面本文就以上提到的各个功能要求展开分析。装载数据要求在尽可能短的 时间内完成，以及在内存申请释放的考虑，所以在底层的内存管理的开销将会是 影响姗d b 性能的瓶颈。因此在操作系统层应采取内存管理，通过预分配内存来 加快管理。本文就设计了内存银行( m e m o r yb a n k ) 来提供底层的内存分配。 3 2m m d b 总体架构 基于以上设计考虑，项目组提出基于消息中间件( s s a g e0 r i e n t e d m i d d l e w a r e 简称m o m ) 和内存数据库( m a i nm e m o r yd a t a b a s e ，简称删d b ) 的体 系架构方案。 基于以上实际需求设计的删册的体系结构如图3 1 所示，应用程序和删d b 在同一个进程地址空间，应用程序通过调用ba p i 实现对删d b 的访问，这样 1 1 撷江大学硕士研究生毕业论文 实现的优点是减少通讯开销，增加系统并发度。 图3 1m m d b 总体架构 如图3 1 所示，应用程序和m m d b 在同一个进程地址空间，应用程序通过 调用m m d ba p i 实现对删d b 的访问，这样实现的优点是减少通讯开销，增加系 统并发度。该体系结构可以方便地扩展成基于s o c k e t 的c s 模式。 图中各部分功能描述如下： 应用线程：应用线程是应用程序所对应的线程，应用程序调用枞b 服务层 提供的a p i 实现对数据库的访问。 主线程：是删d b 进程的主工作线程，负责数据库的启动和关闭，数据库启 动工作流程如下： 1 ) 根据数据库规模，向操作系统申请足够大的内存，并进行初始化( 数 据字典、数据区、索引、锁表、日志缓冲) ； 2 ) 读入数据字典： 3 ) 判断数据库是否完整，若不完整，则进行数据库恢复：先读入数据文 浙江大学硕士研究生毕业论文 件，然后根据日志文件进行数据库恢复； 4 ) 根据读入或恢复的数据库，创建索引； 5 ) 创建一个日志刷新线程和一个检查点线程。 日志刷新线程：负责将事务在内存的日志缓冲区中的日志信息写入磁盘日 志文件，写的策略有两种：( 1 ) 定期写，即当日志缓冲区中日志数目达到 一定数量时；( 2 ) 当事务发起c o 岫i t 操作时，如果要求实时写，就写日志。 根据实际测试数据，建议采用策略( 1 ) 。 检查点线程：本系统将实现基于日志的检查点，基于日志的检查点能实现 和正常事务的完全并行，无需对数据上任何锁，只需对所操作的日志缓冲 区上l a t c h 即可。在内存中保存两个循环使用的日志缓冲区l l 、l 2 ，当l l 满时，启动检查点线程，把l 1 中对数据的修改重写到数据文件中，正常事 务可继续往l 2 中写日志，当l 2 满时，再次启动检查点线程，把l 2 中对数 据的修改重写到数据文件中，正常事务可继续往l l 中写日志。检查点正确 的前提是l l 和l 2 中没有未完成的事务。 数据字典：保存表结构、属性结构和索引结构的描述。 数据区：数据文件的内存拷贝。 索引：所有的索引，目前为h a s h 索引。 日志缓冲：所有已经c o 唧i t 事务的日志，尚未c o 唧i t 事务的日志保存在 事务私有空间。 锁表：保存上锁信息，不想传统的磁盘数据库，本数据库的锁表将直接和 记录关联，以提高上锁的效率。 数据文件：磁盘上的数据，保持最后一次c h e c k p o i n t 后的一致状态。 控制文件：记录数据完整性以及数据恢复的起点。 日志文件：磁盘日志。在控制文件中保留了最后一次c h e c k p o i n t 后的日志 开始点。 浙江大学硕士研究生毕业论文 3 3m m d b 服务层设计 3 3 1 服务层总体架构 删d b 服务层为应用程序提供完整的事务处理能力。 m m d b 服务层体系结构如图3 1 所示： 索引管理数据字典管理 ； 数据访问层 图3 2m m d b 服务层体系结构 由于采用和应用程序紧密结合的方式，减少了网络开销，增加了并发度。m m d b 服务层为每个应用线程建立一个私有的会话( s e s s i o n ) ，每个s e s s i o n 保留正在 处理的事务信息以及一个私有的工作区( 称为局部工作区，1 0 c a lw o r k s d a c e 。 l w s ) 。l w s 主要包括该应用线程当前正在处理的事务的私有日志缓冲以及向应用 程序返回的数据缓冲。 蝴d b 服务层由三部分构成： ( 一) 操作系统层 浙江大学硕士研究生毕业论文 封装特定操作系统的实现细节，提供对系统同步、内存管理、文件管理和线 程处理等一系列服务的支持。 ( 二) 数据存储层 这是一个通用的删d b 数据存储引擎，具有数据存储、并发控制和数据恢复 等功能，在这一存储模型中，表被映射为段，元组被映射为行，整个数据存储层 提供如下功能： 1 ) 事务管理：开始提交回滚事务； 2 ) 锁表管理：对行加解锁； 3 ) 行管理：删除选择更新行； 4 ) 段管理：创建删除段； 5 ) 表管理：创建删除表，顺序遍历表，在表尾插入行； 6 ) 私有日志管理：管理当前事务的私有日志； 7 ) 全局日志管理：管理全局日志； ( 三) 数据访问层 对应用程序提供数据访问接口，内部实现调用数据字典管理接口实现对数据 字典的访问调用索引管理接口实现对索引的访问和维护。调用数据存储层的事务 管理、行管理和锁管理接口完成数据访问功能。 下图是一个正常事务处理的总体流程，图中，客户端把数据操作语句封装成 消息，然后进行数据同步和消息分发，如果数据同步成功，则提交交易处理模块 进行消息解包和事务处理，然后把处理结果返回个客户端。如果数据同步失败和 事务处理超时，则重新同步和分发消息。 服务层的事务处理流程如下图所示： 浙江大学硕士研究生毕业论文 3 3 2 操作系统层 处世 束 图3 - 3 事务处理流程 为了优化内存分配、释放的执行效率，提高内存访问的安全性，合理解决内 存碎片问题，我们在d b 中设置了动态内存管理( 0 嘲) 模块。d 是操作系统 1 6 浙江大学硕士研究生毕业论文 的一次扩展，是删明的最底层，删d b 中的其他部分，都是d 姗的用户。 d 咖采用堆式内存管理方法，算法的核心有两条，其一是把数据区与控制区 分开，其二是使用循环分配算法。 ( 一)数据区与控制区分开 把数据区与控制区分开是为了提高系统的安全性。所谓数据区就是供用户使 用的存储区，所谓控制区，就是由d 删自己使用的存储区。把数据区与控制区分 开，大大提高了数据安全性，用户操作数据区不会改写控制区的内容。 数据区实际上是一次性向o s 申请的连续的内存区。控制区存放描述内存块 的控制节点，每个节点主要包括以下几个字段： 且d d r l8 d d r 28 d d r 3 耐d 。4刊d r 5 e n d _ o f r e a i 螋一竺一j 一竺+ j 一竺一l 一鲤 d a t b f r e “t i f r ” “棚1 l t e 础b l 。c ki t e 曲b 1 0 c k j h t a r e al 甜o u t 哳n t r o ih 0 d e 8 。ft h e 0 帅r yi t e s m c o 呻同n o 曲$ v sd 1 i 咖a 图3 - 4 动态内存管理 ( 二) 循环内存分配 空闲内存块的分配算法采用循环分配算法。其基本思想来源于这样的假设： 在平均意义下，越早申请的内存越可能先被释放，这些释放了的内存又会连成一 片较大的内存。因此，申请最久前被分配的内存区，成功的概率相对较大。 d 删设置了个循环查找指针指向下一个可分配的空闲内存块。 内存申请遇到一个较大的内存块时，进行内存块分裂。分裂的阈值是个系 1 7 浙江大学硕士研究生毕业论文 统参数。分裂时先申请一个空闲控制结点，用它描述分裂后的空闲内存块。分裂 后，循环查找指针指向分裂出的空闲块上。 内存释放遇到一个相邻的空闲内存块时，进行内存块合并。若被合并的块是 循环查找指针指出的内存块，则要把循环查找指针调整到合并后的大块上。合并 后，释放被合并块的控制结点。 3 3 3 数据存储层 3 3 3 1 表管理 表管理模块管理数据库中所有表在内存中的存储信息，但不保留其模式信 息。表管理模块主要实现对表占用的内存空间的管理。表管理模块主要的数据结 构如下： 3 3 3 2 行管理 0 3 5 表管理结构 行管理主要实现针对行的操作。每个行后都有其对应的行级锁表，记录了哪 些事务已获得锁，哪些事务正在等待锁，这样可以避免对行级锁的h a s h 查找。 行管理是数据存储查询更新的重要部分，基本的数据交换都发生在这一层。 而且涉及到并发控制，错误恢复等方面，所以本模块需要调用锁管理模块接口和 事务管理模块中私有日志接口。 为了进行并发访问，对数据进行实际操作以前必须对相应数据加锁( 对更改 数据的插入，更新，删除操作加写锁，访问数据的选择操作加读锁) 。只有在得 1 8 浙江大学硕士研究生毕业论文 到相应数据行的相应类型的锁以后才可以对数据进行读写操作，否则只能等待。 对数据的加锁首先通过表管理模块对相应表加l a t c h ，然后通过锁管理模块对相 应的行请求锁。如成功得到锁则释放全局表的l a t c h ，之后就可以进行数据读写 操作；否则也要释放全局表l a t c h 。 错误恢复通过记录事务的私有日志实现。每个事务包括一个私有的u n d o 目 志链表和一个私有r e d o 链表。每次对数据进行更改以前，先记录u n d o 日志， 以便回滚，对数据更改以后，记录r e d o 日志，以便重做。 3 3 - 4 数据访问层 数据访问层主要维护三张h 袖表，分别用于表、索引和属性的查找；下豳中的 t a b k d e 凼、a t t r d e 酬l i s t 、h d e x d e s c l 主吼可用静态数组实现。 3 4 性能分析 图3 缶数据访问层数据结构 本文的设计应用于内存数据库系统中，在以下硬件环境下：i b mp s e r i e s6 6 0 ( 6 f 1 ) 卜明yc p u6 0 0 姗z ，3 2 位元，4 gr a l l l ，1 2 6 gh d ，操作系统a i x5 o 。 1 9 浙江大学硕士研究生毕业论文 系统达到如表所示的性能。 表争1 性能测试结果 1 b t 资料 1 u m a r o i l i l d m m d b呦b c r i t e r i a 人数 t i m ec p u m e m o r y 量 ( 每笔r e q s t ) l m d i n g l o a d i f l g 11 0 0 1 0 0 万0 0 1 秒 l o 1 0 2l o2 0 万000 i i 僦 0 d 2 秒 31 0 0 1 0 0 万 u i 畦他 0 0 1 秒2 0 2 0 d e l e t e0 0 1 秒 45 0 中等0 1 秒4 0 5 0 注：c p ul o a d i n g 及m e m o r yl o a d i n g 皆只针对删d b 所执行的p r o c e s s 。 t u r n a r o u n dt i m e 、c u pl o a d i n g 、m e m o r yl o a d i n g 为平均值。 3 5 本章总结 本章首先介绍了删叮b 项目总体的设计，然后对删d b 服务端的设计作了详细 介绍。服务端由主要介绍了数据存储层的设计，经过测试表明本文的m b 设计 性能和稳定性上都能满足实际商业应用。 2 0 浙江大学硕士研究生毕业论文 第4 章事务管理研究 4 1 事务的概念 事务是指一个单元的工作，这些工作要么全做，要么全部不做。其形式化定 义【p 8 6 为： 事务t 是一个对数据库进行读写操作的有穷序列，记为t = 4 - ，4 ：4 一。 其中q 为事务t 的一个操作。 事务作为一个逻辑单元，必须具备四个属性：自动性、一致性、独立性和持 久性。 自动性是指事务必须是一个自动的单元工作，要么执行全部数据的修改，要 么全部数据的修改都不执行。 一致性是指当事务完成时，必须使所有数据都具有一致的状态。在内存数据 库中，所有的规则必须应用到事务的修改上，以便维护所有数据的完整性。所有 的内部数据结构，例如树状的索引与数据之间的链接，在事务结束之后，必须保 证正确。 独立性是指并行事务的修改必须与其他并行事务的修改相互独立。一个事务 看到的数据要么是另外一个事务修改这些事务之前的状态，要么是第二个事务已 经修改完成的数据，但是这个事务不能看到正在修改的数据。这种特征也称为串 行性。 持久性是指当一个事务提交之后，它的影响永久性的产生在系统中，也就是 这种修改写到了数据库中。 我们规定事务的结构满足以下两条规则： 1 在一个事务中，对一个数据项最多只能进行一次读或写操作，即在事务 的抽象模型中r e a d ( x ) 或w r i t e ( x ) 不能重复。 2 在一个事务中，对同一个数据项的操作同时存在r e a d ( x ) ，w r i t e ( x ) ， w r i t e ( x ) 只能在r e a d ( x ) 之后执行。 浙江大学硕士研究生毕业论文 事务机制保证一组数据的修改要么全部执行，要么全部不执行。d b 使用 事务保证数据的一致性和确保在系统失败时的可恢复性。事务是一个可以恢复的 单元的工作，由一条或者多条s q l 语句组成，可以影响到表中的一行或者多行数 据。事务打开以后，直到事务成功完成之后提交为止，或者到事务执行失败全部 取消或者滚回去为止。 4 2 实时事务管理 事务管理由并发控制和系统恢复两部分组成。在 h l s r 7 4 ，事务被抽象为一 个数据库操作序列。 p 8 6 给出了事务的形式化描述。从数据库当前的状态来考 虑，为了数据库状态的一致性，要求事务具有原子性、一致性、持久性等特点。 当系统中有多个事务存在时，又要求这些事务能够并发执行且互相不产生干扰。 因此事务的执行顺序是至关重要的。在 p b r 7 7 和 p 7 9 中介绍了数据库最终状态 可顺序化的正确性标准。 传统的事务操作步骤由事务管理器完成。事务送交系统后，事务管理器对其 做语法、词法及安全性约束等检查，然后交给事务调度器处理。事务调度器收到 这些事务后会对其进行排队，根据所采用的并发控制策略和方法以及数据项的使 用情况，对这些事务做出延迟、执行或放弃的操作。如果调度器放弃执行此事务， 则会向管理器发回一个放弃操作信息，然后管理器会放弃此操作；如果延迟操作 则会将事务放入操作队列，等待调度器调度。如果同意执行此事务，则将其送交 给数据管理器执行，执行结果再返回给事务管理器，最终结果返回给用户。因此 在这种模型下事务t 的执行是按照调度器送交数据管理器的顺序执行的。 传统的事务是一系列彼此孤立的工作单元，事务处理强调绝对的正确性，而 不涉及事务的实时性，因此传统的标准是事务的原子性与可串行性。实时的事务 的特性主要表现在： 正确性：不仅要求结果正确，还需要时间正确，即在截止期内执行。 可预测性：需要预测事务的执行时间，来确保事务能满足截止期。 可恢复性：事务因为访问冲突或错失截止期而必须重启时，则整个事务 的操作都应该能取消并恢复到原来的数据库状态。系统发生故障时，例 浙江大学硕士研究生毕业论文 如断电，系统也应能恢复成正确的状态。 4 2 1 实时事务调度 传统的数据库保存的是持久稳固的数据。不同的事务更新共享数据需要保持 数据的一致性。一般情况下并没有和事务相关的时间限制。然而对于内存数据库 之类的实时数据库而言：达到最大的事务的吞吐量和最短的事务平均响应时间是 我们追求的目标。因此内存数据库需要提供统一的方法来保证数据的一致性和时 间方面的限制。 一个事务与以下的性能相关： 4 ：事务到达时间。 d ，：事务要求的完成时间。 j ，：事务在珥之前完成的最长延迟时间。 坼：事务执行时间。 ：事务的运行结果。 弓：事务的优先级。 前四个属性的关系是： d r1 4 f + r + _ s r 根据事务的完成时限的严格程度，我们将事务划分为以下几类： 刚性期限事务：具有严格的事务完成期限，系统必须提供调度方法来保 证能在预定的期限内完成。例如核反应设旌控制系统，交通控制系统通 常采用这种事务。 软性期限事务：基于完成期限调度，在指定期限内完成仍然是主要的性 能指标：但是并不一定要保证在期限内完成。软性期限的事务在执行中 并不管事务自身是否已过期。 稳定期限事务：这种事务介于上述两者之间。不同于软性期限的事务的 是，一旦超过执行期限事务会被系统终止。 现实世界中支持软性期限事务和稳定期限事务的应用在 a m 9 2 中有详细的 浙江大学硕士研究生毕业论文 例予。例如银行系统和预定机票系统这样的系统，通常采用软性期限事务。用户 提交一个事务，如果系统无法在期限内完成，用户更希望获得一个延时的响应。 在股票交易系统中则会采用稳定性期限事务，例如一个获得当前价格的事务被提 交给系统，则系统或者在指定期限内返回结果或者根本就不执行这个操作，应为 股票市场的价格变化很快，超时的结果对用户来说是没有意义的。 为了尽可能的满足实时需求，事务调度应尽量在期限内完成。其中两种使用 广泛的调度策略如下： 最近期限优先( e a r l i e s td e a d l i n ef i r s t ) ：期限最近的事务具有高优先 级。 最短空余时间优先( l e a s ts l a c kf i r s t ) ：具有最短空余时间的事务具有 高优先级。 最早放行优先( e a r l i e s tr e l e a s ef i r s t ) ：具有最早可以开始执行的时 间的事务赋予最高优先级。 内存数据库作为一种实时数据库在事务调度上需要考虑事务在无法满足截 止期的情况下的行为以及事务在错过截止期或操作失败时能够自动回滚和强制 回滚操作。 实时事务的调度策略主要可以预先分析事务的特性，来产生一个调度规则， 来指定何时执行何种事务，也可以根据当时事务的运行环境，来实现对事务的调 度，视具体情况而定。此外，实时事务的调度一般采取抢占式的调度方式，即高 优先级事务可以抢占低优先级事务的执行时间和资源，低优先级的事务被挂起。 4 2 2 实时事务的预分析 非预先安排的事务夭折所引起的回滚和重启会造成系统资源的巨大浪费，也 会影响事务的实时性。如果能对实时事务在系统中执行顺序和执行时间的作适当 的预测，就能够有效地避免或减少这种问题。 实时事务预分析在传统的预分析之中增加了实时事务分解，其步骤为： 静态分析：提取有关存取行为的知识( 操作数据集、时间限制等) ，以便在执行 时进行基于上述提取知识的内外存数据交换，从而支持事务的定时限制 事务分解：根据实时事务的同构性分懈该实时事务得到替代 浙江大学硕士研究生毕业论文 动态预分析：在动态环境下分析替代的行为特性，如分析替代的估算执行时 间、事务间的时间相关性等 实时事务之间可能存在结构、行为、数据、时间上的相关性，事务调度就需 要考虑这种相关性。对事务的相关性的预分析，有助于我们进行合理的事务调度， 从而提高系统的执行效率。我们可以通过采用事务的相关图来分析相关性。具体 参见 l l l x 9 8 中的介绍。 实时事务的动态预分析处理主要是在执行阶段根据当前的系统资源使用情况 和事务的运行情况，以及事务的特性，例如截止期，预测的运行时间来对事务的 调度进行预先的安排。 4 3 恢复处理 为保证事务的a c i d 特性，事务提交时必须强制写事务活动的日志到稳定介质 由于内存的易失性，因此必须写日志到可靠的存储介质中。写曰志的过程很可能 成为整个数据库系统的瓶颈。因为磁盘i 0 的时间相比内存访问来说是相当可观 的，如何在写日志的同时能够尽量不影响事务的正常处理是内存数据库研究中必 须面对的问题，目前常用的方法有以下几种： ( 1 ) 使用稳定内存 稳定( s t a b l e ) 内存是一块非易失的r a m ，当事务准备提交时，只要将日志 写入稳定内存即可，这一操作花费时间很少，等于内存到内存的拷贝。稳定内存中 积累一定量的日志后，由专门的进程完成日志到磁盘的刷新。 ( 2 ) 群提交 在并没有专门的稳定内存可用的系统。可以采用群提交的方法，即事务提交 时，先将日志写入一块内存缓冲区，称作预提交，预提交后，事务即可释放持有的 锁。当内存缓冲区一页满时，一次刷新到磁盘，最后完成一批事务提交。 ( 3 ) 只写r e d o 日志 某些内存数据库系统采用了一种提交协议以减少写到磁盘的日志数量，使用 该协议时，事物正常执行时，u n d o 、r e d 0 日志都写入内存缓冲区，但事务提交 时，u n d o 日志被丢弃，只将r e d o 日志持久化。 浙江大学硕士研究生毕业论文 由于内存中非常容易丢失数据，所以删d b 的恢复处理一直是内存数据库领域 的一个研究热点。恢复处理主要包括了日志、检查点和数据重装三种技术。 日志的功能是记录对数据库的修改操作；检查点主要是功能是把内存中的数 据持久化到磁盘文件中；数据重装则是将磁盘中的数据重新目一| i _ l ! ；# 馨= g ! i i ；强戳甄辅摇 嘏漤溢哺婆 x 浙江大学硕士研究生毕业论文 4 4 2 2 基于时间戳的并发控制 基于时间戳的并发控制是一种重要的并发控制技术。在时间戳方法中，1 m 为每个事务赋一个独一无二的时间戳，并且为事务的每个操作赋该事务的时间 戳。时间戳调度器根据这些时间戳排序冲突的时间戳。基本的时间戳技术是抢占 式的时间戳并发控制技术。基本时间戳调度器会立即调度那些可以执行的操作。 调度器会拒绝那些有更大时间戳并发生冲突的操作，当操作被拒绝时，相应的事 列的操作，它可能会拒绝其中很大一部分操作，从而使很多事务中止。在这种系 统中，因为平凡的冲突及中止，可能会导致饿死现象的出现。下面叙述经典的时间戳算法。 1 每个事务被赋一个事件戳t s ( t i ) 。事务时间戳满足如下条件：如果先到的事务有时间戳1 鞫t j ) ，那么鸭 t s c r i ) 。 2 对每个对象q 提供两个时间戳，t s w ( q ) 和t s | ( q ) 。骶；。( o ) 是执行w r i 似q ) 的事务中最大的t s 值。弼i ( q ) 是执行r e a d ( q ) 的事务中最大的t s 值。 3 当事务t i 执行r d ( q ) 时，如果t s 髑“q ) ，那么t i 将要读一个已经 被写过的数据，出现读脏数据现象，这时r c a d 被拒绝，t i 回滚。如果 t s ( ，r i ) z t s w ( q ) ，r e a d 执行，t s r ( o ) 被设成t s r ( q ) 和t s 中的较大值。 4 当事务t i 执行w h t e ( q ) 时，如果m ) t s 。( q ) 并且t s m )