多核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年生，教授，研究方向為分布式系統、高性能計算.