本站小編為你精心準(zhǔn)備了預(yù)取算法研究與實(shí)現(xiàn)參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

《計(jì)算機(jī)研究與發(fā)展雜志》2016年第二期

摘要

預(yù)取作為一種提升存儲(chǔ)系統(tǒng)性能的有效手段被廣泛使用，然而傳統(tǒng)的預(yù)取算法大多基于順序性訪問特征的探測(cè)，這使得它們?cè)诜琼樞驍?shù)據(jù)訪問環(huán)境下很難奏效，甚至可能因?yàn)轭A(yù)取準(zhǔn)確率較低而對(duì)存儲(chǔ)系統(tǒng)的性能帶來負(fù)面影響．而基于頻繁序列挖掘的預(yù)取算法則能夠通過分析數(shù)據(jù)的訪問行為找出潛在規(guī)律，從而能在非順序訪問模式下也取得一定的性能提升．同時(shí)，為了應(yīng)對(duì)某些緩存受限的應(yīng)用場(chǎng)景，如嵌入式系統(tǒng)，預(yù)取算法通過提高分析的準(zhǔn)確率減少預(yù)取可能對(duì)緩存帶來的不利影響．新提出的預(yù)取算法基于頻繁序列挖掘技術(shù)，并使用字典樹組織預(yù)取規(guī)則，通過多步匹配和子樹分割技術(shù)精細(xì)地控制規(guī)則的使用，提升預(yù)取的準(zhǔn)確率，從而使得預(yù)取算法能夠有效提升存儲(chǔ)系統(tǒng)的性能.

關(guān)鍵詞

頻繁序列挖掘；預(yù)取算法；字典樹；多步匹配；子樹分割

頻繁序列是指在一組有序的數(shù)據(jù)列組成的數(shù)據(jù)集合中，出現(xiàn)次數(shù)不小于閾值的序列．頻繁序列挖掘算法屬于數(shù)據(jù)挖掘的一個(gè)分支，它于1993年由Agrawal等人［1］提出，至今已經(jīng)有20多年歷史．期間出現(xiàn)了各種各樣的頻繁序列挖掘算法，具有代表性的有Apriori［2］，PrefixSpan［3］，CloSpan［4］等．預(yù)取作為一種提高性能的有效手段已被廣泛用于各種存儲(chǔ)系統(tǒng)中，而通常提到的預(yù)取大部分是基于順序訪問特征，例如Linux內(nèi)核使用一種帶有預(yù)取窗口的順序預(yù)取方法［5］，DiskSeen［6］采用一種基于歷史訪問信息分析的順序預(yù)取方法，它們的時(shí)間和空間開銷小，很多情況下對(duì)性能的提升也非常明顯．然而順序預(yù)取并不適用所有情形，特別是當(dāng)數(shù)據(jù)布局是非順序時(shí)，例如文件系統(tǒng)中元數(shù)據(jù)信息的訪問、數(shù)據(jù)庫文件內(nèi)部的索引結(jié)構(gòu)等．這種非順序的頻繁訪問模式在存儲(chǔ)系統(tǒng)中是比較常見的，于是出現(xiàn)了針對(duì)頻繁序列訪問模式的預(yù)取算法，最有代表性的是C－Miner［7］和C－Miner＊［8］，它們通過頻繁序列挖掘算法生成規(guī)則集，然后根據(jù)規(guī)則判斷需要預(yù)取的數(shù)據(jù)塊，但是它們挖掘過程中的時(shí)間和空間開銷比較大，而且對(duì)規(guī)則的利用不夠準(zhǔn)確高效．本文提出的Trie預(yù)取算法針對(duì)頻繁序列訪問模式，改進(jìn)了頻繁序列挖掘算法，并采用字典樹組織規(guī)則集，通過在樹中匹配序列判斷預(yù)取的數(shù)據(jù)塊，預(yù)取的準(zhǔn)確度更高．

1算法架構(gòu)

如圖1所示，Trie預(yù)取算法包括3部分，即緩存管理模塊，頻繁序列挖掘模塊和預(yù)取模塊．緩存管理模塊用于緩存塊設(shè)備上的部分?jǐn)?shù)據(jù)，如果上層用戶請(qǐng)求的數(shù)據(jù)在緩存管理模塊中，即緩存命中，則直接將緩存管理模塊的數(shù)據(jù)返回給上層用戶；如果不在，即緩存不命中，則需要向底層塊設(shè)備發(fā)出讀請(qǐng)求，并將取到的數(shù)據(jù)拷貝一份放入緩存模塊中，同時(shí)將數(shù)據(jù)返回給上層用戶．緩存模塊用LRU（leastrecentlyused）算法管理．頻繁序列挖掘模塊收集到達(dá)緩存的用戶請(qǐng)求元數(shù)據(jù)信息，并把它作為樣本序列，當(dāng)樣本序列達(dá)到預(yù)先設(shè)定的規(guī)模時(shí)，執(zhí)行頻繁序列挖掘算法，輸出頻繁序列數(shù)據(jù)集，即關(guān)聯(lián)規(guī)則.預(yù)取模塊產(chǎn)生預(yù)取請(qǐng)求．當(dāng)用戶請(qǐng)求在緩存模塊不命中時(shí)，預(yù)取模塊會(huì)搜索關(guān)聯(lián)規(guī)則，若找到與該請(qǐng)求相關(guān)的關(guān)聯(lián)規(guī)則，則根據(jù)這些關(guān)聯(lián)規(guī)則產(chǎn)生預(yù)取請(qǐng)求．

2頻繁序列挖掘算法

2．1請(qǐng)求序列預(yù)處理存儲(chǔ)系統(tǒng)中用戶請(qǐng)求序列是單個(gè)長(zhǎng)序列，無法直接適用頻繁序列挖掘算法，通常的做法是把這個(gè)長(zhǎng)序列分割成多個(gè)等長(zhǎng)的短序列．算法參考C－Miner的預(yù)處理方法，采用非重合式等長(zhǎng)分割．同時(shí)，短序列的長(zhǎng)度根據(jù)經(jīng)驗(yàn)預(yù)先設(shè)置一個(gè)合適的值，因?yàn)槿绻绦蛄械拈L(zhǎng)度太長(zhǎng)會(huì)導(dǎo)致挖掘算法的開銷劇增，長(zhǎng)度太短則可能丟失大量的頻繁序列信息．

2．2頻繁序列挖掘頻繁序列挖掘算法的核心數(shù)據(jù)結(jié)構(gòu)包括一棵字典樹和一個(gè)散列表，其中字典樹用于保存所有的頻繁序列信息，散列表用于臨時(shí)保存已處理的結(jié)點(diǎn)的信息．算法開始時(shí)，字典樹只有一個(gè)空的根結(jié)點(diǎn)指針head，散列表為空．為了提高挖掘效率，算法一方面根據(jù)頻繁條目集合對(duì)初始的數(shù)據(jù)集進(jìn)行修剪，從而大大減小后續(xù)操作中數(shù)據(jù)集的大小；另一方面，利用散列表快速判斷等價(jià)結(jié)點(diǎn)，從而減小遞歸深度．具體處理步驟描述如下：輸出：以字典樹組織的頻繁序列集．步驟1．對(duì)初始數(shù)據(jù)集S進(jìn)行統(tǒng)計(jì)，得到所有長(zhǎng)度為1的頻繁條目，組成頻繁條目集合．如果此集合為空，則整個(gè)算法結(jié)束；否則創(chuàng)建head結(jié)點(diǎn)，將集合中的條目存放在head結(jié)點(diǎn)中，將head結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，并進(jìn)入步驟2．步驟2．根據(jù)步驟1中得到的頻繁條目集合對(duì)初始的數(shù)據(jù)集S進(jìn)行修剪，除去S中的非頻繁條目，得到精簡(jiǎn)的數(shù)據(jù)集S′，將S′作為當(dāng)前數(shù)據(jù)集，并進(jìn)入步驟3．步驟3．根據(jù)當(dāng)前數(shù)據(jù)集的大小快速判斷當(dāng)前結(jié)點(diǎn)在散列表中是否存在等價(jià)的結(jié)點(diǎn)．若存在等價(jià)的結(jié)點(diǎn)，則算法對(duì)當(dāng)前結(jié)點(diǎn)的遞歸調(diào)用結(jié)束，并進(jìn)入步驟5，否則進(jìn)入步驟4．步驟4．取當(dāng)前結(jié)點(diǎn)的1個(gè)條目生成相應(yīng)的數(shù)據(jù)集，如果該條目的后綴數(shù)據(jù)集不為空，則為此條目創(chuàng)建1個(gè)新結(jié)點(diǎn)，并把新結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，跳入步驟3，否則繼續(xù)對(duì)當(dāng)前結(jié)點(diǎn)的下1個(gè)條目作步驟4的操作；如果當(dāng)前結(jié)點(diǎn)的條目全部處理完，則進(jìn)入步驟5．步驟5．判斷當(dāng)前結(jié)點(diǎn)在字典樹中是否存在未遍歷的兄弟結(jié)點(diǎn)，若存在，則把兄弟結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，并轉(zhuǎn)入步驟3，否則將當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)；如果當(dāng)前結(jié)點(diǎn)是head，則整個(gè)算法結(jié)束，否則重復(fù)步驟5．挖掘算法結(jié)束后，規(guī)則樹中有很多并不是閉合的頻繁序列，需要對(duì)它們進(jìn)行刪除．由于散列表中保存的結(jié)點(diǎn)在具有等價(jià)后綴數(shù)據(jù)庫的結(jié)點(diǎn)中，均是最長(zhǎng)的序列，因此對(duì)散列表中所有的結(jié)點(diǎn)進(jìn)行掃描，查找到所有葉子結(jié)點(diǎn)，將它們標(biāo)記為FLAG＿CLOSET，并將它們的所有祖先結(jié)點(diǎn)標(biāo)記為FLAG＿INUSE．散列表掃描結(jié)束后，對(duì)之前生成的頻繁序列集進(jìn)行整理，僅保留標(biāo)志位FLAG＿INUSE的結(jié)點(diǎn)，新生成的樹則為最終的頻繁序列規(guī)則字典樹．如果把挖掘的頻繁序列的長(zhǎng)度限制成1個(gè)常量，則此算法在最壞情況下與CloSpan算法的時(shí)間復(fù)雜度相當(dāng)，即為O（n2）［9］，同時(shí)，由于在CloSpan算法的基礎(chǔ)上做了上述優(yōu)化，所以新算法的計(jì)算開銷更小．

3基于字典樹匹配的預(yù)取算法

為了能夠有效存儲(chǔ)和使用挖掘算法輸出的關(guān)聯(lián)規(guī)則，預(yù)取算法采用字典樹組織規(guī)則．任何一條頻繁序列都是作為一個(gè)整體出現(xiàn)的，一旦檢測(cè)到某個(gè)頻繁序列的第1個(gè)請(qǐng)求時(shí)，預(yù)取算法就將該頻繁序列中的所有其他請(qǐng)求預(yù)取到內(nèi)存．圖2描述了一棵簡(jiǎn)單的頻繁序列規(guī)則樹，它包含5條頻繁序列｛abcd，aefg，aefh，b，cfai｝．其中，所有規(guī)則的前綴都分布于規(guī)則樹的第1層，那么當(dāng)請(qǐng)求到來時(shí)僅需要從規(guī)則樹的第1層查找訪問請(qǐng)求是否存在．如果存在，則表示在接下來的訪問可能對(duì)應(yīng)于請(qǐng)求子樹中的某一條頻繁序列，需要將這棵樹的子樹預(yù)取到內(nèi)存中．例如，如果探測(cè)到請(qǐng)求條目a，則將a的子樹的所有條目｛b，c，d，e，f，g，h｝預(yù)取到內(nèi)存中．雖然在頻繁序列cfai中，條目a與條目i也存在關(guān)聯(lián)關(guān)系，但是由于沒有探測(cè)到條目c的到來，i不會(huì)被預(yù)取．采用這樣的方式，可以大量減少無關(guān)數(shù)據(jù)的預(yù)取，從而減少預(yù)取的失效率．然而，當(dāng)字典樹具有較多分支且樹的深度較深時(shí)，上述預(yù)取方式仍然會(huì)導(dǎo)致過度預(yù)取，特別是當(dāng)系統(tǒng)緩存比較小時(shí)，這種預(yù)取方式可能給系統(tǒng)帶來更大的負(fù)擔(dān)．因此，為了進(jìn)一步提高預(yù)取的精度，提出了多步匹配和子樹分割的方法．

3．1多步匹配上述提到的基于字典樹匹配的預(yù)取算法僅僅通過匹配頻繁序列前綴的首個(gè)條目，就預(yù)取該條目的所有子樹上的條目．如果某條目有多棵子樹（如圖2中的條目a有2棵子樹），那么預(yù)取時(shí)將會(huì)把這2棵子樹上的所有條目都預(yù)取到內(nèi)存中，但實(shí)際上可能只有1棵子樹將被訪問，特別是當(dāng)子樹很多時(shí)，這種預(yù)取的正確率更低，帶來的開銷也更大．多步匹配能夠較好地解決這個(gè)問題，其基本思路是當(dāng)一個(gè)條目有多棵子樹時(shí)，先把此條目保存在一個(gè)隊(duì)列結(jié)構(gòu)中，當(dāng)該條目的某個(gè)子樹的根條目被訪問時(shí)，則將這個(gè)子樹的根條目也加入到此隊(duì)列中，直到一個(gè)頻繁序列的前n個(gè)條目都出現(xiàn)時(shí)，才把此頻繁序列的后續(xù)條目全部預(yù)取到內(nèi)存．具體的做法是在緩存中創(chuàng)建一個(gè)隊(duì)列，每當(dāng)一個(gè)新的請(qǐng)求到來時(shí)，通過對(duì)比隊(duì)列中已經(jīng)匹配的前綴，決定是否進(jìn)行匹配層級(jí)增加或者進(jìn)行預(yù)取操作．圖3模擬一個(gè)正在運(yùn)行的多步預(yù)取隊(duì)列，設(shè)定的預(yù)取步長(zhǎng)為4．在條目f到達(dá)之前，匹配隊(duì)列中維護(hù)著若干個(gè)已經(jīng)匹配的條目，隊(duì)列的每個(gè)結(jié)點(diǎn)保存一個(gè)條目的數(shù)據(jù)塊信息及當(dāng)前已經(jīng)匹配的層級(jí)，同時(shí)還有一個(gè)結(jié)構(gòu)指向規(guī)則樹中已經(jīng)匹配到的結(jié)點(diǎn)．當(dāng)f到達(dá)時(shí)，從LRU隊(duì)列的頂端查找是否所指向的樹結(jié)點(diǎn)的子結(jié)點(diǎn)中存在f，如果存在，則將結(jié)構(gòu)放到LRU的頂端，并且匹配層級(jí)自增1．例如，從圖2可以看出，條目e所在的結(jié)點(diǎn)的子樹中有f，所以當(dāng)f到達(dá)時(shí)，用f替代e，并且將此結(jié)點(diǎn)的匹配層級(jí)變?yōu)?．如果經(jīng)過變化的匹配層級(jí)達(dá)到多步預(yù)取的步長(zhǎng)4，則進(jìn)行預(yù)取操作，并且將該結(jié)點(diǎn)刪除；否則沒有達(dá)到預(yù)取的要求，繼續(xù)進(jìn)行后面的操作．

3．2子樹分割多步匹配策略提高了預(yù)取的準(zhǔn)確度，而且步長(zhǎng)越長(zhǎng)，預(yù)取的準(zhǔn)確度也越高，然而如果步長(zhǎng)設(shè)置過長(zhǎng)，則預(yù)取的數(shù)據(jù)會(huì)大大減小，使得預(yù)取的效果被削弱，而且匹配帶來的開銷也會(huì)增大，故在使用時(shí)需要設(shè)置一個(gè)比較合適的步長(zhǎng)．但是在某些情況下，超過設(shè)定步長(zhǎng)的子樹仍然有很多分支，此時(shí)多步匹配對(duì)精度的提高就比較有限．為了應(yīng)對(duì)這種情況，提出子樹分割的策略，即將規(guī)則生成樹進(jìn)行預(yù)處理，使得規(guī)則樹的高度維持在一定范圍內(nèi)，而分割后靠近葉子結(jié)點(diǎn)的部分掛載到另外一個(gè)線性表中，只有在實(shí)際訪問到某棵子樹的父結(jié)點(diǎn)時(shí)，才將其預(yù)取到緩存中．圖4描述了對(duì)前面描述的例子中的子樹進(jìn)行分割的過程，設(shè)定子樹分割的深度為2，那么將初始的規(guī)則樹深度為2的子樹全部切割，掛載到一個(gè)數(shù)組下面．當(dāng)條目a的請(qǐng)求到來時(shí)，根據(jù)規(guī)則樹將b和e預(yù)取到內(nèi)存中，但卻不預(yù)取它們各自的子樹cd和fgh．而且隨著請(qǐng)求的繼續(xù)，若某一時(shí)刻，條目e在內(nèi)存中命中，并檢測(cè)到該條目e是某一棵子樹的根結(jié)點(diǎn)，那么通過其ID查找到相應(yīng)的子樹，從而將子樹預(yù)取．

4實(shí)驗(yàn)及結(jié)果分析

本文的負(fù)載采用惠普實(shí)驗(yàn)室的HPCello96數(shù)據(jù)集，它是1996年在惠普Cello系統(tǒng)上跟蹤采集的2級(jí)磁盤IO請(qǐng)求，而Cello是由一組研究者用來作仿真、編譯、編輯文檔和收發(fā)郵件的分時(shí)共享系統(tǒng)．為了驗(yàn)證算法，搭建了模擬實(shí)驗(yàn)原型系統(tǒng)，原型系統(tǒng)的架構(gòu)與圖1基本吻合．實(shí)驗(yàn)平臺(tái)是1臺(tái)浪潮NF5280服務(wù)器，具體的硬件配置如表1所示．原型系統(tǒng)運(yùn)行于64位RedHatEnterpriseLinuxServerRelease5．3操作系統(tǒng)上，它是自主實(shí)現(xiàn)的一個(gè)用戶態(tài)仿真程序，包括緩存管理模塊、頻繁序列挖掘模塊和預(yù)取模塊，其中緩存管理模塊不存儲(chǔ)真實(shí)的數(shù)據(jù)，只存儲(chǔ)請(qǐng)求的元數(shù)據(jù)信息，因?yàn)橥ㄟ^元數(shù)據(jù)信息就可以判斷是否命中．實(shí)驗(yàn)方法分2個(gè)階段，第1階段是頻繁序列挖掘階段，此階段尚沒有關(guān)聯(lián)規(guī)則可用，所以預(yù)取模塊不可用．當(dāng)關(guān)聯(lián)規(guī)則樹生成后，程序進(jìn)入第2階段，此階段預(yù)取模塊是可用的．分段的標(biāo)準(zhǔn)是trace文件中前半部分的IO請(qǐng)求屬于第1階段，后半部分屬于第2階段．這種實(shí)驗(yàn)方法是參考C－Miner中的做法，方便與之對(duì)比．圖5和圖6分別描述了不同算法的命中率和預(yù)取準(zhǔn)確率的比較情況，緩存大小為64MB．其中LRU是標(biāo)準(zhǔn)的緩存替換算法；C－Miner是目前比較好的一個(gè)頻繁序列預(yù)取算法；Trie是單步匹配的頻繁序列預(yù)取算法，是本文的核心算法；Trie（3）是3步匹配的頻繁序列預(yù)取算法，是對(duì)Trie的一種改進(jìn)；Trie（3）＆CutTree是同時(shí)使用3步匹配和子樹分割策略優(yōu)化的頻繁序列預(yù)取算法，是在Trie（3）的基礎(chǔ)上做進(jìn)一步的優(yōu)化．從圖5可以看出，LRU算法的緩存命中次數(shù)在580000左右，其他4種算法的緩存命中次數(shù)均在750000左右，即Trie（3）＆CutTree算法的緩存命中率比LRU算法提高29．3％，與C－Miner算法的緩存命中率基本一致，但Trie（3）＆CutTree的預(yù)取條件更嚴(yán)苛，所以它的預(yù)取次數(shù)比C－Miner減少40％左右，緩存替換次數(shù)比C－Miner減少8％左右．從圖6可以看出，Trie（3）＆CutTree的預(yù)取準(zhǔn)確率是最高的，達(dá)到92．9％；C－Miner的預(yù)取準(zhǔn)確率是最低的，只有75．4％；另外，LRU算法不存在預(yù)取，所以不考慮它的預(yù)取準(zhǔn)確率．從而，根據(jù)圖5和圖6可以得出，Trie（3）＆CutTree在緩存命中率與C－Miner達(dá)到相同效果的情況下，預(yù)取的準(zhǔn)確率更高，從而能夠有效減輕磁盤負(fù)擔(dān)，并降低緩存替換的頻度．

5結(jié)論

本文提出一種基于頻繁序列挖掘的預(yù)取算法，它能夠挖掘存儲(chǔ)系統(tǒng)中數(shù)據(jù)塊的關(guān)聯(lián)性，并通過合理使用這些關(guān)聯(lián)特性，提高緩存的命中率．與通用的C－Miner算法相比，本文方法使用關(guān)聯(lián)規(guī)則的條件更加嚴(yán)苛，使得它能在命中率與C－Miner基本保持一致的情況下，表現(xiàn)出更高的預(yù)取精度，這使得它在存儲(chǔ)系統(tǒng)內(nèi)存資源有限的情況下比C－Miner算法更加適用．

作者：王芳 王培群 朱春節(jié) 單位：武漢光電國家實(shí)驗(yàn)室 華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院