（计算机应用技术专业论文）内存数据库中数据恢复技术的研究与实现.pdf

摘要 随着硬件工艺的不断提高，内存越来越便宜存储容量越来越大，这使得将整 个数据库放在内存中成为了可能；而且有很多应用需要快速的响应时间和大的吞 吐率。正是由于这样需求的推动和硬件条件的保障促使了近年来内存数据库 ( m m d b ) 领域研究的飞速发展。在m m d b 中，整个数据主版本放在内存中， 这必然比传统的磁盘数据库更加容易崩溃、丢失数据，因此其恢复管理子系统就 显得格外重要。本文主要关注m m d b 中恢复系统技术的研究，并且详细介绍了 自主研发的内存数据库o t bm m d b 中恢复系统的实现。 本文先给出了内存数据库的定义，并且将它与传统的磁盘数据库做了方方面 面的对比。然后对目前内存数据库的技术分多个方面做了概括性介绍，并且扼要 介绍了o t b _ m m d b 的总体设计框架。接着则对m m d b 恢复模块分为l o g g i n g ， c h e c k p o i n t i n g 和r e l o a d i n g 三个部分详细讨论，讲述了包含w a l ( w r i t ea h e a d l o g g i n g ) 协议、l a w ( l o g g i n ga f t e r w r i t i n g ) 协议在内的多种日志登记规则， 描述了多种检查点算法，包括模糊检查点算法、黑白点算法、c o p y o n u p d a t e 算法等。最后讲解o t b _ m m d b 中的恢复系统的实现，并讨论了其中一些优化 系统性能的措施。 关键词：内存数据库，日志规则，检查点，黑臼点算法，c o p y o n u p d a t e 算法 a b s t r a c t i nam a i nm e m o r yd a m b a s e ( m m d b ) t h ep r i m a r yc o p yo ft h ed a t a b a s er e s i d e s i nv o l a t i l em a i nm e m o r y t h i sn l a k e sm m d bs y s t e m sm o r ev u l n e r a b l et of a i l u r e s c o m p a r e dt ot h et r a d i t i o n a ld i s kr e s i d e n td a t a b a s e s r d b ) ab a c k u pc o p yo ft h e d a t a b a s ei sm a i n t a i n e di n s e c o n d a r ys t o r a g ef o rr e c o v e r yp u r p o s e s r e c o v e r y a c t i v i t i e sl i k el o g g i n g ，c h e c k p o i n t i n ga n dr e l o a d i n ga r eu s e dt or e s t o r et h ed a t a b a s et o a c o n s i s t e n ts t a t ea f t e ras y s t e mc r a s hh a so c c u r r e d i n t h i sp a p e r , w ef o c u so i lt w op o i n t s f i r s t l yw ee x a m i n em m d bl o g g i n g ， c h e c k p o i n t i n ga n dr e l o a d i n ga c t i v e i t i e s s e c o n d l y ，w ei m p l e m e n tar e c o v e r ys c h e m e w i t ht r a n s a c t i o nc o n s i s t e n tc h e c k p o i n t i n gf o ram a i nm e m o r yd a t a b a s e k e y w o r d s ：m a i nm e m o r yd a t a b a s e s ，l o g g i n g ，c h e c k p o i n t i n g ，r e c o v e r y 2 1 1 背景介绍 第一章绪论 1 1 1 什么是内存数据库 内存数据库还是一个较新的研究领域，目前对内存数据库尚无统一的定义。 对于什么是内存数据库，有着几中说法： 观点一：整个数据库全部驻留内存，数据存取无需y o 操作。 观点二：数据库常驻磁盘，在事务执行前将所需数据集调入内存，提交时所 有对数据库的修改必须写回磁盘。 观点三：数据库常驻磁盘，在内存中开辟一个大缓冲区，通过适当的缓冲管 理以减少i ，o 操作。 目前，大多数内存数据库都是基于第一种观点的。然而在很多现实应用中， 往往难以保证内存总是能够容纳整个数据库。因此，数据库的定义必须包含内存 不足以容纳整个数据库的情形。而第二、三两种观点下的数据库本质上无异于常 规磁盘数据库，只不过改变了数据调入内存的时机、增大了缓冲区的容量，不能 称为内存数据库。判断一个数据库是否为内存数据库的标准应该取决于其数据库 的主拷贝是否常驻内存，而不能只看内存的大小和存取数据所需的i ，o 次数及数 据调入内存的时机。一般，对内存数据库的定义如下： 定义1 设有数据库d b ，t s 为所有事务构成的集合。v t et s ，d ( d 为t 的 操作数据集( d ( d c _ d b ) ，d b m ( t ) 是t 时刻d b 在内存中的数据集( d b m ( t ) _ c d b ) ，a t ( t ) 是t 时刻的活动事务集，a t ( t ) _ t s 。若在任一时刻t ，均有 v t ea t ( t )d ( d d b m ( t ) 成立，则称d b 为一个内存数据库，间称为m m d b 。 直观的说，m m d b 就是指数据库的“工作版本”( 当然也可以是整个数据库) 常驻内存，任何一个事务在执行过程中没有与内外存间的数据y o 。显然，它需 要一定的内存容量，至少能容纳一个事务所要求的数据集，但并不一定需要容纳 整个数据库。活动事务的执行从开始到提交，均不与外存打交道。当事务提交时 数据库的“外存版本”可以不必立即反映出事务提交后的结果，并且当系统出现 故障时应恢复在内存中的数据库主拷贝。 对于传统的磁盘数据库来说，即使其缓冲区足够大，以至于可使整个数据库 或其“工作版本”常驻内存因而i o 极少，系统性能很好，但它是针对磁盘特性 设计的，是在假定数据库常驻磁盘的情况下设计的，不可能具有m m d b 的各种 功能特性和优点。 1 1 2 是什么推动了内存数据库的迅猛发展 m m d b 的理论基础是在1 9 8 0 年代后期通过积极的研究和开发形成的。当时， 3 2 位处理器最大支持4 g b 地址空间，但是由于操作系统和软件操作的限制，3 2 位地址空间实际上只有2 g b 左右( 现在的数据库的大小) 。然而，6 4 位的内存 数据库仅受系统中配置的物理内存的数量的限制，6 4 位系统支持最高1 0 0 g b 的 内存容量。但由于经济和技术的限制，目前为止投入实际应用的内存数据库系统 商业化产品还是比较少的一般都是针对某个实际应用场合的定制产品。 ( 1 ) 存储器价格的下降 半导体技术的高速发展使d r a m 的成本戏剧性的下降，在过去的几十年中， d r a m 的成本下降了几十上百倍。1 9 8 6 年时1 g b 内存的成本是4 0 0 0 0 美元，但 是现在还不到1 0 0 0 人民币。i d c 预测存储器的价格还会持续下降。考虑到这种 趋势，在数据库解决方案中引入内存数据库是可行的，这正被越来越多的人所接 受。 ( 2 ) 6 4 位系统的关键作用 3 2 位系统只能访问大约2 g b 的内存，这限制了系统中主存数据的存储。另 一方面，6 4 位系统可以访问最多1 6 0 亿g b 的内存，所以在6 4 位系统中的主存 数据存储容量的限制仅仅是可以被安装到系统中的物理内存的数量。内存数据库 巧i 受地址访问空间的限制。 ( 3 ) 数据库管理技术的提高 在实际应用中用户通常会有两个考虑：内存数据库的稳定性和数据库的大 小会不会有限制。目前已有很多内存数据库应用于各种高科技领域而且具有和传 统基于磁盘数据库同样的稳定性。 1 1 3 为什么内存数据库快 即使是磁盘数据库的内存缓冲区足够大，将整个数据库都放在缓冲区中，磁 盘数据库的性能也是不可以和m m d b m s 相媲美。磁盘数据库的u p d a t e 操作 需要和磁盘同步数据，但是s e l e c t 操作可以得到差不多的效率。但是由于磁 对于传统的磁盘数据库来说，即使其缓冲区足够大，以至于可使整个数据库 或其“工作版本”常驻内存因丽y o 极少，系统性能很好，但它是针对磁盘特性 设计的，是在假定数据库常驻磁盘的情况下设计的不可能具有m m d b 的各种 功能特性和优点。 1 1 2 是什么推动了内存数据库的迅猛发展 m m d b 的理论基础是在1 9 8 0 年代后期通过积扳的研究和开发形成的。当时， 3 2 位处理器最大支持4 g b 地址空间，但是由于操作系统和软件操作的限制，3 2 位地址空间实际上只有2 g b 左右( 现在的数据库的大小) 。然而，6 4 位盼内存 数据库仅受系统中配置的物理内存的数量的限制，6 4 位系统支持最高1 0 0 g b 的 内存容量。但出于经济和技术的限制，目前为止投入实际应用的内存数据库系统 商业化产品还是比较少的，一般都是针对某个实际应用场合的定制产品。 f 1 ) 存储器价格的下降 半导体技术的高速发展使d r a m 的成本戏剧性的下降，在过去的几十年中， d r a m 的成本下降了几十上茸倍。1 9 8 6 年时1 g b 内存的成本是4 0 0 0 0 美元，但 是现任还不到1 0 0 0 人民币。i i ) c 预测存储器的价格还会持续下降。考虑到这种 趋势在数据库解决方案中引入内存数据库是可行的，这正被越来越多的人所接 受。 ( 2 ) 6 4 位系统的关键作用 3 2 位系统只能访到大约2 g b 的内存，这限制了系统中主存数据的存储。另 一方帆6 4 位系统可以访问虽多1 6 0 亿g b 的内存，所以在6 4 位系统中的辛存 数搬存储容量的限制仅仅是可以被安装到系统中的物理内存的数量。内存数据库 不受地址访问空间的限制。 ( 3 ) 数据库管理技术的提高 在实际应用中用户通常会有两个考虑：内存数据库的稳定性和数据库的大 小会不会有限制。目前已有很多内存数据库应用于各种高科技领域而且具自和传 统基于磁盘数据库同样的稳定性。 1 1 3 为什么内存数据库快 即使是磁盘数据库的内存缓冲区足够大，将糌个数据库都放在缓冲区中，磁 稿擞据库的性能也是不可以和m m d b m s 相媲美。磁盘数据库的u p d a t e 操作 需要和磁盘同步数据，但是s e l e c t 操作可以得到差不多的效率。但是由于磁 需要和磁盘同步数据，但是s e l e c t 操作可以得到差不多的效率。但是由于磁 盘数据库查询处理算法的复杂性，主要是为了优化磁盘访问，磁盘系统还不能得 到我们希望的高性能。内存数据库系统高性能的最主要原因在于它的数据库管理 技术和数据库系统的架构。 ( 1 ) 数据访问的成本 磁盘的价格低于存储器的价格，存储器的价格低于c p uc a c h e 的价格，换 句话说，速度越快，价格越高。另一方面，在处理速度方面，磁盘的访问时间位 毫秒级，而内存的方位时间为数十纳秒的数量级。要想得到高性能仅仅将数据库 存储在主存中是不够的，还需要高效内存结构技术，高速缓存数据管理技术和基 于主存的查询优化技术。 ( 2 ) 主存狃磁盘的地址映射。 假定磁盘d b m s 管理的所有数据主要的存在于磁盘中，记录的访闻是通过 r i d ( r e c o r di d e n t i f i e r ) 实现的。因此要访问一个记录，需要地址映射将r i d 转换为 内存的物理地址。内存物理地址和数据库地址的地址映射时间非常短，但是在高 速数据处理的情况下是不能忽略的。 主存d b m s 直接通过内存指针访问数据库，因为没有了地址映射的时间，可 以提高数据库的性能。同样，在向磁盘中备份数据库和生成用于恢复的日志时也 需要地址映射时间。根据使用的地址映射技术效率的区别和地址映射次数的多 少，内存数据库的性能会有很大的不同。 ( 3 ) 内存优化的索引结构 磁盘数据库系统的典型的索引技术是b t r e e 索引。b - t r e e 结构的主要目的是 减少完成数据文件的索引查找所需要的磁盘i 0 的数量。b t r e e 通过控制节点内 部的索引值达到这个目的，在节点中包含尽可能多的索引条目( 增加一次磁盘 g o 可以访问的索引条目) 。另一方面，t - t r e e 是针对主存访问优化的索引技术。t - t r e e 是一种一个节点中包含多个索引条目的平衡二叉树，t - t r e e 的索引项无论是从大 小还是算法上都比b - t r e e 精简得多。t - t r e e 的搜索算法不分搜索的值在当前的节 点还是在内存中的其它地方，每访问到一个新的索引节点，索引的范围减少一半。 ( 4 ) 查询优化 磁盘数据库系统的查询优化算法基本上也是为了实现减少磁盘 0 。 d r d b m s 系统优化的方针假定数据主要是存放在磁盘上的。磁盘数据库中的数 据可能在磁盘上，也可能在内存缓冲中，但是磁盘i 0 的成本远远大于内存访问， 所以磁盘数据库不得不假定最坏的情况，所有的数据都在磁盘中。另一方面，在 内存数据库可以确定所有的数据都在主存中，可以在这个简单的假设( 数据都在 主存中) 下优化器查询算法。内存数据库的查询优化不需要考虑磁盘的问题所以 更简单，更精确。内存数据库系统可以实现比磁盘数据库更多的优化算法。 ( 5 ) 日志和恢复 由于主存是易失性的存储介质，所以需要进行数据库的备份。m m d b m s 在 磁盘上的备份数据库可以弥补主存的易失性，因而，内存数据库和备份数据库之 问需要同步以保持数据的耐用性，这是数据库的基本标准，另外精确的曰志和恢 复能力也是事务处理中a c i d 标准的基本要求。现在，商业内存数据库系统已经 应用于各种技术领域，保证了数据的耐用性。但是，按照怎样实现优化的同步， 日志，恢复能力和数据耐用的程度不同，系统的性能有很大的不同。 1 2 内存数据库和传统数据库的对比 1 2 1 传统数据库和实时数据库 传统数据库系统( t r a d i t i o n a ld a t a b a s es y s t e m ，t d b s ) 处理对永久数据的管 理，实现事务对永久数据的存取，同时维护其完整性、一致性。所以传统的数据 库具有a c i d ( a t o m i e i t y ，c o n s i s t e n c y ，i s o l a t i o n ，d u r a b i l i t y ) 特征，即原子性、 一致性、隔离性和永久性。传统数据库管理系统的典型代表是关系型数据库 r d b m s ( r e l a t i o n a ld a t a b a s em a n a g e m e n ts y s t e m ) ，我们平常用到的商用数据 库管理系统如o r a c l e ，i n f o r m i x ，s y b a s e , s q ls e r v e r 等都是r d b m s 。r d b m s 已 发展了很多年，其技术成熟度己广为人接受，其可靠性、可用性已被广泛验证 并在传统的商务和管理事务型的应用领域获得了极大成功，然而它们在现代的 ( 非传统) 工程和时间关键型应用面前却显得软弱无力，其主要原因是其数据存 取服务的实时性很难得到保障，由此导致了实时数据库系统( r e a l t i m e d a t a b a s e s y s t e m ) 的产生和发展。 实时数据库系统就是其事务和数据都可以具有定时特性或显式的定时限制 的数据库系统，系统的正确性不仅依赖于逻辑结果，而且还依赖于逻辑结果产生 的时间。近年来，实时数据库系统已发展成现代数据库系统研究的重要方向之， 在数据库研究领域受到极大关注。实时数据库系统通常简称为实时数据库 ( r e a l - t i m ed a t a b a s e ，r t d b ) 。 1 2 2 传统数据库与内存数据库 正如前面所述，我们平常用到的商业关系数据库系统，其主要目标是保证数 据存取的a c i d 特征，为各类商务及事务应用提供强大的数据管理与存取服务。 但它们的数据服务的实时性很难得到保障，其根本原因在于： 传统数据库是磁盘数据库( d i s kr e s i d e n t d a t a b a s e ，d r d b ) ，即数据的主拷 贝( p r i m a r yd b ) 在磁盘上，数据库管理系统为了向应用系统提供存取服务，将 用户需要访问的数据装入主存中，即对数据的管理是“基于磁盘的缓存技术”。 而我们知道，磁盘相对于主存来说是极其低速的存储介质，且磁盘存取速度还和 欲存取的数据的物理位置和当前磁头状态有关。另外，管理缓存( c a c h e ) 或缓 冲( b u f f e r ) ，无论是在操作系统( o s ) 层，还是数据库管理系统层，都需要付 出较大的代价( 时间和空间，尤以时间代价为甚) 。因此，即使将磁盘数据全部 缓存到主存，其管理代价仍较大，存取速度仍然无法满足多数实时性应用系统的 要求。 为了实现实时数据库系统，人们自然想到了基于内存的数据库，即内存数据 库( m a i n m e m o r y d a t a b a s e ，m m d b ) 。m m d b 与d r d b 的根本区别在于，在 m m d b 中，数据库的全部或活动事务存取的数据放于内存中( 如下图所示) ， 这样事务对盘的访河完全取消了。由于整个数据库放于内存，数据库则不再作为 大量存储文件看待而作为内存中可寻址的大量数据，不同于d r d b 中的缓存或 缓冲区方式，它完全打破了传统磁盘数据库系统的设计宗旨，带来了其自身新的 设计问题。如：传统磁盘数据库系统的数据组织、访问方法、查询处理算法的设 计都针对减少磁盘访问次数与有效利用盘存储空间，甚至牺牲c p u 时间来减少 i o 次数( 如查询处理有大量中间数据) ，而内存数据库的设计则主要考虑如何 有效地利用c p u 的时间和内存空间。对传统磁盘数据库系统相当有效的数据组 织、访问方法、查询处理算法，对于内存数据库系统可能并不有效，相反，一一些 认为对传统磁盘数据库系统无用的办法，反而成为可行的。显然此方式可完全消 除事务与盘打交道，且可避免与影响性能的缓冲区管理程序发生联系，故采用此 方式使数据库系统性能极大提高。 9 m m d b 埘d bv sd r d b a r c h i t e c t u r a lc o m p a r i s o n 每t h r e a d o p r o c e s s d r d b 图1 1m m d b 与d r d b 比较 1 2 3 传统磁盘数据库与内存数据库的特点比较 传统磁盘数据库的优点 传统数据库的a c i d 机制成熟、可靠； 提供强大的数据定义语言( d d l ) 及数据操作语言( d m l ) ，提供s q l 支持； 提供一定的主动机制( 如触发器，t r i g g e r ) 和后台数据处理能力( 如存 储过程，s t o r e dp r o c e d u r e ) 。 传统磁盘数据库的主要缺陷 占用、消耗的系统资源较多； 数据存取的速度慢； 数据存取时间不一致且难以预测 内存数据库的突出优势 存取速度快速、一致 存取时间易于预测 易于定制数据存取方式 内存数据库的主要特点 o 为了降低m m d b 的内存开销，m m d b 往往简化了对复杂事务处理的支 持，如m m d b 一般不提供事务的u n d o 机制，代之以“补偿事务”的方 式来实现事务处理的原子性和一致性。 由于m m d b 中的数据库“主拷贝”在内存中，因此，m m d b 对系统的 故障恢复提出了更高的要求，实现起来难度更大。 通用性不强，由于不同的实时应用系统中的数据对象不同，对数据库的 访问要求及访问方式不同。为了提高数据库的实时性，在设计m m d b 时，需要根据应用特点，采取一些针对性的措旖。因此，设计上往往有 一定的特殊性。 1 3 课题背景及本文主要工作 1 3 1 课题背景 期货交易系统平台是提供专业期货商及相关金融机构从事期货交易的支撑 平台，其主要目的是向上层的期货交易业务提供高可用、高性能的数据库存取服 务。期货交易分秒必争，对交易系统提出很高的实时响应要求。 国外目前有一些内存数据库系统的报道，如美国a t & t 公司的d a t a b l i t z ( 前 身为d a f t ) ，韩国的x m a s ，美国的b e r k l e yd b ，e x t r e m ed b 等。但这些系统往 往只适合某些类特定的应用，且基本上都不商品化，而只是为了满足特定的应用 需求而开发的。而对于交易系统而言，其实时性要求非常高，如果采用商业传统 磁盘数据库系统，其实时性很难令人满意。而交易系统对数据的操作事务并不十 分复杂，因此，开发面向交易系统的实时内存数据库系统是必要、可行的。 为此，整个开发团队自主研发了o t b _ m m d b 内存数据。目前，试运行基 于o t b _ m m d b 的交易系统，结果表明整个系统性能获得了极大提高。 1 3 2 本文主要工作 本文主要关注m m d b 的数据恢复技术，研究了主流的m m d b 数据恢复技 术，另外还对o t b _ m m d b 恢复技术做了具体讲述。 第一章中主要介绍了内存数据库的背景知识，以及和传统磁盘数据库的比 较。 第二章对内存数据库的主要技术特点做了讲解，然后讲述了o t bm m d b 的实现框架。 第三章中重点关注内存数据库的恢复技术，主要分日志、检查点、数据重装 三个方砸描述。着重讲述了日志和检查点部分。 第四章是关于o t b m m d b 中如何实现其数据恢复技术的详细阐述。 最后在第五章中，对全文作了个总结及展望。 第二章内存数据库技术概要及o t bm m d b 框架 2 1 内存数据库技术概要 内存数据库和传统数据库有着如此大的差异，显然它们的设计理念必然有所 不同。实际上，m m d b 的出现给数据库管理系统在设计上带来了前所未有的冲 击，提出一些新的设计思想，下面我们根据m m d b 对数据库管理系统一些组成 部分的影响分别加以讨论。 2 1 1 并发控制 比起磁盘的访问速度来说，内存的访问实在是快太多了，一个事务在内存中 完成的速度非常之快。在基于锁的并发控制机制中，这意味着事务锁不会被长时 间占用，锁竞争的程度比磁盘数据库要轻许多。传统数据库系统中般选择小粒 度的锁，比如一个域或一条记录，就是为了减轻锁的竞争。在m m d b 中，锁竞 争的程度比较小，那么降低锁粒度的意义就不大了。因此，很多研究者认为我们 应该选用粒度比较大的锁，比如说锁整张表。极端地，选择这个数据库作为锁的 粒度，这相当于事务的串行化执行了。这看起来相当具有诱惑力，因为并发控制 带来的一些诸如如何管理锁、如何对付死锁问题等都不存在了。并且c p u 的 c a c h e 刷新频率大大降低。( 每次当一个事务在一个锁上挂起等待时，c p u 执行 一个新的事务，所需数据的不同导致c a c h e 的刷新。当串行化执行时候，每次一 个事务执行完开始下一个事务时才需要刷新c a c h e ) 。在高性能的计算机中，c a c h e 的一次刷新相当于数千条指令，可见串行化的增益是非常可观的。然而当长事务 存在时，串行化策略是不适合的，它导致其它事务等待过久。为公平起见，应该 采取让短事务和长事务都能够有效执行的策略。此外，在多处理器系统中，即使 所有的事务都是短事务，还是需要并发控制的。 2 1 2 提交处理 为防止存储介质实效，数据库的备份版本和事务活动的日志备份都是非常必 要的。由于主存是脆弱易失的，日志备份必须要保存在稳定的存储器中。在一个 事务提交之前，它的活动记录必须要写到日志中。这种登记日志的行为对m m d b 性能的影响非常之大，处理不好会导致其速度优越性大打折扣。由于每次事务在 提交之前至少要有一次日志写磁盘，导致事务响应时间受其影响。如果登记日志 是系统的瓶颈，它必然导致系统的吞吐率降低。尽管这些问题在磁盘数据库中也 是存在的，但是这些问题在m m d b 中尤为突出，因为日志登记是每次事务执行 中唯一的磁盘i o 操作。 目前的研究提出了好几种解决方案： 1 使用一块较小的非易失性内存临时存储曰志。当事务将日志记入此存储器 中，一次事务就可阻完成了。有个后台进程负责将此存储器中的数据刷入磁盘。 尽管这种解决方案并没有减轻登记的日志写到磁盘的瓶颈问题，但是它的确大大 缩减了事务的响应时间，因为事务不需要等待磁盘操作了。相关研究试验表明只 需要很小块这样的非易失内存就能满足要求，即使是在高性能系统的情况下。 2 很多场合都没有上述解决方案中所用的非易失性内存。我们这里讨论另一 种预提交的解决方案。一个事务将它的日志放到日志缓冲区后，就认为它已经预 提交完毕，释放它所有的锁，而不关心它的日志信息是否刷入磁盘。日志本身串 行化的特征保证了一个事务不会在它所依赖的事务完成前提交。事务的彻底完成 仍需要等待日志信息刷入磁盘，可见预提交的方式并没有缩短此事务本身的响应 时间，但是它减少了其它并发事务等待锁的时间，加快了依赖于此事务的其它事 务的响应时间。 3 还有一种称之为成组提交的方式可以减轻记写日志瓶颈问题。此方案中， 一个事务的日志并不是在它提交后立即刷入磁盘的。相反的是，允许多个事务口 志在内存中的累积。当累积到一定程度，比如一页满了后，只需要一次磁盘 将所有的信息一并写出。成组提交的方式大大减少了磁盘i o 次数。 o t b _ m i v i d b 采用的预提交和成组提交的结合方式，第四章有详细的描述。 2 1 3 数据访问 在m m d b 中，像b - t r e e s 这样专为块存储设备而设计的索引数据结构失去了 很多吸引力。这个领域的研究比较热门，很多学者提出并且试验了很多种索引数 据结构，包括各种各样的哈稀方法和树方法。哈稀访问的优点是非常快速，缺点 是比树方法费空间，而且不能很好的支持范围查询。目前在m m d b 中应用较广 的是t - t r e e 或其变种。由于内存中遍历深树要比磁盘中快的多，因而m m d b 中 的树不需要像磁盘数据库中b - t r e e s 那么短且粗。 目前很多文献中指出，所有的内存数据访问方法都不必像b 树那样在索引结 构中再存储索引键值本身，因为内存中的随机访问快的多，只要使用一个指针就 能很快的查到索引键值。所以索引结构存储的是指向键值所在元组的指针，而不 1 4 是键值本身，这消除了在索引中存储可变长度数据的管理开销或者压缩键值的开 销，而且也更节省空间。 2 1 4 数据表示 在m m d b 中可充分利用指针来表示数据，例如关系元组可以表示成一个指 向实际数据的指针集合。当大数据出现多次时指针的使用可以减少对内存空间的 占用，因为实际的数据只需在内存中存在一份拷贝即可。指针的使用也简化了可 变长度数据域的处理，因为这些数据值可以存储在堆中，而使用指向其的指针即 可。 2 1 5 查询处理 因为在 m d b 中串行化访问并不比随机访问有多少速度优势，那么为了加 快串行化济问的查询处理技术也就失去了存在的意义。比如一个排序归并i o i n 处理，它首先对两个关系进行排序，这样就能利用串行化访问的优势。尽管在 m m d b 中使用指针队列很容易实现关系排序，但并没有这个必要，因为对关系 排序已经没有什么吸引力了。例如如果希望基于公共属性a 连接关系r 和s 。一 种方法可以是首先扫描一个较小的关系，比如r 。对r 中的每个元组，然后顺着 指向属性a 的指针得到实际值a i ，从那个值我们可以反过来得到所有指向它的 s 的元组。为了这样的方式能够工作，需要在实际的值a i 中保存足够的反向指 针来指向所有的相关元组，这必然会消耗更多的存储空间，但是回报是显著的， 因为这样做所带来性能上的增益是非常可观的。能够这样做的关键原因是在于数 据是存储在内存中的，因此就有可能构建合适的压缩的数据结构以加快查询速 度。 m m d b 查询处理主要关注点在于如何减少c p u 执行代价上，而传统的数据 库系统则更加关注的是如何减少磁盘访问次数。困难的是，在一个复杂的数据库 管理系统中，执行代价是很难衡量的。我们应该先要找出最耗时的操作( 比如创 建索引或拷贝数据) ，设计更好的策略以减少这些耗时操作的发生频率。不同系 统中同样操作的执行代价可能差异很大，所以在某个系统中应用很好的优化技术 在另外一个系统也许根本没有任何效果。 2 1 6 恢复处理 m m d b 必须要在磁盘或者其它非易失性存储器中保存它的备份，以防系统 崩溃导致内存中的数据丢失。恢复处理大体上分为两步，一是系统正常运行时间 断的把内存中新的数据拷贝到磁盘备份中去，二是系统崩溃后从磁盘中恢复数据 到内存中来。 前面已经讨论过了提交处理，它必须保证已提交事务的正确性。大多数系统 是通过写日志的方式来保障事务提交的，而且使用检查点来减少必须被查阅的曰 志量( 如果系统从崩溃中恢复) 。c h e c k l o - o i n t i n g 不时的将内存中新的数据库备 份到磁盘中去，而减少对老日志的依赖。 在m m i ) b 中，正常事务是不需要访问磁盘数据库的，仅仅在c h e c k p o i n t i n g 和系统从错误中恢复时才需要访问磁盘上的数据库备份。因此m m d b 中磁盘的 访闯一般要特别设计以满足c h e c k p o i n t e r 的需要。比如在做o 对尽量使用大的 块。尽管大块写起来时间长些，但是确更有效率。而且只有c h e c k p o i n t e r 在等待 3 i 0 而不是普通事务在等待，所以这样做是必要的。 在做c h e c k p o i n t i n g 的时候应该尽可能的减少它对正常事务的干涉。事务一致 性( t r a n s a c t i o nc o n s i s t e n t ) 或动作一致性( a c t i o nc o n s i s t e n t ) 的检套点技术和正 常事务有较多的同步，它们都属于非模糊检套点技术；对比的是，模糊检查点技 术几乎对正常事务运行没什么影响。这些在第三章中的检查点技术中有详细的描 诉。 2 2o t b m m d b 实现框架 2 2 1 系统主体框架概述 o t b _ m m d b 主体框架图如下所示 图2 1o t bm m d b 框架 l 数据区 保存所有的表数据 数据以内存银行的形式管理( 后有说明) 目前支持最多的数据表个数为2 5 5 个 数据表记录必须是定长的，但对记录的长度没有特别的限制 数据表的记录数只受内存大小限制 2 索引 索引为h a s h 索引，因此只支持等值查询 索引只在打开数据库时构造，在磁盘上没有索引 索引在内存中以内存银行的形式管理 对数据表索引的数量没有特别的限制 索引的最大字段个数可以通过参数设置 如果一张表的索引个数过多，会影响效率 3 日志缓冲 日志分成两级缓冲，私有和公有分开，可以增加并发度 第一级为私有日志，所有事务在未c o m m i t 或未r o b a c k 之前，都 放在私有日志中 第二级为公有日志，事务提交时把日志挂载到公有日志 公有日志在内存中保存了两个可相互切换的缓冲，称为a c t i v e 和 i n a c t i v e 缓冲，正常事务操作a c t i v e 日志，c h e c k p o i n t 事务操作i n a c t i v e 日志，从而做到事务线程和c h e c k p o i n t 线程互不干涉 4 数据字典 保存所有字典信息 字典维护只在离线时进行 5 锁表 保存系统中所有的锁信息 保存一张等待图，每次事务需要等待时，均扫描等待图，入有死锁 则回滚 6 检查点线程 当日志缓冲中日志数量到达一定量时，触发检奄点线程 检查点线程重做i n a c t i v e 日志中的所有日志，把数据同步到磁盘文件 中 一次检查点线程结束，则磁盘文件匕的数据进入下一个完整状态 尽管检查点线程和事务线程完全并行，但由于检查点线程会占用较 多的系统资源，如c p u ，i o 等，因此检查点线程会对正常线程产生 一定的影响 为了避免检查点线程和写日志线程同时写一个磁盘而影响效率，数 据和日志最好分布在不同的物理磁盘上 7 目志刷新线程 日志刷新线程和事务线程通过消息队列通讯 日志刷新线程总是处在待命状态 当消息队列中有需要刷新的日志时，日志刷新线程立刻从消息队列 中取日志 本系统采取每次都取空的方式，即有多少事务即取多少，避免了一 次只刷新一个事务，大大提高了日志刷新效率 同时，用户还可以通过配置参数的方式，设置曰志刷新线程在处理 完所有的事务后，是否要立刻f s y n c 8 数据文件 一张表一个数据文件 数据文件格式为二进制 9 控制文件 控制文件保存数据库目录信息( 数据目录和日志目录) 、完整性信 息 控制文件在创建数据库时产生，数据库恢复程序根据控制文件中的 信息决定是否需要数据恢复 一个数据库对应一个控制文件，不同的数据库不能公用相同的数据 目录和日志目录 数据目录中保存数据和字典表 。 日志目录中保存日志文件 1 0 日志文件 每个数据库有两个日志文件l o g _ f i l e l 和l o g _ h l e 2 日志文件和数据文件最好分布在不同的物理磁盘上 2 2 2o t b _ m m d b 服务层 m m d b 服务层为应用程序提供完整的事务处理能力。 m m d b 服务层为每个应用线程建立一个私有的会话( s e s s i o n ) ，每个s e s s i o n 保留正在处理的事务信息以及一个私有的工作区( 称为局部工作区，l o c a l w o r k s p a c e ，l w s ) 。l w s 主要包括该应用线程当前正在处理的事务的私有数据、 私有曰志缓冲以及向应用程序返回的数据缓冲。 m m d b 服务层体系结构如下图所示： 应用代码 应用层 索b 管理数据字典管理 数据访问层 行管理事务管理 数 据 存 表管理 私有日志管理 储 层 锁表管理全局日志管理 ， 0 操作系统支持 操作系统层 图2 2o t b _ m m d b 服务层体系结构 m m d b 服务层由三部分构成： ( 一) 操作系统层 封装特定操作系统的实现细节，提供对系统同步、内存管理、文件管理和线 程处理等一系列服务的支持。 ( 二) 数据存储层 这是一个通用的m m d b 数据存储引擎，具有数据存储、并发控制和数据恢 复等功能，在这一存储模型中，一张表对应一个内存银行，元组被映射为行，整 个数据存储层提供如下功能： 事务管理：开始提交徊滚事务； 锁表管理：对行加解锁； 行管理：删除，选择，更新，插入行： 表管理：创建，删除表，顺序遍历表，在表尾插入行； 私有日志管理：管理当前枣务的私有日志； 全局日志管理：管理全局日志； ( - - ) 数据访问层 对应用程序提供数据访问接口，内部实现调用数据字典管理接口实现对数据 字典的访问，调用索引管理接口实现对索引的访问和维护。调用数据存储层的事 务管理、行管理和锁管理接口完成数据访问功能。 2 2 3 内存管理 在实际实现o t bm m d b 数据恢复中的装载数据，日志缓冲模块管理等过 程中很多地方都需要对内存操作，所有有必要介绍其服务层中的内存管理。至于 其它所有服务层中的模块，这里就不做介绍了。 为了优化内存分配、释放的执行效率，提高内存访问的安全性，合理解决内 存碎片问题，我们在m m d b 中设置了动态内存管理( d m m ) 模块。d m m 是操 作系统的一次扩展，是m m d b 的最底层，m m d b 中的其它部分，都是d m m 的 用户。 由于使用c 提供的m a u o c 等内存分配接口效率低下，而本程序中需要大量 使用内存块的分配，因此如果直接在程序中使用m a l l o c 会极大地影响整个程序 的效率。而另一方面内存的频繁使用是无法避免的，因此通过采用一种策略性的 内存管理机制来解决这一效率上的问题。一种方式是通过在初始化时分配一块大 内存，之后的所有内存请求都有内存管理模块从这块内存中分配，但是这种方式 对内存的与分配不够灵活，并且在使用内存大小超过该内存块时会有与原内存块 之间的协调问题，因此这里采用的方式是前面两种内存分配的折中，即多次分配 较大内存块，内存请求由这些内存块中调配，当请求内存超过预分配的内存时， 则预分配另一块较大内存块。 此方式使用一种称为内存银行的管理机制，在初始化时先使用m a l l o c 分配 一块较大内存空间，称为b a n k c h u n k ，以后其它模块需要请求内存则从该预分配 内存中划拨出相应大小的内存给请求者。这里有一个前提假设，也就是在内存数 据库中某种特定操作大部分的内存请求都是相同大小的内存空间涛求，这样大小 的内存块称为n o d e 。基于这个前提，这种机制在分配这个特定的内存大小给请 求者后，请求者使用完之后并不释放，而是将这块内存n o d e 的指针放到一个被 称为f f e e f i s t 的数据结构中，以便以后分配给其它请求者使用，在f r e e l i s t 中有这 样的空闲n o d e 时，当有该大小内存的分配请求，优先从f r e e l i s t 中分派，若f r e e l i s t 为空，才从预分配的内存块中继续按地址往后分配内存空间建立新的n o d e 。对 于那些请求大小并不是该特定数值的，则也从预分配的内存块中继续按地址往后 分配内存空间，使用完之后不放入f x e e l i s t 之中，而是任由其空闲。当b a n k c h u n k 空间不足以分配时，新预分配另个b a n k c h u n k ，但是这个b a n k c h u n k 大小可 以和第一块不同，一般略小，主要考虑到内存的使用情况，当这个b a n k c h u n k 也用完后，可以继续分配新的b a n k c h u n k 。如果请求的内存很大甚至超过了 b a n k c h u n k 的最大值，那么就按照它所需的大小分配一个b a n k b l o c k 。虽然这种 非特定大小的内存申请并不多，但时间长了之后仍会有内存闲置，因此会定时销 毁整个内存银行重新建立。这种内存银行对于每一个线程建立若干个，对每个特 定的数据结构可以有一个对应的特存银行，这样有机会聚集较多相同大小的内存 请求。由于线程内事务是串行的，因此在某个事务结束后，可以销毁内存银行而 不用担心会有正在使用的数据被一同销毁。以上所描述的是一种可以申请不同大 小内存的情形，另一种情形是使允许申请和n o d c s i z e 相同大小的内存，主要应 用于内存数据库记录。 第三章r d b 中恢复技术研究 由于m m d b 的主拷贝是驻留在易失的主存中的，因此m m d b 比起传统的 d r d b 更加脆弱容易崩溃。再加上m m d b 系统通常是用在高性能高吞吐高响应 的场合，这更加复杂化了它的恢复处理。f 图给出了m m d b 的一般性系统结构： 图3 1 一般m m d b 系统结构 m m d b 般有这几个组成部分m m ( 主存，m a i nm e m o r y ，一般是普通的 r a m ) ，可选的非易失性内存s m ( s t a b l em e m o r y ) 。数据库的主拷贝在m m 中，因此事务就是在m m 中执行的。s m 通常是用来做日志缓存的，此举可以避 免在事务提交时必须等待g o 将日志写入磁盘，而由一个后台进程将日志异步的 写入曰志磁盘。在很多实现中，s m 对于保证整个m m d b 的性能是不可或缺的 一个部件，但本文提出的o t b _ m m d b 中整套恢复机制不需要使用昂贵的s m 就 可以使系统获得的较好性能。a r c l l i v em e m o r y ，a m ，保存了m m d b 的完全备 份，一般由磁盘构成。 由于r a m 的脆弱性，m m d b 的数据恢复一点以来都是非常活跃的研究领域。 本章主要对m m d b 整个恢复处理作了描述。对恢复技术分三个组成部分l o g g i n g ， c h e c k p o i n t i n g ，r e l o a d i n g 来描述，重点放在前两个部分。l o g 垂n g 记录数据库修 改记录；抵k p o m f i n g 备份内存中的数据库到非易失性存储器中；龇a d i n g 则是 在系统崩溃后，从非易失的备份数据库中装载数据到m m 中，然后根据日志信 息把数据库恢复到最近的一致性状态。l o g 垂n g 、c h e c k p o i 以n 昏r e l o a d i n g 是数据 库恢复处理的三大组成部分。 3 。1 日志概述 3 1 1 日志分类 日志是日志记录的一个序列，每个日志记录都用来记载有关某个事务已经做 某事的一些情况。几个事务的行为可以是“交错的”，因此可能是一个事务的某 个步骤被执行并且其效果被记录到日志中，接着对另一个事务的某个步骤做同样 的事情，然后对第一个事务的下一步骤或第三事务的某个步