MR—DC：基于MapReduce的輕量級數據壓縮策略

田波　丁祥武

摘 要：大數據平臺Hadoop為追求通用性，犧牲了對結構化大數據的處理性能。為此，提出了一種Hadoop平臺上的針對結構化數據的壓縮存儲策略。首先，針對多種不同的數據類型，結合輕量級壓縮算法的特點，設計了多種數據類型的壓縮數據頁；然后，設計了基于HDFS的頁式行列混合存儲結構；最后，設計并實現了基于MapReduce的MR-DC數據壓縮策略，將數據壓縮存儲到設計的存儲結構中。在大規模數據倉庫基準數據集上的實驗結果驗證了提出的策略能夠顯著減少結構化數據的存儲量，從而為提高后續的數據分析處理性能打下基礎。

關鍵詞：數據壓縮；Hadoop；壓縮數據頁；行列混合存儲結構

中圖分類號：TP311 文獻標識碼：A 文章編號：2095-2163（2015）01-

Abstract： Taking account of generality， the big data platform Hadoop sacrifices process performance for structured data. This paper presents a data compression strategy based on Hadoop for structured data. Firstly， considering different data types， combined with characteristics of lightweight compression algorithms， this paper designs a variety of types of compressed data page. Then， the paper proposes the hybrid storage structure of compressed data page based on HDFS. Finally， the paper designs and implements the MR-DC data compression strategy to compress and store big data into the proposed storage structure. Experimental results on large-scale data warehouse benchmark datasets demonstrate the effectiveness of the proposed strategy in reducing the storage amount of structured big data， so as to improve the data analysis processing performance subsequent.

Keywords： Data Compression； Hadoop； Compressed Data Page； Hybrid Storage Structure

0 引 言

信息社會已進入大數據時代，如何高效地存儲和分析大數據，給數據驅動型企業帶來了巨大的挑戰[1]。數據壓縮技術充分利用數據冗余，設計巧妙算法對數據進行重新組織或編碼，從而減少數據存儲量，提高數據的處理效率，是數據分析型應用中重要的研究內容。

列存儲技術[2]在物理上將關系中的元組按屬性拆分，同一屬性的數據連續存儲。由于同一屬性的數據通常具有較大的冗余，且存儲位置物理上相鄰，能夠極大地提高數據壓縮率，減少數據存儲量，進而減少查詢時的I/O開銷，而且提高數據分析應用的查詢處理性能。

作為大數據處理領域事實上的標準，Hadoop被廣泛應用于存儲和處理大規模數據集。Hadoop是MapReduce計算模型的開源實現，并以分布式文件系統HDFS[3]和分布式計算框架MapReduce[4]為核心。HDFS設計的目的是為了存儲大數據，但在數據管理領域中十分重要的數據壓縮方面，卻只提供了通用的壓縮算法如DEFLATE、GZip、BZip2、LZO等[5]，并且只支持文件級、塊級、記錄級壓縮，而忽略了列存儲技術在數據壓縮存儲方面的優勢。MapReduce計算框架對問題采用分治的思想，數據分散到多個DataNode上，多個TaskTracker并行讀取數據進行計算，這對大數據處理則更為有效。但MapReduce讀取HDFS上的數據時只能整個數據塊順序掃描，讀取粒度太大，且讀入了大量不必要的數據，延長了Hadoop集群多用戶的等待時間。

針對上述情況，本文提出了一種基于MapReduce的輕量級數據壓縮策略MR-DC。首先，針對多種不同的數據類型，結合輕量級壓縮算法的特點，設計了基于HDFS的多種數據類型的壓縮數據頁；然后，設計了基于HDFS的頁式行列混合存儲結構；最后，提出并實現了MR-DC數據壓縮策略，將數據壓縮存儲到設計的存儲結構中。基于以上設計，即可達到減少數據量，提高Hadoop對結構化大數據的處理性能之目的。

1 相關工作

1.1數據壓縮

在大數據環境下，數據倉庫應用需要處理的數據量十分巨大，導致了查詢時大量的磁盤I/O。但CPU處理速度與磁盤訪問發展的不平衡，可使得磁盤I/O成為查詢處理的性能瓶頸。而數據壓縮技術減少了數據存儲量，相比之下，讀取壓縮后的數據顯然能夠減少磁盤I/O次數，從而能夠提高查詢效率。

數據壓縮是數據管理領域長期關注的研究內容，壓縮能夠減少數據存儲量，節省I/O帶寬，提升I/O密集型應用的處理效率，被廣泛應用于文本、圖像、音頻、視頻等數據。常用的壓縮算法很多[6-8]，如字典編碼、游程編碼、空值壓制、位圖編碼、增量編碼、LZ系列編碼等。主流的基于行存儲的RDBMS如Oracle、IBM DB2、Microsoft SQL Server等主要采用字典編碼、空值壓制等方法實現壓縮。在列存儲系統中，同一列的數據存儲在物理上相鄰的位置，對其進行壓縮取得了更好的壓縮率。典型的列存儲數據庫系統如C-Store[2]等主要采用字典編碼、空值壓制、游程編碼等進行壓縮。

然而，不同的數據類型適合的壓縮方法不同，即使是同一列的數據，其數據分布特征也影響到壓縮的效果。因此，對壓縮策略選擇的研究也隨著壓縮技術的發展而獲得了重大進展。在壓縮策略選擇上，Abadi等人通過建立決策樹[8]的方式，判定一列數據選用何種壓縮算法；文獻[7]則提出了一種區級壓縮模式下的基于學習的壓縮策略選擇方法，同時考慮數據類型和數據的局部分布特點，對不同列甚至同一列不同分區的數據采用不同的壓縮算法，取得了較好的效果。

1.2行列混合存儲結構

2001年，Ailamaki提出了PAX （Partition Attributes Across）技術[9]，將大的數據塊切分為多個小數據區，每個數據區存儲表中一個屬性列的值，提高了查詢的效率。Abadi等人提出并實現了C-Store[2]存儲架構，數據在底層采用列存儲方式，而上層查詢按照行存儲的方式執行，存儲層和查詢層之間則借助Tuple Mover實現數據遷移。孫林超等人通過研究列存儲技術的特點，提出了一種行列混合存儲[10]數據庫系統的設計方案，在存儲層設計獨立的行存儲引擎和列存儲引擎，采用早物化技術，在數據讀出來之后，將列表轉換為行表，再以行的形式完成后續處理。He等人提出了基于HDFS的RCFile[11]存儲結構，一張表的數據被水平劃分后依次存儲在多個HDFS block，每個block內數據被再次水平劃分，存儲到多個行組，每個行組存儲若干行數據，行組內數據采用列存儲的方式進行存儲。

行列混合存儲結構結合了行存儲和列存儲各自的優點。與列存儲相比，混合存儲結構保證了一條記錄在一個存儲單元內，因而避免了元組重構時數據跨網絡節點傳輸，并且能夠減小查詢開銷；與行存儲相比，混合存儲結構局部仍然采用列存儲，能夠避免無關列的讀取，因而能夠加快查詢處理速度。

2MR-DC數據壓縮策略

2.1頁式行列混合存儲結構

HDFS將數據按大的數據塊來組織，默認情況下，MapReduce計算框架將整個數據塊作為輸入分片來進行處理。Hive的行列混合存儲格式RCFile引入了行組的概念，將行組作為基本的數據存儲單元，但在對數據的壓縮上，只采用了單一的GZip壓縮算法來壓縮所有列，而未能考慮數據類型和分布特征。為此，研究考慮將壓縮數據頁存儲結構引入到HDFS，使得HDFS塊上的數據按頁組織，這樣在每個塊上可以對不同列的數據采用不同的壓縮算法，不同列的數據存儲在不同數據類型的壓縮數據頁中。由于頁結構的引入，可以方便地為列值關聯對應的rowId，這是RCFile所不具備的。

基于以上考慮，文中設計了基于HDFS的壓縮數據頁行列混合存儲結構。基本的思路是，先將一張大表的數據按行劃分，然后將每個劃分的數據選擇合適的輕量級壓縮方法進行壓縮，并將壓縮數據存儲到設計的壓縮數據文件中。在每個壓縮數據文件中，數據按列的順序依次存儲到相應類型的連續多個壓縮數據頁中。每個壓縮數據文件大小略小于HDFS塊大小，保證可以存放在一個HDFS塊中。壓縮數據文件的存儲組織結構為頁式行列混合存儲結構，如圖1所示，首先存儲壓縮數據文件頭頁，然后依次存儲第一列、第二列直至最后一列的數據，每列數據對應連續若干個壓縮數據頁。

壓縮數據文件頭頁中存放該壓縮數據文件的元數據信息，主要有元數據頭信息（MetaDataHeader）、與頁相關的元數據信息（PagesMataData）、與列相關的元數據信息（ColumnsMetaData）、與字典相關的元數據（DictionariesMetaData）和與位圖相關的元數據（BitMapMetaData）等。壓縮數據頁主要用于存放壓縮狀態的數據，元數據（MetaData）部分存放該頁的起始行號（firstRowId）、行數（rowsNum）、數據類型（dataType）、占用字節數（itemLen）、是否壓縮（isCompressed）、壓縮方法（CompressMethod）以及剩余空間（freeSpace）等信息，而數據Data部分存放了該頁存放的壓縮數據。由于頁通常不是恰好裝滿，因此需要進行填充，Fill中保存的是freeSpace字節大小的0。

在本文設計的壓縮數據文件存儲結構中，定位到任意數據頁或者讀取任意一頁中指定索引位置的數據的時間復雜度均為O（1）。在查詢操作時，一旦確定了選中的RowId集合，即可根據壓縮數據文件頭頁的元數據信息，快速過濾掉不需要的頁。在大數據環境下，減少大量不必要的磁盤I/O顯然能夠顯著提升查詢的效率。

不同的數據類型適用的壓縮算法不同，壓縮后的數據表現形式也不盡相同，故針對每種數據類型，設計了相應類型的壓縮數據頁存儲結構。這些數據頁包括CompressedCharDataPage、CompressedVarCharDataPage、CompressedIntDataPage、CompressedLongDataPage、CompressedFloatDataPage、CompressedDoubleDataPage、CompressedDateDataPage。

2.2MR-DC數據壓縮策略

本小節主要研究如何將已有的數據壓縮算法應用到3.1節設計的頁式行列混合存儲結構上。為此，首先研究了一些常見的輕量級數據壓縮算法，然后設計了將數據按照已有的壓縮算法壓縮后存儲到壓縮數據頁的算法，并在此基礎上提出并設計了MR-DC數據壓縮策略，包括兩個階段。

階段1主要的任務是確定出每個劃分中的行數，并為每行數據關聯對應的RowId。該過程使用MapReduce實現。Map任務統計對應的Input Split中記錄的行數，輸出鍵值對為（splitId， rows）對，Reduce任務將鍵值對結果輸出到HDFS上。這樣，當后續MapReduce任務處理任意輸入分片時，該split中的firstRowId的計算公式為：

階段2主要的任務是數據壓縮、壓縮數據文件組裝、持久化。分別對應到MapReduce作業的Map、Reduce、OutputFormat三個處理階段。具體地，Map任務的主要工作是讀取數據，調用相應的壓縮算法，對數據按列進行壓縮，對每列數據輸出多個壓縮數據頁。根據預處理階段的輸出結果，容易計算當前Map所處理的輸入分片的firstRowId，從而為每個記錄關聯真實的RowId。Reduce任務的主要工作是將Map壓縮好的數據頁整理、組裝成一個完整的壓縮數據文件并輸出，OutputFormat負責將組裝好的壓縮數據文件持久化到HDFS上?；贛apReduce的數據壓縮的Map過程的偽代碼描述如算法1所示。

算法1大體上分為兩個階段，數據項的按列收集和多個列的相應頁鏈的壓縮，分別對應步5～11和步12～19。步2從HDFS上讀取表的相關元數據信息，步4初始化數據項集合，為每一列創建一個對應數據類型的數據項鏈表，步5～11循環將每一行的數據收集到對應的數據項鏈表上。步14通過自學習，確定該列適合的壓縮算法，對壓縮方法的選擇算法參考文獻[7-8]。步15將該列的數據按上一步確定的壓縮算法進行壓縮，返回壓縮數據頁鏈表，步17則將壓縮后的數據頁鏈中的頁依次寫到輸出中。

Map和Reduce之間的Partition過程，其輸入是Map的輸出，輸出是Reduce的輸入，作用在于確定將哪些壓縮數據頁交給一個Reduce處理。本文中Partition的設計策略是將每個Map壓縮好的數據頁交由一個Reduce處理。當Map任務對數據進行壓縮之后，數據通過網絡傳遞給Reduce任務，Reduce任務主要負責收集Map壓縮好的數據頁，并將其組裝成順序正確的壓縮數據文件，而后按照該文件中定義的輸出格式將數據寫到輸出流。數據壓縮的Reduce過程的偽代碼描述如算法2所示。

步1～3創建相應的空對象作為容器，步6將壓縮頁依次添加到壓縮數據頁鏈中，步7～9對壓縮文件頭頁中相應的元數據狀態信息進行更新（update）。例如，每處理一個頁，壓縮數據文件頭頁中MetaDataHeader的pageNum將執行加1操作，PagesMetaData中將會增加一條元數據信息記錄該頁的起始行號和該頁的行數；若處理的頁是新的列，ColumnsMetaData中將增加一條元數據信息記錄該列的列名、列類型、是否壓縮、壓縮方法等相關信息。步11～12將壓縮數據文件頭頁和壓縮數據頁鏈組裝成壓縮數據文件并輸出。

3 實驗與分析

3.1實驗環境

實驗使用的開發環境為Eclipse INDIGO，使用的Hadoop版本為1.0.2，HDFS副本因子設置為默認值3，Hive版本為0.11.0。Hadoop集群采用9臺相同配置的節點，其中1臺作為NameNode和JobTracker節點，其余8臺作為DataNode和TaskTracker節點。各個節點配置均為Intel? Core? i7-3770 CPU@3.40GHz，內存8GB，SATA3硬盤容量500GB，操作系統CentOS 6.4。

實驗數據來源于工業界和學術界都普遍采用的大規模基準數據集TPCH。TPCH中共有八張表，其為雪花模式，實驗中主要使用的是事實表part表、lineitem表和orders表。實例數據集的大小由增量因子SF控制。當SF=1時，lineitem表的數據量為6 000 000行。

3.2實驗結果及分析

3.2.1 壓縮算法選擇的評估

實驗1采用本文提出的壓縮策略將part（sf=10）、lineitem（sf=10）、orders（sf=10）三張表壓縮后存儲到本文設計的壓縮數據頁行列混合存儲結構中，以對壓縮方法選擇策略進行評估。壓縮方法及對應列如表1所示。其中，主要使用了游程編碼RLE、位圖向量編碼BE、簡單字典編碼SDE、差量編碼DE。表中的其他列未壓縮。

從表1中看出，本文所提出的對數據分塊壓縮、在壓縮時自動選擇合適的壓縮算法是行之有效的。這些列的數據分布特征與所采用的壓縮算法的適用情形匹配。

3.2.2存儲量的比較

實驗2采用本文提出的壓縮策略將part（sf=10）、lineitem（sf=10）、orders（sf=10）三張表壓縮，對比三張表壓縮存儲時（COMP）占用的存儲量和未壓縮數據（NONE）占用的存儲量。圖2給出了三張表在兩種策略下的存儲量比較結果。

從圖2可以看出，三張表的原始數據占用的存儲量大約是壓縮數據的1.4～2倍。從整張表上看，壓縮率并不高，是因為每張表只對其中的部分列進行了壓縮。相比之下，Orders表壓縮率最低，因為Orders表第9列的取值是字符串類型，該列數據占一條記錄數據量的比例很大，但因為是隨機取值的字符串而未進行壓縮。而其他兩張表由于壓縮的列數較多，因此壓縮后減少的存儲量較多。

實驗3考察SF=20時，對part表中適合采用輕量級壓縮算法進行壓縮的第1、3、4、5、7列進行壓縮，比較壓縮類型為不壓縮（NONE）和壓縮（COMP）情況下的存儲量，圖3給出了比較結果。

從圖3可以看出，在列的數據分布特征比較明顯的情況下，采用輕量級壓縮算法對其進行壓縮時節省存儲空間的效果非常明顯，壓縮率達到了3.4%～33.2%。第1列未壓縮和壓縮后每個元素分別占4字節和1字節的空間，因此壓縮后存儲空間約為原來的25%。第3和4列采用位圖編碼，壓縮率分別為3.4%、32.3%。第5、7列分別使用3個字節和2個字節的字典編碼進行壓縮，壓縮率分別約為14%、20%。

4結束語

本文結合HDFS高擴展性的優點和MapReduce并行計算能力，從減少數據存儲量并提高壓縮效率的角度出發，設計了基于HDFS的壓縮數據頁行列混合存儲結構，并提出了MR-DC數據壓縮策略，將數據壓縮存儲到設計的頁式混合存儲結構中。從而能夠減少數據的存儲量，提高數據分析處理的性能。未來將繼續完善本文提出的數據壓縮策略，并考慮該存儲結構上并行查詢的實現，以及對MapReduce 框架進行優化。

參考文獻：

[1] 孟小峰， 慈祥. 大數據管理： 概念， 技術與挑戰[J]. 計算機研究與發展， 2013， 50（1）： 146-169.

[2] STONEBRAKER M， ABADI D J， BATKIN A， et al. C-store： a column-oriented DBMS[C]//Proceedings of the 31st international conference on Very large data bases. VLDB Endowment， 2005： 553-564.

[3] SHVACHKO K， KUANG H， RADIA S， et al. The hadoop distributed file system[C]//Mass Storage Systems and Technologies （MSST）， 2010 IEEE 26th Symposium on. New York， USA：IEEE， 2010： 1-10.

[4] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[J]. Communications of the ACM， 2008， 51（1）： 107-113.

[5] LAI H， XU M， XU J， et al. Evaluating data storage structures of MapReduce[C]//Computer Science & Education （ICCSE）， 2013 8th International Conference on. Colombo， Sri Lanka：IEEE， 2013： 1041-1045.

[6] WESTMANN T， KOSSMANN D， HELMER S， et al. The implementation and performance of compressed databases[J]. ACM Sigmod Record， 2000， 29（3）： 55-67.

[7] 王振璽， 樂嘉錦， 王梅， 等. 列存儲數據區級壓縮模式與壓縮策略選擇方法[J]. 計算機學報， 2010， 8（33）： 1523-1530.

[8] ABADI D， MADDEN S， FERREIRA M. Integrating compression and execution in column-oriented database systems[C]//Proceedings of the 2006 ACM SIGMOD international conference on Management of data， New York： ACM， 2006： 671-682.

[9] AILAMAKI A. A Storage Model to Bridge the Processor/Memory Speed Gap[C]/ High Performance Transaction Systems Workshop（HPTS）. Asilomar， CA：[s.n.]， 2001.

[10] 孫林超， 陳群， 肖玉澤， 等. 行列混合存儲數據庫系統的研究[J]. 計算機應用研究， 2013， 30（2）： 480-482.

[11] HE Y， LEE R， HUAI Y， et al. RCFile： A fast and space-efficient data placement structure in MapReduce-based warehouse systems[C]//Data Engineering （ICDE′11）， 2011 IEEE 27th International Conference on. Annover， Germany： IEEE， 2011： 1199-1208.