一種對象存儲設備中自適應動態預取策略

摘 要：在對象存儲系統中，對象存儲設備具有很高的智能和處理能力，它負責對象及其屬性的數據組織和管理，向外提供基于對象的訪問接口。每個對象均具有屬性，它反映了對象的某些特征。通過為每個對象自定義一個預取屬性頁，對用戶訪問對象存儲設備的規律進行智能的自我學習，從而實現一種高效的、自適應的動態預取算法，可以提高對象存儲設備的預取命中率，從而提高對象存儲設備的性能。

關鍵詞：對象存儲設備； 對象屬性； 自適應預取

中圖法分類號：TP393 文獻標識碼：A 文章編號：1001-3695(2006)10-0054-03

Adaptive Dynamic Prefetching Policy on ObjectBased Storage Device

GONG Wei， FENG Dan， QIN Lingjun

(Key Laboratory of Data Storage System， Ministry of Education， Huazhong University of Science Technology， Wuhan Hubei 430074， China)

Abstract:ObjectBased Storage Device(OBSD) has intelligence and processing ability， which is responsible for managing objects as well as their attributes， and provides objectbased interface to the storage system. Every object has attributes which reflects some of its characteristics. OBSD can learn users’ accessing regularity through defining a “prefetch” attribute page for every object. An adaptive prefetching algorithm with great efficiency is achieved， and prefetch hit rate is increased， ultimately OBSD’s capability is improved.

Key words:ObjectBased Storage Device(OBSD); Object Attribute; Adaptive Prefetching

現在計算機系統的計算能力和網絡傳輸能力均有了顯著提高，而存儲系統卻成為計算機進一步發展的瓶頸。傳統的存儲系統體系結構暴露出的各種問題使得存儲系統在性能、可靠性和安全性上很難再有更大的提高。對象存儲系統（ObjectBased Storage System， OBSS）概念[1，2]的提出在一定程度上緩解了這種壓力。

傳統的存儲系統均以數據塊或文件為訪問接口提供給用戶使用，它們都在不同程度上存在著缺陷。以數據塊為基本傳輸單元，在存儲管理和數據共享方面代價比較大；以文件為基本傳輸單元，在性能上受限制于文件服務器。對象存儲系統以對象為基本傳輸單元。其繼承了以數據塊為訪問接口時的高性能和以文件為訪問接口時的安全性及跨平臺的可操作性。對象是可變長的，可包含任何類型的數據，如文件、數據庫記錄、圖像以及多媒體視頻/音頻等，至于包含何種類型數據由應用決定。對象還具有屬性，用于描述對象的特征，如多媒體數據對象的QoS屬性描述了該對象的網絡延遲要求[3]。對象存儲系統的實現得益于集成電路技術的高速發展和嵌入式系統的流行，它使存儲設備本身具有很高的處理能力和智能成為可能。

預取策略是提高存儲系統性能的主要方法之一。傳統的存儲系統中，存儲設備本身很難實現高效的預測，這主要有以下兩方面的原因：①以數據塊為訪問接口的系統（如SAN）中，數據塊的管理相當復雜，而且主要依賴于中心管理器，存儲設備本身只能被動響應中心管理器的訪問請求，在存儲設備端很難實現高效的預取算法；②以文件為訪問接口的系統（如NAS）中，文件服務器本身負載就很大，而預取策略需要文件服務器直接參與，其效率很難提高。在對象存儲系統中，存儲設備本身具有很強的處理能力和智能，在它之上實現對象一級的預取策略對提高存儲設備的性能有很大幫助。

本文根據當前存儲系統應用的一些特點，結合對象存儲設備自身的優點，提出了一種對象存儲設備(Object Based Storage Device，OBSD)中高效的自適應預取策略，并分析了影響預取策略的各種因素。

1 對象存儲系統（OBSS）和對象存儲設備（OBSD）

對象存儲系統的體系結構如圖1所示。高速網絡將用戶、元數據服務器（Metadata Server，MDS）和對象存儲設備（OBSD）連接起來。OBSS實現一個基于對象的分布式文件系統；MDS提供全局名字空間，管理文件到對象的映射，提供身份驗證等安全機制；OBSD則向外提供對象接口，以對象作為存取單元。用戶訪問文件時先向元數據服務器發送請求，獲取文件的信息（如文件由哪些對象組成以及對象所在的設備等）及訪問證書，然后客戶與OBSD直接交互；OBSD收到客戶請求后，對其身份進行認證，然后執行客戶的對象讀寫請求。在這里客戶向OBSD發送的I/O請求與基于塊的I/O請求不同，僅包括對象ID、對象的偏移地址以及長度。OBSD包括CPU、Memory、網絡接口以及塊設備接口，管理對象存儲空間的分配、數據組織以及對象的屬性[1，2]。對象存儲系統的最大好處之一就是將底層的數據組織和同步操作交由OBSD管理，這就大大減輕了用戶端和元數據服務器的負擔，同時也提高了整個系統的并行性和可擴展性[4]。

對象的屬性可以描述對象的各種特征，加上OBSD上集成處理能力[5]，我們可以合理地利用對象的屬性在OBSD端實現高效的自適應預取策略。后面將詳細描述如何利用對象屬性在OBSD上實現的一種高效的、自適應的預取策略。

2 自適應動態預取策略

在對象存儲設備中，提供給用戶的是以對象為單位的邏輯視圖[5]。而對象的屬性能反映對象的某些特性，如對象的總訪問次數、最后一次訪問時間等。這就為在對象存儲設備中實現高效的預取策略提供了基本條件。在對象存儲系統中，對象本身是一個有結構和特定意義的數據載體，它可以是個數據庫中的表，描述一些字段之間的聯系；也可以是一段精彩的多媒體視頻，描述一部電影中最精彩的部分[2]。這使得用戶訪問OBSD中的對象時具有一定的特征，他們在一段時間內訪問的對象會存在一定的聯系。比如，當用戶訪問一個保存在數據庫中一張表的對象時，用戶可能會很快就訪問與此表相關的其他對象；當用戶訪問一段電影片斷時，用戶可能會很快訪問這部電影的下一個片斷[6，7]?；谶@一特性，本文提出了一種具有自我學習能力的自適應預取策略。根據不同的應用，適當調整預取策略中對預取屬性頁的屬性設置和對屬性頁的各種操作，以便滿足不同的應用需求。

在對象存儲系統中，用戶除了能對OBSD中的對象進行讀寫外，還可以對對象的屬性進行操作[2]。對象的屬性除了標準中定義的公共屬性外，還可以自定義屬性[2]，他們均作為對對象某些特征的描述。用戶可以為了滿足特殊應用的需要而為每個對象自定義一些標志對象特征的屬性。比如在流媒體中，就可以為每個對象定義一個QoS屬性，標志對象中所包含的流媒體數據需要的最小延遲和網絡帶寬等。為了實現高效的智能預取，我們在對象存儲設備中為每個對象定義一個預取屬性頁。屬性頁中有L條屬性。每條屬性記錄一個對象ID、訪問次數和最后一次訪問時間，其中第一條屬性記錄該屬性所屬對象的ID號、訪問次數和最后一次訪問時間。每當訪問對象A時，預取屬性頁中第一條屬性的訪問次數加1，最后一次訪問時間更新為當前時間，該屬性頁后面的L-1條屬性遵循以下規則進行刷新：

（1）當系統訪問完對象A后，接著訪問B，則在預取屬性頁中查找是否存在對象B的ID。如果存在，則將屬性中的訪問次數加1，最后一次訪問時間改為當前時間；如果不存在，則添加一條新的屬性，屬性中的ID號為對象B的ID號，訪問次數為1，最后一次訪問時間改為當前時間。

（2）屬性頁中L條屬性沒有填滿時，該屬性頁中的記錄依次按照規則（1）進行添加；屬性頁中L條記錄均填滿后，則根據公式：

Attr_out=k·nTlast_to_now

計算每個屬性的Attr_out值，將值最小的那條屬性刪除，并按照規則（1）添加新的屬性。其中n為屬性中對象的訪問次數，Tlast_to_now為對象的最后一次訪問時間與當前時間的時間差，k為常數。

按照上述規則，當用戶對OBSD進行了若干次訪問后，OBSD中的每個對象均創建了相應的如表1所示的預取屬性頁，根據預取屬性頁便可以實現如下的預取算法。

設對象A在某個時間段內的訪問次數（即對象A的預取屬性頁的第一個屬性中的訪問次數）為CA，用戶訪問完對象A后接著訪問對象B的次數（即對象A的預取屬性頁中對象ID為B的對象ID屬性中的訪問次數）為CAB，根據如下公式計算對象B的訪問概率[7，8]：

P(B|A)=CABCA對象B在A的預設屬性頁

P（B|A）=0 對象B不在A的預設屬性頁

由于系統的CPU，Memory等資源有限，我們設定一個動態的預取極限H（0≤H＜1），當用戶訪問對象A時，OBSD就根據對象A的預取屬性頁計算出訪問概率大于預取極限H的若干個對象，并將其預取到對象存儲設備的內存中。這樣，當用戶對OBSD進行了若干次的訪問后，對象的預取屬性頁就能很好地反映用戶對OBSD中對象訪問在先后關系上的興趣。以流媒體為例，OBSD中存放的對象均是多媒體數據，當用戶對OBSD進行了一定時間的訪問后，對象的預取屬性頁就能反映出用戶訪問完一段視頻后，下一個極有可能訪問的對象。與此同時，隨著用戶對OBSD的不斷訪問，對象的預取屬性頁也要進行相應的更新，它將隨著用戶對OBSD中對象訪問興趣的變化而變化。這就使得此預取策略有一定的自我學習的智能。預取對象時，與哪些系統資源有關，預取多少對象最為合適將在下一節進行詳細分析。

3 算法分析

為了分析方便，我們假設對象存儲設備中的對象保存在磁盤上的一個連續區域中，這樣當訪問某個對象時，磁盤定位到對象起始位置后便可以連續讀取該對象。我們利用代價函數對算法進行分析。設αw為設備訪問對象時定位到該對象的起始位置所付出的代價，它與磁盤的尋道速度，對象在磁盤上存放的位置有關；αr為將單位大小的數據從磁盤介質上讀到內存中（或將內存中的數據寫到磁盤上）的代價，它與磁盤的讀寫速度，系統可利用的CPU、內存等資源有關；b為OBSD網絡帶寬，它與當前的網絡負載有關；at為在單位時間內通過網絡傳輸數據所需的代價，它與OBSD的處理能力以及用戶要求OBSD對對象作何處理有關。下面將對用戶訪問OBSD時，預取策略的相關代價函數進行分析。

用戶對某個OBSD進行了一段時間的訪問后，當用戶請求一個對象而此對象并沒有被OBSD預取時，用戶訪問此對象的代價就與設備的系統負載以及網絡傳輸有關，設其代價為

C1=αw+αr·S+αt·tt=αw+αr·S+αt·Sb(1)

其中S為對象的大小。如果用戶請求的對象已經被存儲設備預取到內存中，則用戶請求的對象只需要從對象存儲設備的內存中傳輸給用戶即可，這時的代價為

C2=αt·Sb(2)

根據以上的分析，我們現在假設用戶請求一個新的對象，此對象的屬性頁中有m個對象的訪問概率P大于0。這時若要滿足用戶的下一個請求，在沒有預取的情況下，其平均代價C3為

C3=∑mi=1Pi·αw+αr·si+αt·Sibi(3)

其中，Pi為對象i的訪問概率，Si為對象i的大小，bi為傳輸對象i時的網絡傳輸能力。如果在m個對象中，有n個對象已經在設備端進行了預取，那么這時的平均代價C4為

C4=∑ni=1αt·Sibi+∑mi=n+1Pi·αw+αr·Si+αi·Sibi(4)

比較式（3）和式（4）可以得到，要想C4的值最小，就必須預取滿足以下條件的對象：

P＞1bαt·αwS+αr+1(5)

我們定義

H=1bαt·αwS+αr+1(6)

為預取極限。從式（6）中可以看出，隨著αw和αr增大，預取極限H就越小，OBSD就可以預取更多的對象，有助于提高命中率。這說明，提高OBSD上磁盤的讀寫速度，以及盡量使對象存放在磁盤上的連續區域從而減少磁盤在讀取對象時的定位時間可以提高OBSD的預取效率；另一方面，OBSD的網絡帶寬也影響OBSD的預取。合理地利用網絡帶寬，并在多個OBSD之間進行負載平衡，將有利于OBSD的預取效率。預取極限H還與αt有關，OBSD本身的處理能力越強，其預取極限H越小，因此OBSD大多采用高性能的嵌入式系統進行設計與開發。

我們以流媒體服務器為例對以上算法進行驗證。在OBSD中存放1 000個多媒體影片對象，并讓用戶對OBSD進行長時間的訪問。編寫程序實現以上描述的自適應預取算法，并將用戶對OBSD中對象的訪問次數和預取的命中率進行記錄。為了證明上述算法的智能性，我們記錄了用戶對OBSD不同訪問次數下的預取命中率，在測試平臺上設置了不同的預取極限，得到的結果如圖2所示。

從圖2中我們很明顯地看到，當用戶的訪問次數達到一定值后，OBSD對用戶的興趣進行了有效的學習，預取的命中率能維持在一個穩定的水平上。這就充分證明，以上描述的算法具有很高的智能和自我學習能力。預取命中率的大小取決于預取極限H的值，因此，提高OBSD本身的處理能力有助于提高OBSD的命中率。

比較普通的預取算法和自適應預取算法的命中率。普通的預取算法一般都是根據目前訪問的對象，預取緊接著的若干個對象，它是一種靜態的預取。我們使用了同樣的測試平臺，OBSD中存放1 000個多媒體影片對象，讓用戶按照同樣的訪問方式對兩個OBSD進行訪問，分別記錄下兩個OBSD中隨著用戶對OBSD訪問次數的增加，其預取對象的命中率。圖3是對兩種算法的比較結果。

從圖3中可以看出，對于流媒體服務器而言，自適應的動態預取策略能夠很好地學習用戶訪問多媒體對象的興趣。隨著用戶對OBSD訪問次數的增加，預取的命中率能穩定在一個較高的水平，它比靜態的預取相鄰對象預取策略的命中率高出近一倍，其動態的自我學習能力體現得相當明顯。

4 結論

在對象存儲系統中，對象的屬性能反映對象的某些特征。自定義的對象屬性能針對用戶不同的應用描述用戶訪問OBSD中對象的訪問興趣。借助自定義預取屬性的預取策略，能夠根據用戶對OBSD的訪問情況進行實時的自我學習，從而實現高效的智能預取。它較普通的預取策略在命中率上有較大的提高。

參考文獻：

[1]M Mesnier， G R Ganger， E Riedel. Objectbased Storage[J]. IEEE Communications Magazine，2003，41(8):84-90.

[2]J Satran. Objectbased Storage Device Commands[EB/OL]. http://www.t10.org/draft/osd， 2004.

[3]Lu Y， Du D H C， Ruwart T. QoS Provisioning Framework for an OSDbased Storage System[C]. Proceeding of the 22nd IEEE/the 13th NASA Goddard Conference on Mass Storage Systems and Technologies， 2005.28-35.

[4]Richard Hedges， Bill Loewe. Parallel File System Testing for the Lunatic Fringe: The Care and Feeding of Restless I/O Power Users[C]. Proceeding of the 22nd IEEE/the 13th NASA Goddard Conference on Mass Storage Systems and Technologies， 2005.317.

[5]Dan Feng， Lingjun Qin， LingFang Zeng， et al. A Scalable Objectbased Intelligent Storage Device[C]. Proceeding of the 3rd International Conference on Machine Learning and Cybernetics， 2004.387-391.

[6]Philip A， Bernstein， Shankar Pal. Contextbased Prefetch for Implementing Objects on Relations[C]. Proceeding of the 25th VLDB Conference， 1999.102107.

[7]Zhimei Jiang. An Adaptive Network Prefetch Scheme[C]. IEEE International Conference on Communications，1998.812.

[8]Zheng Zhao， Jie Yang. Measurement Based Intelligent Prefetch and Cache Technique in Web[C].Proceeding of the 1999 IEEE Canadian Conference on Electrical and Computer Engineering， 1999.912.

作者簡介：

龔瑋（1981-），男，湖北鄂州人，碩士研究生，主要研究方向為網絡存儲系統；馮丹(1971-)，女，湖北金山人，教授，博導，主要研究方向為網絡存儲系統、計算機高速接口通道；覃靈軍（1975-），男，廣西柳州人，博士研究生，主要研究方向為對象存儲系統。

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