賈威威　林　奕　張延園

(西北工業(yè)大學計算機學院　陜西 西安 710129)

?

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

賈威威林奕張延園

(西北工業(yè)大學計算機學院陜西 西安 710129)

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

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

0　引　言

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

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

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

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

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

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

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

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

HLFS有兩種模式：一種是本地模式，另一種是HDFS模式。當格式化HLFS文件系統(tǒng)的時候可以選擇格式化為其中的一種模式。HLFS本地模式就和普通文件系統(tǒng)一樣，這種模式主要用于數(shù)據(jù)的本地化，這樣可以降低網(wǎng)絡(luò)負載，提高讀寫性能。還有一個用途就是方便設(shè)計與調(diào)試，而HLFS的HDFS模式主要是把數(shù)據(jù)存放到HDFS這個分布式文件系統(tǒng)之上，提供高可靠、高可擴展以及可容錯的大數(shù)據(jù)存儲服務(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)的思想，因此對HLFS文件的每次更新都會追加一個日志，邏輯上HLFS的存儲空間是由很多個log組成的，如圖3所示。每個日志分為五個部分，依次為日志頭、數(shù)據(jù)塊、索引塊、索引節(jié)點和索引節(jié)點映射。日志頭包含了整個日志的大小和其他日志元數(shù)據(jù)，數(shù)據(jù)塊存儲了用戶的數(shù)據(jù)，索引塊是用來存儲數(shù)據(jù)塊的索引地址，索引節(jié)點包含了HLFS文件的索引地址，索引節(jié)點映射可以很快找到索引節(jié)點，日志結(jié)構(gòu)如圖4所示。

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

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

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

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

2　HLFS快照

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

圖7　HLFS樹形快照

圖6HLFS線性快照

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

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

HLFS垃圾數(shù)據(jù)回收子系統(tǒng)分為兩個部分：快照下的垃圾數(shù)據(jù)回收和非快照下的垃圾數(shù)據(jù)回收子系統(tǒng)。因為不能回收用戶設(shè)置快照的數(shù)據(jù)，所以即使用戶設(shè)置快照的數(shù)據(jù)是垃圾數(shù)據(jù)也不能對其進行回收。

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

對HLFS文件的任何更新都會追加新的日志，每個日志包含五個域，其中索引節(jié)點實體域包含了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é)點數(shù)據(jù)結(jié)構(gòu)中l(wèi)ength表示hlfs的大小，ctime、mtime、atime分別表示hlfs文件的創(chuàng)建、最后修改、最后訪問時間，blocks、iblock、doubly_iblock、triply_iblock是hlfs文件的三級索引結(jié)構(gòu)，blocks是直接索引，iblock是一級索引，doubly_iblock是二級索引，triply_iblock是三級索引。三級索引結(jié)構(gòu)是hlfs索引節(jié)點最重要的信息，三級索引結(jié)構(gòu)具體如圖8所示。

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

當用戶需要更新或者寫入新的數(shù)據(jù)，需要創(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ù)塊，最后添加邏輯地址到三級索引結(jié)構(gòu)。在這個過程中的內(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ù)存儲空間的高可用性，要對垃圾數(shù)據(jù)所占用的存儲空間進行回收。為了更高效地管理HLFS存儲空間，垃圾數(shù)據(jù)回收的單位并非以日志為單位。因為如果以日志為單位那么管理回收效率很低，力度不夠大，所以在日志之上劃分了HLFS段文件，每個HLFS段文件都是由若干個日志組成的，段文件大小不超過64 MB。HLFS的存儲空間是64位，前38位是段號，后26位是段內(nèi)偏移地址，因此HLFS文件系統(tǒng)可以有238個段文件，而每個段的大小為64 MB。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5　結(jié)　語

在分析了云存儲日志文件系統(tǒng)的基礎(chǔ)上，設(shè)計與實現(xiàn)了基于HLFS云存儲日志文件系統(tǒng)垃圾數(shù)據(jù)回收子系統(tǒng)。HLFS支持垃圾數(shù)據(jù)回收子系統(tǒng)之后，系統(tǒng)存儲空間利用率更高，有效地提升了本地存儲，避免了網(wǎng)絡(luò)負載。最后對比了HLFS垃圾回收子系統(tǒng)和Sheepdog垃圾回收子系統(tǒng)優(yōu)缺點，方便用戶根據(jù)特定場景選擇適合的垃圾回收子系統(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] 陳莉君,康華,賈威威.云存儲日志文件系統(tǒng)中快照的設(shè)計與實現(xiàn)[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。國家自然科學基金項目(61272123)。賈威威，碩士生，主研領(lǐng)域：存儲系統(tǒng)。林奕，副教授。張延園，教授。

TP3

A

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