大數(shù)據(jù)存儲與處理第二講課件

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

Web

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

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

三大關(guān)鍵問題

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

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

容量–

吞吐量

容量–

單硬盤容量提升：MB

→

GB

→

TB

→

┈–

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

吞吐量

=

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

/

傳輸時(shí)間–

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

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

RAID：Redundant

Array

of

Inexpensive

Disks，冗余磁盤陣列–

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

RAID0：連續(xù)以位或字節(jié)為單位分割數(shù)據(jù)，并行讀/寫于多個(gè)磁盤上，提升吞吐量提升吞吐量RAID：RedundantArray三大關(guān)鍵問題存儲計(jì)算容錯(cuò)三大關(guān)鍵問題存儲多核技術(shù)

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

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

MF

IPC

多處理器技術(shù)

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

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

1

F

1

F/

N

非對稱多處理器架構(gòu)（ASMP）––––不同類型計(jì)算任務(wù)或進(jìn)程由不同處理器執(zhí)行簡單，操作系統(tǒng)修改小低效早期過渡性架構(gòu)對稱多處理器架構(gòu)（SMP）––––所有處理器完全對等計(jì)算任務(wù)按需分配高效普遍采用IPSMFIPC多處理器技術(shù)并行模式獨(dú)立并行–兩個(gè)數(shù)據(jù)操作間沒有數(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è)子操作只處理對應(yīng)的部分?jǐn)?shù)據(jù)，并將這些子操作配到不同的處理器上執(zhí)行–例：

Scan

→

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

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

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

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

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

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

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

故障監(jiān)測–

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

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

布林

合作開發(fā)BackRub

搜索引擎

命名Google

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

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

址索引商品+新聞+API

開始收購+Google

圖書

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

地圖+Talk+

分析YouTube+Google

Apps

Gmail+

街景+AndroidHealth+

iPhone

應(yīng)用

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

地圖導(dǎo)航+

搜索

收購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)爬?。⊿cooter）–

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

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

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

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

覆蓋率

VS.

準(zhǔn)確率：魚與熊掌不可兼得？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ù)存儲與處理第二講課件

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

佩奇（Page），斯坦福–

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

每個(gè)網(wǎng)頁的鏈接就像一個(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ì)算問題如何計(jì)算10億、100億個(gè)網(wǎng)頁？行列數(shù)以億為單位的矩陣相乘！PageRank（9）–算法的計(jì)算問題如何計(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ī)模矩陣相乘問題：我拆

Cm

=

Am

ⅹ

B

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

Cm,n

=

Am

ⅹ

Bn

M

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

CABA1AmAM=ⅹC1,1Cm,1CM,1B1BnBM想辦法解決大規(guī)模矩陣相乘問題：我再拆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的來源

編程模型：–

1956年John

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

Map輸入是一個(gè)函數(shù)和n個(gè)列表，輸出是一個(gè)新的列表，列表中的元素是將輸入函數(shù)作用在n個(gè)輸入列表中每個(gè)對應(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的來源編程模型：–1956年JoMapReduce原理MapReduce原理MapReduce機(jī)制

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

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

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

大數(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ì)算框架–

程序員只需要編寫少量的程序?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簡介

GFS

–

Google

File

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

為什么需要GFS？–

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

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

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

爬取的網(wǎng)頁–

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

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

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

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

倒排索引–

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

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

特點(diǎn)–

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

數(shù)量龐大–

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

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

CPU

+

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

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

–

抓取網(wǎng)頁并存儲：順序?qū)懭耄瑯O少發(fā)生隨機(jī)寫的情況

–

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

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

①

順序?qū)懭?，順序讀取，避免隨機(jī)讀寫文件傳輸效率公式

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)行存儲（64MB

vs.

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

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

Intel

CPU

+

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

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

②

①

③

④

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

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

獲取文檔docs

,建立文檔docIDs

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

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

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

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

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

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

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

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

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

海量的處理請求–

成本與控制力

BigTable的目標(biāo)：–

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

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

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

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

架構(gòu)與使用的簡潔性為什么需要BigTable？GFS的局限性：文件系統(tǒng)BigTable數(shù)據(jù)模型

BigTable：是一個(gè)經(jīng)過排序后的分布式的、稀疏的、多維映射表–

分布式：數(shù)據(jù)是分布式存儲的–

稀疏：列數(shù)可能很多，而某一行中可能只有少數(shù)列有數(shù)據(jù)–

多維映射表：

數(shù)據(jù)索引由行關(guān)鍵字（Row

Key）、列關(guān)鍵字（Column

Key）和時(shí)間戳

（Time

Stamp）三個(gè)維度構(gòu)成

數(shù)據(jù)以鍵/值映射的形式組織(

row:string,

column:string,

time:int64

)

→

stringBigTable數(shù)據(jù)模型BigTable：是一個(gè)經(jīng)過BigTable示例–

t3、t5、t6三個(gè)時(shí)間點(diǎn)抓取的網(wǎng)頁內(nèi)容存儲在contents列中文字CNN，和位于my.look.ca頁面的超鏈接文字CNN.com第43BigTable示例–t3、t5、t6三個(gè)時(shí)間點(diǎn)抓取BigTable表的展開行數(shù)行關(guān)鍵字版本列族：contents列族：anchor限定詞：限定詞：my.look.ca12“CNN”“CNN.com”t2t1t7t6t5t4t3

<html>a2</html><html>a1</html><html>d4</html><html>c3</html><html>b2</html>BigTable表的展開行數(shù)行關(guān)鍵字版本列族：content

面向列的存儲–

提高訪問少數(shù)列的效率

整行掃描

vs.

單列讀取–

提高壓縮比

雜

vs.

純面向列的存儲–提高訪問少數(shù)列的效率整行BigTable系統(tǒng)架構(gòu)子表（Tablet）過大的數(shù)據(jù)表不利于存儲和訪問效率大表在水平方向上被分為多個(gè)子表，每個(gè)子表包含表中若干行的數(shù)據(jù)支持?jǐn)?shù)據(jù)表的分布式存儲和表訪問的負(fù)載均衡

主控服務(wù)器操作及管理數(shù)據(jù)表元數(shù)據(jù)子表分配與監(jiān)控負(fù)載均衡控制子表服務(wù)器數(shù)據(jù)服務(wù)器的基本單元數(shù)據(jù)以文件形式存儲在GFS文件系統(tǒng)中BigTable系統(tǒng)架構(gòu)子表（Tablet）過大的數(shù)據(jù)表不大數(shù)據(jù)的三個(gè)關(guān)鍵問題Google的大數(shù)據(jù)技術(shù)Google的業(yè)務(wù)：PageRank三大法寶52第二講大數(shù)據(jù)的關(guān)鍵技術(shù)大數(shù)據(jù)的三個(gè)關(guān)鍵問題1第二講大數(shù)據(jù)的關(guān)鍵技術(shù)52文件存儲數(shù)據(jù)分析數(shù)據(jù)計(jì)算數(shù)據(jù)存儲平臺管理數(shù)據(jù)集成數(shù)據(jù)源Database

Web

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

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

三大關(guān)鍵問題

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

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

容量–

吞吐量

容量–

單硬盤容量提升：MB

→

GB

→

TB

→

┈–

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

吞吐量

=

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

/

傳輸時(shí)間–

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

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

RAID：Redundant

Array

of

Inexpensive

Disks，冗余磁盤陣列–

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

RAID0：連續(xù)以位或字節(jié)為單位分割數(shù)據(jù)，并行讀/寫于多個(gè)磁盤上，提升吞吐量提升吞吐量RAID：RedundantArray三大關(guān)鍵問題存儲計(jì)算容錯(cuò)三大關(guān)鍵問題存儲多核技術(shù)

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

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

MF

IPC

多處理器技術(shù)

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

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

1

F

1

F/

N

非對稱多處理器架構(gòu)（ASMP）––––不同類型計(jì)算任務(wù)或進(jìn)程由不同處理器執(zhí)行簡單，操作系統(tǒng)修改小低效早期過渡性架構(gòu)對稱多處理器架構(gòu)（SMP）––––所有處理器完全對等計(jì)算任務(wù)按需分配高效普遍采用IPSMFIPC多處理器技術(shù)并行模式獨(dú)立并行–兩個(gè)數(shù)據(jù)操作間沒有數(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è)子操作只處理對應(yīng)的部分?jǐn)?shù)據(jù)，并將這些子操作配到不同的處理器上執(zhí)行–例：

Scan

→

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

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

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

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

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

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

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

故障監(jiān)測–

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

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

布林

合作開發(fā)BackRub

搜索引擎

命名Google

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

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

址索引商品+新聞+API

開始收購+Google

圖書

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

地圖+Talk+

分析YouTube+Google

Apps

Gmail+

街景+AndroidHealth+

iPhone

應(yīng)用

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

地圖導(dǎo)航+

搜索

收購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)確率：魚與熊掌不可兼得？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ù)存儲與處理第二講課件

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

佩奇（Page），斯坦福–

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

每個(gè)網(wǎng)頁的鏈接就像一個(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ì)算問題如何計(jì)算10億、100億個(gè)網(wǎng)頁？行列數(shù)以億為單位的矩陣相乘！PageRank（9）–算法的計(jì)算問題如何計(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ī)模矩陣相乘問題：我拆

Cm

=

Am

ⅹ

B

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

Cm,n

=

Am

ⅹ

Bn

M

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

CABA1AmAM=ⅹC1,1Cm,1CM,1B1BnBM想辦法解決大規(guī)模矩陣相乘問題：我再拆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的來源

編程模型：–

1956年John

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

Map輸入是一個(gè)函數(shù)和n個(gè)列表，輸出是一個(gè)新的列表，列表中的元素是將輸入函數(shù)作用在n個(gè)輸入列表中每個(gè)對應(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的來源編程模型：–1956年JoMapReduce原理MapReduce原理MapReduce機(jī)制

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

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

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

大數(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ì)算框架–

程序員只需要編寫少量的程序?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簡介

GFS

–

Google

File

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

為什么需要GFS？–

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

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

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

爬取的網(wǎng)頁–

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

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

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

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

倒排索引–

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

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

特點(diǎn)–

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

數(shù)量龐大–

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

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

CPU

+

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

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

–

抓取網(wǎng)頁并存儲：順序?qū)懭耄瑯O少發(fā)生隨機(jī)寫的情況

–

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

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

①

順序?qū)懭?，順序讀取，避免隨機(jī)讀寫文件傳輸效率公式

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)行存儲（64MB

vs.

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

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

Intel

CPU

+

IDE硬盤集群多節(jié)點(diǎn)數(shù)據(jù)冗余存儲GFS支持容錯(cuò)Google的第一臺服務(wù)器（1998）集群多節(jié)GFS系統(tǒng)架構(gòu)客戶端（Client）GFS提