内存数据库的实现.docx

《内存数据库的实现.docx》由会员分享，可在线阅读，更多相关《内存数据库的实现.docx（8页珍藏版）》请在三一办公上搜索。

1、内存数据库的实现一、内存数据库的概念：传统的磁盘数据库DRDB,其主要的工作版本保存在非易失性的存储设备磁盘上，因此DRDB系统在 进行数据操作和管理时，经常需要对磁盘进行访问，将数据从磁盘读到内存，然后在内存上对数据进 行处理，处理完后再将内存中的数据写回磁盘。由于磁盘数据库的诸多操作都涉及磁盘的I/O,而磁 盘由于机械设备的特性，磁盘的I/O操作速度较慢，且随机和连续的I/O顺序也对其速度影响很大。 因此磁盘数据库的I/O是其性能的瓶颈所在。磁盘数据库系统的算法设计也是针对提高I/O效率来进 行设计的。然而经过几十年的发展，磁盘数据库的算法几经改进，然而始终绕不过磁盘I/O这道坎， 磁盘I

2、/O成为阻碍磁盘数据库性能提高的关键。减少甚至不使用I/O操作成为数据库系统性能改进的 研究方向，于是使用大内存的策略内存数据库（MMDB）成为了研究的热点。数据库系统中使用大内存，经历过两种主要途径。一是在内存中创建很大的缓冲池，使得数据库将磁 盘数据库的一部分内存放在内存缓冲池中，使近期正在进行操作的事务所需数据的大部分甚至全部都 保存在内存缓冲池中，以减少磁盘的I/O,这种方法还是未能跳出传统磁盘数据库的框架，只是增大 了传统的磁盘数据库缓冲区大小而己，数据库的“主版本”或“工作版本”仍然保存在磁盘上。另一 种主要途径是让数据库常驻内存，数据库的“主版本”或“工作版本”常驻内存，而磁盘版

3、只做后备， 针对数据库的所有事物操作都在内存上进行。内存数据库的这个特性，使得传统磁盘数据库的算法设 计对内存数据库已经不在适用，关于内存数据库的查询处理、并发控制和恢复等的算法与数据结构都 必须重设计与重构造，设计的原则以CPU和内存的高效使用为目标。关于内存数据库的具体定义， 典型的有下面几种不同的观点：1, 整个数据库全部常驻内存，存取数据时没有必要I/O操作，这就要求内存足够大，以容纳数据库 的所有数据。2, 内存不必足够大到容纳整个数据库，但数据被存取时，先进入内存，数据库的存取在内存进行。3, 数据库常驻磁盘，在事务执行前将所需要的数据集调入内存，提交时所有对数据库的修改必须写回

4、磁盘。4, 数据库常驻磁盘，但内存有很大的缓冲区或高速缓存，因而使数据库的大部分乃至全部可在内存， 通过适当的缓冲区的处理以减少内外存I/O操作。二、内存数据库的特点：内存系统和磁盘系统具有不同的特性，这是引起内存数据库和磁盘数据库之间差别的根本所在。主要 表现在以下几方面：1, 内存和磁盘在存取时间上有数量级的差别。内存数据可以和CPU直接打交道；而磁盘数据库有个IO 过程，先读入内存再被CPU处理，因此内存数据库在存取时间上远低于磁盘数据库。简单说，就是 内存数据库更快，效率高。2, 内存的易失性决定了内存数据库也是易失的，它的存在是为了更好的效率和并发性。它是磁盘数据 库在内存中的一个临

5、时版本，所有更改最终只有反映到磁盘中才能被永久储存。断电后，内存数据库 的数据会完全消失。3, 数据的储存组织方法对性能的影响不同。不同的组织方式对磁盘数据库的性能影响远大于内存数据 库。比如顺序存取与随机存取的时间对内存没有什么变化，而对磁盘则几乎有数量级的差别。4, 存取方式不同。内存可由CPU直接存取，磁盘则不能，但内存比磁盘更易受到来自程序错误的直接 数据破坏。三、实时内存数据库的数据装入策略：从某种角度看，内存数据库是一种Cache机制，是磁盘数据库的Cacha，通过对内存中的数据直接操 作，减少了到磁盘间的IO交互。实际操作时，往往因为内存容量的限制，无法将磁盘数据库所有的 数据都

6、读入内存，所以在初始化数据装入时必须要有一定的规则来保证装入的数据必须是最重要的。在内存没有足够大以容纳全部外存数据库的条件下，首先给出如下的内存数据库定义：设有数据库系统DBS，DB为DBS中的数据库，DBM(t)为在时刻t DB在内存的数据集，DBM(t)属于 DB。TS为DBS中所有可能的事务的集合，AT(t)为在时刻t处于活动状态的事务集，AT(t)属于TS。 Dt(T)为事务T在时刻t所操作的数据集，Dt(T)属于DB。若在任一时刻t，均有：V TAT(t)，Dt(T) 属于DBM(t)成立，则称DBS为一个内存数据库系统，简写为MMDBS； DB为一个内存数据库，简 写为MMDB。

7、除了内存不必足够的大就可以容纳全部的外存数据库外，ERTDBMS的架构在整体上和国际上传统的 内存数据库是相似的。为了提高交换的效率，内存和外存被划分成固定的大小，并且内存的段的大小 等于外存的块。为了更好地满足实时事务的定时限制，实时数据库把可以预定义的实时事务和对系统影响比较夫的非 实时事务进行静态的预分析，进行知识提取，为数据装入提供下列必需的信息：(1) 事务类型：硬实时事务，软实时事务，非实时事务。(2) 事务的开始时间，包括绝对开始时间和相对开始时间。(3) 事务的截止期，包括静态截止期和相对截止期。(4) 事务的存取过程集，也就是事务对数据的约束条件。如果约束条件中包含动态执行时

8、才能获得的信 息，则静态预分析不提取对应的约束条件。所以按照静态预分析的存取过程集取得的数据要大于等于 事务实际需要的数据。(5) 数据的有效期，是指数据库中的数据反应的外部环境与真实的现实世界是否一致。当事务存取了超 过数据有效期的数据，就不能保证事务的正确性。(6) “超存取过程集”，由于实时数据库宁可要不完整但及时的数据，不要完整但过时的数据，因此如 果一个静态预分析的实时事务被接纳的时候，其数据集不在内存。启动的是由其“超存取过程集”组 成的“超事务”，可以使原事务在有一部分数据集进入内存后就可以启动。(7) 事务数据装入时间的静态估计。通过判断一个事务所存取的全部关系在外存有多少块的

9、记录和系统 1，0 一次所花费的时间，静态估计装入一个事务的数据需要多长时间。事务的数据还是个未知数，事务类型、开始时问、结束时问等标准的相互冲突，都给事务的选择带来 了难度。在静态预分析的基础上，我们把全部分析好的事务排成一个队列。内存数据库初始化的时候 从队列的第一个事务开始装入，无论内存有多大，装入的数据都是最应该装入的数据。队列的形成策 略如下：(1) 队列的开始是随机发生的硬实时事务。由于硬实时事务如果超过了截止期会给系统带来毁灭性 的后果，因此随机发生的硬实时事务的数据应该最先被调入内存。(2) 其次是周期事务的数据。由于实时数据库的周期事务频繁地执行，如果不能保证数据在内存， 就

10、会发生“抖动”，严重影响系统的效率，因此周期事务的数据也应该被调入内存。(3) 然后是内存数据库初始化时就应该把数据调入内存，否则会超过截止期的硬实时事务。设一个 硬实时事务的开始时间Ts与当前Tn的差为N，事务数据装入时间的最坏静态估计为M(最坏情况下 所有涉及到的关系的外存块数和读取一块的平均时间)，如果NX*M，则此事务的数据现在町以不在 内存X是一个很夫II数，用来保证N远远人1 M( l rMMDB巾X的初始值为10)如果N和M不满 足此条件则该硬实时事务的数在内存数据库初始化的时候就应该装入内存(4) 如果在装入以上3事务的数据的过程中，内存耗尽，则内存数据库初始化失败(5) 接下

11、来同(3)，判断内存数据库初始化时就应该装入的软实时事务。(6) 然后装入随机发生的软实时事务的数据。(7) 如果在以上两类事务的装入过程中，内存耗尽，则内存数据库虽然初始化成功，但是性能堪忧。(8) 接下来为所有内存数据库初始化时，数据不在内存的实时事务设置定时器，在开始时间Ts前 Y*M的时间Ti启动该事务的数据装入事务，Y是一个比较大的正数，以保证该事务的数据可以换入(在 ERTMMDB中Y的初始化值为3)。把设置了定时器的实时事务按照Ti和非实时事务的开始时间按照时间顺序排列，随机发生的非实时事务排在最后。如果事务的开始时间相同，则截止期和数据有效期 最早的最优先如果在装入此类事务的过

12、程中，内存耗尽或者内存足够大把全部队列的事务都装入完 毕，都宣布内存数据库初始化成功完成。以上的装入顺序保证了无论内存有多大，装入的数据从事务类型、事务的开始时间和截止期，以及数 据的有效期来看都是最应该装入的数据。而且也给后来的数据换出及如何方便地换出最应该换的数据 打下了基础。四、内存数据库的关键技术：1.数据组织结构：目前较通用的数据组织结构有基于关系表的区段式的组织结构和基于对象的组织结构。 区段式数据组织结构目前绝大多数数据库都是数据基于关系表的关系数据库，在关系数据库中往往使用二维的关系表来保 存数据。二维表在磁盘数据库中已被广泛使用，使用二维表保存数据主要是维护两方面信息，即描述

13、 信息和记录信息。所谓描述信息即指表名，个字段名及类型信息，索引，主键等用于描述关系表的信 息；而记录信息则是保存在关系表中的每一条记录的数据内容。在关系数据库往往使用区段式的数据 组织结构，区段式数据组织结构，将共享内存划分为若干个“分区”，每个分区存储关系数据库的一个 关系。每个分区又是由若干固定长度的“段”（也称作“页”）组成，一个段往往是共享内存动态分配 的一个单位。而数据库具体的数据记录则保存在段中分配的一个记录块中。区段式数据组织结构的示 意图如图所示：由上述可知，在采用区段式的数据组织结构的数据库中，一个记录的地址信息由一个三元组 标志，其中P是分区号，一般对应于一个关系表名，S

14、是段号，标志组成这个分区的具体的段，L是 段内记录槽号，主要保存了记录在段内的偏移和长度，用来在段内进行寻址。从而通过这个三元组可 以唯一的定位一个记录的具体位置。当前基于关系表的内存数据库一般都采用区段式的数据组织方式, 较典型的代表有SQLite。 基于对象的数据组织结构除了区段式的数据组织形式外，随着面向对象技术在内存数据库的应用和对象数据库的兴起很多数据 库采用了基于对象的组织结构。当采用基于对象的数据组织结构时，数据库的记录，记录的索引都用 对象来实现，以对象为单位进行内存的分配，记录对象之间和索引对象之间的联系由对象自身来维持。 基于对象的数据组织结构示意图如图所示：Object

15、-Tji bits ParlAbk。硕IjibLe ObjecETjible Objecl:F-Retard Ptr-Lmlei Pti/Beroid Objec tRecord ObjectTIM 1Fm 2HM iiTim 点;impPrePn-Truki Objec-c-JLitdeiN ode Pcilb由图可知在使用基于对象的数据组织结构时往往使用指针来维持对象之间的联系，较典型的基于对象 的内存数据库如fastDB则采用了这种数据组织方式。2.索引的结构：内存数据库由于其工作的主版本保存在内存中，所以内存数据库的索引选择应结合存储介质的特点， 从而通过索引的建立来保证内存数据库查寻

16、操作的高效性。索引用于在查询时提高效率之用。可以为 每张表的某个字段定义索引来提高在该字段上的查询效率。由于数据库要处理的数据量非常大，而内 存因为价格昂贵，而容量有限，且必须满足一定的实时性，因而对其中的数据的存储及索引方式进行 研究，找出有效的数据组织方式是非常有必要的。磁盘数据库系统的典型的索引技术是B-tree索引。 B-tree结构的主要目的是减少完成数据文件的索引查找所需要的磁盘I/O的数量。B-tree通过控制节 点内部的索引值达到这个目的，在节点中包含尽可能多的索引条目（增加一次磁盘I/O可以访问的索 引条目）。目前在内存数据库中经常选用的索引结构有hash索引和T树索引。Ha

17、sh索引hash索引定义了一个hash函数，通过将关系表的索引项传入到hash函数可以计算出相应的hash值， 从而在索引项和hash值之间建立起对应关系。同时用于保存不同的hash值的索引信息首地址往往是 线性结构，从而可以迅速的找到每个hash值的首地址，使得通过hash索引查找数据只需常数时间的 复杂度。hash索引的示意图如图所示：由图可知，往往索引项不同的具体数据使用hash往往会得到相同的hash值，所以一般为每个hash值 建立一个动态的冲突链表来保存同一 hash值的记录索引信息。当为一条记录建立索引时只需通过对 索引项使用hash函数的到其hash值，通过计算得到的hash值

18、迅速找到保存此hash值冲突链的首地 址，并将这条记录的地址信息插入到冲突链表中。当需要通过这个索引项的一个特定值对记录查找时， 只需对这个索引项的给定的值运用hash函数求的hash值，找到该hash值冲突链的首地址，顺序遍 历冲突链以找到待查找的记录的地址信息。hash索引的查找和维护非常简单，但是hash函数的选择 往往非常困难，hash函数的hash值过小，往往使得冲突链过长，以致遍历过长的冲突链降低效率； hash函数产生的hash值不均匀则会使得不同冲突链长度差距悬殊；hash函数的产生的hash值过多 则会造成内存空间的浪费。T树索引T-tree是针对主存访问优化的索引技术。T-

19、tree是一种一个节点中包含多个索引条目的平衡二叉树， T-tre的索引项无论是从大小还是算法上都比B-treel简得多T-tre的搜索算法不分搜索的值在当前 的节点还是在内存中的其他地方，每访问到一个新的索引节点，索引的范围减少一半。T树索引用来 实现关键字的范围查询。T树是一棵特殊平衡的二叉树（结合B树和AVL树进化而来），它的每个节 点存储了按键值排序的一组关键字。T树除了较高的节点空间占有率，遍历一棵树的查找算法在复杂 程度和执行时间上也占有优势。现在T树己经成为内存数据库中最主要的一种索引方式。T树索引的 示意图如图所示：父结点指针T树结点T树具有以下特点：左子树与右子树之差不超过1

20、，在一个存储节点可以保存多个键值，它的最 左与最右键值分别为这个节点的最小与最大键值，它的左子树仅仅包含那些键值小于或等于最小键值 的一记录，同理右子树只包括那些键值大于或等于最大键值的记录，同时拥有左右子树的节点被称 为内部节点，只拥有一个子树的节点被称为半叶一，没有子树的节点被称为叶子，为了保持空间的 利用率，每一个内部节点都需要包含一个最小数目的键值。由此可知T树是一个每个结点含有多个关 键字的平衡二叉树，每个节点内的关键字有序排列，左子树都要比根节点关键字小，右子树都要比根 节点关键字大。在上述T树结点结构中，包含如下信息：(1) balance(平衡因子)，其绝对值不大于1，bala

21、nce =右子树高度-左子树高度；Left_child_ptr和Right_child_ptr分别表示当前结点的左子树和右子树指针；(3) Max_Item表示结点中所能容纳的键值的最大数；Key0至KMax_Item-1为结点内存放的关键字；(5)nItem是当前节点实际存储的关键字个数。对于T树有如下特征：与AVL树相似，T树中任何结点的左右子树的高度之差最大为1；(2) 与AVL树不同，T树的结点中可存储多个键值，并且这些键值排列有序；(3) T树结点的左子树中容纳的键值不大于该结点中的最左键值；右子树中容纳的键值不小于该结点中 的最右键值；(4) 为了保证每个结点具有较高的空间占用率，

22、每个内部结点所包含的键值数目必须不小于某个指定的 值，通常为(Max_Item-2)(Max_Item为结点中最大键值目)。T树索引的操作：用T树作为索引方式主要完成三个工作：查找，插入，删除。其中插入和删除都是以查找为基础。下 面分别介绍三种操作的流程。(1) T树的查找类似于二叉树，不同之处主要在于每一结点上的比较不是针对结点中的各个元素值， 而是首先检查所要查找的目标键值是否包含在当前结点的最左键值和最右键值所确定的范围内，如果 是的话，则在当前结点的键值列表中使用二分法进行查找；如果目标键值小于当前结点的最左键值， 则类似地搜索当前结点的左孩子结点；如果目标键值大于当前结点的最右键值，

23、则类似地搜索当前结 点的右孩子结点。(2) T树的插入是以查找为基础，应用查找操作定位目标键值插入位置，并记下查找过程所遇到的 最后结点。如果查找成功，判断此结点中是否有足够的存储空间。如果有，则将目标键值插入结点中； 否则将目标键值插入此结点，然后将结点中的最左键值插入到它的左子树中(此时是递归插入操作)， 之后结束；否则分配新结点，并插入目标键值；然后根据目标键值与结点的最大最小键值之间的关系， 将新分配的结点链接为结点的左孩子或右孩子；对树进行检查，判断T树的平衡因子是否满足条件， 如果平衡因子不满足则执行旋转操作。(3) T树的删除操作也是以查找为基础，应用查找操作定位目标键值。如果查

24、找失败，则结束；否 则令N为目标键值所在的结点，并从结点N中删除目标键值；删除节点后，如果结点N为空，则删 除结点N，并对树的平衡因子进行检查，判断是否需要执行旋转操作；如果结点N中的键值数量少于 最小值，则根据N的平衡因子决定从结点N的左子树中移出最大的键值或者右子树中移出最小值来 填充。T树索引实现关键技术：实现T树索引即要实现T树的查找，插入和删除。其中又以查找为基础，对T树的维护也就是T树 的旋转为关键。当由于插入或删除键值导致树的失衡，则要进行T树的旋转。使之重新达到平衡。在插入情况下，需要依次对所有沿着从新创建结点到根结点路径中的结点进行检查，直到出现如下两 种情况之一时中止：某个

25、被检查结点的两个子树高度相等，此时不需要执行旋转操作；某个被检查结 点的两个子树的高度之差大于1，此时对该结点仅需执行一次旋转操作即可。在删除情况下，类似地需要依次对所有沿着从待删除结点的父结点到根结点路径中的结点进行检查， 在检查过程中当发现某个结点的左右子树高度之差越界时，需要执行一次旋转操作。与插入操作不同 的是，执行完旋转操作之后，检查过程不能中止，而是必须一直执行到检查完根结点。由此可以看出，对于插入操作，最多只需要一次旋转操作即可使T树恢复到平衡状态；而对于删除操 作则可能会引起向上的连锁反应，使高层结点发生旋转，因而可能需要进行多次旋转操作。为了对T树进行平衡，需要进行旋转操作，

26、旋转是T树中最关键也是最难的的操作，下面介绍T树 旋转的技术。旋转可分为四种情况：由左孩子的左子树的插入(或者删除)引起的旋转记为LL旋转， 类似有LR，RR及RL旋转。插入时的情况与删除类似。2.封锁技术：封锁是实现并发控制的一个非常重要的技术。封锁的基本思想是:当一个用户对一个表或记录进行更 新时，封锁该表或记录,使其他用户不能在同一时刻更新相同的表或记录。迫使其他用户在更新后的基 础上再实施另外的更新操作。采用封锁技术后的事务进程如图所示：时间A3LOCER)SELECT RLOCK等符UffiATE R等待UN_OCK(R)等待获得 LOCK(iySHLECT RUffiATE RUN

27、LOCK(R)SQL Server的封锁机制：事务是数据库并发控制的逻辑单位，并且具有原子性、一致性、隔离性、持久性四个特性，即事务的 ACID特性。事务的结束分为：提交(COMMIT)和滚回(ROLLBACK)两种情况。为了保证数据的一 致性,并且允许最大量地并发用户,SQL Server提供了多种封锁机制。封锁的对象可以是表格、页或者 记录。(1) 共享封锁(Shared Lock).共享封锁是为读操作设置的一种封锁，目的是想读到一组不变的数据，如果 对数据对象使用了共享锁，其它事务也可以获得该共享锁,使多个事务可以同时读取数据对象，但他们都 不能对该数据进行任何修改操作。在所有共享锁释放

28、之前,其他事务都无法获得这些对象的排它锁。(2) 更新封锁(Update Lock).当需要对一个记录或一组记录进行更新时(只是修改,不包括插入和删除) 使用更新封锁。该封锁的目的是防止其它事务在同一时刻修改同一记录。更新锁与共享锁兼容，已经实 施更新封锁的记录,拒绝来自其他用户的更新封锁或排它锁。(3) 排它封锁(Exclusive Lock).排它封锁也叫独占封锁，这是最严格的一类封锁。当需要对数据对象实 施插入、删除或修改操作时，应当使用排它封锁。已经实施排它封锁的数据对象,拒绝来自其它事务的 任何封锁请求。(4) 意向封锁.表达了使用共享锁或独占锁封锁数据对象的意向，它可以防止其它事务

29、对封锁数据对象 加排他锁,意向锁包括共享意向锁(IS)，排它意向锁封锁的模式取决于并发事务存取资源的方式。通常 写数据的优先级高于读数据，所以，要保证历史数据和实时数据的完整,首先要在读数据时加共享锁，在 写实时数据时加排它锁，写历史数据时加更新锁。所有的封锁都将在事务结束(提交或撤消)时自动释 放。SQL Server的封锁操作是在SELECT语句中完成的，在指定选择表的同时，指定对表所实施的封锁(在FROM子句中).如对sample表实施一个共享封锁，并且保持到事务结束时再释放封锁,相应的命令如 下：SELECT 3FROM sample (TABLOCK HOLDLOCK)其中:TABL

30、OCK说明是对表的共享锁,HOLDLOCK说明封锁将保持到事务结束.说明封锁有关的关键 字如下：NOLOCK:不做任何封锁.TABLOCK:对表施行共享封锁.PAGLOCK:按数据页施行共享封锁.UPDLOCK:在读表时施行更新封锁.TABLOCKX:对表施行独占封锁.HOLDLOCK :说明共享封锁将保持到事务结束现在再来考虑一下前面讨论过的火车票售票系统，显然采用更新封锁最为合适.假设售票信息存放在 关系R(日期，车次，座别，座位号,状态)中,其中座别说明是软卧(RW)、硬卧(YW)、软座(RZ)或硬座 (YZ)，状态表明车票是否售出,初值为NULL.下面是相应程序段：DECLARE rq

31、 datetime , cc char (6) , zb char(4) , zwh char (12)BEGIN TRANSACTIONSELECT zwh =座位号 FROM R (UPDLOCK)WHERE 日期=rq AND 车次=cc AND 座别=zb AND 状态 IS NULLIFUPDATE R SET 状态=YWHERE 座位号=zwh AND 日期=rq AND 车 次=cc AND 座别=zbCOMMIT TRANSACTIONELSEROLLBACK TRANSACTION其中的SELECT语句查询并封锁一条车票记录,UPDATE语句完成更新操作，如果完成更新则提交事 务并自动释放封锁，否则就撤消事务并自动释放封锁。