多核Web服务器中基于分配矩阵的动态请求调度算法

尤国华 陈骏君 赵 英



多核Web服务器中基于分配矩阵的动态请求调度算法

尤国华*陈骏君 赵 英

(北京化工大学信息中心 北京 100029)

为了构建高性能的Web服务器，充分利用Web服务器中多核处理器的性能成为关键。传统的先到先服务策略没有考虑多核处理器的特点，不能充分利用多核处理器的性能。为解决此问题，该文提出一种基于分配矩阵的动态请求调度算法。该算法充分考虑了多核处理器的特点，可将同类动态请求动态分配至同一个处理器核心，提高了Web服务器处理动态请求的速度。仿真实验结果表明，采用该算法的Web服务器在自相似性、平均响应时间、丢包率等方面均优于传统的先到先服务算法。

Web服务器；多核；动态请求；调度

1引言

随着社交网络和云计算技术的发展，越来越多的数据和应用被置于服务器端，服务器的性能成为关键。而实现高性能服务器的一个关键因素就是如何充分利用多核处理器的运算能力，这是一个日益重要但尚未解决的问题[1]。传统的Web服务器，例如Apache，通常采用先到先服务(First Come First Served, FCFS) 算法[2]，即根据用户请求到达服务器的先后顺序进行处理。FCFS算法具有简单、公平的优点，也存在平均时间较长的缺点[3]。因此，Web服务器上也采用过短作业优先(Shortest-Job First, SJF)等算法。使用短作业优先算法时，服务时间短的请求比服务时间长的请求具有更高的服务优先级。因此，短作业优先算法总的平均响应时间更短。

用户请求通常分为静态请求和动态请求两种。静态请求获取服务器中已有的文件(如视频、图片等等)，动态请求向服务器请求某个处理过程，该处理过程通常是执行一段脚本程序(如JSP, PHP等)[4]。相比静态请求，脚本程序的处理过程比较复杂，由于存在一些个性化的内容，脚本程序文件不能有效地被缓存[5]。静态请求的资源瓶颈是内存、硬盘、网络带宽等，而动态请求的资源瓶颈往往是CPU。

引入多核处理器理论上可提升Web服务器处理动态请求的能力，但是以FCFS和SJF为代表的传统请求处理算法并没有考虑多核处理器的特点，依据目前操作系统的调度算法[6]，请求同一个动态内容的动态请求可能被分配至不同的处理器核心，从而导致该动态内容可能在多个处理器核心的私有缓存之间往返，即产生“乒乓”效应问题[7]，因此并不能充分利用多核处理器的运算能力。

为提升多核处理器的利用效率，许多研究者已经针对多核处理器的特性从操作系统或应用程序层面提出了相应的软件体系结构或应用框架。

文献[11]引入了一种新技术，sloopy counters，通过修改系统内核来消除影响多核扩展性的瓶颈因素，这种技术可应用于包括Web服务器在内的众多应用程序。文献[12]通过修改网络堆栈(network stack)以支持DCA(Direct Cache Access)技术，从而可将I/O与CPU的缓存直接相连。他们的实验表明DCA增强的Linux内核通过将应用程序上下文直接分配给多核处理器的共享缓存，最多能提升32%的性能。此外，Hadoop中YARN调度器采用的Capacity和Fair作业调度策略是也比较先进的调度算法。Capacity和Fair算法根据不同用户对提交作业在计算时间、存储空间、数据流量和响应时间上的不同需求，在局部(如池或队列中)采用先进先出(First-In-First-Come, FIFO)，其思想与FCFS相同，或基于优先级的策略，分层分级地综合考虑计算、存储资源等的分配，并基于此对提交的作业进行调度。

文献[1]分别基于事件驱动模型和流水线模型开发了两种高性能Web服务器，并在一个4核的处理器上进行测试。他们的实验表明，通过仔细地配置调优，这两种Web服务器的性能要优于nginx, lighttpd, Apache等知名的Web服务器，因此他们认为配置调优比改变系统结构更重要。文献[13]认为多核Web服务器的扩展性差主要是在于缺省的Web服务器配置。他们研究两种请求：动态请求和静态请求。他们认为两种请求扩展性不同是由于动态请求和静态请求本身特性不同导致的。文献[13]通过实验表明，如果针对不同类型的用户请求进行针对性的调优配置，多核Web服务器能获得更好的性能。文献[13]的工作通过减少用户请求在多个处理器核心之间的迁移次数来获取更好的处理性能。

为解决多核Web服务器存在的“乒乓”效应问题，文献[14]提出了DRWS(Dynamic Requests Web Server)算法。DRWS算法将处理同一类动态请求的服务线程分配至同一个处理器核心上。同一类动态请求服务线程的数量由动态请求的访问频率和平均服务时间决定。为了保持处理器核心之间的负载均衡，DRWS使用遗传算法计算各类动态请求服务线程的分配方案。经实验验证，DRWS算法可有效缓存多核Web服务器中的“乒乓”效应问题。但是文献[14]中所提方法是一种静态的动态请求调度算法，当动态请求的到达频率发生变化时，会导致原有算法不再适用。

本文提出了一种新的动态请求调度算法MSMC(Matrix Scheduling for Multi-Core)。新的动态请求调度算法以分配矩阵、动态请求的服务时间为基础，确定动态请求的分配方案，尽量将同一类动态请求分配至同一个处理器核心，同时兼顾处理器核心之间的负载均衡，从而达到避免“乒乓”效应，充分发挥多核处理器性能的目的。与前人所做工作不同，本文所提算法不需要修改操作系统内核也不需要额外的配置优化，主要针对动态请求进行调度，将属于同一类的动态请求分配至同一核心，减少动态请求对应的动态内容在多个处理器核心之间的迁移，充分利用多核处理器的缓存。本文工作与文献[13]的工作有相似的地方，但是本文目的在于减少动态请求对应的动态内容在核间的迁移，文献[13]的目的在于减少动态请求本身在核心间的迁移。

本文按如下结构组织：第1部分引出多核Web服务器面临的问题；第2部分提出动态请求调度模型；第3部分进行仿真实验，并讨论实验结果；最后，给出本文的结论。

2动态请求调度算法

2.1 算法描述

为解决多核Web服务器中出现的“乒乓”效应问题，需要将请求同一个动态内容的动态请求，即同一类动态请求分配至同一个处理器核心上。但是，同时也需要保证处理器核心之间的负载均衡，以免抵消掉避免“乒乓”效应产生的益处[8]。本文所提出的模型需要在此两者之间寻求平衡点。

如图1所示，当包含动态请求的TCP分组到达Web服务器时，通过解析器的解析，可获取基于HTTP协议的动态请求，以及动态请求所指向的动态内容和动态请求包含的参数。解析后的结果可汇集为动态请求队列。本文将指向同一个动态内容的动态请求归为同一类动态请求，同一类动态请求由于请求的动态内容相同，因此执行过程相似，执行时间(也即动态请求的服务时间)相近，且具有共享数据。

图1 算法原理

为提高多核处理器核心的缓存命中率，充分利用各核心的私有缓存，并解决“乒乓”效应问题，需将同一类动态请求分配至同一个处理器核心。因此，图1中调度器可根据各类动态请求的服务时间及到达率计算各处理核心上的负载状况。依据各处理核心上的负载，调度器尽量将同类动态请求分配至同一个处理核心上。通过线程亲和性方法[15]，可在各核心内绑定相同数目的服务线程。当动态请求被分配至某个处理核心时，若该核心有空闲的服务线程，则给该动态请求分配一个服务线程，若无空闲服务线程，则进入该处理核心的等待队列直到有空闲的服务线程。服务线程基于动态请求的请求内容，从缓存(若已缓存)或内存中调用动态请求所指向的动态内容，然后根据动态请求中的参数，执行对应的动态内容，并生成HTML形式的结果。然后将该HTML结果送至I/O缓存，经由I/O管理模块发送至对应的客户端，此即为响应。

2.2 调度算法

调度算法是整个模型的核心，调度器据此将动态请求分发至各处理器核心。为了避免“乒乓”效应、充分利用缓存局部性，需要将同一类动态请求分发至同一个核心。但是，同时也要尽量保持处理器核心之间的负载均衡，以免抵消避免“乒乓”效应带来的益处。因此，调度算法需要在此两者之间取得平衡。

(1)分配矩阵： 若Web服务器中有类动态请求，个处理器核心，此类动态请求的平均服务时间可依据文献[16]所述方法获取，记为。为记录类动态请求分配至个处理器核心的情况，可提出分配矩阵的概念。分配矩阵记录某动态请求分配至某个处理器核心的累计数目，如式(1)所示。

(4)

因为各核心上的负载是根据动态请求的分配数目与服务时间的乘积累加和计算而得，因此各核心上的负载本质上是服务时间的展开。因此，当前各处理器核心上的负载可根据累积负载减去各核心自第1次分配动态请求的时间至当前时间之间的时间段计算。因此，计算方法如下：

(3)分配核心的确定：由此，可计算出各核心在当前时刻的负载，根据各核心的负载，并结合如下算法可确定当前动态请求的分配核心。若当前待分配动态请求属于第类，则分配算法如下：

(a)根据分配矩阵可获取各类动态请求最近一次所分配的处理器核心，称为预期分配核心，记为，则第类动态请求的预期分配核心为。

此算法尽量将同一类动态请求分配至同一个处理器核心上，但又考虑了各核心上的负载情况，尽量保持核心间的负载均衡。

3实验设置与评估

3.1 实验设置

为了验证上述算法，本文开发了仿真Web服务器MSMC。MSMC使用动态链接库(Dynamic Link Library, DLL)文件模拟动态内容的处理情况，请求同一个DLL文件的动态请求归为一类，当动态请求到达分配器时，根据上述算法将动态请求分配至对应的处理器核心。MSMC使用线程池结构，使用线程硬亲和性的方法在每个处理器核心分配相同数目的服务线程。若处理核心有空闲的服务线程，则根据动态请求所请求的内容和参数从内存中或CPU缓存(若DLL文件已缓存)中调取相应的DLL文件执行，执行结果封装为HTML形式，返回给用户，此即响应。其中，MSMC中的DLL文件的执行时间可以设置，由于实际中不同动态内容的服务时间各不相同，因此MSMC中DLL文件的执行时间也不相同，以尽可能模拟实际情况。为了与FCFS和SJF算法对比，本文也分别开发了基于FCFS和SJF算法的仿真Web服务器。

同时，为了实验能够尽可能地符合实际，本文开发了动态请求生成器。动态请求生成器可自动产生动态请求，并根据ON/OFF模型确定动态请求的发包时间间隔，多个发射源叠加之后产生具有自相似特征的动态请求流。此外，在单位时间内，动态请求产生器产生的动态请求数目与对应DLL文件的执行时间也服从重尾分布。动态请求产生器在实验中可分别向MSMC, FCFS, SJF等仿真Web服务器发送符合自相似特征的动态请求流。

3.2 实验评估

(1)响应时间的分布： Web服务器中，动态请求响应时间的分布是服务质量(Quality of Service, QoS)的重要指标。为了评估FCFS(First Come First Served), DRWS(Dynamic Requests Web Server)和MSMC(Multi-Socket Multi-Core)算法的QoS，本实验分别测量出每种动态请求的响应时间并绘出此3种算法的响应时间分布(如图2所示)。

图2 FCFS, DRWS和MSMC调度算法响应时间对比

由图2可知，在每个时间间隔上FCFS的响应时间分布得更为平均，但是FCFS的平均响应时间更长些。这与FCFS具有公平但排队时间长的特性相一致。由于FCFS算法排队时间长，而且不能充分利用多核系统的性能，因此具有更长的平均响应时间。与FCFS算法相比，DRWS和MSMC算法充分考虑了多核处理器的特性并且部分消除了乒乓效应的影响，于是上述两种算法具有更多更短响应时间的动态请求。DRWS是一种静态的调度算法，DRWS的分配算法在确定之后就不改变，而动态请求的到达是随机的，因此使用DRWS算法会引起核间负载不均衡。与DRWS算法相比，MSMC算法动态分配动态请求，因此可以更好地保持处理器核心之间的负载均衡，所以MSMC算法的平均响应时间更短的动态请求更多，整体平均响应时间更短。

(2)自相似性对3种调度算法平均响应时间的影响： 为了模拟网络流量的自相似性，本实验采用ON/OFF重尾模型生成动态请求流。动态请求的发包时间间隔服从Pareto分布，Pareto分布的形状参数(shape parameter)用于表征Pareto分布的重尾程度，取值越小，Pareto分布的重尾程度越明显，动态请求流的自相似性就越强。为研究动态请求流的自相似性对调度算法的影响，本实验通过调整Pareto分布的形状参数，测量并计算各形状参数下3种算法的平均响应时间(如图3所示)。

图3 FCFS, DRWS和MSMC算法平均响应时间随自相似性的变化

自相似的程度可以使用Hurst参数(0.5<< 1)表示，而和的关系如式(6)所示：

(3)服务线程数目对3种调度算法平均响应时间的影响： 为了研究服务线程的数目对调度算法的平均响应时间和丢包率的影响，本实验改变3种调度算法的服务线程的数目，然后测量并计算出各调度算法的平均响应时间和丢包率，结果如图4所示。

图4 FCFS, DRWS和MSMC算法的平均响应时间和丢包率随线程数目的变化

由图4可知，3种调度算法的平均响应时间和动态请求的丢包率均随服务线程数目的增加而降低。服务线程的增加意味着服务器中有更多的服务线程处理到达的动态请求，因此3种调度算法的平均响应时间和丢包率随之降低。而MSMC和DRWS中的服务线程均被限制到指定的核心上，不能在核心间移动，DRWS和MSMC可以充分利用缓存中的数据，故图4中，DRWS和MSMC算法的平均响应时间和丢包率的下降幅度要大于FCFS。此外，MSMC算法不仅可充分利用缓存数据，而且可以动态调整分配方案应对网络突发和波动的情况，因此与DRWS算法相比，其平均响应时间和丢包率更低(如图4所示)。

4结束语

为了解决多核Web服务器中“乒乓”效应的问题，本文提出了一种新的动态请求调度算法。与传统的FCFS算法相比，新算法通过将同种类的动态请求动态分配至同一个处理器核心的方法，可以更好地利用缓存中的数据。与DRWS算法相比，新算法是动态分配算法，可以更好地保持处理器核心之间的负载均衡。本文详细描述了新调度算法并给出了关键计算公式。而且在此基础上，开发出了相应的仿真程序，进行了仿真实验。实验结果证明新的算法可以缓解“乒乓”效应问题。由于实际应用中，处理动态请求涉及的系统资源比较多，不仅仅是CPU资源，还有I/O资源、数据库连接数资源等，也比较复杂，因此在下一步的工作中，准备针对动态请求涉及的其他资源进行研究，继续完善多核环境中动态请求的调度算法。

[1] HARJI A S, BUHR P A, and BRECHT T. Comparing high-performance multi-core web-server architectures[C]. Proceedings of the 5th Annual International Systems and Storage Conference, New York, 2012: 1-12.

[2] APACHE. The Apache Software Foundation[OL]. http:// www.apache.org. 2012.1.

[3] DENG K, VERBOON R, REN K, et al. A periodic portfolio scheduler for scientific computing in the data center[C]. Job Scheduling Strategies for Parallel Processing, Berlin Heidelberg, 2014: 156-176.

[4] PROCTOR I A R, YANG M, and ZHAO H. Executing server side script code specified using PHP on a server to generate dynamic web pages[P]. USA, 8, 707, 161, 2014-04-22.

[5] VAN DER WEIJ W, BHULAI S, and VAN DER MEI R. Dynamic thread assignment in web server performance optimization[J]. Performance Evaluation, 2009, 66: 301-310.

[6] SIDDHA S B. Multi-core and Linux Kernel[OL]. http://oss. intel.com/pdf/mclinux.pdf. 2011.10.

[7] YOU Guohua, WANG Xuejing, and ZHAO Ying. A dynamic requests scheduling model based on prediction in multi-core web server[C]. Internet of Vehicles-Technologies and Services, Beijing, 2014: 304-312.

[8] GUO Danhua, BHUYAN L N, and LIU B. An efficient parallelized L7-filter design for multicore servers[J]. IEEE/ACM Transactions on Networking, 2012, 20(5): 1426-1439.

[9] CHOI G S and DAS C R. A superscalar software architecture model for multi-core processors[J]. The Journal of Systems and Software, 2010, 83: 1823-1837.

[10] CHONKA A, CHONG S K, ZHOU W, et al. Multi-core defense system (MSDS) for protecting computer infrastructure against DDoS attacks[C]. Proceedings of the 2008 Ninth International Conference on Parallel and Distributed Computing, Dunedin, 2008: 503-508.

[11] BOYD W S, CLEMENTS A T, MAO Y, et al. An analysis of linux scalability to many cores[C]. Proceedings of the 9th USENIX conference on Operating Systems Design and Implementation, Berkeley, 2010: 1-8.

[12] KUMAR A, HUGGAHALLI R, and MAKINENI S. Characterization of direct cache access on multi-core systems and 10gbe[C]. Proceedings of the IEEE 15th International Symposium on High Performance Computer Architecture, Raleigh, 2009: 341-352.

[13] HASHEMIAN R, KRISHNAMURTHY D, ARLITT M, et al. Characterizing the scalability of a web application on a multi- core server[J]. Concurrency and Computation: Practice and Experience, 2014, 26: 2027-2052.

[14] YOU Guohua and ZHAO Ying. A weighted-fair-queuing (WFQ)-based dynamic request scheduling approach in a multi-core system[J]. Future Generation Computer Systems, 2012, 28(7): 1110-1120.

[15] AGRAWAL R, GOYAL A, SAMBASIVAM D, et al. Parallelization of industrial process control program based on the technique of differential evolution using multi-threading [C]. 2014 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Zhuhai, 2014: 546-550.

[16] SHARIFIAN S, MOTAMEDI S A, and AKBARI M K. A content-based load balancing algorithm with admission control for cluster web servers[J]. Future Generation Computer Systems, 2008, 24(8): 775-787.

[17] LI J, SHARMA N K, PORTS D R K,. Tales of the tail: Hardware, os, and application-level sources of tail latency[C]. Proceedings of the ACM Symposium on Cloud Computing, Seattle, 2014: 114.

A Dynamic Request Scheduling Algorithm Based on Allocation Matrix in Multi-core Web Server

YOU Guohua CHEN Junjun ZHAO Ying

Center for Information Technology, Beijing University of Chemical Technology, Beijing 100029, China

To implement the high performance web server, it is a key to exploit fully the performance of multi-core CPUs in web servers. Traditional First Come First Served (FCFS) policy does not consider the characteristic of multi-core processors, and could not fully exploit its performance. To address this problem, a dynamic request scheduling algorithm based on allocation matrix is proposed in this paper. The algorithm fully considers the characteristic of multi-core processors, assigns the same kind of dynamic requests to the same processing core, and improves the speed of handling dynamic requests in web server. The results of the experiment show that the web server that adopts this algorithm is superior to the traditional FCFS algorithm in the aspect of similarity, mean response time and dropped rate of dynamic requests.

Web Servers; Multi-core; Dynamic requests; Scheduling

TP301

A

1009-5896(2016)09-2188-06

10.11999/JEIT151328

2015-11-15；

2016-05-09；

2016-07-04

中央高校基本科研业务费项目(PT1607)

Fundamental Research Funds for the Central Universities (PT1607)

尤国华 yough@mail.buct.edu.cn

尤国华： 男，1979年生，讲师，研究方向为多核Web服务器软件体系结构.

陈骏君： 男，1990年生，博士生，研究方向为网络流量分析.

赵 英： 男，1966年生，教授，研究方向为分布式系统、高性能计算.