一種對象文件系統的預取方法
2023-04-29 04:44:16
一種對象文件系統的預取方法【專利摘要】本發明公開了一種對象文件系統的預取方法，包括：對對象文件系統的數據結構和變量進行初始化，判斷伺服器是否接收來自客戶端的讀對象請求，如果是則解析讀對象請求，並根據讀對象請求確定當前對象及其Oid，判斷讀對象請求是否命中緩存，如果沒有則判斷是否存在計時值大於或等於時間閾值T_MAX，如果不存在，則根據當前對象的Oid查詢預取屬性表，以獲取當前對象的預取屬性，並根據預取屬性執行讀磁碟和預取操作，根據全局訪問順序數組對預取屬性表的單步預取信息進行修改，根據全局訪問順序數組對預取屬性表的多步預取信息進行修改。本發明實現了預取範圍自適應調節、預取準確率維持在設定閾值附近、單步預取和多步預取兼顧、以及資源佔用可控。【專利說明】一種對象文件系統的預取方法【
技術領域：
】[0001]本發明屬於預取【
技術領域：
】，更具體地，涉及一種對象文件系統的預取方法。【
背景技術：
】[0002]信息技術的發展帶來了日益增長的海量數據，存儲需求增加迅速、存儲應用日益複雜。傳統的基於塊接口的存儲系統難以滿足安全性、跨平臺數據共享、高性能及可擴展性等要求，因此出現了一種基於對象的接口，基於對象的存儲提供了具有高性能、高可靠性、跨平臺以及安全的數據共享的存儲體系結構，在海量數據的應用場景下性能表現優秀。[0003]但是存儲設備的性能提升速度遠遠落後於存儲密度的提高速度，因此對象文件系統也不可避免的遇到了I/o瓶頸的問題。在存儲設備I/O性能提升有限的情況下，採用小容量高速存儲介質來提高系統性能已經成為普遍做法。而利用預取技術能實現處理器請求數據之前從系統存儲器請求該數據，實現處理器不間斷的連續處理多個數據，利用數據訪問的空間局部性，對將來可能發生的數據請求進行預測，在訪問之前取出並緩存，以備用戶訪問，從而減少訪問延遲，加快了讀取速度，提升了系統的讀性能。[0004]幾種常見的預取算法包括:[0005]LS(LastSuccessor):以最近的訪問後繼作為下次訪問的預測,簡潔實用，對訪問模式的反映快，但易受偶然因素、訪問順序的影響。[0006]PNLS(Program-basedLastNSuccessors):以程序信息提高預測精度,適用於程序驅動的數據訪問模式。[0007]SLS(StableLastSuccessor):對LS模型的重新定義,設置頻次閾值,去除噪音，降低偶然因素對模型性能的影響。[0008]FSS(FirstStableSuccessor):以首個出現N次的後繼永久作為預測結果,適用於穩定的模式。[0009]RecentPopularity(koutofη):維護N個最近後繼,至少發生了K次的作為預測結果，當存在多個侯選時，以最近度作為選擇依據。[0010]上述預取方法基本都是通過簡單固定的預取策略來滿足特定訪問模式的需求，且預測的都是下一步的可能訪問。顯然，如果能夠預測到後續多步的訪問順序能夠更好地提升系統性能，但是這需要更大規模量的數據記錄及其內在關聯的分析。[0011]在複雜多變的應用場景下，單一固定的預取方法反而可能造成性能的急劇下降，一個高效的預取方法應當能適應複雜應用場景，在多種場景下動態的調整預取策略，並且在一定規模數據採集量下達到性能的最優化。【
發明內容】[0012]針對現有技術的缺陷，本發明的目的在於提供一種對象文件系統的預取方法，其基於單步訪問順序的數據統計，同步支持單步和多步預取，並根據後續實際訪問結果實時修正預取策略，從而實現了預取範圍自適應調節、預取準確率維持在設定閾值附近、單步預取和多步預取兼顧、以及資源佔用可控。[0013]為實現上述目的，本發明提供了一種對象文件系統的預取方法，包括以下步驟:[0014](I)對對象文件系統的數據結構和變量進行初始化；具體而言，初始化內存池且將表示內存池使用率的全局變量Urate置0，創建並初始化一個具有Bucket_Num個哈希桶的哈希表，申請並初始化一個全局訪問順序數組Access_0rder[Μ+1],其中M表示多步預測的最大步長，數組中的每個元素用於存放對象的Oid，Access_0rder[Μ]為當前訪問對象的Oid,將計時值T_Clock設置為0，且系統每隔一秒T_Clock值加I;[0015](2)判斷伺服器是否接收來自客戶端的讀對象請求，如果是則進入步驟(3)，否則過程結束；[0016](3)解析讀對象請求，並根據讀對象請求確定當前對象及其Oid；[0017](4)判斷讀對象請求是否命中緩存，如果是進入步驟(5)，否則進入步驟(6)；[0018](5)根據當前對象的Oid在內存池中查找對應的緩存空間，並從緩存空間中直接讀取當前對象，然後進入步驟(10)；[0019](6)判斷是否存在計時值T_Clock大於或等於時間閾值T_MAX，如果存在，則表示時間窗口已到，並進入步驟(7)，否則進入步驟(9)；[0020](7)初始化預取屬性表，並將計時值T_Clock置O;[0021](8)從磁碟中讀取讀對象請求的對象，然後進入步驟(10)。[0022](9)根據當前對象的Oid查詢預取屬性表，以獲取當前對象的預取屬性，並根據預取屬性執行讀磁碟和預取操作；[0023](10)根據全局訪問順序數組Access_0rder[M+1]對預取屬性表的單步預取信息進行修改；[0024](11)根據全局訪問順序數組Access_0rder[M+1]對預取屬性表的多步預取信息進行修改。[0025]步驟(7)具體為，將預取屬性表中的所有節點初始化，清空時間閾值T_MAX前一段時間內的統計數據，包括將預取屬性節點中的訪問計數值Visit_Num置O、預取成功次數數組Prefetch_Vnum[M]、預取準確率數組Prefetch_Crate[Μ]、預取大小數組Prefetch_Size[2]、多步預取序列數組Multi_Step[M]設置為零，釋放預取屬性節點中單步預取對列所佔用的內存空間並置指針Psingle為空，並初始化全局訪問順序數組Access_Order[M+1]為零。[0026]步驟(9)包括以下子步驟:[0027](9-1)記錄與對象訪問順序有關的信息，並將當前對象Oid寫入全局訪問順序數組Access_0rder[M+1]；[0028](9-2)判斷預取屬性表中是否存在當前對象對應的預取屬性節點，如不存在則進入步驟(9-3)，否則進入步驟(9-4)。[0029](9-3)為當前對象建立對應的預取屬性節點；[0030](9-4)更新當前對象的預取屬性信息,包括訪問計數值Visit—Num和多步預取序列數組Multi_Step[M]；[0031](9-5)從當前對象對應的預取屬性節點中提取對象預取屬性，包括預取大小數組Prefetch_Size[2]、多步預測序列數組Multi_Step[Μ]、指向單步預取隊列的指針Psingle；[0032](9-6)判斷內存池使用率Urate是否大於一個閾值Umax，大於則進入步驟(9_7)，否則進入(9-8)；[0033](9-7)關閉多步預取，僅執行單步預取；[0034](9-8)從磁碟中讀取當前對象，根據當前對象的預取屬性進行預取操作，並更新內存池使用率Urate。[0035]步驟(9-3)具體為，申請一個預取屬性節點,將當前對象Oid寫入節點記錄的Oid,將訪問計數值Visit_Num置O,將預取成功次數數組Prefetch_Vnum[M]、預取準確率數組Prefetch_Crate[Μ]、多步預取序列數組Multi_Step[Μ]、預取大小數組Prefetch_Size[2]初始化置0，並將單步預取隊列指針Psingle和下一預取屬性節點指針Pnext置為空，根據對象Oid進行哈希計算，並根據哈希計算的結果將預取屬性節點加入到預取屬性表中對應的衝突鏈上，步驟(9-4)具體為，訪問了當前對象一次，則將當前對象對應預取屬性節點中的訪問計數值Visit_Num加I,取出當前對象單步預取隊列的頭節點,將頭節點中記錄的Oid寫入Multi_St印[O]，再將寫入Multi_St印[O]的Oid對應的對象視為當前對象，將其單步預取隊列的頭節點記錄的Oid寫入Multi_Step[l],重複上述過程M次，以找到M個對象，並將其依次寫入數組Multi_St印[M]中，由此組成了當前可以預測到的最有可能的後續訪問順序。[0036]步驟(9-7)具體為，將預取屬性節點中多步預取的預取步長置為0，即設置Prefetch_Size[l]=0,步驟(9_8)具體為，找到當前對象對應的預取屬性節點，進而找到預取屬性節點記錄的單步預取隊列前[0037]Prefetch_Size[0]個節點，對這些節點中記錄的Oid所對應的對象進行預取,實現單步預取；同時，對數組Multi_Step[M]中前Prefetch_Size[I]個元素記錄的Oid所對應的對象進行預取，實現多步預取，預取過程需要向內存池申請緩存資源，申請完畢後內存池自動更新內存池使用率。[0038]步驟(10)包括以下子步驟:[0039](10-1)在全局訪問順序數組中取前一訪問對象的Oid，並根據Oid在預取屬性表中查找到前一訪問對象的預取屬性節點；[0040](10-2)判斷當前對象是否在前一訪問對象對應的預取屬性節點的單步預取範圍內，在則表示前一訪問對象的單步預取成功，並進入步驟(10-3)，否則進入步驟(10-5)；[0041](10-3)將前一訪問對象對應的預取屬性節點記錄的預取成功次數Prefetch_Vnum[O]的值加I;[0042](10-4)修改當前對象在前一訪問對象對應的預取屬性節點單步預取隊列中的預取權值Prefetch_Weight,並將單步預取隊列按照修改後的預取權值大小重新從大到小排序，然後進入步驟(10-8);[0043](10-5)判斷當前對象是否在前一訪問對象對應的預取屬性節點單步預取隊列中，在則返回步驟(10-4)，否則進入步驟(10-6)；[0044](10-6)判斷前一訪問對象的訪問計數值Visit_Num是否大於其單步預取對列尾節點的預取權值Prefetch_Weight,大於則進入步驟(10-7),否則進入步驟(10-8)；[0045](10-7)在前一訪問對象對應的單步預取對列中為當前對象創建節點，對該節點賦值，並根據預取權值Prefetch_Weight重新調整單步預取對列；[0046](10-8)根據預取成功次數Prefetch_Vnum[0]和訪問計數值Visit_Num將前一訪問對象對應的預取屬性節點記錄的單步預取準確率更新為Prefetch_Crate[0]=Prefetch_Vnum[O]/訪問計數值Visit_Num；[0047](10-9)判斷前一訪問對象對應的預取屬性節點記錄的單步預取準確率Prefetch_Crate[O]是否大於閾值M1，大於則進入步驟(10-10)，否則進入步驟(10-11)；[0048](10-10)設置Prefetch_Size[O]=Prefetch_Size[O]-1,然後過程結束；[0049](10-11)判斷前一訪問對象的單步預取範圍Prefetch_Size[0]大小是否大於等於上限Queue_Length,若是則進入步驟(10-12),否則進入步驟(10-13)；[0050](10-12)將前一訪問對象的單步預取範圍大小Prefetch_Size[0]置O,清空其單步預取對列，並將單步預取對列的指針Psingle置空，然後過程結束；[0051](10-13)將前一訪問對象的單步預取範圍Prefetch_Size[0]設置為Prefetch_Size[O]=Prefetch_Size[O]+1；[0052]步驟(10-7)具體為，將創建節點的Oid值置為當前對象的Oid，預取權值置為前一訪問對象的Visit_Num,刪除單步預取對列中尾節點並將創建的節點加入隊列,仍保持單步預取對列中按照預取權值的大小排列。[0053]步驟(11)包括以下子步驟:[0054](11-1)將臨時變量i的值置為M；[0055](11-2)判斷i是否大於1，若是則進入步驟(11-3)，否則過程結束；[0056](11-3)將全局訪問順序數組Access_Order[M+l]中後i個Oid與該數組中第M_i個對象的多步預取序列數組Multi_Step[M]中前i個Oid進行比對，以判斷比對的Oid序列是否相同，如果相同則進入步驟(11-4)，否則進入步驟(11-5)；[0057](11-4)將全局訪問順序數組中第M-1個對象對應的預取成功次數Prefetch_Vnum[Μ-1-l]加I;[0058](11-5)根據第M-1個對象的預取成功次數Prefetch_Vnum[M-1_l]和訪問計數值Visit_Num將其對應的預取屬性節點記錄的多步預取準確率更新為Prefetch_Crate[M-1-1]=Prefetch_Vnum[M-1-1]/訪問計數值Visit_Num；[0059](11-6)獲取更新的預取準確率數組Prefetch_Crate[M]中大於等於閾值M2的個數，取該個數和Prefetch_Size[0]中的較小值作為新的多步預取的步長Prefetch_Size[I]；[0060](11-7)設置i=i_l，並返回步驟(11-2)。[0061]通過本發明所構思的以上技術方案，與現有技術相比，本發明具有以下的有益效果:[0062](I)能夠自適應應用場景的變化:由於採用了步驟(10-4)、(10-7)，對統計時間窗口內對象的訪問計數，採用求和累加的方法兼顧訪問計數值和訪問時間兩個因子，使訪問計數值越多、訪問時間越近的對象預取權值越大。因此，即使用戶行為發生改變，預取方法也能在一定時間的訪問後，相應改變預取權值的分布，向更適應於當前應用場景的方向變化。[0063](2)能夠動態調整單步預取範圍:採用預取單個對象的方法無法解決諸如ABACABAC的顛簸訪問模式，由於採用了步驟(10-10)、(10-12)、(10-13)，單步預取範圍實現了動態變化，可以將權值較大的一個或多個對象預取到緩存，保證預取的準確率。允許預取範圍動態變化更符合實際多變的應用場景。[0064](3)能夠根據當前結果修正預取策略:預取權值的大小僅代表一種基於歷史記錄的預測，單純設置預取權值的閾值，自適應的調整存在滯後性。由於採用了步驟(10)、(11)，實現了對預取結果的監測，實時反饋修正預取策略，根據預取準確率的變化動態調節預取範圍，保證預取準確率維持在較好的狀態，實現對預取主要指標準確率的快速調節。[0065](4)能夠兼顧單步預取和多步預取:多數預取方法更多考慮保證單步預取的性能，因為多步預取需要統計更多的訪問順序信息，處理流程更複雜。但單步預取已經記錄了大量歷史訪問信息，可以嘗試用於多步預取的分析。由於採用了步驟(11)，本發明在優先保障單步預取性能的情況下，基於已有歷史訪問信息，預測一種最大概率的多步訪問順序，並在多步預取達到一定準確率的情況下才進行多步預取，根據後續訪問記錄實時調整多步預取策略，提高多步預取的準確率，並動態自適應調整單步預取範圍和多步預取步長。[0066](5)預取資源佔用可控:保證預取性能的同時，本發明針對緩存資源進行了有效控制，由於採用了步驟(I)、(9-7)、(9-8)、(10-12)，通過對緩存資源的集中分配管理，限制了單步預取範圍和多步預取步長的上限，在單步預取範圍達到上限仍不能滿足準確率要求時，不再繼續擴大預取範圍，清空佔用的緩存資源；在緩存資源緊張時，優先關閉多步預取步長，保障單步預取的進行。[0067](6)能夠適用於各種對象文件系統:由於採用了步驟(I)、(6)、(7)，本發明在不改變對象屬性的情況下建立哈希表記錄對象訪問順序的有關信息，通過分析表內數據實現高效的預取，並根據實際訪問情況修正哈希表內的記錄；通過定時清理哈希表，清除上一時間段的記錄，符合程序訪問的局部性，控制了哈希表的規模。對於不同的對象文件系統，都能夠通過本發明實現高效的預取。【專利附圖】【附圖說明】[0068]圖1是本發明對象文件系統中預取屬性表的示意圖。[0069]圖2是本發明對象文件系統的預取方法的流程圖。[0070]圖3是本發明步驟(9)的細化流程圖。[0071]圖4是本發明步驟(10)的細化流程圖。[0072]圖5是本發明步驟(11)的細化流程圖。【具體實施方式】[0073]為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，並不用於限定本發明。[0074]以下首先對本發明的技術術語進行解釋和說明:[0075]內存池:從內存申請固定大小的內存空間，以便統一管理和分配緩存資源。[0076]哈希表:根據關鍵碼值(Keyvalue)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找速度。這個存放記錄的數據結構叫做哈希表。[0077]哈希桶:哈希表中存放記錄的一個位置叫做哈希桶。[0078]衝突鏈:不同的關鍵碼值可能映射到表中的同一個位置，由此產生了衝突，而用於存放這些衝突信息的鍊表結構叫做衝突鏈。[0079]緊鄰訪問:無間隔的後續訪問叫做緊鄰訪問。[0080]單步預取:預取一個對象的下一緊鄰訪問對象叫做單步預取。[0081]多步預取:預取一個對象後續將要訪問的多個對象叫做多步預取。[0082]預取步長:預取一個對象後續將要訪問的對象的個數叫做預取步長。[0083]預取屬性:包括對象後續可能訪問的對象，預取區間大小等信息。[0084]預取屬性節點:存放對象預取屬性的節點。[0085]預取屬性表:用哈希表來存放多個預取屬性節點的數據結構。[0086]下面結合附圖來解釋本發明的思路:[0087]如圖1所示，本發明主要通過分析預取屬性表來預測對象的後續訪問順序。預取屬性表主要由三部分構成，一個是由Bucket_Num個哈希桶組成的哈希表,在本實施方式中，Bucket_Num的取值為512k至IM;—個是衝突鏈中的預取屬性節點，其記錄有對象號(ObjectIDNumber,簡稱Oid)、訪問計數值Visit_Num、預取成功次數數組Prefetch_Vnum[Μ]、預取準確率數組Prefetch_Crate[Μ]、預取大小數組Prefetch_Size[2]、多步預取序列數組Multi_Step[Μ]、指向一個單步預取隊列的指針Psingle和指向下一預取屬性節點的指針Pnext，本實施方式中，M取值範圍為2至6，即多步預取的最大預取步長為2至6;一個是單步預取隊列，隊列中每個節點記錄有01(1和預取權值？代作丨011_1618111:,隊列長度不超過Queue_Length,在本實施方式中，Queue_Length取值範圍是2至6。[0088]對象文件系統中，Oid唯一標識了一個對象。若讀對象請求未命中緩存，則啟動預取，即讀緩存失效才啟動預取。根據正在處理的當前對象Oid查詢預取屬性表，建立當前對象到預取屬性節點的對應關係，可以獲取當前對象的預取屬性信息:[0089]預取屬性節點中記錄的訪問計數值Visit_Num對應一個時間段內系統訪問當前對象的次數；指針Psingle指向當前對象對應預取屬性節點的單步預取隊列，隊列中每個節點記錄的Oid代表一個時間段內，當前對象緊鄰訪問過該Oid的對象,節點在隊列中的位置按照預取權值[0090]Prefetch_ffeight值從大到小排序，Prefetch_ffeight值最大的節點位於對列頭；多步預取序列數組Multi_Step[M]中存放著當前對象後續多步預測訪問的Oid,元素Multi_Step[na](0〈=na〈M)為預取步長等於na+1時預測的Oid,多步預取序列數組Multi_Step[Μ]中記錄了當前對象最有可能的後續訪問順序，具體來說，取出當前對象對應單步預取隊列的頭節點，節點中記錄的Oid寫入Multi_Step[0],再將寫入Multi_Step[O]的Oid對應的對象視為當前對象重複上述過程，將找到的Oid依次寫入Multi_Step[l]、Multi_Step[2]到Multi_Step[Μ]，因為單步預取隊列中的首節點均為預取權值最大的節點，即最有可能的緊鄰訪問對象，所以訪問當如對象時，最有可能的後續訪問順序就是Multi_Step[Μ]中元素組成的序列；預取大小數組Prefetch_Size[2]存放著單步預取範圍大小和多步預取的預取步長，其中元素Prefetch_Size[0]對應單步預取範圍中對象的個數，Prefetch_Size[l]對應多步預取的預取步長；預取成功次數數組Prefetch_Vnum[M]存放著一個時間段內當前對象後續預取成功的次數，元素Prefetch_Vnum[nb](0〈=nb〈M)代表預取步長為nb+1時，預取成功的次數，對於單步預取，預取成功指實際緊鄰訪問對象的oid在單步預取範圍中，單步預取範圍指當前對象對應預讀屬性節點的單步預取隊列前Prefetch_Size[O]個節點記錄的Oid的範圍，單步預取成功Prefetch_Vnum[0]加I,對於預取步長為nc(l<nc<=M)的多步預測，通過當前對象找到對應的預取屬性節點，若節點記錄的數組Multi_Step[M]前nc個元素和多步預取順序完全匹配,則認為多步預取成功，Prefetch_Vnum[nc-Ι]加I;預取準確率數組Prefetch_Crate[M]由訪問計數值Visit_Num、預取成功次數數組Prefetch_Vnum[M]計算得出，元素Prefetch_Crate[nd](0〈=nd〈M)=Prefetch_Vnum[nd]/Visit_Num。[0091]因此，首先訪問一個對象即可獲取相應的預取屬性，預測後續訪問的順序:由預取大小數組中Prefetch_Size[0]控制單步預取範圍中對象個數，決定了在當前對象的單步預取隊列中最有可能緊鄰訪問的對象的個數，單步預取的範圍即單步預取隊列的前Prefetch_Size[0]個節點所對應的對象；由Prefetch_Size[I]控制的多步預取的步長,決定了按照最有可能的後續訪問順序進行預取的步長，先找到當前對象對應的單步預取隊列頭結點，即找到最有可能的緊鄰訪問對象，再同理找到該緊鄰訪問對象的最有可能的緊鄰訪問對象，以此直至找到M個對象組成了當前可以預測到的最有可能後續訪問順序；[0092]然後，後續實際訪問的順序又可以對當前訪問對象預測的信息進行修正。根據後續實際訪問的順序調整當前訪問對象的預取成功次數數組Prefetch_Vnum[M]、預取準確率數組Prefetch_Crate[Μ]；[0093]進而根據準確率的變化更新單步預取範圍的值Prefetch_Size[0]和多步預取步長的值Prefetch_Size[l],完成訪問信息的反饋。具體來說,若單步預取準確率Prefetch_Crate[O]低於給定閾值Ml,則逐步遞增單步預取範圍Prefetch_Size[O],否則逐步遞減Prefetch_Size[0],Prefetch_Size[O]達到最大值M準確率仍低於Ml則說明當前預取無法達到效果，故Prefetch_Size[0]置O;多步預取則統計預取準確率數組Prefetch_Crate[M]中大於等於閾值M2的個數,取該個數和Prefetch_Size[0]中的較小值作為多步預取的步長。本實施方式中，Ml的取值範圍為60%至80%，M2的取值範圍為40%-70%；[0094]最後，通過訪問信息的反饋以及緩存資源使用情況的監測，動態自適應的調節後續訪問單步預取的範圍、多步預取的順序及步長，達到預取性能的優化。實現先預取，後驗證，再用驗證結果修正預取參數，利於下次訪問時達到更好的預取效果。[0095]如圖2所示，本發明對象文件系統的預取方法包括以下步驟:[0096](I)對對象文件系統的相關數據結構和變量進行初始化；具體而言，向內存申請固定大小的內存池作為全局緩存空間，初始化內存池且將表示內存池使用率的全局變量Urate置O,創建並初始化一個具有Bucket_Num個哈希桶的哈希表(在本實施方式中，Bucket_Num的取值為512k至1M),哈希桶的編號從O到Bucket_Num_l,申請並初始化一個全局訪問順序數組Access_0rder[M+1](其中M表示多步預測的最大步長,其取值範圍為2至6),數組中的每個元素用於存放對象的Oid,從Access_0rder[O]到Access_0rder[M]讀出的Oid序列即為最近訪問的對象Oid順序,且Access_0rder[M]為當前訪問對象的Oid,將計時值T_Clock設置為O且系統每隔一秒T_Clock值加I;[0097](2)判斷伺服器是否接收來自客戶端的讀對象請求，如果是則進入步驟(3)，否則過程結束；[0098](3)解析讀對象請求，並根據讀對象請求確定當前對象及其Oid；[0099](4)判斷讀對象請求是否命中緩存，如果是進入步驟(5)，否則進入步驟(6)；[0100](5)根據當前對象的Oid在內存池中查找對應的緩存空間，並從緩存空間中直接讀取當前對象，然後進入步驟(10)；[0101](6)判斷是否存在計時值T_Clock大於或等於時間閾值T_MAX，如果存在，則表示時間窗口已到，並進入步驟(7)，否則進入步驟(9)，在本實施方式中，T_MAX的取值範圍為60至600秒；[0102](7)初始化預取屬性表，並將計時值T_Clock置O;具體而言，將預取屬性表中的所有節點初始化，清空時間閾值T_MAX前一段時間內的統計數據，包括將預取屬性節點中的訪問計數值Visit_Num置O、預取成功次數數組Prefetch_Vnum[M]、預取準確率數組Prefetch_Crate[Μ]、預取大小數組Prefetch_Size[2]、多步預取序列數組Multi_Step[Μ]設置為零，釋放預取屬性節點中單步預取對列所佔用的內存空間並置指針Psingle為空，並初始化全局訪問順序數組Access_0rder[Μ+1]為零；[0103](8)從磁碟中讀取讀對象請求的對象，然後進入步驟(10)。[0104](9)根據當前對象的Oid查詢預取屬性表，以獲取當前對象的預取屬性，並根據預取屬性執行讀磁碟和預取操作；[0105]如圖3所示，本步驟包括以下子步驟:[0106](9-1)記錄與對象訪問順序有關的信息，並將當前對象Oid寫入全局訪問順序數組Access_0rder[M+1];具體而言,刪除最早的記錄Access_0rder[O],將全局訪問順序數組Access_0rder[M+1]中的元素整體向前移動一位，並將當前對象Oid寫入Access_Order[Μ]；[0107](9-2)判斷預取屬性表中是否存在當前對象對應的預取屬性節點，如不存在則進入步驟(9-3)，否則進入步驟(9-4)。[0108](9-3)為當前對象建立對應的預取屬性節點；具體而言，申請一個預取屬性節點，將當前對象Oid寫入節點記錄的Oid,將訪問計數值Visit-Num置O,將預取成功次數數組Prefetch_Vnum[M]、預取準確率數組Prefetch_Crate[M]、多步預取序列數組Multi_Step[Μ]、預取大小數組Prefetch_Size[2]初始化置O,並將單步預取隊列指針Psingle和下一預取屬性節點指針Pnext置為空，根據對象Oid進行哈希計算，並根據哈希計算的結果將預取屬性節點加入到預取屬性表中對應的衝突鏈上；[0109](9-4)更新當前對象的預取屬性信息，包括訪問計數值Visit_Num和多步預取序列數組Multi_Step[Μ];具體而言,訪問了當前對象一次，則將當前對象對應預取屬性節點中的訪問計數值Visit_Num加I,取出當前對象單步預取隊列的頭節點,將頭節點中記錄的Oid寫入Multi_St印[O]，再將寫入Multi_St印[O]的Oid對應的對象視為當前對象，將其單步預取隊列的頭節點記錄的Oid寫入Multi_Step[l],重複上述過程M次，以找到M個對象，並將其依次寫入數組Multi_St印[M]中，由此組成了當前可以預測到的最有可能的後續訪問順序。[0110](9-5)從當前對象對應的預取屬性節點中提取對象預取屬性，包括預取大小數組Prefetch_Size[2]、多步預測序列數組Multi_Step[Μ]、指向單步預取隊列的指針Psingle；[0111](9-6)判斷內存池使用率Urate是否大於一個閾值Umax，大於則進入步驟(9_7)，否則進入(9-8);在本實施方式中，Umax取值範圍為70%至90%；[0112](9-7)關閉多步預取，僅執行單步預取；具體而言，將預取屬性節點中多步預取的預取步長置為0，即設置Prefetch_Size[l]=0；[0113](9-8)從磁碟中讀取當前對象，根據當前對象的預取屬性進行預取操作，並更新內存池使用率Urate;具體來說，找到當前對象對應的預取屬性節點，進而找到預取屬性節點記錄的單步預取隊列前Prefetch_Size[0]個節點,對這些節點中記錄的Oid所對應的對象進行預取，實現單步預取；同時,對數組Multi_Step[M]中前Prefetch_Size[I]個元素記錄的Oid所對應的對象進行預取，實現多步預取，預取過程需要向內存池申請緩存資源，申請完畢後內存池自動更新內存池使用率；[0114](10)根據全局訪問順序數組Access_0rder[M+1]對預取屬性表的單步預取信息進行修改；具體而言，僅需修改預取屬性表中前一訪問對象的單步預取信息。[0115]如圖4所示，本步驟包括以下子步驟:[0116](10-1)在全局訪問順序數組中取前一訪問對象的Oid，並根據Oid在預取屬性表中查找到前一訪問對象的預取屬性節點；具體而言，全局訪問順序數組中AccessOrder[Μ-1]元素的值即前一訪問對象的Oid；[0117](10-2)判斷當前對象是否在前一訪問對象對應的預取屬性節點的單步預取範圍內，在則表示前一訪問對象的單步預取成功，並進入步驟(10-3)，否則進入步驟(10-5)；[0118](10-3)將前一訪問對象對應的預取屬性節點記錄的預取成功次數Prefetch_Vnum[O]的值加I;[0119](10-4)修改當前對象在前一訪問對象對應的預取屬性節點單步預取隊列中的預取權值Prefetch_Weight,並將單步預取隊列按照修改後的預取權值大小重新從大到小排序，然後進入步驟(10-8);具體而言，將預取權值Prefetch_Weight設置為Prefetch_ffeight=Prefetch_ffeight+前一訪問對象的訪問計數值Visit_Num,然後進入步驟(10_8)；[0120](10-5)判斷當前對象是否在前一訪問對象對應的預取屬性節點單步預取隊列中，在則返回步驟(10-4)，否則進入步驟(10-6)；[0121](10-6)判斷前一訪問對象的訪問計數值Visit_Num是否大於其單步預取對列尾節點的預取權值Prefetch_Weight,大於則進入步驟(10-7),否則進入步驟(10-8)；[0122](10-7)在前一訪問對象對應的單步預取對列中為當前對象創建節點，對該節點賦值，並根據預取權值Prefetch_Weight重新調整單步預取對列；具體而言，將創建節點的Oid值置為當前對象的Oid，預取權值置為前一訪問對象的Visit_Num，刪除單步預取對列中尾節點並將創建的節點加入隊列，仍保持單步預取對列中按照預取權值的大小排列；[0123](10-8)根據預取成功次數Prefetch_Vnum[0]和訪問計數值Visit_Num將前一訪問對象對應的預取屬性節點記錄的單步預取準確率更新為Prefetch_Crate[0]=Prefetch_Vnum[O]/訪問計數值Visit_Num；[0124](10-9)判斷前一訪問對象對應的預取屬性節點記錄的單步預取準確率Prefetch_Crate[O]是否大於閾值M1，大於則進入步驟(10_10)，否則進入步驟(10-11);在本實施方式中，Ml的取值範圍為60%至80%；[0125](10-10)設置Prefetch_Size[O]=Prefetch-Size[O]-1,然後過程結束；[0126](10-11)判斷前一訪問對象的單步預取範圍Prefetch_Size[0]大小是否大於等於上限Queue_Length,若是則進入步驟(10-12),否則進入步驟(10-13);在本實施方式中，Queue_Length的取值範圍是2至6;[0127](10-12)將前一訪問對象的單步預取範圍大小Prefetch_Size[0]置O,清空其單步預取對列，並將單步預取對列的指針Psingle置空，然後過程結束；[0128](10-13)將前一訪問對象的單步預取範圍Prefetch_Size[0]設置為Prefetch_Size[O]=Prefetch_Size[O]+1；[0129](11)根據全局訪問順序數組Access_0rder[M+1]對預取屬性表的多步預取信息進行修改；具體而言，需修改前M個對象的多步預取信息。[0130]如圖5所示,本步驟包括以下子步驟:[0131](11-1)將臨時變量i的值置為M;[0132](11-2)判斷i是否大於1，若是則進入步驟(11-3)，否則過程結束；[0133](11-3)將全局訪問順序數組Access_Order[M+l]中後i個Oid與該數組中第M_i個對象的多步預取序列數組Multi_Step[M]中前i個Oid進行比對，以判斷比對的Oid序列是否相同，如果相同則進入步驟(11-4)，否則進入步驟(11-5)；[0134](11-4)將全局訪問順序數組中第M-1個對象對應的預取成功次數Prefetch_Vnum[Μ-1-l]加I;[0135](11-5)根據第M-1個對象的預取成功次數Prefetch_Vnum[M-1_l]和訪問計數值Visit_Num將其對應的預取屬性節點記錄的多步預取準確率更新為Prefetch_Crate[M-1-1]=Prefetch_Vnum[M-1-1]/訪問計數值Visit_Num；[0136](11-6)獲取更新的預取準確率數組Prefetch_Crate[M]中大於等於閾值M2的個數，取該個數和Prefetch_Size[0]中的較小值作為新的多步預取的步長Prefetch_Size[l];在本實施方式中，閾值M2的取值範圍是40%-70%;[0137](11-7)設置i=i_l，並返回步驟(11-2)。[0138]本領域的技術人員容易理解，以上所述僅為本發明的較佳實施例而已，並不用以限制本發明，凡在本發明的精神和原則之內所作的任何修改、等同替換和改進等，均應包含在本發明的保護範圍之內。【權利要求】1.一種對象文件系統的預取方法，其特徵在於，包括以下步驟:(1)對對象文件系統的數據結構和變量進行初始化；具體而言，初始化內存池且將表示內存池使用率的全局變量Urate置O，創建並初始化一個具有Bucket_Num個哈希桶的哈希表，申請並初始化一個全局訪問順序數組Access_Order[M+l],其中M表示多步預測的最大步長,數組中的每個元素用於存放對象的Oid，Access_Order[M]為當前訪問對象的OidJf計時值T_Clock設置為0，且系統每隔一秒T_Clock值加I;(2)判斷伺服器是否接收來自客戶端的讀對象請求，如果是則進入步驟(3)，否則過程結束；(3)解析讀對象請求，並根據讀對象請求確定當前對象及其Oid；(4)判斷讀對象請求是否命中緩存，如果是進入步驟(5)，否則進入步驟(6)；(5)根據當前對象的Oid在內存池中查找對應的緩存空間，並從緩存空間中直接讀取當前對象，然後進入步驟(10);(6)判斷是否存在計時值T_Clock大於或等於時間閾值T_MAX，如果存在，則表示時間窗口已到，並進入步驟(7)，否則進入步驟(9)；(7)初始化預取屬性表，並將計時值T_Clock置O;(8)從磁碟中讀取讀對象請求的對象,然後進入步驟(10)；(9)根據當前對象的Oid查詢預取屬性表，以獲取當前對象的預取屬性，並根據預取屬性執行讀磁碟和預取操作；(10)根據全局訪問順序數組ACCesS_0rder[M+l]對預取屬性表的單步預取信息進行修改；(11)根據全局訪問順序數組ACCesS_0rder[M+l]對預取屬性表的多步預取信息進行修改。2.根據權利要求1所述的預取方法，其特徵在於，步驟(7)具體為，將預取屬性表中的所有節點初始化，清空時間閾值T_MAX前一段時間內的統計數據，包括將預取屬性節點中的訪問計數值Visit_Num置O、預取成功次數數組Prefetch_Vnum[M]、預取準確率數組Prefetch_Crate[Μ]、預取大小數組Prefetch_Size[2]、多步預取序列數組Multi_Step[Μ]設置為零，釋放預取屬性節點中單步預取對列所佔用的內存空間並置指針Psingle為空，並初始化全局訪問順序數組Access_0rder[Μ+1]為零。3.根據權利要求1所述的預取方法，其特徵在於，步驟(9)包括以下子步驟:(9-1)記錄與對象訪問順序有關的信息，並將當前對象Oid寫入全局訪問順序數組Access_0rder[M+1]；(9-2)判斷預取屬性表中是否存在當前對象對應的預取屬性節點，如不存在則進入步驟(9-3)，否則進入步驟(9-4)。(9-3)為當前對象建立對應的預取屬性節點；(9-4)更新當前對象的預取屬性信息，包括訪問計數值Visit_Num和多步預取序列數組Multi_Step[M]；(9-5)從當前對象對應的預取屬性節點中提取對象預取屬性，包括預取大小數組Prefetch_Size[2]、多步預測序列數組Multi_Step[Μ]、指向單步預取隊列的指針Psingle；(9-6)判斷內存池使用率Urate是否大於一個閾值Umax，大於則進入步驟(9_7)，否則進入(9-8)；(9-7)關閉多步預取，僅執行單步預取；(9-8)從磁碟中讀取當前對象，根據當前對象的預取屬性進行預取操作，並更新內存池使用率Urate。4.根據權利要求3所述的預取方法，其特徵在於，步驟(9-3)具體為，申請一個預取屬性節點，將當前對象Oid寫入節點記錄的Oid，將訪問計數值Visit_Num置O,將預取成功次數數組Prefetch_Vnum[M]、預取準確率數組Prefetch_Crate[Μ]、多步預取序列數組Multi_Step[Μ]、預取大小數組Prefetch_Size[2]初始化置0，並將單步預取隊列指針Psingle和下一預取屬性節點指針Pnext置為空，根據對象Oid進行哈希計算，並根據哈希計算的結果將預取屬性節點加入到預取屬性表中對應的衝突鏈上；步驟(9-4)具體為，訪問了當前對象一次，則將當前對象對應預取屬性節點中的訪問計數值Visit_Num加I,取出當前對象單步預取隊列的頭節點,將頭節點中記錄的Oid寫入Multi_Step[O]，再將寫入Multi_Step[O]的Oid對應的對象視為當前對象，將其單步預取隊列的頭節點記錄的Oid寫入Multi_Step[l],重複上述過程M次，以找到M個對象，並將其依次寫入數組Multi_Step[M]中，由此組成了當前可以預測到的最有可能的後續訪問順序。5.根據權利要求3所述的預取方法，其特徵在於，步驟(9-7)具體為，將預取屬性節點中多步預取的預取步長置為0，即設置PrefetchSize[I]=0；步驟(9-8)具體為，找到當前對象對應的預取屬性節點，進而找到預取屬性節點記錄的單步預取隊列前Prefetch_Size[0]個節點,對這些節點中記錄的Oid所對應的對象進行預取，實現單步預取；同時，對數組Multi_Step[M]中前Prefetch_Size[I]個元素記錄的Oid所對應的對象進行預取，實現多步預取，預取過程需要向內存池申請緩存資源，申請完畢後內存池自動更新內存池使用率。6.根據權利要求1所述的預取方法，其特徵在於，步驟(10)包括以下子步驟:(10-1)在全局訪問順序數組中取前一訪問對象的Oid，並根據Oid在預取屬性表中查找到前一訪問對象的預取屬性節點；(10-2)判斷當前對象是否在前一訪問對象對應的預取屬性節點的單步預取範圍內，在則表示前一訪問對象的單步預取成功，並進入步驟(10-3)，否則進入步驟(10-5)；(10-3)將前一訪問對象對應的預取屬性節點記錄的預取成功次數Prefetch_Vnum[0]的值加I;(10-4)修改當前對象在前一訪問對象對應的預取屬性節點單步預取隊列中的預取權值Prefetch_Weight,並將單步預取隊列按照修改後的預取權值大小重新從大到小排序,然後進入步驟(10-8)；(10-5)判斷當前對象是否在前一訪問對象對應的預取屬性節點單步預取隊列中，在則返回步驟(10-4)，否則進入步驟(10-6)；(10-6)判斷前一訪問對象的訪問計數值Visit_Num是否大於其單步預取對列尾節點的預取權值Prefetch_Weight,大於則進入步驟(10-7),否則進入步驟(10-8)；(10-7)在前一訪問對象對應的單步預取對列中為當前對象創建節點，對該節點賦值，並根據預取權值Prefetch_Weight重新調整單步預取對列；(10-8)根據預取成功次數Prefetch_Vnum[0]和訪問計數值Visit_Num將前一訪問對象對應的預取屬性節點記錄的單步預取準確率更新為Prefetch_Crate[0]=Prefetch_Vnum[O]/訪問計數值Visit_Num；(10-9)判斷前一訪問對象對應的預取屬性節點記錄的單步預取準確率Prefetch_Crate[O]是否大於閾值M1，大於則進入步驟(10-10)，否則進入步驟(10-11)；(10-10)設置Prefetch_Size[0]=Prefetch_Size[0]-l,然後過程結束；(10-11)判斷前一訪問對象的單步預取範圍Prefetch_Size[0]大小是否大於等於上限Queue_Length,若是則進入步驟(10-12),否則進入步驟(10-13)；(10-12)將前一訪問對象的單步預取範圍大小Prefetch_Size[0]置O,清空其單步預取對列，並將單步預取對列的指針Psingle置空，然後過程結束；(10-13)將前一訪問對象的單步預取範圍Prefetch_Size[O]設置為Prefetch_Size[O]=Prefetch_Size[O]+1；7.根據權利要求6所述的預取方法，其特徵在於，步驟(10-7)具體為，將創建節點的Oid值置為當前對象的Oid，預取權值置為前一訪問對象的Visit_Num,刪除單步預取對列中尾節點並將創建的節點加入隊列,仍保持單步預取對列中按照預取權值的大小排列；8.根據權利要求1所述的預取方法，其特徵在於，步驟(11)包括以下子步驟:(11-1)將臨時變量i的值置為M;(11-2)判斷i是否大於1，若是則進入步驟(11-3)，否則過程結束；(11-3)將全局訪問順序數組Access_Order[M+l]中後i個Oid與該數組中第M_i個對象的多步預取序列數組Multi_Step[M]中前i個Oid進行比對，以判斷比對的Oid序列是否相同，如果相同則進入步驟(11-4)，否則進入步驟(11-5);(11-4)將全局訪問順序數組中第M-1個對象對應的預取成功次數Prefetch_Vnum[Μ-1-l]加1;(11-5)根據第M-1個對象的預取成功次數Prefetch_Vnum[M-1_l]和訪問計數值Visit_Num將其對應的預取屬性節點記錄的多步預取準確率更新為Prefetch_Crate[M-1-1]=Prefetch_Vnum[M-1-1]/訪問計數值Visit_Num；(11-6)獲取更新的預取準確率數組Prefetch_Crate[M]中大於等於閾值M2的個數,取該個數和Prefetch_Size[0]中的較小值作為新的多步預取的步長Prefetch_Size[I]；(11-7)設置i=i_l，並返回步驟(11-2)。【文檔編號】G06F9/44GK103902260SQ201210570438【公開日】2014年7月2日申請日期:2012年12月25日優先權日:2012年12月25日【發明者】王芳,馮丹,李潔瓊,閆陽申請人:華中科技大學