一种分布式实时数据系统中的基于动态索引策略的存取定.doc

一种分布式实时数据系统中的基于动态索引策略的存取定位机制李德文，贾士博，谭彰，姚罕琦浙江中控技术股份有限公司，浙江杭州，310053摘 要：提出一种分布式实时数据系统中的基于动态索引策略的存取定位机制。该机制结合了改进的一致性哈希算法与“虚拟Token空间”机制。在该机制基础上，针对流程工业领域测点数据的特征和需求，用大量的廉价服务器实现了实时性高、吞吐量大、可扩展性好的分布式实时数据库系统。该数据库系统具有测点数据写入位置的自寻找、服务器集群内部状态变更时测点数据位置的自切换、数据查询的自优化、服务器负载自均衡等优势。该系统封装了分布式系统的各种瓶颈问题，使用户不需要关心系统内部的机制，可以像使用单体数据库系统一样直接向系统读写数据，而该系统性能又是单体数据库的叠加。通过在原型系统中测试验证，结果表明该机制能够达到设计预期目标和性能要求。关键词：分布式；实时数据；虚拟Token空间；动态索引；负载均衡A storage and inquiry location mechanism in distributed real-time data system based on dynamic index strategyLi Dewen, Jia Shibo, Tan Zhang, Yao HanqiZhejiang SUPCON Co., Ltd., Hangzhou, Zhejiang, 310053Abstract:A storage and inquiry location mechanism in distributed real-time data system based on dynamic index strategy is proposed. Combining the improved consistent hash algorithm with a Virtual Token Space mechanism and needs of the measuring point data in the field of process industries, the mechanism achieves a highly real-time, large throughput per second and good scalability distributed real-time database systems. The database system has advantages of point-data self locating, location self switching when the internal state of the server cluster changed, self-optimizing of data inquiry, self balancing of servers load. The system encapsulates a variety of bottlenecks problems in distributed systems , so that users do not need to care about the internal mechanisms of systems .Users could read and write data directly toward the system like using a single-server database,but the system performance is the superposition of the single database. Related tests show that this mechanism achieves expected target and meets performance requirement.Key words: distributed; real-time data; Virtual Token Space; dynamic index; load balance0 引言面向石化、化工等流程工业领域的实时数据库是现代大型过程控制系统的核心数据平台，向效益评估、工艺优化、管理决策等上层应用提供高效的数据服务。近年来，随着产业结构优化和集中度提升，企业的生产规模不断扩大，对实时数据库的性能、可靠性、可扩展性要求越来越高。而实时数据的动态存取索引机制作为系统提供各项数据服务的基础，其设计与实现的优劣直接影响到整个实时数据库的运行效率、数据安全与弹性扩展能力。因此，如何设计高效、高可靠性、高可扩展性的实时数据动态存取索引机制，成为实时数据库研究领域的一项关键问题。关注于上层控制策略的用户对底层数据实时存取系统的封装性要求也日益增强，更多的用户希望用大量的廉价服务器来实现系统存取性能的叠加，同时希望系统能克服掉分布式系统相较于单体系统的自然缺陷和瓶颈问题。现有实时数据存储动态存取索引方面的研究通过将实时数据的组织特点与应用特性结合1, 2，从而提高数据库的数据存储、查询性能。当前主流实时数据库产品虽然能够在一定程度上实现分布式存储，但服务器节点之间运行相对独立，任务协同性不足，难以灵活实现数据扩展与迁移，其带有Master性质的节点又会成为系统可靠性、可扩展性和廉价性的瓶颈。而现有的互联网行业的分布式存储系统,如Hadoop3、Cassandra4、Lucene5等，面向的数据对象是相对独立的数据块，无法直接匹配流程工业领域对大量连续推送的数据的实时存取的特殊需求。由于NoSQL技术6具有面向海量数据应用、规模动态扩展、系统可用性与可靠性高等特点，本文通过将NoSQL技术结合流程工业领域对数据系统的特殊需要，提出一种基于分布式系统的实时数据动态存取索引机制，在保证数据存取实时性的基础上，有效提高了实时数据库的海量数据存储与处理能力，能够适应当前流程工业企业对数据高可用性、高可靠性的需求。1 概述1.1系统结构系统结构如图1所示。采集器上送的数据通过分布式通讯服务平台分别存储至系统的多个节点中形成多重冗余，当某个节点无法正常工作而造成数据点备份失效时，其他备份仍能够正常存储、检索，提供与失效节点完全一致的数据服务。在数据库系统中，事务服务负责数据库系统中所有请求的管理，查询服务为数据库客户提供统一的查询接口。在数据安全性方面，通过多个数据服务器间产生不同数量的冗余备份，从而区别对待关键数据与普通数据，兼顾系统成本与可靠性。系统中的分布式通讯服务平台是一个分布式的通讯系统，又可以称为消息系统，为复杂网络、多平台下的应用提供消息接收、发送服务，保障数据传输的可靠性、实时性、安全性和高效性。图1 分布式实时数据库系统结构图1.2数据存储方案设计多个对等的服务器节点、采集器以及应用客户端通过接入到分布式通讯服务平台，构成统一的分布式实时数据库系统。本文结合了一致性哈希算法7、8、9及DHT算法10，设计了一种基于虚拟Token的索引机制，确定了各个服务器节点对测点数据的接收范围。系统的数据存储流程可分为以下5步：（1） 采集器对实时数据进行采集和整理、汇总后直接通过分布式通讯服务平台发往实时数据接收服务；（2） 不同的数据可根据其重要性配置不同份数的副本；（3） 根据数据的副本情况，本文所叙述的机制将采集器的数据定位到目标节点；（4）将实时数据上送至对应的服务器节点；（5）服务器节点进行解包，将数据点名按照一致性哈希算法映射为数据点ID，按照各个服务器节点所指定的令牌号将相应ID的数据发送至指定的服务器中，从而进入各个服务器的内部数据处理过程；（6）当节点不可用或接近磁盘空间的存储上限时，系统将根据本文所提供的机制智能地为采集器分配一个新的服务器节点来推送数据。1.3数据查询方案设计数据查询分为历史数据查询和实时数据的订阅查询两个部分。系统对实时数据的订阅查询的请求有如下3个步骤：（1） 根据虚拟Token机制和系统所维护的集群状态变化日志所记录的当前服务器节点对Token的管辖情况，计算出待查测点所在的服务器节点；（2） 订阅查询服务向该服务器节点订阅实时数据；（3） 当集群状态变化，致使该待查测点的数据被推送到其他服务器节点上时，系统将订阅查询服务引领至新的服务器节点上进行订阅查询。系统对历史数据的查询请求有如下4个步骤：（1） 根据虚拟Token机制和系统所维护的集群状态变化日志所记录的当前服务器节点对Token的管辖情况，以及查询的起止时间，计算出待查测点在查询起止时间范围内，每个时间段上的历史数据分别位于哪个服务器节点上。如果该测点有副本，则同时提供副本数据每个时刻分别位于哪个服务器节点上；（2） 分布式事务调度服务将根据（1）中提供的测点数据及副本数据在不同时间段上在个服务器节点的分布情况，将该查询事务分解为多个子事务，形成一个高效的并发查询策略。（3） 历史数据查询服务将向（1）和（2）中指定的服务器节点查询。（4） 分布式事务调度服务最终归并查询结果，返回给客户端。下文将重点介绍基于虚拟Token空间的动态存取的索引机制。2 机制基本原理2.1定义：虚拟Token空间用一个全局唯一的GroupID标识一个众多测点的集合，集合的生成方式依赖于用户所定义的测点的物理或逻辑关联性。这样，系统中的海量测点会被初步归并成多个Group。定义Token空间为0x0000-0xffff。对于每个Group，将其GroupID作为MD5哈希算法的输入量，其哈希结果为形如352d fcd6 fcc7 9137 95e6 e963 7a72 74d9的32位16进制数，取其前四位（上例中为352d），作为这个Group的Token值。无论系统中服务器集群状态如何变化，每个Group始终一一对应这个Token，这时，可以在上述的虚拟空间中找到该Group的位置，如图2。图2 GroupID在虚拟Token空间的对应位置2.2集群状态变化日志的职能集群状态变化日志分为集群实时状态变化日志和集群历史状态变化日志两部分。（1）集群实时状态变化日志记录了集群中每个服务器节点当前时间管辖了虚拟Token空间中的Token范围，以Token（以下简称T）NodeID（服务器节点ID，以下简称N）序列的形式记录，形如：上述序列记录了当前时刻的NodeID为1的节点管辖了虚拟Token空间中服务器节点的管辖范围T1到T2，即Token值在T1到T2之间的Group在当前时段都写入到N1上，Token值在T2到T3之间的Group在当前时段都写入到N2上，以此类推，每次更新实时的T-N序列时还需记录更新时间。该日志常驻内存。（2）集群历史状态变化日志记录了在虚拟Token空间中每段Token在每个时刻分别被哪个Node所管辖。其具体记录格式下文中将会详述。2.3 数据读写过程在流程工业领域中，数据写事务的特点是写过程持续不间断（采集器源源不断地上送实时数据）、数据结构简单、对写入效率要求高。数据读事务分为历史数据查询和实时订阅查询两种：历史数据查询的特点是查询时间可能很长（1-2年），查询数据量大；实时数据订阅的特点是对实时性要求高。下面针对这些特点，简述数据读写的基本流程。写数据时，首先，系统根据用户对测点关联性的配置为每个采集器所采集的为测点分组（前文所述的Group），每个采集器采集的测点被分成至多10个Group，如果有重要的、需要备份实时数据的点，则要被多个Group包含。然后按照0.1中所述的方法计算每个Group的Token值，再查阅集群实时状态变化日志，得到这个Group中的测点应推送至的目标服务器节点，当该服务器节点不可用时，系统将按照后文所述的算法自动分配一个或多个新的服务器节点来代偿管辖该不可用节点的原管辖的Token空间范围。订阅实时数据时，先计算所订阅的测点所在的Group的GroupID的Token值，再根据实时状态变化日志，得到这个Group中的该测点所在的服务器节点，当集群状态变化致使该Token归属于另外的服务器节点所管辖，系统将有通知，订阅者接到通知后，按照实时状态变化日志的变更，到新的服务器节点上订阅。3 方案实现3.1 集群状态变化日志的数据结构的设计与实现在整个系统初始化的时候，系统根据集群中服务器的数量生成一个初始的T-N序列：T1N1T2N2T3N3Tn-1Nn-1TnNn，集群实时状态变化日志和集群历史状态变化日志都记录这个T-N全序列。当服务器集群状态变化时，系统将以后文所述的算法生成一个新的T-N序列。集群历史状态变化日志分为全量序列和增量序列两部分。每次集群状态变化后，更新T-N全序列记录到集群实时状态变化日志中，将增量T-N序列Append到集群历史状态变化日志中。当记录条数达到一个“全量周期值”（可选为1000即集群状态变化1000次）时，将集群实时变化日志所记录的当前时刻的全量T-N序列同步给集群历史状态变化日志，集群历史状态变化日志开始新的一轮增量记录。一个周期值内的集群状态变化称为一个变化周期，每个周期维护一张快查表。下面以三个集群状态变化情景为例，说明该机制。情景1：在t1时刻，N2达到了所设定的饱和阈值（可设定为该服务器节点磁盘容量的80%左右）。假设根据后文所述的集群状态变化策略，T2到T3范围内的Token应由N6来管辖，则集群实时状态变化日志所记录的内容变更为：T1N1T2N6T3N3Tn-1Nn-1TnNn。同时，集群历史状态变化日志记录了受影响的Token范围的T-N序列：T2N6T3。上式表示相比于t0时刻的实时状态序列，t1时刻的集群历史状态变化为，T2到T3范围内的Token应由N6来管辖。情景2：假设N8所管辖的节点范围是T8-T9，此时T8在t2时刻失效。假设根据后文所述的集群状态变化策略，T8-T9范围内的Token被管辖的情况如下：T8-T8.5范围内的Token被T10管辖，T8.5-T9范围内的Token被T11管辖，则相比于t1时刻，集群历史状态变化日志追加一条记录：T8N10T8.5N11T9。情景3：假设在t3时刻有新的服务器节点N15加入。假设根据后文所述的集群状态变化策略，N15将代偿其他服务器节点管辖一部分Token范围，则相比于t2时刻，集群历史状态变化日志追加一条记录：T12N15T13; T18N15T20; T23N15T24。集群历史状态变化示意图如图3所示。图3 集群历史状态变化示意图3.1.1 日志的数据结构设计集群实时状态变化日志的数据结构为:structTIMEcurrentTime;/当前时间stringcurrentTN; /当前T-N全序列下面介绍集群历史状态变化日志的数据结构:首先引入速查表Table。对于每个变化周期，维护一个速查表。用一维的bitset数组Table65536*1000存储图4所示的速查表的信息。图4中，Tablei*65536+j表示Token值为i、本变化周期内集群状态变化次数为j的元素是否属于某段增量状态变化记录，1表示在，0表示不在。 例如，在t2时刻，管辖情况变更的Token范围为T1-T2。形如T8N10T8.5N11T9的增量序列，在表中表示为第T8-T9列，第2行的元素置为“1”。图4 一个集群变化周期内的速查表集群历史状态变化日志的数据结构由下 面几个部分组成：（1） 全局唯一的map其中，n表示该时刻（time）对应的是第n个变化周期的速查表的第r行。（2） 对于每张速查表，有：mapn,r, map 其中，startToken表示每一个“1”序列的起始Token。3.1.2 查询过程首先，客户端将待查的测点所在的Group做一次MD5哈希运算，取其前四位，即为该Group的Token。对于订阅查询，直接通过访问集群实时状态变化日志,发起Group的位置查询请求，收到请求后，动态索引服务先将GroupID再次做MD5哈希运算，得到其对应的Token，再读取实时日志中记录的T-N序列，找到其Token在当前时刻所在的Node。对于历史数据查询，步骤如下：（1） 横向定位：先根据全局唯一的map，将查询的时间范围初步分解到每一个集群变化周期的速查表中。对于每一张速查表，再根据时间，按map定位到对应的行上。（2） 纵向定位：通过再次做MD5哈希运算，得到待查测点所在Group的Token值，直接以下标的方式定位到表中的一列。至此，得到了待查测点在每个待查时间段上属于表中的哪个单元。（3） 纵向回溯定位：如果（2）中的那个单元的值为“1”，则直接执行步骤（4）；如果值为“0”，则在表中竖直向上搜索，直到遇到值为“1”的单元格为止（如果上推到表的第一行还未遇到“1”，则无需执行（4），该Token的管辖范围在本集群变化周期内未改变，直接到本全量周期内的全量T-N序列中查找待查测点所在的Node）。（4） 横向回溯定位：（3）中纵向回溯至“1”处后，向左寻找这个“1”所在的“1”序列中第一个“1”的Token，根据mapn,r, map 定位到待查点在对应时刻所在的Node。（5） 合并查询结果，返回。3.2 集群状态变化生成策略算法首先介绍系统的负载均衡服务要为集群状态变化生成策略算法实时地记录哪些服务器节点负载指标。（1） 每个服务器节点的当前剩余磁盘容量Cremain（NodeID）。（2） 每个服务器节点的当前管辖的Token数T（NodeID）。（3） 所有服务器节点剩余磁盘总容量CallRemain。（4） 系统总剩余容量密度：Cdensity=CallRemain/65536。（5） 每个服务器节 吧 点的当前相对剩余磁盘容量CrelativeRemain（NodeID）=Cremain（NodeID）-T（NodeID）*Cdensity。这个指标表征了该节点除完成自身管辖外，还有多少代偿他人管辖的能力。集群状态变化生成原则有三点：（1） 尽量让负载较轻的节点代偿失效节点或空间接近耗尽的节点管辖的Token范围。（2） 在一个时刻内，尽量让一个节点管辖连续的Token区间。（3） 对于一段Token范围的不同时刻，让它被尽量少的节点管辖。根据以上原则，得到集群状态变化策略：当有服务器节点磁盘容量超出阈值或失效时，要为该节点管辖的每一段连续的Token制定代偿策略：对于待代偿的每一段Token，有如下步骤：1.首先检查其左、右节点是否满足：（1） CrelativeRemain（left） 0；（2） CrelativeRemain（right） 0；（3） Cremain（left）+Cremain（right）T（DownNode）*Cdensity（4） 其中，T（DownNode）为失效节点原管辖的Token范围中的连续的一段。若满足，按照Cremain（left）与Cremain（right）的比例分配左、右节点分别为之代偿的Token范围。若有CrelativeRemain（left/right） 0并且Cremain（left/right）T（DownNode）*Cdensity，则由其左/右节点独立承担代偿功能。2.若不满足上述条件，则对于它的原管辖的每段Token的大小Tk（k为该服务器节点管辖多段不连续的Token范围的编号），分别由近向远、左右同时地搜索满足这一条件的其它服务器节点。3.若遍历整个系统还无法找到一个/两个符合条件的节点，则重新由近向远、左右同时地搜索三个及三个以上节点的CrelativeRemain之和大于Tk的情况，以三个或三个以上的节点代偿管辖Tk。4 机制优势（1）适应了应用于流程工业的分布式实时数据库的特殊性需求：数据采集器不断地推送每一个测点的实时监测值，而查询者既有订阅实时数据的需求，又有查询一个长时间段的历史数据的需求。使推送者和查询者不必关心系统内部是否有机器存满、失效等问题。（2）系统可扩展性好，可适用于不同规模的集群。（3）兼容了多重副本冗余的数据可靠性策略、分布式事务调度策略、分布式错误监测及恢复策略、数据对象化服务策略等上层策略。上层策略可以不依赖于本系统而灵活挂载、替换。（4）解决了普通DHT、一致性哈希机制的性能问题和中心化节点机制的中心节点瓶颈问题：系统只保存了与服务器数量大致相当的轻量级全局信息，规避了上述二者的缺陷。（5） 服务器节点对虚拟Token空间的动态管辖机制避免了服务器网络上的数据流迁移，以轻量级的控制流代替。5 测试与验证5.1 测试环境数据服务器为DELL 990DT，数据模拟采集器和客户端均为DELL 380，运行Windows 7操作系统。5.2 测试步骤首先配置100000个测点，其ID为1-100000，使用4台服务器搭建服务器集群，数据备份参数N设置为2。点数总规模为10W点。使用2台数据模拟采集器模拟10W点正弦波采集数据，采集周期为2s，通过分布式通讯服务平台向服务器集群发送数据，使单台服务器平均实时存储数据量达到2.5W点。为测试在测点向各服务器节点推送速度不等的情况下，系统是否能自调整其负载情况，按如下步骤进行测试：（1）使用2台数据模拟采集器模拟10W点正弦波采集数据，采集周期为2s，向系统推送数据1000s。此时统计一分钟内各服务器节点的CPU平均使用率、内存使用率如表1所示：表1 CPU、内存使用率（例1）服务器节点CPU平均使用率内存平均使用率Node1约33%约25%Node2约28%约31%Node3约27%约27%Node4约28%约27%（2）找出20000个Token值为0x0000-0x4000的测点，采集周期改为1s；找出20000个Token值为0xa000-0xffff的测点，采集周期改为5s，继续推送1000s，再次统计一分钟内各服务器节点的CPU平均使用率、内存使用率如表2所示：表2 CPU、内存使用率（例2）服务器节点CPU平均使用率内存平均使用率Node1约26%约33%Node2约24%约31%Node3约31%约28%Node4约29%约29%5.3 测试结论结果表明，在人为构造的负载不均衡的条件下，系统可以较好地满足分布式数据库的性能要求。本节通过搭建测试平台，对本文所设计的分布式系统的主要功能和性能做了测试，测试结果表明，本文所设计的分布式实时数据库的智能索引系统可以将多个单体大型实时数据库较好地协调管理起来，达到流程工业实时数据库的功能和性能要求。 6 结束语由于流程工业领域对实时数据库的性能、可靠性、可扩展性要求越来越高，本文以实时数据检索机制的设计与实现作为切入点，提出了结合一致性哈希算法的数据存储方案，设计并实现了基于多版本控制的数据管理