潘仙張　郭文平　應(yīng)國良

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

關(guān)鍵詞：緩存替換算法；OA系統(tǒng)；WEB服務(wù)性能優(yōu)化；代理服務(wù)器

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

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

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

1相關(guān)研究

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

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

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

21基于PageRank建模

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

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

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

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

結(jié)論：依據(jù)用戶對OA系統(tǒng)的歷史操作行為集合W，預(yù)測用戶的下幾次操作行為集合W1，是圖靈不可判定問題。

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

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

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

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

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

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

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

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

22響應(yīng)速度理論分析

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

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

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

23實驗設(shè)計

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

收集他們的http連接數(shù)。以每隔2小時為單位統(tǒng)計OA服務(wù)器http連接數(shù)。數(shù)據(jù)對比如表3和圖5，通過表3和圖5發(fā)現(xiàn)，本文的OA服務(wù)器http并發(fā)連接數(shù)和系統(tǒng)的響應(yīng)性能都比較好。也說明了本文的緩存算法比較有優(yōu)越性。

3結(jié)語

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

參考文獻

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

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

[3]賈鐵軍.網(wǎng)絡(luò)安全技術(shù)及應(yīng)用[M].北京：機械工業(yè)出版社，2010，26-83.

[4]劉化君.網(wǎng)絡(luò)安全技術(shù)[M].北京：機械工業(yè)出版社，2010，38-82.

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

[6]楊華甫.網(wǎng)絡(luò)環(huán)境下數(shù)據(jù)庫的一致性研究[J].計算機時代，2004，33（7）：3-4.

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

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

[9]陳愛林、樂全明 .代理服務(wù)器在智能變電站和調(diào)度主站無縫通信中的應(yīng)用[J].電力系統(tǒng)自動化，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]劉寶鋒、張文軍、谷志奇.基于代理服務(wù)器緩存的Internet分層視頻點播[J].上海交通大學(xué)學(xué)報.2005，39（4）：645-648.

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

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

[14]廖建新 楊波.基于網(wǎng)絡(luò)代價的流媒體緩存策略研究[J].電子與信息學(xué)報.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]李時.應(yīng)用統(tǒng)計學(xué)[M].北京，清華大學(xué)出版社，2005.