Hadoop開(kāi)源軟件與云計(jì)算

中科f陰苴用

Hadoop開(kāi)源軟件與云計(jì)算

查禮(char@)

中科院計(jì)算所

2010.10.11

內(nèi)容提要

?大規(guī)模數(shù)據(jù)處理研究背景

會(huì)大規(guī)模數(shù)據(jù)處理開(kāi)源軟件Hadoop

會(huì)分布式數(shù)據(jù)存儲(chǔ)計(jì)算相關(guān)研究@ICT

內(nèi)容提要

?大規(guī)模數(shù)據(jù)處理研究背景

0大規(guī)模數(shù)據(jù)處理開(kāi)源軟件Hadoop

分布式數(shù)據(jù)存儲(chǔ)計(jì)算相關(guān)研究@ICT

研究背景

?云計(jì)算的外延主要是大規(guī)模數(shù)據(jù)處理和基礎(chǔ)設(shè)施彈性管理及租約式供

應(yīng)

?通信、網(wǎng)絡(luò)、存儲(chǔ)、傳感器等電子信息技術(shù)飛速發(fā)展導(dǎo)致數(shù)據(jù)規(guī)模極

大增加

?:?傳統(tǒng)的存儲(chǔ)并處理這些數(shù)據(jù)的技術(shù)手段遇到瓶頸

Processing100TBdatasets

OnenodeScanning?50MB/s=35,000min

1000nodeScanning?50MB/s=35min

D*?yP""Ac<M(

SearchEngineDataWarehousingLogProcessing

MapReduce并行編程模型

?E.g.,IO10Internetwebpages

5Reduce對(duì)處理結(jié)果進(jìn)行聚集

■系統(tǒng)處理資源分配和可靠性問(wèn)題

■Map:對(duì)所有單詞產(chǎn)生（word,count〉對(duì)

■Reduce:累計(jì)單詞數(shù)

WhyMapReduce?

?:?簡(jiǎn)單VS.復(fù)雜

■并行計(jì)算模式簡(jiǎn)單，編程容易。與MPI、

OpenMP相比門檻低

■為用戶屏蔽數(shù)據(jù)通信、并發(fā)、同步、一致性等

問(wèn)題

?:?專用VS.通用

■適用于大規(guī)模數(shù)據(jù)處理，如搜索引擎、用戶日

志分析等

■計(jì)算與存儲(chǔ)方式緊密結(jié)合

■利于提高系統(tǒng)擴(kuò)展性名

GFS-Google分布式文件系統(tǒng)

?:?特點(diǎn)

■GFS中所存儲(chǔ)的文件通常較大（GB級(jí)），采用

64MB數(shù)據(jù)塊作為基本存儲(chǔ)單元；

■Google業(yè)務(wù)邏輯特點(diǎn)決定了GFS中的文件讀多

寫少，寫主要是追加操作，基本不存在隨機(jī)寫

操作；

■GFS的負(fù)載主要是對(duì)大文件的流式處理，客戶

端緩存無(wú)意義；

-64MB數(shù)據(jù)塊降低了元數(shù)據(jù)的數(shù)量，因此系統(tǒng)

可使用單元數(shù)據(jù)服務(wù)器結(jié)構(gòu)。.

SanjayGhemawat,et.al.,TheGoogle

FileSystem,SOSP'03

內(nèi)容提要

?大規(guī)模數(shù)據(jù)處理研究背景

大規(guī)模數(shù)據(jù)處理開(kāi)源軟件Hadoop

分布式數(shù)據(jù)存儲(chǔ)計(jì)算相關(guān)研究@ICT

Hadoop系統(tǒng)

?ApacheNutch,2002

?NDFS+MapReduce,2004

?Hadoop,2006

?ApacheHadoop,200過(guò)**I哂）

■/

■Book:

http:〃ore/catalog/9780596521998/index.html

>WritteninJava>Runson

?DoesworkwithotherLinux,Windowsandmore

languagesCommodityhardwarewithhighfailure

rate

Hadooo組成部分

OIJHDFS4HadoopDistrbutionFileSystem

expressingdataanalysisprograms

。MapReduce

0PigProject

Ahigh-leveldata-flowlanguageforparallelcomputation

pMhiaxncvtiMn

ZooKeepetAhigh-performancecoordinationservice

；Goo9WCtahby/x*MAC*

a*Avrodataserializationsystem

Protocol

，0chukwadatacollectionsystem

；;HBasestructureddatastorage

datawarehouse

HiveQL

HDFS設(shè)計(jì)目標(biāo)

?VeryLargeDistributedFileSystem

■lOKnodes,100millionfiles,10PB

?ConvenientClusterManagement

■Loadbalancing

■Nodefailures

■Clusterexpansion

?OptimizedforBatchProcessing

■Allowmovecomputationtodata

■Maximizethroughput

HDFS體系結(jié)構(gòu)

HadoopMapReduce處理流程二TE…""

內(nèi)容提要

?大規(guī)模數(shù)據(jù)處理研究背景

0大規(guī)模數(shù)據(jù)處理開(kāi)源軟件Hadoop

分布式數(shù)據(jù)存儲(chǔ)計(jì)算相關(guān)研究@ICT

數(shù)據(jù)計(jì)算相關(guān)研究@ICT

?:?軟件系統(tǒng)

?大規(guī)模數(shù)據(jù)處理系統(tǒng)（VegaCloudDCP）

?:?關(guān)鍵技術(shù)

■列存儲(chǔ)數(shù)據(jù)管理技術(shù)（RCFile）

■DOT聚簇式互補(bǔ)索引（CCIndex）

■HDFSNameNode高可用增強(qiáng)

■資源感知MapReduce任務(wù)調(diào)度

■小文件存儲(chǔ)優(yōu)化

VDCP大規(guī)模數(shù)據(jù)處理系統(tǒng)構(gòu)成

應(yīng)用戶行為數(shù)據(jù)挖掘計(jì)算機(jī)科學(xué)文獻(xiàn)共享系統(tǒng)

其他應(yīng)用

用（離線處理類）（存儲(chǔ)?在線處理類）

.

大并行連接優(yōu)化聚簇式互補(bǔ)索弓1

川E

規(guī)IVHBase

列存儲(chǔ)數(shù)據(jù)管數(shù)據(jù)在線恢復(fù)

模

數(shù)

Hadoop

據(jù)

處I

Resource-aware

IMapReduceJobTrackerTaskTracker

理動(dòng)態(tài)任務(wù)調(diào)度器

平

臺(tái)

HDFSNameNodeDataNode小文件存儲(chǔ)優(yōu)化

高而用增強(qiáng)

列存儲(chǔ)數(shù)據(jù)管理-RCFile

?將分布式數(shù)據(jù)處理系統(tǒng)中以記錄為單位的存儲(chǔ)結(jié)構(gòu)變?yōu)橐粤袨閱挝?/p>

的存儲(chǔ)結(jié)構(gòu)，進(jìn)而減少磁盤訪問(wèn)數(shù)量，提高查詢處理性能。

?由于相同屬性值具有相同數(shù)據(jù)類型和相近的數(shù)據(jù)特性，以屬性值為

單位進(jìn)行壓縮存儲(chǔ)的壓縮比更高，能節(jié)省更多的存儲(chǔ)空間。

Relation

RCFile

WBytesRecordRelation

SyncNumberA|B[C|D

HDFSBlockRowGroup

CompressedCompressedHDFS

KeysLengthsKeysData

StoreBlock110111112113116BytesMeradara

102112122132SyncHeader

RowGroup1

CompressedValuesLengths103113123133

StoreBlock2104114124134匚F1二41C3.1；：1"、

105115105135111,112,113,114.115

CompressedValuesDataRowGroup2

StoreBlock3121,122,123,124125

121,131)131,132,133,134.135

(102,112,122,132)

II

(105,115.125,135)RowGroupn

列存儲(chǔ)-RCFile

①分布式文件系統(tǒng)中高效的列數(shù)據(jù)組織方式

SequenceFile：關(guān)系數(shù)據(jù)水平拆分為塊，塊內(nèi)按行序存儲(chǔ)

?RCFile：關(guān)系數(shù)據(jù)水平拆分，分片內(nèi)按列序存儲(chǔ)（已應(yīng)用于Facebook

Inc.）

②提供與Hadoop框架兼容的列存儲(chǔ)文件訪問(wèn)接口，支持

Hadoop程序?qū)α写鎯?chǔ)文件中關(guān)系數(shù)據(jù)的透明訪問(wèn)。

③支持列數(shù)據(jù)獨(dú)立壓縮機(jī)制，在不影響列數(shù)據(jù)獨(dú)立訪問(wèn)的

前提下降低存儲(chǔ)空間消耗。

?RLE：行程長(zhǎng)度編碼

?BitMap：位圖編碼

?Zlib,Gzip等：通用壓縮方法

RCFile在Hive體系結(jié)構(gòu)中的位置

J，,

Application/EndUser

WebUI+HiveCLI+MapReduceHDFS

JDBC/ODBCUser-defined

Browse,Query,DDLMap-reduceScripts

MetaStoreUDF/UDAF

substr

sum

ThriftAPIaverage

FileFormats

SerDe

□TextFile

CSVSequenceFile

ThriftC***RCFile^2>

Regex

Reference:ZhengShao@HadoopinChma2009

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

數(shù)據(jù)表存儲(chǔ)空間比較:

儲(chǔ)格式原始文件大小壓縮行存儲(chǔ)文件大RCFILE壓RCFILE文

數(shù)康、小縮文件大小件長(zhǎng)度同

M5.49X

uri_infor10.11MB2.13MB1.8MB/

user_login_data68.71MB21.03MB20.28MB/3.57%1

16.48%I

url_access_data219.44MB69.59MB58.12MBI

30.7%/

lineitem724.66MB227.07MB157.29MB\

注：RCFILE文件長(zhǎng)度同比減小二（RCFILE壓縮文件大小-壓縮行存

儲(chǔ)文件大?。?壓縮行存儲(chǔ)文件大小

RCFile查詢性能對(duì)比

?：?在Hive中測(cè)試RCFile的性能

測(cè)試環(huán)境

節(jié)點(diǎn)操作系統(tǒng)：LinuxCentOSrelease5.3

■CPU：4核AuthenticAMD1.8GHz

內(nèi)存：5GB

?:?測(cè)試查詢

selectl_returnflag,l_linestatus,sum(l_quantity)assum_qty,sum(l_extendedprice)as

sum_base_price,sum(l_extendedprice*(1-l_discount))assum_disc_price,sum(l_extendedprice*

(1-l_discount)*(1+l_tax))assum_chargefromlineitemwherel_shipdate<='1998-12-01'group

byl_returnflag,l_linestatus;

?:?測(cè)試結(jié)果

單位：秒

節(jié)點(diǎn)也模4nodes7nodes

、、、存儲(chǔ)方式

RCFile性靛RCFile性能提RCFile性能RCFile崢提

提高（對(duì)比高（對(duì)比行存提高（對(duì)比高（對(duì)比行存

行存儲(chǔ)行存儲(chǔ)壓縮RCFile壓縮行存儲(chǔ)）儲(chǔ)壓寫、行存儲(chǔ)行存儲(chǔ)壓縮RCFile壓縮行存儲(chǔ)）儲(chǔ)壓縮）

5GB971797.1185.0612%63.4365.2961.024%

10GB16771172.53153.229%I11%\96.2397.5688.978%I9%

112%

15GB240.56243.19214.5211%|130.59140.10121.817%113%|

100GB1561791574.941370.3012%\13%j797.86785.73670.3416%V5%/

加速性能：5GB28%/10GB42%/15GB43%/100GB51%

互補(bǔ)式聚簇索引（CQndex）

?研究動(dòng)機(jī)

-多種的資源發(fā)現(xiàn)請(qǐng)求是多維區(qū)間查詢ComplementaryClusteringIndex

?網(wǎng)絡(luò)應(yīng)用中多維區(qū)間查詢是普遍需求

-不斷增大的數(shù)據(jù)量提出了挑戰(zhàn)：性能、存儲(chǔ)開(kāi)銷、可靠性

?應(yīng)用需要什么樣的數(shù)據(jù)模型？

/數(shù)據(jù)模型介于

實(shí)現(xiàn)復(fù)雜性增加M

R：模型

數(shù)據(jù)邏輯OrderedTable

關(guān)聯(lián)強(qiáng)度?和關(guān)系模型之間

-

多列多表，關(guān)系模型-/思路：增強(qiáng)高可擴(kuò)

但表間有關(guān)系（關(guān)系數(shù)據(jù)庫(kù)）-

&展性、高性能、高可

K

w

s靠性的分布式順序表

多列多表，

fc

但表間無(wú)關(guān)系商（DistribuedOrdered

定

-以支持

-Table,DOT）

-

-多維區(qū)間查詢__

單列單表-^CCIndexW^^T^S

的索引百匚矗

基于主鍵的多維通用關(guān)系O：

區(qū)間查詢區(qū)間查詢查詢數(shù)據(jù)查詢能力

基于HBase實(shí)現(xiàn)CCIndex

?把用于備份數(shù)據(jù)的副本組織成為多份互為補(bǔ)

充和校驗(yàn)的互補(bǔ)聚簇索引表，利用索引表上

高效的連續(xù)掃描代替原表上的隨機(jī)讀取。

多屬性區(qū)間查詢、?基于分布式順序表的分片信息對(duì)子查詢結(jié)果

查詢優(yōu)化、記錄查詢優(yōu)化集的大小進(jìn)行估算，最后挑選最小子查詢執(zhí)

級(jí)數(shù)據(jù)恢復(fù)行查詢過(guò)程。

?通過(guò)互補(bǔ)聚簇索引表和互補(bǔ)校驗(yàn)表進(jìn)行數(shù)據(jù)

數(shù)據(jù)恢復(fù)恢復(fù)，保證可恢復(fù)性同時(shí)僅少量增加存儲(chǔ)開(kāi)

CCIndex銷。

CQndex數(shù)據(jù)組織

基于ApacheHBase

CC1T2,key2=idx2+id+idx2Length

ComplementalClusteringIndexTable(CC1T0)

-禁用底層HDFS的副key2idxlinfo

ididxlidx2info

本機(jī)制nl00102cpuinfol

001cpunlinfol

nlOO2O2meminfo2

-互補(bǔ)聚簇表和互補(bǔ)檢002memnlinfo2

n200402cpu1nfo4

查表用HBase存儲(chǔ)003netn3info3

n3OO3O2netinfo3

-數(shù)據(jù)物理分布004cpun2info4

多張互補(bǔ)聚簇索引表1dx2key2idxl

CCIT

-分別以某索引列全局CCIT1,key1=idx1+id+idx1Length

有序keyl1dx2infoCCT2,

ComplementalCheckTable,CCTO,replicated

-其主鍵為索引列的值replicatedcpu00103nlinfol

+原主鍵+索引列的值cpu00403n2info4

的長(zhǎng)度memOO2O3nlinfo2

netOO3O3n3info3

-隨機(jī)變連續(xù)

keylIidx2

Primarykey

互補(bǔ)校驗(yàn)表CCTCCTl,

replicatedindexcolumn

-存儲(chǔ)主鍵和索引列的

IIdata卜

對(duì)應(yīng)關(guān)系

查詢優(yōu)化與數(shù)據(jù)恢復(fù)

region1startkey=>2endregion1startkey=>0end

key=>3key=>3

通過(guò)CCT校驗(yàn)數(shù)據(jù)，并從其它表中

region2startkey=>3endregion2startkey=>3end

key=>5key=>8獲取數(shù)據(jù)，修補(bǔ)缺失。

CC1T2,key2=idx2+id+idx2Length

ConiplenientalClusteringIndexTable(CCITO)

key2info

region60startkey=>90idinfow

region60startkey=>852nl00102infol

endkey=>93endkey=>91001infol

*nlOO2O2info2

002info2

n200402info4

region61startkey=>93region61startkey=>91003info3w

n300302

endkey=>100endkey=>100004info4info3

metadataoftableindexedbymetadataoftableindexedbyIkey2

id

CPULoadmemoryusagekey2

id9

data

找到內(nèi)存占用較高但CPU較空閑的Server

query:select,where(CPULoad<50andmemoryusage>98)74CCIT1,keyl=idxI+id-idxILength

7

keylinfoCCT2,

c(mplementalCheckTable.CCTO,replicated

個(gè)個(gè)2

40region1regionreplicatedcpu00103infol

I\掃描按內(nèi)存占用率索引表,并用CPULoad篩cpu00403info4

?LZ選結(jié)果LostdatairrFn?

netOO3O3info3

\|keyl

RyercheckCCT||Primarykey

keyl44^CCTl,

通過(guò)分片信息預(yù)估掃描范圍，優(yōu)化data

7re)licatedIndexcolumn

查詢執(zhí)行速度。mem00203*||data

<>

CCIndex應(yīng)用效果

■環(huán)境：3節(jié)點(diǎn)

-雙CPU共4核，2.0

GHzAMDOpteron,6

(

SGB內(nèi)存，186GB

VP5

」

。RAID1SCSI磁盤，千

①。

M

)兆以太網(wǎng)

?負(fù)載

-100萬(wàn)隨機(jī)生成數(shù)據(jù)，

長(zhǎng)度1K字節(jié)，

-主鍵+3個(gè)索引列

■測(cè)試內(nèi)容

?CCIndex的索引掃描操作吞吐率是隨機(jī)讀寫，連續(xù)讀寫,

IndexedTable的11.4倍掃描原表，掃描索引

?CCIndex的隨機(jī)寫和順序?qū)懲掏侣史謩e比

IndexedTable快54.9%和121.4%

注：IndexedTable是HBase中的二級(jí)索引實(shí)現(xiàn)

CCIndex應(yīng)用效果

?CCIndex與

IndexedTable相比:

-索引列數(shù)N,取

值從2到4_

—IndexTable的副

本數(shù)，取值為

N+1（估計(jì)值）

-記錄長(zhǎng)度蟒5/四

長(zhǎng),取值從10到30

?CCIndex存儲(chǔ)開(kāi)銷相

CCIndex應(yīng)用效果