基于改進(jìn)PageRank的調(diào)用鏈異常節(jié)點(diǎn)定位研究

陳樂 紀(jì)炎明 肖忠良

摘? 要：微服務(wù)、云原生是當(dāng)前信息系統(tǒng)發(fā)展的主流方向，給信息系統(tǒng)帶來高可用的同時(shí)也讓IT系統(tǒng)變得前所未有的復(fù)雜，這對(duì)IT運(yùn)維工作帶來了巨大的挑戰(zhàn)。機(jī)器學(xué)習(xí)正是當(dāng)前時(shí)代下應(yīng)對(duì)復(fù)雜系統(tǒng)和海量信息的可選措施。文章將討論基于PageRank的算法在接口服務(wù)調(diào)用鏈上定位異常節(jié)點(diǎn)，并且經(jīng)過測(cè)試，可在錯(cuò)綜復(fù)雜的調(diào)用關(guān)系上實(shí)現(xiàn)快速準(zhǔn)確的異常定位。

關(guān)鍵詞：IT運(yùn)維;機(jī)器學(xué)習(xí);PageRank;調(diào)用鏈分析;異常節(jié)點(diǎn)定位

中圖分類號(hào)：TP18? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2096-4706（2021）22-0059-04

Abstract： Microservices and cloud native are the mainstream development directions of current information systems. While bringing high availability to information systems， they also make IT systems more complex than ever before， which bring huge challenges to IT operation and maintenance. Machine learning is an optional measure to deal with complex systems and massive amounts of information in the current era. This paper will discuss the algorithm based on PageRank to locate the exception node on the interface service call chain， and after testing， it can realize fast and accurate exception location on the complex call relationship.

Keywords： IT operation and maintenance; machine learning; PageRank; call chain analysis; abnormal node location

0? 引? 言

當(dāng)前的IT系統(tǒng)大多以采用微服務(wù)+云原生的架構(gòu)[1]。微服務(wù)架構(gòu)是將一個(gè)復(fù)雜的應(yīng)用拆解成多個(gè)獨(dú)立自治的服務(wù)，服務(wù)之間以松耦合的形式交互。如此部署應(yīng)用的優(yōu)勢(shì)很明顯，即業(yè)務(wù)邏輯清晰、部署簡單、可拓展、高可用等等。以中國移動(dòng)某省CRM為例，2018年完成了分布式5層云化IT系統(tǒng)，設(shè)計(jì)的系統(tǒng)極為龐大[2]。其中某訂單系統(tǒng)的規(guī)模如圖1所示。

微服務(wù)的劣勢(shì)也隨著IT系統(tǒng)規(guī)模的擴(kuò)大而愈發(fā)明顯，各個(gè)組件的調(diào)用關(guān)系錯(cuò)綜復(fù)雜，對(duì)運(yùn)維的壓力也與日俱增。為了掌握系統(tǒng)的實(shí)時(shí)狀態(tài)，大多數(shù)IT廠商會(huì)建設(shè)集中化監(jiān)控系統(tǒng)，在IT系統(tǒng)中部署采集agent，實(shí)時(shí)采集系統(tǒng)各個(gè)層級(jí)，比如應(yīng)用、中間件、主機(jī)等的告警信息。這從原來缺少信息的極端，走到信息過載的另一個(gè)極端。同時(shí)，高度復(fù)雜的IT系統(tǒng)架構(gòu)意味著，一旦某個(gè)局部組件發(fā)生異常，故障信息就極易在短時(shí)間內(nèi)擴(kuò)散，觸發(fā)大量告警。大量的告警信息中存在巨大的冗余，會(huì)淹沒掉真正有用的信息?！稊?shù)字企業(yè)雜志》于2019年的IT運(yùn)維管理研究報(bào)告中顯示，大型廠商的IT系統(tǒng)每停機(jī)1小時(shí)，可造成12.7萬美元的損失，而恢復(fù)系統(tǒng)正常平均需要3.7個(gè)小時(shí)[3]。

面對(duì)這樣的挑戰(zhàn)，傳統(tǒng)的運(yùn)維方式屬于被動(dòng)式響應(yīng)，雜亂無章且充斥冗余信息的告警事件讓運(yùn)維人員疲于奔命，在異常事件發(fā)生時(shí)，被動(dòng)的人工排查方式存在故障定位困難、運(yùn)維效率低下的問題。并且隨著業(yè)務(wù)的拓張，系統(tǒng)的擴(kuò)容也在所難免，而運(yùn)維的擴(kuò)展很難跟上系統(tǒng)擴(kuò)容的速度。而機(jī)器學(xué)習(xí)算法輔助的智能運(yùn)維[4]，正是實(shí)現(xiàn)復(fù)雜系統(tǒng)運(yùn)維和處理海量告警信息的可行方向。本文通過引入圖的鏈接（link analysis）的代表性算法PageRank，在多筆業(yè)務(wù)調(diào)用鏈構(gòu)成的有向圖上計(jì)算每個(gè)節(jié)點(diǎn)的異常得分，最終在高度復(fù)雜的調(diào)用關(guān)系網(wǎng)絡(luò)中快速準(zhǔn)確的定位到異常節(jié)點(diǎn)，幫助運(yùn)維人員在異常、故障發(fā)生時(shí)快速定位異常根因，從而縮短修復(fù)時(shí)間，快速恢復(fù)業(yè)務(wù)正常可用。

1? 基于PageRank的調(diào)用鏈算法流程

1.1? PageRank算法描述

PageRank最初是用于計(jì)算網(wǎng)頁重要度的方法，于1966年由Page和Brin提出[5]，并用于谷歌搜索引擎的網(wǎng)頁排序。除此之外，在圖書影響力評(píng)價(jià)[6]、全球貿(mào)易網(wǎng)絡(luò)格局演變分析[7]、微博用戶影響力評(píng)價(jià)[8]等方面都有廣泛引用。PageRank算法的基本思想是在將網(wǎng)頁及其訪問關(guān)系定義為有向圖，并在圖上定義一個(gè)隨機(jī)游走模型，即一階馬爾可夫鏈，模擬網(wǎng)頁訪問者隨機(jī)瀏覽網(wǎng)頁的過程。網(wǎng)頁訪問者在每個(gè)網(wǎng)頁依照網(wǎng)頁鏈接出去的超鏈接，以一定概率跳轉(zhuǎn)到下一個(gè)網(wǎng)頁，不斷重復(fù)這個(gè)過程，極限情況下每個(gè)網(wǎng)頁的訪問概率收斂于平穩(wěn)分布，這時(shí)候每個(gè)網(wǎng)頁的訪問概率就是其PageRank值，也就是網(wǎng)頁的重要度。如圖2所示。

PageRank基于兩個(gè)假設(shè)：

（1）如果一個(gè)網(wǎng)頁能被很多其他的網(wǎng)頁鏈接到，說明這個(gè)網(wǎng)頁非常重要，PageRank值也就越高。

（2）一個(gè)PageRank值非常高的網(wǎng)頁鏈接到另一個(gè)網(wǎng)頁，被鏈接網(wǎng)頁的PageRank也應(yīng)該提高。

接下來使用PR值代表網(wǎng)頁的PageRank值，來總結(jié)PageRank值的計(jì)算方法。

輸入：需要計(jì)算網(wǎng)頁P(yáng)R值的N個(gè)網(wǎng)頁，以及網(wǎng)頁之間互相鏈接構(gòu)成的有向圖。

輸出：全部網(wǎng)頁的PR值，以及按照PR值排序得到的網(wǎng)頁重要性順序。

（1）統(tǒng)計(jì)每個(gè)網(wǎng)頁的出鏈對(duì)象，以及所有的出鏈數(shù)量。假設(shè)網(wǎng)頁A的全部的出鏈對(duì)象有網(wǎng)頁B和C，則其出鏈數(shù)量為2。

（2）給每個(gè)網(wǎng)頁賦予一個(gè)初始PR值，假設(shè)存在N個(gè)網(wǎng)頁，定義每個(gè)網(wǎng)頁的初始PR值為1/N。

（3）在每一個(gè)epoch中，依次計(jì)算每個(gè)網(wǎng)頁的PR值，迭代計(jì)算方式為：

其中α是阻尼系數(shù)，一般設(shè)定為0.85，MA指的是對(duì)網(wǎng)頁A出鏈的全部網(wǎng)頁，L（x）指的是網(wǎng)頁X的出鏈數(shù)量，N為網(wǎng)頁總數(shù)。

（4）持續(xù)迭代多個(gè)epoch，直到每網(wǎng)頁的PR值不再顯著變化。即全部的網(wǎng)頁的PR值不再顯著變化。

（5）輸出每個(gè)網(wǎng)頁的PR值。并將網(wǎng)頁按照PR值進(jìn)行排序，輸出重要性排行靠前的網(wǎng)頁。

1.2? 改進(jìn)PageRank算法

PageRank算法主要用作計(jì)算互聯(lián)網(wǎng)網(wǎng)頁重要度的算法。其實(shí)除了之前提到的2個(gè)假設(shè)外，存在一個(gè)隱藏假設(shè)，即各個(gè)網(wǎng)頁之間存在大量的、充分的互相訪問構(gòu)成的鏈接關(guān)系，并且網(wǎng)頁之間按照一定概率進(jìn)行隨機(jī)跳轉(zhuǎn)。這也是PageRank的核心迭代公式的簡單理解。

但對(duì)于接口服務(wù)的業(yè)務(wù)調(diào)用構(gòu)成的調(diào)用網(wǎng)絡(luò)上，直接使用PageRank的節(jié)點(diǎn)權(quán)重計(jì)算方式則存在一定的問題，其基本假設(shè)不成立，即：

（1）單位時(shí)間內(nèi)節(jié)點(diǎn)之間的訪問次數(shù)是有限的，比如5分鐘內(nèi)可能存在最多50筆業(yè)務(wù)，而我們需要在這50筆業(yè)務(wù)調(diào)用中定位到異常節(jié)點(diǎn)，如果節(jié)點(diǎn)非常多，則可能存在某些節(jié)點(diǎn)未被調(diào)用。我們需要基于單位時(shí)間內(nèi)產(chǎn)生的有限業(yè)務(wù)調(diào)用中定位到異常節(jié)點(diǎn)。

（2）節(jié)點(diǎn)之間的訪問存在層次關(guān)系，比如接口服務(wù)層節(jié)點(diǎn)調(diào)用應(yīng)用層節(jié)點(diǎn)，應(yīng)用層調(diào)用中間件節(jié)點(diǎn)，依次類推，不存在頂層的接口服務(wù)節(jié)點(diǎn)直接調(diào)用底層的主機(jī)節(jié)點(diǎn)的情況。

因此我們需要對(duì)PageRank做一定的改進(jìn)，使其能應(yīng)用到業(yè)務(wù)調(diào)用的異常節(jié)點(diǎn)定位。

首先，我們定義一個(gè)節(jié)點(diǎn)與它上下文的調(diào)用節(jié)點(diǎn)、被調(diào)用節(jié)點(diǎn)存在圖相鄰關(guān)系。假設(shè)在多筆調(diào)用鏈構(gòu)成的調(diào)用關(guān)系網(wǎng)絡(luò)中，節(jié)點(diǎn)H分別調(diào)用了節(jié)點(diǎn)O、P、Q，而有節(jié)點(diǎn)A、B、C調(diào)用了節(jié)點(diǎn)H，則H和節(jié)點(diǎn)列表{A，B，C，O，P，Q}都存在圖相鄰關(guān)系。

其次，基于調(diào)用關(guān)系和調(diào)用耗時(shí)，定義節(jié)點(diǎn)之間的有向邊E和權(quán)重W。假設(shè)節(jié)點(diǎn)H調(diào)用了節(jié)點(diǎn)A，則存在一個(gè)有向邊H->A。SRE中提到的4個(gè)黃金指標(biāo)中，耗時(shí)最適合用作計(jì)算異常得分。這里基于節(jié)點(diǎn)之間的調(diào)用耗時(shí)，定義邊的權(quán)重。假設(shè)單位時(shí)間內(nèi)存在50筆業(yè)務(wù)，每筆業(yè)務(wù)的總耗時(shí)為Ti，i=1，2，...，50，則節(jié)點(diǎn)H與節(jié)點(diǎn)A的邊H->A的邊權(quán)重為：

wHA=tHA

其中tHAt為單位時(shí)間內(nèi)發(fā)生的所有業(yè)務(wù)調(diào)用中節(jié)點(diǎn)H調(diào)用節(jié)點(diǎn)A的平均耗時(shí)。

再則，假設(shè)節(jié)點(diǎn)H被調(diào)用時(shí)的平均耗時(shí)越大，則H的異常得分也越大。而一個(gè)異常得分很高的節(jié)點(diǎn)調(diào)用另一個(gè)節(jié)點(diǎn)時(shí)，被調(diào)用節(jié)點(diǎn)的異常得分也相應(yīng)增大。

最后，基于節(jié)點(diǎn)的多筆調(diào)用鏈構(gòu)成的調(diào)用關(guān)系，改進(jìn)PageRank的節(jié)點(diǎn)異常得分的迭代公式為：

其中vj是調(diào)用vi的節(jié)點(diǎn)，M（vi）表示調(diào)用節(jié)點(diǎn)vi的節(jié)點(diǎn)集合，out（vj）表示被節(jié)點(diǎn)vj調(diào)用的節(jié)點(diǎn)集合，wjt表示調(diào)用節(jié)點(diǎn)vj和vi之間有向邊的權(quán)重。

由于節(jié)點(diǎn)間的業(yè)務(wù)調(diào)用可能并不充分，部分節(jié)點(diǎn)存在不被調(diào)用的可能，并且還去除了節(jié)點(diǎn)之間隨機(jī)調(diào)用，這意味著經(jīng)過多次epoch迭代后，節(jié)點(diǎn)的PR值可能不會(huì)收斂。因此我們判斷迭代是否停止的條件需要做修改，即每個(gè)epoch結(jié)束時(shí)，輸出節(jié)點(diǎn)的PR值和節(jié)點(diǎn)的PR排名，如果排名和上一個(gè)epoch相等時(shí)則停止迭代。

改進(jìn)PageRank算法總結(jié)：

輸入：基于多筆調(diào)用鏈構(gòu)成的調(diào)用網(wǎng)絡(luò)N，每筆調(diào)用鏈的調(diào)用總耗時(shí)T，以及每個(gè)節(jié)點(diǎn)之間的調(diào)用平均耗時(shí)t。

輸出：節(jié)點(diǎn)的異常得分序列PR及其排序R。

計(jì)算過程為：

（1）定義節(jié)點(diǎn)的初始PR值。假設(shè)調(diào)用網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)為N。則每個(gè)節(jié)點(diǎn)的初始PR值為：

（2）定義節(jié)點(diǎn)之間的有向邊的權(quán)重。假設(shè)節(jié)點(diǎn)vj調(diào)用節(jié)點(diǎn)vj的平均耗時(shí)為，則節(jié)點(diǎn)vj和節(jié)點(diǎn)vj之間的有向邊的權(quán)重wjt為：

wjt=tjt

（3）從epoch=1開始，依次對(duì)計(jì)算每個(gè)節(jié)點(diǎn)vj 的PR值，計(jì)算方式為：

其中vj是調(diào)用vj的節(jié)點(diǎn)，M（vi）表示調(diào)用節(jié)點(diǎn)vi的節(jié)點(diǎn)集合，out（vj）表示被節(jié)點(diǎn)vj調(diào)用的節(jié)點(diǎn)集合，wjt表示調(diào)用節(jié)點(diǎn)vj和vi之間有向邊的權(quán)重。

（4）輸出每個(gè)節(jié)點(diǎn)的PR值及其排序R，如果第m+1個(gè)epoch輸出的節(jié)點(diǎn)排序Rm+1和前一次，也就是第m個(gè)epoch輸出的節(jié)點(diǎn)排序Rm一樣，則停止迭代，否則重復(fù)步驟3。

以上就是本文用于調(diào)用鏈異常節(jié)點(diǎn)定位的改進(jìn)PageRank算法。

2? 實(shí)驗(yàn)與結(jié)果分析

一個(gè)典型的業(yè)務(wù)調(diào)用鏈如圖3所示。

由于目前計(jì)算機(jī)系統(tǒng)的故障次數(shù)很少，為了驗(yàn)證改進(jìn)PageRank算法在異常節(jié)點(diǎn)定位的準(zhǔn)確率，我們基于業(yè)務(wù)特征仿真了一個(gè)接口服務(wù)調(diào)用網(wǎng)絡(luò)，本次模擬定義了5層業(yè)務(wù)系統(tǒng)，每層分別有10個(gè)節(jié)點(diǎn)，只有相鄰網(wǎng)絡(luò)層可以相互調(diào)用。如此構(gòu)成了如圖4所示的網(wǎng)絡(luò)架構(gòu)。

接下來在網(wǎng)絡(luò)圖中隨機(jī)將1個(gè)節(jié)點(diǎn)，或2個(gè)節(jié)點(diǎn)定義為異常節(jié)點(diǎn)，異常節(jié)點(diǎn)可能在最底層，也可能在最外層?；谡{(diào)用耗時(shí)區(qū)分普通節(jié)點(diǎn)和異常節(jié)點(diǎn)，普通節(jié)點(diǎn)的被調(diào)用耗時(shí)為0～100 ms，而異常節(jié)點(diǎn)在耗時(shí)為200 ms～300 ms。

之后，在接口服務(wù)調(diào)用網(wǎng)絡(luò)中，模擬多筆業(yè)務(wù)的完整調(diào)用，每一筆業(yè)務(wù)都是從最外層節(jié)點(diǎn)一直執(zhí)行到最里層。比如其中的一筆業(yè)務(wù)調(diào)用如圖5所示。

通過在網(wǎng)絡(luò)上模擬w筆業(yè)務(wù)，并使用改進(jìn)的PageRank算法計(jì)算每個(gè)節(jié)點(diǎn)的異常得分，也就是PR值，推舉排序最高的3個(gè)作為推薦結(jié)果。如果預(yù)埋的異常節(jié)點(diǎn)都在推薦結(jié)果之內(nèi)，則定義算法的異常節(jié)點(diǎn)定位正確。本次實(shí)驗(yàn)中主要驗(yàn)證改進(jìn)PageRank算法在不同的預(yù)埋節(jié)點(diǎn)k和模擬業(yè)務(wù)次數(shù)w下的異常節(jié)點(diǎn)定位準(zhǔn)確率。圖6中白色節(jié)點(diǎn)為算法推薦的3個(gè)異常節(jié)點(diǎn)。

改進(jìn)PageRank在多次實(shí)驗(yàn)的異常定位準(zhǔn)確率如表1所示。

異常定位準(zhǔn)確率很好的反映了算法的有效性。以上數(shù)據(jù)表明，隨著模擬業(yè)務(wù)次數(shù)w的增多，改進(jìn)PageRank對(duì)異常節(jié)點(diǎn)的定位準(zhǔn)確率也在逐漸提升，當(dāng)業(yè)務(wù)次數(shù)為節(jié)點(diǎn)數(shù)量的2倍以上，算法的異常定位也更穩(wěn)定，基本滿足業(yè)務(wù)所需。

3? 結(jié)? 論

針對(duì)復(fù)雜系統(tǒng)中難以定位異常節(jié)點(diǎn)的問題，本文基于圖分析算法PageRank算法和業(yè)務(wù)調(diào)用特征，改進(jìn)PageRank算法，改進(jìn)方向主要是邊權(quán)重和節(jié)點(diǎn)異常分?jǐn)?shù)的計(jì)算方式。之后模擬單位時(shí)間內(nèi)產(chǎn)生的多筆業(yè)務(wù)調(diào)用構(gòu)成調(diào)用網(wǎng)絡(luò)，試驗(yàn)改進(jìn)PageRank算法在模擬的業(yè)務(wù)調(diào)用中定位異常節(jié)點(diǎn)的準(zhǔn)確率。實(shí)驗(yàn)結(jié)果表明，本文提出的方法可以在在復(fù)雜的調(diào)用關(guān)系網(wǎng)絡(luò)中快速準(zhǔn)確的定位到異常節(jié)點(diǎn)，可在業(yè)務(wù)上幫助運(yùn)維人員在異?；蚬收习l(fā)生時(shí)快速定位異常原因，縮短修復(fù)時(shí)間，恢復(fù)業(yè)務(wù)正?？捎?。

參考文獻(xiàn)：

[1] 董瑞志，李必信，王璐璐，等.軟件生態(tài)系統(tǒng)研究綜述 [J].計(jì)算機(jī)學(xué)報(bào)，2020，43（2）：250-271.

[2] 范鵬里.甘肅移動(dòng)CRM系統(tǒng)項(xiàng)目優(yōu)化研究 [D].南京：南京郵電大學(xué)，2019.

[3] DANG Y，LIN Q，HUANG P. AIOps：Real-World Challenges and Research Innovations [C]//2019 IEEE/ACM 41ST INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING：COMPANION PROCEEDINGS （ICSE-COMPANION 2019）.Montreal：IEEE，2019：4-5.

[4]裴丹，張圣林，裴昶華.基于機(jī)器學(xué)習(xí)的智能運(yùn)維 [J].中國計(jì)算機(jī)學(xué)會(huì)通訊，2017，13（12）：68-72.

[5] BRIN S，PAGE L. The anatomy of a large-scale hypertextual Web search engine [J].Computer networks，1998，30 （1-7） ：107 - 117.

[6] 宋京京，潘云濤，蘇成.基于Pagerank算法的圖書影響力評(píng)價(jià) [J].中華醫(yī)學(xué)圖書情報(bào)雜志，2015，24（12）：9-14.

[7] 蔣雪梅，張少雪.基于Pagerank算法的中間品全球貿(mào)易網(wǎng)絡(luò)格局演變分析 [J].國際商務(wù)研究，2021，42（1）：38-49.

[8] 吳柯.基于交互行為的微博用戶影響力評(píng)價(jià)研究 [D].廣州：華南理工大學(xué)，2014.

作者簡介：陳樂（1982—），男，漢族，重慶人，項(xiàng)目總監(jiān)，碩士研究生，研究方向：AIOps、業(yè)務(wù)支撐系統(tǒng)運(yùn)營支撐;紀(jì)炎明（1995—），男，漢族，廣東廣州人，項(xiàng)目經(jīng)理，本科，研究方向：AIOps算法;肖忠良（1986—），男，漢族，廣東廣州人，項(xiàng)目經(jīng)理，碩士研究生，研究方向：AIOps、業(yè)務(wù)支撐系統(tǒng)運(yùn)營支撐。