（计算机应用技术专业论文）基于监控系统的内存数据库的研究与设计.pdf

浙江大学硕士学位论文 基于监控系统的内存数据库的研究及实现 曹志刚 ( 浙江大学人工智能所，杭州，31 0 0 2 7 ) 摘要 随着新的过程型，时间型等高级数据库应用的不断涌现，支持现代的数据库系统应 该同时提供正确性、及时性和主动性，同时为了满足实时事务的时间限制，提高事务 的可预报性。使得以内存数据库作为应用底层的支持技术，使得对内存数据库技术的 研究成为当前研究的热门。 传统的数据库对实时的支持较少，同时也不支持对时间数据类型，不能描述事务的 定时限制以及复杂的事务结构，这使得对内存数据库的研究处于实际应用阶段，对内 存数据库的研究及应用是为了更好的服务于国民经济。 本文简单的回顾了一些内存数据库的一一些经典的系统，参照工业监控系统的需求， 对内存数据库的数据搜索技术、并发控制、数据的恢复及重装进行了研究，并根据实 际工程的需要，进行了设计：在数据库访问技术当中，我们是对传统的t 树进行了改 进，设置了新的t 十树的数据组织，并给出了具体的操作。在数据库的并发控制当中， 我们提出了新的协议，并在此协议上提出了可恢复的自旋锁的技术：针对数据的恢复 及重装，我们提出了我们自己的算法并在我们的系统中得到了具体的实现。 本文最后对整个内存数据库的研究作了总结，并给出了在研究及实际应用的一些 建议。 关键字：实时数据库内存数据库元数据 浙江大学硕士学位论文 a b s t r a c t a sn e wp r o c e s s e sa n da p p l i c a t i o n sc o m eo u t ，f o re x a m p l e ，p r o j e c t t y p e a n dt i m et y p ee t c ，m o d e r nd a t a b a s es h o u l db ea c c u r a t e ，t i m e l ya n di n i t i a t i v e 。 i no r d e rt om e e tt h ed e m a n do ft i m ei i m i ta n de n h a n c ep r e d i c t i o ni nr e a l t i m e a c t i v i t ya tt h es a m et i m e ，m e m o r yd a t a b a s ew i l lb em o r ei m p o r t a n ta st h eb a s i c s u p p o r t ，w h i c hm a k i n gt h es t u d yo nm e m o r yd a t a b a s ei sp o p r e c e n t l y 。 t r a d i t i o n a ld a t a b a s ei s h a r d l yr e a l t i m ea n dc a nn o ts u p p o r tt i m e t y p e ，a tt h es a m et i m ei ts u p p o r t i n gc o m p l e xa f f a i ri sn o tw e l l 。a 1 lt h ea b o v e r e a s o n sm a k em e m o r yd a t a b a s ep u ti n p r a c t i c e ，w h i c hs e r v e r st h ed o m e s t i c e c o n o l l l i c 。 t h i sp a p e rr e v i e w st h eh i s t o r i c a l d e v e l o p m e n t so fm e m o r yd a t a b a s ea n d i su po ns o m es u t r am e m o r yd a t a b a s es y s t e m s 。w e s t u d ys o m et e c h n o l o g yo f m e m o r yd a t a b a s e ，f o re x a m p i e ，s e a r c h i n gm e t h o d ，i n t e r c u r r e n tm e t h o da n d r e c o v e r i n ga n dr e l o a d i n gm e t h o dw i t ht h ed e m a n do fp r a c t i c ep r o j e c t 。w e i m p r o v eo nt h em e m o r yd a t a b a s es y s t e mo nt h ea s p e c to ft h ea b o v ed e m a n d 。 f i n a l l ye x p e r i m e n t a ls t u d yo nm e m o r yd a t a b a s ei ss u m m a r iz e d ，a n ds o m e s u g g e s t i o n st of u r t h e rs t u d ya n da p p l i c a t i o ni sa l s og i v e ni nt h i s p a p e r 。 k e yw o r d s ：r e a l _ t i m ed a t a b a s e ：m a i nm e m o r yd a t a b a s e ：m e t a d a t a 独创性声明 y 7 0 0 3 9 6 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得滥至三盘茔或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘鲎有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权迸江盘鲎可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名导师签名 签字日期：年月 e l签字e l 期：年 月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 冀鼯毒勿全文公布 电话 邮编 浙江大学硕士学位论文 第一章绪论 1 1 内存数据库概述 内存数据库系统( m a i nm e m o r yd a t a b a s es y s t e m ，m m d b ) 的数据永久驻留在内 存中，而常规的磁盘数据库系统( d i s kr e s i d e n td a t a b a s es y s t e m ，d r d b ) 的数据 则是驻留在磁盘中的。在一个d r d b 中，通过b u f f e r 管理器可以为磁盘数据建立数 据缓存，从而实现对数据的较快访问：而在一个m m d b 中，内存驻留的数据也可能需 要在磁盘中建立备份拷贝从而防止数据库被破坏。关键的区别是在于m m d b 中数据主 拷贝一直驻留在内存中，这对于m m d b 如何构造以及内存数据如何访问都有重要的影 响。 现在芯片的集成度越来越高，内存价格越来越便宜。在内存中存储越来越大的 数据库变得可行，使得m i f b 走向实用。由于数据能够在内存中被访问，m m d b 和d r d b 相比较能够提供更快的响应时间和更高的事务谈吐量。对于那些需要在指定的时间 内完成大数据量的实时应用( 如实时决策系统一雷达跟踪系统等) ，需要提供并发大 数据量访问的处理平台，作为底层的数据库平台，m m d b 是一个理想的选择。 另外，随着处理器技术，内存技术和网络技术的不断发展，移动计算是当前发 展及研究的重点。而移动数据库是移动计算中的关键一环。移动数据库的体系结构 中，其移动终端的数据库管理系统一般都是基于m m d b ，因为移动终端一般没有配备 磁盘，只配备内存，而且大部分是r a m ，少量高端机才配备少量f l a s h 内存。 总之，随着实时和移动应用的不断增加，这一切使得大家越来越关注内存数据 库的实现技术。 1 1 1 内存数据库的定义 内存数据库的研究是一个比较新的研究领域，对什么是内存数据库有下面几种 不同的说法： 观点一：整个数据库全部常驻内存，存取数据时没有i o 操作，这就要求内存足够 大，以容纳数据库的所有数据。 观点二：数据库常驻磁盘。在事务执行前将所需要的数据集调入内存，提交时所有 对数据库的修改必须写回磁盘。 浙江大学硕士学位论文 观点三；数据库常驻磁盘，在内存中开辟一个大的缓冲区，通过适当的缓冲区的管 理以减少内外存i o 操作。 目前，大多数内存数据库系统的建立都是基于第种观点的，然而在现实应用 中，往往难以保证内存总能够容纳整个数据库。因此，内存数据库的含义包含内存 不足容纳整个数据库的情景。而第二、三种内存数据库定义的情况跟基本的常规数 据库系统本质上没有什么异议。跟普通的数据库系统不同的就是改变了数据调入内 存的时机，增大了缓冲区的容量，不能称为内存数据库。 就本人而言，判断一个数据库是否为内存数据库的标准应该取决于其数据库的 主拷贝是否长驻内存，而不能只看内存的大小和存取数据所需要的i o 次数及数据 被调入内存的时机。因此，我们对内存数据库给出如下的定义： 定义1 设有数据库d b ，t s 为所有事务构成的集合。v t t s ，d ( t ) 为t 的操作 数据集( d ( t ) 量d b ) ，d b m ( t ) 是t 时刻d b 在内存中的数据集( o b y l ( t ) d b ) ， a t ( t ) 是t 时刻的活动事务集，a t ( t ) 5 t s 。 若在任一时刻，均有v t a t ( t ) d ( t ) 互d b m ( t ) 成立，则称d b 为一个内 存数据库，简称为m m d b 直观地说，m m d b 就是指数据库的“工作版本”( 当然也可以是整个数据库) 常 驻内存，任何一个事务在执行过程中没有内外存间的数据i o 。当然，它需要一定 的内存容量，至少要能容纳一个事务所需要的数据集，但不一定需要容纳整个数据 库的容量。活动事务的执行从开始到提交，均不与外存打交道。当事务提交到数据 库的外存版本时，可以不必立即反映事务提交后的结果，并且当系统出现故障时应 首先恢复在内存和总的数据库主拷贝。 需要指出的是，对于传统的数据库结构体系，即使其缓冲区足够大，大到可以 容纳所有的数据及其工作版本也不能算是一个m m i ) b ，因为它是针对磁盘特性，在假 设数据库常驻磁盘的情况下设计的，即使其它的性能较好，也不具有所有的m m d b 的特性和优点。例如，索引结构是针对磁盘存取的，数据的存取要经过缓冲区的管 理，这势必影响存取效率。因此，内存数据库的设计应完全打破传统磁盘的数据库 的设计宗旨，设计全新的实用内存特点的算法和数据结构。对于内存数据库的物理 数据结构、存取方法、查询处理及优化、并发控制及数据库恢复都应有新的方法和 策略，以便更有效利用内存空间并提高系统性能。 1 1 2 内存数据库和磁盘数据库的区别 计算机的内存和磁盘有着完全不同的属性，这些差异对数据库的设计和性能有着 深刻的影响。尽管这些差别是众所周知的，但简要的回顾一下这种差别还是很有意 义的： 内存数据的访问时间比磁盘数据的访问时间低好几个数量级。 内存是属于易失性存储介质，然而磁盘不是。所谓易失性。就是指断电后内存上 2 浙江大学硕士学位论文 的数据全部丢失，而磁盘则能永久保存数据。然而，有可能建立非易失眭内存，如 通过u p s ，新的f l a s hm e m o r y 技术或者昂贵的s r a m 。 磁盘访问的代价很高，每次访问都有很高的固定访问开销，而不是这次访问实际 上所需要获取的有用数据大小。例如每次访问，都会从磁盘中获取一个扇区的数据， 即使需要的只是这个扇区中的一个字节，正是这个原因，磁盘被看作是块设备，而 内存则不是。磁盘中数据的布局，比起内存中数据的布局，对于数据库的整体性能 要关键的多，因为对磁盘的序列访问比起随机访问要快多了。可以设想，如果相关 数据尽可能的在一个扇区，访问这些数据的开销要小得多。而在内存中，序列访问 则显得相对不那么重要，但是可以在以后的分析中发现，由于现代计算机中c a c h e 对系统性能的相当大影响，c a c h e 一致性的数据布局也是很重要的。 内存一般而言是直接被处理器访问的，然而磁盘不是。这意味内存中的数据比起 磁盘数据更容易受到软件错误的毁灭，如应用程序的错误或操作系统的致命性错误。 由于这些的性质差异，m m d b 和d r d b 相比，在以下五个方面提高了系统性能： 连接开销传统：d b m s 使用多地址空间体系，有利于进程保护，但是实时性能严 重降低。而无论是实时系统还是嵌入式系统，一般而言都是应用专有系统，意味整 个系统一般只存在一个应用，所以m m d b 一般而言都直接和应用代码链接在一起，违 约单一进程地址空间，这使得应用和阴之间的连接开销最小。 地址翻译开销：m m i ) b 中，系统直接指向某一记录的内存位置：而传统的d b m s 中， 系统指向一个块号和块内偏移量。系统必须定位这个块，然后把这个块装载进内存 b u f f e r 中，然后再通知d b m s 数据在内存b u f f e r 中的具体位置。 b u f f e r 管理：传统d b m s 假设磁盘中的新数据最终要替换掉内存b u f f e r 中的老 数据。所以内存b u f f e r 不断的增加它们的“年龄”，当“年龄”到一定程度时，一 个特殊的线程或进程负责把这些足够老的内存b u f f e r 写入磁盘中，并且修改该内存 b u f f e r 的状态标志。而m m d b 完全不需要有b u f f e r 参与管理。 内存拷贝：在基于磁盘的d b m s 中，应用从不直接访问系统中的数据记录，而是 把它拷贝到应用私有进程空间的某个地址后再访问，这又增加了系统的负担。而 m m d b 则可以直接访问数据。 兼容开销：传统d b m s 添加了大量的代码，以便和一些过时的特性兼容。这些特 性是随着2 0 多年来传统数据库的发展一起建立起来的，而这些特性现在以及被新的 标准和现代方法所取代。但是m m d b 则没有这些问题。 1 1 3 内存数据库的应用 内存数据库的应用非常广泛，常用的应用有下面几种。一种是大型应用，这种应 浙江大学硕士学位论文 用要求能够尽可能快的处理海量数据，有的甚至有实时性要求，例如电子商务、数 据仓库、网络管理、事件跟踪和决策系统、图像匹配、电信领域和仓储控制等领域 的应用。这些应用需要把数据库全部或者至少是最关键的那些数据放到内存中由 m m d b 管理；另一种则是嵌入式系统和移动计算。随着信息产业竞争的日趋激烈，移 动通信技术发展迅速，智能化终端产品将不断涌现；移动计算硬件平台的技术改进 和价格的不断下降，移动电子商务应用解决方案的不断完善，这一切都使得企业对 移动计算需求稳步增长。随着无线数字化将随着移动计算的发展一步一步向我们走 近。随着移动数据库的发展，我们才真正进入了一个信息无所不在的信息时代。通 过具有移动计算功能的移动急速机、汽车、手机甚至手表等新一代的智能化设备。 随时随地的移动数据库连接所需要的信息系统，获取所需的信息，这将大大地改变 人们的生活方式和工作方式。 这里举几个应用的实例，可以感性的了解m m d b 的强大性能、功能和实旋的可行 性和必要性。 1 图像数据库系统。这种系统的目的在于搜索出和用户所提供的一个图像尽可 能匹配的所有图像。例如，一个正在设计时装的设计师也许想找到所有花纹是黑白 斑纹的图片。在这样的一个数据库中直接搜索图像是非常耗时的，因为图像很大， 每个图片可能有1 0 0 k 甚至更大。所以多媒体d b m s 为每个图像产生一个特征矢量， 这个矢量用来衡量图像表现出来的某种特征。例如颜色、文字、花纹、特征矢量， 这个矢量比起整个图片来说小得多了，一般说来只有百分之一大小( 这个技术广泛 应用于公安部门的刑事侦察中) 。假如整个数据库中有1 0 0 ，0 0 0 幅图片，每个图片 大小大约l o k ，那么整个图像数据库将占有1 0 g 的空间，但是使用特征矢量则只需 要1 0 0 m 。这样存储整个数据库在内存中就不经济了，相反存储特征矢量将变得可行 的，而且也是必要的。这样傲可以大大降低搜索时间，因为唯一的磁盘访问只是用 例读取匹配用户需求的图像矢量。没有这样的改进，图像搜索对于许多应用如c a d 和安全系统的人脸识别系统等都是不切实际和不可能的。 2 雷达跟踪系统。常规的d b m s 把数据存储在磁盘中，这是因为常规数据库应用 要求数据的持久性，也就是说再关闭计算机后再重新启动它，数据也不会丢失。但 是对于雷达跟踪系统而言，如果不能在几分钟内跟踪到有用的数据，那么那些跟踪 历史数据就再没有什么用了，这样的系统中，d r d b 完全没有必要，相反m m d b 却不 仅合适，而且必要，因为如果不能再限定时间内锁定目标，那么灾难也许将是致命 的。 3 移动计算能够极大地提高实地调查或实地工作的效率。煤气、水、电等公用事 业检查员检查数据就是一个很好的应用实例，目前的检查员一般仍是将检查的数据 记录在纸上。然后再回到局里通过上传就可把数据汇总到中心计算机系统中，再遇 到纠纷时就可以实时查询历史数据，这将使得我国公用事业的收费工作大大改善。 4p s 导航系统。 主要的技术就是把g p s 接收器收到的地形特征和掌上电脑系统 事先从p c 或其他系统上的地理数据库中下载的地理数据进行匹配，从而再显示屏上 浙江大学硕士学位论文 绘制从而起到导航作用。 1 1 46 4 b i t 的计算机一未来的趋势 现代应用开发的趋势将是充分利用大内存，而i n t e r n e t 的发展日新月异，使得 基于w e b 的高速，实时事务处理系统越来越多。g a d b 的大型应用市场将因为越来越 大，这将导致m m d b 研究的蓬勃发展。 但是我们知道就目前的3 2 位的计算机只能对4 g b 内存进行编址。这个限定将严 重妨碍m m d b 技术的发展，因为现代海量处理机要求能够迅速的处理数十g 的数据， 幸运的是，6 4 位的计算机已经开始出现，基于6 4 位的处理的c p u 已经使得寻址范 围扩大到1 6 0 6 。这可以在一定程度上满足多年的需求。 1 2m m d b 的研究现状 本文前面已经分析过了，m m d b 系统应该完全重新设计。接下来，本文要讨论数 据驻留在内存对d b m s 部件的影响以及目前删d b 优化技术。 1 2 1 并发控制 由于访问内存数据非常快，事务在内存中停留时间会很短。在基于锁机制的数 据库系统中，这意味事务占用锁的时间不会很长，锁竞争( l o c k c o n t e n t i o n ) 的程 度不如在磁盘系统中那么严重。选择很小锁力度( 如域或者元组) 的系统是为了降 低锁的竞争程度。如果竞争已经很低了( 就如d b 中一样) ，那么降低锁粒度的一 样就不是很大了。正因为如此，有些m m d b 系统实现或者相关论文建议使用非常大的 锁粒度，例如锁粒度建立在整个关系上。 如果走极端的话，可以选择整个数据库作为锁的粒度，这就相当于事务的串行 化执行，串行化执行事务是非常有诱惑力的，因为并发控制的代价( 如设置和释放 锁，处理死锁等) 几乎完全消除了。而且c p u 的c a c h e 刷新和具备虚拟内存管理机 制处理器的t l b 刷新次数将大大降低( 这种具备虚拟内存机制的c p u 存取数据时， 并不是直接引用物理地址，而是要通过指向物理地址映射的虚拟地址，从虚拟地址 到物理地址映射的最近结构就存放再t l b 中，t l b 通道数量的提高和减少t l b 失效 并从新装载的次数就大大提高系统的性能) ，这是因为每当一个事务由于等待一个锁 被中断，将会有一个新事务准备运行，那么c p u 缓存的内容不得不相应替换，t l b 也不得不被刷新。在高性能计算机上，刷新c a c h e 相当于数千条指令，串行化的增 量是相当高的。但是串行化执行事务在某些情况下可能不合适的，尤其是长事务存 浙江大学硕士学位论文 在时( 例如对话事务、移动计算环境下事务执行) 。因此为了公平起见，应该有一些 方法能够运行和长事务并发执行的短事务。而且目前在海量计算中，多处理机的应 用是普遍的，那么即使所有的事情都是短事务也要求某种并发控制机制，否则多处 理机的优势将大打折扣。 锁机制的实现也能够因为对象驻留在内存而进行优化。在d r d b 系统中，锁是通 过一张h a s h 表来实现的，这张表含有当前被锁住的对象及其占有事务与等待事务的 列表。这张h a s h 表位于内存中，磁盘上的对象自身不带有任何锁信息。但在m g d b 中，对象处于内存中，可以在对象本身上添加一位比特来表示它的锁状态。 这里演示一种当前实现中普遍采用的思想，出于简单考虑，这里只考虑排他锁。 每个对象增加两个位来代表锁信息，如果第一位被置位，那么意味着对象已经被锁 住了，否则对象可以使用；如果对象被锁并且第二位也被置位，那么系统中最少有 一个等待这个对象的事务，这些等待事务的i d 存储在一个常规的h a s h 锁表中。如 果一个事务试图去锁住另一个对象时，它首先检查第一位，如果没有置位，这个事 务设置该位就完成了设置锁的过程( 当然要某种“t e s ta n ds e t ”指令来防止另一 个事务同时设置这个位，本文把这样的锁叫做系统锁，像信号量机制，而数据库系 统中用于并发控制的锁我们称为数据锁) 。如果第二个事务希望使用这个对象时，它 设置第二个位然后把自己添加到该对象的等待事务列表中去。 当原来的那个事务要释放锁时，首先检测到该对象的第二位是否释放置位了， 如果没有，则没有事务在等待该对象，那么它只对第一位复位就可以了；如果第二 位置位，可以通过常规过程来唤醒等待的事务，这里显然省略了很多细节。演示这 个优化的过程的目的在于，类似的实现大大降低了并发控制的代价。因为在m m d b 中最可能的情形就是低竞争的情况，这就是说一个事务通常只是锁住一个对象，修 改这个对象，然后在任何别的事务等待该对象前就释放这个锁。这样的情形下，获 得和释放这个锁只需要使用最少的指令集，免去了查询h a s h 锁表的开销。这样的改 进时很有帮助的。当然，这样的方法带来了额外的空间开销。但是典型的数据库记 录一般都是有几十个字节甚至更多，两个比特位的开销是很低的。 本文除了介绍一种动态锁机制外，还在该机制基础上进一步的改进。提出了一种 多版本并发控制方法，这种机制使得只读事务不需要申请任何数据锁或者系统锁就 可以执行，这样就保证修改事务不会影响只读事务，保证了只读事务快速响应。而 吼d b 很大的一个应用范畴都需要处理只读事务。 1 2 2 提交处理 为了防止介质失效，在磁盘中进行各份并且记录下事务活动的日志是必要的。 既然内存通常都是易失的，日志一定要驻留在可靠性存储里，如f l a s h 或者磁盘中。 在事务提交之前，事务的活动记录一定要写入日志( l o g ) 。 浙江大学硕士学位论文 等待日志的过程将会影响事务的响应时间，因为每个事务在提交事务之前都要 等待至少一次写磁盘的时间。记录日志也会影响整个系统的吞吐量。尽管这些f q n 在d r d b 中也存在。但是在内存数据库中这个问题显得尤为突出，因为登记日志是每 个事务执行过程中影响要做的磁盘i o 动作。 目前有好几种方案用来提出用来解决这个问题。 使用很小一块可靠内存来保存一部分日志。事务一旦把日志信息写入这块稳定内 存就提交完成，相对而言非常快。然后，一个后台的进程或线程负责把这块内存的 数据拷贝到日志磁盘中，尽管这种方法并没有很好的解决日志的瓶颈问题，但是它 消除了响应时间很慢的问题，因为事务无需等待磁盘操作就可以提交了。有研究表 明只需要很少的可靠内存就足够了，即使在高性能系统中，但是这种方法的最大的 缺点也就在于需要额外的可靠内存，并不是任何场合都提供这种可靠内存的。 在没有可靠内存的情况下，可以采用接下来描述的两种登记日志的方法，其中 之一是预提交方式。所谓预提交就是一旦日志记录出现在日志缓冲区时就宣布事务 预提交完成。同时释放该事务所有的锁，不需要等待缓冲区的日志记录刷新到磁盘 中。日志记录自身的串行性保证了事务不会在它所依赖的事务之前提交。由于事务 的提交仍然要等到日志信息写入磁盘，所有这样的方法并没有降低事务的响应时间。 但是却能够降低别的并发事务的阻塞迟延，也相当于就是提高了整个系统的吞吐量。 组提交方式是一种能够解决日志瓶颈问题的方法，在组提交方式下，事务的日 志记录不会在提交时刻立刻写入日志磁盘，相反多个事务的日志记录可以在磁盘的 缓冲区内积累，当积累到一定程度时，例如一个页面被充满了，那么所有这些事务 的日志通过一次操作写入磁盘。组提交方式降低了日志磁盘的操作的总次数。因为 一次磁盘操作提交多个事务。 1 2 3 数据访问技术 在内存数据库中，像b 树这样专为块存储设备而设计的索引数据结构将失去优 势。为了加快m m d b 的数据访问速度，已经提出并且比较了很多的索引数据结构，包 括常用的h a s h i n g 方法和树方法。h a s h i n g 提供了快速的查询方法，但是空间利用 率却不如树，而且不支持范围查询。而一些树结构如tt r e e s 是专为m m d b 设计的， 目前的产品实现中普通采用了t 树或者是其的变种作为索引方式。内存中的树不像 b 树那样浅，因为在内存中遍历更深的树比在磁盘中要快得多。 过去的一些论文认为，所有的内存数据库访问方法都不必像b 树那样在索引结 构中再存储索引键值本身，因为内存中的随机访问要快的得多，只要使用一个指针 就能很快的查到索引键值。所以索引结构存储的是指向键值所在元组的指针。而不 是键值本身，这消除了在索引中存储可变长度数据的管理开销或者压缩键值本身开 销，而且更节省空间，因为指针的大小一般比实际的索引键值要小得多。 但是随着c p u 的速度越来越快，c p u 和内存数据访问差别越来越大，c a c h e 命中 浙江大学硕士学位论文 与否对软件的性能影响越来越大。而在索引结构中存储指针，显然带来了一个重要 的性能隐患，那就是查找失效和t l b 刷新，造成键值比较的开销非常大。而b 树这 样的结构由于存储实际的键值，所以c a c h e 命中率很高，但是相对而言空间效率很 低 1 2 4 数据表示 原有的内存数据库充分利用指针来表示数据，例如关系元组可以表示成指向实 际数据的指针的集合。当大数据出现多次时，指针的使用可以减少对内存空间的占 有，因为时间的值只需要在内存中出现一次。指针也简化了可变长度数据域的处理， 因为这些数据值可以存储在堆中，而关系可以用一种紧凑的方法来表示，但是相对 于管理指针的优点，还是可以使用指针。而且只用于查询出来也有相当大的好处。 1 2 5 查询处理 既然序列化访问的好处在于m m d b 中不显著，那些充分挖掘更快序列访问技术的 方法也失去了自己的优势。一个例子就是归并排序j o i n 处理，这种方法首先对两个 关系进行排序，这样就能利用序列化访问的优势，尽管在 i 旧b 中使用指针队列很容 易实现关系排序，但是真的没有必要做这样的处理，因为对关系排序已经没有什么 好处。 当关系的元组使用指针集合队列来实现时，一些关系的操作现在就可以非常有 效的执行。例如，如果希望给予公共属性a 连接关系r 和s 。一种方法是首先扫描 一个较小的关系，比如说r 。对r 中的每个元组，然后顺着指向属性a 的指针得到 实际的数值a ，从那个数值我们可以反过来得到索引指向他的s 的元组。为了这样 的方式能够工作，需要在实际的数值a ，中保存足够的反向指针来指向索引的相关元 组。这显然增加了m m d b 的存储空间，但是有足够的数据表明，这样做所需的性能提 高是明显的，关键在于数据是存储在内存中，这样就可能建构加快查询的数据结构。 内存数据的查询处理的关注的焦点是放在c p u 处理代价( 也就是c p u 指令数上) ， 然而大部分d r d b 系统关注的是如何降低磁盘访问次数。然而一个难点在于一个负责 的数据库管理系统中很难衡量处理的代价。必须首先找到那些耗时的操作，然后使 用恰当的策略来降低执行这些操作的次数，接下来再对这项操作的实现进行优化。 具体某个操作的开销再系统之间的差异是很大的，所以一个系统中做的耗时优化技 术在另一个系统中却可能导致系统整个性能不大，甚至下降。 浙江大学硕士学位论文 1 2 6 恢复处理 内存数据库必须在一个磁盘或者别的某种稳定可靠存储上维护一个备份以防止 易失性的内存数据突然丢失。恢复处理由几个部件共同完成，整个过程可以分为两 个部分，一个就是在数据库正常的事务操作过程中把最新的数据库拷贝更新到磁盘 中的过程；第二个技术用于在介质失效或软件出错后使用最新的数据库备份和日志 恢复到尽可能新的一致状态的过程。 一般说来，记录日志必须满足下面三种策略。 w a l ( w r i t ea h e a dl o g g i n g ) 也就是说必须在修改数据库之前要把u n d o 日志 记录存储在非易失性存储器中，这用来保证在未提交事务时能够回滚。 l a w ( l o g g i n ga f t e rw r i t i n g ) 也就是说必须在对内存数据库的修改操作完成后 才把r e d o 日志记录写入非易失性存储中( 磁盘或非易失性内存) 。它和一种检查点 方法想配合，能够非常简单的判断重装点的位置，并使得所需查找的日志量最少。 r e d o 规则，也就是说一个事务只能在它的索引r e d o 日志记录全部刷新到非易失 性存储中才能够提交，这用于保证，如果一个事务已经提交，那么d b m s 必须保证能 够一直反应这个事务对数据库的全部修改动作，不论是否该系统会失效。 已经讨论了提交和记录日志过程，大部分使用习志提交的系统也会指向数据库 的备份或者检查点，这样做的目的是减少系统失效后用于恢复处理的日志量，提高 恢复速度。检查点过程就是使得磁盘上的数据库拷贝更新，这就消除了对较老日志 项的依赖。 在一个内存数据库中，检查点过程和失效恢复是访问磁盘数据库拷贝的唯一动 作。应用事务从不需要访问那些磁盘数据库。所以，内存数据库中必须设计专门的 磁盘访问技术以满足专门的检查点过程需求。应该尽量的使用更大的块来执行磁盘 i o ，块越大，写盘的效率越高，尽管这需要花费更长的时间，但是只有检查点过程 需要等到这些磁盘i l o 操作完成，而不是应用事务，对于应用的影响是很小的。 检查点过程应该尽可能少的影响事务处理。事务一致性的方向或者动作一致性 的方式都要求和应用事务进行某种同步。但是一种失真转储的检查点方法却不是要 求任何同步的过程，f u z z yc h e c k p o i n t i n g 证明是最好的一种m m d b 检查点方法，因 为它对事务正常处理的影响非常小。 相对而言，日志信息可以位于不同的抽象层次，在系统中，主要是物理日志和 逻辑日志两种，物理臼志意味着修改操作前后的数据库状态被记录下来。只记录了 存储单元的物理地址( 例如页号，段号，偏移量，长度) 。而逻辑日志页包括了更高 层的数据库描述，例如关系，元组，属性，以及数据库的状态转移情况。逻辑日志 的好处在于能够解释操作的语义以及占用更少的空间( 因为记录状态转移和逻辑操 作要求少的多的日志项) 。但是这样的好处是有代价的，逻辑日志使得系统在事务 正常处理和系统重启时都负责的多。这对很多实时应用是不可接受的，对于一些处 理能力不是很强的嵌入式应用也是很不实用的。所以在删d b 种，本论文采用了记录 物理日志的方法。 系统崩溃后，m m d b 必须使用磁盘备份重装数据，然后在这个备份基础上根据日 志施加操作，从而恢复到最近的一致性状态。如果数据库很大，只是简单的把数据 浙江大学硕士学位论文 从磁盘中转让内存的方法就会耗费很长的时间，这对于一些实时应用是无法接受的 ( 例如一些电信系统中的应用，即使系统“荡”掉几十秒，也会带来几十万的损失) 。 一种可能的解决方案是按需装入数据库，直到数据库完全装入，在整个数据库装入 之前就容许应用提交事务。另一种可能的解决方案是使用磁盘阵列，数据库的备份 分别在多个磁盘中，可以并行的从不同盘中读取数据。 以上的分析清楚的表明，整个恢复过程可以看作是l o g g i n g ，c o m m i t t 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 ，r e c o v e r i n g 这一系列相互影响，需要相互协同，甚至 并行的动作，这样也可以看出恢复过程的复杂性。 1 2 7 性能分析 性能是到目前为止本文讨论的所有数据库管理部件都关注的焦点，除了提交处 理过程外，内存数据库系统的性能主要取决于处理时间( 也就是说c p u 指向时间) 而不是磁盘i o 。即使是恢复管理，尽管牵涉到整个磁盘，仍然主要是通过处理器 来影响性能，因为正常的事务处理过程一般不和磁盘操作相关。大部分m m i ) b 技术就 是根据处理代价来衡量性能的，也都是以处理代价为参数来建模，这和传统的d r d b 完全不同，这些系统一般都是根据指向的i o 操作次数来衡量一个算法的优劣。 不仅仅衡量性能的指标是完全不同的，而且需要重点分析的数据库管理系统的 部件也不杀完全一样的。例如，常规系统中，在事务执行过程中备份( 也就是检查 点) 并不影响系统性能但是在m m d b 中，c h e c k p o i n t i n g 却需要认真研究。正如本 文指出的那样，m m d b 系统中的备份需要更频繁的备份，并且是备份到一个比内存慢 一个数量级以上的磁盘设备。这样，备份算法的性能就非常关键了，需要特别认真 的研究。本文仔细研究了恢复管理、并发控制这两个主题。 l - 2 。8 应用编程接口和保护 常规d r d b 中，应用和d b m s 之间通过私有的空问进行数据交换。例如，为了读取 一个对象，应用系统向数据库管理系统申请，以对象i d 和自己地址空间的缓存地址 作为参数。系统从磁盘中读取数据进入自己的b u f f e r 空间，然后再拷贝到应用提供 的私有空间中。为了写数据，应用修改自己空间的数据，然后调用系统，系统把修 改过的对象拷回自己的缓冲中，写入相关得到日志记录，再在合适的时候刷到新的 磁盘中。 而在删d b 中，访问一个对象可以更有效率。首先，应用可以使用对象的时间内 存位置，而不是更一般性的对象i d 。例如，当应用系统首次引用某一个元组时，它 可以使用关系名字或者主键数值。在首次读之后，系统返回元组的实际内存位置， 用于接下来的访问。这避免了开销很大的地址翻译。但是这使系统不得不在那个位 浙江大学硕士学位论文 置一直保留这个对象，至少到引用该元组的事务退出前不得移动对象，我们使用了 一种快速地址翻译机制，返回给应用系统的是一个内存块号。 其次，也许可以容许可以事务之间访问对象，而不需要使用应用私有的存储空 间，性能会有很大的提高，因为如果事务很简单的话，大部分的指向开销是花在了 数据库空间和应用空间之间的拷贝上。如果能够减少这样的拷贝，一个事务指向的 指令数有可能减半，甚至更多。但是这样的失效机制有可能带来两个问题：一旦一 个事务可以之间修改内存数据库，它也回读取或修改没有授权的数据；系统没有办 法知道修改了什么东西，也就不可能进行日志登记。索引本文仍然使用了间接的方 法，来实现相应的监控。 1 3 本文的工作 本文从理论和实践两个方面对内存数据库的体系结构和不同的部件进行系统的 研究，主要做了三个方面的工作。首先，通过实际的工作和大量的文献，对现有内 存数据库系统的体系结构和实现方法进行了研究，借鉴了其中的有效算法和机制， 同时发现了其中存在的问题：其次，通过对现在计算机体系结构和处理器发展的研 究，针对m m d b 系统性能主要取决于c p u 执行指令数的特征，从考虑m m d b 的主要应 用场景，对m m d b 的关键组成部分提出了自己的设计方案：并将这些技术应用于一个 实际的m m d b 系统中。下面介绍了一些本文的简要内容。 第二章主要是介绍m m d b 的索引结构，尤其详细的介绍适合m m d b 系统的树型结 构，主要是b 树和t 树。内容主要包括数据库管理系统中索引数据结构及其分类，b 树及t 树。 第三章主要是研究了m m d b 系统中并发控制机制。针对m m d b 中数据竞争少的环 境，开发出最少代价的并发控制机制，提出了一种能够根据系统运行过程中负载和 竞争的变化而自动调整锁力度的动态机制：同时针对m m d b 中主要的应用场景之一是 只读实时应用这一假设，提出了一种不需要任何锁和系统锁就可以执行只读事务的 机制，两种机制的结合会大大改善系统的效率。 第四章主要时研究恢复重装技术。正如我们在以前所讨论过的，恢复机制对整 个系统的性能影响很大。本文对在没有可靠性非易失内存的情况下恢复管理所牵涉 到的各个动作都进行了重新考虑，完整介绍了实现中采用的恢复和重装技术，提出 了恢复算法和重装算法，并在系统中得到了实现。 第五章主要是对本文的小节，展望了m m d b 的将来的发展方向。 浙江大学硕士学位论文 第二章数据库访问技术 2 数据库访问技术概论 尽管在m m d b 系统中，关系是存储在内存中，但我们仍然需要使用索引技术来加 快数据访问速度。本文介绍了旧的和新出现的数据库索引技术，判断在内存数据库 环境下究竟什么样的技术是比较省内存空间而又速度较快的，并且在新的计算环境 下对已有的技术重新考虑，提出了一种新的数据索引技术，获得尽可能佳的效果。 索引结构可以分成两大类，一类是树结构，一类是h a s h 结构，但是 l a s h 结构太 浪费空间，并且不支持范围检索，所以本文只考虑树结构。本章内容主要是两部分 组成，第一部分主要是介绍数据库索引技术，着重介绍了t 树，这是一种从a v l 树 和b 树进化而来的树结构。这种结构专为内存数据库设计，具有很多优点，已经在 非常多的产品和项目被采纳使用。第二部分主要介绍了在计算机技术飞速发展的今 天，由于c p u 速度越来越快，和内存速度的差异越来越大，正是在这样的背景下， 本文讨论了一种对树型结构加以改进的技术索引技术，能够以较小的存储代价获得 较高的性能提升，在空间和时间方面有了一个平衡，并在我们的系统中得到了实现， 效果还比较明显，相对平常的传统的数据库系统有一定的改进。 2 1 几种常见的数据组织结构 目前，对于树型多维索引结构的研究成果很多，其中最具有代表性的就是k d 树和r 树。但在内存数据库( b ) 系统中，由于数据库工作版本常驻内存，先前 所说的相对于传统数据库的索引技术已经不再实用了，因为它们每个节点的覆盖率 不超过5 5 ，这对内存空间极为宝贵的m m i ) b 来说存储效率太低。而t 树是目前最 为流行的内存数据库索引结构，它的特点是在一个树节点中保存多个记录的键值， 每个节点只有两个指向子节点的指针，与前面我们所提到的索引技术而言就节约了 大量指针占用的内存空间。它在一维索引的情况下不管是精确查询还是范围查询都 是一个比较理想的选择。但对于多维的情况效率却不高。我们下面介绍了k d 树 和r 树的特点及其在m m d b 系统中缺点：然后介绍了t 树的特点及其操作，并分析 了它在多维索引情况下的缺点，并根据其不足，提出了一种对其采用网格来降低维 度的改进方法，不仅提高了搜索速度，同时也提高了内存利用率。 浙江大学硕士学位论文 2 1 1 k d 树简介 k - - d 树是一种k 维空间中的一种二叉查找树，它主要存储的是点数据，在每个 内部节点系统中，它用一个k l 维的超平面将节点所表示的k 维空间分成两个部分， 这些超平面在k 个可能的方向上交替出现，而且在每一个超平面至少要包括一个点 数据，见下图是一个k d 树的例子； a 图2 - 1k d 树结构示意图 g k - - d 树的查找和插入操作是很简单的，而删除操作则有点复杂，因为一个点的 删除可能会导致它的子树重建。由于k d 树只能处理点数据，因此对其它具有一定 形状的数据只能用它们的中心点来代替。需要指出的是当数据插入的顺序不同时， k - - d 树的结构也不同，而且数据会分散到树的任何地方，而不会只出现到叶子节点。 由以上介绍可以看出，k d 树是种多维二叉树结构，因此对于传统给于磁盘 的数据库系统，有很好的索引效率。但由于每个节点仅包含一个数据节点和两个指 向左右孩子的指针，这对内存空间极为宝贵的内存数据库来说存储效率太低，所以 不是很适合内存数据库。 2 1 2 r 树简介 r 树是一种类似卧树的多维索引结构。它的每个中间节点存储的不是数据，而 是索引子节点的最小外接矩形，实际数据都保存在叶子节点中，所有的叶子节点都 出现在同一层上。 浙江大学硕士学位论文 r 树的查找算法是从根节点出发，对内部节点，检查每一项是否与要查找的区域 重叠，如果重叠，则检查该项所指向的子节点，直到找到叶予节点。插入操作首先 从根节点开始，在经过的每个内部节点中选择为容纳下插入节点其m b r 的面积扩 大为最小的项，到达叶子节点后插入节点，并按原路径返回依次修改其祖先节点的 m b r 。删除操作首先进行一次精确查询，如果找到该节点，则将其删除，并依次修改 其祖先节点的m b r 。 由以上的介绍我们可以看出，r 树的结构类似于b + 树，因此它满足减少磁盘访问 次数和检索速度快的要求。但由于它将所有数据保存在叶子节点中，中间节点只保 存子节点的相关信息，所以r 树的内存空间浪费很严重。其对应的结构图见下图： a 2 1 3 t 树及其操作 图2 - 2