PageRank在OA系統中的應用

潘仙張　郭文平　應國良

摘要：改進了OA系統緩存替換算法。本文針對OA系統的http動態請求進行PageRank建模，極大提高了系統的響應速度。解決了超大量并發用戶的動態請求響應瓶頸。本文的OA緩存替換算法依據每個用戶連接的行為特征預測它下次請求的最大可能，并把用戶下次可能操作所需的數據提前存儲在內存中以求最大的響應性能，本文的OA性能超過了目前已有的OA。

關鍵詞：緩存替換算法；OA系統；WEB服務性能優化；代理服務器

中圖分類號：TP393.07文獻標識碼：A

Abstract：improving the cache replacement algorithm of OA.In this paper，using PageRank to model dynamic http request of OA，it greatly improves the systems response speed.Solving the problem of super large number of dynamic request.The cache replacement algorithm of OA is based on the behavior characteristics of each user connections to predict the next maximum possible request of the user，and the next time possible required data will be stored in memory in order to perform the maximum response performance.This paper performance is over the existing OA system.

Key words：cache replacement algorithm；OA system；WEB server performance optimization；proxy server

0引言

521031568web服務的主要功能是提供網上信息瀏覽服務[1-2]。學校的辦公系統（OA）是基于web服務的開發方式。OA系統對服務器硬件和網絡設備硬件資源的要求極其高，當數據處理功能復雜之后，把功能處理和網頁表示層處理合為一體的方式已經不適合越來越復雜的MIS系統了，目前OA的研發過程中會把一些通用MIS系統的功能模塊獨立出來建立一個通用單獨系統，比如事務處理、數據庫連接、應用系統的安全性連接。這樣OA系統就可以在這些中間件系統的基礎上搭建自己的功能而不需要自己從頭做起。為了使OA系統在上線后能使用戶獲得最大的使用體驗，在OA系統的Web服務器前面搭建一個緩存服務器，它專門負責處理和用戶瀏覽器之間的數據交換。

521031569學校的每年預算是非常有限的，因此，在有限的帶寬和服務器資源的情況下，即在不增加額外硬件開銷的情況下，非常需要通過緩存服務器的應用，提高OA系統的用戶響應速度。緩存服務器采用的緩存軟件一般有squid、Redis、Ngnix。目前流行的OA系統緩存服務采用squid方式。本文針對OA系統，只研究了和基于squid緩存服務器的區別。因squid、Redis、Ngnix [17]采用的LRU、LFU和FIFO算法對動態請求數據緩存效果并不是很好。本文針對高校OA數據請求特點，進行緩存替換算法研究，以此提高OA系統對用戶的響應速度，提升用戶對OA的體驗。

OA 具有非常多文檔、非常復雜的鏈接，但是用戶使用web頁面的內容具有很大的正態分布，從大數據的角度，OA系統的數據訪問具有一定的規律性，符合hmm過程，很適合用PageRank建模。OA采用B/S結構，它整理和儲存高校用戶行政辦公資源，服務器對用戶的請求作出及時的響應 [1-2]。在UNIX和LINUX下使用apache、weblogic作為web服務器，而在Windows下使用IIS作為web服務器。在選擇web服務器時考慮的因素有：性能、安全性、日志和統計、緩沖服務和集成應用程序等。目前OA系統普遍采用圖1[1-2，6]，用戶在瀏覽器通過http協議先請求緩存服務器，如果緩存服務器中存在請求的數據，則直接應答http請求，而不再轉發http請求到web服務器，如果緩存服務器中沒有所請求的數據，則直接把http請求轉到web服務器。這種web服務架構的缺點是緩存服務器對所請求的靜態數據命中率很高，而對動態數據卻表現的并不很好，而OA的http請求好多是動態信息。圖1中的緩存服務器是基于squid的服務器 ，squid是一種用來緩存Internet數據軟件，它接受來自用戶需要的目標請求并適當地處理這些請求后，squid會把用戶請求的數據響應到客戶端機器。Squid很適合靜態數據緩存，當動態數據比較多時，squid的緩存就顯得存儲量大，緩存的命中率低。在圖1的OA系統中，所有的服務器采用DL580 G9，web服務器采用weblogic11g，數據庫采用oracle11g，當同時在線人數超過6500的時候，響應速度就很慢了，用戶的體驗就很差了?；赑ageRank的緩存服務器（緩存服務器中的緩存替換算法采用PageRank）能解決這個問題，而不增加額外的硬件投資。

1相關研究

2005年上海交大劉寶鋒在論文中提出采用緩存的辦法來提高視頻點播的性能[11]。周洲儀等在2010設計并實現了高速安全反向代理服務器 [8].他們用實驗證明了用代理服務的緩存分擔系統響應壓力的可行性。陳兵等實現了哈希鏈表和時間鏈表的HTTP代理緩存機制[12]，在有限的帶寬和服務器資源的情況下，極大的加快了用戶的瀏覽速度。Squid的緩存替換機制主要有兩類，它們分別是基于堆替換緩存機制和基于雙向鏈表的緩存替換機制[16]。 陳愛林等把代理服務器應用在了智能變電站和調度主站無縫通信中[9]取得了極好的用戶使用體驗。廖建新、楊波采用了基于網絡代價的流媒體緩存策略，該算法有效提高了緩存命中率，降低了傳送流媒體所消耗的總體網絡代價，特別適合在網絡結構復雜、節目數量龐大的Internet流媒體。Xiaoming Jiang和Jingqiao Shi在2016年實現了以最低的web服務器資源消耗為代價的穩定的代理服務器[10]。P Cao，S Irani提出在代理服務器中采用GreedyDualSize算法替換緩存的策略，該策略應用在web系統大大減少了網絡的擁堵和系統的響應時間[15]。目前已有的緩存替換算法主要有如下幾種[17]：（1）Least-Recent-Used（LRU）算法，即緩存中只存在最近使用的數據。（2）Least-Freqquently-Used（LFU），即緩存中只存儲最頻繁使用的數據。（3）FIFO，先進先出算法，即一個數據最先進入緩存，則會最早被淘汰。針對OA系統的動態情況，以上算法都欠考慮了用戶操作頁面的互鏈接存在環的情況，以及動態http請求數據的不穩定，存在異方差。國內外學者很早就考慮到采用緩存來提升服務的性能，從理論到實踐積累了豐富的經驗，這些都為本文的工程實踐帶來了寶貴的參考價值。本文把PageRank做為緩存替換算法并應用到OA系統中，在本校OA系統產生的歷史訪問數據做為數據集，并在此數據集上對LRU、LFU、Size、PageRank的緩存命中率進行了比較（見表1）。表1的實驗環境如下：圖1和圖2的所有服務器采用DL580 G9，web服務器采用weblogic11g，數據庫采用oracle11g，圖1和圖2除了緩存服務器上的算法不同，其他軟硬件配置都相同，其中LRU、LFU、Size算法在圖1的緩存服務器上使用，PageRank在圖2的緩存服務器上使用。

學校OA系統的每個用戶就是高校中教職工的某個崗位，每個崗位具有固定的職責，每個職責在近幾年中的變化特別的少，并且每個崗位每天工作的重復性很大，以及在時間序列上有很大的相關性，這些特性是PageRank在OA上應用成功的基礎。PageRank算法能找出每個用戶在使用OA中的數據的時間序列的相關性，預測用戶在接下來的操作中最有可能的行為，并把最有可能供以后訪問所使用的數據通過cache存儲起來。極大提高了OA系統的用戶響應性能?；赑ageRank的OA系統（見圖2）能支持同時在線人數6500人，極大地改善了目前已有的OA系統響應能力。在圖2中，基于PageRank緩存服務器就是緩存服務器采用PageRank算法。

在圖2中，用戶在瀏覽器通過http協議先請求基于PageRank緩存服務器，它依據每個用戶的id記錄出每個用戶的行為請求數據，當用戶的行為數據積累到一定程度，用戶的行為就會呈現明顯的正態分布特性，它就會預測用戶的下次請求最大的幾個可能的內容，并提前預取這些可能數據，并存入緩存服務器中。當用戶下次的數據在緩存服務器中時，則它直接響應用戶的http請求，反之把該用戶的http請求轉到web服務器，web服務器接收到所需的動態數據，并組織成html返回給客戶端瀏覽器，瀏覽器解析web服務器的結果，并顯示給客戶。

21基于PageRank建模

PageRank表示網頁排名算法[17]， 通過PageRank計算每一個網頁的PageRank值，然后根據這個值的大小對網頁的重要性進行排序。它的思想是模擬一個悠閑的上網者，上網者首先隨機選擇一個網頁打開，然后在這個網頁上呆了幾分鐘后，跳轉到該網頁所指向的鏈接，這樣無所事事、漫無目的地在網頁上跳來跳去，PageRank就是估計這個悠閑的上網者分布在各個網頁上的概率。本文用PageRank估計每個用戶在OA系統上的行為在各個功能模塊上的概率。并在PageRank緩存服務器中預存用戶下次最大的幾個可能的數據。高校OA系統的主要功能模塊如表2。OA系統的高效、穩定運行關乎到每個用戶的日常正常工作，關系到高校的日常辦公正常運轉。

定理1：（貝努力大數定律）在獨立隨機試驗中，當實驗次數n無限增加時，事件A的概率收斂某個確定的值。[18]

馬爾可夫鏈平穩分布定義：如X=（x1，x2，L，xN）為一狀態概率向量，P為狀態轉移概率矩陣。若XP=X，則稱X為馬爾可夫鏈的一個平穩分布。[18]

定理2：給定圖靈機M和輸入字符串W，M不在輸入W上停機，為圖靈不可判定問題[7]。

結論：依據用戶對OA系統的歷史操作行為集合W，預測用戶的下幾次操作行為集合W1，是圖靈不可判定問題。

證明：按照用戶對OA系統的歷史操作行為集合W，W1的具體數值并不能確定，因為用戶下幾次對OA系統的操作集合W1受各個隨機未知因素的影響，而W1并不包含在W中，按照定理2，用反正法，假設構造圖靈機M判定W1，M=在輸入上，此處是圖靈機M和用戶對OA系統的歷史操作行為集合W。1）在輸入上運行圖靈機M。2）如果M沒有識別到W1，不停機。3）如果M識別到W1，則接受，停機。依據假設，圖靈機M當識別到W1時，就接受，而實際上W1并為發生，在當前時刻并不是個確定數值，圖靈機M是不能識別W1，且圖靈機并不能停機，這與假設矛盾；所以W1并不可判定。

W1并不可判定，但W1在實際的工程中意義重要，處理的方法是依據定理1和馬爾可夫鏈平穩分布定義，我們可以對W的統計分析，取極大擬然估計，取W1在W集合中會發生的最大概率做為PageRank緩存服務器緩存數據的依據。這樣就極大的提高了OA系統對用戶的響應速度。蔡偉鴻在2010年提出基于選擇性馬爾可夫模型的緩存預取策略[13]，該文獲得了在最好情況下能達到60%的命中率。但是本文的用戶操作頁面的鏈接之間是存在環，單單用馬爾可夫過程很難獲得穩定的收斂結果。而PageRank能解決節點之間鏈接的環問題。

A（i）=∑j∈C（i）A（j）N（j）（1）

A（x）表示該用戶操作頁面x的PageRank值，C（x）表示所有指向x的用戶操作頁面，N（x）表示用戶操作x頁面能鏈接出去的頁面數。OA系統中部分功能PageRank值計算過程如圖3。

由于公式（1）是遞歸定義一個用戶操作頁面的PageRank值，就是要得到一個頁面的PageRank值就要先知道另一些頁面的PageRank值。因此需要設置合理的PageRank初始值。本文采用矩陣的觀點解決使得無論怎樣設置PageRank初始值，最后都會收斂到同一個值。OA系統的操作頁面之間的鏈接關系通過大數定理統計出該頁面轉到接下來用戶操作頁面的概率，把高概率的幾個頁面做為該頁面鏈接頁面。

設鄰接矩陣P表示這個圖的頂點關系，如果頂點（用戶的操作頁面）x向頂點（用戶的下個操作頁面）y有鏈接情況，則Pij=1否則Pij=0。再將每行除以該行非零數字之和，就得到轉移矩陣P，如果用戶的操作頁面總數為M，則這個操作頁面的鏈接矩陣就是N*N矩陣，使用冪法求PageRank值，本文每個操作頁面的PageRank值轉化為求limAnX的值，其中A=q*P+（1-q）*eet/N。P為概率轉移矩陣，et是n維的全1行，q為阻尼系數，取q=0.85，q是為了解決那些不鏈接任何其他用戶操作頁面的頁面，即孤立用戶操作頁面。則

eet=1...1···1···1...1 （2）

X為任意的初始向量，本文設為1，不斷的迭代AX，直到最后兩次的結果近視或相同，最終收斂的向量值就是用戶操作的各個頁面的PageRank值。本文OA系統隨著訪問用戶的增加，緩存的命中率也越來越高，如圖4，A代表圖1中采用LFU的基于squid的緩存服務器的命中率，B代表圖2中采用PageRank的緩存服務器命中率。也說明了本文的OA系統的緩存服務器能通過自我學習調整服務響應的最大性能極限。

22響應速度理論分析

圖1目的是在用戶web訪問的時候增加反向代理，它做為web服務器的替身和web服務器集群的負載均衡器。本文只討論做為web服務器的替身，圖2具有更高的http請求的響應速度。設web服務器的響應速度為a（a>0），即緩存服務器中沒有用戶所請求的數據時的OA系統響應速度；緩存服務器響應速度b（b>0），即web的代理服務器中存在用戶所請求的數據時的OA系統響應速度； a>b，緩存服務器的命中率為X，則瀏覽器訪問web系統的期望響應速度為：

E=bX+a（1-X）（3）

則X越大E越小，即OA系統對用戶的響應速度越快。其中a的實驗環境代表web服務器關閉了所有無用端口，操作系統采用freebsd等安全開源并內核經過定制的操作系統。Web服務器采用weblogic11g，weblogic服務器只開啟授權的合法的web config供web服務器訪問數據庫的訪問。b代表在同樣的硬件型號DL580 G9服務器的情況下，采用squid開源軟件做為緩存服務器，或采用weblogic二次開發的基于PageRank緩存算法（即本文的模式）。通過實驗可得到本文的X比較高，故本文的響應速度比較快。

23實驗設計

為了體現出本文的緩存算法的優越性，圖1和圖2除了緩存服務器上的替換算法不同，其他的軟硬件都相同，服務器都采用DL580 G9，web服務器都采用weblogic11g，數據庫都采用oracle11g，操作系統都采用freebsd 8.1，存儲采用DMX-4。在表1中，LRU、LFU、Size這3個替換算法，LFU在OA系統中的命中率最高，故圖1的基于squid的緩存服務器采用LFU算法，它用A表示。圖2用B表示。

收集他們的http連接數。以每隔2小時為單位統計OA服務器http連接數。數據對比如表3和圖5，通過表3和圖5發現，本文的OA服務器http并發連接數和系統的響應性能都比較好。也說明了本文的緩存算法比較有優越性。

3結語

本文解決了OA系統中大量動態http請求并發瓶頸，極大地提高了web訪問性能。OA系統的用戶操作從數據的角度看有數據的讀、存、刪除、更新部分，本文只是在緩存服務器中考慮用戶下次操作的預取數據讀的部分，在接下來的工作把緩存服務器應用到數據的存、刪除、更新部分，即在用戶操作中先把數據的存、刪除、更新在緩存服務器的內存中操作，再等用戶操作OA系統閑的時候，通過緩存服務請求OA系統，進行真正的數據存、刪除、更新操作。

參考文獻

[1]刁維漢.基于web的信息服務OCLC FirstSerch服務分析[M].上海：上?？茖W技術文獻出版社，2002，56-106.

[2]ABLAN J.Developing Intranet Applications with Java[M].Sams.net，1996，2-15.

[3]賈鐵軍.網絡安全技術及應用[M].北京：機械工業出版社，2010，26-83.

[4]劉化君.網絡安全技術[M].北京：機械工業出版社，2010，38-82.

[5]張文.基于Servlet的搜索引擎[J].軟件，2011，32（2）：75-77.

[6]楊華甫.網絡環境下數據庫的一致性研究[J].計算機時代，2004，33（7）：3-4.

[7]LEWIS H R，PAPADIMITRIOU C H.計算理論基礎[M].張立昂，劉田，譯.清華大學出版社，2006.

[8]周洲儀、吳新松.一種高速安全反向代理服務器的設計與實現[J].計算機研究與發展，2010，46（z1）：332-336.

[9]陳愛林、樂全明 .代理服務器在智能變電站和調度主站無縫通信中的應用[J].電力系統自動化，2010，34（20）：99-105.

[10]JIANG Xiaoming，SHI Jingqiao.Proxisch：An Optimization Approach of LargeScale Unstable Proxy Servers Scheduling[J].International Journal of Computer，Electrical，Automation，Control and Information Engineering，2016，6（10）：1115-1120.

[11]劉寶鋒、張文軍、谷志奇.基于代理服務器緩存的Internet分層視頻點播[J].上海交通大學學報.2005，39（4）：645-648.

[12]陳兵、王立松.基于哈希鏈表和時間鏈表的HTTP代理緩存機制的實現[J].南京航空航天大學學報.2002，34（1）：50-54.

[13]蔡偉鴻、 肖水.基于選擇性馬爾可夫模型的緩存預取策略[J].通信學報.2010，31（2）：58-66.

[14]廖建新 楊波.基于網絡代價的流媒體緩存策略研究[J].電子與信息學報.2007，29（9）：2239-2243.

[15]CAO P，IRANI S.Costaware WWW proxy caching algorithms[C].Proceedings of the Usenix Symposium on Internet Technology & Systems.1997，56（1）：193—206.

[16]LANGVILLE A N，MEYER C O，et al.Googles PageRank and Beyond：The Science of Search Engine Rankings[M].Princeton University Press，2006.

[17]TATARINOV I，ROUSSKOV A.Static caching in Web servers[C].Computer Communications and Networks，Proceedings of Sixth International Conference on.1997.

[18]李時.應用統計學[M].北京，清華大學出版社，2005.