云存儲日志文件系統中垃圾數據回收的設計與實現

賈威威　林　奕　張延園

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

?

云存儲日志文件系統中垃圾數據回收的設計與實現

賈威威林奕張延園

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

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

云存儲日志文件系統垃圾數據回收

0　引　言

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

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

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

1　HLFS的設計與實現

為了給網頁應用，如維基百科、論壇等，提供小數據密集寫服務，以及虛擬機提供后臺存儲服務，基于HDFS設計與實現了HLFS。HLFS結合了HDFS和LFS的優點，不但可以提供隨機讀寫功能，同時還能支持垃圾數據回收等特性。

圖1　Linux文件系統架構

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

圖2　HLFS文件系統架構

HLFS有兩種模式：一種是本地模式，另一種是HDFS模式。當格式化HLFS文件系統的時候可以選擇格式化為其中的一種模式。HLFS本地模式就和普通文件系統一樣，這種模式主要用于數據的本地化，這樣可以降低網絡負載，提高讀寫性能。還有一個用途就是方便設計與調試，而HLFS的HDFS模式主要是把數據存放到HDFS這個分布式文件系統之上，提供高可靠、高可擴展以及可容錯的大數據存儲服務。HLFS架構如圖2所示，在操作系統內核空間之上就HLFS的兩種模式，分別是HDFS文件系統服務和本地文件系統服務，而這之上就是HLFS的日志文件系統層。

HLFS借助經典日志文件系統的思想，因此對HLFS文件的每次更新都會追加一個日志，邏輯上HLFS的存儲空間是由很多個log組成的，如圖3所示。每個日志分為五個部分，依次為日志頭、數據塊、索引塊、索引節點和索引節點映射。日志頭包含了整個日志的大小和其他日志元數據，數據塊存儲了用戶的數據，索引塊是用來存儲數據塊的索引地址，索引節點包含了HLFS文件的索引地址，索引節點映射可以很快找到索引節點，日志結構如圖4所示。

圖3HLFS存儲結構

圖4HLFS日志結構

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

圖5　HLFS分層結構

2　HLFS快照

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

圖7　HLFS樹形快照

圖6HLFS線性快照

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

3　HLFS垃圾回收子系統的設計與實現

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

3.1HLFS垃圾數據

對HLFS文件的任何更新都會追加新的日志，每個日志包含五個域，其中索引節點實體域包含了HLFS文件的主要元數據信息，具體如下所示：

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));

在以上索引節點數據結構中length表示hlfs的大小，ctime、mtime、atime分別表示hlfs文件的創建、最后修改、最后訪問時間，blocks、iblock、doubly_iblock、triply_iblock是hlfs文件的三級索引結構，blocks是直接索引，iblock是一級索引，doubly_iblock是二級索引，triply_iblock是三級索引。三級索引結構是hlfs索引節點最重要的信息，三級索引結構具體如圖8所示。

圖8　HLFS文件索引結構

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

3.2HLFS垃圾數據回收

HLFS垃圾數據節描述了HLFS文件系統中垃圾數據的產生原因。為了保證數據存儲空間的高可用性，要對垃圾數據所占用的存儲空間進行回收。為了更高效地管理HLFS存儲空間，垃圾數據回收的單位并非以日志為單位。因為如果以日志為單位那么管理回收效率很低，力度不夠大，所以在日志之上劃分了HLFS段文件，每個HLFS段文件都是由若干個日志組成的，段文件大小不超過64 MB。HLFS的存儲空間是64位，前38位是段號，后26位是段內偏移地址，因此HLFS文件系統可以有238個段文件，而每個段的大小為64 MB。

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

3.3HLFS快照下的垃圾數據回收

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

4　HLFS垃圾數據回收子系統性能分析

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

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

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

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

表1　HLFS和Sheepdog數據操作相關性對比

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

表2　HLFS垃圾數據回收系統和Sheepdog垃圾數據系統對比

當把HLFS垃圾回收子系統的段回收閾值設置為不同的值時，HLFS垃圾數據回收子系統的空間回收率可以不斷調整，而Sheepdog垃圾回收子系統垃圾數據回收率無法手動控制，具體如表3所示。

表3　HLFS和Sheepdog垃圾數據回收率對比

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

5　結　語

在分析了云存儲日志文件系統的基礎上，設計與實現了基于HLFS云存儲日志文件系統垃圾數據回收子系統。HLFS支持垃圾數據回收子系統之后，系統存儲空間利用率更高，有效地提升了本地存儲，避免了網絡負載。最后對比了HLFS垃圾回收子系統和Sheepdog垃圾回收子系統優缺點，方便用戶根據特定場景選擇適合的垃圾回收子系統。

[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] 陳莉君,康華,賈威威.云存儲日志文件系統中快照的設計與實現[J].計算機應用與軟件,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)。賈威威，碩士生，主研領域：存儲系統。林奕，副教授。張延園，教授。

TP3

A

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