基于灰色预测模型的优先级队列缓存管理策略

唐定勇,林正红,江 虹

(1.西南交通大学CAD工程中心,成都610031;2.西南科技大学信息工程学院,四川绵阳621010)

基于灰色预测模型的优先级队列缓存管理策略

唐定勇1,林正红2,江 虹2

(1.西南交通大学CAD工程中心,成都610031;2.西南科技大学信息工程学院,四川绵阳621010)

为解决企业服务总线(ESB)集成平台中的服务队列管理问题,在考虑队列优先级因素的基础上,提出一种优先级消息服务队列缓存管理策略。将不同优先级的业务数据封装为消息服务放入不同队列中,按照消息优先级顺序对其进行服务管理,在下一次业务消息到达前,使用灰色预测模型实时预测优先级队列的缓存分配情况,使得队列缓存分配更合理。实验结果表明,该策略能保障ESB集成平台中高优先级业务和低优先级业务的正常运行,并降低高优先级业务的平均等待时间、平均停留时间及消息队列拥塞的风险。

软件企业服务总线;优先级;缓存管理;服务调度;灰色预测;稳定性分析

1 概述

随着集团企业信息集成与共享需求的不断发展,其纵横各级应用系统间的数据交换需求日益增多。同时,信息资源的共享应用呈现出多样、复杂与海量等特性,这迫切需要对业务数据进行高效可靠的处理。面向服务架构(Service Oriented Architecture, SOA)［1］是一种松耦合的粗粒度服务架构,它屏蔽了底层通信协议,服务间通过标准接口进行通信。企业服务总线(Enterprise Service Bus,ESB)［2］平台的目标是为企业提供一种能够屏蔽各类应用系统复杂数据结构的共享数据应用服务,做到集团应用系统间、集团和二级单位间、二级单位间的业务协同,实现分布式系统间信息的融合与传输。基于SOA构建的ESB集成平台［3］能完成应用系统间的互操作,适用于即时资源的共享和业务系统的协同互操作,满足集团各级间的信息集成与共享需求,而缓存调度是该平台下的关键技术。本文在基于SOA的ESB集成平台上,提出一种基于灰色预测模型的优先级队列缓存管理策略来解决动态环境下的存储管理问题,其中包括降低冲突和处理延迟,并保障服务队列的公平性。

2 队列缓存管理

ESB是一个能实现互连、通信、转换、可移植性且支持SOA的基础软件架构［3］。用户可在ESB端点上对所需服务类型进行分类、调用和编排等配置。服务一般被分为多个等级,不同等级的消息被放入不同队列中等待服务。采用ESB中间件的SOA架构如图1所示。

图1 采用ESB中间件的SOA架构

为使ESB平台中服务队列能高效可靠地工作,如何对缓存进行有效管理是缓存调度机制必须要解决的关键问题。

存储管理的重点是如何降低访问冲突与延迟。典型的存储管理技术主要包含先进先出(First-in First-out,FIFO)［4］、访问回退(backoff)［5］、缓存代理等方法［6］。传统ESB系统的服务调度通常采用基于FIFO的方法,如文献［4］提出一种基于优先级队列的FIFO缓存管理机制,该机制能为高优先级消息提供更好的服务质量保证,但其优先级队列的缓存大小是固定的,不能适用于消息优先级实时变化的服务队列管理,使其在集团级大规模应用中受到较大限制。文献［5］提出一种动态回退法来解决缓存竞争管理,其要点是在冲突后控制重起间隔时间,本质上属于事后处理。文献［6］研究基于代理的缓存管理技术来降低服务响应时间,使用FIFO和后进先出(Last-in First-out)2种并行队列结构进行队列缓冲区的管理。文献［6-7］需增加额外存储单元来保证性能,不适用于优先级队列的缓存资源管理。文献［8］给出一种可分析队列中每个元素权值相同时排队系统队长分布特性的方法,但该方法仅从队长特性来研究排队系统性能,并未对队长进行优化,也未区分队列中每个元素的权值。文献［9］提出一种基于动态带宽分配的ESB模型,系统根据当前流量动态调整分配给各业务的带宽,该策略能保证高优先级业务的带宽需求,但这种机制有一定滞后性,不适用于动态性较强的应用环境。

从以上分析可看出,在ESB系统的缓存管理研究中,重点是如何降低冲突和处理延迟,目前典型的处理方法要么是事后型,处理有滞后性,要么需要额外资源。与这类处理思路不同,本文采用预测方法来优化解决该问题,提出一种基于灰色预测［10］的优先级队列缓存策略来解决动态环境下的存储管理。该策略先将业务消息按不同优先级进行划分,再将其放入对应优先级队列中,当与优先级队列相对应的服务通道空闲时,业务消息才能接收服务。同时,本文使用灰色预测方法根据历史优先级队列的缓存大小预测未来优先级队列的缓存大小,以达到合理利用ESB集成平台中的队列缓存资源。另外,本文对消息序列进行交叉服务,防止高优先级消息泛洪使得低优先级消息得不到服务而出现“饿死”的现象,以保证服务尽可能公平。

3 基于灰色预测的优先级队列缓存管理

本文提出的基于灰色预测的优先级队列缓存管理策略主要针对缓存管理和服务调度两方面对优先级队列管理进行改进,其整体框架如图2所示。

图2 优先级队列缓存管理策略示意图

3.1 优先级队列缓存管理策略

在传统队列缓存管理中,为优先级队列分配的缓存一般为固定大小,这使得队列资源得不到有效利用,以致出现高优先级队列缓存有剩余,低优先级队列仍得不到缓存资源的情况。这种不合理的缓存管理机制将不能改善高优先级和低优先级队列中消息的平均等待时间和平均停留时间等指标。

本文提出的基于灰色预测模型的优先级队列缓存管理策略可有效解决该问题。根据优先级队列缓存大小的历史信息预测未来优先级队列的缓存大小,并为其动态分配缓冲区,因此,不会造成低优先级队列需要的缓存资源一直被高优先级队列抢占而逐渐减少的情况,从而保证了公平性。该策略在充分利用缓存资源的同时,不仅能保证高优先级消息的优先性,还能兼顾低优先级消息的服务。

3.2 优先级队列调度管理策略

由于ESB端点是开放的,因此可将ESB端点上的业务消息分为应急消息和普通消息。在实际应用中,可将控制消息和一般业务消息分别视为应急消息和普通消息。因此,本文为ESB端点上的业务消息设置2个不同的优先级缓存队列,分别为应急队列(高优先级队列)和普通队列(低优先级队列)。应急队列用于存放应急消息,普通队列存放普通消息,其中,应急队列和普通队列缓存由3.1节所述机制分配。如图2所示,在不同业务消息到达ESB端点并进入优先级队列前,先对其分类,然后在缓存调度中区别存储应急和普通消息。当服务通道空闲时,预测的应急队列缓存中的应急请求会优先得到处理,等到应急队列中的请求被处理完成后,服务总线才处理普通队列中的服务请求。若需服务的消息过多,已超过预测的缓存分配长度,则系统对空余可用缓存进行动态利用,系统优先对高优先级的消息进行存储。此时,调度服务为满足公平性,即为防止高优先级队列消息泛洪,使普通队列得不到服务而出现“饿死”现象,系统首先服务预测缓存中的应急消息,然后服务一部分普通消息(该服务比例为预测应急消息缓存长度与实际应急消息长度的百分比),最后服务剩余应急队列和普通队列。

3.3 优先级队列缓存管理策略仿真

ESB系统作为企业级的应用集成平台,需对服务请求(即业务消息)进行调度管理［11］,以保证该系统具有高度的灵活性和可靠性,从而满足企业级应用中高度并发的访问请求。

由于系统中每次到达的业务消息优先级是随机的,因此应急队列和普通队列中的消息数量会呈现动态变化趋势,这将给队列缓存资源的分配带来挑战。在传统缓存管理系统中,缓存分配大多凭经验完成,没有充分利用业务消息到达时所蕴藏的信息,存在资源浪费与效率低下的问题。为使系统中历史队列缓存大小能给未来的队列缓存大小分配提供依据,本文利用灰色预测模型对每次大量业务消息到达时队列缓存值应分配的大小进行预测,使队列缓冲区资源得到合理利用。

灰色预测技术是通过对原始数据的处理和灰色模型的建立,发现并掌握系统发展规律,对系统的未来状态做出科学定量预测的一门技术［12］。本文设灰色预测GM(1,1)模型［12］输入的原始数据列为Xo={Qs(1),Qs(2),…,Qs(t)},s∈{m,n},t∈N+,其中,Qm(t)和Qn(t)分别为第t阶段的普通队列和应急队列的缓存长度,通过对{Qm(t)}和{Qn(t)}进行预测,得到Qm(t+1)和Qn(t+1),根据预测值为t+1阶段的序列分配缓存长度,以实现对缓存的优化利用。

为使序列成为有规律的时间序列数据,对其作一次累加生成运算,即令,则新生成数列为X1={X1(1),X1(2),…,X1(n)}。判断X1是否满足GM(1,1)预测建模要求,即X1的覆盖是否属于区间［exp{-1/(n+1)},exp{1/(n+1)}］。本文将X∧(t+1)定义为t+1阶段的预测值,即下一时刻应为队列分配的缓存大小,其形式如下:

其中,a和u分别为灰色预测模型中的发展系数和灰作用量,为得到它们的值,本文对原始数列定义以下中间量:

其中,Xz(t)为背景值序列,定义为Xz(t)=(X1(t)+ X1(t-1))/2。a和u的推算公式如下:

根据以上推导,可得最终的灰色预测输出如式(4)所示:

综上所述,基于灰色预测的优先级队列缓存管理策略的一次仿真过程如图3所示。当应急消息和普通消息分别进入应急队列和普通队列后,首先利用前t时刻的数据序列长度向量(普通队列和应急队列的缓存长度向量分别为［Qm(i),i={1,2,…, t}］和［Qn(i),i={1,2,…,t}］),根据灰色预测机制对t+1时刻的数据序列长度进行预测(即对Qm(t+ 1)和Qn(t+1)的值进行预测),基于预测值为应急和普通队列分配对应的数据缓存空间。此时若为应急优先队列分配的缓存已经处于饱和状态,但缓存中还有未分配的空间,则应急消息将占用剩余缓存空间,以满足优先队列的服务质量。

图3 优先级队列缓存管理策略的仿真过程

当新到数据包时,根据第3.2节所述的优先级队列管理机制对其进行调度。此时若应急消息过多,即已经占用了剩余缓存空间,则首先服务预测缓存中的应急消息,然后服务一部分普通消息(该服务比例为预测应急消息缓存长度与实际应急消息长度的百分比),其次服务剩余应急队列和普通队列,避免高优先级队列泛洪。最后对每次所得的调度仿真结果进行记录,为最终结果分析提供依据,以此达到充分合理利用队列缓存资源,公平服务的目的。

3.4 队列长度预测算法稳定性分析

灰度预测GM(1,1)白化型响应式［10］如下:

其中,φ＞0。V(x1)关于时间的微分为:

将带入式(8)可得:

根据Lyapunov稳定性第二法则［13］,若a大于0,则V’(x1)半负定,即式(9)在a大于0的情况下,函数关于0解渐进稳定。

讨论关于式(9)解的稳定性,其解如下:

其中,η定义如下:

其中,N为迭代次数;xi为第i次迭代值。因此,式(12)关于解的Lyapunov指数计算如下:

式(11)可改写为σt≅σ0·exp(-a·t)。在灰色预测中,为了保证预测精度,将a限制在区间［-2/(n+1),2/(n+1)］,其中,n表示原始数据序列长度［10］。 当a∈(0,2/(n+1)］时,系统的Lyapunov指数谱η∈［-2/(n+1),0)＜0,即该灰队列长度预测算法受到的初始扰动随时间收缩,因此该算法是稳定的,且以幂为a的指数函数收敛。

4 仿真结果与分析

4.1 仿真设置

本文仿真场景基于某集团的企业服务总线系统,该系统基于SOA架构,采用东方通的ESB产品TI-ESB构建。在该集团企业服务总线的基础上,对以下2种优先级队列缓存策略进行仿真分析:(1)随机选择服务队列的缓存管理策略(简称方案1),即不对ESB端点上不同优先级的业务消息进行分类,所有消息都在一个队列中按照随机到达时间排队等待服务;(2)基于灰色预测的优先级队列和普通队列管理机制(简称方案2),即ESB端点设置应急队列和普通队列对消息进行按策略进行服务。

本文使用Matlab对上述2种队列缓存管理机制进行仿真。设ESB端点上单位时间内服务消息的达到速率服从泊松分布,消息到达时间间隔和服务时间都服从指数分布,每个消息数据包大小相同;基于灰色预测的优先级队列缓存管理策略中的应急队列和普通队列的初始缓存容量均为5 000个单元;仿真次数为100次。同时,程序将对每次仿真时队列中的消息平均个数、消息平均停留时间、消息平均等待时间、消息丢失率以及缓存利用率进行记录,然后使用每10次仿真后对记录结果所取的平均值来分析这2种缓存管理机制的性能。

4.2 结果分析

图4和图5分别为方案1和方案2中消息平均等待时间和平均停留时间对比。消息的平均等待时间和平均停留时间越短,说明消息获得服务的响应越快。如图4、图5所示,由于方案2对消息采取区分服务,即高优先级消息总是先于低优先级消息接收服务,因此应急队列中消息平均等待和停留时间均低于普通队列中消息的平均等待和停留时间。由于方案1不对消息的优先级进行划分,仅按随机设定的消息到达时间和服务时间接收服务,因此其队列中消息的平均等待和停留时间略高于应急队列中消息的平均等待和停留时间,但却略低于普通队列中消息的平均等待和停留时间。

图4 消息平均等待时间对比

图5 消息平均停留时间对比

图6 为方案1和方案2中的平均消息个数对比。在方案1中,消息并未使用优先级进行区分,所有消息都存储在一个固定队列中,前一个消息被服务后,后一个等待的消息即可接收服务,所以随机选择服务队列中的消息平均个数均大于方案2中应急或普通队列中的消息平均个数。在方案2中,根据预测的队列长度分配缓存,采用3.2节所述的优先级队列服务方式,防止优先级队列“泛洪”而使低优先级队列得不到服务的情况发生。在图6中,应急队列和普通队列的排队长度交叉变化,应急消息拥有一定的优先特性,而又不完全占用消息服务通道,比随机服务方案拥有更好的公平性。

图6 队列中平均消息个数对比

图7 为方案1和方案2中的平均消息丢失率对比。方案2使用灰色预测模型预测下一次仿真时应急队列和普通队列所需分配的缓存大小,即应急队列和普通队列的缓存大小会随着每次仿真而自适应变化。

图7 队列中消息丢失率对比

然而,方案1既不区分消息的优先级,也不为其动态分配缓存大小,所以方案1中随机选择服务队列的数据丢包率高于方案2中应急队列和普通队列的数据丢包率。在方案2中,由于应急队列中的消息总是先于普通队列中的消息,即应急队列中的消息不会出现长时间的排队等待现象。同时,空闲缓存队列更倾向于为优先级高的消息服务,所以,其数据丢包率低于普通队列的数据丢包率。从图7可看出,采用3.1节的预测缓存管理方法和3.2节的避免“泛洪”服务调度机制后,应急队列的平均丢包率低于1%,大大低于普通队列的平均丢包率,普通队列的平均丢包率比随机选择服务队列又低了约15%。

图8为方案1和方案2中的缓存利用率对比。方案1由于对服务消息固定分配缓存造成的缓存空余量过多,缓存利用率低,不足60%。在方案2中,根据灰队列长度预测算法,为下一时刻的应急队列和普通队列动态分配缓存空间,能实时反映缓存的变化,使得缓存管理更加灵活,提升了缓存利用率。该方案使得应急队列和普通队列的缓存平均利用率均达到95%以上,比方案1平均提升了30%左右。

图8 队列中缓存利用率对比

5 结束语

为解决基于SOA架构的ESB集成平台中的服务队列缓存管理问题,本文提出基于灰色预测的优先级队列缓存管理策略。该策略考虑业务消息的优先级,将不同优先级业务消息加入到不同优先级队列中,并按照业务消息的优先级先后顺序对其进行服务,不仅保证了高优先级业务的服务质量,而且降低了高优先级业务消息的平均等待时间、平均停留时间和消息队列堵塞的风险。同时,在每次有大量业务消息进入队列前,该策略都会根据灰色预测机制为各优先级队列分配合适的缓存大小,在提高优先级队列缓存利用率的同时,避免了缓存资源的浪费。

［1］Waris M,Khan S A,Fakhar M Z.Factors Effecting Service Oriented Architecture Implementation［C］// Proceedings of Science and Information Conference. Washington D.C.,USA:IEEE Press,2013:1-8.

［2］Li Gang,Xiao Jian,Li Chun,et al.A Comparative Study Between SoftSystem Bus and Enterprise Service Bus［C］//Proceedings of 2012 International Conference on Computer Science Service System.Washington D.C., USA:IEEE Press,2012:557-561.

［3］邵欢庆,康建初.企业服务总线的研究与应用［J］.计算机工程,2007,33(2):220-222.

［4］姜宏岸,王 刚.优先级队列的缓存管理机制的性能分析［J］.计算机工程与应用,2009,45(25):86-88.

［5］Seung Hun-Kim,Choi Dong-Min,Won Woo-Ro,et al. Complexity-effective Contention Management with Dynamic Backoff for Transactional Memory Systems［J］. IEEE Transactions on Computers,2013,63(7):1696-1708.

［6］李笑一.面向服务环境中的SOAP缓存代理研究及其应用［D］.重庆:重庆大学,2009.

［7］Huang Po-Kai,Chang Cheng-Shang,Cheng J,et al. Recursive Constructions of Parallel FIFO and LIFO Queueswith Switched Delay Lines［J］.IEEE Transactions on Information Theory,2007,53(5): 1778-1798.

［8］Ashour M,Lengoc T.Performance of Weighted Fair Queuing Systems with Long Range Dependent Traffic Inputs［C］//Proceedings of 2005 Canadian Conference on Electrical and Computer Engineering.Saskatoon, Canada:IEEE Press,2005:1002-1005.

［9］夏纯中,宋顺林.一种基于动态带宽分配的企业服务总线模型［J］.计算机工程,2011,37(21):1-3.

［10］刘思峰,谢乃明.灰色系统理论及其应用［M］.北京:科学出版社,2013.

［11］邝景胜.分布式企业服务总线可靠性机制的研究与实现［D］.杭州:浙江大学,2011.

［12］崔立志.灰色预测技术及其应用研究［D］.南京:南京航空航天大学,2010.

［13］Paunonen L,Zwart H.A Lyapunov Approach to Strong Stability of Semi Groups［J］.System&Control Letters, 2013,62:673-678.

编辑 陆燕菲

Buffer Management Strategy of Priority Queue Based on Gray Prediction Model

TANG Dingyong1,LIN Zhenghong2,JIANG Hong2
(1.Engineering Center of CAD,Southwest Jiaotong University,Chengdu 610031,China;
2.School of Information Engineering,Southwest University of Science and Technology,Mianyang 621010,China)

To solve the service queue management problem in the Enterprise Service Bus(ESB)integration platform, the buffer management strategy of priority message service queue is proposed.This strategy puts the different priorities business data into different queues.The Business is serviced according to the order of priority packets.Before the next packets arrive,the strategy uses gray prediction to make a real-time prediction about the priority queue’s buffer size which can be assigned,makes the queue’s buffer allocation more reasonable.Experimental results show that the proposed strategy not only can guarantee high priority and low priority traffic to run smoothly in ESB integration platform,but also can reduce the average waiting time,the average residence time for high priority traffic and the risk of message queue congestion.

software Enterprise Service Bus(ESB);priority;buffer management;service scheduling;gray prediction; stability analysis

1000-3428(2015)05-0056-06

A

TP311

10.3969/j.issn.1000-3428.2015.05.010

国家科技支撑计划基金资助项目(2012BAH20F01);四川省制造业产业链协同与信息化支撑技术重点实验室基金资助项目(2013002)。

唐定勇(1972-),男,研究员、博士研究生,主研方向:信息安全,数据挖掘;林正红,硕士研究生;江 虹,教授、博士。

2014-07-07

2014-08-02E-mail:tdy2000@126.com

中文引用格式:唐定勇,林正红,江 虹.基于灰色预测模型的优先级队列缓存管理策略［J］.计算机工程,2015, 41(5):56-61.

英文引用格式:Tang Dingyong,Lin Zhenghong,Jiang Hong.Buffer Management Strategy of Priority Queue Based on Gray Prediction Model［J］.Computer Engineering,2015,41(5):56-61.