吳嘉軒，代 鈺，張 斌，楊 雷

基于拓撲匹配的組件服務副本放置算法

吳嘉軒1，代 鈺2，張 斌1，楊 雷1

(1. 東北大學信息科學與工程學院 沈陽 110819；2. 東北大學軟件學院 沈陽 110819)

提出了一個基于拓撲匹配的組件服務副本放置算法，該方法首先通過多規(guī)模圖聚類算法獲取組件服務的通信拓撲結構，隨后使用譜聚類算法獲取計算節(jié)點的拓撲結構，最后通過使用貪心算法匹配上述兩種拓撲結構來進行組件服務副本的放置?；贑loudSim云仿真軟件搭建了一個仿真實驗環(huán)境并開展了一系列實驗，仿真實驗結果表明了所提出的方案和算法對于提高云服務系統(tǒng)的性能是有效的。

云計算; 聚類算法; 組件服務副本; 副本放置; 拓撲匹配

副本技術作為一種提高系統(tǒng)可用性、負載均衡及訪問效率的手段，目前已經(jīng)廣泛應用于各種云服務系統(tǒng)的性能保障[1]。隨著副本技術的不斷發(fā)展，在云服務系統(tǒng)中部署組件服務副本已越來越普遍。組件服務副本在云服務系統(tǒng)中得到了廣泛的應用，采用這種機制可以提升組件服務的可用性、提高云服務系統(tǒng)整體的性能。組件服務副本放置作為云服務系統(tǒng)中組建服務副本的一個關鍵問題，能否順利解決，直接影響云服務系統(tǒng)的整體性能。

目前，針對如何進行副本放置問題開展了很多工作，在組件服務副本放置位置選擇方面，目前的研究工作可以分為非云計算背景下的副本放置和云技術背景下的副本放置兩類。

在非云計算背景下的副本放置研究中，文獻[2]提出了一種圖著色算法來放置副本；文獻[3]介紹了基于層疊網(wǎng)的服務質(zhì)量感知對象復制問題，并提出了GreedyMSC、CORE-SELECTON和TTL-BASED 3種算法，可在O(n3)的時間復雜度下得到副本放置策略；文獻[4]給出了一種QoS感知的副本放置問題定義，提出了一類啟發(fā)式算法L-Greedy-Insert，通過帶回溯的循環(huán)試探尋求滿足QoS約束的副本集合。在云計算背景下的副本放置研究中，文獻[5]提出了一種志愿者計算框架；CloudRank[6]是一種面向云計算的基于QoS的組件排名框架，通過將計算節(jié)點的QoS值從高到低進行排序，并從中選取QoS值的計算節(jié)點進行副本放置；文獻[7]針對副本的負載均衡問題提出了副本放置算法；文獻[8]通過對歷史訪問記錄的分析，給計算節(jié)點賦予決策值，用以放置副本并平衡系統(tǒng)總體負載情況。

然而，上述研究工作大都沒考慮組件服務副本與數(shù)據(jù)副本的區(qū)別，與傳統(tǒng)分布式計算平臺上的數(shù)據(jù)副本相比，云計算平臺上的組件服務副本有著顯著的區(qū)別，最主要的兩個區(qū)別為：1) 云服務系統(tǒng)上的云應用大多由多個不同的組件服務構成，這些組件服務之間相互協(xié)作共同完成整個系統(tǒng)的服務，并可能具有較強的數(shù)據(jù)依賴關系，類似科學工作流當中的I/O密集型應用。2) 云計算平臺上的用于放置副本的計算節(jié)點數(shù)量眾多，各個計算節(jié)點性能各異。

基于以上分析，得知組件服務不同于單一的、獨立的數(shù)據(jù)，在組件服務之間可能存在著緊密的數(shù)據(jù)依賴關系，即一個組件服務的輸出是另一個組件服務的輸入。如果在組件服務訪問頻繁的時候，還按照針對數(shù)據(jù)副本的放置方式來放置，將難以保證性能。一個完整的云應用程序大多是一個拓撲感知方式的[9]，因此在放置組件服務副本時采取與計算節(jié)點拓撲結構相匹配的放置方式，對于提高云應用的執(zhí)行效率是有益的。

為此，本文針對具有強數(shù)據(jù)依賴關系的組件服務副本放置這個關鍵問題進行分析，并提出基于拓撲匹配的組件服務副本放置算法。該算法包括3個主要的步驟：首先介紹了一種如何來獲取各個組件服務之間的通信拓撲結構的方法；然后給出了一個獲取計算節(jié)點拓撲結構的方法；最后提出了一個依據(jù)組件服務與計算節(jié)點的拓撲信息來進行組件服務副本放置的方法，并通過真實數(shù)據(jù)對本文提出的組件服務副本放置算法進行實驗以證明其優(yōu)越性和有效性。

2 組件服務副本放置算法

2.1 云服務邏輯拓撲結構探索算法

云應用中的各個組件服務之間的通信關系可以用一個通信矩陣來表示，矩陣當中的值表示兩個組件服務之間通信的頻繁程度，其值越大則表示兩個組件服務之間的通信更緊密。

本文將通信拓撲探索歸結為圖聚類問題，即把通信矩陣進行結構的劃分，使得通信緊密的組件服務處于一個結構當中。本文使用層次聚類算法來獲取云應用中各個組件服務的通信拓撲結構。層次聚類算法事先并不需要假定分解成多少個聚類，而是通過對系統(tǒng)生成樹的任意層次進行“cutting”操作來獲得適合的聚類數(shù)。層次聚類算法得到的結果不一定是最優(yōu)的，通常還需要對結果使用優(yōu)化算法針對聚類的模塊性[10]進行改進。本文使用多規(guī)模優(yōu)化算法來對聚類結果進行優(yōu)化[11-12]。

假設G為通信矩陣生成的無向圖，表示為(V，E)，其中V表示為節(jié)點的集合，E表示邊的集合。邊的權重可以通過函數(shù)f(x, y)來表示。其中，節(jié)點x的度表示為deg(x)，即該節(jié)點所有邊的權重之和。一個節(jié)點集合的度表示為deg(V)；為每對不同的聚類(A,B)分配一個實數(shù)值，稱之為融合優(yōu)先度(merging priority)，如式(1)。當不同的聚類需要進行合并操作時，它們之間的融合優(yōu)先度決定它們的融合次序，融合優(yōu)先度越高的，越優(yōu)先進行融合。

是否具有良好的模塊性是權衡圖聚類質(zhì)量的重要標志。文獻[13]提出了一個評估n個分離的節(jié)點集之間模塊性的方法，具體形式為：

式中，E表示邊的數(shù)目；cut(Vi, vj)表示被切斷的所有邊的權重之和[14]。通過式(2)推斷出，如果融合聚類A與聚類B將會改變模塊性大小的值為：

此外，把屬于聚類A的服務節(jié)點v移動到另一個聚類B中，會在一定程度上影響兩個聚類之間的模塊性，具體影響的大小又以式(4)來表示：

本文提出的邏輯拓撲結構探索算法的具體步驟如算法1所示。

算法1：云服務邏輯拓撲結構探索算法。

輸入：鄰接矩陣M，邊集E，點集N。

輸出：k個不同聚類的拓撲結構。

1) 通過式(1)計算權重密度(weight density)，并對權重密度從高到低進行排序操作。

2) 如果某條邊的起始節(jié)點與結束節(jié)點沒有融合到一起，并且這條邊的權重密度(weight density)大于atedges/atparis(atedges表示鄰接矩陣M生成的無向圖當中所有邊的權重之和，而atparis表示無向圖當中所有節(jié)點的權重和的平方)，那么就對這條邊的起始節(jié)點和結束節(jié)點進行融化操作。融化完成后重新生成新的鄰接矩陣M和新的邊集E。重復該操作直至沒有聚類可以進行融合操作。

3) d為系統(tǒng)生成樹的高度，其值與步驟2)中的循環(huán)數(shù)相等，本算法通過使用式(4)計算移動一個聚類中的節(jié)點到另一個聚類里所得到的新的模塊性，從中選擇最優(yōu)移動(v,B)，即新的模塊性最高的一個移動。

4) 如果(v,B)是最優(yōu)移動并且DQv→B＞0，就把節(jié)點v移動到聚類B中，重復此操作直至DQv→B≤0。

2.2 云環(huán)境物理拓撲結構探索算法

在獲取邏輯拓撲結構之后，本節(jié)將進一步介紹如何獲取計算節(jié)點的拓撲結構，即物理拓撲結構。此物理拓撲結構發(fā)現(xiàn)算法是以計算節(jié)點之間的響應時間作為劃分拓撲結構的依據(jù)，即一個相同拓撲結構的聚類里的計算節(jié)點之間有著更小的延遲，因此，如果把云環(huán)境中的各個計算節(jié)點之間響應時間用鄰接矩陣的形式來表示的話，物理拓撲結構發(fā)現(xiàn)問題也可以歸類為一個圖聚類問題。

用C={ci|i=1,2,??,n}表示整個云服務系統(tǒng)，其中，ci表示第i個計算節(jié)點，并且每個計算節(jié)點都有其極限帶寬。計算節(jié)點之間的響應時間可以通過一個n×n的矩陣R來表示。為了解決這個問題，提出基于普聚類算法[15]的云環(huán)境物理拓撲結構識別算法，把大量計算節(jié)點分解成多個不同的聚類，使得相同聚類里的各個計算節(jié)點之間的響應時間較短。為了方便計算，把響應時間矩陣R進行標準化操作，轉化為一個帶權矩陣W，有：

式中，bij表示計算節(jié)點ci和cj之間的響應時間；wij表示兩個計算節(jié)點之間通信能力的強弱，其值如式(5)所示，可以看出wij的值越大意味著更短的響應時間。

本文使用拉普拉斯矩陣(Laplacian matrix)作為譜聚類的方法，定義如下：

式中，D表示為矩陣W的度矩陣。

本文提出的物理拓撲結構探索算法的具體步驟如算法2所示。

算法2：云環(huán)境物理拓撲結構探索算法。

輸入：響應時間矩陣R，需要分割成的聚類個數(shù)k。

輸出：k個聚類。

1) 通過響應時間矩陣R計算出相似圖矩陣W，再通過相似圖矩陣W計算出帶權矩陣D；

2) 通過式(6)計算出拉普拉斯矩陣L；

3) 計算拉普拉斯矩陣L的k個最小的特征值以及對應的特征向量u1, u2,…,uk；

4) 把特征向量u1, u2,…,uk作為k個列生成一個新的n行k列的矩陣U；

5) 令(ri)i=1,2,…,n表示矩陣U的第i行；

6) 使用k-means對(ri)i=1,2,…,n進行聚類操作，使之分解成{A1, A2,…,Ak}k個聚類；

2.3 組件服務副本放置

上文所述的兩個聚類操作完成后，組件服務節(jié)點與計算節(jié)點均被分解到不同的聚類中。這時就可以依據(jù)邏輯拓撲結構和物理拓撲結構進行副本的放置。依據(jù)拓撲結構來放置副本實際就是一個映射操作。聚類完成后，計算節(jié)點分割成了多個不同的聚類，本文使用平均響應時間(ART)來表示每一個聚類的通信能力，如下述公式計算。

式中，ARTi表示第i個計算節(jié)點聚類的平均響應時間；Ci表示第i個聚類的質(zhì)心；Cij表示與節(jié)點j之間的響應時間；n表示計算節(jié)點聚類i當中的節(jié)點數(shù)。當放置組件服務副本時，可以依據(jù)組件服務聚類的權重以及計算節(jié)點聚類的ART來放置。使用I來表示計算節(jié)點聚類的集合，而每一個計算節(jié)點聚類又是許多計算節(jié)點的集合，計算節(jié)點之間的表現(xiàn)使用一個n×n矩陣φ來表示，n表示某個計算節(jié)點聚類當中節(jié)點的數(shù)目，φ中元素的值使用φ(pi, pj)來表示，其表示計算節(jié)點pi和pj的親和程度，具體定義為：

式中，Commij表示計算節(jié)點pi和pj之間的通信能力；Computij表示兩個計算節(jié)點的計算能力；ω表示通信能力和計算能力之間的一個權值；Commij和Computij通過基礎測試獲取。通過式(8)可為每一對計算節(jié)點計算出它們的親和度，從計算節(jié)點聚類中選取若干個彼此之間親和度盡可能大的計算節(jié)點，記為ρ。為了獲取ρ，一種可能的方法就是遍歷所有節(jié)點來選取最優(yōu)的節(jié)點集ρ。然而，這種方法在節(jié)點數(shù)目為n的前提下存在著Cn?ρ種可能性，并且當n的數(shù)目非常大的情況下，這種方法的效率將會非常低下。為了解決這一問題，本文使用貪心選擇算法來獲取近優(yōu)放置節(jié)點集合ρ，如算法3所示。

算法3：貪心選擇算法。

輸入：計算節(jié)點聚類C，矩陣φ，需要的用于放置組件服務副本的計算節(jié)點數(shù)m。

輸出：近優(yōu)放置節(jié)點集合ρ。

1) 對于每一個計算節(jié)點，分別計算它和其他計算節(jié)點之間的親和值，并把所有親和值相加作為該計算節(jié)點的總親和值。

2) 節(jié)點的總親和值越小，意味著該節(jié)點作為組件服務副本放置節(jié)點的可能性越低。找出總親和值最小的節(jié)點并把它從組件服務副本放置候選節(jié)點集C中刪除出去。刪除完成后，需要為節(jié)點集C中剩余的每一個計算節(jié)點重新計算其總親和值。重復該步驟直至C中剩余的計算節(jié)點數(shù)目與m相等。

3) 令ρ=C，則ρ就是近視最優(yōu)解。

3 模擬實驗與性能分析

為模擬本文的組件服務副本放置算法，實驗建立了基于CloudSim[16]的實驗框架，根據(jù)實驗需要，實驗基于CloudSim仿真工具進行結果仿真之前需要對CloudSim內(nèi)部的調(diào)度模塊進行改寫，因為CloudSim內(nèi)部調(diào)度模塊是按照全局并行的調(diào)度方式，即所有部署的組件服務同時調(diào)用執(zhí)行。這種調(diào)度方式并不符合本算法的要求。所以需要對CloudSim內(nèi)部的調(diào)度模塊進行修改，使其調(diào)度方式可以按照某種用戶自定義的規(guī)則進行，并在CloudSim內(nèi)部加入代理模塊來完成組件服務副本放置工作，從而有效的對本章的算法進行仿真。

實驗對本文的基于拓撲匹配的組件服務副本放置算法與文獻[17]的不考慮拓撲結構的組件服務副本隨機放置算法以及文獻[6]的組件排名放置框架CloudRank進行比較，驗證了算法的有效性。實驗使用執(zhí)行周期(makespan)和延遲(latency)兩個指標作為判斷有效性的依據(jù)。其中，一個云應用的執(zhí)行周期表示從其第一個組件服務開始執(zhí)行，到其最后一個組件服務執(zhí)行完成這一段時間；一個云應用的延遲表示該云應用從運行到結束這段時間內(nèi)，每一對具有前后調(diào)用關系組件服務之間延遲的總和。

實驗選取3種不同的云應用CA1、CA2、CA3進行組件服務副本的放置，每個云應用均有各自不同的組件服務流程，分別為并行結構、選擇結構及并行-選擇混合結構。在正式進行仿真實驗之前，需要通過查看日志文件獲取云應用CA1、CA2、CA3中各個組件服務之間的通信頻繁程度以及各個組件服務的參數(shù)，即組件服務id、組件服務指令長度和組件服務輸出文件大小。

通過使用算法1來獲取組件服務的拓撲結構；通過使用算法2來獲取計算節(jié)點的物理拓撲結構。本文實驗將計算節(jié)點分成3個聚類，并使用算法3來進行組件服務副本放置，假設所有的副本數(shù)量均為1。使用CloudSim按照上文所述進行內(nèi)容放置，對實驗進行仿真。使用CloudSim進行10次仿真實驗，仿真實驗如圖1、圖2、圖3所示。實驗最終結果如表1、表2所示。

圖1 CA1仿真實驗

圖2 CA2仿真實驗

圖3 CA3仿真實驗

表1、表2所反映出的10次實驗的平均結果表明，采用本文所提出的組件服務副本放置算法即基于圖拓撲匹配的組件服務副本放置算法，較之目前常用的副本隨機放置算法，無論是在整個云應用的執(zhí)行周期還是云應用的延遲時間上，都有比較明顯的降低。圖3、圖4、圖5通過對CA1、CA2、CA33個不同結構的云應用來進行組件服務放置實驗對比，說明本文提出的組件服務副本放置算法不僅適用于某一種特殊結構的云應用，而且對大部分結構的云應用都有一定的效果。

表1 平均響應時間對比

表2 平均延遲時間對比

4 結 論

組件服務副本放置問題是部署組件服務副本的云服務系統(tǒng)上的一個關鍵問題，合理的組件服務副本分布可以有效提高系統(tǒng)的性能、可用性與可靠性。而組件服務副本不同于以往的數(shù)據(jù)副本，組件服務副本之間具有前后的依賴關系，放置時也必須根據(jù)組件服務副本之間的依賴關系來選取合適的計算節(jié)點進行放置。所以本文提出了基于圖拓撲匹配的組件服務副本放置算法，通過匹配組件服務的拓撲關系與計算節(jié)點的拓撲關系來進行組件服務副本放置，使得云系統(tǒng)可以更加高效和可靠。通過實驗的比較分析，驗證了基于圖拓撲匹配的組件服務副本放置算法的有效性。

[1] ALLCOCK B, BESTER J, BRESNAHAN J, et al. Data management and transfer in high-performance computational gridenvironments[J]. Parallel Computing, 2002, 28(5): 749-771.

[2] KO B J, RUBENSTEIN D. Distributed self-stabilizing placement of replicated resources in emerging networks[J]. IEEE/ACM Transactions on Networking(TON), 2005, 13(3): 476-487.

[3] WANG H, LIU P, WU J. A QoS-aware heuristic algorithm for replica placement[C]//Proceedings of the 7th IEEE/ACM international conference on grid computing. Barcelona: IEEE Press, 2006: 96-103.

[4] TANG X, XU J. QoS-aware replica placement for content distribution[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(10): 921-932.

[5] ANDERSON D P. Boinc: a system for public-resourcecomputing and storage[C]//Fifth IEEE/ACM International Workshop on Grid Computing. Pittsburgh: IEEE Press, 2004: 4-10.

[6] ZHENG Z, ZHANG Y, LYU M R. CloudRank: a QoS-drivecomponent ranking framework for cloud computing[C]//2010 29th IEEE Symposium on Reliable Distributed Systems. New Delhi: IEEE Press, 2010: 184-193.

[7] ZHAO W Q, XU X B, WANG Z W. Load balancing-based replica placement strategy in data grid system [C]//Proceedings of 2010 Third International Conference on Education Technology and Training. Wuhan: IEEE Press, 2010: 314-316.

[8] CHANG R S, CHANG H P, WANG Y T. A dynamic weighted data replication strategy in data grids[C]// IEEE/ACS International Conference on Computer Systems and Applications. Doha: IEEE Press, 2008: 414-421.

[9] FAN P, CHEN Z, WANG J, et al. Scientific application deployment on cloud: a topology-aware method[J]. International Journal of Web and Grid Services, 2014, 10(4): 338-370.

[10] KARYPIS G, HAN E, KUMAR V. Multilevel refinement forhierarchical clustering[R]. Minneapolis: Dept of Computer Science , Minnesota Univ, 1999.

[11] NOACK A, ROTTA R. Multi-level algorithms for modularity clustering[M]//Experimental Algorithms. Berlin, Heidelberg: Springer, 2009: 257-268.

[12] HADANY R, HAREL D. A multi-scale algorithm for drawing graphs nicely[J]. Discrete Applied Mathematics, 2001, 113(1): 3-21.

[13] NEWMAN M E J. Analysis of weighted networks[J]. Physical Review E, 2004, 70(5): 056131.

[14] NOACK A. Energy models for graph clustering[J]. J Graph Algorithms Appl, 2007, 11(2): 453-480.

[15] MOHAR B. Some applications of Laplace eigenvalues of graphs[M]. Netherlands: Springer, 1997: 225-275.

[16] CALHEIROS R N, RANJAN R, BELOGLAZOV A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: Practice and Experience, 2011, 41(1): 23-50.

[17] MALECOT P, KONDO D, FEDAK G. Xtremlab: a system for characterizing internet desktop grids[C]//2006 15th IEEE International Symposium on High Performance Distributed Computing. Island of Kos: IEEE Press, 2006: 357-358.

編 輯 蔣 曉

Component Service Replicas Placement Algorithm Based on the Topology Matching

WU Jia-xuan1, DAI Yu2, ZHANG Bin1, and YANG Lei1

(1. College of Information Science and Engineering, Northeastern University Shenyang 110819; 2. College of Software, Northeastern University Shenyang 110819)

A topological matching-based component service replicas placement method is proposed in this paper. In this method, the communication topology of component services is discovered by multi-scale graph clustering, the topology of compute nodes is acquired by spectral clustering, and lastly the component service replicas is placed through matching the above two topological structures by greedy select algorithm. Comprehensive experiments are conducted by comparing the performance of our method with other methods based on CloudSim simulation software. The results show the effectiveness of our method for improving the performance of cloud service system.

cloud computing; clustering algorithms; component service replicas; replica placement; topology matching

TP319

A

10.3969/j.issn.1001-0548.2015.06.019

2014 ? 08 ? 20；

2014 ? 11 ? 10

國家科技支撐項目(2015BAH09F02, 2014BAI17B00)；國家關鍵科技研發(fā)基金(2015BAH09F02, 2015BAH47F03)；國家自然科學基金(61572116,61572117,61502089)；中央高校東北大學基本科研專項基金(N120804001, N120204003)

吳嘉軒(1990 ? )，男，博士生，主要從事云計算及服務性能管理方面的研究.