田波　丁祥武

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

關(guān)鍵詞：數(shù)據(jù)壓縮；Hadoop；壓縮數(shù)據(jù)頁；行列混合存儲結(jié)構(gòu)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：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 引 言

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

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

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

針對上述情況，本文提出了一種基于MapReduce的輕量級數(shù)據(jù)壓縮策略MR-DC。首先，針對多種不同的數(shù)據(jù)類型，結(jié)合輕量級壓縮算法的特點，設(shè)計了基于HDFS的多種數(shù)據(jù)類型的壓縮數(shù)據(jù)頁；然后，設(shè)計了基于HDFS的頁式行列混合存儲結(jié)構(gòu)；最后，提出并實現(xiàn)了MR-DC數(shù)據(jù)壓縮策略，將數(shù)據(jù)壓縮存儲到設(shè)計的存儲結(jié)構(gòu)中?；谝陨显O(shè)計，即可達(dá)到減少數(shù)據(jù)量，提高Hadoop對結(jié)構(gòu)化大數(shù)據(jù)的處理性能之目的。

1 相關(guān)工作

1.1數(shù)據(jù)壓縮

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

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

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

1.2行列混合存儲結(jié)構(gòu)

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

行列混合存儲結(jié)構(gòu)結(jié)合了行存儲和列存儲各自的優(yōu)點。與列存儲相比，混合存儲結(jié)構(gòu)保證了一條記錄在一個存儲單元內(nèi)，因而避免了元組重構(gòu)時數(shù)據(jù)跨網(wǎng)絡(luò)節(jié)點傳輸，并且能夠減小查詢開銷；與行存儲相比，混合存儲結(jié)構(gòu)局部仍然采用列存儲，能夠避免無關(guān)列的讀取，因而能夠加快查詢處理速度。

2MR-DC數(shù)據(jù)壓縮策略

2.1頁式行列混合存儲結(jié)構(gòu)

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

基于以上考慮，文中設(shè)計了基于HDFS的壓縮數(shù)據(jù)頁行列混合存儲結(jié)構(gòu)?；镜乃悸肥?，先將一張大表的數(shù)據(jù)按行劃分，然后將每個劃分的數(shù)據(jù)選擇合適的輕量級壓縮方法進(jìn)行壓縮，并將壓縮數(shù)據(jù)存儲到設(shè)計的壓縮數(shù)據(jù)文件中。在每個壓縮數(shù)據(jù)文件中，數(shù)據(jù)按列的順序依次存儲到相應(yīng)類型的連續(xù)多個壓縮數(shù)據(jù)頁中。每個壓縮數(shù)據(jù)文件大小略小于HDFS塊大小，保證可以存放在一個HDFS塊中。壓縮數(shù)據(jù)文件的存儲組織結(jié)構(gòu)為頁式行列混合存儲結(jié)構(gòu)，如圖1所示，首先存儲壓縮數(shù)據(jù)文件頭頁，然后依次存儲第一列、第二列直至最后一列的數(shù)據(jù)，每列數(shù)據(jù)對應(yīng)連續(xù)若干個壓縮數(shù)據(jù)頁。

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

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

不同的數(shù)據(jù)類型適用的壓縮算法不同，壓縮后的數(shù)據(jù)表現(xiàn)形式也不盡相同，故針對每種數(shù)據(jù)類型，設(shè)計了相應(yīng)類型的壓縮數(shù)據(jù)頁存儲結(jié)構(gòu)。這些數(shù)據(jù)頁包括CompressedCharDataPage、CompressedVarCharDataPage、CompressedIntDataPage、CompressedLongDataPage、CompressedFloatDataPage、CompressedDoubleDataPage、CompressedDateDataPage。

2.2MR-DC數(shù)據(jù)壓縮策略

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

階段1主要的任務(wù)是確定出每個劃分中的行數(shù)，并為每行數(shù)據(jù)關(guān)聯(lián)對應(yīng)的RowId。該過程使用MapReduce實現(xiàn)。Map任務(wù)統(tǒng)計對應(yīng)的Input Split中記錄的行數(shù)，輸出鍵值對為（splitId， rows）對，Reduce任務(wù)將鍵值對結(jié)果輸出到HDFS上。這樣，當(dāng)后續(xù)MapReduce任務(wù)處理任意輸入分片時，該split中的firstRowId的計算公式為：

階段2主要的任務(wù)是數(shù)據(jù)壓縮、壓縮數(shù)據(jù)文件組裝、持久化。分別對應(yīng)到MapReduce作業(yè)的Map、Reduce、OutputFormat三個處理階段。具體地，Map任務(wù)的主要工作是讀取數(shù)據(jù)，調(diào)用相應(yīng)的壓縮算法，對數(shù)據(jù)按列進(jìn)行壓縮，對每列數(shù)據(jù)輸出多個壓縮數(shù)據(jù)頁。根據(jù)預(yù)處理階段的輸出結(jié)果，容易計算當(dāng)前Map所處理的輸入分片的firstRowId，從而為每個記錄關(guān)聯(lián)真實的RowId。Reduce任務(wù)的主要工作是將Map壓縮好的數(shù)據(jù)頁整理、組裝成一個完整的壓縮數(shù)據(jù)文件并輸出，OutputFormat負(fù)責(zé)將組裝好的壓縮數(shù)據(jù)文件持久化到HDFS上。基于MapReduce的數(shù)據(jù)壓縮的Map過程的偽代碼描述如算法1所示。

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

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

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

3 實驗與分析

3.1實驗環(huán)境

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

實驗數(shù)據(jù)來源于工業(yè)界和學(xué)術(shù)界都普遍采用的大規(guī)?；鶞?zhǔn)數(shù)據(jù)集TPCH。TPCH中共有八張表，其為雪花模式，實驗中主要使用的是事實表part表、lineitem表和orders表。實例數(shù)據(jù)集的大小由增量因子SF控制。當(dāng)SF=1時，lineitem表的數(shù)據(jù)量為6 000 000行。

3.2實驗結(jié)果及分析

3.2.1 壓縮算法選擇的評估

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

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

3.2.2存儲量的比較

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

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

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

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

4結(jié)束語

本文結(jié)合HDFS高擴(kuò)展性的優(yōu)點和MapReduce并行計算能力，從減少數(shù)據(jù)存儲量并提高壓縮效率的角度出發(fā)，設(shè)計了基于HDFS的壓縮數(shù)據(jù)頁行列混合存儲結(jié)構(gòu)，并提出了MR-DC數(shù)據(jù)壓縮策略，將數(shù)據(jù)壓縮存儲到設(shè)計的頁式混合存儲結(jié)構(gòu)中。從而能夠減少數(shù)據(jù)的存儲量，提高數(shù)據(jù)分析處理的性能。未來將繼續(xù)完善本文提出的數(shù)據(jù)壓縮策略，并考慮該存儲結(jié)構(gòu)上并行查詢的實現(xiàn)，以及對MapReduce 框架進(jìn)行優(yōu)化。

參考文獻(xiàn)：

[1] 孟小峰， 慈祥. 大數(shù)據(jù)管理： 概念， 技術(shù)與挑戰(zhàn)[J]. 計算機(jī)研究與發(fā)展， 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] 王振璽， 樂嘉錦， 王梅， 等. 列存儲數(shù)據(jù)區(qū)級壓縮模式與壓縮策略選擇方法[J]. 計算機(jī)學(xué)報， 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] 孫林超， 陳群， 肖玉澤， 等. 行列混合存儲數(shù)據(jù)庫系統(tǒng)的研究[J]. 計算機(jī)應(yīng)用研究， 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.