基于頻繁序列挖掘的預(yù)取方法研究.pdf

1、在存儲系統(tǒng)中，CPU的處理速度遠(yuǎn)大于磁盤等I/O設(shè)備的讀寫速度，兩者間的速度不匹配嚴(yán)重影響了系統(tǒng)整體性能。預(yù)取技術(shù)能夠有效地彌補(bǔ)I/O設(shè)備與CPU之間的速度差異，因此被廣泛應(yīng)用。隨著云技術(shù)、虛擬化技術(shù)的普及，集中存儲前端往往承載著各種應(yīng)用服務(wù)，導(dǎo)致前端單一應(yīng)用負(fù)載內(nèi)在的訪問局部性和順序性在后端被破壞，以往廣泛采用的順序預(yù)取不能很好地發(fā)揮作用。針對這樣的問題，提出一種基于頻繁序列挖掘的預(yù)取算法，以改進(jìn)I/O預(yù)取效率，提高存儲性能。

2、　　然而目前已提出的許多頻繁序列挖掘算法針對的問題基本上是相關(guān)性挖掘、關(guān)聯(lián)性分析等對時(shí)間響應(yīng)沒有嚴(yán)格要求的場景，這類場景更多的是關(guān)注序列挖掘的準(zhǔn)確性從而相對地忽視了挖掘效率。但實(shí)時(shí)預(yù)取等時(shí)間關(guān)鍵的應(yīng)用場景更多關(guān)注響應(yīng)時(shí)間，現(xiàn)有的頻繁序列挖掘算法往往會產(chǎn)生較大的時(shí)間開銷。因此為了降低挖掘開銷，適應(yīng)存儲系統(tǒng)等場景的在線連續(xù)運(yùn)行，快速的頻繁序列挖掘算法TcMiner能夠有效地解決時(shí)間關(guān)鍵場景的局限性帶來的問題。
　　基于TcMiner預(yù)

3、取算法利用頻繁序列挖掘技術(shù)對已發(fā)生的I/O訪問行為進(jìn)行快速分析，獲取相關(guān)性強(qiáng)的數(shù)據(jù)序列，形成預(yù)取規(guī)則并采用子樹間無包含關(guān)系的字典樹（Tire Tree）來保存數(shù)據(jù)塊間的相互關(guān)系，從而進(jìn)行精度較高的預(yù)取操作。同時(shí)，為了適應(yīng)不同的負(fù)載環(huán)境，在采用字典樹進(jìn)行預(yù)取的基礎(chǔ)上進(jìn)一步改進(jìn)的多步預(yù)取和子樹切割兩種算法也可以進(jìn)一步提高預(yù)取算法的精度。
　　測試表明，在內(nèi)存占數(shù)據(jù)量5％的情況下，基于TcMiner的預(yù)取算法及其改進(jìn)方法相比于LRU算法