在大規(guī)模文件系統(tǒng)中，大多數(shù)文件長(zhǎng)期不用，少數(shù)文件經(jīng)常使用，就單個(gè)文件來(lái)說(shuō)，剛創(chuàng)建之后的一段時(shí)間內(nèi)訪問(wèn)頻率最高；隨著時(shí)間推移，訪問(wèn)頻率下降，鑒于不同數(shù)據(jù)之間存在著顯著的訪問(wèn)頻率差異，人們提出了分級(jí)存儲(chǔ)系統(tǒng)，它由具有不同的存儲(chǔ)容量、I／O速度、單位價(jià)格的多級(jí)存儲(chǔ)設(shè)備構(gòu)成；按照近期訪問(wèn)情況的不同，將數(shù)據(jù)存放到合適的存儲(chǔ)設(shè)備上，目標(biāo)是在滿足存儲(chǔ)容量和硬件成本約束的前提下，提供較高的I／O性能。
在分級(jí)存儲(chǔ)系統(tǒng)中，數(shù)據(jù)的訪問(wèn)頻率和服務(wù)質(zhì)量需求是不斷變化的，為了使數(shù)據(jù)能夠與存儲(chǔ)設(shè)備動(dòng)態(tài)匹配，需要在不同級(jí)別的存儲(chǔ)設(shè)備之間遷移數(shù)據(jù)，數(shù)據(jù)遷移的規(guī)則通常由數(shù)據(jù)的訪問(wèn)頻率、存儲(chǔ)設(shè)備的容量和性能等因素確定，這就要求分級(jí)存儲(chǔ)系統(tǒng)能夠檢測(cè)到數(shù)據(jù)狀態(tài)的變化，并進(jìn)行數(shù)據(jù)在線遷移，同時(shí)，數(shù)據(jù)位置的移動(dòng)需要對(duì)應(yīng)用是透明的，數(shù)據(jù)遷移過(guò)程對(duì)于應(yīng)用I／O性能影響不大。
現(xiàn)有的分級(jí)存儲(chǔ)系統(tǒng)中的數(shù)據(jù)遷移方法對(duì)前臺(tái)I／O性能影響較大，原因包括數(shù)據(jù)分級(jí)只考慮文件的創(chuàng)建時(shí)間、上次訪問(wèn)時(shí)間或文件大小等單一因素；數(shù)據(jù)訪問(wèn)缺失則觸發(fā)數(shù)據(jù)升級(jí)活動(dòng)，造成數(shù)據(jù)遷移量較大；數(shù)據(jù)降級(jí)遷移過(guò)程缺乏自動(dòng)控制。
本文提出了分級(jí)存儲(chǔ)系統(tǒng)中一種數(shù)據(jù)自動(dòng)遷移方法AutoMig，它綜合考慮了文件訪問(wèn)歷史、文件大小、設(shè)備的空間利用情況、文件關(guān)聯(lián)性等因素，對(duì)文件進(jìn)行動(dòng)態(tài)分級(jí)，并在數(shù)據(jù)遷移過(guò)程中，根據(jù)負(fù)載變化自適應(yīng)地調(diào)整遷移速率，在實(shí)際系統(tǒng)中的實(shí)驗(yàn)表明：與已有方法相比，AutoMig有效縮短了前臺(tái)I／O響應(yīng)時(shí)間。
1 相關(guān)工作
He等人提出了一種基于面向?qū)ο笪募到y(tǒng)Lustre的分級(jí)存儲(chǔ)系統(tǒng)，數(shù)據(jù)從磁帶到磁盤(pán)的遷移是由訪問(wèn)缺失觸發(fā)的，缺點(diǎn)是升級(jí)的文件過(guò)多，SANBoost系統(tǒng)口3使用SSD設(shè)備和磁盤(pán)構(gòu)成兩級(jí)存儲(chǔ)系統(tǒng)，它引入一個(gè)遷移閾值以減少數(shù)據(jù)遷移量，只有用戶訪問(wèn)達(dá)到一定次數(shù)后才進(jìn)行遷移。
有效的數(shù)據(jù)預(yù)取能夠降低I／O訪問(wèn)延遲，而錯(cuò)誤的預(yù)取只會(huì)干擾前臺(tái)I／O負(fù)載，已經(jīng)有一些數(shù)據(jù)預(yù)取算法，如穩(wěn)固后繼預(yù)測(cè)方法、首次穩(wěn)固后繼、最近最常見(jiàn)預(yù)測(cè)方法等，它們的缺點(diǎn)是只預(yù)測(cè)下一個(gè)訪問(wèn)，可用于預(yù)取的時(shí)間間隙很短。
降級(jí)遷移算法需要選擇遷移哪些文件到慢速設(shè)備，現(xiàn)有的降級(jí)遷移算法主要包括FIFO，LRU，size—only，space—time和file—aging，space—time算法根據(jù)文件大小和文件上次使用間隔的乘積來(lái)分級(jí)，file-aging算法根據(jù)文件上次使用時(shí)間、文件大小和以前計(jì)算的遷移值來(lái)計(jì)算當(dāng)前的遷移值，應(yīng)用在Web文件緩存中的GreedyDualSize替換算法，根據(jù)文件的時(shí)效性、大小和預(yù)取成本給出文件替換決策。
分級(jí)存儲(chǔ)系統(tǒng)TH—TS中實(shí)現(xiàn)了一種自動(dòng)的數(shù)據(jù)遷移方法CuteMig，它的缺點(diǎn)是沒(méi)有考慮文件訪問(wèn)之間的關(guān)聯(lián)性。
在數(shù)據(jù)遷移速率控制方面，第1種方式在保證數(shù)據(jù)遷移期限的前提下，盡量使用磁盤(pán)的空閑周期進(jìn)行數(shù)據(jù)遷移，第2種方式MS Manners，當(dāng)檢測(cè)到非重要進(jìn)程的前進(jìn)速度放緩時(shí)，進(jìn)一步降低它的運(yùn)行速率，第3種方式Aqueduct把存儲(chǔ)系統(tǒng)看作一個(gè)黑盒子，只測(cè)量應(yīng)用所察覺(jué)到的性能，因此無(wú)法迅速檢測(cè)到存儲(chǔ)系統(tǒng)上的應(yīng)用負(fù)載的變化，第4種方式是用收益最大化框架來(lái)解決數(shù)據(jù)遷移問(wèn)題，缺點(diǎn)是需要事先詳細(xì)掌握系統(tǒng)特性和負(fù)載特征，從而使該方法受到一定的實(shí)用性限制。
2 數(shù)據(jù)遷移方法AutoMig
數(shù)據(jù)自動(dòng)遷移方法AutoMig由3部分組成：1)數(shù)據(jù)動(dòng)態(tài)分級(jí)策略，數(shù)據(jù)分級(jí)的改變觸發(fā)數(shù)據(jù)的遷移；2)關(guān)聯(lián)文件挖掘技術(shù)，關(guān)聯(lián)的文件用于自動(dòng)預(yù)取；3)遷移過(guò)程中的速率控制，在前臺(tái)I／O性能影響和數(shù)據(jù)遷移完成期限之間尋找合理的權(quán)衡。
2.1數(shù)據(jù)動(dòng)態(tài)分級(jí)策略
AutoMig中的數(shù)據(jù)分級(jí)評(píng)價(jià)包括文件升級(jí)評(píng)價(jià)和文件降級(jí)評(píng)價(jià)2部分。
AutoMig根據(jù)數(shù)據(jù)升級(jí)的單位成本收益效率來(lái)決定是否對(duì)文件執(zhí)行升級(jí)操作，文件升級(jí)的收益效率用文件升級(jí)后單位時(shí)間內(nèi)被訪問(wèn)的數(shù)據(jù)量來(lái)衡量，令A(yù)S和AF分別表示文件升級(jí)后的文件訪問(wèn)大小和文件訪問(wèn)頻率，則文件升級(jí)后的性能收益效率為AS×AF，文件升級(jí)的成本可以使用文件大小FS來(lái)衡量，由此，數(shù)據(jù)升級(jí)的單位成本收益效率（即效用值）計(jì)算為util=(AS×AF)/FS，如果一個(gè)文件的升級(jí)效用值高于升級(jí)閾值，則升級(jí)該文件。
在給出升級(jí)決策時(shí)，只有文件大小FS是確定的，AutoMig統(tǒng)計(jì)文件歷次訪問(wèn)大小的平均值，作為未來(lái)訪問(wèn)大小AS的估計(jì)值，為了能夠在文件訪問(wèn)間隔的預(yù)測(cè)中體現(xiàn)變化趨勢(shì)，引入時(shí)效性因子(recency factor)概念，預(yù)測(cè)文件訪問(wèn)間隔的公式為Ik=β×Ik-1+（1-β）×Mk，這里，M為第k次訪問(wèn)間隔的測(cè)量值；β為時(shí)效性因子，因?yàn)? <β<1，一次測(cè)量值對(duì)于未來(lái)預(yù)測(cè)值的貢獻(xiàn)隨著時(shí)間而以因子β衰減。
AutoMig降級(jí)算法的基本思想是，根據(jù)訪問(wèn)情況在LRU隊(duì)列中維護(hù)快速存儲(chǔ)設(shè)備上的所有文件，一個(gè)降級(jí)線程每隔一定時(shí)間從LRU隊(duì)列中取出最冷的文件作為降級(jí)對(duì)象，該降級(jí)間隔時(shí)間長(zhǎng)短與快速存儲(chǔ)設(shè)備的空間空閑率有關(guān)。
AutoMig的數(shù)據(jù)升級(jí)算法兼顧了文件訪問(wèn)歷史和文件大小兩個(gè)指標(biāo)，既使得文件遷移所需代價(jià)相對(duì)較小，也保證遷移后得到的文件I/O性能收益較高，降級(jí)間隔的確定方式保證了快速存儲(chǔ)設(shè)備始終有足夠的空閑空間，當(dāng)存儲(chǔ)在慢速存儲(chǔ)設(shè)備上的文件被訪問(wèn)時(shí)，計(jì)算升級(jí)遷移的效用值；當(dāng)存儲(chǔ)在快速設(shè)備上的文件被訪問(wèn)時(shí)，更新對(duì)應(yīng)LRU隊(duì)列狀態(tài)，數(shù)據(jù)動(dòng)態(tài)分級(jí)算法無(wú)需定期掃描所有文件以進(jìn)行文件價(jià)值評(píng)價(jià)，故增加的計(jì)算開(kāi)銷(xiāo)不大。
2.2關(guān)聯(lián)文件挖掘技術(shù)
為了有效實(shí)現(xiàn)文件預(yù)取，AutoMig使用數(shù)據(jù)挖掘技術(shù)來(lái)有效識(shí)別系統(tǒng)中的文件關(guān)聯(lián)性，它把一個(gè)文件映射成一個(gè)項(xiàng)，把一個(gè)訪問(wèn)序列映射成序列數(shù)據(jù)庫(kù)中的一個(gè)序列，一個(gè)頻繁子序列表示相關(guān)文件經(jīng)常一起被訪問(wèn)。
一個(gè)文件能以各種方式訪問(wèn)，除了打開(kāi)關(guān)閉，還可能以進(jìn)程形式執(zhí)行，AutoMig通過(guò)記錄這些系統(tǒng)調(diào)用來(lái)構(gòu)建一個(gè)長(zhǎng)的訪問(wèn)trace. AutoMig采用簡(jiǎn)單切割的方法把長(zhǎng)trace切成許多短序列，AutoMig把問(wèn)題轉(zhuǎn)化為挖掘頻繁閉合序列問(wèn)題，采用挖掘算法BIDE，并作了一定程度的改進(jìn)。
BIDE算法本質(zhì)是以深度優(yōu)先的方式，一邊構(gòu)建頻繁子樹(shù)，一邊檢查閉合性，一邊進(jìn)行剪枝，BIDE算法實(shí)現(xiàn)的兩個(gè)關(guān)鍵任務(wù)是：1）閉合性檢查；2)搜索空間剪枝，BIDE算法采用了雙向擴(kuò)展模式：向前擴(kuò)展用于增長(zhǎng)前綴模式和前綴模式的閉合性檢查；向后擴(kuò)展用于前綴模式的閉合性檢查和搜索空間剪枝，對(duì)于當(dāng)前序列，BIDE向前掃描每個(gè)映射序列，找到局部頻繁項(xiàng)，對(duì)于每個(gè)局部頻繁項(xiàng)，檢查是否可以剪枝，如果不能剪枝則向前擴(kuò)展當(dāng)前序列。
在AutoMig實(shí)現(xiàn)中，運(yùn)用邏輯短路原理，對(duì)BIDE作了3點(diǎn)優(yōu)化：
1)閉合性檢查時(shí)，因?yàn)橄蚯皵U(kuò)展檢查是容易完成的，故先做向前檢查，若“沒(méi)有向前擴(kuò)展項(xiàng)”這一命題為假，則無(wú)需進(jìn)行向后檢查；
2)在每次進(jìn)行閉合性檢查時(shí)，都已經(jīng)有在半最大段組中搜索不到向后擴(kuò)展項(xiàng)這一結(jié)論，如果該前綴序列的第一實(shí)例的最后一項(xiàng)和最后實(shí)例的最后一項(xiàng)位置相同，則不必檢查最大段就可斷定沒(méi)有向后擴(kuò)展項(xiàng)；
3)眾多最大段組中只要得到一個(gè)最大段組中各序列交集非空即可斷定向后擴(kuò)展項(xiàng)存在。
為了把頻繁序列轉(zhuǎn)換成關(guān)聯(lián)規(guī)則，AutoMig由每個(gè)序列生成一些規(guī)則，AutoMig規(guī)定一個(gè)規(guī)則右邊的項(xiàng)數(shù)為1，因?yàn)檫@對(duì)于文件預(yù)取是足夠的，為了限制規(guī)則數(shù)目，AutoMig約束一個(gè)規(guī)則左邊的項(xiàng)數(shù)不超過(guò)2。
AutoMig還用可信度參數(shù)來(lái)衡量規(guī)則的可依賴程度，一條規(guī)則a一b的可信度可以通過(guò)如下公式計(jì)算：conf（a-6）=sup（ab）/sup(a)，這里，sup(a)和sup(ab)分別表示序列a和序列ab的支持度，當(dāng)用一條關(guān)聯(lián)規(guī)則來(lái)預(yù)測(cè)未來(lái)訪問(wèn)時(shí)，規(guī)則的可信度表示預(yù)測(cè)的精度，AutoMig使用最小可信度閾值過(guò)濾低質(zhì)量的關(guān)聯(lián)規(guī)則，剩下的規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則。
把這些強(qiáng)關(guān)聯(lián)規(guī)則直接用于文件預(yù)取，存在嚴(yán)重的冗余現(xiàn)象，從而加重了維護(hù)和查找的成本，把前件長(zhǎng)度為L(zhǎng)的規(guī)則稱為“L_規(guī)則”，對(duì)于一條2-規(guī)則xy-z，AutoMig通過(guò)檢查是否存在同時(shí)滿足如下條件的1-規(guī)則a-b來(lái)判斷它是否為冗余規(guī)則：1)b=z，即有著相同后件；2）a-x或者a-y，即1-規(guī)則的前件與2一規(guī)則的前件中某項(xiàng)相同，AutoMig -旦檢測(cè)到冗余規(guī)則，就將其從規(guī)則集合中刪除，剩下非冗余的強(qiáng)關(guān)聯(lián)規(guī)則可以直接用于文件預(yù)取。
預(yù)取與升級(jí)文件相關(guān)聯(lián)的文件可以降低對(duì)這些文件的訪問(wèn)延遲，然而，一個(gè)普遍擔(dān)心的是數(shù)據(jù)預(yù)取是否會(huì)影響正常數(shù)據(jù)升級(jí)的性能，AutoMig采取兩種方法來(lái)避免文件預(yù)取的性能影響，對(duì)于關(guān)聯(lián)的小文件組，在低級(jí)設(shè)備上集中存放，并采取升級(jí)捎帶的方式進(jìn)行預(yù)取，對(duì)于稍大的關(guān)聯(lián)文件，采取下面介紹的速率控制機(jī)制來(lái)保證在前臺(tái)負(fù)載較輕時(shí)執(zhí)行數(shù)據(jù)預(yù)取。
2.3 遷移速率控制機(jī)制
AutoMig中的遷移速率控制方法，將遷移任務(wù)劃分成緊急遷移和可控遷移2種，并采用不同的遷移速率控制策略，文件升級(jí)等任務(wù)比較緊迫，因而采用“盡力而為”的策略；降級(jí)任務(wù)、數(shù)據(jù)預(yù)取等任務(wù)相對(duì)不緊迫，可以進(jìn)行速率控制。
AutoMig的遷移速率控制的核心思想是反饋控制，系統(tǒng)檢測(cè)當(dāng)前存儲(chǔ)子系統(tǒng)的負(fù)載密集程度，相應(yīng)的調(diào)整遷移速率，從而平衡系統(tǒng)性能和遷移效率間的矛盾，圖1給出了反饋控制的邏輯示意圖，執(zhí)行器以一定速率執(zhí)行數(shù)據(jù)遷移操作，檢測(cè)器對(duì)存儲(chǔ)子系統(tǒng)進(jìn)行采樣，并把所得的負(fù)載信息W (k)傳遞給控制器，控制器比對(duì)W(k)和性能參照值，并通過(guò)控制函數(shù)來(lái)調(diào)整遷移速率，輸出新的遷移速率R(k)給執(zhí)行器，執(zhí)行器相應(yīng)地調(diào)整數(shù)據(jù)降級(jí)的速率。
圖1 反饋控制的邏輯示意圖
在分級(jí)存儲(chǔ)系統(tǒng)中，快速存儲(chǔ)設(shè)備往往負(fù)載較重，而慢速存儲(chǔ)設(shè)備一般是低負(fù)載或者無(wú)負(fù)載的，所以在速率控制過(guò)程中，主要考慮的是快速存儲(chǔ)設(shè)備所承受的IOPS。
控制器的性能參照值為W，它是快速存儲(chǔ)設(shè)備所能承受的最大負(fù)載，負(fù)載總量w由前臺(tái)I/O請(qǐng)求和遷移I/O請(qǐng)求兩部分組成，每個(gè)采樣周期，控制器得到存儲(chǔ)設(shè)備的負(fù)載參數(shù)W(k)，首先，控制器計(jì)算W(k)與性能參照值之間的差值：E(k)=W-W(k)，在得到E(k)之后，通過(guò)控制函數(shù)計(jì)算出新的遷移速率：R(k) =R(k-1)+E(k)。
AutoMig中的遷移速率控制方法將區(qū)別遷移需求和反饋控制思想相結(jié)合，根據(jù)前臺(tái)I/O負(fù)載變化，自適應(yīng)調(diào)整數(shù)據(jù)遷移速率，使得數(shù)據(jù)遷移動(dòng)作本身對(duì)于前臺(tái)I/O性能的影響非常小，同時(shí)使得數(shù)據(jù)遷移任務(wù)能夠盡快完成。
3 性能測(cè)試
本文將數(shù)據(jù)自動(dòng)遷移方法AutoMig應(yīng)用到分級(jí)存儲(chǔ)系統(tǒng)Tri-Right中，進(jìn)行了比較全面的性能測(cè)試。
3.1分級(jí)存儲(chǔ)系統(tǒng)原型
如圖2所示，Tri-Right采用帶外架構(gòu)，并在文件系統(tǒng)內(nèi)部實(shí)現(xiàn)，它由文件系統(tǒng)客戶端、元數(shù)據(jù)服務(wù)器和數(shù)據(jù)服務(wù)器組成，客戶端節(jié)點(diǎn)向用戶提供I/O訪問(wèn)接口，它接收用戶的文件訪問(wèn)請(qǐng)求；向元數(shù)據(jù)服務(wù)器讀寫(xiě)相關(guān)文件的元數(shù)據(jù)；向數(shù)據(jù)服務(wù)器讀寫(xiě)相關(guān)文件的內(nèi)容；并最終把結(jié)果返回給用戶。
圖2 Tri-Right的系統(tǒng)架構(gòu)
元數(shù)據(jù)服務(wù)器維護(hù)所有文件的相關(guān)信息，包括文件數(shù)據(jù)在多個(gè)數(shù)據(jù)服務(wù)器上的分布情況等；根據(jù)文件訪問(wèn)情況和設(shè)備分級(jí)信息，給出數(shù)據(jù)遷移的決策；根據(jù)數(shù)據(jù)服務(wù)器的負(fù)載情況進(jìn)行文件遷移的速率控制，數(shù)據(jù)服務(wù)器用來(lái)實(shí)際存儲(chǔ)分片后的文件數(shù)據(jù)，它處理來(lái)自客戶端的文件I/0請(qǐng)求；把自身負(fù)載情況返回給元數(shù)據(jù)服務(wù)器；并在元數(shù)據(jù)服務(wù)器的指示下執(zhí)行文件的遷移操作。
核心關(guān)注：拓步ERP系統(tǒng)平臺(tái)是覆蓋了眾多的業(yè)務(wù)領(lǐng)域、行業(yè)應(yīng)用，蘊(yùn)涵了豐富的ERP管理思想，集成了ERP軟件業(yè)務(wù)管理理念，功能涉及供應(yīng)鏈、成本、制造、CRM、HR等眾多業(yè)務(wù)領(lǐng)域的管理，全面涵蓋了企業(yè)關(guān)注ERP管理系統(tǒng)的核心領(lǐng)域，是眾多中小企業(yè)信息化建設(shè)首選的ERP管理軟件信賴品牌。
轉(zhuǎn)載請(qǐng)注明出處：拓步ERP資訊網(wǎng)http://www.oesoe.com/
本文標(biāo)題：分級(jí)存儲(chǔ)系統(tǒng)中一種數(shù)據(jù)自動(dòng)遷移方法(上)
本文網(wǎng)址：http://www.oesoe.com/html/support/1112156920.html
相關(guān)文章
