（计算机应用技术专业论文）空间数据库缓冲区和大对象存储的研究.pdf

重庆邮电学院硕士论文 摘要 近年来，随着传统数据库技术的发展，以及计算机处理能力的不断加强，g i s 技术也取得了迅速的发展，其应用范围也越来越广，空间数据库的建设越来越受 到重视。但由于空间数据自身具有数据量大、数据之间的关系性强、数据内容包 含较多的大对象等特点，传统的数据库管理系统在处理空间数据方面显得能力不 足。为了提高处理的效率，并满足g i s 系统的各种特殊需求，就需要根据空间数 据的特点，量身定做专用的空间数据库系统。 本文首先系统地介绍了空间数据库系统及其相关理论知识基础，接着，从总 体上给出了空间数据库系统的设计方案。最后，分别就缓冲区和b l o b 存储系统 的设计和实现作了详细的介绍，并进行了一些开创性的研究。 本课题着重对以下两个方面的内容进行研究： ( 一) 缓冲管理模块的设计与研究：研究了缓冲区管理模块的总体设计方案； 然后分别详细介绍了缓冲管理模块的内部结构，并对其四个重要组成部分分别作 了深入的介绍；接着，通过详尽的算法描述和说明，阐述了缓冲区管理模块的具 体实现方法，并提出了对现有算法的改进方案；最后，结合空间数据之间相关性 强的特点，提出了“相关数据预读入缓冲区”的方案，给出了方案的严谨的定义， 并对其作了细致深入的分析，最后给出了相关的算法和实现方法。 ( 二) b l o b 存储管理的研究：在这一部分，作者先从总体上介绍了b l o b 管 理模块的总体设计和内部槊构，然后，给出了它的详细设计思想和具体的实现函 数，最后，结合空间数据中b l o b 数据的特点，对扩展b l o b 数据类型和在b l o b 数据内部进行检索进行了一定的研究，并给出了相关的方案。 构建完善的空间数据库系统是一项长期而艰巨的任务，本文对其中的两个关 键部分进行了详细的分析和设计，并朝着前人很少涉及的两个方向相关数据 预读入缓冲区、b l o b 类型扩展和内容检索作了一些创造性的研究和探讨工 作，具有较好的借鉴意义。 关键字：空间数据库地理信息系统缓冲区b l o b 一重壅墅皇兰堕堡圭堡壅 a b s t r a c t i nr e c e n ty e a r s ，t h er e q u i r e m e n to fc o n s t r u c t i o no fs p a t i a ld a t a b a s e s y s t e mi n c r e a s e sc o n s t a n t l y m a n ys p a t i a ld a t a b a s es y s t e ma r eb a s e do n r d b m s tb u tn e i t h e rc a nt h e yw o r ke f f i c i e n t l yn o rc a nt h e ym e e tt h e r e q u i r e m e n t sc o r r e c t l y w en e e dt od e v e l o ps p e c i a ld a t a b a s es y s t e m sf o r w o r k i n go ns p a t i a ld a t aa n dm e e t i n gt h er e q u i r e m e n t so fg i s t h i sa r t i c l ed e s c r i b e dt h ef u n d a m e n t a ik n o w l e a g eo fs p a t i a ld a t a b a s e s y s t e m ，a n dg a v eas i m p l eb l u e p r i n to fi t t h e n i td i s c u s s e dt h ed e s i g n a n di m p l e m e n t a t i o no fb u f f e rm a n a g e m e n ta n db l o bs t o r a g ei nd e t a i l ，w h i c h i n c l u d e ss o m ea d v a n c e dr e s e a r c hr e s u l t t h i sa r t i c l em a i n l yf o c u s e do nt h ef o l l o w i n g2 p o i n t s t h ef i r s tp o i n ti sa b o u tt h ed e s i g na n dr e s e a r c ho fb u f f e rm a n a g e m e n t m o d u l e t h ea u t h o ra n a l y z e dt h eg e n e r a lt e c h n i c a ls o l u t i o no f i t ，t h e n d e s c r i b e di t si n s i d es t r u c t u r ea n df o u rm a i nc o m p o n e n t si nd e t a i l l a t e r ， al o to fa l g o r i t h m sa n di l l u s t r a t i o n sa r el i s t e d a tl a s t ，t h ea u t h o r b r o u g h tf o r w a r da “r e l a t e dd a t ap r e r e a di n t ob u f f e r t h e o r y ，a n d 口a v e am i n u t ed e d u c t i o nf o ri t i nt h es e c o n dp a r t ，t h ea u t h o rg a v eac o m p r e h e n s i v ed e s c r i p t i o no f t h e d e s i g ni d e a sa n di m p l e m e n t a lf u n c t i o n so fb l o bs t o r a g es y s t e m ，a n d e n d e dt h i sp o i n tw i t hh i ss o l u t i o n sf o re x t e n d e d b l o b t y p e s a n d i n s i d e b l o bq u e r y t h e r ei ss t i l lal o n gw a yt oa c h i e v et h eg o a lo f c o n s t r u c t i n g a c o n s u m m a t es p a t i a ld a t a b a s es y s t e m t h ea u t h o rd i s c u s s e dt h et w oo fm o s t c r i t i c a lc o m p o n e n t so fi t ，a n dd i dal o to fr e s e a r c ho nt h e m s h ea l s o f o c u s e do nt w oi s s u e st h a to t h e rr e s e a r c h e r si nt h i sf i e l ds e l d o mc a r e a b o u t - - t h e o r yo f “r e l a t e dd a t ap r e r e a di n t ob u ff e r ”a n d e x t e n d e db l o b t y p e sa n di n s i d 窟一b l o bq u e r y ”t h o s ec r e s t i o n a r yw o r ks h ed i dm a yh a v e u n c o u n t a b l er e s e a r c hv a l u ef o rr e s e a r c h e r so ft h i s f i e l d k e y w o r d s ：s p a t i a ld a t a b a s e ，g i s ，b u f f e r ，b l o b i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庆邮电 学院或其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：阵点良 签字日期： 2 0 0 _ 年月口日 学位论文版权使用授权书 本学位论文作者完全了解重庆邮电学院有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重庆邮电学院可以将学位论文的 全部或部分内容编人有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：陆玉良 签字日期： 2 0 0 ”e 月t o 日 导师签名：乡批 ， 签字日期：伽。牛年月p 日 重庆邮电学院硕士论文 1 1 论文的研究与选题背景 第一章绪论 数据库系统是管理数据的一种新技术，其主要目标是解决数据管理中数据 的获取、编码、组织、存储、访问和处理等问题。数据库技术是计算机科学技 术中发展最快的重要分支之一，它已经成为计算机信息系统和应用系统的重要 技术支柱，在短短的3 0 年左右，取得了迅速的发展。虽然目前市场上已经有 了一些比较成熟、通用的数据库系统产品，如o r a c l e ，d b 2 ，s y b a s e 等，但是， 对于一些特定的需求而言，仍然需要针对存储内容的特点，设计相关的专用数 据库系统。 随着计算机技术的飞速发展和计算机图形学理论的日趋完善，近年来，地 理信息系统( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ，g i s ) 作为- - 1 新兴的边缘 学科，无论是在理论上还是在应用中，都处在一个飞速发展的阶段。对空间数 据( 地理数据) 的处理是g i s 的核心功能，近年来，空间数据库的建设越来越 受到重视，基于空间数据基础设施的建设，开始了空间数据的共享和互操作的 研究。空间数据相对于传统数据丽言，具有许多新特点：数据源多元化，数据 存储容量大，数据之间的逻辑关系强，数据维护操作( 插入、删除、修改) 的 数据最大，并要求能提供灵活多样的信息查询、检索方式；此外，还需要内嵌 一些数据分析和计算的工具，不仅能够实现空间地理环境信息的快速获取和存 储，而且还要实现数据的快速转换和联机分析功能。 目前，绝大部分空间数据库都构建在目前流行的通用关系数据库基础之 上。例如，在o r a c l e 企业版中创建一个新的数据库实例时，如果选择了将来 用于空间数据的处理，o r a c l e 会根据空间数据的处理需要，专门对其做相关的 优化。但是，这些通用的数据库都是按照常用的事务处理需求来设计的，即使 针对空闻数据的特点进行了一些优化，但是无法得到性能上的全面提升。如果 能借鉴传统关系数据库的设计经验，并结合空间数据库的特点和处理需求，针 对数据库系统中的b u f f e r 、存储系统、查询处理引擎等关键部位进行优化的设 计，实现一套专用的空间数据库管理系统，在处理空间数据的时候莅陛能上会 有很大的提高。 我的论文空间数据库缓冲区和大对象存储的研究的选题和研究工作立 足于需求和技术的发展，以项目为依托，对数据库系统中的缓冲管理和大对象 管理进行了研究和开发的工作，并在常用的缓冲管理算法的基础上提出了自己 创新的算法。 重庆邮电学院硬士论文 1 2 本文主要研究内容和作者的主要工作 空间数据库系统牵涉的知识范围非棠广，它要涉及到传统数据库所要提供 的所有功能，并需要在此基础上进行改进和增强，其设计和开发都需要投入大 量的人力和物力，因而绝非单个人可以完成的。在研究生期闯，我的主要研究 方向是空间数据库系统中的缓冲区子系统( b u f f e rs u b s y s t e m ) 和大对象数据 ( b l o b ，b i n a r yl a r g eo b j e c t s ，大型二进制对象，如地图) 处理子系统的设 计，在本文中我将介绍我在这两方面所做的工作及研究结果。这两个子系统在 功能上相互独立，我将分别予以介绍。 本人的主要工作是对缓冲区管理模块、b l o b 管理模块进行总体结构的设 计，函数的定义以及相关编码工作，并对部分算法提出了改进。 1 3 论文的章节安排 第一章绪论，引出了本文的研究背景，并简述了论文的章节安排； 第二章相关理论知识介绍，简要介绍了数据库缓冲区及缓冲管理技术、 b l o b 及其处理技术； 第三章空间数据库系统总体设计，介绍了空间数据库存储管理系统的总体 结构的组成以及内部各个模块的功能； 第四章缓冲管理模块的研究与实现，介绍了该模块的总体设计、数据结构 和部分功能实现，并对“相关数据预读入缓冲区方案”进行了详细而且富有创 造性的研究； 第五章b l o b 数据存储和处理的研究与实现，介绍了b l o b 管理模块的总体 设计，数据结构及功能实现，以及b l o b 类型扩充和内容查询的研究； 第六章给出了本文的结论； 最后是致谢和参考文献。 2 重庆邮电学院硕士论文 第二章相关理论知识介绍 2 1 缓冲区及缓冲管理技术简介 在数据库管理系统( 以下简称d b m s ) 中，数据最终都存储在磁盘上，要对 数据进行处理，必须先将其读入到内存，才能处理。数据库系统的一个主要目 标是减少磁盘和存储器之间传输的块的数目。为达到这个目标，我们可以使用 缓冲区，把系统中经常被使用的磁盘上的数据维持在内存的缓冲中，以减少系 统对磁盘的平均i o 访问。缓冲管理模块在整个系统中位于磁盘管理模块和文 件管理模块之间，负责管理缓冲区的一切操作。当需要从磁盘上往内存中读取 任意数据页时，可以先根据该页的关键字( p a g ei d ) 在缓冲区中查找，若该 页在缓冲区中，就直接在缓冲区中读取，否则，把该数据块从磁盘调人缓冲区 中再进行读取。内存不必直接和磁盘交互数据，两者通过缓冲区进行数据交互， 只有当要读取的内容不在缓冲区中的时候，才需要访问磁盘。因此，只要设计 适当的缓冲区替换算法，尽量提高内存访问缓冲区时的命中率，就可以减少磁 盘i o 的访问次数，从而提高挨个系统的性能。缓冲管理模块与磁盘管理模块 的上下层关系如下页图i - i 所示： 圈 降写一f 小 i 山 、l ， 鼹冲区管理器i | b u 仟e rm a n g e 叶。一7 ( 幻 图1 1 缓冲区的工作原理模型 对于传统数据库系统，数据库缓冲区管理器中包括以下几个部分：一个空 3 重庆邮电学院硬士论文 闲缓冲区块标识表( f r e eb u f f e rb l o c kt a b l e ) ，标记缓冲池( b u f f e rp 0 0 1 ) 中所有的空闲缓冲区块；一个“脏”数据块标识表( d i r t yb u f f e rb l o c kt a b l e ) ， 标记所有被修改了还没有被写到磁盘上去的缓冲区块；还有一个分区 ( p a r t i t i o nt a b l e ) 和一个散列表( h a s ht a b l e ) ，它们是为处理和协调多个 事务并发访问而设置的。 对于太多数简单的数据库系统，缓冲区一般是一块连续的内存区域，这样 读取和检索起来也会更加方便。 在缓冲管理中，页替换算法采用l r u ( l e a s tr e c e n t l yu s e d ) 方式，其意思 是在多个b u f f e rp a g e 中选择淘汰历史最长( 很久以前被修改的) 的p a g e 。 缓冲管理模块管理的对象包括：b u f f e rp o o l 中所有的f r e eb u f f e r b l o c k ，所有被修改了还没有被写到磁盘上去的d i r t yb u f f e rb l o c k ，还有为 增加多个事物同时访问的并发性所设置的p a r t i t i o nt a b l e ( 分区) 和h a s h t a b l e ( 散列表) o 它们的结构将在下面详细介绍。 和b u f f e r 模块相关的所有动作都遵循w a l ( w r i t e a h e a dl o g g i n g ) 算法， 该w a l 方式和恢复相关。w a l 的意思是对b u f f e rp a g e 的变更在写到物理磁盘 上之前，都要先把该p a g e 的变更和相关事务日志写入到物理磁盘上。 对于b u f f e r 管理考虑事项有：( 1 ) b u f f e r 大小由系统根据使用的频繁程 度和实际同时并发用户大小进行自动调节，即在系统运行过程中可以自动增加 或者减少b u f f e rp o o l 中b u f f e r 的数量；( 2 ) 对b u f f e r 的访问都需要通过相 应的并行处理任务来进行。 如果采用这种缓冲区结构，对于空间数据来说，由于数据量比较大，很可 能一次需要读取大量数据，其容量足以刷新整个缓冲区。但如果把缓冲区做得 很大的话，则又会占用宝贵的存储空间和增加寻址的时间，而且大多数时候缓 冲区中的内容都会被闲置而不被访问，这样系统效率的提高无法挽回空间上的 损失。因此，在设计空间数据库系统时，要针对空间数据的存取特点对缓冲区 的实现方式进行改进，以提高其处理效率，进而提高整个系统的效率。 2 2b l o b 的存储、检索和维护方式简介 2 2 1b l o b 数据的存储与检索 随着多媒体技术的发展和数据库系统在各行各业的普及，数据库系统除了 需要存储文本、数字和日期等简单类型的数据外还要存储声音、图像、w o r d 4 重庆邮电学院硕士论文 文档等复杂的对象数据。这些数据都是以二进制方式( 即使是纯文本的内容， 最终还是属于二进制形式) 来存储和处理，通常被简称为b l o b ( b i n a r yl a r g e o b j e c t s ，大型二进制对象) 数据。由于其数据量非常大，变化性强无法预测， 为了不浪费磁盘空问和处理效率，需要对他们做特殊的处理。最简单的方式就 是把它们存放在附加的数据文件中，然后在基本表里面存放一个指针，指向它 位于附加数据文件中的起始位置位于文件中的偏移量。同时，在附加数据文件 中相应位置的开头，写入一个固定宽度( 如3 2 b i t 的长整型) 的指针，指向基 本表中相应记录的位置，或直接在该位置写入基本表中相应记录的记录号，只 要能够根据这些数据就从基本表中找到对应的记录即可。 下图1 - 2 描述了重庆邮电学院软件学院在读研究生基本档案的保存方式， 其中的简历和照片为两个b l o b 字段： 基本表 编号姓名性别简历照片 1 舒息玲 m0 x 0 0 0 0 0 0 0 00 0 0 0 0 1 7 5 6 2 唐隆宏 m o x 。o 即爹眵0 x 0 0 0 q 7 8 b c 夕气- 夕形7 弋j 舒赢玲的鸢麟的 庸l 蔓寡的庶隆寡的 简历数据照片数据简历数据 照片数据 o x 4 2 5 o x t 8 虬o 蚂9 8 c 趣大文本和图像内容 图i - 2 数据库中b l o b 字段存储的示意图 在物理上，b l o b 数据必须存储在磁盘上的一个或多个柱面中连续的一些数 据块中，也有可能存储在链表结构的数据块中。如果要对b l o b 进行很快的检 索，有必要将b l o b 中的各个对象进行分割，将其内容分别存储在几个不同的 磁盘上，即在这些磁盘上交替存储b l o b 的块。这样就可以同时对b l o b 的几个 块进行检索，由于是并行处理，检索效率会大大提高。 5 重庆邮电学院硕士论文 2 2 2b l o b 记录的维护 在向数据库操作含b l o b 的记录时，要比对普通数据表的操作复杂。首先， 除了要有普通的事务处理日志外，还要增加一个记录未提交的b l o b 事务处理 的h 志。插入新记录时，先将b l o b 数据写入到附加文件中问( 当以前清除过 数据并留下空位置时) 或附加到其尾部，然后再将其指针和其他基本类型的数 据一起插入到基本表中，并将插入的位置记录到事务处理日志中。删除记录时， 对基本表和附加文件中要删除的记录作上删除标记，而不是从物理上作真正地 删除，并都记录到事务处理日志中。更新记录时，对基本表和附加文件中要更 新的记录做上标记，然后将用来替换的内容记录到事务处理日志中。在c o m m i t 的时候，将根据保存在事务处理日志中的具体操作来保存事务的结果：对于插 入操作，直接保存插入结果；对于删除操作，就需要同时删除基本表和附加内 容中保存的b l o b 数据；对于修改操作，先要删除附加文件中的内容，然后再 重新写入替换的内容并根据具体需要决定是否要修改基本表中的指针。每 c o m m i t 完一项操作，都要删除事务处理日志中的相应记录。如果要r o l l b a c k ， 对于插入操作，则清除插入位置的记录；对于删除和修改操作，则只需要从事 务处理日志中清除相关的记录即可。 如果要清空整个表中的内容( 相当于o r a c l e 中的t r u n c a t e 操作) ，则无 须写人事务处理日志，直接将基本表和附加文件中的所有记录全部清空，同时 清除事务处理日志中与该表相关的记录。 2 3 本章小结 本章简要介绍了数据库缓冲区及缓冲管理技术、b l o b 及其处理技术，结合 了b u f f e r 管理和b l o b 技术在传统数据库系统中的实现，论述了它们在空间数 据库系统中实现所面临的问题。这一章是本文的理论基础和研究内容的引子。 6 重庆邮电学院硕士论文 第三章空间数据库系统的总体设计 3 1 空间数据库存储管理系统的总体结构和模块 3 1 1 空间数据库存储管理系统总体结构介绍 空间数据库存储管理系统由d i s km a n a g e r 、b u f f e rm a n a g e r 、f i l e m a n a g e r 、b l o bm a n a g e r 、i n d e xm a n a g e r 、c u r s o rm a n a g e r ，l o c km a n a g e r 、 t r a n s a c t i o nm a n a g e r 、r e c o v e r ym a n a g e r 等模块组成。 图3 1 空间数据库存储管理系统体系结构图 7 t r a n s a c t i o n t r a n s a c ti o n m a n a g e r l ock m a n a g e r 重庆邮电学院硕士论文 3 1 2 空间数据库系统模块介绍 各模块的介绍如下： d i s km a n a g e r ：是空间数据库存储管理系统最基本的模块，管理物理上的 存储空间d i s k 。负责磁盘文件分区的管理，担负b u f f e r 和磁盘之间的读 写任务； b u f f e rm a n a g e r ：负责全局变量中的b u f f e r 管理，在b u f f e r 中维持经常 使用的p a g e ，使磁盘输入输出( 读写) 最小化； f i l em a n a g e r ：负责顺序文件的管理，文件内r e c o r d 的管理； b l o bm a n a g e r ：负责b l o b 空间和b l o b 空间内的b l o b 数据管理，为空间 数据管理和多媒体数据管理提供支持； i n d e xm a n a g e r ：为经常使用的数据提供快捷访问方式，提供传统的 b - t r e e ，提供对空间数据快速访问的r - t r e e 或其变种； c u r s o rm a n a g e r ：为用户提供便利的记录级顺序文件检索机制； l o c km a n a g e r ：提供共享数据的顺序化访问和各个t r a n s a c ti o n 间独立的 数据访问； t r a n s a c t i o nm a n a q e r ：为用户提供事务管理功能，分布在f i l e 、c u r s o r 、 i n d e x 等模块； r e c o v e r ym a n a g e r ：提供系统安全故障时恢复故障的功能。 3 2 空间数据库存储管理系统的应用 空间地理技术在我们的生活中扮演着越来越重要的角色，有越来越多的应 用需要地理信息系统的支持。随着以计算机为基础的空间地理信息的潜力不断 扩大，大量的人力与物力投入到空间地理技术的研究中，这也促使人们创建基 于地理数据存储的数据库管理系统。现在的关系数据库已经具备越来越强的空 间能力，例如能够组织和存储地理特性、提供r - 树状索弓 和数据刀片技术等， 从而确保许多任务关键型应用的运行能够更快、更安全且更易于实施。未来 的数据库管理系统应能有效地管理这些空间数据，从而导致空间数据库存储管 理系统的开发。空间数据库存储管理系统可以用于g i s 方面，对空间数据进行 存储和处理。不管是在传统的商业领域还是尖端的技术领域方面，空间数据库 8 重庆邮电学院硬士论文 存储管理系统都能发挥其威力。 同时，随着当今社会的信息化，计算机需要管理庞大复杂的多媒体 ( m u l t i m e d i a ) 数据( 包括数值、文本( t e x t ) 、图形( g r a p h i c s ) 、图像( i m a g e ) 、 声音( s o u n d ) 、视像( v i d e o ) 以及其它计算机所能处理的信息等等) ，这些多数 为海量数据。现代计算机应用领域对数据库管理系统所提出新的要求，要求未 来的数据库管理系统应能有效地管理这些大数据( 在数据库里，这些数据可以 用b l o b 形式来存储) 。空间数据库存储管理系统可以用于存储多种二进制大对 象，使用于互联网广播、网络视频、音频等方面。 3 3 本章小结 本章简要介绍了空间数据库存储管理系统的总体结构的组成以及内部各 个模块的功能，并介绍了该系统在现实生活中的应用( g i s 方面和多媒体数据方 面) 。 9 重庆邮电学院硕士论文 第四章缓冲管理器的研究与实现 4 1 缓冲管理模块的总体设计 缓冲管理模块位于磁盘管理模块和文件管理模块之间，负责管理b u f f e r 。 当需要从磁盘上往内存中读取任意p a g e 时，可以先根据该p a g e 的p a g e i d 在 缓冲区中查找，若p a g e 在b u f f e r 中则直接在b u f f e r 中读取，否则，把该p a g e 从磁盘调入缓冲区中再进行渎取。内存不必直接和磁盘交互数据，两者通过缓 冲区进行数据交互，进而可以减少d i s ki o 。其结构如下页图4 - i 所示。 b u f f e rm a n a g e r 模块内部有四个t a b l e ，分别是b u f f e rt a b l e 、h a s ht a b l e 、 p a r t i t i o nt a b l e 、b u f f e rd i r t yt a b l e 。各个表的详细结构请参考接下来的 第4 2 节中的说明。 4 2 缓冲管理模块的内部结构 4 2 1b u f f e rt a b l e 的设计思想 b u f f e rt a b l e 由包含d i s kd a t a 的b u f f e rp a g e 和描述b u f f e rp a g e 状态 的b u f f e rh e a d e r 两部分构成。当d b m s 初始化时，缓冲区的数目m a x b u f f e r s 是一个设置的参数，存放在系统p r o f i l e 中。d i s k 和b u f f e rt a b l ep o o l 之间 以p a g e 为单位进行数据交换。 b u f f e rh e a d e r 部分主要包含下列字段：p r e y 指针、n e x t 指针、p a g e 指 针。通过b u f f e rt a b l e 的p r e v 和n e x t 指针把各个b u f f e rt a b l e 连成一个l r u 链表，每个b u f f e rt a b l e 都有一个指向对象b u f f e rp a g e 的p a g e 指针。b u f f e r t a b l e 中包含的字段还有：s t a t u s ( 状态) ，m o d e ( 访l 可方式) ，d i r t y ( “脏”标 志位) p a g e i d ( p a g ei d 字段) 。其中状态字段有三种取值：b u f e m p t y ( 该 b u f f e r 从来没有用过) ；b u f _ f r e e ( b u f f e r 目前空闲) ；b u fb u s y ( b u f f e r 在 被使用中) 。访问模式有读写方式。当一块b u f f e r 的内容被修改后还没有被 写回磁盘，该b u f f e r 被打上d i r t y ( “脏”】标志。b u f f e rt a b l e 的结构为： 1 0 塞压墅皇堂堕堡主笙壅 t 弓矾 图4 1 缓冲管理模块的总体结构图 1 1 一茎墨墅墨兰堕堡主笙茎 t y p e d e fs t r u c t ( t _ s l a t c h s e m ；| s e m a p h o r eo ft h i sb u f f e r + i n t 4 s t a t u s ： + s t a t u so ft h i se n t r y + i n t 4 m o d e ；卜a c c e s sm o d e i n t 4 d i r t y l | d i r t yf l a g | i n t 4r e f c n t ：| r e f e r e n c ec o u n tt | i n t 4s h a r e d c n t ；r e a dm o d e c o u n t + t _ p i dp a g e l d ； + p a g ei do ft h eb u f f e r + l c h a r p a g e ；pb u f f e rc o n t e n tp o i n t e r + f i n t 4 n e x t ；+ l r un e x tc h a i n + ， i n t 4 p r e y ； l r up r e v i o u sc h a i n # if d e fd e b u g _ b u f c h a r f i l e n a m e m a x n a m e l e n g t h 1 f o rd e b u go u t p u t i n t 4 l i n e n u m ； # e n d i f ) tb u f t a b ； 4 2 2p a r t i t i o nt a b l e 的设计思想 分区表是为了提高多个事务同时访问缓冲池的性能而设立的。一共有 b u f n u m p a r t s 个分区表，所有的b u f f e r s ( 数目为m a x b u f f e r s ) 都被分配到这 b u f n u m p a r t $ 个分区表中，每个p a r t i o n 中，m a x b u f f e r s ，b u f n u m p a r t s 个 b u f f e r s 通过l r u 链接起来。p a r t i t i o nt a b l e 中主要有4 个指针字段：指向 l r u 链头部和尾部的l r u t o p 和l r u b o t t o m 指针，指向h a s ht a b l e 开始处和空 闲处的h a s h t a b s t a r t 和h a s h t a b f r e e 指针，此外还有两个整数字段：n u m b u f ( 分区中所有缓冲区的数目) 、n u m f r e e b u f ( 分区中空闲缓冲区的数目) 。 每个b u f f e r 所属于的p a r t i o n 可以通过p a g e i d 和h a s h 函数确定下来。 l r u 链接由b u f f e rh e a d e r 中的的n e x t ，p r e v 域，和p a r t i t i o nt a b l e 中的 l r u t o p ，l r u b o t t o m 域来构成并维持。分配b u f f e r 时在c h i a n 的末尾 ( l r u b o t t o m ) 分配，b u f f e r 返还时，在c h a i n 的开始处( l r u t o po h a s h t a b s t a r t 和h a s h t a b l e f r e e 域中存放b u ff e rh a s ht a b l e 中可以使用 的基本b u c k e t 和o v e r f l o wb u c k e t 的i n d e x 数目。 p a r t i t i o nt a b l e 的结构如下： t y p e d e f s t r u c t ( t _ s e m asem；|+semaphore o ft h i sp a r t i t i o n + 1 2 曼堡坚皇堂睦堡主堡苎 i n t 4 i n t 4 工n t 4 i n t 4 i n t 4 n u m b u f ； + # o fb u f f e r si nt h i sp a r t i o t i o n + n l u m f r e e b u f ：+ # o ff r e eb u f f e r si nt h ep a r t i t i o n h a s h t a b s t a r t ：+ s t a r ti n d e xo fh a s ht a b l e + h a s h t a b f r e e ；+ f r e el i s ti nh a s ht a b l e + l r u t o p ； + l r uf r e eb u f f e r c h a i n t o p t b u f t a b + i n t 4 l r u b o t t o m ； l r uf r e eb u f f e rc h a i n b o t t o m tb u f t a b + 】t b u f p a r t ； 4 2 3h a s ht a b l e 的设计思想 这个表是为了快速访问b u f f e r 而设立的。每个p a r t i t i o n 维持一个 b u f f e rh a s ht a b l e ，b u f f e rh a s ht a b l ee n t r y 的数目是每个p a r t i t i o n 所拥 有b u f f e r 数目( n u m b u f ) 的两倍。 在每个p a r t i t i o n 内，根据h a s h 函数和p a g e i d 来确定b u f f e r 。h a s h 函 数的输入参数是p a g ei d ，在两个p a g ei d 的h a s h 值一样的情况下，也就是发 生冲突时( 基本p a c k e t 已经被使用的情况下) ，剩余的放在o v e r f l o wp a c k e t 中，h a s h 值通过p a g ei d 和b u f f e rp a r t i o nt a b l e 的i n d e x 数目来确定，使 用的公式如下： h a s h 值= p a r t i t i o n sh a s h t a b s t a r t + ( p a g e i d p a r t i t i o n 内的b u f f e r 数目) h a s ht a b l e 中有两个指针，指向相应b u f f e rt a b l e 的b u f i d x 指针和指向 碰撞同义词所在表项的n e x t 指针。在h a s ht a b l e 中，主要是要解决碰撞问题。 ( 两个不同p a g e i d 的h a s h 值相等，即h ( p a g e i d1 ) = h ( p a g e i d2 ) ，这个 现象叫做碰撞。) h a s ht a b l e 的结构如下 t y p e d e f s t r u c t ( i n t 4b u f l d x ； i n t 4 n e x t ； ) t _ b u f h a s h ； + p o i n t e rt ob u f f e rt a b l e + n e x tc h a i np o i n t e r + | 1 3 重庆邮电学院硕士论文 4 2 4b u f f e rd i r t yt a b l e 的设计思想 该t a b l e 维护d b m s 系统中处于修改模式状态的所有b u f f e r ，该t a b l e 的 内容包含在c h e c k p o i n tl o g 中，作为c h e c k p o i n tl o g 的一部分，在系统发生 各种错误时，由恢复模块使用。 b u f f e rd i r t yt a b l e 中有两个字段，分别是b u f f e r 中的d i s kp a g ei d 和 b u f f e r 的日志序列号。 b u f f e rd i r t y t a b l ee n t i t y 的数量和b u f f e r 的数量一致，对所有的b u f f e r 进行管理，丽不区分p a r t i o n 。任何b u f f e r 都有被更改的可能性。 b u f f e rd i r t yt a b l e 的详细结构如下： t y p e d e fs t r u c t tp i dp a g e l d ；| d i s kp a g ei d i nt h eb u f f e r | tl s nr e c l s n ；，f i x e dt i m el s no ft h eb u f f e r 1tb u f d i r t y t a b ； 4 3 缓冲管理模块的功能实现 4 3 1 缓冲管理模块在内存中的数据结构 为了更清楚地说明缓冲管理模块的总体结构，给出一个模块的总体初始化 结构图，如下：( 注：图中各表字段为主要字段而不是所有字段) 1 4 重庆邮电学院硬士论文 h 嬲b 艋e b u f f e r i h b l e 图4 - 2 模块的总体初始化结构图 初始化分为下面几步： 1 、从p r o f i l e 中获取m a x b u f f e r s ( 最大b u f f e r 数量) 。 2 、为缓冲区表( b u f t a b ) 分配空间并进行初始化。对每一个b u f t a b ， 有： b u f t a b ( i ) s t a t u s = b f _ e m p t y ；把每块b u f f e r 状态设置为b f _ e m p t y b u f t a b ( i ) p a g e = c h a r * ) m a l l o c ( d s k p a g e s i z e ) ；把每块b u f f e r 的p a g e 指针指向该p a g e 所 在的磁盘上的位置 3 、为散列表( b u f h a s h ) 分配空间并进行初始化，散歹i j 表中的元素个 1 5 重庆邮电学院硬士论文 数是所有b u f t a b 的两倍。对于散列表中的每个元素，有 b u f h a s h ( i ) b u f l d x = n i l ；把b u f l d x 指针设为n i l ( 空值) b u f h a s h i i ) n e x t = n i l ；把n e x t 指针设为n i l ( 空值) 4 、为分区表( b u f p a r t s ) 分配空间并进行初始化。步骤如下： 4 1 分配分区表的空间 4 2 设置分区内的缓冲区个数 4 3 在分区内建立o v e r f l o wh a s ht a b l e 的链表，设置好分区表的 h a s h t a b s t a r t 、h a s h t a b f r e e 字段；并填充好b u f h a s h 的n e x t 字段。 4 4 在分区内建立b u f t a b 的l r u 链表，同时设置好分区表的l r u t o p 、 l r u b o t t o m 字段；并填充b u f t a b 的p r e v 、n e x t 字段。 5 、为脏缓冲区表( b u f d i r t y t a b ) 分配空间并初始化。b u f d i r t y t a b 的元素个数和所有缓冲区个数相等。对表中的每个元素，有： b u f d i r t y ( i ) p a g e i d = m a x _ n a t 8 ； b