内存数据库

内存数据库的数据组织摘要：近年来，电信和金融领域的主要应用已经转变为数据密集型的应用，据库系统在其中起到了关键作用。这些应用大多要求高性能、实时/近实时的数据访问，但传统的基于磁盘的关系数据库系统无法满足上述应用的要求。基于上述应用需求产生了内存数据库系统，它能很好满足各种应用系统的实时数据管理需求。文章以HLR(HomeLocationRegister)为例介绍适合内存数据库的记录数据组织方法以及内存数据库的索引结构。关键词：内存数据库记录索引AbstractInrecentyears，thetelecommunicationandthefinancialdomain'smainapplicationhasbecometheapplicationofdataintensity，anddatabasesystemplayedthecrucialrole.Theseapplicationsmostlyrequestthehighperformance，thereal-time/nearreal-timedataaccessing，butthetraditiondatabasesystemthatbasedonfloppydisk'sunabletosatisfythisrequest.Basedontheaboveapplicationshavebecomethemainmemorydatabasesystem，itisagoodvarietyofapplicationsystemstomeetreal-timedatamanagementneeds.ThisarticleasHLRforexampletointroduceseveralrecordsformainmemorydatabase’sdataorganizationmethodsandseveralmemorydatabaseindexstructure.Keywordsmainmemorydatabaserecordindex一、引言在电信和金融等领域中，数据管理系统负责处理用户和网络信息，还是关键的底层支撑系统之一。随着网络应用的智能化、多媒体化以及用户规模的扩大和通信市场竞争的加剧，运营商要求应用系统能实时进行数据的存取、处理和发送。传统基于磁盘的关系数据库系统由于主数据库常驻磁盘，事务处理往往涉及磁盘I/O操作，其，体系结构设计优化目标是如何减少读写磁盘的次数，很难满足基于网络的应用系统对高性能数据访问能力的需求。为了应对这些挑战，电信企业引入了内存数据库。内存数据库的定义：任意时刻t，对于活动状态事务集的任意事务T所操作的数据集存在于内存中。它所关注的是数据库永久留驻内存、事务的数据存取只涉及内存。相对于磁盘，内存的数据读写速度要高出几个数量级，同时，内存数据库抛弃了磁盘数据管理的传统方式，基于全部数据都在内存中重新设计了体系结构，并且在数据缓存、快速算法、并行操作方面也进行了相应改进，数据处理速度比传统数据库的数据处理速度要快很多。内存数据库与磁盘数据库相比的主要优势在于:1、内存数据库主数据常驻内存，体系结构设计的优化目标是提高内存和CPU使用效率，由于事务处理无需进行磁盘访问，使用内存数据库的应用系统性能得到极大提高。2、内存数据库不再需要缓冲区管理器，消除了磁盘与内存之间额外的数据拷贝开销，在数据和索引的组织管理中广泛使用指针，简化了内存管理，降低了内存开销。本文介绍了内存数据库的数据的组织结构，包括数据的物理存储结构、空间结构及索引所采用的数据结构的选择。二、记录数据组织结构内存数据库的总体设计目标是使内存和CPU的利用率尽可能高，而内存数据库的物理组织是实现该目标的基础，其存储结构、索引结构都必须考虑内存的直接存取这一特征，以下介绍几种适合内存数据库的数据组织结构。2.1区段式数据组织结构目前，绝大多数数据库都是数据基于关系表的关系数据库，在关系数据库中往往使用二维的关系表来保存数据。二维表在磁盘数据库中已被广泛使用，使用二维表保存数据主要维护两方面信息:描述信息和记录信息。描述信息即指表名、字段名、类型信息、索引、主键等用于描述关系表的信息。记录信息是保存在关系表中的每一条记录的数据内容。区-段式是将使用的内存空间划分为多个可不连续的段空间,段内则是一片连续的内存区域多段构成一个区空间。区或段都由其各自的标号导向,即存储一条表记录需要指定其区标号、段标号和段内实存地址号区段式数据组织结构将共享内存划为若干个“分区”，每个分区存储关系数据库的一个关系，每个分区又由若干固定长度的“段”(也称作“页”)组成，一个段往往是共享内存动态分配的一个单位。数据库具体的数据记录保存在段中分配的一个记录块中。区段式数据组织结构如图1所示。在采用区段式的数据组织结构的数据库中，一个记录的地址信息由一个三元组P，S，L标志，其中，P是分区号，一般对应于一个关系表名；S是段号，标志组成这个分区的具体的段；L是段内记录槽号，主要保存记录在段内的偏移和长度，用来在段内进行寻址。通过这个三元组可以唯一地定位一个记录的具体位置。图1区-段式数据组织结构图2.2影子内存式影子内存式是针对当多事务共享数据库的情况时，依据优先权或抢占式机制，分配事务占用内存空间的方法。如图2所示。其中PDB是内存数据库的主副本，SM是影子区。图2影子内存2.3基于对象的数据组织结构除区段式的数据组织形式外，随着面向对象技术在内存数据库的应用以及对象数据库的兴起，很多数据库采用了基于对象的组织结构。当采用基于对象的数据组织结构时，数据库的记录及记录的索引都用对象来实现，以对象为单位进行内存的分配，记录对象之间和索引对象之间的联系，由对象自身来维持。在使用基于对象的数据组织结构时往往使用指针来维持对象之间的联系，较典型的基于对象的内存数据库就采用了这种数据组织方式。区号段号段内槽号PDBSMMMDBRecordPtrRecordNumLinkedPtr…….TableObjectRecordPtrRecordNumLinkedPtr…….TableObjectRecordPtrRecordNumLinkedPtr…….TableObjectDataBaseObjectTablePtr……IndexObjectIndexPtrIndextype……RecordPtrRecordNumLinkedPtr…….RecordObjectRecordPtrRecordNumLinkedPtr…….RecordObjectFile1…….FilenRecordObjectIndexObjectIndexPtrIndextype……IndexNodeObjectDateRcordPtrLchildRchildIndexNodeObjectDateRcordPtrLchildrchildIndexNodeObjectDateRcordPtrLchildrchild三、索引的结构四、由于内存数据库工作的主版本保存在内存中，所以内存数据库的索引选择应结合存储介质的特点，通过索引的建立来保证内存数据库查寻操作的高效性。目前，在内存数据库中经常选用的索引结构有hash索引和T树索引。3.1hash索引hash索引定义了一个hash函数，通过将关系表的索引项传入到hash函数可以计算出相应的hash值，从而在索引项与hash值之间建立起对应关系。由于用于保存不同的hash值的索引信息首地址往往是线性结构，所以可以迅速找到每个hash值的首地址，使得通过hash索引查找数据只需一个常数的时间复杂度。hash索引如图3所示。O-DB(Office-DB)T-DB(Temporal-DB)M1—VolatileMemoryM2—Non-VolatileRAMM3—DiskM4—TapesS-DB(Second-DB)A-DB(Archive-DB)Hashvalue1Hashvaluen……Hashvalue2Hashvaluen-1FieldValueAddressAddressFieldValueFieldValueAddressAddressFieldValueHash数组Hash冲突链图3Hash索引示意图由图2可知，索引项不同的数据使用hash往往会得到相同的hash值，所以一般为每个hash值建立一个动态的冲突链表来保存同一hash值的记录索引信息。当为一条记录建立索引时，只需要通过对索引项使用hash函数得到其hash值，通过得到的hash值迅速找到保存此hash值冲突链的首地址，并将这条记录的地址信息插入到冲突链中。当需要通过这个索引项的一个特定值查找记录时，只需对这个索引项给定的值运用hash函数求得hash值，找到该hash值冲突链的首地址，顺序遍历冲突链，找到待查找的记录的地址信息。hash索引的查找和维护非常简单，但是hash函数的选择往往非常困难，如果hash函数的hash值过小，往往使得冲突链过长，以致遍历过长的冲突链，降低效率。3.2T树索引传统磁盘数据库中使用B树索引，通过B树索引查寻数据可以减少磁盘访问次数，提高磁盘I/O效率。但是如果在内存数据库中使用B树，B树在内存数据库中的覆盖率较低。目前，内存数据库中较广泛使用的是结合B树和AVL树进化而来的T树。T树索引如图4所示。图4T树索引示意图T树节点中包括数据域和指针域。数据域中包含了多个数据对象，即按序排列的多个关键值。指针域包含一个指向父节点和两个子节点的指针，节点还拥有最大最低边界值(GLB)和最小最高边界值(LUB)。对内部节点来说，最大最低边界值是中序遍历访问时前一个节点中数据的最大值，最小最高边界值是中序遍历访问时后一个节点中数据的最小值。因为T树建立在树基础上，所以T树具有良好的二叉搜索特性。它的单个节点有多个数据，也拥有良好的修改和存储特性。T树节点还拥有两个特性:最小充满度和最大充满度。充满度是指节点中包含的数据值的个数。T树在节点内直接存放数据，克服了把所有真实数据全部存放在叶节点而造成节点数据覆盖率低的缺点。节点内数据的存取减小了在树上递归查找数据的深度，同时，由于T树属于AVL树的一种演进，具有AVL树平衡特性，从而进一步提升了树的搜索性能，因此，树在时间与空间两者间具有较好的平衡性。当使用T树索引时，插入、删除和查询索引主要涉及到的操作有:树的中序遍历、树的平衡、树的旋转和节点内数据的维护。父节点指针Data2Data4Data1Data3控制信息LchildRchildTnodeTnodeTnodeTnodeTnodeTnodehash索引在进行定值的查找时效率很高，而T树索引不仅具有树的二叉性，而且其设计特性符合内存数据库存储介质的特性，当前主流的内存数据库都至少提供了这两种索引结构。四、用户记录淘汰策略HLR系统中内存数据库为oracle的缓存数据库它存储了外存数据库的少量活跃用户数据。内存数据库需要从外存数据库加载用户数据当达到饱和后在倒入新活跃用户数据之前需要设法将内存中活跃程度较低的用户淘汰以节省内存空间。为此必须选择合适的淘汰内存非活跃用户策略并设计进行操作维护的数据结构。考虑对内存数据库中用户数据排序。一般越活跃的用户其数据越应存在内存中其权值也越高因而可对用户数据进行排序以决定下一个间隔后将被淘汰的用户。为了减少排序对系统资源的占用可以采用传统LRU(LeastedRecentUsed)的算法即用单链管理所有的用户数据记录每当一个用户的数据被访问到时就将其移到链尾淘汰用户从链头开始这样可以保证被淘汰的用户是内存数据库中活跃度最低的用户。算法简单但对用户的活跃程度描述并不精确可能会降低系统效率甚至引起死锁。为此将内存数据库中的用户定义若干种活跃状态处于同一种状态的用户被一条双向链连接。这样能够依据用户的活跃程度调整其所属双向链并淘汰低活跃权值链上的用户从而降低事务操作遇锁的概率。为了保证对用户数据记录的高效倒换和及时淘汰内存数据库在数据结构组织时需要在Hash索引表中增加对用户活跃权