基于譜聚類的BaaS資源負載均衡調(diào)度算法

熊衍捷，高 鎮(zhèn)，李 根，楊晉生

(天津大學(xué) a.微電子學(xué)院; b.電氣自動化與信息工程學(xué)院，天津 300072)

近年來，區(qū)塊鏈[1-2]技術(shù)不斷發(fā)展壯大，作為區(qū)塊鏈與云計算結(jié)合的產(chǎn)物——區(qū)塊鏈即服務(wù)，正改變著傳統(tǒng)的云計算服務(wù)模式[3]，使區(qū)塊鏈技術(shù)成為一種觸手可及、開箱即用的工具服務(wù)于大眾。超級賬本[4](Fabric)是BaaS的核心模塊，提供基于聯(lián)盟鏈的身份認證、交易背書及區(qū)塊上鏈等功能。網(wǎng)絡(luò)節(jié)點peer負責(zé)維護賬本(Ledger)，依據(jù)具體功能的不同，可分為提交節(jié)點(committer peer)和背書節(jié)點(endorser peer)，F(xiàn)abric從1.0版本開始采用了多通道(channel)的設(shè)計，盡管有利于增強用戶的隱私性和系統(tǒng)的擴展性，但是每一個peer均要處理來自不同通道的事務(wù)且保存一份相應(yīng)的賬本，將對有限的計算資源帶來挑戰(zhàn)并增大磁盤空間的存儲壓力。改善BaaS的性能已經(jīng)變得愈加迫切。

基于Kubernetes[5]的云計算平臺，才麗[6]提出了面向BaaS的Best-Balanced加權(quán)評分模型解決資源負載均衡問題，Best-Balanced算法從資源量負載平衡、資源量剩余量平衡和不同資源類型間負載平衡來衡量資源分配的平衡性。Medel等[7]通過基于Petri網(wǎng)的性能模型對Kubernetes容器的部署和終止開銷進行分析，提出合理的Pod下容器配額規(guī)則，最后實現(xiàn)一種考慮容器資源爭奪現(xiàn)象的調(diào)度算法。

基于多通道的設(shè)計，如果多個peer加入了同一通道并被調(diào)度至同一虛擬機，即使通道內(nèi)的業(yè)務(wù)量不大，其任意時間點的負載均為每一個peer負載的總和，也可能造成虛擬機的負載過重，甚至發(fā)生單點故障,從而降低用戶服務(wù)質(zhì)量。針對上述問題，筆者提出了一種面向多通道的基于譜聚類(Spectral Clustering)的負載均衡調(diào)度算法SC-channel，使用典型的NJW[8]譜聚類算法進行聚類分析，采用Jaccard相似系數(shù)依據(jù)對應(yīng)的通道度量peer之間的相似度，使用基于數(shù)量加權(quán)的k-means算法做最后的特征聚類，并與平臺默認提供的調(diào)度算法進行對比，實驗結(jié)果證明了所提出算法能夠增強系統(tǒng)的可靠性與可用性。

1 SC-channel算法描述

譜聚類算法[9]是機器學(xué)習(xí)領(lǐng)域中的一種無監(jiān)督學(xué)習(xí)算法，基于圖的分割理論劃分樣本集，以達到類內(nèi)樣本點距離最小而類間的樣本點距離最大。相較于傳統(tǒng)的聚類算法，如k-means聚類[10]、層次聚類[11]、基于密度的聚類(DBSCAN)[12]等，能夠在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解。為了充分發(fā)揮譜聚類適應(yīng)性強、收斂度高的優(yōu)勢，需要合理地選擇具體譜聚類算法并依據(jù)問題空間選擇度量樣本間距離的方式。

1.1 算法可行性分析

如圖1所示，F(xiàn)abric產(chǎn)生一筆交易的基本流程如下：

圖1 交易的基本流程Fig. 1 The basic process of transaction

Step1 客戶端創(chuàng)建一筆交易，該交易包括客戶端的ID、鏈碼(chaincode)ID、提交交易自身的載體、時間戳、其他域客戶端的簽名，依據(jù)背書策略被發(fā)送到所選擇的背書節(jié)點；

Step2 背書節(jié)點模擬交易并產(chǎn)生背書簽名；

Step3 客戶端收集到足夠多的交易背書后，通過排序(ordering)服務(wù)廣播該交易，如果客戶端沒有設(shè)法為交易收集背書，則放棄這個交易并稍后再試；

Step4 排序服務(wù)向各peer節(jié)點提交交易，在完成最終的確認后交易被提交上鏈。

圖1中的①②③④對應(yīng)于step1、2、3、4。除步驟3外其余基本流程均需要peer的響應(yīng)，因此peer在Fabric中承擔著主要的計算任務(wù)。

如表1所示，該實驗將4個peer以兩兩一組的方式分別放置于2臺虛擬機(1G2核)192.168.10.157和192.168.10.158上，創(chuàng)建通道channel1和channel2，給定每秒處理的交易量分別為6和3進行2組實驗，每組實驗重復(fù)3次，結(jié)果如圖2、圖3所示。

表1 部署peer的兩組實驗

圖2 同一通道的peer在不同虛擬機的結(jié)果Fig. 2 Resulets of peer in the same channel in different virtual machines

圖3 同一通道的peer在相同虛擬機的結(jié)果Fig. 3 Resulets of peer in the same channel in the same virtual machine

如圖2所示，將同一通道的peer放置于不同虛機上，通過對peer合理的分類，使各虛擬機cpu利用率更接近平臺的平均cpu利用率，負載的均衡度更高，然而這僅考慮的是一種簡單的場景，如果peer的數(shù)量較多，需要創(chuàng)建的通道數(shù)量也較多，那么如何確定分類原則將變得復(fù)雜。由于譜聚類算法不依賴于樣本的形狀，聚類效果優(yōu)異，因此采用該算法對復(fù)雜場景下的peer做聚類，以此來提高平臺的可用性。

1.2 算法思想描述

根據(jù)圖劃分準則的不同，經(jīng)典的譜聚類算法可分為PF算法[13]、SM算法[14]和NJW算法等，NJW算法采用高斯徑向核(Radial Basis Function,RBF)構(gòu)造相似矩陣W，即

(1)

能夠直接得到聚類效果較好的樣本集k路分割，因此選擇NJW算法作為文中譜聚類算法的具體實現(xiàn)，該算法的主要步驟如下：

Step1 計算相似矩陣W，獲得度矩陣D，得到拉普拉斯矩陣L；

Step2 計算矩陣L的前k個最大特征值所對應(yīng)的特征向量x1,…,xk，構(gòu)造矩陣X=[x1,...,xk]∈Rn×k；

Step4 使用k-means算法或其他經(jīng)典算法按行對矩陣Y聚類。

盡管NJW算法具有聚類效果好、多路分割的優(yōu)勢，但是簇類數(shù)目C和尺度參數(shù)σ需要人為選定，具有一定的不確定性。對于簇類數(shù)目C的選定，文獻[15]提出了一種啟發(fā)式確定類數(shù)的DP-NJW譜聚類算法，根據(jù)密度分布確定類中心和類數(shù)，Zeng等[16]通過使用模糊聚類測量譜聚類數(shù)目，Li等[17]基于傳統(tǒng)的量子聚類，能夠在不知道聚類數(shù)量的情況下找到任何形狀的聚類，進一步縮短了計算時間，提高了計算效率；對于尺度參數(shù)σ的選擇，Xie等[18]提出了局部標準偏差(Local Standard Deviation Spectral Clustering,SCSD)譜聚類算法改進NJW和Self-Turning算法[19]對σ的選取，Mohanaval- li等[20]計算每個數(shù)據(jù)點i與其他點的距離，基于該點的度Di使用四分位數(shù)自動確定σi，具有較好的聚類效果，文獻[21]提出SC_SD和SC_MD兩種譜聚類算法，其定義樣本的標準差與樣本到其余樣本的距離的均值作為鄰域半徑，具備完全的自適應(yīng)性。

將平臺下具備計算能力的虛擬機數(shù)量作為簇類數(shù)目C，使得類之間隔離計算資源，能夠較好解決人為因素帶來的影響。相似矩陣W的構(gòu)造，由于peer樣本集屬于離散型、集合型數(shù)據(jù)，不再適用于采用RBF構(gòu)造的相似矩陣，因此采用Jaccard相似系數(shù)度量樣本間的距離。Jaccard系數(shù)適用于表示有限樣本集合的相似性與差異性，假定x和y分別具有n維特征(n個通道)，xi和yi的取值為二元類型數(shù)值{0,1}，對于計算x與y的距離，Jaccard系數(shù)使用a,b,c,d4個參數(shù)來計算相似度,即

(2)

式中:1)a表示樣本x和y中滿足xi=yi=1的數(shù)量，在SC-channel中表示x和y加入同一通道的數(shù)量。2)b表示樣本x和y中滿足xi=1,yi=0的數(shù)量，在SC-channel中表示x加入某通道而y未加入該通道的數(shù)量。3)c表示樣本x和y中滿足xi=0,yi=1的數(shù)量，在SC-channel中表示x未加入某通道而y加入該通道的數(shù)量。4)d表示樣本x和y中滿足xi=yi=0的數(shù)量，在SC-channel中表示x和y均未加入同一通道的數(shù)量。

由式(2)可知，加入相同通道數(shù)量越多的x和y相似度越高，越趨向于分入同一個類，而據(jù)1.1節(jié)實驗可知，加入不同通道的x和y處于同一虛擬機，即處于同一類簇，使負載均衡度提高，文中使用改寫的Jaccard系數(shù)構(gòu)造相似矩陣，即

(3)

使用式(3)計算peer間的相似度將更適合文中的研究問題。SC-channel算法偽代碼如算法1所示。

算法1 SC-channel偽代碼

輸入：數(shù)據(jù)集Peer={peer1,peer2,…,peern}，標簽集Channel={channel1,channel2,…,channelm} ，類別數(shù)C。

輸出：聚類后的各簇H={h1,h2,…,hC},按簇binding至C臺虛擬機。

1)遍歷peer根據(jù)標簽信息利用式(3)求出鄰接相似矩陣W；

5)Kubernetes調(diào)度器執(zhí)行binding操作，按聚類結(jié)果將peer pod調(diào)度至不同虛擬機。

2 SC-channel實驗

筆者在基于Kubernetes v1.14.2的云平臺上用5臺虛擬機進行了實驗驗證，實驗配置詳情如表2、表3所示，通道創(chuàng)建詳情如表4所示。使用Python、Shell混合編寫SC-channel算法放于Master監(jiān)聽peer的調(diào)度，k-means算法參考sklearn.cluster包改進。在Master機器使用Fabric Nodejs SDK向BaaS發(fā)起invoke合約調(diào)用，部署Heapster、Influxdb對實驗數(shù)據(jù)進行監(jiān)視和收集，取平衡因子P為15，為了校驗資源調(diào)度算法的有效性，采用資源利用率Vi的方差評價資源負載均衡度，即

表2 虛擬機配置詳情

表3 集群網(wǎng)絡(luò)拓撲

表4 通道的創(chuàng)建

Vi=αVicpu+βViram,

(4)

(5)

由于BaaS上CPU相比于內(nèi)存變化波動較大，式(4)中取α為0.3，β為0.7。比較了SC-channel與僅僅采用經(jīng)典的k-means的NJW算法(NJW)、(LRP, Least Requested Priority)、SSP, Selector Spread Priority)對9個peer pod的調(diào)度實驗。

如圖4所示，channel1與channel3始終保持較低吞吐率，channel2在第30 s發(fā)起交易，第150 s處結(jié)束，逐步增大TPS量，結(jié)果顯示，負載均衡度隨著不斷增長的交易量呈現(xiàn)出先下降后上升的態(tài)勢，當channel2具有小于等于15的吞吐量時，SC-channel與其他3種調(diào)度算法下的負載均衡度總體相差不大，隨著TPS的不斷提高,二者負載均衡度拉開差距。這是由于負荷的提高，平臺下的一部分虛擬機已經(jīng)達到了資源使用上限，而那些計算資源充足的虛擬機因peer未加入始終無法釋放潛在的能力。

圖4 TPS增大時2種算法下的負載均衡度Fig. 4 Load balance degree under two algorithms when TPS increases

統(tǒng)計每組實驗的最高S值如表5所示?？梢钥闯?，當通道接近空載，默認調(diào)度算法LRP、NJW的均衡度更高，且二者相差不大，但隨著處理量的增大，均衡度值不斷降低，下降極為迅速，將降低用戶響應(yīng)時間，增大單點故障概率，若Pod因資源不足而遷移將產(chǎn)生額外的資源損耗，影響服務(wù)質(zhì)量。隨著TPS的提高，使用經(jīng)典k-means的NJW調(diào)度算法與LRP、SSP的均衡度差距不斷縮小，甚至在TPS為40時，相比于SSP均衡度更高，由于該算法產(chǎn)生了幾個數(shù)量極少的簇，導(dǎo)致相應(yīng)的虛擬機始終處于空載的狀態(tài)，該算法更適應(yīng)于龐大交易量的定向通道的業(yè)務(wù)場景，使那些需要處理繁重業(yè)務(wù)的少數(shù)peer分布在一個虛擬機中。SC-channel在20～40的TPS范圍具有較高的均衡度，隨著TPS的提高，均衡度表現(xiàn)得比較穩(wěn)定。根據(jù)表5計算4種算法NJW、LRP、SC-channel、SSP下的平均S值分別為88.42、72.78、62.60和83.94，可見SC-channel負載均衡性能較好。

表5 每組實驗取最高值S

3 結(jié) 論

區(qū)塊鏈技術(shù)以其去中心、去信任的優(yōu)點成為當前社會的研究熱點，其衍生的比特幣、以太坊、超級賬本等區(qū)塊鏈項目正煥發(fā)生機，研究時下熱門的BaaS平臺，提出了基于NJW譜聚類的資源負載算法，該算法改進默認調(diào)度算法的不足，基于peer加入的通道作為調(diào)度考量，實驗結(jié)果表明，利用該算法對peer進行調(diào)度使平臺面對不同負載壓力下的負載均衡度顯著提高，增強了平臺的可用性與可靠性。