基于超市模型的文件復制策略

摘要：為了有效地對文件復制進行管理，在資源網格中引入了超市模型，提出了基于超市模型的文件復制管理策略，利用超市模型與疊層復制相結合的方法來復制文件的副本，使文件復制過程中既有推力也有拉力，提高了整體系統效率。

關鍵詞：網格； 復制； 超市模型； 副本； 虛擬組織

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)04－1230－03

網格是一個廣域的、大規模分布的計算系統，在一個通用的面向服務的軟件架構下，能夠集成遠程定位、斷開、分散處理和數據存儲設備[1，2]。在網格中，個人計算機節點上存儲能力的有限性，數據被廣泛地分布在網格中的各個節點上，但是對網格中的所有節點要有相同的讀取能力。因此，使用局部緩存策略來減少網絡延遲，網絡延遲可增加讀取遠程數據的開銷。

在網格系統中，一個有效提高可用性的方法是復制。如果數據的多個副本存放在獨立節點上，讀取數據的成功率就會增大。如果副本和對副本的請求合理地分布，數據讀取性能將會增加，并且整個網絡的負載將會減少。通過將數據復制的節點接近于應用節點，則會減少應用對數據的讀取延遲，從而提高整個系統的讀取性能。

通過復制文件到網格cache中，可以實現快速文件讀取，并提高整個系統的可靠性。復制系統的性能依靠很多因素，如文件的放置和大小、網絡的帶寬和延遲、系統可靠性等。目前有六種復制策略：無復制或緩存策略、最佳客戶策略、疊層復制策略、緩存＋疊層復制策略和快速擴展策略。本文提出了一種基于超市模型的文件復制管理方法，通過模擬現實生活中的超市的運作原理，主動分析文件的需求情況來實現對文件復制的管理，并實現副本管理系統的全局最優性。

1相關工作

網格系統是一種無縫的、集成的資源共享和協作環境，其目標是協調網格中資源的使用，以便及時地響應網格用戶的資源請求。但是，網絡傳輸會造成相當大的延遲，尤其是當用戶所訪問的資源非常大時延遲就會更大，再加上網格中資源能力的不均衡和異構特性給系統造成的瓶頸，這些均會引起客戶端延遲[3]。

為了解決網格傳輸瓶頸帶來的問題，引入了cache技術[3]，對常用的資源進行緩存，從而減少傳輸所造成的時延，使網格的性能得以提高。網格cache指存儲能力強于本地磁盤弱于主存節點的暫時性存儲。使用cache可以減少多個任務使用相同資源時的重復傳輸，既減少了帶寬占用、緩存中央服務器的負載，也降低了異構系統間因傳輸造成的處理開銷。

網格cache由SRM（storage resource management）管理。在網格中SRM本質上就是一個中間件，其作用是使共享數據和資源更加靈活[4]。一個SRM管理一個大容量的磁盤cache用于緩存從MSS（mass storage system）讀出或寫入MSS的對象，其功能是依靠一系列的cache策略（如cache替換策略、文件緩存策略等）來實現的。

2超市模型

復制技術已經被廣泛地研究，并且許多分布的副本管理策略已經提出[5~7]。網格是一個動態的環境，副本的數量和位置也是動態變化的。副本管理服務解決資源復制的三個基本問題，即復制哪個資源，何時復制及復制到何處。當文件被訪問的次數達到一定閾值時，就對文件進行復制。在本文中，文件復制的策略則由副本管理服務根據超市模型來實現。

2．1超市模型的原理

超市模型是通過模擬現實中超市管理其商品的行為，提出來的一種新型的模擬物流算法。現實生活中，超市根據顧客對物品的需求及興趣等情況作分析、比較，從而買進最適合顧客需求的物品來增加自己的銷售額。

引入超市模型主要是為了使信息在傳遞過程中既有推力也有拉力，使網格cache主動地統計文件的使用情況，并主動地緩存文件。整個模型可以按照圖1中的三種類型的節點來考慮。



在網格系統中，每個節點既是消費者也是生產者，而超市則由網格cache來充當，網格cache中存儲的文件副本，則根據提出的超市模型來決定。

2．2超市模型與網格中節點的關系

現實中的超市、生產者、消費者三者之間存在著非常松散的耦合關系：超市并不關心每個用戶的興趣愛好，而用戶也不用把自己的興趣告訴超市，超市完全靠數據統計和分析來為用戶提供更好的服務。

a)以節點作為生產者來說，為了讓自己的資源獲得最大的收益，其自身存儲的信息不只存放在本地超市，還可根據市場需求將信息發布到其他超市。

b)作為超市的網格cache，其中存放的信息主要是滿足本地用戶的需要。超市負責對產品信息進行分類。若本地用戶查詢的信息在本地超市不存在，超市向其他超市發出請求，通過對其他超市的查詢得到產品的信息，然后返回給客戶。超市為了獲得最大的效益，可根據自身得到的數據，對產品信息進行更新。為了保證產品交易的公平性超市根據市場對產品進行定價。

c)以節點作為消費者來說，為了得到自己的信息首先在本地進行查詢，如果本地沒有該信息，系統自動到本地超市進行查詢；若本地超市中沒有所需求的信息，則可到其他非本地超市查詢，并將查詢結果返回給用戶。

3基于超市模型的復制策略

3．1副本分布拓撲

為了實現上述超市模型的復制策略，筆者將整個網格系統按地理分布上的特性分成若干個虛擬組織（virtual organization）。一個虛擬組織指有一部分網格資源節點的集合，這些節點通過局域網連接在一起。多個VO通過廣域網的連接，相互之間可以共享網絡中的資源。本文采用文獻[8]中的樹型網絡拓撲結構。如圖2所示，四個VO組成基于樹的拓撲結構。



每個VO內，每個節點本身開辟一個空間來充當cache，稱之為本地cache，用來存放從其他節點獲取的文件副本信息，而每個VO內有一個本地的cache，稱之為目錄cache，用來存放整個VO內的文件副本的目錄信息和從其他VO獲得的文件的副本信息，所有VO內的目錄cache由一個全局的中心cache來管理。三種不同的cache內，維持一個副本路由表，完成Globus toolkit中副本目錄的一部分功能，除了表示邏輯文件名與物理文件名的映射外，還可以定位最近的副本節點。每隔一段時間間隔，當副本狀態發生變化時如副本的刪除和創建，副本路由表也應當相應地更新。越靠近根節點，其cache的存儲容量越大。用戶節點放在最低層。

對于cache的管理，筆者采用文獻[9]提出的樹和環相結合的混合拓撲結構。這種結構反映了客戶—服務器模式的使用和用P2P模式來開發位置，并且具有高帶寬利用率來減少數據讀取時間。在客戶—服務器模式中，維持副本一致性的代價要比P2P模式大。對同一層上的節點，用環形將其相互連接起來，以便相互之間查詢的需要和同層間數據的讀取。因此，基于上述，所有的cache可組織成如圖3所示的樹型結構。



3．2文件復制原理

基于超市模型的文件副本的管理，可以分為兩層，即VO內文件副本的管理和網格系統中所有VO的文件副本的管理。步驟如下：

a)VO內文件副本的管理

(a）單個節點角度上，若某個節點對某個文件的訪問率超過一定閾值，則根據疊層復制原理[8]將該文件的副本拷貝到節點上的本地cache中。

(b）一個VO系統角度上，每個VO中的目錄cache，統計本VO內文件的訪問情況（如統計出哪些文件經常被訪問，被哪個節點經常訪問），將經常被訪問的文件副本復制到經常訪問它的并且訪問次數超過一定閾值的節點上（若該節點沒有該文件的副本則復制，若已有該文件的副本則不必復制）。

b)網格系統中所有VO的文件副本的管理

(a)某個VO內的節點要訪問的文件不在本VO內，則向其他所有VO的目錄cache發送查詢請求，若其他VO有該文件則返回該文件，沒有則返回無。若該VO對該文件的訪問次數超過一定閾值，則復制該文件的地址信息到該VO的目錄cache中，此時并不復制文件。過一定的時間間隔后，若對該文件的訪問次數仍超過一定閾值，則此時復制該文件的副本到VO的目錄cache中。

(b)中心cache節點統計全局內文件的訪問情況（如統計出哪些文件經常被訪問，經常被哪個節點訪問），將經常訪問的文件的地址復制到經常訪問它的VO的目錄cache內（若該VO內沒有該文件及其副本）。過一定的時間間隔后，若該文件仍被VO的訪問次數超過一定閾值，則復制該文件的副本到VO內的目錄cache中。

當有新的副本創建時，會發送信息到它的兄弟和孩子節點，同時副本路由表相應地更新，以維持副本路由表和副本的一致性。由于節點上的cache空間是有限的，當存儲空間滿時，必須刪除相應的副本來釋放空間以存放其他更加被經常訪問的文件的副本。本文采用LFU（least frequently used algorithm）最少訪問頻率的方法，即用新的副本替換最小訪問頻率的副本。

VO內文件復制和整個VO系統的文件復制管理，筆者采用超市模型的兩種不同的策略；VO內文件復制管理，筆者采用疊層復制與超市模型相結合的管理方式，而整個VO系統則采用二次復制的方式。因為在網格系統中對文件的訪問情況是高度動態變化的，采用二次復制，避免由于文件從很高的訪問頻率突然降到很低的訪問頻率時而引起的對文件的復制，從而造成存儲空間的浪費和網絡性能的下降。

基于超市模型的文件復制策略，不僅可以使節點主動地根據自己的需求來復制文件，使節點對信息的流通起到一定的推動作用，并且由于目錄cache和中心cache還可以根據系統中文件的全局使用情況對文件復制，起到一定的拉力作用。通過系統不斷地學習，系統的檢索效率會不斷地提高。

4策略分析

文獻[5]中提出的文件復制策略有兩個度量參數，即平均響應時間和完全完成時的帶寬消耗。響應時間指從一個節點對一個文件發出需求，到該節點完全接收所需的時間。如果一個本地cache中該文件的拷貝存在，則該響應時間為0。帶寬消耗包括在節點發生請求時，也包括在服務器產生復制時。最好的復制策略即是低時間消耗，又是低帶寬占用。但所有的策略不需要兩個都減少。

基于超市模型的文件復制管理策略，利用了現實生活中超市的運作原理，現實中超市根據自身的銷售情況及時調整自己的商品的種類及數量，以最大化超市自身的效益，使超市自身承擔最小的風險，并獲得較大的收益。基于超市模型的文件復制管理策略優點如下：

a)超市模型的管理方式和疊層復制相結合的方法來復制文件，充分利用了超市模型的主動性和疊層復制的最小平均響應時間性。

b)將對文件的復制分為VO內部和整個VO系統的文件復制。不管是內部還是外部均利用了超市模型來管理，使對文件的復制不管在VO內部還是整體均具有一定的主動性。

c)對整個VO系統的文件復制，本文還采用了二次復制的方式，即第一次先不復制文件而是復制文件的地址。若對文件的訪問量仍很高時，第二次再復制文件的副本。這種方式有利于下述情況：若在某一個時間段內對文件的訪問量很高，但過一段時間后，對文件的訪問量馬上降低的情況。這樣，避免了當對文件訪問量很高時馬上就復制文件而帶來的系統開銷（如帶寬消耗、占用系統時間、占用cache空間等）。

d)利用超市模型，使對文件的復制具有主動性。以前的文件復制管理策略均是被動地復制文件的副本。而本文中，中心節點會根據整個系統對文件的訪問情況作出判斷，從宏觀的角度來放置文件的副本到適當的節點，即相當于超市根據當前消費者的消費情況提前對消費者的需求作出推斷，并適量地批發該商品。

綜上所述，基于超市模型的文件復制管理策略可以減少平均響應時間和帶寬消耗。其缺點是不能精確地確定間隔時間。若間隔時間太短，則不能適應網格的動態性；若間隔時間太長，則失去了超市模型的文件復制的主動性。

5結束語

本文討論了基于超市模型的文件復制管理策略。利用超市模型與疊層復制相結合的方法來復制文件的副本，使文件復制過程中既有推力也有拉力，并且提出了二次復制策略，避免由于文件訪問頻率由高突然變低而造成的存儲空間的浪費和帶寬的消耗。策略分析顯示通過系統不斷地學習，使整個系統的總體性能不斷提高。

參考文獻：

［1］FOSTER I， KESSELMAN C. The grid: blueprint for a new computing infrastructure[M]. San Fransisco，CA: Morgan Kaufmann， 1999.

[2］FOSTER I， KESSELMAN C， TUECKE S.The anatomy of the grid:enabling scalable virtual organizations[J]. International Journal of High Performance Computing Applications，2001，15(3):200－222.

[3］陳梅，都志輝.網格cache若干問題分析[J].計算機科學，2004，31（5）：15－17.

[4］OTOO E， SHOSHANI A. Accurate modeling of cache replacement policies in a data grid[C]//Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies(MSS’03).San Diego: [s.n.]， 2003.

[5］何炎祥，范清風，張力飛.網格計算中動態復制策略的設計[J].計算機工程， 2004(3):94－98.

[6］GWERTZMAN J S， SELTZER M. The case for geographical push－caching[C]//Proc of the 5th Workshop on Hot Topics in Operating Systems. 1995.

[7］MICHEL S， NGUYEN K， ROSENSTEIN A，et al. Adaptive Web caching:towards a new global caching architecture[C]//Proc of the 3nd International WWW Caching Workshop. 1998.

[8］NAM D S，YOUN C H. An efficient replication scheme for data grids[C]//Proc ofIEEE International Conference on Cluster Computing. 2004:392－395.

[9］LAMEHAMEDI H，SHENTU Z，SZYMANSKI B，et al. Simulation of dynamic data replication strategies in data grids[C]//Proc of the 12th Heterogeneous Computing Workshop.Nice，France:[s.n.]，2003.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”