云计算环境下基于排队论的数字图书馆性能优化

陈丽萍，郭力争，赵曙光

（东华大学a.图书馆；b.信息科学与技术学院，上海 201620）

云计算环境下基于排队论的数字图书馆性能优化

陈丽萍a，郭力争b，赵曙光b

（东华大学a.图书馆；b.信息科学与技术学院，上海 201620）

云计算技术的成功发展及其应用，为用户方便地访问基于该技术的数字图书馆提供了技术保障.但由于该类数字图书馆具有海量资源且用户访问数量庞大、需求复杂，保障其用户服务质量是极具挑战性的问题.为了优化数字图书馆的用户服务性能，通过对服务性能参数的分析，提出了基于排队论的综合性能优化模型和优化方法.仿真结果表明，相对于经典的最小服务优先排队论模型和先到先服务模型，该模型和方法能有效提高服务用户数量，减少等待时间和队列长度.

数字图书馆；云计算；性能优化；排队论

随着通信、计算机及软件技术的发展，特别是云计算技术的出现，效用计算正在从梦想变为现实［1］.云计算技术将图书文献资源的数字化进程向前推进了一大步，使得数字图书馆可以实现跨越Web的信息发布和集成应用.世界各地的图书馆都在利用云计算技术建设数字图书馆（系统平台），以显著降低数字图书的管理及维护成本，丰富系统资源，提高效率.例如，美国俄亥俄州都柏林市的联机计算机图书馆中心（Online Computer Library Center，OCLC）现已发展成为世界上最大的非营利性图书馆组织联盟［2］，包括72 000个成员馆，涉及171个国家，语言和方言数超过470种，拥有178 954 122条书目信息.OCLC为全球用户提供了“WorldCat.org”和“WorldCat Local”两种加入方式，并将其作为云计算的先导方式［3］.用户可以通过移动电话访问WorldCat，并且4G的无线网络下载速度是原先OCLC网络速度的2 500倍［4］.2012年3月，美国佩珀代因大学将其图书馆管理系统迁移到了云服务系统上，整个过程比预期顺利且节省了大量时间和资金［5］.新西兰国家图书馆借助OCLC改善了馆际借阅且减少成本支出［6］.迄今全球超过240个图书馆已经选择了WorldShare Management Services（WMS）系统，超过150个图书馆正在使用 WMS提供的服务［7］.

同时，由于数字图书馆的用户可以通过多种途径访问和使用云数字资源，用户剧增给云数字图书馆的系统性能优化带来了新的挑战.所谓系统性能即服务质量QoS（quality of service），主要包括响应时间、任务阻塞率、服务提供率、用户等待时间、用户的服务时间、等待服务的队列长度等［8］.从理论上讲，系统性能参数优化可利用排队论加以解决［9］.但由于数字图书馆包含大量服务器且其用户访问具有不可预知性，需要动态自适应地调整服务器参数以提供用户所需的服务资源.而传统的排列论方法对此类情况研究较少，且云计算研究界也较少涉及云计算性能的研究.文献［10］提出了一种云计算环境下区分服务的资源调度方法，通过为不同用户的不同服务请求，建立非抢占式优先权的M／G／1排队模型，可获得最优的结果.文献［11］假设用户到达时间和服务时间服从指数分布且将云中心模式看作经典的开放式网络，从而得到了响应时间分布并用其实现顾客服务能力（数量）最大化.文献［12］使用线性预测方法，从资源利用日志得到有用信息，利用M／M／1排队论预测方法，对响应时间和能源消耗进行优化.文献［13］使用排队模型，研究了单级、多级服务情况下的资源分配问题，以减少平均响应时间或在每种情况下最小化资源成本.总之，已有相关研究大多侧重于单个服务质量参数的优化，难以整体提升数字图书馆的服务性能.本文为优化数字图书馆的综合服务性能，将其服务中心作为M／M／m排队系统来研究，利用M／M／m排队理论模型推导出各参数方程，进而提出综合优化方法.

1 优化模型

图1 数字图书馆服务请求实例Fig.1 An example of service requesting for digital library

为了评估和优化云数字图书馆的服务性能，首先推导出各个性能参数的表达式.为便于推导和理解，先定义和说明一些有关概念：Ls为系统的队列长度，表示系统内用户数（包括排队等候的用户数和正在接受服务的用户数）；Lq为排队等候服务的队列长度；Ns为正在接受服务的队列长度；Ws为顾客在系统中逗留的时间；Wq为用户排队等待服务的时间；τ为用户的服务时间.根据以上定义和前面的分析，可以得到如下结论：

为了获得E［Lq］，考虑两个互斥事件（其中q＝Ls）：q≥m和q＜m，于是有

另外，由于E［Lq｜q＜m］＝0，且P（q≥m）＝Cm（ρ），于是可得

2 优化策略

在云服务数字图书馆排队系统的所有参数中，Lq能充分反映系统的整体性能，因为正在接受服务的用户数量由云服务中心服务器的数量决定，而Lq又由服务器的服务性能所决定.为了充分优化整个系统性能，满足用户的服务器性能体验且保持负载平衡，本文设计了基于排队论的系统任务调度和性能优化模型，如图2所示.其工作流程：所有用户的服务请求首先进入服务队列，任务调度器根据优化函数的输出结果，指派最合适的服务器为用户提供服务.优化函数的输入参数：服务器的利用率、服务器服务时间的均值和排队等待服务的队列长度.假设每个服务器被选中的概率为p i，其服务时间为ti，则服务器服务时间的均值E［t］为

优化函数f为

其中：α，β，χ为系统参数，可以根据具体系统通过学习获得；E［t］，Lq，U i分别为每个服务器的服务时间均值、排队等候服务的队列长度和服务器的利用率.在式（9）中，利用率U i＝λi／μi.优化函数根据输入参数的值计算出函数值，然后根据函数值对服务器进行升序排列，调度器选择具有最小函数值的服务器为用户提供服务.

图2 基于排队论的任务调度和性能优化模型Fig.2 Performance optimizing and task scheduling model based on queuing theory

3 实验及分析

3.1 实验环境

本文使用Matlab离散事件仿真工具SimEvents测试各种优化策略对数字图书馆数据中心性能的改善效果.仿真所用的硬件：CPU为AMD Phenom［tm］Ⅱ X4 B95 3.0 GHz，内存为2G byte，软件为 Windows XP和Matlab R2009b.根据亚马逊标准的按需服务实例类型［14］，服务器分为4类，服务速率为｛μ1＝3.00，μ2＝2.40，μ3＝2.00，μ4＝1.71｝，每个服务器的服务时间服从负指数分布，用户的服务请求到达的间隔也服从负指数分布，服务请求的到达率为｛λ1＝30，λ2＝20，λ3＝15，λ4＝12｝；整个的仿真时间为1 d即1 440 min；服务器的数量为｛4，20，40，48，52，60，80｝.

3.2 仿真结果及分析

为了检验上述优化模型和方法——综合优先级队列（SO）方法，以经典的短服务优先队列（SSF）方法、先到先服务（FIFO）方法为比较对象，进行了多组仿真实验.

对于服务器个数为｛4，20，40，48，52，60，80｝的情况，分别测试每个用户的平均等待时间，测试结果如表1所示.从表1可以看出，当服务器数量为4和20时，SSF方法的平均等待时间最短，但当服务器数量超过40时，SO方法的平均等待时间均为最短.分析其原因，当服务数量较少时，很多用户不得不在队列中排队等待服务，而SSF方法优先服务需时较短的用户，因而能在相同时间内服务更多的用户，相应地总的用户等待时间就会减少，但是这样对于服务需时较长的用户不够公平，他们可能一直得不到服务.当服务器数量足够多时，SO方法因为能综合优化服务器的利用率、平均等待时间和平均队列长度，所以总体上的平均等待时间优于其他两种方法.与SO方法相比，SSF方法和FIFO方法不能充分利用服务器性能，而是按短服务优先或先来先服务的原则选择用户和分配服务器，因此，一些服务性能好和空闲的服务器不能得到充分利用，一些服务性能差的服务器则很可能超载，从而导致平均等待时间增加、服务性能下降.

表1 平均等待时间Table 1 Average waiting time min

在相应情况下上述3种方法的平均队列长度和平均用户服务数分别如表2和3所示.从表2和3可以看出，尽管在服务器数量较少时，SO方法的平均等待时间指标劣于SSF方法，但SO方法的平均队列长度、服务用户数指标均优于另外两种方法.其原因是SO方法能优化服务器的利用率，使利用率低的服务器和性能好的服务器优先被指派给用户，从而能充分利用所有服务器的性能，服务更多的用户，其平均队列长度因而较短.

表2 平均队列长度Table 2 Average queue length

表3 服务用户数Table 3 Number of users served

4 结 语

本文研究了云计算环境下数字图书馆的性能优化问题，提出了基于排队论的云计算数字图书馆性能优化模型和优化方法.通过仿真实验证明，该模型和方法能有效地减少用户排队等待时间，服务更多用户请求，因而对于相关的理论研究和实际应用均具有一定参考价值.未来计划将数字图书馆服务中心的能耗与性能同时作为主要优化指标，研究实现其高性能、低能耗的有效方法.

［1］ARMBRUST M，FOX A，GRIFFITH R，et al.A view of cloud computing［J］.Communications of the ACM，2010，53（4）：50-58.

［2］周津慧，初景利.分报告七：OCLC考察报告［J］.数字图书馆论坛，2011（1）：61-70.

［3］OCLC announces strategy to move library management services to Web scale ［EB／OL］.（2009-04-23）［2014-01-10］.http：／／www.oclc.org／news／releases／200927.htm.

［4］WorldCat turns 40 ［EB／OL］.（2011-08-26）［2014-01-10］.http：／／www.oclc.org／en-US／news／releases／2011／201149.html.

［5］DULA M， JACOBSEN L， FERGUSON T， et al.Implementing a new cloud computing library mana gement service：A symbiotic approach［J］.Computers in Libraries，2012，32（1）：6-11.

［6］National Library of New Zealand reduces costs by moving Te Puna Interloan service to OCLC ［EB／OL］.（2013-10-18）［2014-01-10］.https：／／www.oclc.org／en-US／news／releases／2013／201345dublin.html.

［7］Lethbridge College，Tyndale University and University of New Brunswick now using OCLC WorldShare Management ［EB／OL］.（2013-10-24）［2014-01-10］.https：／／www.oclc.org／en-US／news／releases／2013／201346dublin.html.

［8］WANG L，VON LASZEWSKI G，YOUNGE A，et al.Cloud computing： A perspective study ［J］. New Generation Computing，2010，28（2）：137-146.

［9］KLEINROCK L.Queueing systems volume 1：Theory［M］.New York：Wiley-Interscience，1975.

［10］LI L.An optimistic differentiated service job scheduling system for cloud computing service users and providers ［C］／／Multimedia and Ubiquitous Engineering， 2009. Third International Conference on MUE，2009：295-299.

［11］XIONG K，PERROS H.Service performance and analysis in cloud computing［C］／／2009 World Conference on Services-I，2009：693-700.

［12］SHI Y，JIANG X，YE K.An energy-efficient scheme for cloud resource provisioning based on CloudSim ［C］／／2011 IEEE International Conference on Cluster Computing，2011，595-599.

［13］NAN X，HE Y，GUAN L.Optimal resource allocation for multimedia cloud based on queuing model［C］／／IEEE 13th International Workshop on Multimedia Signal Processing，2011：1-6.

［14］Amazon EC2 Pricing［EB／OL］.（2013-11-17）［2014-01-10］.http：／／aws.amazon.com／ec2／pricing／.

Digital Library Performance Optimization Based on Queuing Theory in Cloud Computing

CHENLi-pinga，GUOLi-zhengb，ZHAOShu-guangb

（a.Library；b.College of Information Science and Technology，Donghua University，Shanghai 201620，China）

Successful development of cloud computing techniques and their applications provide technical supports for users to access digital library using cloud computing resource.But there are massive resources along with numerous and complicated user requirements in such digital libraries，it is a challenging problem to ensure service quality for users.In order to optimize the performance of user service，an overall performance optimizing model and a consequent method are proposed based on queuing theory and analysis of service performance parameters.Simulation results show that，compared to the classic model of a minimum service priority queuing theory and the first come first serve model，the model and method proposed can effectively improve user service capacity and obviously reduce waiting time and queue length.

digital library；cloud computing；performance optimization；queuing theory

G 250

A

2014-02-19

国家自然科学基金资助项目（61271114）

陈丽萍（1965—），女，浙江台州人，工程师，硕士，研究方向为计算机应用和软件工程.E-mail：chen＿lp＠dhu.edu.cn

1671-0444（2014）03-0318-04