基于頻繁序列挖掘的預取算法研究與實現

王 芳 王培群 朱春節

1（武漢光電國家實驗室（華中科技大學） 武漢 430074）2（華中科技大學計算機科學與技術學院 武漢 430074）（wangpeiqun＠hust．edu．cn）

基于頻繁序列挖掘的預取算法研究與實現

王 芳1，2王培群2朱春節1

1（武漢光電國家實驗室（華中科技大學） 武漢 430074）2（華中科技大學計算機科學與技術學院 武漢 430074）（wangpeiqun＠hust．edu．cn）

預取作為一種提升存儲系統性能的有效手段被廣泛使用，然而傳統的預取算法大多基于順序性訪問特征的探測，這使得它們在非順序數據訪問環境下很難奏效，甚至可能因為預取準確率較低而對存儲系統的性能帶來負面影響．而基于頻繁序列挖掘的預取算法則能夠通過分析數據的訪問行為找出潛在規律，從而能在非順序訪問模式下也取得一定的性能提升．同時，為了應對某些緩存受限的應用場景，如嵌入式系統，預取算法通過提高分析的準確率減少預取可能對緩存帶來的不利影響．新提出的預取算法基于頻繁序列挖掘技術，并使用字典樹組織預取規則，通過多步匹配和子樹分割技術精細地控制規則的使用，提升預取的準確率，從而使得預取算法能夠有效提升存儲系統的性能．

頻繁序列是指在一組有序的數據列組成的數據集合中，出現次數不小于閾值的序列．頻繁序列挖掘算法屬于數據挖掘的一個分支，它于1993年由Agrawal等人［1］提出，至今已經有20多年歷史．期間出現了各種各樣的頻繁序列挖掘算法，具有代表性的有Apriori［2］，PrefixSpan［3］，CloSpan［4］等．

預取作為一種提高性能的有效手段已被廣泛用于各種存儲系統中，而通常提到的預取大部分是基于順序訪問特征，例如Linux內核使用一種帶有預取窗口的順序預取方法［5］，DiskSeen［6］采用一種基于歷史訪問信息分析的順序預取方法，它們的時間和空間開銷小，很多情況下對性能的提升也非常明顯．然而順序預取并不適用所有情形，特別是當數據布局是非順序時，例如文件系統中元數據信息的訪問、數據庫文件內部的索引結構等．這種非順序的頻繁訪問模式在存儲系統中是比較常見的，于是出現了針對頻繁序列訪問模式的預取算法，最有代表性的是C－Miner［7］和C－Miner＊［8］，它們通過頻繁序列挖掘算法生成規則集，然后根據規則判斷需要預取的數據塊，但是它們挖掘過程中的時間和空間開銷比較大，而且對規則的利用不夠準確高效．本文提出的Trie預取算法針對頻繁序列訪問模式，改進了頻繁序列挖掘算法，并采用字典樹組織規則集，通過在樹中匹配序列判斷預取的數據塊，預取的準確度更高．

1 算法架構

如圖1所示，Trie預取算法包括3部分，即緩存管理模塊，頻繁序列挖掘模塊和預取模塊．

緩存管理模塊用于緩存塊設備上的部分數據，如果上層用戶請求的數據在緩存管理模塊中，即緩存命中，則直接將緩存管理模塊的數據返回給上層用戶；如果不在，即緩存不命中，則需要向底層塊設備發出讀請求，并將取到的數據拷貝一份放入緩存模塊中，同時將數據返回給上層用戶．緩存模塊用LRU（least recently used）算法管理．

頻繁序列挖掘模塊收集到達緩存的用戶請求元數據信息，并把它作為樣本序列，當樣本序列達到預先設定的規模時，執行頻繁序列挖掘算法，輸出頻繁序列數據集，即關聯規則．

Fig．1 Algorithm architecture．圖1 算法架構

預取模塊產生預取請求．當用戶請求在緩存模塊不命中時，預取模塊會搜索關聯規則，若找到與該請求相關的關聯規則，則根據這些關聯規則產生預取請求．

2 頻繁序列挖掘算法

2．1 請求序列預處理

存儲系統中用戶請求序列是單個長序列，無法直接適用頻繁序列挖掘算法，通常的做法是把這個長序列分割成多個等長的短序列．算法參考C－Miner的預處理方法，采用非重合式等長分割．同時，短序列的長度根據經驗預先設置一個合適的值，因為如果短序列的長度太長會導致挖掘算法的開銷劇增，長度太短則可能丟失大量的頻繁序列信息．

2．2 頻繁序列挖掘

頻繁序列挖掘算法的核心數據結構包括一棵字典樹和一個散列表，其中字典樹用于保存所有的頻繁序列信息，散列表用于臨時保存已處理的結點的信息．算法開始時，字典樹只有一個空的根結點指針head，散列表為空．為了提高挖掘效率，算法一方面根據頻繁條目集合對初始的數據集進行修剪，從而大大減小后續操作中數據集的大小；另一方面，利用散列表快速判斷等價結點，從而減小遞歸深度．具體處理步驟描述如下：

算法1．頻繁序列挖掘算法．

輸入：字典樹根結點head，初始的數據集S，篩選的閾值min＿sup；

輸出：以字典樹組織的頻繁序列集．

步驟1．對初始數據集S進行統計，得到所有長度為1的頻繁條目，組成頻繁條目集合．如果此集合為空，則整個算法結束；否則創建head結點，將集合中的條目存放在head結點中，將head結點作為當前結點，并進入步驟2．

步驟2．根據步驟1中得到的頻繁條目集合對初始的數據集S進行修剪，除去S中的非頻繁條目，得到精簡的數據集S′，將S′作為當前數據集，并進入步驟3．

步驟3．根據當前數據集的大小快速判斷當前結點在散列表中是否存在等價的結點．若存在等價的結點，則算法對當前結點的遞歸調用結束，并進入步驟5，否則進入步驟4．

步驟4．取當前結點的1個條目生成相應的數據集，如果該條目的后綴數據集不為空，則為此條目創建1個新結點，并把新結點作為當前結點，跳入步驟3，否則繼續對當前結點的下1個條目作步驟4的操作；如果當前結點的條目全部處理完，則進入步驟5．

步驟5．判斷當前結點在字典樹中是否存在未遍歷的兄弟結點，若存在，則把兄弟結點作為當前結點，并轉入步驟3，否則將當前結點的父結點作為當前結點；如果當前結點是head，則整個算法結束，否則重復步驟5．

挖掘算法結束后，規則樹中有很多并不是閉合的頻繁序列，需要對它們進行刪除．由于散列表中保存的結點在具有等價后綴數據庫的結點中，均是最長的序列，因此對散列表中所有的結點進行掃描，查找到所有葉子結點，將它們標記為FLAG＿CLOSET，并將它們的所有祖先結點標記為FLAG＿INUSE．散列表掃描結束后，對之前生成的頻繁序列集進行整理，僅保留標志位FLAG＿INUSE的結點，新生成的樹則為最終的頻繁序列規則字典樹．如果把挖掘的頻繁序列的長度限制成1個常量，則此算法在最壞情況下與CloSpan算法的時間復雜度相當，即為O（n2）［9］，同時，由于在CloSpan算法的基礎上做了上述優化，所以新算法的計算開銷更小．

3 基于字典樹匹配的預取算法

為了能夠有效存儲和使用挖掘算法輸出的關聯規則，預取算法采用字典樹組織規則．任何一條頻繁序列都是作為一個整體出現的，一旦檢測到某個頻繁序列的第1個請求時，預取算法就將該頻繁序列中的所有其他請求預取到內存．

圖2描述了一棵簡單的頻繁序列規則樹，它包含5條頻繁序列｛abcd，aefg，aefh，b，cfai｝．其中，所有規則的前綴都分布于規則樹的第1層，那么當請求到來時僅需要從規則樹的第1層查找訪問請求是否存在．如果存在，則表示在接下來的訪問可能對應于請求子樹中的某一條頻繁序列，需要將這棵樹的子樹預取到內存中．例如，如果探測到請求條目a，則將a的子樹的所有條目｛b，c，d，e，f，g，h｝預取到內存中．雖然在頻繁序列cfai中，條目a與條目i也存在關聯關系，但是由于沒有探測到條目c的到來，i不會被預取．采用這樣的方式，可以大量減少無關數據的預取，從而減少預取的失效率．

Fig．2 Prefetching tree of rules．圖2 規則預取樹

然而，當字典樹具有較多分支且樹的深度較深時，上述預取方式仍然會導致過度預取，特別是當系統緩存比較小時，這種預取方式可能給系統帶來更大的負擔．因此，為了進一步提高預取的精度，提出了多步匹配和子樹分割的方法．

3．1 多步匹配

上述提到的基于字典樹匹配的預取算法僅僅通過匹配頻繁序列前綴的首個條目，就預取該條目的所有子樹上的條目．如果某條目有多棵子樹（如圖2中的條目a有2棵子樹），那么預取時將會把這2棵子樹上的所有條目都預取到內存中，但實際上可能只有1棵子樹將被訪問，特別是當子樹很多時，這種預取的正確率更低，帶來的開銷也更大．

多步匹配能夠較好地解決這個問題，其基本思路是當一個條目有多棵子樹時，先把此條目保存在一個隊列結構中，當該條目的某個子樹的根條目被訪問時，則將這個子樹的根條目也加入到此隊列中，直到一個頻繁序列的前n個條目都出現時，才把此頻繁序列的后續條目全部預取到內存．具體的做法是在緩存中創建一個隊列，每當一個新的請求到來時，通過對比隊列中已經匹配的前綴，決定是否進行匹配層級增加或者進行預取操作．

圖3模擬一個正在運行的多步預取隊列，設定的預取步長為4．在條目f到達之前，匹配隊列中維護著若干個已經匹配的條目，隊列的每個結點保存一個條目的數據塊信息及當前已經匹配的層級，同時還有一個結構指向規則樹中已經匹配到的結點．當f到達時，從LRU隊列的頂端查找是否所指向的樹結點的子結點中存在f，如果存在，則將結構放到LRU的頂端，并且匹配層級自增1．

Fig．3 Prefetching cache pools based multistep matching．圖3 多步匹配預取緩存池

例如，從圖2可以看出，條目e所在的結點的子樹中有f，所以當f到達時，用f替代e，并且將此結點的匹配層級變為3．如果經過變化的匹配層級達到多步預取的步長4，則進行預取操作，并且將該結點刪除；否則沒有達到預取的要求，繼續進行后面的操作．

3．2 子樹分割

多步匹配策略提高了預取的準確度，而且步長越長，預取的準確度也越高，然而如果步長設置過長，則預取的數據會大大減小，使得預取的效果被削弱，而且匹配帶來的開銷也會增大，故在使用時需要設置一個比較合適的步長．但是在某些情況下，超過設定步長的子樹仍然有很多分支，此時多步匹配對精度的提高就比較有限．為了應對這種情況，提出子樹分割的策略，即將規則生成樹進行預處理，使得規則樹的高度維持在一定范圍內，而分割后靠近葉子結點的部分掛載到另外一個線性表中，只有在實際訪問到某棵子樹的父結點時，才將其預取到緩存中．

圖4描述了對前面描述的例子中的子樹進行分割的過程，設定子樹分割的深度為2，那么將初始的規則樹深度為2的子樹全部切割，掛載到一個數組下面．當條目a的請求到來時，根據規則樹將b和e預取到內存中，但卻不預取它們各自的子樹cd和fgh．而且隨著請求的繼續，若某一時刻，條目e在內存中命中，并檢測到該條目e是某一棵子樹的根結點，那么通過其ID查找到相應的子樹，從而將子樹預取．

Fig．4 Subtree partitioning．圖4 子樹分割

4 實驗及結果分析

本文的負載采用惠普實驗室的HP Cello96數據集，它是1996年在惠普Cello系統上跟蹤采集的2級磁盤IO請求，而Cello是由一組研究者用來作仿真、編譯、編輯文檔和收發郵件的分時共享系統．為了驗證算法，搭建了模擬實驗原型系統，原型系統的架構與圖1基本吻合．實驗平臺是1臺浪潮NF5280服務器，具體的硬件配置如表1所示．原型系統運行于64位Red Hat Enterprise Linux Server Release 5．3操作系統上，它是自主實現的一個用戶態仿真程序，包括緩存管理模塊、頻繁序列挖掘模塊和預取模塊，其中緩存管理模塊不存儲真實的數據，只存儲請求的元數據信息，因為通過元數據信息就可以判斷是否命中．

Table 1 Hardware Configuration of the Server表1 服務器硬件配置

實驗方法分2個階段，第1階段是頻繁序列挖掘階段，此階段尚沒有關聯規則可用，所以預取模塊不可用．當關聯規則樹生成后，程序進入第2階段，此階段預取模塊是可用的．分段的標準是trace文件中前半部分的IO請求屬于第1階段，后半部分屬于第2階段．這種實驗方法是參考C－Miner中的做法，方便與之對比．

實驗中關注的參數主要有：hit＿num為緩存命中次數，replace＿num為緩存替換次數，prefetch＿hit＿num為預取命中次數，prefetch＿num為預取次數．

定義1．預取準確率＝預取命中的請求數?預取的次．

圖5和圖6分別描述了不同算法的命中率和預取準確率的比較情況，緩存大小為64MB．其中LRU是標準的緩存替換算法；C－Miner是目前比較好的一個頻繁序列預取算法；Trie是單步匹配的頻繁序列預取算法，是本文的核心算法；Trie（3）是3步匹配的頻繁序列預取算法，是對Trie的一種改進；Trie（3）＆CutTree是同時使用3步匹配和子樹分割策略優化的頻繁序列預取算法，是在Trie（3）的基礎上做進一步的優化．

Fig．5 Comparison of hit rate．圖5 命中率比較

Fig．6 Prefetching accuracy．圖6 預取準確率

從圖5可以看出，LRU算法的緩存命中次數在580 000左右，其他4種算法的緩存命中次數均在750 000左右，即Trie（3）＆CutTree算法的緩存命中率比LRU算法提高29．3%，與C－Miner算法的緩存命中率基本一致，但Trie（3）＆CutTree的預取條件更嚴苛，所以它的預取次數比C－Miner減少40%左右，緩存替換次數比C－Miner減少8%左右．

從圖6可以看出，Trie（3）＆CutTree的預取準確率是最高的，達到92．9%；C－Miner的預取準確率是最低的，只有75．4%；另外，LRU算法不存在預取，所以不考慮它的預取準確率．從而，根據圖5和圖6可以得出，Trie（3）＆CutTree在緩存命中率與C－Miner達到相同效果的情況下，預取的準確率更高，從而能夠有效減輕磁盤負擔，并降低緩存替換的頻度．

5 結 論

本文提出一種基于頻繁序列挖掘的預取算法，它能夠挖掘存儲系統中數據塊的關聯性，并通過合理使用這些關聯特性，提高緩存的命中率．與通用的C－Miner算法相比，本文方法使用關聯規則的條件更加嚴苛，使得它能在命中率與C－Miner基本保持一致的情況下，表現出更高的預取精度，這使得它在存儲系統內存資源有限的情況下比C－Miner算法更加適用．

［1］Agrawal R，Imielinski T，Swami A．Mining association rules between sets of items in large databases［C］??Proc of the 19th ACM SIGMOD Int Conf on Management of Data．New York：ACM，1993：207 216

［2］Agrawal R，Srikant R．Fast algorithms for mining association rules［C］??Proc of the 20th Int Conf on Very Large Data Bases．San Francisco，CA：Morgan Kaufmann，1994：487 499

［3］Pei J，Han J，Mortazavi－Asl B，et al．PrefixSpan：Mining sequential patterns efficiently by prefix－projected pattern growth［C］??Proc of the 17th Int Conf on Data Engineering．Washington，DC：IEEE Computer Society，2001：215 224

［4］Yan X，Han J，Afshar R．CloSpan：Mining closed sequential patterns in large datasets［C］??Proc of the 3rd SIAM Int Conf on Data Mining．Philadelphia，PA：SIAM，2003：166 177

［5］Wu Fengguang．Prefetching algorithm in Linux kernel［D］．Hefei：University of Science and Technology of China，2008（in Chinese）（吳峰光．Linux內核中的預取算法［D］．合肥：中國科學技術大學，2008）

［6］Ding Xiaoning，Jiang Song，Chen Feng，et al．DiskSeen：Exploiting disk layout and access history to enhance I?O prefetch［C］??Proc of the 2007USENIX Annual Technical Conf．Berkeley，CA：USENIX Association，2007：261 274

［7］Li Zhenmin，Chen Zhifeng，Sudarshan M，et al．C－Miner：Mining block correlations in storage systems［C］??Proc of the 3rd USENIX Conf on File and Storage Technologies．Berkeley，CA，USA：USENIX Association，2004：173 186

［8］Avichai G，Dan P，Eran R，et al．Using machine learning technique to enhance the performance of automatic backup and recovery system［C］??Proc of the 3rd Annual Haifa Experimental Systems Conf．New York：ACM，2010：1 10

［9］Li Zhenmin，Lu Shan，Myagmar S，et al．CP－Miner：Finding copy－paste and related bugs in large－scale software code［J］．IEEE Trans on Software Engineering，2006，32（3）：176 192

Wang Fang，born in 1972．Professor in the Huazhong University of Science and Technology．Member of China Computer Federation．Her main research insterests include computer architecture，computer energy，distributed file system and parallel I?O storage system．

Wang Peiqun，born in 1990．Received his master degree from the Huazhong University of Science and Technology．His main research interests include mass network storage system and parallel I?O storage system．

Zhu Chunjie，born in 1988．PhD in the Huazhong University of Science and Technology．Student member of China Computer Federation．His main research interests include mass network storage system and parallel I?O storage system．

Study and Implementation of Frequent Sequences Mining Based Prefetching Algorithm

Wang Fang1，2，Wang Peiqun2，and Zhu Chunjie11（Wuhan National Laboratory for Optoetectronics（Huazhong University of Science and Technology），Wuhan 430074）2（School of Computer Science and Technology，Huazhong University of Science and Technology，Wuhan 430074）

Prefetching technology is widely used as an efficient means to improve the performance of storage systems．However，traditional prefetching algorithms are mostly based on detecting sequential access features，which makes them hard to work in the environment with less or no sequential access features．What s worse，the storage system may even suffer from negative effects with poor prefetching accuracy．Whereas the proposed prefetching algorithm based on frequent sequences mining can make some contributions to the storage system in such environment by analyzing the behavior of the data accessing to find the potential rules．Meanwhile，in some application scenarios where the cache capacity may be limited，such as the embedded system，the proposed prefetching algorithm improves the prefetching accuracy to avoid some adverse impacts which may be caused by prefetching．The new proposed prefetching algorithm is based on the frequent sequences mining technology，and the prefetching rules derived from the mined frequent sequences are organized in a Trie tree．To improve the accuracy of the prefetching，the multistep matching technology and the subtree partitioning technology are introduced，which can subtly control the using of prefetching rules，so that the prefetching algorithm with relatively high prefetching accuracy can efficiently improve the performance of the storage system．

frequent sequences mining；prefetching algorithm；Trie tree；multistep matching；subtree partitioning

TP302

2014－09－19；

2015－05－14

國家“八六三”高技術研究發展計劃基金項目（2013AA013203）；華中科技大學自主創新研究基金項目（2014QN010）

This work was supported by the National High Technology Research and Development Program of China（863Program）（2013AA013203）and the Innovation Research Foundation of Huazhong University of Science and Technology（2014QN010）．

關鍵詞 頻繁序列挖掘；預取算法；字典樹；多步匹配；子樹分割