3.1　大數(shù)據(jù)存儲系統(tǒng)中的順序訪問模式

對于磁盤系統(tǒng)來說，順序訪問是能夠改善其性能的最有效的一種訪問模式。也正是因?yàn)檫@個(gè)原因，它在計(jì)算機(jī)各種存儲組件中得到了廣泛的挖掘和利用。通常來說，磁盤為了完成一個(gè)隨機(jī)的數(shù)據(jù)訪問需要以下幾個(gè)步驟：磁頭臂尋道、旋轉(zhuǎn)及數(shù)據(jù)傳輸。前兩者都屬于機(jī)械運(yùn)動，是為具體數(shù)據(jù)傳輸而進(jìn)行的磁頭定位。相對于真正的數(shù)據(jù)傳輸來說尋道以及旋轉(zhuǎn)需要耗費(fèi)大量的時(shí)間，它們往往幾十倍于數(shù)據(jù)的實(shí)際傳輸時(shí)間。而在某些工作負(fù)載中，這種差距甚至可能達(dá)到幾個(gè)數(shù)量級以上。換而言之，尋道以及旋轉(zhuǎn)時(shí)間在整個(gè)數(shù)據(jù)請求響應(yīng)時(shí)間中占據(jù)了很大的比例，而這個(gè)比例往往能達(dá)到90%以上。所以說，磁盤I/O性能的改善在很大程度上就是減少或者縮短磁盤的磁頭定位時(shí)間，而這正是順序訪問的優(yōu)點(diǎn)所在。當(dāng)一系列數(shù)據(jù)在磁盤上順序擺放，并且針對這些數(shù)據(jù)的訪問請求也是按照它們的物理地址順序排序，這種磁盤訪問模式可以稱之為順序訪問模式。順序訪問可以節(jié)省磁頭尋道和旋轉(zhuǎn)的時(shí)間，從而大大減少磁盤的訪問響應(yīng)時(shí)間，提高磁盤的效率及吞吐率。

順序訪問模式是如此重要，以至于大量的研究和技術(shù)都集中在這個(gè)方面，試圖改善或者挖掘隱含在工作負(fù)載中的順序訪問。具體來說，這些工作可以分為兩類：一類是增加磁盤上數(shù)據(jù)的順序性；另一類是挖掘隱含在工作負(fù)載中的順序訪問。前者主要指的是磁盤數(shù)據(jù)組織技術(shù)[48] [51]，它們通過不同的算法動態(tài)或者靜態(tài)的組織磁盤數(shù)據(jù)，從而將盡量多的數(shù)據(jù)塊按照訪問順序進(jìn)行放置。在這個(gè)過程中可能會需要獲取文件[133]或者數(shù)據(jù)塊[134]之間的訪問關(guān)系來作為數(shù)據(jù)重組織的依據(jù)。后者則主要用于發(fā)掘已經(jīng)蘊(yùn)含在數(shù)據(jù)訪問流中的順序訪問。在實(shí)際的工作負(fù)載中，順序訪問流與隨機(jī)訪問流是相互夾雜在一起的，因此，對于底層的磁盤驅(qū)動來說看到的是一個(gè)隨機(jī)的不連續(xù)的訪問流。而要從這種訪問流中獲取其中的順序訪問就需要諸如緩存、順序預(yù)取及磁盤調(diào)度等技術(shù)的支持。

無論是增加磁盤上數(shù)據(jù)的順序性還是從復(fù)雜訪問流中挖掘順序訪問，精確預(yù)測順序訪問流長度信息是有效利用順序訪問模式的關(guān)鍵因素之一。如果能夠獲取一個(gè)順序訪問流的剩余長度，存儲系統(tǒng)就可以利用這些信息來提高各種存儲技術(shù)的有效性從而進(jìn)一步提高系統(tǒng)的性能。舉例來說，如果一個(gè)順序預(yù)取算法能夠獲取順序訪問流的長度信息，它就可以優(yōu)化預(yù)取請求的大小，從而在開發(fā)磁盤順序性和有效利用緩存空間之間取得完美的平衡。

然而，順序訪問流的長度信息很難得到準(zhǔn)確的評估。其中一個(gè)主要的原因就在于文件系統(tǒng)與存儲設(shè)備之間簡單的接口。通常來說，一個(gè)存儲設(shè)備只能從文件系統(tǒng)中接收讀和寫等簡單操作，卻很難獲取諸如文件長度以及用戶訪問等方面的信息。這就導(dǎo)致底層設(shè)備無法了解關(guān)于順序訪問流長度的任何消息。為了解決這個(gè)問題，存儲系統(tǒng)需要一種對上層透明的技術(shù)或者方法來預(yù)測順序訪問流的長度，而且這種方法能夠僅基于底層塊訪問來完成預(yù)測。

在此之前，很多研究[51] [54] [55]都意識到一個(gè)給定順序訪問流的剩余訪問與這個(gè)訪問流的當(dāng)前訪問長度具有密切的關(guān)系。具體來說，一個(gè)順序訪問流已經(jīng)被訪問的數(shù)據(jù)越長，那么它接下來的順序數(shù)據(jù)就越可能被訪問[50]。在本章中，這種訪問趨勢被定義為增長的順序流訪問定律（Growing Sequential stream Access，GSA）。當(dāng)前用來挖掘這種GSA定律的方法可以籠統(tǒng)地分為兩類：一類是基于經(jīng)驗(yàn)的定性分析方法。這類方法的典型技術(shù)就是順序預(yù)取，像Linux等操作系統(tǒng)中的默認(rèn)順序預(yù)取算法，它會隨著某個(gè)順序訪問流預(yù)取數(shù)據(jù)的不斷增加而逐步擴(kuò)大預(yù)取請求的大小[135]。而另一類方法則采用了一種定量的方法，它們利用一個(gè)數(shù)學(xué)函數(shù)[51][54]來模擬近似某類工作負(fù)載中順序訪問流長度的分布。舉例來說，文獻(xiàn)[54]通過對數(shù)據(jù)庫工作負(fù)載的研究而得出它們的順序訪問流長度的分布近似于指數(shù)正態(tài)分布。雖然以前的研究工作提供了各種不同的挖掘GSA的方法，然而它們卻很難精確地評估順序流長度。造成這種境況的原因是多方面的，首先，順序訪問流的長度分布是非常復(fù)雜的，簡單而且確定的數(shù)學(xué)函數(shù)很難有效地模擬。其次，不同類型大數(shù)據(jù)處理的工作負(fù)載中其順序流長度分布是不同的，針對某種具體工作負(fù)載設(shè)定并優(yōu)化參數(shù)的數(shù)學(xué)函數(shù)很難適應(yīng)不同負(fù)載之間的差異性。最后，即便是針對同一類的工作負(fù)載，它們的順序流長度分布往往也是不規(guī)則的。研究證明，即便是同一種應(yīng)用在不同的時(shí)間段也會有完全不同的訪問特征，這一點(diǎn)在數(shù)據(jù)庫工作負(fù)載[54]以及OLTP工作負(fù)載[51]中得到了很好的驗(yàn)證。這種不規(guī)則性很難用數(shù)學(xué)表達(dá)式來模擬。

從上述內(nèi)容可以看出，無論是定性分析的方法還是基于數(shù)學(xué)函數(shù)的方法都很難準(zhǔn)確、全面地評估長度信息。上述的評估方法也許對隨機(jī)訪問主導(dǎo)的系統(tǒng)性能影響不大，但對于那些順序訪問流密集的系統(tǒng)可能帶來嚴(yán)重的性能影響。

3.1.1　順序訪問流長度信息的使用

順序訪問流長度信息是順序訪問模式能夠得到有效利用的重要基礎(chǔ)。實(shí)際上在存儲系統(tǒng)中有很多提高系統(tǒng)讀寫性能的技術(shù)都是基于順序訪問的，這些技術(shù)如果能夠得到順序流長度信息的支持將會變得更加高效而簡單。

1．順序預(yù)取技術(shù)

順序預(yù)取技術(shù)是底層存儲設(shè)備中使用非常廣泛的一種預(yù)取技術(shù)，它是一種塊級別的預(yù)取，能夠通過將多個(gè)數(shù)據(jù)塊包含在一個(gè)預(yù)取請求中來有效地利用順序訪問模式。而順序預(yù)取的預(yù)取度也就是每個(gè)請求中的預(yù)取數(shù)據(jù)塊數(shù)量在很大程度上決定了預(yù)取本身的效率，它的優(yōu)化需要順序訪問流長度信息的支持。如果缺乏訪問流的長度信息，順序預(yù)取就可能因?yàn)轭A(yù)取命中率的降低而浪費(fèi)寶貴的磁盤帶寬以及緩存資源，從而使得存儲系統(tǒng)性能得不到有效的改善甚至性能惡化。

順序訪問流長度信息的重要性在很多基于順序預(yù)取的研究中得到過驗(yàn)證。舉例來說，STEP預(yù)取策略[51]是一種比較典型的順序預(yù)取算法，它設(shè)定了一個(gè)成本收益（Cost-Benefit）模型來試圖實(shí)現(xiàn)預(yù)取度的最優(yōu)化。在這個(gè)模型中預(yù)取的成本是傳輸預(yù)取數(shù)據(jù)花費(fèi)的額外時(shí)間，而收益則來源于因?yàn)轭A(yù)取數(shù)據(jù)命中而節(jié)省的尋道以及旋轉(zhuǎn)時(shí)間。因此，在這個(gè)模型中順序訪問流的長度就變得非常重要了，了解長度信息就可以確定預(yù)取數(shù)據(jù)是否會命中。如果命中概率高，那么，預(yù)取算法的收益相應(yīng)也會較高，反之如果沒有命中，預(yù)取算法就沒有收益，只剩下額外成本了。這無助于存儲系統(tǒng)性能的提高，反而可能增加請求的響應(yīng)時(shí)間。STEP一文通過對OLTP類工作負(fù)載的離線統(tǒng)計(jì)得出了其中順序訪問流長度的分布圖，并在模型中利用一個(gè)指數(shù)函數(shù)來近似模擬基于順序訪問的工作負(fù)載，利用線性函數(shù)來近似模擬基于隨機(jī)訪問的工作負(fù)載。這種近似的模擬雖然缺乏靈活的適應(yīng)性以及準(zhǔn)確性，但STEP一文的實(shí)驗(yàn)表明，即使通過這種粗糙的、原始的長度信息獲取方法，順序預(yù)取的有效性也得到了很大的提高。另外，也有一些基于其他不同工作負(fù)載的預(yù)取技術(shù)意識到了順序訪問流長度信息的重要性。Hsu[54]等提出如果一個(gè)順序流的訪問長度超過了16pages，那么預(yù)取算法應(yīng)該在緩存中預(yù)取（但未訪問）數(shù)據(jù)還有剩余的時(shí)候（4pages），就加大接下來的預(yù)取數(shù)據(jù)（從1page增加到8pages）。而實(shí)驗(yàn)結(jié)果也表明，這種簡單的改進(jìn)可以有效減少90%的緩存缺頁（Cache Miss）。

2．存儲緩存技術(shù)

隨著存儲技術(shù)的發(fā)展，越來越多的緩存技術(shù)注意到了順序訪問數(shù)據(jù)與隨機(jī)訪問數(shù)據(jù)的不同，并針對順序流數(shù)據(jù)的特點(diǎn)對現(xiàn)行緩存管理技術(shù)進(jìn)行改進(jìn)[100][136]。具體來說，順序訪問數(shù)據(jù)與隨機(jī)訪問數(shù)據(jù)在緩存中的重要性是不同的，因?yàn)樽x取后者相較于讀取前者來說需要更高的時(shí)間成本。而且順序訪問數(shù)據(jù)往往只被訪問一次。因此，如果緩存管理算法不加區(qū)分地對待隨機(jī)數(shù)據(jù)和順序數(shù)據(jù)，就可能導(dǎo)致大量有價(jià)值的隨機(jī)數(shù)據(jù)被過早替換出內(nèi)存[46][47]，從而增加整個(gè)磁盤訪問流中隨機(jī)訪問的比例。這對于磁盤性能的提高造成很大的障礙。

在上述對緩存技術(shù)的介紹中，值得注意的一點(diǎn)是：如果能夠獲取順序訪問流的長度信息，緩存技術(shù)的有效性完全可以得到進(jìn)一步加強(qiáng)。例如，更加高效地為預(yù)取數(shù)據(jù)與緩存數(shù)據(jù)劃分緩存空間、更加高效地管理預(yù)取數(shù)據(jù)，等等。

3．磁盤請求調(diào)度技術(shù)

磁盤驅(qū)動通過調(diào)度I/O請求來挖掘隱含在數(shù)據(jù)訪問流中的空間局部性（尤其是順序性）。通過對磁盤請求順序的重組織，磁盤請求調(diào)度技術(shù)可以有效地減少磁頭的尋道次數(shù)以及平均尋道時(shí)間。在整個(gè)過程中，最理想的情況就是將具有順序性的請求集中到一起從而可以形成順序訪問流。因此，順序訪問流的長度信息，對于磁盤調(diào)度也是非常重要的。基于長度信息，磁盤調(diào)度算法可以預(yù)測一個(gè)順序流是否結(jié)束，從而可以進(jìn)一步判斷出當(dāng)前磁盤請求的下一個(gè)連續(xù)請求是否會到達(dá)。可以說，長度信息能夠很大程度上成為調(diào)度算法有效管理請求的依據(jù)。

舉例來說明順序訪問流長度信息對于磁盤請求調(diào)度的重要性。Anticipatory Scheduling[137]是Linux操作系統(tǒng)內(nèi)核中接受的磁盤調(diào)度算法，其主要目標(biāo)是解決磁盤訪問中的假空閑（Deceptive Idleness）問題。假空閑指的是進(jìn)程發(fā)出同步磁盤請求，它會在上一個(gè)請求結(jié)束之后的很短時(shí)間內(nèi)再發(fā)出下一個(gè)請求。如此一來，該進(jìn)程在任何時(shí)候最多只能保持一個(gè)請求。這會讓磁盤調(diào)度器過早地做出調(diào)度決定，因?yàn)檎{(diào)度算法會假定進(jìn)程在發(fā)出上一個(gè)請求之后的一段時(shí)間內(nèi)不會有下一個(gè)請求發(fā)出，并因此選擇一個(gè)其他進(jìn)程的請求交給磁盤服務(wù)。這會造成磁頭定位操作的增加。而Anticipatory Scheduling算法會在該進(jìn)程一個(gè)請求完成之后等待一段時(shí)間，以期待它下一個(gè)請求的到來。如果此算法能夠了解順序訪問流長度，也就可以更加準(zhǔn)確地預(yù)測下一個(gè)請求是否會到來，從而決定是否等待。這更有利于提高磁盤的利用率。除此之外，還有其他一些磁盤調(diào)度算法諸如SSTF（Shortest Seek Time First，SSTF）、FSCAN（Frequently Scanning，F(xiàn)SCAN）、CSCAN，等等。這些都是最基本方法，它們的一個(gè)共同思想就是盡量挖掘隱藏在訪問流中的順序性。

3.1.2　不斷增加的順序訪問

隨著大數(shù)據(jù)應(yīng)用和挖掘的不斷普及，順序訪問模式在存儲系統(tǒng)中變得越來越重要，這是由兩方面因素綜合影響的結(jié)果，一方面是大數(shù)據(jù)對于性能的需求越來越高，而上述各種性能改進(jìn)技術(shù)對于順序訪問模式具有很強(qiáng)的依賴性；另一方面大數(shù)據(jù)處理往往需要批量、重復(fù)地訪問數(shù)據(jù)，因此，順序訪問流本身占據(jù)存儲系統(tǒng)請求的比例日益增加。更具體來說，首先是大數(shù)據(jù)應(yīng)用對于數(shù)據(jù)的需求量越來越大、對數(shù)據(jù)處理也越來越復(fù)雜。這就導(dǎo)致應(yīng)用過程中涉及的文件越來越多，而文件本身也變得越來越大[3]，無形中會增加順序訪問的比例以及順序訪問的平均長度。其次是各種大數(shù)據(jù)布局（分割）技術(shù)在存儲設(shè)備中的廣泛應(yīng)用，如果說前者由于不同類型的應(yīng)用其發(fā)展方向不同，可能使得順序訪問增加這一事實(shí)缺乏明顯、確定的證據(jù)，那么數(shù)據(jù)布局技術(shù)從其一出現(xiàn)就是為改善磁盤的空間局部性（尤其是順序性）而設(shè)計(jì)的。

大多數(shù)據(jù)布局技術(shù)是針對磁盤類設(shè)備的訪問特點(diǎn)以及分布式數(shù)據(jù)處理而設(shè)計(jì)的。根據(jù)布局技術(shù)的適應(yīng)性不同可以分為兩類：靜態(tài)數(shù)據(jù)布局[138][139]及動態(tài)數(shù)據(jù)布局[115][134][141][142]。前者的主要目標(biāo)在于從數(shù)據(jù)布局的角度來維護(hù)文件系統(tǒng)的目錄結(jié)構(gòu)，同時(shí)優(yōu)化單個(gè)文件中的順序訪問[140]。這樣的布局算法往往在數(shù)據(jù)產(chǎn)生的時(shí)候就決定了數(shù)據(jù)的物理位置，在此后的應(yīng)用過程中極少進(jìn)行修改；而后者根據(jù)負(fù)載的訪問情況，將那些相互之間存在訪問關(guān)系的數(shù)據(jù)進(jìn)行重新排列，從而使得這些數(shù)據(jù)在設(shè)備上的物理地址是接近的甚至是連續(xù)的。經(jīng)過數(shù)據(jù)的動態(tài)布局以及組織，可以使得存儲系統(tǒng)適應(yīng)盡可能多種類的應(yīng)用，而且可以使得訪問流變得更加具有順序性，這會大大提高存儲設(shè)備的讀寫性能。

在動態(tài)數(shù)據(jù)布局技術(shù)中，根據(jù)布局及其重組織的數(shù)據(jù)粒度不同，它們大體可以分為三個(gè)級別：卷級別數(shù)據(jù)布局、文件級別數(shù)據(jù)布局、塊級別數(shù)據(jù)布局。卷級別數(shù)據(jù)布局顧名思義就是以卷作為數(shù)據(jù)重組織的原子單元。舉例來說，Arnan等[142]提出的動態(tài)數(shù)據(jù)重組織算法，通過對并行磁盤系統(tǒng)中的數(shù)據(jù)卷的管理完成了對可能造成訪問中相互打擾的數(shù)據(jù)卷的分離，從而最大可能地保證了磁盤訪問的局部性。此算法通過獨(dú)立訪問模型（Independent Reference Model，IRM）評估在一段時(shí)間內(nèi)不同卷上的訪問情況，如果這些卷上的訪問相互打擾，就很可能造成磁頭在這些卷之間來回尋道從而增加平均的尋道時(shí)間，降低磁盤的性能。因此，算法將這樣的卷分離出來，并重布局到不同的磁盤上，如此一來在任何一段時(shí)間內(nèi)同一個(gè)磁盤上的不同卷上的訪問很少會相互打擾。這樣也就保證了任何一段時(shí)間內(nèi)數(shù)據(jù)訪問的局部性，提高了磁盤的性能，也增加了順序訪問的數(shù)量。文件級別的數(shù)據(jù)布局是介于卷布局以及塊布局之間的一種數(shù)據(jù)重布局技術(shù)。較早的基于文件級別的方法是由Staelin等[143]提出來的，它們偵測文件的訪問并將那些經(jīng)常被訪問的文件放到磁盤的中央，以期減少磁盤的平均尋道。LFS[144]文件系統(tǒng)通過將大量小的寫數(shù)據(jù)整合到一起并以一種順序的方式批量寫到磁盤的結(jié)尾日志區(qū)來實(shí)現(xiàn)寫操作的順序性。也有大量研究集中在開發(fā)面向特定數(shù)據(jù)及應(yīng)用的文件布局機(jī)制[143][145][146][147]。塊級別數(shù)據(jù)布局技術(shù)是一種廣泛應(yīng)用于存儲系統(tǒng)底層的數(shù)據(jù)布局技術(shù)，它也是效率最高的布局方法。由于這些布局技術(shù)以數(shù)據(jù)塊作為最基本的數(shù)據(jù)重組織單元，因此，無論是存在于文件之間、文件之內(nèi)還是部分文件中的順序性都可以得到有效的利用，而且不會造成額外的帶寬浪費(fèi)。另外，塊級別的數(shù)據(jù)布局與文件系統(tǒng)無關(guān)也無須上層提供信息，因此，更加適用于存儲系統(tǒng)底層。比較典型的塊級別數(shù)據(jù)重布局包括C-Miner[53]以及BORG[149]等算法。前者利用一種高級的數(shù)據(jù)挖掘技術(shù)來挖掘多個(gè)數(shù)據(jù)塊之間的關(guān)系，并根據(jù)這些關(guān)系來重新組織數(shù)據(jù)塊。而后者著重于對數(shù)據(jù)重組織算法的實(shí)現(xiàn)，并且設(shè)計(jì)了一種較為通用的解決方案。

通過上文的敘述可以看到，無論基于怎樣的具體技術(shù)數(shù)據(jù)布局，最終目的就是不斷增加訪問流中的順序訪問比例。因此，研究高效、準(zhǔn)確的技術(shù)方法來挖掘順序訪問流的長度信息是一項(xiàng)非常重要的研究課題。