基于多维度QoS约束的大规模企业信息副本定位方法.doc

基于多维度QoS约束的大规模企业信息副本定位方法

摘要：为了解决大规模企业信息系统中副本定位的目标节点服务质量问题，提出了一种基于多维度QoS约束的副本定位方法MQoSRL（Replica Location with Multidimensional QoS）。该方法把目标节点面向特定应用的多维度QoS保障程度纳入副本定位计算，采用分层和对等的混合定位机制，高效定位的同时有效避免了现有副本定位中目标节点服务质量无保障的风险。给出了大规模企业信息系统覆盖网模型、MQoSRL定义和算法及与之相关的应用层路由算法和副本发布算法。分析和应用表明，MQoSRL具有高效、有效、负载均衡等特性，同时对降低系统平均响应时间起到了一定的作用。
关键词：大规模企业信息系统；副本定位；多维度QoS约束；应用层路由
Replica Location with Multidimensional QoS Constraint in Large Scale Enterprise Information System
Abstract：To achieve high QoS of destination node in Replica Location (RL) over Large Scale Enterprise Information System (LSEIS), a novel Replica Location with Multidimensional QoS (MQoSRL) is put forward. MQoSRL offers a mechanism to achieve efficient and avoid risking bad QoS for a given application in existing RL. It is implemented by taking into account the guarantee degree of destination node for a special application with multidimensional QoS constraints and employing hybrid location mechanism based on layered and peer to peer. The overlay network model about LSEIS is described. The definition of MQoSRL is given. The sub-arithmetic about MQoSRL and other correlative arithmetics, such as replica publishing and application layer routing, are described. Analysis and application results illustrate its efficient, valid, load balanceable and other characteristics. Meanwhile, it is valuable to reduce the system response time.
Key words：Large Scale Enterprise Information System; Replica Location; Multidimensional QoS constraints; Application Layer Routing
0 引言
大规模企业信息系统（Large Scale Enterprise Information System, LSEIS）通常采用分布式方式构建或基于现有中小型企业信息系统集成，利用分布式、网格、面向服务、构件等技术为企业提供广域范围内的数据资源共享和计算能力集成[1,2,3]。随着企业规模的不断扩大和发展，与企业信息化管理中计划、组织、控制、指挥、协调等功能相关的数据、信息和知识等资源与日俱增，如何在这些海量资源中快速准确定位目标资源已经成为信息化大规模企业提高工作效率和降低运营成本亟待解决的关键问题之一。
资源定位是各种大、中型信息系统的共性问题。在采用复制共享资源以提高系统鲁棒性、可扩展性和服务性能的分布式系统中，资源定位的研究热点主要集中在副本定位方法和技术。对此，国内外学者在各种不同应用领域展开了大量的研究工作[4-6]，重点解决了基于现有数据网络的副本定位方法和支持高效副本定位的覆盖网络(Overlay Network)构建问题。两者本质上都是基于覆盖网的副本定位，且在不同程度上解决了副本定位的效率、负载均衡和可扩展性等问题。但是，目标节点是否能满足特定应用的服务质量(Quality of Service, QoS)需求仍是一个悬而未决的问题；同时，现有覆盖网结构也不能很好满足大规模企业管理模式下LSEIS信息管理的区域化需求。鉴于此，本文提出了一种基于多维度QoS约束的副本定位方法MQoSRL(Replica Location with Multidimensional QoS)，把区域化概念和实体引入LSEIS覆盖网的构建，基于区域内分层和区域间对等的混合副本定位方法，把目标节点面向特定应用的多维度QoS保障程度纳入副本定位计算，实现了副本定位的高效率，有效避免了现有副本定位中目标节点QoS无保障的风险。文中建立了适合于LSEIS的混合覆盖网拓扑模型，定义并形式化描述了MQoSRL，给出了区域间路由表结构和路由算法、基于LSEIS拓扑结构的副本发布算法以及MQoSRL各子算法，分析了系统性能并给出了一个应用实例。
1 LSEIS拓扑模型
站2
站1
站2
站1
区n
区4
区2
区1
：资源存储节点
：站代理节点
：区代理节点
图1 LSEIS网络拓扑模型
Internet
区3
在基于网络的应用中，覆盖网拓扑结构对整个系统性能的优劣起着至关重要的作用。为了模拟大规模企业内部的分级、分区域管理模式，兼顾现有基础网络的区域化特性，我们在粒度大小适中的管理区域内部采用区/站/资源节点三层结构和区域间对等的方式构建LSEIS的覆盖网拓扑结构如图1所示。
LSEIS包含如下三种不同角色的节点：
资源存储节点(Resources Storage Node, RSN)：资源的实际存储节点，可广域分布于世界各地。通常可把同一局域网的RSN组织为一个“站”并生成相应的站代理节点。
站代理节点(Site Agent Node, SAN)：专门配置或在本站RSN中选取的综合性能(在线时间、网络带宽、节点处理能力等)相对较好的节点，用于站内副本目录的管理与维护。站内副本目录信息包括资源的逻辑名及其一个或多个对应副本的物理地址、存储节点属性(IP 地址、CPU 速度、内存、带宽、存储容量等)、版本号、副本数等。根据区域化管理模式，一般将相邻多个站组织为一个“区”并生成相应的区代理节点。
区代理节点(District Agent Node, DAN)：专门配置或在本区SAN中选取的综合性能相对较好的节点，负责本区副本目录索引、副本目录区间索引以及区间路由信息的管理与维护。DAN名要求全局唯一，各DAN间关系对等。
2 OoSRL定义及描述
现有副本定位（Replica Location, RL）算法和技术根据指定的资源逻辑名(Resource Logical Name, RLN)找到一个或多个与其对应的副本物理地址(Replica Physical Address, RPA)。这对大多具有QoS需求的应用 (如：多媒体数据流、IP电话、应急系统等网络应用通常对带宽、抖动、延迟、包丢失率和可用性等具有多种不同的QoS需求) 来说，因不曾考虑找到的RPA所在节点能否满足特定的QoS需求，不可避免存在着目标节点对特定应用服务的QoS无保障风险。
为了弥补现有RL的不足，我们定义MQoSRL如下：
定义1 MQoSRL：即基于多维度QoS(Multidimensional QoS, MQoS)约束的副本定位，指根据网络上可利用资源和RSN的综合性能共同确定RLN的一个或多个能满足特定应用多维度QoS 需求的RPA全过程。
在此定义下，MQoSRL不仅要求快速定位到指定RLN的RPA，而且要求定位到的目标节点RSN能满足特定应用的MQoS需求。因此，MQoSRL需要有定位过程本身的延迟约束和特定应用的MQoS约束共同作为目标RSN的定位标准，前者用于确保副本定位效率，后者用于保障目标节点面向特定应用的服务质量。当不满足前者时副本定位失败，只满足前者时需要目标节点重定位，满足前者而不满足后者时副本定位结果为空。从这个角度来讲，RL是MQoSRL中QoS约束数量退化为0时的特殊情况。
为了将MQoSRL一般化，下面推导其形式化描述。
一般地，我们把覆盖网表示为一个二元组G = ( V, E)，其中，V = { v1 , v2 ,…, v n}是由RSN或SAN或DAN构成的节点集，E = { e1,e2, …,em }是网络节点间覆盖链路构成的边集。
这样，MQoSRL定位标准就转化为覆盖路径延迟约束和目标节点综合QoS约束。
对于节点vi 到vj之间的一条覆盖路径p( vi, vj)，由延迟特性可得副本定位延迟dp(delay of path)计算公式如下：
(1)
由于LSEIS中节点参与了数据转发，故节点vm和vm+1间的覆盖链路延迟，包括传输延迟和每跳产生的上游节点输出延迟和下游节点输入延迟。当弱化节点及链路间区别后可用跳步(Hop)等价计算dp，即dp=Hop，且有：Hop初值为0，每增加一跳Hop=Hop+1。
目标节点综合QoS约束主要包括目标节点的QoS约束和副本定位请求节点到目标节点间物理路径的QoS约束。目标节点的QoS约束指特定应用对目标节点的请求平均响应时间、不同业务类型的比例、接入带宽、吞吐量、可用性等QoS规约，物理路径的QoS约束指特定应用对物理路径的带宽、时延、时延抖动、可靠性、可用性等QoS规约。因物理路径与覆盖路径可能存在较大差异，因此，无法用覆盖路径延迟简单代替物理路径延迟计算，路径的选择由网络层路由实现；而节点的QoS值可由副本目录管理节点定期检测获取。因此，这里用目标节点的QoS度量值代表其综合QoS。
假设每个应用都给定了一个必要的k(k≥0)维QoS约束度量(metric)及权重(weight)集MW={(m1,w1),(m2,w2),…,(mk,wk)}，且有：
(1) ；
(2) 每个mi都有一个最大值max(mi)和最小值min(mi)。
将mi中表示最低质量保障效果的值记为参考值ref(mi)，而另一值记为最优值opt(mi)。例如：对于响应时间有ref(mi)=max(mi)和opt(mi)=min(mi)，而对于带宽却是ref(mi)= min(mi)和opt(mi)= max(mi)。
由以上分析可得MQoSRL形式化定义如下：
(2)
(3)
定义2 MQoSRL就是要根据RLN找到满足如下多维度QoS约束的一个或多个副本存储节点：

其中，TTL(Time to Live)为副本定位的最大跳步限制，为定期检测到的节点相关MQoS度量值。
当MQoSRL定位到多个目标节点时还需从中选取综合QoS最佳者。由于能有效描述节点在mi度量上的QoS保障程度(分析见5.1)，所以，在满足(2)、(3)的情况下，多个节点综合QoS保障程度可由下式度量和比较：
(4)
3 区间路由表结构及路由算法
由于LSEIS中各DAN为对等关系，故选取常规的DHT方法可将副本区间索引信息在DAN间均匀分布并通过应用层路由逆向实现区间副本索引信息定位。
首先，将所有RLN和DAN哈希映射生成m位标识符。m要求足够长以保证两个RLN或DAN哈希映射到同一个标识符上的概率尽量小，一般选用SHA-1、MD5 等哈希算法。
D56
D20
D11
D3
D34
D1
R1
R2
R3
R9
R18
R10
R55
R28
R31
R56
图2 RLN与DAN哈希映射关系示意图
R64
其次，把所有DAN按照标识符Dd从小到大顺序排列在如图2 所示的一个单循环逻辑链上，并规定RLN-DAN映射规则为：哈希映射标识为Rr的RLN区间定位信息(RLN,DAN)存储到等于Rr (如：R1,R3,R56)或者链上大于Rr且离Rr最近(如：R2,R9,R10,R18等) 的Dd对应DAN节点上，或者存储在链上小于Rr且后继节点标识小于本节点(如：R64)的Dd对应的后继节点上。
在单循环路由表结构和RLN-DAN映射规则下，每个DAN只需维护其直接后继节点路由信息(DAN, Dd)，节点加入和退出只需修改其直接前驱路由表，RLN的查找也只需顺链推进，实现非常简单。但是，在DAN数目为n的系统中，节点查找、加入和退出维护的最坏时间复杂度为高达O(n)。因此，当n较大时需通过改造链表结构为B+树、构造区代理节点为超立方体对等结构等方法改进。因篇幅有限，路由表的维护以及路由性能优化等问题此处都不做讨论。
基于上述路由表结构和映射规则，任何一个标识为Dd，直接后继标识为的DAN收到标识为Rr的RLN区间索引信息定位请求时，都可通过如下路由算法找到存储该信息的DAN。
算法1 区间路由算法
(1) 比较Rr和Dd，若Rr= Dd时，返回本节点，转(5)；
(2) 若Dd＜Rr≤，返回其直接后继节点，转(5)；
(3) 若Rr＞Dd＞，返回其直接后继节点，转(5)；
(4) 进行下一跳匹配，令Hop=Hop+1，Dd=，转(2)；
(5) 区间路由结束。
4 MQoSRL算法实现
本节描述基于LSEIS的副本信息发布算法和MQoSRL各子算法实现。
4.1副本信息发布
每个副本生成后由所在RSN向本站SAN进行副本发布生成站内RLN目录信息，然后由本站SAN向本区DAN发布生成区内RLN目录索引信息，最后由本区DAN在区间发布生成区间RLN目录索引信息，算法如下：
算法2 副本发布算法
Step1：副本生成节点RSN向本站SAN发布新生成副本目录信息(RLN, RPA,版本号,节点属性等)；
Step2：SAN在本站副本目录中登记相关副本目录项后向本区DAN发布RLN的区内副本目录索引信息(RLN, SAN)；
Step3：DAN在本区副本目录索引中登记相关索引项后汇聚生成区间索引信息(RLN,DAN)，若有新的(RLN, DAN)值对产生则取出其RLN进行哈希计算，根据RLN-DAN映射规则将该值对(RLA, DAN)存储到匹配的DAN节点；
Step4：副本发布结束。
4.2 MQoSRL算法
基于LSEIS拓扑模型，MQoSRL分为区内定位和区间定位，区内又包含站内定位。定位过程总是按站内→区内→区间→区内→站内的顺序推进，在找到一个满足MQoS约束的节点或定位失败时终止。
4.2.1 站内副本定位
站内副本定位包括站内节点RSN直接向SAN发起副本定位请求和SAN接收到本区DAN副本定位请求两种情况，需要分别处理，算法如下：
算法3 站内副本定位
Step1：站内副本定位发起节点Nini(RSN或DAN)向本站SAN发起副本定位信息LocR(RLN,Nini)；
Step2：SAN查询本地副本目录，若存在LocR(RLN,Nini)中的RLN，则在找不到满足式(3)的RSN时转Step4；
Step3：根据公式(4)计算各RSN节点并返回至Nini，Nini取本站最优QoS值=max()及其对应节点IP返回Nini转Step6；
Step4：令Hop=Hop+1；
Step5：当Hop=TTL时定位失败，将定位结果返回Nini，否则在Nini为RSN时启动本区的区内副本定位后站内副本定位结束；
Step6：当Nini为RSN时副本定位结束，当Nini为DAN时站内副本定位结束。
4.2.2 区内副本定位
DAN在接收到本区SAN或其他区DAN的定位请求信息LocR(RLN,Nini)时启动区内副本定位，算法如下：
算法4 区内副本定位
Step1：收到LocR(RLN,Nini)的DAN查询本区副本目录索引，若不存在LocR(RLN, Nini)中的RLN则返回空值至Nini，转Step7；
Step2：组播LocR(RLN,本区DAN)定位信息到本区存在RLN的所有SAN；
Step3：收到LocR(RLN,本区DAN)的SAN启动站内定位算法；
Step4：DAN收集各SAN定位结果，根据公式(4)计算并取本区最优QoS值=max()对应节点IP返回Nini，转Step7；
Step5：令Hop=Hop+1；
Step6：当Hop=TTL时副本定位失败，将定位结果返回Nini后副本定位结束；
Step7：当Nini为SAN且定位结果为空时启动区间定位算法；
Step8：本区副本定位结束。
4.2.3 区间副本定位
区间副本定位由某DAN发起，定位目标是定位请求信息LocR(RLN,Nini)中RLN对应区间副本索引信息(RLN,DAN)的存储节点，算法如下：
算法5 区间副本定位
Step1：收到LocR(RLN, Nini)的DAN取出RLN进行哈希映射得标识符Rr并启动区间路由算法；
Step2：若找到区间目录索引存储节点DAN，则由该DAN查找区间索引信息获取目标DAN并返回Nini后转Step5；
Step3：令Hop=Hop+1；
Step4：当Hop=TTL时副本定位失败，将定位结果返回Nini后副本定位结束，否则转Step2；
Step5：Nini组播LocR(RLN, Nini)到各目标DAN；
Step6：各目标DAN启动本区区内副本定位算法；
Step7：区间定位结束。
5 性能分析与实例
本节主要对上文中提出的算法及策略进行性能分析，同时给出一个系统实例。
5.1 性能分析
基于LSEIS的MQoSRL具有高效、有效和负载均衡等特性，分析如下：
(1) 定位过程高效性。由于LSEIS的拓扑结构基于物理网络进行了虚拟区域划分，结合系统中多副本存储策略可有效保障分布式环境下数据资源访问的小世界特性[7](即资源访问的高度局部聚类特性)，这种特性使得大量副本定位结果在副本定位发起节点所在站或区产生，只有当副本不在本区或虽然本区存在目标副本但目标节点不能满足应用的MQoS需求时才进行区间路由定位。因此，MQoSRL具有较小的总体平均定位延迟，定位效率虽然可能比同一模型下的RL低但明显高于未进行区域划分的系统。
(2) 定位结果有效性。定位结果是否有效依赖于MQoSRL的定位标准。在两个定位标准中，式(2)对副本定位路径长度约束显然有效，因此，这里仅对式(3)的有效性进行说明。
若令式(3)中=，则有：
==
=
=，
令QoS参考值和最优值间步长≠0，则有：=。由此可知，可描述与的接近程度，并且与有如图3所示的线性关系。
(2)

O

1

O

1

图3 与间的线性关系示意图
(1)

根据式(3)，只有在或时有效，如图3中实线段所示，即用的大小描述RSN节点面向该维度QoS约束的保障程度是有效的。
(3) 定位计算负载均衡性。副本区内定位负载与用户操作频度和副本分布相关，而区间定位负载则与定位算法相关。本方法中使用的区间定位借助应用层路由实现，由区间路由算法可知，各副本的区间索引信息通过RLN-DAN映射规则存储在匹配的DAN节点上，而SHA-1或MD5等哈希函数本身的哈希均衡性可将所有RLN区间索引信息均匀分布于各DAN节点。因此，区间定位过程中每个DAN被定位访问的概率相当，即区间定位算法能有效保障区间副本定位计算在各DAN间的负载平衡。
另外，基于LSEIS的MQoSRL还具有较高的可靠性、可用性和可扩展性等，此处不一一分析。
5.2 LSEIS系统实例
图4 MQoSRL中区间索引信息分布情况
四川省某大型企业基于LSEIS模型构建覆盖网络后被分为19个区，每个区内站数从1到7不等，每个站内服务器也从1到5不等，客户机若干；服务器软件平台是一套基于Linux开发的文件系统和基于Mysql开发的数据库系统，系统具备单一映像功能，面向各种应用提供若干类似MQoSRL的访问接口；共享资源存储在服务器上并按该系统资源存储策略动态调整副本数及分布地点。
通过对某区三组分别800、1000和1500条本区间索引信息跟踪统计得到它们在各DAN的实际分布情况如图4所示，结果显示这三组数据在19个DAN的存储总数大致趋于平衡。
图5 MQoSRL与RL平均定位延迟比较
我们还通过对查询事务个数分别为100、200、300和400的四组应用进行QoS参数个数配置，比对了基于MQoSRL和RL的平均定位延迟和系统平均响应时间，结果如图5和图6。容易看出，MQoSRL与RL相比，其平均定位延迟稍大，但系统平均响应时间却提高明显。
图6 系统平均响应时间比较

6 结语和进一步工作
基于多维度QoS约束的副本定位方法MQoSRL针对现有副本定位中目标节点服务质量(QoS)无保障风险提出。该方法基于区域化大规模企业信息系统区域内分层、区域间对等的覆盖网拓扑结构，利用分布式环境下资源访问的小世界特性使大量副本定位在本区域完成从而有效降低了定位延迟；以满足特定应用的多维度QoS规约作为副本定位标准有效保障了目标节点的高服务质量。该方法在大规模企业信息系统的副本定位中发挥了重要作用，降低了系统平均响应时间，达到了副本定位效率高、目标节点服务质量有保障的目的，应用效果良好。
随着大规模企业信息化进程的不断推进，基于LSEIS共享的各种资源将会越来越多，由此造成的副本目录及其索引信息膨胀势必影响到MQoSRL的定位效率。因此，在下一步工作中，我们将研究站内副本目录及其在区内和区间索引信息的压缩方法以期进一步提高副本定位的时空效率。
参考文献
[1] XU Zhaomin, CAI Ming, DONG Jinxiang. Integrated CAPP system based on service-oriented middleware [J]. Computer Integrated Manufacturing Systems, 2009, 15(5): p.973-981. (in Chinese). [徐照旻,蔡铭,董金祥. 基于面向服务中间件的集成化CAPP系统研究[J]. 计算机集成制造系统, 2009, 15(5): 973-981.]
[2] L V Zhi. Grid-based distributed manufacturing integrated architecture framework [J]. Computer Integrated Manufacturing Systems, 2008,14(8):1586-1595.(in Chinese)[吕志. 网格化分布式制造一体化体系结构框架[J]. 计算机集成制造系统, 2008, 14(8): 1586-1595.]
[3] REN Wu-ling, TANG Renzhong, GUO Shanghong, et al. I Component2based enterprise applications integration techniques [J]. Journal of Zhejiang University (Engineering Science), 2007,41(8): p.1283-1287.(in Chinese). [任午令,唐任仲,郭尚鸿,等. 基于构件的企业应用集成技术[J]. 浙江大学学报(工学版), 2007,41(8): 1283-1287.]
[4] CHERVENAK A, SCHULER R, RIPEANU M, et a1. The Globus Replica Location Service: Design and Experience [J]. IEEE Transactions on Parallel and Distributed Systems, 2009,20(9): 1260-1272
[5] CHERVENAK A, CAI M, FRANK M. Applying Peer-to-Peer Technology to Grid Replica Location Services [J]. Journal of Grid Computing, 2006, 4(1): 49-69.
[6] JIANG Hai, LI Jun, LI Zhongcheng. Hybrid Content Distribution Network and Its Performance Model ing [J]. Chinese journal of computers, 2009, 32(3): 473-482. (in Chinese). [蒋海, 李军, 李忠诚.混合内容分发网络及其性能分析模型[J]. 计算机学报, 2009, 32(3): 473-482. ]
[7] WATTS D, STROGATZ S. Collective dynamics of ‘small-world’ networks. Nature, 1998, 393: 440~442.
- 10 -