魏學(xué)才 宮慶媛 沈佳杰 周揚(yáng)帆 王 新

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203) (綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 陜西 西安 710071) (網(wǎng)絡(luò)信息安全審計(jì)與監(jiān)控教育部工程研究中心 上海 200433)

適應(yīng)冷熱數(shù)據(jù)存儲(chǔ)的多編碼架構(gòu)的設(shè)計(jì)與實(shí)證

魏學(xué)才 宮慶媛 沈佳杰 周揚(yáng)帆*王 新

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203) (綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 陜西 西安 710071) (網(wǎng)絡(luò)信息安全審計(jì)與監(jiān)控教育部工程研究中心 上海 200433)

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，數(shù)據(jù)爆炸性增長(zhǎng)，互聯(lián)網(wǎng)的實(shí)際應(yīng)用也已廣泛依賴于海量數(shù)據(jù)的存儲(chǔ)。實(shí)際的互聯(lián)網(wǎng)應(yīng)用往往需要存儲(chǔ)多種類型數(shù)據(jù)，根據(jù)數(shù)據(jù)被訪問(wèn)頻率差異可以將數(shù)據(jù)劃分為冷熱數(shù)據(jù)。然而，現(xiàn)有的編碼存儲(chǔ)機(jī)制往往只能采用固化的實(shí)現(xiàn)機(jī)制，無(wú)法適應(yīng)多種數(shù)據(jù)類型的編碼存儲(chǔ)，導(dǎo)致存儲(chǔ)系統(tǒng)性能(如數(shù)據(jù)訪問(wèn)時(shí)間)惡化?？紤]到冷熱存儲(chǔ)數(shù)據(jù)的不同，提出一種基于多數(shù)據(jù)編碼機(jī)制的存儲(chǔ)系統(tǒng)框架。對(duì)于冷數(shù)據(jù)，該框架可以采用冗余度較低的編碼，從而提高空間利用率；對(duì)于熱數(shù)據(jù)，該框架可以采用解碼速度較快的編碼，從而提高數(shù)據(jù)訪問(wèn)速度?；贖DFS-RAID設(shè)計(jì)了這一框架并將之實(shí)現(xiàn)為真實(shí)系統(tǒng)，實(shí)際部署在一個(gè)Hadoop集群中。另外基于一個(gè)實(shí)際系統(tǒng)的用戶數(shù)據(jù)軌跡，在搭建的集群中進(jìn)行了試驗(yàn)，實(shí)驗(yàn)結(jié)果表明該框架可以滿足不同類型數(shù)據(jù)同時(shí)高效存取的需求，并對(duì)編碼機(jī)制具備高擴(kuò)展性。

分布式數(shù)據(jù)存儲(chǔ) HDFS 編碼存儲(chǔ)

0 引 言

隨著互聯(lián)網(wǎng)應(yīng)用的興起及移動(dòng)智能時(shí)代的到來(lái)，數(shù)據(jù)增長(zhǎng)的速度越來(lái)越快。根據(jù)IDC的統(tǒng)計(jì)，到2020年全球的數(shù)據(jù)總量將超過(guò)44 ZB[1]。數(shù)據(jù)量的急劇增加，使得數(shù)據(jù)存儲(chǔ)方式逐漸偏向分布式存儲(chǔ)，專用的存儲(chǔ)服務(wù)器也逐漸被低成本存儲(chǔ)設(shè)備替代。然而，廉價(jià)的存儲(chǔ)設(shè)備常常因硬件故障、軟件升級(jí)等導(dǎo)致存儲(chǔ)節(jié)點(diǎn)宕機(jī)、失效，帶來(lái)了數(shù)據(jù)存儲(chǔ)可靠性的問(wèn)題。為保證系統(tǒng)中數(shù)據(jù)的可靠性及可用性，分布式存儲(chǔ)系統(tǒng)引入了相應(yīng)的冗余機(jī)制。

目前實(shí)際系統(tǒng)中常見的產(chǎn)生數(shù)據(jù)冗余的方法有副本、糾刪碼兩種。副本方式下，實(shí)現(xiàn)副本冗余存儲(chǔ)的分布式系統(tǒng)主要有HDFS、GFS、Ceph等[2-4]。

糾刪碼方式與副本不同，通過(guò)對(duì)原文件進(jìn)行分塊、編碼引入冗余，可在保證同樣的存儲(chǔ)可靠性的前提下，引入更小的存儲(chǔ)空間開銷，因而得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。糾刪碼因其在存儲(chǔ)效率上的巨大優(yōu)勢(shì)，已經(jīng)應(yīng)用到了不少實(shí)際的分布式存儲(chǔ)系統(tǒng)中，例如微軟的WAS(Windows Azure Storage)系統(tǒng)[5]、社交網(wǎng)站Facebook的數(shù)據(jù)存儲(chǔ)系統(tǒng)[6,21]、NCCloud系統(tǒng)[7,22]、TFS阿里云[8]等。編碼存儲(chǔ)的性能、失效數(shù)據(jù)修復(fù)等問(wèn)題也存在很多的研究工作，針對(duì)編碼存儲(chǔ)的學(xué)術(shù)研究領(lǐng)域也常常在實(shí)際的分布式存儲(chǔ)系統(tǒng)上來(lái)做性能測(cè)試，進(jìn)行系統(tǒng)級(jí)驗(yàn)證，例如NCFS[9]、NCCloud[7]、文獻(xiàn)[10]中設(shè)計(jì)的Raid6文件系統(tǒng)，以及文獻(xiàn)[11]中設(shè)計(jì)的分布式文件系統(tǒng)。

在“互聯(lián)網(wǎng)+”時(shí)代，越來(lái)越多的企業(yè)需要依賴互聯(lián)網(wǎng)技術(shù)，如云計(jì)算，大數(shù)據(jù)，物聯(lián)網(wǎng)等來(lái)創(chuàng)造更大的企業(yè)價(jià)值及社會(huì)價(jià)值。企業(yè)的業(yè)務(wù)運(yùn)營(yíng)產(chǎn)生了大量數(shù)據(jù)，而數(shù)據(jù)內(nèi)部往往隱藏著價(jià)值，對(duì)這些數(shù)據(jù)的存儲(chǔ)及處理便成為了一項(xiàng)基本的任務(wù)。針對(duì)此任務(wù)，在企業(yè)內(nèi)部部署實(shí)際的分布式系統(tǒng)便是一個(gè)行之有效的應(yīng)對(duì)方案。當(dāng)前主流的分布式系統(tǒng)，包括實(shí)際使用、以及學(xué)術(shù)研究之用，通常采用一種固定的編碼存儲(chǔ)方式，便于設(shè)計(jì)和管理。然而，我們發(fā)現(xiàn)，在同一數(shù)據(jù)中心中通常有多種不同類型的數(shù)據(jù)，例如，在之前的統(tǒng)計(jì)中發(fā)現(xiàn)，存儲(chǔ)系統(tǒng)中存在有90%的數(shù)據(jù)為冷數(shù)據(jù)，通常情況下被訪問(wèn)的頻率小于10%；而只有10%的數(shù)據(jù)為熱數(shù)據(jù)，其被訪問(wèn)的頻率大于90%[12]。如何在具有顯著差別的冷熱數(shù)據(jù)的情況下，優(yōu)化存儲(chǔ)系統(tǒng)的性能成為了當(dāng)前研究的熱點(diǎn)問(wèn)題。目前存儲(chǔ)系統(tǒng)設(shè)計(jì)中所采用的單一固定編碼模式，造成了無(wú)法針對(duì)于不同類型的數(shù)據(jù)進(jìn)行優(yōu)化。因此如何設(shè)計(jì)一個(gè)存儲(chǔ)系統(tǒng)可以同時(shí)支持不同類型的編碼(包括副本方式)就成為了一個(gè)值得研究的問(wèn)題。

冷熱數(shù)據(jù)共存是不同存儲(chǔ)系統(tǒng)都需要考慮的問(wèn)題。如Windows Azure Storage采用LRC算法編碼不再被更改的數(shù)據(jù)，不但降低了存儲(chǔ)開銷，在能耗方面也帶來(lái)了很多益處[5]。有研究工作嘗試使用一種HoVer編碼來(lái)優(yōu)化當(dāng)前系統(tǒng)中編碼的更新效率[13]。然而，在一些應(yīng)用場(chǎng)景中，數(shù)據(jù)的讀取是更頻繁的操作，并且存在大量用戶同時(shí)訪問(wèn)系統(tǒng)的情況。因此如何在大量用戶同時(shí)訪問(wèn)的情況下，提高分布式存儲(chǔ)系統(tǒng)的性能意義重大。

為提高系統(tǒng)的整體性能，應(yīng)該把不同的數(shù)據(jù)區(qū)別看待，如分類為冷數(shù)據(jù)和熱數(shù)據(jù)，采用不同的存儲(chǔ)機(jī)制進(jìn)行實(shí)際存儲(chǔ)。本文設(shè)計(jì)并實(shí)現(xiàn)了一種支持多種編碼并且允許共存的混合存儲(chǔ)框架。通過(guò)對(duì)于不同類型數(shù)據(jù)進(jìn)行不同的處理，本文實(shí)現(xiàn)了在保證數(shù)據(jù)存儲(chǔ)效率的前提下提升存儲(chǔ)系統(tǒng)的數(shù)據(jù)讀取效率。針對(duì)冷熱數(shù)據(jù)存取的問(wèn)題，本文提出了多重編碼混合存儲(chǔ)機(jī)制，并通過(guò)具體的系統(tǒng)試驗(yàn)驗(yàn)證了該存儲(chǔ)框架的有效性。

1 分布式存儲(chǔ)系統(tǒng)與編碼

在存儲(chǔ)以及處理PB甚至ZB級(jí)別的數(shù)據(jù)時(shí)，現(xiàn)在主流的方式是將數(shù)據(jù)放在分布式存儲(chǔ)系統(tǒng)中，如GFS、Ceph、HDFS等。GFS是由谷歌公司研發(fā)的一款可擴(kuò)展的分布式文件系統(tǒng)，可運(yùn)行在大量廉價(jià)的機(jī)器上，專門用于存儲(chǔ)海量搜索數(shù)據(jù)。Ceph是一個(gè)PB級(jí)的分布式文件系統(tǒng)，可同時(shí)支持文件存儲(chǔ)，對(duì)象存儲(chǔ)以及塊存儲(chǔ)，并具有高并發(fā)及高可靠特點(diǎn)。HDFS是Hadoop默認(rèn)的分布式文件系統(tǒng)，在進(jìn)行文件訪問(wèn)時(shí)具有很高的數(shù)據(jù)吞吐率。作為一款優(yōu)秀的開源系統(tǒng)，HDFS在業(yè)界得到廣泛的部署；在進(jìn)行分布式存儲(chǔ)相關(guān)的研究時(shí)，Hadoop以及HDFS越來(lái)越被廣泛地用作研究支撐平臺(tái)。我們的系統(tǒng)也是基于HDFS進(jìn)行的設(shè)計(jì)實(shí)現(xiàn)。

1.1 HDFS

HDFS是集成在Hadoop內(nèi)部的分布式文件系統(tǒng)，目前采用副本的方式來(lái)保證數(shù)據(jù)的可靠性，并且可以達(dá)到很高的數(shù)據(jù)吞吐率。但隨著數(shù)據(jù)規(guī)模的擴(kuò)大，副本方式造成的存儲(chǔ)效率問(wèn)題逐漸引起人們的擔(dān)憂。所以，可以在HDFS中引入糾刪碼等編碼算法，達(dá)到同副本同樣可靠性的情況下，可極大減小數(shù)據(jù)的存儲(chǔ)成本。但在目前的HDFS中引入糾刪碼機(jī)制相當(dāng)困難，因?yàn)楫?dāng)初HDFS在設(shè)計(jì)之初并沒(méi)有引入糾刪碼的考慮，這意味著要么重構(gòu)整個(gè)系統(tǒng)框架，要么舍棄部分性能，從HDFS上層入手解決。目前的可用方案有兩種：

1) HDFS-RAID

HDFS-RAID[14]本身沒(méi)有對(duì)HDFS做任何修改，只是在HDFS上層設(shè)計(jì)實(shí)現(xiàn)了一套框架，作為中間件，間接地引入糾刪碼機(jī)制。下圖是在引入HDFS-RAID以后，用戶讀取異常數(shù)據(jù)時(shí)的一個(gè)詳細(xì)流程。其中DRFS用來(lái)替代原來(lái)的用戶接口，以便利用糾刪碼進(jìn)行數(shù)據(jù)的恢復(fù)。圖1中的RaidNode是最主要模塊，用來(lái)管理文件的編碼及修復(fù)。

圖1 用戶讀取數(shù)據(jù)流程

1. Client向DRFS請(qǐng)求讀取文件數(shù)據(jù)；

2. DRFS將讀取請(qǐng)求轉(zhuǎn)發(fā)給下層的HDFS；

3. HDFS檢測(cè)到用戶讀取的數(shù)據(jù)丟失或出錯(cuò)，拋出異常；

4. DRFS捕獲HDFS拋出的異常，并向RaidNode請(qǐng)求對(duì)用戶正在讀取的文件進(jìn)行臨時(shí)修復(fù)；

5 6 7 8. RaidNode向NameNode請(qǐng)求出錯(cuò)文件的元信息，并從DataNode中讀取其他數(shù)據(jù)進(jìn)行出錯(cuò)數(shù)據(jù)的修復(fù)；

9. RaidNode將生成的臨時(shí)文件句柄返回給DRFS；

10. Client繼續(xù)讀取數(shù)據(jù)，并將數(shù)據(jù)返回給用戶。

目前HDFS-RAID只在內(nèi)部集成了有限的一種或兩種糾刪碼算法，主要的是RS碼。RS碼的參數(shù)選擇很靈活，但在進(jìn)行數(shù)據(jù)恢復(fù)時(shí)會(huì)產(chǎn)生較大的帶寬開銷。用戶若想加入新的編碼算法，不僅需要修改原有的代碼本身，用戶承擔(dān)的工作量也是相當(dāng)大的，因?yàn)橐笥脩羯钊肓私釮DFS-RAID核心部件的內(nèi)部原理，這對(duì)一般研究人員來(lái)說(shuō)尤其困難。另外，HDFS-RAID對(duì)于再生碼是完全不支持的。

2) HDFS-7285

由于HDFS-RAID本身的一些缺點(diǎn)，如數(shù)據(jù)的編碼以及恢復(fù)需要依賴MapReduce,主要適用于冷數(shù)據(jù)處理等，HDFS-7285[15]方案被提出來(lái)。HDFS-7285的作用類似于HDFS-RAID，不過(guò)其是從內(nèi)部修改HDFS原有的結(jié)構(gòu)，使得HDFS內(nèi)置糾刪碼的支持。比如原有的NameNode，DataNode等結(jié)構(gòu)都得到擴(kuò)充，以支持糾刪碼。但目前還在測(cè)試中，部分功能尚未完善；另外，其也沒(méi)有提供對(duì)再生碼的支持。

在本文中，為了能夠更靈活地支持?jǐn)?shù)據(jù)的差異性對(duì)待，即支持更多種類的存儲(chǔ)機(jī)制，我們?cè)O(shè)計(jì)了一套系統(tǒng)框架。該框架基于HDFS-RAID，使得HDFS-RAID不僅能夠支持多種編碼，并且允許多種編碼算法的共存。

1.2 糾刪碼及再生碼

糾刪碼可以有效減少集群的存儲(chǔ)成本，比如系統(tǒng)采用RS(10,4)編碼機(jī)制后，不僅可以容忍任意4個(gè)數(shù)據(jù)塊的丟失，帶來(lái)的冗余開銷也僅為40%(4/10×100%)。目前主流的分布式存儲(chǔ)系統(tǒng)中，幾乎都引入了糾刪碼機(jī)制。如Google的ColossusFs[23]中引入了RS(Reed-Solomon Code)[16]編碼、Microsoft的Azure系統(tǒng)引入了LRC(Local Reconstruction Codes)[5]編碼等。

但在數(shù)據(jù)修復(fù)過(guò)程中，糾刪碼會(huì)造成較大的帶寬開銷。比如對(duì)于RS(10,4)編碼，為了修復(fù)一個(gè)受損的數(shù)據(jù)塊X，需要在網(wǎng)絡(luò)中傳輸10倍于數(shù)據(jù)塊X的數(shù)據(jù)量。雖然一些編碼如LRC對(duì)此作了很好的優(yōu)化，但能夠?qū)崿F(xiàn)修復(fù)帶寬最小的方法是采用再生碼算法。

再生碼[17,18]由網(wǎng)路編碼啟發(fā)而來(lái)，在數(shù)據(jù)修復(fù)過(guò)程中，通過(guò)從更多的存活節(jié)點(diǎn)中讀取數(shù)據(jù)，來(lái)減少需要在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)，從而降低帶寬開銷。在分布式系統(tǒng)中，帶寬是極為珍貴的資源，因此再生碼的意義也顯得尤為重要。

2 軌跡數(shù)據(jù)分析及冷熱數(shù)據(jù)

在提出相應(yīng)系統(tǒng)設(shè)計(jì)之前，先分析實(shí)際系統(tǒng)中數(shù)據(jù)使用的一些特點(diǎn)。

2.1 軌跡數(shù)據(jù)

我們分析了由Harvard大學(xué)發(fā)布的來(lái)取自NFS系統(tǒng)的軌跡數(shù)據(jù)集[19]。此數(shù)據(jù)集涵蓋了多種數(shù)據(jù)流，如郵件通信、研究交流等，具體包括用戶請(qǐng)求及服務(wù)器響應(yīng)等詳細(xì)信息。整個(gè)軌跡數(shù)據(jù)集歷時(shí)41天，開始于2003年1月29日，到2003年3月10日結(jié)束。每個(gè)用戶請(qǐng)求信息中，包括時(shí)間戳、源、宿IP地址以及RPC方法等信息。根據(jù)不同的RPC方法，請(qǐng)求中還可能包括文件句柄，文件偏移位置及長(zhǎng)度信息。

2.2 軌跡數(shù)據(jù)分析

以一周作為粒度(這也是原始數(shù)據(jù)的存在形式)，對(duì)每周的數(shù)據(jù)進(jìn)行分析。把用戶請(qǐng)求中的讀請(qǐng)求及寫請(qǐng)求作為對(duì)文件的一次訪問(wèn)，統(tǒng)計(jì)每個(gè)文件的一周訪問(wèn)量。由于在原始的數(shù)據(jù)中，有些時(shí)間段并沒(méi)有達(dá)到一周的時(shí)間，所以最終我們是以單位小時(shí)內(nèi)文件的訪問(wèn)量來(lái)度量文件的熱度。結(jié)果發(fā)現(xiàn)，在一周的時(shí)間內(nèi)，只有不到10%的文件訪問(wèn)量達(dá)到熱度級(jí)別，其中我們定義熱數(shù)據(jù)(文件)為單位小時(shí)內(nèi)的訪問(wèn)量大于100次/小時(shí)。

隨后分析了熱數(shù)據(jù)以及冷數(shù)據(jù)在每周的變化趨勢(shì)。結(jié)果如圖2、圖3所示，我們可以看到在實(shí)際系統(tǒng)中數(shù)據(jù)的冷熱往往具有連續(xù)性，即熱數(shù)據(jù)往往可以在很長(zhǎng)的一段時(shí)間內(nèi)保持較高的被訪問(wèn)頻率，而冷數(shù)據(jù)訪問(wèn)的頻率也會(huì)長(zhǎng)時(shí)間保持在較低狀態(tài)。從圖中還可以看出，每周的數(shù)據(jù)訪問(wèn)頻率會(huì)有較小幅度的波動(dòng)，因此可以推斷，過(guò)去一周的熱數(shù)據(jù)會(huì)有較小一部分比例可能轉(zhuǎn)換為冷數(shù)據(jù)，反之也應(yīng)成立，但轉(zhuǎn)換比例較前者降低許多。

圖2 熱數(shù)據(jù)每周變化趨勢(shì)

圖3 冷數(shù)據(jù)每周變化趨勢(shì)

通過(guò)軌跡數(shù)據(jù)的分析可知，在一個(gè)分布式存儲(chǔ)系統(tǒng)中，冷熱數(shù)據(jù)的比例往往差異很大，如果單單使用一種存儲(chǔ)機(jī)制，往往會(huì)限制系統(tǒng)某方面的表現(xiàn)，如系統(tǒng)的存儲(chǔ)空間占用，整體的數(shù)據(jù)訪問(wèn)吞吐量等。另外，由于冷熱數(shù)據(jù)的變化趨勢(shì)是連續(xù)的，且變化幅度不明顯，使得系統(tǒng)可以將過(guò)去的文件熱度作為參照，預(yù)測(cè)未來(lái)的文件訪問(wèn)熱度，以便使用合理的存儲(chǔ)方案。

2.3 混合存儲(chǔ)機(jī)制

在目前的多數(shù)分布式存儲(chǔ)系統(tǒng)中，一般采用單一的糾刪碼算法，或者優(yōu)化修復(fù)時(shí)間，或者優(yōu)化存儲(chǔ)開銷。例如，在Google的ColossusFs，F(xiàn)acebook自身使用的HDFS中，以及一些其他的存儲(chǔ)系統(tǒng)[24-25]都選擇RS碼作為內(nèi)部的冗余算法。ColossusFs使用的RS碼帶來(lái)的存儲(chǔ)成本為1.5X，同時(shí)為了修復(fù)一個(gè)失效數(shù)據(jù)塊，需要讀取6個(gè)數(shù)據(jù)塊的數(shù)據(jù)，即需要6倍數(shù)據(jù)的磁盤I/O及網(wǎng)絡(luò)傳輸。在Facebook的HDFS中存儲(chǔ)成本為1.4X，但是需要讀取10倍的數(shù)據(jù)來(lái)修復(fù)一個(gè)失效塊。其他存儲(chǔ)系統(tǒng)中使用的還有LRC碼[5-6]，但在存儲(chǔ)成本與修復(fù)代價(jià)之間與ColossusFs等系統(tǒng)有類似的一個(gè)權(quán)衡關(guān)系。

如果可以在存儲(chǔ)系統(tǒng)中采用兩種或多種糾刪碼算法(包括副本機(jī)制)，則我們就可以在數(shù)據(jù)讀取時(shí)間、修復(fù)時(shí)間與存儲(chǔ)成本以及其他因素之間做一個(gè)更好的權(quán)衡，提高系統(tǒng)的整體性能。例如，系統(tǒng)可以選擇解碼時(shí)間較快的算法來(lái)存儲(chǔ)熱數(shù)據(jù)，存儲(chǔ)代價(jià)較低的算法來(lái)存儲(chǔ)冷數(shù)據(jù)，這樣就可以在存儲(chǔ)成本、數(shù)據(jù)修復(fù)、數(shù)據(jù)訪問(wèn)時(shí)間的等多種因素之間都達(dá)到一個(gè)較好的效果。

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

在系統(tǒng)設(shè)計(jì)上，我們借用了HDFS-RAID的框架結(jié)構(gòu)。HDFS-RAID是基于HDFS的一套框架，在沒(méi)有修改HDFS的前提下,使用戶可以在HDFS中引入糾刪碼機(jī)制。但正如前文所述，HDFS-RAID在編碼支持方面存在許多限制，對(duì)研究帶來(lái)了阻礙。我們?yōu)榱私鉀Q這一問(wèn)題，基于HDFS-RAID設(shè)計(jì)并實(shí)現(xiàn)了一套新的編解碼框架，并對(duì)HDFS-RAID本身的核心模塊做了部分修改，使其不但支持更多種類的編碼，包括再生碼，并允許多種編碼的共存，為不同數(shù)據(jù)的差異化存儲(chǔ)提供了可能性。HDFS-RAID的內(nèi)部架構(gòu)如圖4所示。在圖4中，RaidNode負(fù)責(zé)文件編碼以及恢復(fù)的管理工作，具體的操作交由TriggerMonitor及BlockFixer負(fù)責(zé)。無(wú)論編碼還是恢復(fù)文件，都需要調(diào)用框架內(nèi)部的一個(gè)編解碼模塊Encoder/Decoder。另外，RaidNode還負(fù)責(zé)編碼產(chǎn)生的校驗(yàn)數(shù)據(jù)的簡(jiǎn)單維護(hù)，如尋址，刪除不再被使用的校驗(yàn)數(shù)據(jù)等，并負(fù)責(zé)與HDFS通信(實(shí)際上是跟NameNode通信)，獲取文件的相關(guān)信息，比如掃描當(dāng)前的受損文件以便進(jìn)行修復(fù)。

圖4 HDFS-RAID架構(gòu)圖

系統(tǒng)設(shè)計(jì)的框架結(jié)構(gòu)如圖5所示。

圖5 框架結(jié)構(gòu)圖

從圖中可以看出，沿用了HDFS-RAID的基本結(jié)構(gòu)。但是為了支持多種編碼，對(duì)其中的編解碼模塊做了替換，加入了我們自己設(shè)計(jì)的編解碼模塊。圖中的Replication代表副本編碼方式，用戶可以隨意設(shè)置副本系數(shù)；ErasureCodes代表糾刪碼對(duì)應(yīng)的編解碼器，RegeneratingCodes代表再生碼對(duì)應(yīng)的編解碼器，用戶只需實(shí)現(xiàn)對(duì)應(yīng)的接口，就可以把自身感興趣的相關(guān)算法集成進(jìn)系統(tǒng)之中。另外，為了便于用戶改變存儲(chǔ)機(jī)制，對(duì)RaidNode和BlockFixer都做了相應(yīng)的改善及擴(kuò)充，具體的細(xì)節(jié)可查看對(duì)應(yīng)的源碼及系統(tǒng)文檔。

需要指出的是，我們加入了對(duì)再生碼的支持。因?yàn)樵偕a本身的優(yōu)勢(shì)，在存儲(chǔ)系統(tǒng)中加入對(duì)再生碼的支持意義重大。就我們所知，在HDFS中加入對(duì)再生碼的支持是目前鮮有研究人員涉及的工作。再生碼如前文所述，極大優(yōu)化了數(shù)據(jù)修復(fù)過(guò)程，相比于糾刪碼，引入了更多的幸存節(jié)點(diǎn)向替代節(jié)點(diǎn)傳輸數(shù)據(jù)，實(shí)現(xiàn)修復(fù)帶寬最小化。這也導(dǎo)致再生碼數(shù)據(jù)的存儲(chǔ)方式、修復(fù)時(shí)需要傳輸?shù)臄?shù)據(jù)生成方式更為復(fù)雜。在具體實(shí)現(xiàn)的過(guò)程中，甚至對(duì)底層的HDFS做了相應(yīng)的擴(kuò)充，來(lái)實(shí)現(xiàn)再生碼的向量化存儲(chǔ)，以及修復(fù)時(shí)對(duì)節(jié)點(diǎn)內(nèi)部數(shù)據(jù)的預(yù)編碼。

再生碼的編解碼模塊組成如圖6所示，從圖6中可以看出，恢復(fù)工作是最復(fù)雜的一個(gè)部分。因?yàn)樵谠偕a中，往往存在需要節(jié)點(diǎn)內(nèi)部數(shù)據(jù)預(yù)編碼的需求(也是再生碼優(yōu)越的一個(gè)所在)，而在目前的HDFS以及HDFS-RAID架構(gòu)中并沒(méi)有提供這種支持。AdaptiveBlockSreamReader負(fù)責(zé)如何對(duì)失效的文件進(jìn)行修復(fù)，比如從哪些存活節(jié)點(diǎn)中讀取數(shù)據(jù)，讀取怎樣的數(shù)據(jù)，節(jié)點(diǎn)內(nèi)部的數(shù)據(jù)是否需要預(yù)編碼等；NodeReader代表一個(gè)參與數(shù)據(jù)修復(fù)的存活節(jié)點(diǎn)，在其內(nèi)部可能維護(hù)著數(shù)個(gè)數(shù)據(jù)塊；EncodedSender負(fù)責(zé)發(fā)送預(yù)編碼后的數(shù)據(jù)，這也是對(duì)HDFS做的一個(gè)擴(kuò)充。

圖6 再生碼編解碼框架圖

集成本框架的Hadoop系統(tǒng)支持多種編碼的共存，比如對(duì)長(zhǎng)期訪問(wèn)頻率低的數(shù)據(jù)采用存儲(chǔ)碼率比較高的編碼算法進(jìn)行編碼；對(duì)于訪問(wèn)熱度很高的文件采用恢復(fù)速度較快的編碼算法進(jìn)行編碼，或者直接采用副本方式進(jìn)行存儲(chǔ)。為實(shí)現(xiàn)這一功能，在框架內(nèi)對(duì)TriggerMonitor及BlockFixer都做了相應(yīng)程度的修改，改變了其處理文件時(shí)的部分流程，方便用戶使用。更為主要的是，修改了相關(guān)配置文件的格式，使其適用多種編碼共存的需求。

總而言之，系統(tǒng)框架主要有三個(gè)優(yōu)點(diǎn)：

1) 多種編碼的支持

不僅包括傳統(tǒng)的糾刪碼，我們同時(shí)加入了對(duì)再生碼的支持，另外，我們把副本也作為一種編碼方式。

2) 多種編碼的共存

本框架允許在系統(tǒng)中同時(shí)集成多種編碼算法，為差別地處理不同類型的數(shù)據(jù)建立了基礎(chǔ)。

3) 框架的易用性

本框架在設(shè)計(jì)過(guò)程中，考慮到了用戶的易用性。在原來(lái)的HDFS-RAID中，用戶為了在HDFS上研究感興趣的某種算法，必須對(duì)HDFS-RAID做相應(yīng)的修改，包括核心模塊，如RaidNode，BlockFixer等，并且需要重新編譯HDFS-RAID。在本框架中，用戶只要在相關(guān)配置文件中指明使用的編解碼器，系統(tǒng)在運(yùn)行過(guò)程中就可以動(dòng)態(tài)加載進(jìn)來(lái)，不需對(duì)當(dāng)前的框架做任何修改。

4 實(shí)驗(yàn)結(jié)果與分析

我們搭建了一個(gè)實(shí)際的Hadoop[20]系統(tǒng)，并將本文中設(shè)計(jì)并實(shí)現(xiàn)的框架集成到了系統(tǒng)中。通過(guò)相應(yīng)的實(shí)驗(yàn)，來(lái)驗(yàn)證混合存儲(chǔ)方案對(duì)解決冷熱數(shù)據(jù)問(wèn)題帶來(lái)哪些性能上的提升。

4.1 系統(tǒng)環(huán)境

整個(gè)集群共有12臺(tái)虛擬機(jī)器，其中10臺(tái)作為DataNode。每臺(tái)機(jī)器配置Intel Xeon CPU，單核，主頻2.13 GHz；1 GB內(nèi)存；30 GB硬盤。

每臺(tái)機(jī)器裝載Ubuntu 14.04LTS操作系統(tǒng)；Hadoop中附帶HDFS-RAID模塊，不過(guò)被集成進(jìn)本文實(shí)現(xiàn)的框架。實(shí)驗(yàn)中，我們同時(shí)采用副本和糾刪碼兩種存儲(chǔ)機(jī)制，其中采用的副本方案為3-副本，糾刪碼方案為RS(5,3)。之所以采用RS碼，在于RS是目前在存儲(chǔ)系統(tǒng)中最為廣泛使用的一種編碼算法；將編碼參數(shù)設(shè)置為(5,3)主要是由于目前集群機(jī)器數(shù)量的限制。

4.2 實(shí)驗(yàn)說(shuō)明

在具體實(shí)驗(yàn)中，將第一周的所有文件按訪問(wèn)熱度進(jìn)行排序，其中前10%的文件定義為熱數(shù)據(jù)，后10%的文件定義為冷數(shù)據(jù)。在所有的熱數(shù)據(jù)中，訪問(wèn)頻度至少可以達(dá)到100次/小時(shí)；在所有的冷數(shù)據(jù)中，訪問(wèn)頻度平均小于20次/小時(shí)。隨后我們抽取軌跡數(shù)據(jù)中每周對(duì)應(yīng)于熱數(shù)據(jù)以及冷數(shù)據(jù)的訪問(wèn)模式(即訪問(wèn)次數(shù)，讀取位置及每次的平均訪問(wèn)量)，在實(shí)際的Hadoop系統(tǒng)中再重現(xiàn)，測(cè)得每周的總體訪問(wèn)時(shí)間。

將熱數(shù)據(jù)用副本方式進(jìn)行存儲(chǔ)，將冷數(shù)據(jù)用RS編碼進(jìn)行存儲(chǔ)。在訪問(wèn)副本存儲(chǔ)的文件時(shí)，我們通過(guò)調(diào)用底層的block相關(guān)接口將用戶請(qǐng)求均勻地分布到3個(gè)副本上，以發(fā)揮副本并行讀取的優(yōu)勢(shì)。在訪問(wèn)RS碼存儲(chǔ)的文件時(shí)，使用同副本方式同樣的接口，以避免帶來(lái)不確定因素，當(dāng)然，RS編碼的文件只有一個(gè)原始文件。

根據(jù)第2節(jié)對(duì)軌跡數(shù)據(jù)的分析，了解到熱數(shù)據(jù)及冷數(shù)據(jù)在每周的變化趨勢(shì)并不明顯，但會(huì)有較小比例的浮動(dòng)。在實(shí)驗(yàn)中我們簡(jiǎn)單假設(shè)上一周的熱數(shù)據(jù)中會(huì)有10%轉(zhuǎn)化為冷數(shù)據(jù)；上一周冷數(shù)據(jù)中的10%會(huì)轉(zhuǎn)化為熱數(shù)據(jù)。之后我們會(huì)使用每周的訪問(wèn)模式訪問(wèn)冷熱數(shù)據(jù)得出每周的平均訪問(wèn)時(shí)間。

設(shè)定HDFS的block大小為64 MB，每個(gè)文件大小為320 MB，這主要是為了適應(yīng)RS碼的編碼系數(shù)；另外，集群總的存儲(chǔ)空間限制也是如此設(shè)定的一個(gè)原因。

由于軌跡數(shù)據(jù)所在的實(shí)際系統(tǒng)的規(guī)模可能大于本文實(shí)驗(yàn)所使用的集群，為了實(shí)驗(yàn)結(jié)果的可用性，對(duì)軌跡數(shù)據(jù)中的訪問(wèn)次數(shù)進(jìn)行了相應(yīng)比例的縮減，大約轉(zhuǎn)化為原來(lái)的幾十分之一。

在實(shí)驗(yàn)時(shí)，以軌跡數(shù)據(jù)中第一周的狀態(tài)作為實(shí)驗(yàn)的初始狀態(tài)，根據(jù)每周的訪問(wèn)模式統(tǒng)計(jì)出每周的所有文件平均訪問(wèn)時(shí)間以及所有文件的磁盤占用空間。在得出某一周的相關(guān)數(shù)據(jù)后，根據(jù)之前的策略將冷數(shù)據(jù)及熱數(shù)據(jù)進(jìn)行相應(yīng)比例的轉(zhuǎn)換，然后進(jìn)行下一周的實(shí)驗(yàn)。對(duì)于每周的數(shù)據(jù)，進(jìn)行3次實(shí)驗(yàn)，然后求取平均值。

4.3 對(duì)比實(shí)驗(yàn)設(shè)計(jì)

設(shè)定了兩組對(duì)比實(shí)驗(yàn)，用來(lái)測(cè)定系統(tǒng)在使用單一的存儲(chǔ)機(jī)制時(shí)會(huì)帶來(lái)什么影響。一組將所有的文件看作冷數(shù)據(jù)，使用RS碼進(jìn)行編碼并存儲(chǔ)；另一組將所有的文件看作熱數(shù)據(jù)，使用副本方式進(jìn)行存儲(chǔ)。

隨后的實(shí)驗(yàn)過(guò)程與4.2節(jié)描述的相同，即利用同樣的訪問(wèn)模式統(tǒng)計(jì)出每周的平均訪問(wèn)時(shí)間及磁盤占用空間。

4.4 實(shí)驗(yàn)結(jié)果與分析

通過(guò)一組原始實(shí)驗(yàn)及兩組對(duì)比實(shí)驗(yàn)，我們得出了每周所有文件的平均訪問(wèn)時(shí)間，及所有文件的磁盤占用空間。如圖7、圖8所示。

圖7 三組實(shí)驗(yàn)比較

圖8 存儲(chǔ)空間對(duì)比

從圖8可以看出，單一熱數(shù)據(jù)機(jī)制雖然總體訪問(wèn)時(shí)間較低，但所占存儲(chǔ)空間卻是最大的，為96 000 MB；混合存儲(chǔ)機(jī)制所占空間為73 600 MB，相對(duì)于前者降低了23.3%，由此也可以看出混合存儲(chǔ)機(jī)制的優(yōu)勢(shì)。

由圖可以看出以下幾個(gè)特點(diǎn)：

1) 多數(shù)情況下，混合存儲(chǔ)的平均訪問(wèn)時(shí)間是略大于單一熱數(shù)據(jù)存儲(chǔ)機(jī)制的。原因有兩個(gè)，一個(gè)在當(dāng)訪問(wèn)副本機(jī)制存儲(chǔ)的文件時(shí)，可以同時(shí)訪問(wèn)多個(gè)副本，利用訪問(wèn)的并行性降低總體訪問(wèn)時(shí)間；另一個(gè)在全部數(shù)據(jù)中，冷數(shù)據(jù)占的比例雖然較大，但總的訪問(wèn)量卻非常小，因此兩種存儲(chǔ)機(jī)制的差距并沒(méi)有很明顯，甚至有些接近。

2) 單一冷數(shù)據(jù)機(jī)制的訪問(wèn)時(shí)間雖然大于單一熱數(shù)據(jù)機(jī)制的訪問(wèn)時(shí)間，但差別卻不明顯。我們知道單純的讀取操作是完全可以并發(fā)的，如果用戶的請(qǐng)求規(guī)模沒(méi)有超過(guò)節(jié)點(diǎn)的負(fù)載能力，那么一個(gè)節(jié)點(diǎn)無(wú)論是處理較多還是較少的用戶請(qǐng)求，差別是不明顯的。由于本實(shí)驗(yàn)中，無(wú)論是數(shù)據(jù)規(guī)模還是用戶請(qǐng)求規(guī)模都沒(méi)有達(dá)到一定的級(jí)別，所以出現(xiàn)了這種結(jié)果。不過(guò)，當(dāng)用戶請(qǐng)求規(guī)模達(dá)到一定程度，兩種存儲(chǔ)機(jī)制的差距會(huì)拉大。

3) 在一些情況下，數(shù)據(jù)出現(xiàn)了反常，比如第二周的數(shù)據(jù)。經(jīng)分析，我們?cè)谙螺d軌跡數(shù)據(jù)時(shí)，對(duì)方服務(wù)器出現(xiàn)錯(cuò)誤，導(dǎo)致若干天的數(shù)據(jù)丟失，造成一些結(jié)果比如訪問(wèn)模式出現(xiàn)誤差。

5 結(jié) 語(yǔ)

本文通過(guò)對(duì)冷熱數(shù)據(jù)在實(shí)際存儲(chǔ)系統(tǒng)中的分析，指出在實(shí)際的系統(tǒng)中應(yīng)該加入對(duì)混合存儲(chǔ)機(jī)制的支持?；旌洗鎯?chǔ)機(jī)制能夠?qū)Σ煌愋偷臄?shù)據(jù)差異性處理，比如選擇不同的編碼算法，適時(shí)地切換數(shù)據(jù)的存儲(chǔ)機(jī)制等等，能夠帶來(lái)系統(tǒng)在存儲(chǔ)效率、響應(yīng)時(shí)間等指標(biāo)上的顯著提升。我們基于HDFS設(shè)計(jì)并實(shí)現(xiàn)了一套支持多種編碼算法，并允許多編碼共存的系統(tǒng)框架，通過(guò)實(shí)驗(yàn)驗(yàn)證了系統(tǒng)框架的可用性，及混合存儲(chǔ)機(jī)制在存儲(chǔ)效率、數(shù)據(jù)訪問(wèn)時(shí)間等方面對(duì)系統(tǒng)性能的提升。本文工作并沒(méi)有對(duì)我們實(shí)現(xiàn)的系統(tǒng)框架做非常深入的使用，下一步計(jì)劃中，準(zhǔn)備基于本框架對(duì)混合存儲(chǔ)機(jī)制在實(shí)際系統(tǒng)中的應(yīng)用做更進(jìn)一步的研究，比如編碼算法的選擇、不同編碼之間切換的開銷等等。

[1] Gantz J,Reinsel D.Extracting value from chaos state of the universe:an executive summary[R].IDC iView,2011:1-12.

[2] Shvachko K,Kuang H,Radia S,et al.The Hadoop distributed file system[C]//2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST).IEEE Computer Society,2010:1-10.

[3] Ghemawat S,Gobioff H,Leung S T.The Google file system[J].ACM SIGOPS Operating Systems Review,2003,37(5):29-43.

[4] Weil S A,Brandt S A,Miller E L,et al.Ceph:a scalable,high-performance distributed file system[C]//Proceedings of the 7th Symposium on Operating Systems Design and Implementation,Seattle,WA,USA.USENIX Association,2006:307-320.

[5] Huang C,Simitci H,Xu Y,et al.Erasure coding in Windows Azure storage[C]//2012 USENIX Annual Technical Conference,2012:15-26.

[6] Sathiamoorthy M,Asteris M,Papailiopoulos D,et al.XORing elephants: novel erasure codes for big data[J].Proceedings of the VLDB Endowment,2013,6(5):325-336.

[7] Hu Y,Chen H C H,Lee P P C,et al.NCCloud:applying network coding for the storage repair in a cloud-of-clouds[C]//Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST 12),2012:21.

[8] TFS Erasure code實(shí)現(xiàn)方案[EB/OL].(2014-04-16).[2015-12-09].http://blog.chinaunix.net/uid-20196318-id-4212712.html.

[9] Hu Y,Yu C M,Li Y K,et al.NCFS:on the practicality and extensibility of a network-coding-based distributed file system[C]//Network Coding (NetCod),2011 International Symposium on.IEEE,2011:1-6.

[10] 衛(wèi)東升.一種修復(fù)優(yōu)化的Raid6文件系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].上海:復(fù)旦大學(xué),2015.

[11] 權(quán)恒星.基于SDN的分布式文件系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].上海:復(fù)旦大學(xué),2015.

[12] Hafner J L.HoVer erasure codes for disk arrays[C]//Dependable Systems and Networks,2006 International Conference on.IEEE,2006:217-226.

[13] Xia M,Saxena M,Blaum M,et al.A tale of two erasure codes in HDFS[C]//Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST 15),2015:213-226.

[14] Hadoop Wiki.HDFS RAID[OL].(2011-11-02).[2015-12-09].http://wiki.apache.org/hadoop/HDFS-RAID.

[15] The Apache Software Foundation.Erasure coding support inside HDFS[OL].(2015-09-30).[2015-12-09].https://issues.apache.org/jira/browse/HDFS-7285.

[16] Reed I S,Solomon G.Polynomial codes over certain finite fields[J].Journal of the Society for Industrial and Applied Mathematics,1960,8(2):300-304.

[17] Dimakis A G,Godfrey P B,Wu Y,et al.Network coding for distributed storage systems[J].IEEE Transactions on Information Theory,2010,56(9):4539-4551.

[18] Dimakis A G,Ramchandran K,Wu Y,et al.A survey on network codes for distributed storage[J].Proceedings of the IEEE,2011,99(3):476-489.

[19] Ellard D J.Trace-based analyses and optimizations for network storage servers[D].Cambridge,MA,USA:Harvard University,2004.

[20] The Apache Software Foundation.Welcome to Apache Hadoop[OL].(2015-10-30).[2015-12-09].http://hadoop.apache.org.

[21] Rashmi K V,Shah N B,Gu D,et al.A solution to the network challenges of data recovery in erasure-coded distributed storage systems:a study on the Facebook warehouse cluster[C]//Proceedings of the 5th USENIX Conference on Hot Topics in Storage and File Systems,2013:8.

[22] Hu Y,Lee P P C,Shum K W.Analysis and construction of functional regenerating codes with uncoded repair for distributed storage systems[C]//2013 IEEE International Conference on Computer Communications.IEEE,2013:2355-2363.

[23] Fikes A.Storage architecture and challenges[DB/OL].(2010-07-29).[2015-12-09].http://static.googlecontent.com/media/research.google.com/zh-CN//university/relations/facultysummit2010/storage_architecture_and_challenges.pdf.

[24] Khan O,Burns R,Plank J,et al.Rethinking erasure codes for cloud file systems:minimizing I/O for recovery and degraded reads[C]//Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST 12),2012:20.

[25] Rashmi K V,Shan N B,Gu D,et al.A “hitchhiker′s” guide to fast and efficient data reconstruction in erasure-coded data centers[J].ACM SIGCOMM Computer Communication Review,2014,44(4):331-342.

DESIGN AND DEMONSTRATION OF MULTI-CODES FRAMEWORK FOR COLD/HOT DATA STORAGE

Wei Xuecai Gong Qingyuan Shen Jiajie Zhou Yangfan*Wang Xin

(SchoolofComputerScience,FudanUniversity,Shanghai201203,China) (StateKeyLaboratoryofIntegratedServicesNetworks,Xi’an710071,Shaanxi,China) (EngineeringResearchCenterofCyberSecurityAuditingandMonitoring,MinistryofEducation,Shanghai200433,China)

With the rapid development of the Internet and the explosive growth of data, large-scale distributed storage systems are widely used in Internet application. Recent Internet applications usually involve different types of data, and data can be considered as hot data or cold data based on their access frequency. However, a storage system with erasure codes is generally implemented with a fixed coding mechanism, which cannot adapt well to the diverse types of data coexisting in the same system. As a result, the system performance may greatly degrade. Thus, a new storage system framework is suggested to improve the system performance based on multiple codes, considering the difference between hot and cold data. For cold data, it can adopt a low-redundancy coding mechanism to improve space efficiency. For hot data, in contrast, it can reduce the data access time by taking a code that can be rapidly decoded. Then, real-world implementations of such a framework based on HDFS-RAID are designed, which is deployed in a Hadoop tested cluster. Besides, based on a real-world data access trace, the effectiveness of our system in improving the system performance is verified. The results show that the system can adapt well to the diverse types of data.

Distributed data storage HDFS Encoding storage

2016-01-20。國(guó)家自然科學(xué)基金項(xiàng)目(61571136)；上海市“科技創(chuàng)新行動(dòng)計(jì)劃”項(xiàng)目(14511101000)；綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室開放研究課題(ISN15-08)。魏學(xué)才，碩士生，主研領(lǐng)域：分布式存儲(chǔ)系統(tǒng)中的冗余修復(fù)。宮慶媛，博士生。沈佳杰，博士生。周揚(yáng)帆，副研究員。王新，教授。

TP3

A

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