基于B+树和一致性Hash的分布式实时数据库索引算法

---------------------------------

收稿日期： ；修返日期： 基金项目：电子信息产业发展基金：分布式实时数据库管理系统研发及产业化。

作者简介: 李贤慧(1983－),男,湖南省郴州市嘉禾县人，软件工程师，硕士，主要研究方向为分布式实时数据库，基于内容的视频检索，lixianhui@https://www.wendangku.net/doc/6b5456601.html, ；岳梦龙（1988-）男，河南郑州人，软件工程师，硕士研究生，主要研究方向为关系数据库与实时数据库；季胜鹏(1978-)，男，产品开发部主任，硕士研究生，主要研究方向为电力系统自动化信息化，实时数据库；赵京虎(1972-)，男，江苏南京人，高级工程师/副总经理，硕士研究生，主要研究方向为电力系统自动化，实时数据库.

基于B+树和一致性Hash 的分布式实时数据库索引算法

李贤慧1 岳梦龙

1，2

季胜鹏1 赵京虎1

(1.江苏瑞中数据股份有限公司,南京市 21000；2.南京大学软件学院，南京市 21000)

摘要：提出一种基于B+树和一致性哈希算法的分布式实时数据库层次索引方法。首先，将存储节点和测点映射到环形哈希空间，确定分布式环境下每个测点的存储位置；然后，在每个数据存储服务器，维护一张测点哈希表，记录该数据存储服务器每个测点索引的位置；最后，每个测点建立B+树索引，组织维护该测点所有历史数据。实验结果证明了该方法的有效性。 关键词：分布式系统；实时数据库；层次索引；一致性哈希 中图分类号：TP311.13 文献标识码: A

A Distributed Real-time Database index algorithm based on B+ Tree

and Consistent Hashing

Xian-Hui Li 1,Meng-long Yue 1,2

(1. China Realtime Database CO.LTD., SGEPRI, Nanjing, 210000, China; 2.Software Institute of Nanjing University, Nanjing,

21000, China)

Abstract: This paper proposed a novel method of Distributed Real-time Database index algorithm based on B+ Tree and Consistent Hashing. In order to determine the storage location of each TAG point in the distributed environment, First of all, every storage node and each TAG point are mapped to circular hash space. Secondly, create a hash table of TAG point in every storage node, which record the position of index in each TAG point. Finally, a B+ Tree index are established to organize and maintain the historical data of one TAG point. Theoretical analysis and experimental results show the validity of the proposed method. Key words ：d istributed s ystem, r eal-time d atabase, h iberarchy i ndex, c onsistent h ashing.

0. 引言

随着计算机技术的发展以及自动化水平的提高，出现了很多对数据的存取和管理具有时间约束的应用，例如电力系统调度、工业控制、证券交易、航空航天等等。这些应用通常需要实时对监控设备进行采样以了解系统运行最新状况，因而采集频率非常高，达到每秒25、50甚至100帧；同时，指定时间内的所有数据必须完整保存，从而需要维护海量的数据；并且要求在指定的时刻或时间范围内对数据进行采集、处理并做出正确响应，具有明显的时效性。如此海量、实时、高频的数据，传统的关系型数据库无论是存储还是检索都显得捉襟见肘，很难满足这些应用的需求。近年来，实时数据库的出现使得这些应用需求的实现成为可能。从而使得实时数据库成为当前企业和学术界的研究热点

[1,2]

。目前，

国内外比较成熟的实时数据库系统包括美国OSIsoft 公司的PI [3]

、美国InStep 公司的eDNA [4]

、瑞中数据的HighSoon [5]

以及朗坤软件的LiRTDB [6]

等。

实时数据库是专门设计用来处理具有时间序列特性的数据库管理系统，该系统用于对上述领域实时、高频、海量数据进行存储管理。同时，为了提高系统的扩展性、容错性以及存储检索速度，将实时数据库系统分布式化。正因为分布式实时数据库实时、海量、高频以及分布式的特点，如何提供一种好的索引方法对数据库进行存储和检索效率起着至关重要的作用。基于此目的，本文提出了一种分布式实时数据库层次索引算法，首先，通过一致性哈希算法确定每个

测点与数据存储服务器的对应关系；然后每个数据存储服务器内部维护属于该节点的测点的哈希表，通过测点名字或者测点ID作为哈希键值；最后，为每个测点分配一颗索引B+树，记录该测点所有数据的存储位置。实验部分通过对比几种索引方法证明了该方法的有效性。

1.分布式实时数据库框架

整个分布式实时数据库系统主要由两类节点[7-9]，其一是中心控制服务器NameServer，整个系统只有一个，主要存储系统相关元数据，如每个数据存储服务器信息，数据分片信息，访问控制信息等；其二是数据存储服务器DataServer，整个系统可以有多个，可以分步在不同的计算机，它主要用于分布式实时数据库数据的存储。客户端对数据的存储和检索首先向中心控制服务器发送请求，查询实际数据所在的数据存储服务器，然后再跟具体的数据存储服务器通信，实现数据的真正存储和检索。因而实际数据库数据的传输在客户端和数据存储服务器之间进行。NameServer 一般采用双机热备的形式提供系统的可用性和可靠性。正常情况下，NameServer Active 对外提供服务，一旦NameServer Active出现故障停止服务，NameServer Standby将自动切换为Active模式对外提供服务以保证系统的高可用性和可靠性。DataServer内部存放以测点为单位的数据文件。每个测点数据文件在整个分布式实时数据库中存在多份副本以提高系统的可用性和容错能力。同时测点也是动态负载均衡的基本单位，NameServer通过分析每个DataServer负载情况动态的调整每个DataServer的负载情况。NameServer通过心跳机制检测每个DataServer的运行状况，心跳包包括当前DataServer的CPU、内存、磁盘使用情况，是nameServer施行动态负载均衡的依据。图1为分布式实时数据库框架的一个典型用例。

图1 分布式实时数据库框架图

Fig.1 Distributed Real-time Database framework diagram

2.层次索引方法

2.1 数据分片

在分布式实时数据库系统中，随着数据量的不断增加，如何更好的存储和管理数据成为影响分布式实时数据库性能的主要指标。一种比较好的方法是对分布式系统进行数据分片[10]。通过数据分片将整体数据分摊在多个存储设备上，这样每个存储设备的数据量相对就会小很多，以此满足系统的性能需求。当然，数据分片的方法有很多种，有通过ID 特征分片的，有根据时间范围分片的，有根据数据量分片的。本文结合公司系统业务范围，通过测点ID作为数据分片的策略，同时为了提高系统的容错性以及尽量减少节点上线或节点下线后重新哈希导致数据的大量迁徙，结合本公司业务，选择文献[11-13]所提方法作为数据分片哈希算法，通过该方法，在移除/添加一个数据存储服务器时，它能够尽可能小的改变已存在key映射关系，尽可能的满足单调性、平衡性和分散性的要求。

定义1平衡性(Balance)：指哈希算法要均匀分布，不能有明显的映射规律，这对一般的哈希实现也是必须的。

定义2单调性(Monotonicity)：指有新节点加入时，已经存在的映射关系不能发生变化。

定义3分散性(Spread)：指避免不同的内容映射到相同的位置和相同的内容映射到不同的位置。

本文方法数据分片的方案步骤如下：

2.2 构造环形Hash空间

将要映射的实体通过一定哈希算法映射到n位的哈希键值，也即0~2^n-1次方的数值空间，然后将该空间首(0)尾(2^n-1)相连，构成环形哈希空间。本文结合具体情况，取n为32位，那么，构造的hash空间如图2所示。其中hash映射函数采用下面的形式：

Key = hash(objectID);

图2 hash环空间

Fig.2 hash space

2.1.1DataServer映射

系统初始化过程中，对所有数据存储服务器根据特征标识码(如数据存储服务器的地址和端口)，通过相应哈希算法将该特征码映射到环形哈希空间，对应到哈希环空间的某个值，作为该数据存储服务器节点的标识；本文假设系统中存在7个数据存储服务器，分别是DataServer1~7,经过hash 映射后，在环形hash空间中的映射关系如图3所示。

图3 DataServer经过映射后的分布情况

Fig.3 The Distribution of DataServer after mapping

2.1.2测点映射

系统添加测点的过程中，客户端发送加点请求给中心控制服务器，中心控制服务器根据请求测点特征标识码(如点名，点ID)计算该点名MD5值，通过相同的哈希算法将该MD5值映射到环形哈希空间，并且按顺时针方向(哈希键值增大方向)寻找数据存储服务器节点，第一个成功节点即为该测点存放位置；本文系统中存在P1~P17共17个测点，那么经过对测点用相同的hash算法映射后，测点在环形hash空间上的分布情况如图4所示，经过hash映射后具体每个数据存储服务器存储的测点如表1所示。

图4 DataServer和测点映射后的分布情况

Fig.4 the Key value distribution of DataServer and TAG

point after mapping

表1 数据存储服务器所存储的测点

Table1 TAG point store in each DataServer

数据存储服务器存储测点数据存储服务器存储测点DataServer1 P10 DataServer5 P02,P09,P14,P16 DataServer2 P04,P12 DataServer6 P06,P11 DataServer3 P01,P07 DataServer7 P05,P08,P15 DataServer4 P03,P12,P17

2.1.3节点失效情况

通过一致性哈希算法，可以保证新的数据存储服务器加入或旧的数据存储服务器失效的情况下，系统仅需要迁徙失效节点的数据，而其他节点的在Hash环上的映射关系基本不变，也即数据不需要迁徙。如图5虚线所示节点DataServer1失效后，仅仅需要将DataServer1内部的点P10的数据迁徙到DataServer3即可，其他映射关系基本不变。当系统插入数据或查询数据时，首先向中心控制服务器发送请求，查找相应测点在哪个数据存储服务器，此为本方法层次索引第一层：确定测点存放的数据存储服务器。

图5 DataServer1失效后测点映射分布情况

Fig.5 TAG the Key value distribution after DataServer

failure

2.3 测点索引

在每个数据存储服务器内部，维护着一张存储每个测点结构信息的测点哈希表PointHashTable ，记录着本数据存储服务器维护的所有测点的点结构信息，测点结构信息包括测点名称，测点ID ，测点B+树根节点所在位置等。点结构信息PointConfigItem 如下所示：

struct PointConfigItem {

unsigned long pointID; char pointName[32];

char desc[128]; char addr[32]; char unit[32]; ValueItem rtValue; Pointer rtCache; … }

其中测点哈希表PointHashTable 实现为： map(int PointID, PointConfigItem* item);

在PointConfigItem 内部，rtCache 指向测点对应的Cache 缓存区，在缓存区里面有一个指针

rawHist ，指向B+的根节点。客户端向中心控制服务器确定请求测点所在数据存储服务器后，发送请求到测点所在的数据存储服务器，如果是增加测点，通过对测点特征标识码(如点名，点ID 等)做哈希将需要添加的测点映射到测点哈希表中的相应位置；如果是存储或检索数据，数据存储服务器通过对测点名做哈希，取得测点信息，从而获取B+树索引根节点所在位置。此为本文方法层次索引第二层：确定测点数据B+树索引存放位置；测点哈希结构如图6所示。

图6 数据存储服务器测点哈希表

Fig.6 DataServer hash table with TAG points

2.4 数据索引

待确定测点B+树索引所在位置后，如果请求是存储或者检索数据，系统从B+树根节点开始，对比每个索引节点索引的时间范围，确定遍历下一层索引节点的指针，如此层次搜索B+树索引节点，最后确定请求存储或检索数据的实际插入或存放的数据存储服务器位置。此为本方法层次索引第三层：确定存储或检索的测点数据实际存放位置。

数据节点结构： struct DataNode {

long length,type, count;

Pointer prev, next; AbsoluteTime start,end; … }

索引节点结构： struct IndexNode {

long length,type; Pointer prev, next;

AbsoluteTime times[SLOT_COUNT]; Pointer pointer[SLOT_COUNT+1]; ...

}

在B+树的数据节点部分，我们对B+树的结构做了部分修改，将B+树的数据节点通过prev,和next 指针改造为双

向链表，这样可以提高批量检索的速度。每个测点B+树索引结构如图7所示。

图7 分布式实时数据库DataServer 端B+树索引结构图

Fig.7 B+ tree index structure diagram in DataServer side of Distributed Real-time database

3. 实验结果

实验部分采用本公司(江苏瑞中数据股份有限公司)主打产品HighSoon 为测试平台，分别测试不同的索引结构查询、检索效率。对于分片方案的优越性可以参考文献[7-11]，而通过ID 映射查找测哈希表是花费时间比较小，所以本实验重点对比底层数据索引方式对存储和检索效率的影响，同时考虑数据的持久化过程。主要对比了B+、红黑树以及T 树断面插值、批量插值和检索性能，其中整个测试平台基于点数为20万点，插入数据为每个点1000万事件的情况。实验结果如表2所示,单位为万事件每秒，从表中可以看出，B+树作为大数据量、需要持久化的系统中具有更好的性能。

表2 四种数据索引结构插值、和检索性能比较 Table 2 Insert and retrieve performance comparison among four data interpolation index structure 功能 B+ 红黑 T 树

批量插值 309.2 221.5 210.2 断面插值 160.0 120.1 100.6 检索

119.6

91.8

49.7

同时，实验对比了三种索引结构插值事件率跟数据量的关系，具体实验结果如图8所示，从图中可以看出，B+树受数据量大小影响相对较小，而T 树和红黑树受数据量影响相对较大，从而更可以确定，B+树更加适用于需要对数据持久化的系统，而红黑树和T 树适合缓存索引结构。

图8 四种数据索引结构插值性能与数据量关系比较 Fig.8 Four data index structure compared with the relationship between the amount of data and

interpolation performance

4. 结束语

本文提出了一种新的分布式实时数据库层次索引方法。通过引入一致性哈希算法，确定分布式环境下实时数据库数据的分片规则；利用哈希表和改进B+树索引，维护每个测点的数据索引。实验部分对比了本文提出方法和几种常见方法的存储和检索效率，可以看出本文提出方法整体效果更好。由于公司现在主要市场在电力行业，因此下一步工作主要是针对具体实施行业，对索引做参数调优(如B+树每个节点槽位个数)以适应不同行业存储和检索效率要求。 参考文献

[1].Ben Kao, Hector Garcia-Molina. An overview of real-time database systems[R]: Tech. Report of Princeton University,

Stanford University 1990.

[2].叶建位，苏宏业. 实时数据库系统关键技术及实现[J].计

算机应用研究, 2005, 22(3):45-47.

[3].OSI,PI_System_Standards[EB/OL].https://www.wendangku.net/doc/6b5456601.html,/s

oftware-support/what-is-pi/PI_System_Standards.aspx. [4].InStep, edna_overview[EB/OL].

https://www.wendangku.net/doc/6b5456601.html,/edna_overview.asp . [5].CRD ,HighSoon.[EB/OL] .https://www.wendangku.net/doc/6b5456601.html,/html

/cp68.shtm HighSoon.

[6].LUCULENT ,LiRTDB[EB/OL] .https://www.wendangku.net/doc/6b5456601.html,/projec

t/project-sssjk.asp LiRTDB.

[7].Fay Chang, Jeffrey Dean, Sanjay Ghemawat, etc. Bigtable: A

Distributed Storage System for Structured Data[J]. Journal of ACM Transactions on Computer Systems (TOCS). TOCS Homepage archive Volume 26 Issue 2, June 2008, ACM New York, NY, USA.

[8].Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The

Google file system[J]. Proceeding of SOSP '03 Proceedings of the nineteenth ACM symposium on Operating systems principles, Volume 37 Issue 5, December 2003, ACM New York, NY, USA.

[9].Jeffrey Dean, Sanjay Ghemawat. MapReduce: simplified

data processing on large clusters[C]. Communications of the ACM - 50th anniversary issue: 1958 –2008 CACM Homepage archive. Volume 51 Issue 1, January 2008. ACM New York, NY, USA.

[10].Wikipedia, Shard( database architecture)[EB/OL].

https://www.wendangku.net/doc/6b5456601.html,/wiki/Shard_(database_architecture ).

[11].David Karger, Eric Lehman, Tom Leighton, Matthew Levine,

etc. Consistent Hashing and Random Trees: Distributed Caching Protocls for Relieving Hot Spots on the World Wide Web[C]: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, New York, 1997[C].

[12].Giuseppe Decandia, Deniz Hastorun, Madan Jampani, etc.

Dynamo: amazon's highly available key-value store[C].

Proceeding of SOSP '07 Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, Volume 41 Issue 6, December 2007. ACM New York, NY, USA.

[13].THE CODE PROJECT, Consistent hashing [CP].

https://www.wendangku.net/doc/6b5456601.html,/KB/recipes/lib-conhash.aspx.

第一作者简介：李贤慧，男，软件工程师，目前就职于国网电科院瑞中数据股份有限公司，工作期间主要研发和研究分布式实时数据库技术，硕士期间研究基于内容的视频检索。发表论文如下：

1.基于概率距离及融合时空特征的镜头相似性度量，计算

机应用研究。

2.Shot retrieval based on fuzzy evolutionary aiNet and

hybrid features，Computers in Human Behavior (SCI,IF=1.33), Volume 27, Issue 5, September 2011, Pages 1571-1578.

联系电话：139********

联系地址：江苏省南京市新模范马路5号A座19楼

E-mail: lixianhui@https://www.wendangku.net/doc/6b5456601.html,