孟 子 瀟

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室 上海 200433)

0 引 言

在大數(shù)據(jù)時(shí)代，對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)及處理所需要的資源往往會(huì)遠(yuǎn)遠(yuǎn)超出單臺(tái)機(jī)器的存儲(chǔ)容量和處理能力，因而采用分布式平臺(tái)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)和處理成為人們不二的選擇。分布式環(huán)境中數(shù)據(jù)會(huì)被分散到多臺(tái)機(jī)器存儲(chǔ)，對(duì)數(shù)據(jù)的處理也會(huì)由多臺(tái)機(jī)器并發(fā)地進(jìn)行，但是出于對(duì)數(shù)據(jù)存儲(chǔ)持久性以及經(jīng)濟(jì)性的考慮，通常將數(shù)據(jù)存儲(chǔ)分散到不同機(jī)器的磁盤中，并在對(duì)數(shù)據(jù)進(jìn)行處理的時(shí)候從磁盤中讀取數(shù)據(jù)，這樣就導(dǎo)致了數(shù)據(jù)讀取與處理之間的性能鴻溝。隨著內(nèi)存技術(shù)的發(fā)展，購(gòu)置單位內(nèi)存資源所需要花費(fèi)的成本大幅降低，機(jī)器所配置的內(nèi)存容量也隨之大幅提升，人們也逐步通過對(duì)數(shù)據(jù)進(jìn)行緩存的方式來提高對(duì)大數(shù)據(jù)集的處理效率，因而人們逐漸開展了針對(duì)大數(shù)據(jù)集在分布式環(huán)境中的緩存問題的研究。

然而，人們往往需要同時(shí)對(duì)多個(gè)數(shù)據(jù)集進(jìn)行處理才能完成某一項(xiàng)任務(wù)，也就是說數(shù)據(jù)集與數(shù)據(jù)集之間是存在關(guān)聯(lián)性的。但是現(xiàn)有的緩存框架及算法都較少地考慮數(shù)據(jù)集之間關(guān)聯(lián)性，而是把每個(gè)數(shù)據(jù)集當(dāng)作獨(dú)立的緩存單元進(jìn)行考慮，這樣就會(huì)導(dǎo)致多個(gè)相互關(guān)聯(lián)的數(shù)據(jù)集只有一部分被緩存，使對(duì)多個(gè)關(guān)聯(lián)數(shù)據(jù)集進(jìn)行處理的一個(gè)計(jì)算任務(wù)在處理數(shù)據(jù)的時(shí)候仍然需要從磁盤讀取沒有被緩存的數(shù)據(jù)集，從而引起數(shù)據(jù)緩存效果的下降，導(dǎo)致數(shù)據(jù)讀取與處理之間的性能鴻溝依然存在，使得對(duì)數(shù)據(jù)進(jìn)行緩存的意義大大降低。因此，分布式環(huán)境對(duì)數(shù)據(jù)進(jìn)行緩存的時(shí)候需要把數(shù)據(jù)的關(guān)聯(lián)性考慮在內(nèi)，而不能只把每個(gè)數(shù)據(jù)集作為單獨(dú)的緩存對(duì)象進(jìn)行考慮。

文獻(xiàn)[1-2]使用類似HDFS[3]的管理方式來管理緩存，在底層分布式文件系統(tǒng)的基礎(chǔ)上，實(shí)現(xiàn)了一個(gè)額外的緩存層。文獻(xiàn)[4]進(jìn)一步實(shí)現(xiàn)了一個(gè)基于內(nèi)存的分布式文件系統(tǒng)，在HDFS和上層應(yīng)用間增加一層文件緩存機(jī)制，同時(shí)為了保證數(shù)據(jù)一致性和可用性，引入Lineage和Checkpoint機(jī)制，是一個(gè)專門為大規(guī)模數(shù)據(jù)處理而設(shè)計(jì)的系統(tǒng)。文獻(xiàn)[5]提出了一種動(dòng)態(tài)放置數(shù)據(jù)文件的策略，可以在HDFS實(shí)現(xiàn)聯(lián)合定位。文獻(xiàn)[6]提出可以將所有數(shù)據(jù)放在內(nèi)存中提供服務(wù)，以獲得更優(yōu)的效率。在文獻(xiàn)[7]發(fā)現(xiàn)了并行計(jì)算All-or-Nothing的特性，即在進(jìn)行并行計(jì)算時(shí)，部分緩存對(duì)計(jì)算效率沒有幫助，要么都進(jìn)行緩存，要么都不進(jìn)行緩存，為本文提供了重要思路。文獻(xiàn)[8-11]是針對(duì)基本緩存策略LRU、LFU、FIFO等的分析和一些改進(jìn)優(yōu)化。

本文提出一種基于文件關(guān)聯(lián)性的協(xié)同緩存策略，稱為CoCache。主要工作包含：1) 提出數(shù)據(jù)集關(guān)聯(lián)性的量化計(jì)算方式；2) 根據(jù)數(shù)據(jù)集關(guān)聯(lián)性的元信息，提出了協(xié)同緩存策略；3) 實(shí)現(xiàn)CoCache的原型，并在其上進(jìn)行實(shí)驗(yàn)驗(yàn)證方案的有效性。

1 系統(tǒng)框架與算法設(shè)計(jì)

在同時(shí)處理有關(guān)聯(lián)的兩個(gè)數(shù)據(jù)集時(shí)，首先需要考慮關(guān)聯(lián)性的定義，然后基于數(shù)據(jù)集之間的關(guān)聯(lián)性，CoCache實(shí)現(xiàn)了一種協(xié)同緩存方案，即在緩存數(shù)據(jù)集的時(shí)候，不單是考慮該數(shù)據(jù)集本身的元信息，而是結(jié)合和它相關(guān)的其他數(shù)據(jù)集。

本節(jié)將首先介紹CoCache的總體框架設(shè)計(jì)，然后提出關(guān)聯(lián)性的定義方法和在緩存替換過程中的具體算法。

1.1 系統(tǒng)框架設(shè)計(jì)

CoCache是一個(gè)塊式存儲(chǔ)系統(tǒng)，整體框架如圖1所示，虛線框內(nèi)是核心部分，系統(tǒng)由一個(gè)中心的Master節(jié)點(diǎn)和多個(gè)位于存儲(chǔ)節(jié)點(diǎn)上的Worker節(jié)點(diǎn)以及底層文件系統(tǒng)(UFS)組成，其他部分由用戶管理。Master節(jié)點(diǎn)負(fù)責(zé)進(jìn)行緩存控制，根據(jù)預(yù)處理模塊提供的分塊和索引的基本信息，將元數(shù)據(jù)信息存儲(chǔ)到自己的工作內(nèi)存中，并且在計(jì)算過程中，根據(jù)任務(wù)管理器提供的查詢需求，進(jìn)行緩存調(diào)度控制；Worker節(jié)點(diǎn)負(fù)責(zé)將數(shù)據(jù)塊返回給用戶以及從底層文件系統(tǒng)讀取數(shù)據(jù)，并且由Master節(jié)點(diǎn)調(diào)度，進(jìn)行緩存控制；底層文件系統(tǒng)負(fù)責(zé)存儲(chǔ)數(shù)據(jù)集。

圖1 系統(tǒng)架構(gòu)圖

整個(gè)工作流程分為以下幾個(gè)部分：1) 底層文件系統(tǒng)獲取到數(shù)據(jù)集，并且由預(yù)處理模塊進(jìn)行分塊，建立索引，并將預(yù)處理結(jié)果通知Master節(jié)點(diǎn)。2) 任務(wù)管理器發(fā)起查詢，Master節(jié)點(diǎn)接收到查詢請(qǐng)求，在索引中查找對(duì)應(yīng)的數(shù)據(jù)塊，并向Worker節(jié)點(diǎn)請(qǐng)求該數(shù)據(jù)塊，與此同時(shí)，告知Worker節(jié)點(diǎn)緩存調(diào)度信息。3) Worker節(jié)點(diǎn)接收到Master節(jié)點(diǎn)的元信息后，將嘗試從緩存中讀數(shù)據(jù)塊，如果讀到，則將數(shù)據(jù)塊返回任務(wù)管理器；如果緩存中不存在該數(shù)據(jù)塊，則從底層文件系統(tǒng)中讀取并返回給任務(wù)管理器，同時(shí)根據(jù)緩存調(diào)度信息，決定緩存內(nèi)容和方式，該部分會(huì)在1.3節(jié)中詳細(xì)描述。4) 任務(wù)管理器接受到數(shù)據(jù)塊后，計(jì)算出結(jié)果。當(dāng)再次執(zhí)行查詢?nèi)蝿?wù)時(shí)，重復(fù)以上2至4步驟。

1.2 數(shù)據(jù)集的關(guān)聯(lián)性

CoCache的第一步，就是要定義數(shù)據(jù)集之間的關(guān)聯(lián)性。在這里，本文先考慮兩個(gè)數(shù)據(jù)集之間的關(guān)聯(lián)性。表1列出了在此過程中用到的參數(shù)及其定義。

表1 參數(shù)定義

數(shù)據(jù)集Da和Db都是數(shù)據(jù)庫表，它們?cè)谀骋涣猩嫌邢嗤膶傩許ab，關(guān)聯(lián)性針對(duì)Sab定義。將Da和Db按照Sab排序后，把Da和Db按照每塊大小M分成多塊，分別是A1，A2，…，Am和B1，B2，…，Bn，對(duì)每一塊，可以得到該塊在S屬性上的范圍AiS(xai,yai)和BjS(xbj,ybj)。對(duì)此，數(shù)據(jù)集A第i塊和數(shù)據(jù)集B的第j塊的關(guān)聯(lián)系數(shù)通過如下方式計(jì)算：

1) 當(dāng)[xai,yai]∩[xbj,ybj]=?時(shí)，F(xiàn)(Ai,Bj)=0。

2) 當(dāng)[xai,yai]∩[xbj,ybj]≠?時(shí)，令[xai,yai]∩[xbj,ybj]=[x,y]，可計(jì)算出Mai(x,y)和Mbj(x,y)，則：

根據(jù)上述定義，由于數(shù)據(jù)集A和數(shù)據(jù)集B都要進(jìn)行排序，有如下優(yōu)化方式來計(jì)算出各塊之間的關(guān)聯(lián)系數(shù)。

從頭開始，對(duì)數(shù)據(jù)集A和B同時(shí)掃描，Sab字段較小的指針往下掃描，直到一個(gè)塊結(jié)束?？梢杂?jì)算出當(dāng)前對(duì)應(yīng)塊之間的關(guān)聯(lián)系數(shù)，然后標(biāo)記當(dāng)前位置，作為下一個(gè)迭代的起始位置，繼續(xù)掃描，直到文件結(jié)束。未計(jì)算的塊之間的關(guān)聯(lián)系數(shù)均為0。通過這種方式可以不必計(jì)算所有塊，使得尋找關(guān)聯(lián)系數(shù)的復(fù)雜度從O(n2)變?yōu)镺(n)。

1.3 協(xié)同緩存策略

協(xié)同緩存策略是基于數(shù)據(jù)集關(guān)聯(lián)性的緩存策略，是在基于已有的緩存策略上，對(duì)部分有關(guān)聯(lián)性的塊進(jìn)行綁定緩存，因此在協(xié)同緩存之上有一個(gè)基本的緩存策略，如LRU、FIFO等。

查詢?nèi)蝿?wù)的執(zhí)行過程和緩存替換策略如圖2所示。任務(wù)管理器發(fā)起讀請(qǐng)求，Master節(jié)點(diǎn)根據(jù)索引，找到要讀取的塊集合I，然后查看其是否全部在緩存中，如果是，直接從緩存中讀取并返回；如果不是，則從底層文件系統(tǒng)中查找I以及與其相關(guān)的塊集合P，將其存在緩存中并返回。在此，本文定義一個(gè)List，用于保存即將被替換的塊的元信息。當(dāng)涉及到緩存替換時(shí)，首先檢查L(zhǎng)ist里的塊數(shù)量是否充足，如果不足，則通過總體緩存策略選出第一個(gè)被替換的塊，然后將該塊及與其相關(guān)的塊，也加入List中，再次檢查L(zhǎng)ist的塊數(shù)量，直到滿足替換要求。

2 實(shí)驗(yàn)分析

本文基于Tachyon實(shí)現(xiàn)CoCache的原型，使用HDFS作為底層文件系統(tǒng)。Master節(jié)點(diǎn)和Worker節(jié)點(diǎn)均是Amazon EC2 m4.2xlarge型號(hào)機(jī)器，其中一臺(tái)Master節(jié)點(diǎn)，四臺(tái)Worker節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的配置為32 GB內(nèi)存，其中工作內(nèi)存占用12 GB，剩下20 GB作為緩存資源；總共分配80 GB作為緩存數(shù)據(jù)的資源。

圖2 協(xié)同緩存流程圖

實(shí)驗(yàn)主要通過執(zhí)行多次查詢操作，來對(duì)比使用和不使用CoCache時(shí)，查詢操作的總時(shí)間，緩存命中率。

每次測(cè)試的查詢操作混合了若干個(gè)單表查詢和多表join查詢。在實(shí)驗(yàn)中對(duì)比了不同參數(shù)對(duì)結(jié)果的影響，包括數(shù)據(jù)集大小，關(guān)聯(lián)性閾值T，塊大小M。

2.1 數(shù)據(jù)集預(yù)處理

由于CoCache是對(duì)有關(guān)聯(lián)性的數(shù)據(jù)集進(jìn)行處理，所以使用的兩個(gè)數(shù)據(jù)集為形式，且它們的key為同一字段。按照如下方式進(jìn)行預(yù)處理。1) 將數(shù)據(jù)集按照key進(jìn)行排序；2) 將數(shù)據(jù)集按照數(shù)據(jù)塊大小分成若干塊，并取出該數(shù)據(jù)塊的第一個(gè)key作為標(biāo)識(shí)，為數(shù)據(jù)塊建立索引；3) 根據(jù)數(shù)據(jù)塊key的范圍，計(jì)算出關(guān)聯(lián)系數(shù)F(Ai，Bj)，顯然關(guān)聯(lián)系數(shù)F矩陣是一個(gè)稀疏矩陣，所以采用鄰接表的形式存儲(chǔ)；4) 把排好序的兩個(gè)數(shù)據(jù)集存入底層文件系統(tǒng)，同時(shí)把數(shù)據(jù)塊的索引信息和關(guān)聯(lián)系數(shù)鄰接表存入Master節(jié)點(diǎn)。

本實(shí)驗(yàn)所采用的數(shù)據(jù)集為日志信息，以時(shí)間為key，日志內(nèi)容為value，且已排序。使用索引能夠快速地定位到查詢所需要的數(shù)據(jù)塊，避免過多的磁盤掃描。通過關(guān)聯(lián)系數(shù)鄰接表，可以在進(jìn)行緩存的過程中，快速準(zhǔn)確地找出與目標(biāo)塊相關(guān)聯(lián)的塊。為了更好地對(duì)比緩存對(duì)實(shí)驗(yàn)結(jié)果的影響，實(shí)驗(yàn)預(yù)先把數(shù)據(jù)集前部分?jǐn)?shù)據(jù)存入緩存中。

2.2 總體運(yùn)行時(shí)間和緩存命中率的對(duì)比

實(shí)驗(yàn)分別設(shè)置了幾組不同大小的數(shù)據(jù)集(數(shù)據(jù)集A和B大小相同)，將閾值T設(shè)置為0.5，塊大小設(shè)置為128 MB，然后比較了使用Tachyon和使用CoCache時(shí)的總體運(yùn)行時(shí)間和緩存命中率，得到的結(jié)果如圖3和圖4?？梢园l(fā)現(xiàn)當(dāng)數(shù)據(jù)集大小小于緩存資源大小時(shí)，兩者并無區(qū)別，但是一旦超過這個(gè)數(shù)值，CoCache在運(yùn)行時(shí)間和緩存命中率上的表現(xiàn)都優(yōu)于Tachyon。因?yàn)镃oCache能夠減少出現(xiàn)有關(guān)聯(lián)的塊一部分在緩存，一部分不在緩存的現(xiàn)象，使得下一次查詢更大幾率全部命中。

閾值和塊大小的設(shè)置對(duì)整個(gè)查詢也是有影響的，所以接下來將通過設(shè)置不同參數(shù)，來對(duì)比CoCache和Tachyon的性能。

圖3 數(shù)據(jù)集大小對(duì)運(yùn)行時(shí)間的影響

圖4 數(shù)據(jù)集大小對(duì)緩存命中率的影響

2.3 閾值T對(duì)運(yùn)行時(shí)間和緩存命中率的影響

為了比較不同閾值下CoCache的性能，實(shí)驗(yàn)從0.05到1設(shè)置7組不同的閾值(0.05、0.1、0.2、0.4、0.6、0.8、1)，通過分析可以知道，當(dāng)閾值為1時(shí)，幾乎沒有兩個(gè)塊是具有關(guān)聯(lián)性的，因此CoCache等同于Tachyon。在此使用兩個(gè)100 GB的數(shù)據(jù)集，設(shè)置塊大小為128 MB，在此環(huán)境下，對(duì)比了不同閾值的運(yùn)行時(shí)間和緩存命中率，實(shí)驗(yàn)結(jié)果如圖5。可以發(fā)現(xiàn)，隨著閾值增加，緩存命中率越來越小，這說明了CoCache能夠進(jìn)行有效的緩存，使得更多的塊命中。但是，運(yùn)行時(shí)間并不是如此樂觀，當(dāng)閾值很小的時(shí)候，過多的塊具有關(guān)聯(lián)性，使得每次在替換塊時(shí)，同時(shí)有很多塊需要并行處理，造成了一定的IO阻塞，增加了運(yùn)行時(shí)間。

圖5 閾值T的影響

2.4 塊大小的影響

在這一部分，實(shí)驗(yàn)將對(duì)比不同塊大小對(duì)CoCache和Tachyon性能的影響。由上一部分可以看出，當(dāng)閾值為0.2左右時(shí)，能夠在運(yùn)行時(shí)間上取得比較好的效果，所以在這一部分中，閾值設(shè)置為0.2，兩個(gè)數(shù)據(jù)集大小也為100 GB，實(shí)驗(yàn)結(jié)果如圖6所示?？梢园l(fā)現(xiàn)，不管采用何種大小的塊，CoCache的運(yùn)行時(shí)間都優(yōu)于Tachyon。同時(shí)還發(fā)現(xiàn)，當(dāng)每塊越小時(shí)，運(yùn)行時(shí)間越快，因?yàn)槊看尾樵儠r(shí)，索引能夠更準(zhǔn)確地找到相應(yīng)的塊，以及與此同時(shí)被緩存的“無用信息”會(huì)變少。但是這一部分還是受到上層查詢的范圍的影響，如果每次查詢覆蓋的范圍是抖動(dòng)的，會(huì)導(dǎo)致查詢讀取的塊個(gè)數(shù)也是抖動(dòng)的，塊大小的影響就會(huì)逐漸消失。

圖6 塊大小的影響

3 結(jié) 語

隨著大數(shù)據(jù)查詢應(yīng)用的增加，利用分布式緩存來對(duì)運(yùn)算進(jìn)行加速已成為共識(shí)，而多數(shù)據(jù)集的查詢?nèi)蝿?wù)越來越多，為了更好地利用緩存資源，本文提出的基于文件關(guān)聯(lián)性的協(xié)同緩存策略，已經(jīng)開始解決這一部分問題，并且取得了一定的成果。對(duì)比實(shí)驗(yàn)表明，CoCache可以提高數(shù)據(jù)緩存效率，減少查詢時(shí)間。