大數(shù)據(jù)存儲(chǔ)與處理-第二講5課件1

大數(shù)據(jù)的三個(gè)關(guān)鍵問(wèn)題Google的大數(shù)據(jù)技術(shù)Google的業(yè)務(wù)：PageRank三大法寶1第二講大數(shù)據(jù)的關(guān)鍵技術(shù)大數(shù)據(jù)的三個(gè)關(guān)鍵問(wèn)題1第二講大數(shù)據(jù)的關(guān)鍵技術(shù)文件存儲(chǔ)數(shù)據(jù)分析數(shù)據(jù)計(jì)算數(shù)據(jù)存儲(chǔ)平臺(tái)管理數(shù)據(jù)集成數(shù)據(jù)源Database

Web

Log…現(xiàn)代數(shù)據(jù)處理

能力組件現(xiàn)代數(shù)據(jù)處理框架

三大關(guān)鍵問(wèn)題

3V計(jì)算存儲(chǔ)｝容錯(cuò)｝｝文件存儲(chǔ)數(shù)據(jù)分析平數(shù)據(jù)集成數(shù)據(jù)源DatabaseWeb三大關(guān)鍵問(wèn)題存儲(chǔ)計(jì)算容錯(cuò)三大關(guān)鍵問(wèn)題存儲(chǔ)存儲(chǔ)問(wèn)題

解決大數(shù)據(jù)存儲(chǔ)效率的兩方面：–

容量–

吞吐量

容量–

單硬盤容量提升：MB

→

GB

→

TB

→

┈–

系統(tǒng)整體容量提升：DAS、NAS、SAN

吞吐量

=

傳輸數(shù)據(jù)量

/

傳輸時(shí)間–

單硬盤吞吐量提升：轉(zhuǎn)速、接口、緩存等–

節(jié)點(diǎn)吞吐量提升：RAID、專用數(shù)據(jù)庫(kù)機(jī)存儲(chǔ)問(wèn)題解決大數(shù)據(jù)存儲(chǔ)效率的兩方面：–容量–提升吞吐量

RAID：Redundant

Array

of

Inexpensive

Disks，冗余磁盤陣列–

把多塊獨(dú)立的硬盤按一定的方式組合起來(lái)形成一個(gè)硬盤組，從而實(shí)現(xiàn)高性能和高可靠性–

RAID0：連續(xù)以位或字節(jié)為單位分割數(shù)據(jù)，并行讀/寫(xiě)于多個(gè)磁盤上，提升吞吐量Source:

/提升吞吐量RAID：RedundantArray三大關(guān)鍵問(wèn)題存儲(chǔ)計(jì)算容錯(cuò)三大關(guān)鍵問(wèn)題存儲(chǔ)多核技術(shù)

Moor定律：當(dāng)價(jià)格不變時(shí)，集成電路上可容納的晶體管數(shù)目，約每隔18個(gè)月便會(huì)增加一倍，性能也將提升一倍。

采用多核（Multi-core）技術(shù)提升IPC，從而突破性能提升瓶頸。指令數(shù)主頻多核技術(shù)Moor定律：當(dāng)價(jià)格不變時(shí)，集成電路上可容納IPS

MF

IPC

多處理器技術(shù)

多處理器技術(shù)的核心：

按處理器之間的關(guān)系可以分為兩類：

1

F

1

F/

N

非對(duì)稱多處理器架構(gòu)（ASMP）––––不同類型計(jì)算任務(wù)或進(jìn)程由不同處理器執(zhí)行簡(jiǎn)單，操作系統(tǒng)修改小低效早期過(guò)渡性架構(gòu)對(duì)稱多處理器架構(gòu)（SMP）––––所有處理器完全對(duì)等計(jì)算任務(wù)按需分配高效普遍采用IPSMFIPC多處理器技術(shù)并行模式獨(dú)立并行–兩個(gè)數(shù)據(jù)操作間沒(méi)有數(shù)據(jù)依賴關(guān)系––可以采用獨(dú)立并行的方式分配給不同的處理器執(zhí)行例：兩個(gè)獨(dú)立數(shù)據(jù)集的Scan操作流水線并行–多個(gè)操作間存在依賴關(guān)系，且后一個(gè)操作必須等待前一個(gè)操–作處理完后方可執(zhí)行將多個(gè)操作分配給不同處理器，但處理器間以流水線方式執(zhí)行–例：Scan

→

Sort

→

Group分割并行–數(shù)據(jù)操作的輸入數(shù)據(jù)可以分解為多個(gè)子集，且子集之間相互獨(dú)立–分割為若干獨(dú)立的子操作，每個(gè)子操作只處理對(duì)應(yīng)的部分?jǐn)?shù)據(jù)，并將這些子操作配到不同的處理器上執(zhí)行–例：

Scan

→

Merge并行模式獨(dú)立并行–兩個(gè)數(shù)據(jù)操作間沒(méi)有數(shù)據(jù)依賴關(guān)系–可以采用獨(dú)并行系統(tǒng)架構(gòu)共享內(nèi)存（Shared

Memory，SM）–多個(gè)處理器，多個(gè)磁盤，一個(gè)共享內(nèi)存，通過(guò)數(shù)據(jù)總線相連–處理器間共享全部磁盤和內(nèi)存–––結(jié)構(gòu)簡(jiǎn)單，負(fù)載均衡數(shù)據(jù)總線成為瓶頸，可擴(kuò)展性較差，共享內(nèi)存單點(diǎn)故障適合處理器較少（≤8）的小規(guī)模并行數(shù)據(jù)庫(kù)共享磁盤（Shared

Disk，SD）–多個(gè)處理器，每個(gè)處理器擁有獨(dú)立內(nèi)存，多個(gè)磁盤，處理器與磁盤通過(guò)數(shù)據(jù)總線相連–––處理器間共享全部磁盤容錯(cuò)性提高共享磁盤成為性能瓶頸，需要額外維護(hù)內(nèi)存與磁盤間的數(shù)據(jù)一致性無(wú)共享（Shared

Nothing，SN）–每個(gè)處理器擁有獨(dú)立的內(nèi)存和若干磁盤，通過(guò)高速網(wǎng)絡(luò)相連–處理器獨(dú)立處理所管理的數(shù)據(jù)–––––數(shù)據(jù)傳輸量小，效率高可擴(kuò)展性強(qiáng)節(jié)點(diǎn)間交換數(shù)據(jù)開(kāi)銷較大適合處理器數(shù)量較大的大規(guī)模并行系統(tǒng)后期發(fā)展的主流并行系統(tǒng)架構(gòu)共享內(nèi)存（SharedMemory，SM）–多三大關(guān)鍵問(wèn)題存儲(chǔ)計(jì)算容錯(cuò)三大關(guān)鍵問(wèn)題存儲(chǔ)數(shù)據(jù)容錯(cuò)

RAID單節(jié)點(diǎn)數(shù)據(jù)冗余存儲(chǔ)–

RAID0：并行磁盤–

RAID1：鏡像冗余–

RAID10：RAID1+RAID0–

RAID5：校驗(yàn)冗余

Source:

/

集群多節(jié)點(diǎn)數(shù)據(jù)冗余存儲(chǔ)數(shù)據(jù)容錯(cuò)RAID單節(jié)點(diǎn)數(shù)據(jù)冗余存儲(chǔ)–RAID0計(jì)算任務(wù)容錯(cuò)

計(jì)算任務(wù)容錯(cuò)的關(guān)鍵問(wèn)題：–

故障監(jiān)測(cè)–

計(jì)算數(shù)據(jù)定位與獲取–

任務(wù)遷移計(jì)算任務(wù)容錯(cuò)計(jì)算任務(wù)容錯(cuò)的關(guān)鍵問(wèn)題：–故障監(jiān)測(cè)Google是如何解決其大數(shù)據(jù)處理的三個(gè)關(guān)鍵性問(wèn)題的?我們需要先了解Google的業(yè)務(wù)特點(diǎn)。14Google的大數(shù)據(jù)技術(shù)Google是如何解決其大數(shù)據(jù)處理的三個(gè)關(guān)鍵性問(wèn)題的?14G1995199619971999200120032005200720092011...19982000200220042006200820102012當(dāng)佩奇遇見(jiàn)

布林

合作開(kāi)發(fā)BackRub

搜索引擎

命名Google

Google公司成立首名專用廚師入職建立10億網(wǎng)址的索

引圖片搜索+30億網(wǎng)

址索引商品+新聞+API

開(kāi)始收購(gòu)+Google

圖書(shū)

80億網(wǎng)址索引+上市+學(xué)術(shù)搜索

地圖+Talk+

分析YouTube+Google

Apps

Gmail+

街景+AndroidHealth+

iPhone

應(yīng)用

社交網(wǎng)絡(luò)搜索+實(shí)時(shí)

地圖導(dǎo)航+

搜索

收購(gòu)Moto手機(jī)+投

平板電腦資能源+

+Google應(yīng)用商店

眼鏡Google

Google最重要的業(yè)務(wù)？

搜索

AdWords

Google發(fā)展史199519961997199920012003200520Google之前的搜索

目錄型搜索：Yahoo!–

收集：人工分類–

索引：主題–

使用：目錄結(jié)構(gòu)–

優(yōu)點(diǎn)：準(zhǔn)確率高–

缺點(diǎn)：覆蓋率低

索引型搜索：AltaVista–

收集：自動(dòng)爬取（Scooter）–

索引：自動(dòng)標(biāo)記–

使用：輸入關(guān)鍵詞搜索–

優(yōu)點(diǎn)：覆蓋率高–

缺點(diǎn)：準(zhǔn)確率低

覆蓋率

VS.

準(zhǔn)確率：魚(yú)與熊掌不可兼得？Google之前的搜索目錄型搜索：Yahoo!–GoogleGoogle

Google的自我揭秘！

核心算法

–

Lawrence

Page,

Sergey

Brin,

et.

al.,

The

PageRank

Citation

Ranking:

Bringing

Order

to

the

Web.

Technical

Report,

Stanford

InfoLab,

1999.

(6881)

三大法寶

–

Sanjay

Ghemawat,

Howard

Gobioff,

et.

al.,

The

Google

file

system,

Proceedings

of

the

Nineteenth

ACM

Symposium

on

Operating

Systems

Principles,

2003.

(3911)

–

Jeffrey

Dean,

Sanjay

Ghemawat,

MapReduce:

Simplified

Data

Processing

on

Large

Clusters

,

Sixth

Symposium

on

Operating

System

Design

and

Implementation,

2004.

(9569)

–

Fay

Chang,

Jeffrey

Dean,

et.

al.,

Bigtable:

A

Distributed

Storage

System

for

Structured

Data,

Seventh

Symposium

on

Operating

System

Design

and

Implementation,

2006.

(2558)靈魂血肉 Google的自我揭秘！靈血大數(shù)據(jù)存儲(chǔ)與處理-第二講5課件1

搜索結(jié)果如何排序！搜索結(jié)果如何排序！大數(shù)據(jù)存儲(chǔ)與處理-第二講5課件1

佩奇（Page），斯坦福–

整個(gè)互聯(lián)網(wǎng)就像一張大的圖，每個(gè)網(wǎng)站就像一個(gè)節(jié)點(diǎn)，

每個(gè)網(wǎng)頁(yè)的鏈接就像一個(gè)弧。我想，互聯(lián)網(wǎng)可以用一個(gè)

圖或者矩陣描述，我也許可以用這個(gè)發(fā)現(xiàn)做篇博士論文。佩奇（Page），斯坦福–整個(gè)互聯(lián)網(wǎng)就像一張大的圖，每

算法的圖論表述算法的圖論表述

01/2

01/2

0

0

01/2

01/200010000011/31/31/3

0

0n1n2n3

n4

n5 0 0001/3n1n2n3n4n5PageRank（9）–

算法的計(jì)算問(wèn)題如何計(jì)算10億、100億個(gè)網(wǎng)頁(yè)？行列數(shù)以億為單位的矩陣相乘！PageRank（9）–算法的計(jì)算問(wèn)題如何計(jì)算10億、10Google三大法寶之一：MapReduceGoogle三大法寶之一：MapReduce矩陣乘法串行實(shí)現(xiàn)

1:

for

i=1;i<=N;i++2:for

j=1;j<=N;j++3:4:5:6:

for

k=1;k<=N;k++

C[i][j]

+=

A[i][k]*B[k][j]

end

forend

for

7:

end

for

算法復(fù)雜度：O(N3)

以1次乘法需要1個(gè)時(shí)鐘周期，計(jì)算10億維度矩陣為

例，使用1G的CPU，需要的計(jì)算時(shí)間為：

t

=

10億×10億×10億

/

10億

=

317年！是否OK？矩陣乘法串行實(shí)現(xiàn)2:forj=1;j<=N;j++3: f想辦法解決大規(guī)模矩陣相乘問(wèn)題：我拆

Cm

=

Am

ⅹ

B

M臺(tái)服務(wù)器并行計(jì)算，時(shí)間降低為1/MCABC1CmCMA1AmAM=ⅹ想辦法解決大規(guī)模矩陣相乘問(wèn)題：我拆Cm=AmⅹB想辦法解決大規(guī)模矩陣相乘問(wèn)題：我再拆

Cm,n

=

Am

ⅹ

Bn

M

ⅹM臺(tái)服務(wù)器并行計(jì)算，時(shí)間降低為1/M2

CABA1AmAM=ⅹC1,1Cm,1CM,1B1BnBM想辦法解決大規(guī)模矩陣相乘問(wèn)題：我再拆Cm,n=Am子任務(wù)子任務(wù)子任務(wù)…拆的本質(zhì)－

分而治之

分而治之

–

Divide

and

Conquer

–

一個(gè)大的計(jì)算任務(wù)分解為若干小計(jì)算任務(wù)

–

子任務(wù)計(jì)算結(jié)果合并后獲得最終結(jié)果

計(jì)算任務(wù)

DivideConquer

計(jì)算結(jié)果子任務(wù)子任務(wù)子任務(wù)…拆的本質(zhì)－分而治之ConquerMapReduce的來(lái)源

編程模型：–

1956年John

McCarthy（圖靈獎(jiǎng)獲得者）提出的Lisp語(yǔ)言中的Map/Reduce方法–

Map輸入是一個(gè)函數(shù)和n個(gè)列表，輸出是一個(gè)新的列表，列表中的元素是將輸入函數(shù)作用在n個(gè)輸入列表中每個(gè)對(duì)應(yīng)元素獲得的計(jì)算結(jié)果。–

Reduce輸入是一個(gè)函數(shù)和一個(gè)列表，輸出是將函數(shù)依次作用于列表的每個(gè)元素后獲得的計(jì)算結(jié)果(map

'vector

#*

#(1

2

3

4

5)

#(5

4

3

2

1)

->

#(5

8

9

8

5)(reduce

#'+

#(5

8

9

8

5))

->

35Lisp中的Map和Reduce操作MapReduce的來(lái)源編程模型：–1956年JoMapReduce原理Source：sun.fim.uni-passau.de/cl/MapReduceFoundation/MapReduce原理Source：http://www.iMapReduce機(jī)制

主控程序（Master）：將Map和Reduce分配到合適的工作機(jī)上

工作機(jī)（Worker）：執(zhí)行Map或Reduce任務(wù)MapReduce機(jī)制主控程序（Master）：將MMapReduce不僅僅是編程模型!

讓程序員在使用MapReduce時(shí)面對(duì)以下細(xì)節(jié)問(wèn)題？–

大數(shù)據(jù)如何分割為小數(shù)據(jù)塊？–

如何調(diào)度計(jì)算任務(wù)并分配和調(diào)度map和reduce任務(wù)節(jié)點(diǎn)？–

如何在任務(wù)節(jié)點(diǎn)間交換數(shù)據(jù)？–

如何同步任務(wù)？–

相互依賴的任務(wù)是否執(zhí)行完成？–

任務(wù)節(jié)點(diǎn)失效時(shí)該如何處理？

Google的MapReduce是一個(gè)完整的計(jì)算框架–

程序員只需要編寫(xiě)少量的程序?qū)崿F(xiàn)應(yīng)用層邏輯MapReduce不僅僅是編程模型!讓程序員在使用Map程序示例：WordCount#include

"mapreduce/mapreduce.h"class

WordCounter

:

public

Mapper

{

public:

virtual

void

Map(const

MapInput&

input)

{

const

string&

text

=

input.value();

const

int

n

=

text.size();

for

(int

i

=

0;

i

<

n;

)

{

while

((i

<

n)

&&

isspace(text[i]))

i++;

int

start

=

i;

while

((i

<

n)

&&

!isspace(text[i]))

i++;

if

(start

<

i)

Emit(text.substr(start,i-start),"1");

}}};REGISTER_MAPPER(WordCounter);class

Adder

:

public

Reducer

{

virtual

void

Reduce(ReduceInput*

input)

{

int64

value

=

0;

while

(!input->done())

{

value

+=

StringToInt(input->value());

input->NextValue();

}

Emit(IntToString(value));

}};REGISTER_REDUCER(Adder);int

main(int

argc,

char**

argv)

{

ParseCommandLineFlags(argc,

argv);

MapReduceSpecification

spec;

for

(int

i

=

1;

i

<

argc;

i++)

{

MapReduceInput*

input

=

spec.add_input();

input->set_format("text");

input->set_filepattern(argv[i]);

input->set_mapper_class("WordCounter");

}

MapReduceOutput*

out

=

spec.output();

out->set_filebase("/gfs/test/freq");

out->set_num_tasks(100);

out->set_format("text");out->set_reducer_class("Adder");out->set_combiner_class("Adder");spec.set_machines(2000);spec.set_map_megabytes(100);spec.set_reduce_megabytes(100);MapReduceResult

result;if

(!MapReduce(spec,

&result))

abort();return

0;}程序示例：WordCount#include"mapredGoogle三大法寶之二：GFSGoogle三大法寶之二：GFSGFS簡(jiǎn)介

GFS

–

Google

File

System，Google自有的分布式文件系統(tǒng)

為什么需要GFS？–

已有多種分布式文件系統(tǒng)（NFS、AFS、DFS、…）–

Google特有的環(huán)境與負(fù)載需要GFS簡(jiǎn)介GFS–GoogleFileSysteGoogle特有的數(shù)據(jù)和計(jì)算

Google處理的主要數(shù)據(jù)–

爬取的網(wǎng)頁(yè)–

網(wǎng)站訪問(wèn)日志–

其他相對(duì)獨(dú)立的數(shù)據(jù)

數(shù)據(jù)計(jì)算的期望結(jié)果–

詞頻統(tǒng)計(jì)–

倒排索引–

網(wǎng)頁(yè)文檔的鏈接圖–

網(wǎng)站頁(yè)面數(shù)量統(tǒng)計(jì)

特點(diǎn)–

單個(gè)計(jì)算簡(jiǎn)單–

數(shù)量龐大–

數(shù)據(jù)相對(duì)獨(dú)立Google特有的數(shù)據(jù)和計(jì)算Google處理的主要數(shù)GFS支持大容量

用集群方式提升系統(tǒng)整體容量Google的第一臺(tái)服務(wù)器（1998）Intel

CPU

+

IDE硬盤xGFS支持大容量用集群方式提升系統(tǒng)整體容量GooglGFS支持高吞吐量

Google處理的數(shù)據(jù)特點(diǎn)

–

抓取網(wǎng)頁(yè)并存儲(chǔ)：順序?qū)懭?，極少發(fā)生隨機(jī)寫(xiě)的情況

–

分析網(wǎng)頁(yè)內(nèi)容：文件寫(xiě)入后，只會(huì)發(fā)生讀的操作，不會(huì)再修改

GFS實(shí)現(xiàn)高吞吐量的兩個(gè)關(guān)鍵點(diǎn)：

①

順序?qū)懭耄樞蜃x取，避免隨機(jī)讀寫(xiě)文件傳輸效率公式

SEEK

_TIMEblock

_

size/SPEED

SEEK

_TIME1

trans_timetrans_time

SEEK

_TIMEeffect

西數(shù)

80G

SATA硬盤

隨機(jī)讀55

8.2②

數(shù)據(jù)以遠(yuǎn)大于操作系統(tǒng)文件塊的基本單元進(jìn)行存儲(chǔ)（64MB

vs.

512B）GFS支持高吞吐量文件傳輸效率公式 SEEK_TIME1GFS支持容錯(cuò)

問(wèn)題：大量廉價(jià)PC組件構(gòu)成的集群作為硬件基礎(chǔ)，單節(jié)點(diǎn)故障率較高Google的第一臺(tái)服務(wù)器（1998）

Intel

CPU

+

IDE硬盤集群多節(jié)點(diǎn)數(shù)據(jù)冗余存儲(chǔ)GFS支持容錯(cuò)Google的第一臺(tái)服務(wù)器（1998）集群多節(jié)GFS系統(tǒng)架構(gòu)客戶端（Client）GFS提供給上層應(yīng)用使用的一組接口庫(kù)上層應(yīng)用通過(guò)調(diào)用接口庫(kù)中的接口實(shí)現(xiàn)GFS系統(tǒng)中的文件管理適合自身應(yīng)用的簡(jiǎn)單接口主控節(jié)點(diǎn)（Master）管理節(jié)點(diǎn)唯一性保存元數(shù)據(jù)調(diào)配塊服務(wù)器塊服務(wù)器（Chunk

Server）存儲(chǔ)數(shù)據(jù)塊（Chunk）多個(gè)固定塊大?。J(rèn)64MB）數(shù)據(jù)庫(kù)多節(jié)點(diǎn)冗余備份討論：分析一下，GFS的文件讀寫(xiě)流程大致應(yīng)該是怎么樣的？GFS系統(tǒng)架構(gòu)客戶端（Client）GFS提供給上層應(yīng)用使①②③④⑤計(jì)算索引：客戶端將應(yīng)用提供的文件名和字節(jié)偏移通過(guò)固定文件塊大小進(jìn)行計(jì)算后獲得塊索引傳遞索引：客戶端將文件名稱和塊索引發(fā)送給主控節(jié)點(diǎn)返回位置：主控節(jié)點(diǎn)將用于訪問(wèn)文件塊的塊句柄和文件塊所在的塊服務(wù)器位置返回給客戶端訪問(wèn)數(shù)據(jù)：客戶端將位置信息進(jìn)行緩存，并訪問(wèn)離自己距離最近的塊服務(wù)器返回?cái)?shù)據(jù)：被訪問(wèn)的塊服務(wù)器將數(shù)據(jù)返回給客戶端GFS讀數(shù)據(jù)流程

②

①

③

④

⑤①計(jì)算索引：客戶端將應(yīng)用提供的文件名和字節(jié)偏移通過(guò)固定文件塊Google三大法寶之三：BigTableGoogle三大法寶之三：BigTable簡(jiǎn)單搜索框背后的復(fù)雜工作1.

Crawler從URL服務(wù)器提取地址進(jìn)行遍歷查找2.

獲取文檔docs

,建立文檔docIDs

,進(jìn)行分析、壓縮3.

存儲(chǔ)到文檔數(shù)據(jù)庫(kù)4.

索引器為docs建立順排索引和倒排索引5.

索引數(shù)據(jù)存儲(chǔ)到集群中建立索引響應(yīng)請(qǐng)求.5.對(duì)請(qǐng)求進(jìn)行預(yù)處理，包括拼寫(xiě)檢查、附加廣告等GWS向索引服務(wù)器發(fā)送查詢關(guān)鍵字索引服務(wù)器根據(jù)關(guān)鍵字查找匹配文檔并向GWS返回docIDsGWS將docIDs傳給文檔服務(wù)器，獲得文檔GWS將查詢結(jié)果文檔以HTML形式返回給用戶簡(jiǎn)單搜索框背后的復(fù)雜工作1.Crawler從URL服務(wù)為什么需要BigTable？

GFS的局限性：文件系統(tǒng)，不適合結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)和訪問(wèn)

結(jié)構(gòu)化數(shù)據(jù)？使用DB2、SQLServer、MySQL之類的數(shù)據(jù)庫(kù)系統(tǒng)？

非也！因?yàn)椋酣C

存儲(chǔ)數(shù)據(jù)的多樣性與復(fù)雜性：

URL、網(wǎng)頁(yè)內(nèi)容、用戶數(shù)據(jù)等–

海量的處理請(qǐng)求–

成本與控制力

BigTable的目標(biāo)：–

適應(yīng)各種不同類型的數(shù)據(jù)和應(yīng)用–

隨時(shí)增加和減少處理節(jié)點(diǎn)的可擴(kuò)展性和自動(dòng)平衡能力–

PB級(jí)數(shù)據(jù)環(huán)境下的高吞吐量和高并發(fā)（百萬(wàn)級(jí)TPS）–

連續(xù)服務(wù)的高可用性和容錯(cuò)