賈威威　林　奕　張延園

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院　陜西 西安 710129)

?

云存儲(chǔ)日志文件系統(tǒng)中垃圾數(shù)據(jù)回收的設(shè)計(jì)與實(shí)現(xiàn)

賈威威林奕張延園

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院陜西 西安 710129)

互聯(lián)網(wǎng)大數(shù)據(jù)蓬勃發(fā)展，各個(gè)行業(yè)都圍繞著大數(shù)據(jù)展開研究。與此同時(shí)，由于數(shù)據(jù)量的異常膨脹，隨之而來的問題就是如何回收垃圾數(shù)據(jù)。基于云存儲(chǔ)日志文件系統(tǒng)HLFS(Hadoop distributed file system based Log-structured File System)，設(shè)計(jì)與實(shí)現(xiàn)了垃圾數(shù)據(jù)回收子系統(tǒng)。通過在HLFS中添加垃圾回收子系統(tǒng)，不但可以提高數(shù)據(jù)空間的利用率，還可以有效地避免數(shù)據(jù)空間不夠用。為了分析HLFS中垃圾回收子系統(tǒng)的性能，最后對(duì)比了HLFS垃圾回收子系統(tǒng)和其他系統(tǒng)中垃圾數(shù)據(jù)回收機(jī)制的優(yōu)缺點(diǎn)，從而幫助用戶選擇合適的垃圾回收機(jī)制提高磁盤利用率和系統(tǒng)性能。

云存儲(chǔ)日志文件系統(tǒng)垃圾數(shù)據(jù)回收

0　引　言

隨著互聯(lián)網(wǎng)大數(shù)據(jù)的日益增長(zhǎng)，各大互聯(lián)網(wǎng)巨頭推出了各自的存儲(chǔ)系統(tǒng)，這些存儲(chǔ)系統(tǒng)也成為了行業(yè)標(biāo)準(zhǔn)。Google設(shè)計(jì)與實(shí)現(xiàn)了Google File System (GFS)[1]和鍵值存儲(chǔ)系統(tǒng)LevelDB[2],Amazon設(shè)計(jì)與實(shí)現(xiàn)了Simple Storage System (S3)[3]和鍵值存儲(chǔ)系統(tǒng)Dynamo[4]，Yahoo!設(shè)計(jì)與實(shí)現(xiàn)了PNUTS[5]，F(xiàn)acebook設(shè)計(jì)與實(shí)現(xiàn)了Cassandra[6]等。這些存儲(chǔ)系統(tǒng)大部分是不開源的，因此開源組織也針對(duì)其公布的文獻(xiàn)設(shè)計(jì)與實(shí)現(xiàn)了開源版存儲(chǔ)系統(tǒng)，例如Apache基金會(huì)設(shè)計(jì)與實(shí)現(xiàn)了GFS開源版Hadoop Distributed File System[7]。這些存儲(chǔ)系統(tǒng)是針對(duì)互聯(lián)網(wǎng)業(yè)務(wù)的特性而設(shè)計(jì)的，比如需要具備高可用性、可擴(kuò)展性、容錯(cuò)性等。但是大部分都沒有考慮設(shè)計(jì)與實(shí)現(xiàn)垃圾數(shù)據(jù)回收子系統(tǒng)，這主要是互聯(lián)網(wǎng)公司對(duì)用戶數(shù)據(jù)的依賴性，用戶的任何數(shù)據(jù)都具有價(jià)值，即使用戶刪除，其系統(tǒng)也不會(huì)自動(dòng)刪除，而是保存這些數(shù)據(jù)。有些應(yīng)用場(chǎng)景如果不及時(shí)刪除用戶的垃圾數(shù)據(jù)，存儲(chǔ)空間很快就不夠用了，例如，嵌入式系統(tǒng)、云存儲(chǔ)時(shí)代大數(shù)據(jù)暴增等。

垃圾回收通常意義上是指對(duì)內(nèi)存空間進(jìn)行管理，因?yàn)橛?jì)算機(jī)內(nèi)存有限，所以使用完的內(nèi)存要及時(shí)回收，然后用于下次計(jì)算再使用。本文中的垃圾數(shù)據(jù)回收主要是指存儲(chǔ)空間(包含內(nèi)存和外存)的回收利用。因?yàn)樵拼鎯?chǔ)時(shí)代，數(shù)據(jù)量的巨增，外存空間如果不加以合理的管理，也會(huì)被很快使用完，這就要求系統(tǒng)工程師設(shè)計(jì)與實(shí)現(xiàn)垃圾數(shù)據(jù)回收子系統(tǒng)從而可以提高存儲(chǔ)空間的利用率。實(shí)際上，存儲(chǔ)空間的垃圾數(shù)據(jù)回收是一個(gè)永久的話題，尤其是當(dāng)前互聯(lián)網(wǎng)用戶數(shù)據(jù)量日益增大，垃圾數(shù)據(jù)回收的設(shè)計(jì)與實(shí)現(xiàn)就迫在眉睫。垃圾數(shù)據(jù)回收的主要作用是能夠在線或者離線回收用戶的垃圾數(shù)據(jù)，這樣就可以提高存儲(chǔ)空間的利用率，一定程度上還可以提高數(shù)據(jù)檢索速度。設(shè)想如果垃圾數(shù)據(jù)被回收，數(shù)據(jù)檢索時(shí)的數(shù)據(jù)量就可以減少，從而提高數(shù)據(jù)檢索速度。但是這也存在一個(gè)折衷，因?yàn)橄到y(tǒng)在垃圾回收時(shí)，可能會(huì)降低系統(tǒng)的整體性能，因此需要設(shè)計(jì)有效的垃圾回收子系統(tǒng)，從而降低系統(tǒng)性能損耗。

實(shí)際上，當(dāng)前很多存儲(chǔ)系統(tǒng)已經(jīng)設(shè)計(jì)與實(shí)現(xiàn)了垃圾數(shù)據(jù)回收子系統(tǒng)。Sheepdog[8]是一個(gè)基于QEMU[9]/KVM[10]設(shè)計(jì)與實(shí)現(xiàn)的分布式存儲(chǔ)系統(tǒng)，可以為虛擬機(jī)提供高可靠的塊級(jí)別卷存儲(chǔ)解決方案，Sheepdog目前支持快照，克隆和垃圾數(shù)據(jù)回收。當(dāng)然還有很多垃圾回收機(jī)制針對(duì)基于閃存硬件的存儲(chǔ)系統(tǒng)，這是由于閃存無法覆蓋寫所引起的。本文基于分布式存儲(chǔ)系統(tǒng)，設(shè)計(jì)與實(shí)現(xiàn)了垃圾數(shù)據(jù)回收子系統(tǒng)，從而提高了系統(tǒng)的存儲(chǔ)空間利用率。本文最后還對(duì)比了HLFS垃圾回收子系統(tǒng)和Sheepdog垃圾回收子系統(tǒng)的優(yōu)缺點(diǎn)，方便以后的設(shè)計(jì)者和用戶選擇合理的垃圾回收子系統(tǒng)。

1　HLFS的設(shè)計(jì)與實(shí)現(xiàn)

為了給網(wǎng)頁應(yīng)用，如維基百科、論壇等，提供小數(shù)據(jù)密集寫服務(wù)，以及虛擬機(jī)提供后臺(tái)存儲(chǔ)服務(wù)，基于HDFS設(shè)計(jì)與實(shí)現(xiàn)了HLFS。HLFS結(jié)合了HDFS和LFS的優(yōu)點(diǎn)，不但可以提供隨機(jī)讀寫功能，同時(shí)還能支持垃圾數(shù)據(jù)回收等特性。

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

HLFS是一個(gè)在用戶態(tài)基于Hadoop分布式文件系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)的分布式文件系統(tǒng)，Linux文件系統(tǒng)總體架構(gòu)如圖1所示。經(jīng)典的文件系統(tǒng)都掛接在Virtual File System(VFS)之上，對(duì)用戶提供統(tǒng)一的接口，HLFS位于在VFS和用戶之間，這樣HLFS就可以在用戶態(tài)給用戶提供存儲(chǔ)服務(wù)。Hadoop分布式文件系統(tǒng)是Apache基金會(huì)根據(jù)Google公布的GFS論文而設(shè)計(jì)與實(shí)現(xiàn)的分布式文件系統(tǒng)，但是Hadoop分布式文件系統(tǒng)不支持隨機(jī)讀寫，其讀寫語義為一次寫入只能讀取(once-write-many-read)。因此HLFS在其基礎(chǔ)之上借助日志結(jié)構(gòu)文件系統(tǒng)的思想設(shè)計(jì)與實(shí)現(xiàn)可以隨機(jī)讀寫的分布式文件系統(tǒng)HLFS。

圖2　HLFS文件系統(tǒng)架構(gòu)

HLFS有兩種模式：一種是本地模式，另一種是HDFS模式。當(dāng)格式化HLFS文件系統(tǒng)的時(shí)候可以選擇格式化為其中的一種模式。HLFS本地模式就和普通文件系統(tǒng)一樣，這種模式主要用于數(shù)據(jù)的本地化，這樣可以降低網(wǎng)絡(luò)負(fù)載，提高讀寫性能。還有一個(gè)用途就是方便設(shè)計(jì)與調(diào)試，而HLFS的HDFS模式主要是把數(shù)據(jù)存放到HDFS這個(gè)分布式文件系統(tǒng)之上，提供高可靠、高可擴(kuò)展以及可容錯(cuò)的大數(shù)據(jù)存儲(chǔ)服務(wù)。HLFS架構(gòu)如圖2所示，在操作系統(tǒng)內(nèi)核空間之上就HLFS的兩種模式，分別是HDFS文件系統(tǒng)服務(wù)和本地文件系統(tǒng)服務(wù)，而這之上就是HLFS的日志文件系統(tǒng)層。

HLFS借助經(jīng)典日志文件系統(tǒng)的思想，因此對(duì)HLFS文件的每次更新都會(huì)追加一個(gè)日志，邏輯上HLFS的存儲(chǔ)空間是由很多個(gè)log組成的，如圖3所示。每個(gè)日志分為五個(gè)部分，依次為日志頭、數(shù)據(jù)塊、索引塊、索引節(jié)點(diǎn)和索引節(jié)點(diǎn)映射。日志頭包含了整個(gè)日志的大小和其他日志元數(shù)據(jù)，數(shù)據(jù)塊存儲(chǔ)了用戶的數(shù)據(jù)，索引塊是用來存儲(chǔ)數(shù)據(jù)塊的索引地址，索引節(jié)點(diǎn)包含了HLFS文件的索引地址，索引節(jié)點(diǎn)映射可以很快找到索引節(jié)點(diǎn)，日志結(jié)構(gòu)如圖4所示。

圖3HLFS存儲(chǔ)結(jié)構(gòu)

圖4HLFS日志結(jié)構(gòu)

為了方便垃圾數(shù)據(jù)回收以及管理HLFS數(shù)據(jù)，HLFS在日志結(jié)構(gòu)之上又劃分了段結(jié)構(gòu)。HLFS段文件是由很多個(gè)日志組成，每個(gè)段文件不超過64 MB，而HDFS默認(rèn)數(shù)據(jù)塊是64 MB，這樣剛好吻合，可以提高數(shù)據(jù)在HDFS之上的存儲(chǔ)和讀取。HLFS分層架構(gòu)如圖5所示，當(dāng)用戶提出一個(gè)文件隨機(jī)寫請(qǐng)求，首先被封裝成一個(gè)日志，然后被追加到當(dāng)前最新的段文件末尾，而用戶的讀請(qǐng)求只需要讀取最新段文件的最新日志就可以通過索引結(jié)構(gòu)讀取到所有數(shù)據(jù)。HLFS索引節(jié)點(diǎn)中的索引結(jié)構(gòu)和經(jīng)典文件系統(tǒng)一樣，直接索引存儲(chǔ)數(shù)據(jù)塊，一級(jí)索引存儲(chǔ)索引塊的地址，以此類推。

圖5　HLFS分層結(jié)構(gòu)

2　HLFS快照

快照在存儲(chǔ)系統(tǒng)中具有很重要的意義，因?yàn)榇鎯?chǔ)系統(tǒng)中存儲(chǔ)的用戶數(shù)據(jù)可能會(huì)因?yàn)楦鞣N原因而被污染或者丟失。如果存儲(chǔ)系統(tǒng)具有快照功能，那么用戶可以很容易就回滾到指定的時(shí)刻，然后恢復(fù)需要的數(shù)據(jù)。尤其是在互聯(lián)網(wǎng)行業(yè)，快照的作用更明顯，用戶的數(shù)據(jù)就是公司賴以生存的基礎(chǔ)，因此需要保護(hù)用戶數(shù)據(jù)的安全正確。HLFS的存儲(chǔ)空間邏輯上是由很多個(gè)日志依次追加形成的，因此每次順序追加的日志就是天然的線性快照。如圖6所示，HLFS線性快照所示，Tn表示在這個(gè)時(shí)間點(diǎn)創(chuàng)建快照snapshotn，回滾只需要加載指定的日志就可以恢復(fù)用戶數(shù)據(jù)。這種線性快照顯然是不夠的，因?yàn)檫@種快照只能按照順序生成，而且快照中的垃圾數(shù)據(jù)也可能會(huì)被回收，因此需要設(shè)計(jì)更為靈活的線性快照。如圖7所示，HLFS樹形快照所示,Tn表示在這個(gè)時(shí)間點(diǎn)創(chuàng)建一個(gè)快照，樹形快照是用戶手動(dòng)生成的，而非系統(tǒng)自動(dòng)生成，因此垃圾回收不會(huì)回收這些快照中所包含的數(shù)據(jù)。樹形快照只需要一個(gè)實(shí)體用來記錄快照點(diǎn)所記錄的日志信息，如索引節(jié)點(diǎn)地址等。

圖7　HLFS樹形快照

圖6HLFS線性快照

很多存儲(chǔ)系統(tǒng)使用多副本來提升系統(tǒng)容錯(cuò)能力，但是這種方式不但占用多倍的存儲(chǔ)空間，而且恢復(fù)數(shù)據(jù)的時(shí)候會(huì)降低系統(tǒng)的性能。HLFS快照系統(tǒng)借助日志結(jié)構(gòu)文件系統(tǒng)的思想具備天然的快照功能，在此基礎(chǔ)之上又設(shè)計(jì)了樹形快照功能，不但回滾快捷而且提高了系統(tǒng)的可靠性和容錯(cuò)性。

3　HLFS垃圾回收子系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

HLFS垃圾數(shù)據(jù)回收子系統(tǒng)分為兩個(gè)部分：快照下的垃圾數(shù)據(jù)回收和非快照下的垃圾數(shù)據(jù)回收子系統(tǒng)。因?yàn)椴荒芑厥沼脩粼O(shè)置快照的數(shù)據(jù)，所以即使用戶設(shè)置快照的數(shù)據(jù)是垃圾數(shù)據(jù)也不能對(duì)其進(jìn)行回收。

3.1HLFS垃圾數(shù)據(jù)

對(duì)HLFS文件的任何更新都會(huì)追加新的日志，每個(gè)日志包含五個(gè)域，其中索引節(jié)點(diǎn)實(shí)體域包含了HLFS文件的主要元數(shù)據(jù)信息，具體如下所示：

struct inode {

uint64_t length;/* the length of hlfs file */

uint64_t ctime; /* time of hlfs create */

uint64_t mtime; /* time of last modification */

uint64_t atime; /* time of last access */

int64_t blocks[12]; /* the first 8KB*12=96KB */

int64_t iblock; /* the next 8KB/8*8KB=8MB */

int64_t doubly_iblock; /* the next 8K/8*8K/8*8K=8GB */

int64_t triply_iblock; /* the next 8K/8*8K/8*8K/8*8K=8TB */

} __attribute__((packed));

在以上索引節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)中l(wèi)ength表示hlfs的大小，ctime、mtime、atime分別表示hlfs文件的創(chuàng)建、最后修改、最后訪問時(shí)間，blocks、iblock、doubly_iblock、triply_iblock是hlfs文件的三級(jí)索引結(jié)構(gòu)，blocks是直接索引，iblock是一級(jí)索引，doubly_iblock是二級(jí)索引，triply_iblock是三級(jí)索引。三級(jí)索引結(jié)構(gòu)是hlfs索引節(jié)點(diǎn)最重要的信息，三級(jí)索引結(jié)構(gòu)具體如圖8所示。

圖8　HLFS文件索引結(jié)構(gòu)

當(dāng)用戶需要更新或者寫入新的數(shù)據(jù)，需要?jiǎng)?chuàng)建新的數(shù)據(jù)塊。如果要更新之前的數(shù)據(jù)，那就先把之前的數(shù)據(jù)塊加載到內(nèi)存，修改要更改的部分。然后創(chuàng)建新的數(shù)據(jù)塊，接著把內(nèi)存修改過的數(shù)據(jù)塊拷貝到創(chuàng)建的數(shù)據(jù)塊上。最后用新創(chuàng)建數(shù)據(jù)塊的邏輯地址覆蓋舊數(shù)據(jù)塊的邏輯地址，舊的數(shù)據(jù)塊就是垃圾數(shù)據(jù)。如果是寫入新的數(shù)據(jù)，只需要把寫入數(shù)據(jù)從內(nèi)存拷貝到新創(chuàng)建的數(shù)據(jù)塊，最后添加邏輯地址到三級(jí)索引結(jié)構(gòu)。在這個(gè)過程中的內(nèi)存數(shù)據(jù)的一致性和持久性都是由HDFS(HLFS HDFS模式)或者本地文件系統(tǒng)(HLFS 本地模式)保證的。

3.2HLFS垃圾數(shù)據(jù)回收

HLFS垃圾數(shù)據(jù)節(jié)描述了HLFS文件系統(tǒng)中垃圾數(shù)據(jù)的產(chǎn)生原因。為了保證數(shù)據(jù)存儲(chǔ)空間的高可用性，要對(duì)垃圾數(shù)據(jù)所占用的存儲(chǔ)空間進(jìn)行回收。為了更高效地管理HLFS存儲(chǔ)空間，垃圾數(shù)據(jù)回收的單位并非以日志為單位。因?yàn)槿绻匀罩緸閱挝荒敲垂芾砘厥招屎艿停Χ炔粔虼?，所以在日志之上劃分了HLFS段文件，每個(gè)HLFS段文件都是由若干個(gè)日志組成的，段文件大小不超過64 MB。HLFS的存儲(chǔ)空間是64位，前38位是段號(hào)，后26位是段內(nèi)偏移地址，因此HLFS文件系統(tǒng)可以有238個(gè)段文件，而每個(gè)段的大小為64 MB。

HLFS垃圾數(shù)據(jù)回收分為兩個(gè)步驟，首先需要統(tǒng)計(jì)當(dāng)前已生成段文件的段使用情況，這里存在一個(gè)段內(nèi)可用數(shù)據(jù)塊的閾值。如果這個(gè)段內(nèi)的可用數(shù)據(jù)塊數(shù)量低于這個(gè)閾值就需要段回收，相反則保留這個(gè)段文件。這個(gè)垃圾回收段閾值是可以配置的，根據(jù)不同的需求可以在系統(tǒng)初始化的時(shí)候設(shè)置。當(dāng)段統(tǒng)計(jì)完成之后，就需要對(duì)段文件可用數(shù)據(jù)塊低于閾值的段文件進(jìn)行回收，HLFS段文件回收采用move-and-remove語義。首先創(chuàng)建新的段文件，把要回收的段文件的可用數(shù)據(jù)塊寫入到新創(chuàng)建的段文件，然后刪除要回收的段文件，整個(gè)段回收工作是后臺(tái)進(jìn)程完成的，只有在當(dāng)前沒有寫入任務(wù)的時(shí)候才開始執(zhí)行段回收工作，這樣就可以避免并發(fā)帶來的一系列問題。

3.3HLFS快照下的垃圾數(shù)據(jù)回收

HLFS快照分為線性快照和樹形快照，線性快照是HLFS文件系統(tǒng)天然具備的，而樹形快照是用戶手動(dòng)生成的。因此HLFS垃圾數(shù)據(jù)回收不能回收用戶打了快照的日志，HLFS快照下的垃圾數(shù)據(jù)回收需要重新設(shè)計(jì)。當(dāng)沒有快照的時(shí)候，段統(tǒng)計(jì)是把當(dāng)前所有段文件中的日志和HLFS最新日志做比較，如果數(shù)據(jù)塊的索引地址和最新日志的索引地址不一樣，那么說明這個(gè)數(shù)據(jù)塊中所包含的數(shù)據(jù)就是垃圾數(shù)據(jù)。而快照下的垃圾回收則是把HLFS存儲(chǔ)空間劃分為若干個(gè)部分，具體由當(dāng)前快照數(shù)決定，以第一個(gè)快照為參照點(diǎn)開始進(jìn)行垃圾數(shù)據(jù)回收。然后從第一個(gè)快照點(diǎn)之后的日志開始，以第二個(gè)快照為參照點(diǎn)開始進(jìn)行垃圾數(shù)據(jù)回收，依次類推，完成HLFS垃圾數(shù)據(jù)回收段統(tǒng)計(jì)。最后對(duì)劃分的這些部分執(zhí)行段回收工作，這個(gè)階段和沒有快照一樣。

4　HLFS垃圾數(shù)據(jù)回收子系統(tǒng)性能分析

垃圾數(shù)據(jù)回收是存儲(chǔ)系統(tǒng)永久的一個(gè)話題，由于磁盤很廉價(jià)以及互聯(lián)網(wǎng)應(yīng)用特征，因此這個(gè)問題一直研究的很少，但是目前由于數(shù)據(jù)量暴增，垃圾數(shù)據(jù)回收已經(jīng)是一個(gè)不可避免的話題。一些存儲(chǔ)系統(tǒng)已經(jīng)引進(jìn)了垃圾回收子系統(tǒng)，例如，Sheepdog等。

Sheepdog是日本NTT公司設(shè)計(jì)與實(shí)現(xiàn)的一款基于QEMU/KVM虛擬機(jī)的分布式塊存儲(chǔ)系統(tǒng)，Sheepdog存儲(chǔ)系統(tǒng)中包含了垃圾數(shù)據(jù)回收子系統(tǒng)，其采用Generational Reference Counting (GRC)[11]算法進(jìn)行垃圾回收。這個(gè)算法的核心思想是：一個(gè)存儲(chǔ)對(duì)象包含代數(shù)和引用計(jì)數(shù)，這里的代數(shù)指的是這個(gè)存儲(chǔ)對(duì)象是第幾代引用，而引用計(jì)數(shù)用來記錄這個(gè)存儲(chǔ)對(duì)象被做了幾次拷貝。這個(gè)算法還引進(jìn)了一個(gè)存儲(chǔ)表，這個(gè)存儲(chǔ)表包含了存儲(chǔ)鏡像中每個(gè)存儲(chǔ)對(duì)象的總引用計(jì)數(shù)。每個(gè)存儲(chǔ)鏡像可以包含很多個(gè)存儲(chǔ)對(duì)象。

當(dāng)一個(gè)存儲(chǔ)對(duì)象A被創(chuàng)建的時(shí)候，它的代數(shù)和引用計(jì)數(shù)被初始化為零，同時(shí)存儲(chǔ)表的第一個(gè)域初始化為一，其他均為零，這是因?yàn)榈谝粋€(gè)存儲(chǔ)對(duì)象已經(jīng)創(chuàng)建了。當(dāng)另一個(gè)存儲(chǔ)對(duì)象B基于A對(duì)象被克隆，那么B的代數(shù)就初始化為A的代數(shù)加一，這是因?yàn)锽是基于A克隆的，A是第一代那么B就是第二代。B的引用計(jì)數(shù)初始化為零，同時(shí)A的引用計(jì)數(shù)加一。當(dāng)存儲(chǔ)表中的存儲(chǔ)對(duì)象(A或者B)被刪除時(shí)，那么一個(gè)刪除消息發(fā)送給存儲(chǔ)表，這個(gè)刪除消息包含要?jiǎng)h除的存儲(chǔ)對(duì)象的代數(shù)和引用計(jì)數(shù)。最后在存儲(chǔ)表中通過代數(shù)找到這個(gè)域，然后減一，同時(shí)把這個(gè)引用計(jì)數(shù)值加到下一個(gè)域，這是因?yàn)檫@個(gè)存儲(chǔ)對(duì)象被拷貝了引用計(jì)數(shù)次。當(dāng)存儲(chǔ)表的每個(gè)域都為零時(shí)，這個(gè)存儲(chǔ)鏡像就可以回收了。

在Sheepdog中快照也是要做拷貝的，因此快照也會(huì)執(zhí)行以上操作。而HLFS快照[12]不需要消耗額外的存儲(chǔ)空間，在HLFS垃圾回收子系統(tǒng)中，不需要開辟存儲(chǔ)空間。Sheepdog垃圾回收是基于GRC算法，需要開辟新的存儲(chǔ)空間，如果沒有拷貝操作，那么每個(gè)存儲(chǔ)對(duì)象都要產(chǎn)生額外的存儲(chǔ)空間來存儲(chǔ)代數(shù)和引用計(jì)數(shù)。如表1所示，HLFS和Sheepdog數(shù)據(jù)操作相關(guān)性對(duì)比，可以發(fā)現(xiàn)，HLFS的數(shù)據(jù)內(nèi)聚性更高，而Sheepdog則相反。

表1　HLFS和Sheepdog數(shù)據(jù)操作相關(guān)性對(duì)比

如表2所示，HLFS垃圾數(shù)據(jù)回收系統(tǒng)和Sheepdog垃圾回收系統(tǒng)對(duì)比，HLFS垃圾數(shù)據(jù)回收是細(xì)粒度回收，基于段文件，而Sheepdog垃圾數(shù)據(jù)回收是針對(duì)一個(gè)鏡像文件，靈活度更低。HLFS垃圾數(shù)據(jù)回收也不需要開辟新的存儲(chǔ)空間，而Sheepdog垃圾回收則需要開辟新的存儲(chǔ)空間。HLFS垃圾回收子系統(tǒng)支持手動(dòng)垃圾數(shù)據(jù)回收，而且支持手動(dòng)配置段文件回收閾值，這樣可以隨時(shí)回收垃圾數(shù)據(jù)所占用的存儲(chǔ)空間。

表2　HLFS垃圾數(shù)據(jù)回收系統(tǒng)和Sheepdog垃圾數(shù)據(jù)系統(tǒng)對(duì)比

當(dāng)把HLFS垃圾回收子系統(tǒng)的段回收閾值設(shè)置為不同的值時(shí)，HLFS垃圾數(shù)據(jù)回收子系統(tǒng)的空間回收率可以不斷調(diào)整，而Sheepdog垃圾回收子系統(tǒng)垃圾數(shù)據(jù)回收率無法手動(dòng)控制，具體如表3所示。

表3　HLFS和Sheepdog垃圾數(shù)據(jù)回收率對(duì)比

HLFS垃圾數(shù)據(jù)回收率V是根據(jù)段文件回收閾值以及回收代價(jià)和系統(tǒng)負(fù)載，然后判斷是否進(jìn)行垃圾回收，當(dāng)所有段文件中的垃圾數(shù)據(jù)量小于回收閾值，就不進(jìn)行回收操作，垃圾數(shù)據(jù)回收率就是0%。因?yàn)榛厥詹僮鞯拇鷥r(jià)很高，嚴(yán)重影響系統(tǒng)性能。而當(dāng)所有段中的垃圾數(shù)據(jù)大于回收閾值，則進(jìn)行垃圾數(shù)據(jù)回收操作，垃圾數(shù)據(jù)回收率是100%。相反，Sheepdog的垃圾數(shù)據(jù)回收策略單一，無論系統(tǒng)負(fù)載多大，數(shù)據(jù)量多大，垃圾數(shù)據(jù)回收率都為V’。

5　結(jié)　語

在分析了云存儲(chǔ)日志文件系統(tǒng)的基礎(chǔ)上，設(shè)計(jì)與實(shí)現(xiàn)了基于HLFS云存儲(chǔ)日志文件系統(tǒng)垃圾數(shù)據(jù)回收子系統(tǒng)。HLFS支持垃圾數(shù)據(jù)回收子系統(tǒng)之后，系統(tǒng)存儲(chǔ)空間利用率更高，有效地提升了本地存儲(chǔ)，避免了網(wǎng)絡(luò)負(fù)載。最后對(duì)比了HLFS垃圾回收子系統(tǒng)和Sheepdog垃圾回收子系統(tǒng)優(yōu)缺點(diǎn)，方便用戶根據(jù)特定場(chǎng)景選擇適合的垃圾回收子系統(tǒng)。

[1] Ghemawat Sanjay,Howard Gobioff,Shun-Tak Leung.The Google file system[J].ACM SIGOPS Operating Systems Review,2003,37(5):29-43.

[2] Leveldb project[EB/OL].(2011-07-20).[2014-11-03].https://github.com/google/leveldb.

[3] Amazon S3 project[EB/OL].(2011-07-20).[2014-11-03].http://aws.amazon.com/cn/s3/.

[4] DeCandia Giuseppe,Hastorun Deniz,Jampani Madon,et al.Dynamo:amazon’s highly available key-value store[J].ACM SIGOPS Operating Systems Review,2007,41(6):205-220.

[5] Cooper Brian F,Ramakrishnan R,Srivastva U,et al.PNUTS: Yahoo!′s hosted data serving platform[C]//Proceedings of the VLDB Endowment 1.2,2008:1277-1288.

[6] Lakshman,Avinash,Prashant Malik.Cassandra: a decentralized structured storage system[J].ACM SIGOPS Operating Systems Review ,2010,44(2):35-40.

[7] Shvachko Konstantin,Huang Hairong,Radia Sanjay,et al.The hadoop distributed file system[C]//Mass Storage Systems and Technologies (MSST),2010 IEEE 26th Symposium on.IEEE,2010,26(1):1-10.

[8] Sheepdog project[EB/OL].(2012-09-09).[2014-11-03].http://sheepdog.github.io/sheepdog/.

[9] QEMU project[EB/OL].(2010-06-09).[2014-11-03].http://wiki.qemu.org/Main_Page.

[10] KVM project[EB/OL].(2012-06-05).[2014-11-03].http://www.linux-kvm.org/page/Main_Page.

[11] Goldberg,Benjamin.Generational reference counting:A reduced-communication distributed storage reclamation scheme[J].ACM SIGPLAN Notices,1989,24(7):43-81.

[12] 陳莉君,康華,賈威威.云存儲(chǔ)日志文件系統(tǒng)中快照的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(7):204-208.

DESIGN AND IMPLEMENTATION OF JUNK DATA RETRIEVE IN LOG-STRUCTURED FILE SYSTEM OF CLOUD STORAGE

Jia WeiweiLin YiZhang Yanyuan

(SchoolofComputingScience,NorthwesternPolytechnicalUniversity,Xi’an710129,Shaanxi,China)

With the booming development of network big data, industry of all sectors are carrying out study around it. Meanwhile, because of the abnormal data expansion, the ensuing problem is how to retrieve junk data. In this paper, we design and implement a junk data retrieve subsystem based on log-structured file system of cloud storage, HLFS (Hadoop distributed file system based log-structured file system). By appending the subsystem to HLFS, not only the utilisation of data space can be enhanced, but the insufficient data space is also effectively avoided. In order to analyse the performance of junk data retrieve subsystem in HLFS, in end of the paper we compare the pros and cons of this subsystem in HLFS with the junk data retrieve mechanism in other systems, thereby help users to choose proper junk data retrieve mechanism to improve disk utilisation and system performance.

Cloud storageLog-structured file systemJunk data retrieve

2015-01-13。國(guó)家自然科學(xué)基金項(xiàng)目(61272123)。賈威威，碩士生，主研領(lǐng)域：存儲(chǔ)系統(tǒng)。林奕，副教授。張延園，教授。

TP3

A

10.3969/j.issn.1000-386x.2016.08.012