一種門戶環境下的緩存模型和算法
2007-12-31 00:00:00王帥宋靖宇
計算機應用研究 2007年8期
摘要：提出的門戶環境下的緩存模型和算法的基本思想是把門戶頁面分解為I序列、布局塊和內容塊。用戶請求頁面時，門戶系統只生成和傳遞發生改變的塊，再由客戶端根據這些塊和I序列組裝成完整的頁面。實驗結果表明，該算法可以提高網絡帶寬的利用率，縮短響應時間。
關鍵詞：門戶； 緩存； 塊； portlet
中圖分類號：TP302文獻標志碼：A
文章編號：1001－3695(2007)08－0060－04
0引言
1)背景Internet正在飛速發展，其上的信息越來越多，各種不同的學術/商業機構、政府部門等通過Internet發布了很多信息，人們可以通過Internet獲取到幾乎所有需要的信息。但是信息分布的分散性使得用戶需要花費大量時間在獲取所需要的全部信息上，效率非常低。
門戶就是在這種背景下產生的。它是一個集中展示各類信息的系統，可以把不同來源、不同類別的信息放到一個頁面上集中顯示；它是可訂制的，用戶可以根據自己的需求訂制自己的個性化頁面。這樣，用戶可以通過一個頁面就獲取到自己需要的所有信息，提高了效率。
2003年9月，JCP組織針對門戶發布了基于J2EE架構的JSR 168規范[1]。根據規范，門戶是一個基于Web的支持個性化、單點登錄、內容集成和展示的應用系統；portlet是基于Java的Web組件，它可以處理request并生成動態的Web內容，這些動態內容被稱為塊。門戶系統通過portlet容器獲得這些塊，然后根據訂制的頁面布局方式把這些塊組裝成完整的Web頁面。2003年8月，OASIS組織發布了WSRP（Web services for remote portlets）規范。該規范定義了如何利用SOAP的Web服務在門戶應用中生成標記片段，它可以使門戶在其頁面中顯示運行在遠程portlet容器中的portlet[2]。
2）問題
一個門戶頁面往往需要展示多個不同來源、不同類別的portlet的內容。Portal服務器與遠程portlets間的網絡交互、服務器端的計算量，以及portlets發生的異常，均會加大門戶的響應時間。因此，提供一個快速的響應時間成為門戶系統迫切需要面對的問題之一。網站響應時間過長會引起客戶的極大不滿，進而造成客戶的流失，最終導致商業上的損失。
研究表明，在可用的網絡帶寬中，很大一部分均被浪費了。造成浪費的一個原因是頁面上的任何一點修改均會導致整個頁面的重新傳輸；此外，同一個資源對應不同的URI，也會造成數據的重復傳輸，從而導致浪費。Mogul等人的研究表明，25%~30%成功的頁面傳輸是由數據修改引起的；而54%的頁面傳輸包括相同的資源，這些相同的資源占據了傳輸總量的36%[3，4]。
緩存是解決這種問題的有效手段之一。現階段，靜態頁面的緩存技術已經非常成熟，但是并沒有產生非常有效的動態頁面的緩存技術。當前對動態頁面緩存技術的研究主要集中在對動態頁面的分塊上，即根據某種算法，把一個或一系列指向同一個URI的頁面分為多個塊，每個塊可以是頁面上的一個導航欄，或者是一個廣告欄，或者是一段新聞等。對動態頁面的緩存，即是對這些塊的緩存。分塊算法是這類緩存技術的核心，而很多已提出的算法的效率非常低下。
本文專門針對門戶系統提出了一種緩存方法。根據JSR 168規范，門戶系統負責把不同portlet產生的內容集中展示，portlet負責產生內容，門戶系統負責頁面布局，每個portlet產生的內容和負責頁面布局的內容彼此相互獨立，有獨立的更新周期。個性化使得門戶系統的用戶可以調整各自對應的門戶展示頁面。本文提出的方法為每個門戶頁面構造一棵塊關系樹，獲取頁面對應的I序列，生成頁面時分別生成塊關系樹中的布局塊和內容塊，并對這些塊進行緩存。它的好處有：頁面生成的結果即為組成頁面的布局塊和內容塊；
組成頁面的布局塊和內容塊可以分開獨立生成；
可以實現內容塊、布局塊在同構、異構頁面之間的重用；
生成頁面時，只需生成發生改變的內容塊或布局塊。
1緩存模型
本文的目標是在服務器端產生門戶頁面時，生成的不是單一的HTML文檔，而是根據在頁面上的功能，生成描述頁面布局的布局塊和表述頁面內容的內容塊，即單個portlet產生的內容。
定義1內容塊為portlet動態生成的一段HTML代碼。
定義2布局塊為門戶服務器動態生成的一段負責頁面布局的HTML代碼，它一般是固定不變的。
本文使用塊關系樹來描述組成門戶頁面的布局塊和內容塊之間的嵌套關系，稱該樹為LcTree。通過LcTree，可得到：
推論1在LcTree中，所有的內容塊均是葉子節點，所有的布局塊均是非葉子節點。
推論2LcTree的根節點一定是一個布局塊，稱該布局塊為頂層布局塊。
LcTree中的每個節點對應的塊均需要有一個標志符。布局塊的標志符與布局方式是一一對應的，相同布局方式對應的標志符是一樣的。內容塊的標志符與portlet ID一一對應。本文使用IL作為布局塊的標志符，Ic作為內容塊的標志符。
定義3I序列表示組成一個門戶頁面的各個布局塊與內容塊之間的嵌套關系。它是該門戶頁面對應的LcTree的深度優先遍歷。
通過上述定義，本文給出門戶頁面的精確定義如下：
定義4一個門戶頁面是一個I序列和I序列相關的布局塊、內容塊的集合。
生成門戶頁面的過程即為生成門戶頁面對應的I序列和相關塊，再根據I序列和這些塊組裝出完整的門戶頁面的過程。AFTree和I序列生成算法如圖1所示。
2緩存算法
2．1生成I序列和布局塊的算法
一個門戶頁面由一個I序列和對應的布局塊、內容塊組成。其中，I序列和布局塊在頁面布局確定后就不再發生變化，并且布局塊還可以在多頁面之間共享。因此，可以為每個頁面建立其對應的I序列并為所有頁面建立統一的布局塊庫。
生成I序列需要知道布局塊與布局塊以及布局塊與內容塊之間的嵌套關系。這些嵌套關系可以在生成布局塊時得到。一個門戶頁面的頁面布局沒有發生變化時，它對應的I序列和布局塊也是不變的。門戶頁面布局確定時，可以同時為該門戶頁面生成其對應的I序列和布局塊，以后有request請求該頁面時，只需要生成其I序列中對應的內容塊即可。
I序列和布局塊是同時生成的，需要兩個步驟：
a)生成布局塊和塊關系表。生成布局塊的過程與正常生成門戶頁面的過程是基本一樣的，均是從頂層布局塊開始計算，依次處理布局信息；不同之處為，生成布局塊時只處理與布局塊有關的部分，不調用portlet產生內容塊。布局塊中不會真正嵌套其他布局塊或內容塊，而是使用常量const_fragment來標志；同時把該布局塊的標志符IL與它所嵌套的子塊的標志符IL/Ic之間的對應關系放入塊關系表中。生成所有的布局塊后，同時在塊關系表中會得到所有塊之間的嵌套關系。布局塊放入布局塊庫中供以后重用；根據塊關系表可以得到頁面對應的I序列。
b)生成I序列。根據前文，I序列表示組成一個門戶頁面的結構塊與內容塊之間的嵌套關系，是門戶頁面對應的LcTree的深度優先遍歷。根據a)得到的塊關系表可以計算出頁面對應的I序列。本文給出一種計算I序列的遞歸算法：
生成的I序列和布局塊會保存在服務器上。對于門戶頁面的每個request請求，門戶服務器會把該頁面對應的I序列作為請求應答。對于應答I序列中的布局塊，客戶端可以使用本地緩存中已有的布局塊或從服務器端獲取本地緩存中沒有的布局塊。
當頁面布局發生變化時，原有的I序列和布局塊有可能會失效。因此，對于頁面布局發生變化的門戶頁面，需要重新計算其對應的I序列和布局塊。
2．2生成和傳遞內容塊的算法
JSR 168規范為portlet定義了基于生命周期的緩存機制。根據規范，門戶服務器可以為response中對應的每個portlet，即為每個內容塊定義一個生命周期；內容塊的存活時間小于其生命周期，則認為該內容塊是可用的[5]。
以下使用TTL表示內容塊的生命周期，CT表示內容塊的生成時間，NT表示服務器當前時間，則對于緩存中的一個內容塊，如果其CT+TTL>NT，認為該內容塊是有效的。
在本方法中，客戶端和服務器端均有緩存。客戶端緩存由服務器端傳遞過來的布局塊和內容塊；服務器端緩存有效的內容塊和布局塊。由上文可知，布局塊一般不會失效，即只要緩存中存在標志符與所需布局塊相同的布局塊，它就是有效的。內容塊是否有效需根據其生成時間和生命周期來判斷。生命周期是由服務器維護的，因此，在服務器端和客戶端的緩存中，緩存內容塊時，除了要保存該內容塊的內容外，還需要保存其生成時間CT。判斷這些內容塊是否有效，需要把緩存中的塊標志符Ic與其對應的生成時間CT傳遞到服務器端；在客戶端，可以通過使用HTTP header:ifmodifysince來實現。仍舊有效的內容塊可以直接使用，只有失效的內容塊才需要由portlet重新生成。
從一個request請求門戶頁面到傳遞完所有數據的步驟為：
a)客戶端發送request到服務器。
b)服務器接收到request，解析出其請求的門戶頁面的URI，判斷該頁面是否有布局變化；若有變化，則重新生成其對應的I序列和布局塊，并緩存；然后從緩存中取出其對應的I序列，返回給客戶端。
c)客戶端接收到服務器返回的I序列，開始獲取I序列中的每個塊。根據本地緩存中是否存在所需要的塊，客戶端發送到服務器的request請求也有所不同。如果本地緩存中沒有所需要的塊，則request請求中只包含所需要的塊的標志信息；否則，request請求中會包含所請求塊的生成時間，即ifmodifysince:CT這樣的信息（布局塊沒有生成時間，使用當前時間NT代替）。
d)服務器接收到請求塊的request，首先解析出所請求的塊，然后根據塊類別的不同進行不同的操作。
(a)所請求的是布局塊：如果request中包含ifmodifysince信息，則什么都不做；否則從緩存中取出所請求的布局塊，并返回給客戶端。
(b)所請求的是內容塊：如果request中包含ifmodifysince信息，并且根據該信息判斷出位于客戶端緩存中的塊依然有效，則什么都不做；否則，判斷位于服務器緩存中的塊是否有效，若有效，則返回服務器緩存中的塊給客戶端；若以上兩次判斷均失敗，則由portlet重新生成該內容塊，然后更新服務器上的緩存，并把該塊及其生成時間CT返回給客戶端。
e）客戶端接收到服務器返回的信息，并根據情況更新本地緩存。以上兩步可以并行操作。
至此，客戶端接收到了所有需要的信息。
2．3組裝頁面的算法
得到頁面對應的I序列和所有布局塊及內容塊后，就可以根據這些信息獲取完整的門戶頁面。由上文可知，布局塊中const_fragment表示其嵌套子塊的位置，而I序列是一個頁面的LcTree的深度優先遍歷。因此，當前塊中的第一個const_fragment所在的位置，即為I序列中下一個塊的位置。依次替換const_fragment為I序列中的塊，即可得到完整的門戶頁面。
3性能評價
3．1實驗方法
為了測試本緩存方法的性能，構造如下模擬實驗。分別向沒有使用緩存和使用緩存的門戶服務器發送頁面請求，然后計算從門戶服務器傳遞而來的數據大小和從請求發出、獲取到完整門戶頁面之間的時間。通過對使用緩存和不使用緩存得到的數據之間的對比來評價本方法的性能。
使用國產網馳平臺中的OncePortal門戶系統作為門戶服務器，并在其上實現了本文中提出的緩存方法。OncePortal系統中一共有100個portlet，使用這些portlet訂制了100個不同類型的頁面供測試訪問。實驗中，設置門戶系統緩存大小為10 MB，使用LRU替換算法。由于要作大批量請求的測試，實現了一個虛擬客戶環境，用于模擬批量用戶對門戶服務器的大量頁面請求。在該虛擬客戶環境中，設置100虛擬客戶端，每個虛擬客戶端60 s/次向服務器發送頁面請求。
實驗中，門戶服務器和虛擬客戶環境分別運行在Pentinum 4 2．80 GHz CPU、512 MB RAM的主機上，兩臺主機之間通過10 Mbps的網絡相連接。
3．2實驗結果
3．2．1網絡帶寬節省情況
根據測試結果，計算出不同請求規模下，平均每次頁面請求所需的網絡傳輸量。圖2為使用緩存和不使用緩存時網絡傳輸量的對比情況。可以看出，不使用緩存時，每次頁面請求所需的網絡傳輸是一定的，大約71 KB；而使用本文提出的緩存方法時，網絡傳輸量明顯減少，最多時可以減少71．8%，頁面請求數最大時，也減少56.4%，這是非常可觀的。
圖2網絡傳輸量對比
3．2．2頁面獲取時間
同樣地，還計算了平均每次發出頁面請求到獲取到完整門戶頁面的時間。圖3為使用緩存和不使用緩存時頁面平均獲取時間的對比情況。可以看出，在本測試環境下，不使用緩存時，每獲取一個頁面大約要800 ms，而使用緩存則可以把頁面獲取時間降低到220~330 ms，節省了大約62%的頁面獲取時間。
4相關工作
近年來，人們對于動態頁面的緩存技術做了大量的研究工作。其中基于塊的緩存成為研究的熱點。Ramaswamy等人[6]提出了一種可以對動態頁面自動分塊的算法。算法中根據動態頁面的HTML代碼生成其對應的DOM樹，并在DOM樹上擴展，添加它所需要的信息，稱這樣的樹為AF樹；Ramaswamy等人的算法中需要保存一系列這樣的AF樹，然后在對應于同一個URI的AF樹之間作比較，從而得出他們認為有意義的片段，即有緩存價值的片段。Debnath等人[7]給出的算法根據指定的HTML標簽，如table等對頁面進行分塊，然后根據塊中標簽信息確定他們認為有內容的片段。這類算法還有很多，它們均是對一系列完整的動態頁面進行分析，進而對其進行分塊。而且某些算法還需要定義某些參數來控制其精確度，這使得這類算法無論在時間、空間的使用上，還是精確方面均存在不足。本文提出的方法，使得在產生門戶頁面的同時就生成了塊，這些塊是根據頁面結構自動劃分的，可以保證其每個分塊均是有緩存價值的。對于客戶端的每個request請求，門戶服務器均只處理需要更新的部分，可以大大節省服務器的處理時間。合理的緩存池替換算法，也使得本方法對空間的要求很低。
Rhea等人[8]提出的VBWC算法根據頁面的文本內容進行分塊。對于一個完整的HTML頁面，VBWC算法對這個頁面中的每個字符進行掃描；當連續的幾個字符滿足某種條件時，便在這幾個字符之后的位置將該HTML頁面切斷。通過這種方式即可對整個HTML頁面進行分塊，每一塊即是一個緩存單位。VBWC算法同樣是對完整的HTML頁面進行分塊，但是它的分塊是語義無關的，僅僅根據字符的排列進行分塊，隨機性太大。分塊太大，緩存命中率會很低；分塊太小則影響緩存性能，且無法保證分出來的塊的大小均勻。本文提出的方法是專門針對門戶系統的，根據在頁面上的具體功能分塊，可保證每個塊均有緩存價值，從而保證緩存的性能。
Mahdavi等人[9，10]提出的協作門戶系統緩存方法是專門針對門戶系統的，可以對每個信息提供者向門戶服務器傳遞信息，如HTML片段等進行緩存。但是Mahdavi等人的算法僅僅是在門戶服務器端對這些信息進行緩存，門戶服務器傳遞給客戶端的仍舊是完整的HTML頁面，依然存在傳遞重復數據的問題。在網絡帶寬有限或受限制的情況下，這樣做效率是非常低下的。本文提出的算法中，門戶服務器只生成更新過的內容塊或結構塊，傳遞給客戶端的也只有I序列和更新過的結構塊或內容塊，這樣可以大大提高網絡帶寬的使用效率。
5結束語
本文介紹了一種緩存方法。該方法法針對門戶系統的特殊性，根據每個門戶頁面的結構，為每個頁面生成一個I序列；I序列中對應的布局塊和內容塊為緩存對象。對于每個來自客戶端的頁面請求，服務器僅僅生成和傳遞該頁面對應的I序列及客戶端緩存中沒有或失效的塊。最后客戶端再根據I序列和相關塊組成完整的門戶頁面。服務器上少量的運算量和網絡上少量的數據傳輸量，可以有效地縮短從發出頁面請求到頁面展示完成的時間。
參考文獻：
［1］JSR 168 Portlet specification [S]．[S.l.]:Java Community Process，2003.
[2］OASIS Web services for remote portlets (WSRP) TC[S]．[S.l.]:OASIS Open， 2003.
[3］MOGUL J， DOUGLIS F， FELDMANN A， et al．Potential benifits of delta encoding and data compression for HTTP[C]//Proc. of ACM SIGCOMM’97 Conf on Application， Technologies， Architectures， and Protocols for Computer Communication．Cannes. France:ACM Press， 1997:181194.
[4］MOGUL J， KRISHNAMURTHY B， DOUGLIS F， et al．RFC 3229 Delta encoding in HTTP[S]．[S.l.]:The Internet Society， 2002.
[5］NUNN G．Portlet caching[EB/OL]．http://dev2dev.bea.com/pub/a/2005/01/portlet_caching.html.
[6］RAMASWAMY L， LYENGAR A， LIU L， et al．Automatic fragment detection in dynamic Web pages and its impact on caching[J]．IEEE Transactions on Knowledge and Data Engineering， 2005，17（6）:859－874.
[7］DEBNATH S， MITRA P， PAL N， et al．Automatic identification of informative sections of Web pages[J]．IEEE Transactions on Knowledge and Data Engineering，2005，17(9):12331246.
[8］RHEA S C， LIANG K， BREWER E．Valuebased Web caching[C]//Proc of the 12th Int’l Conf on World Wide Web．Budapest. Hungary:ACM Press， 2003:619－628.
[9］MAHDAVI M， SHEPHERD J．Enabling dynamic content caching in Web portals[C]//Proc of the 14th Int’l Workshop on Research Issues on Data Engineering:Web Services for Ecommerce and Egovenment Applications(RIDE’04)．Washington， DC:IEEE Computer Society， 2004:129136.
[10］MAHADVI M， SHEPHERD J， BENATALLAH B．A collaborative approach for caching dynamic data in portal applications[C]//Proc of the 15th Conf on Australasian Database Dunedin. New Zealand:Australian Computer Society， Inc， 2004:181188.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
