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

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

Web

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

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

三大關鍵問題

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

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

容量–

吞吐量

容量–

單硬盤容量提升：MB

→

GB

→

TB

→

┈–

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

吞吐量

=

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

/

傳輸時間–

單硬盤吞吐量提升：轉速、接口、緩存等–

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

RAID：Redundant

Array

of

Inexpensive

Disks，冗余磁盤陣列–

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

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

/提升吞吐量RAID：RedundantArray三大關鍵問題存儲計算容錯三大關鍵問題存儲多核技術

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

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

MF

IPC

多處理器技術

多處理器技術的核心：

按處理器之間的關系可以分為兩類：

1

F

1

F/

N

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

→

Sort

→

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

Scan

→

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

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

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

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

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

RAID0：并行磁盤–

RAID1：鏡像冗余–

RAID10：RAID1+RAID0–

RAID5：校驗冗余

Source:

/

集群多節(jié)點數(shù)據(jù)冗余存儲數(shù)據(jù)容錯RAID單節(jié)點數(shù)據(jù)冗余存儲–RAID0計算任務容錯

計算任務容錯的關鍵問題：–

故障監(jiān)測–

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

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

布林

合作開發(fā)BackRub

搜索引擎

命名Google

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

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

址索引商品+新聞+API

開始收購+Google

圖書

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

地圖+Talk+

分析YouTube+Google

Apps

Gmail+

街景+AndroidHealth+

iPhone

應用

社交網(wǎng)絡搜索+實時

地圖導航+

搜索

收購Moto手機+投

平板電腦資能源+

+Google應用商店

眼鏡Google

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

搜索

AdWords

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

目錄型搜索：Yahoo!–

收集：人工分類–

索引：主題–

使用：目錄結構–

優(yōu)點：準確率高–

缺點：覆蓋率低

索引型搜索：AltaVista–

收集：自動爬取（Scooter）–

索引：自動標記–

使用：輸入關鍵詞搜索–

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

缺點：準確率低

覆蓋率

VS.

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

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

佩奇（Page），斯坦福–

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

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

圖或者矩陣描述，我也許可以用這個發(fā)現(xiàn)做篇博士論文。佩奇（Page），斯坦福–整個互聯(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）–

算法的計算問題如何計算10億、100億個網(wǎng)頁？行列數(shù)以億為單位的矩陣相乘！PageRank（9）–算法的計算問題如何計算10億、10Google三大法寶之一：MapReduceGoogle三大法寶之一：MapReduce矩陣乘法串行實現(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

算法復雜度：O(N3)

以1次乘法需要1個時鐘周期，計算10億維度矩陣為

例，使用1G的CPU，需要的計算時間為：

t

=

10億×10億×10億

/

10億

=

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

Cm

=

Am

ⅹ

B

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

Cm,n

=

Am

ⅹ

Bn

M

ⅹM臺服務器并行計算，時間降低為1/M2

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

分而治之

分而治之

–

Divide

and

Conquer

–

一個大的計算任務分解為若干小計算任務

–

子任務計算結果合并后獲得最終結果

計算任務

DivideConquer

計算結果子任務子任務子任務…拆的本質－分而治之ConquerMapReduce的來源

編程模型：–

1956年John

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

Map輸入是一個函數(shù)和n個列表，輸出是一個新的列表，列表中的元素是將輸入函數(shù)作用在n個輸入列表中每個對應元素獲得的計算結果。–

Reduce輸入是一個函數(shù)和一個列表，輸出是將函數(shù)依次作用于列表的每個元素后獲得的計算結果(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原理Source：sun.fim.uni-passau.de/cl/MapReduceFoundation/MapReduce原理Source：http://www.iMapReduce機制

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

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

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

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

如何調度計算任務并分配和調度map和reduce任務節(jié)點？–

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

如何同步任務？–

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

任務節(jié)點失效時該如何處理？

Google的MapReduce是一個完整的計算框架–

程序員只需要編寫少量的程序實現(xiàn)應用層邏輯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)境與負載需要GFS簡介GFS–GoogleFileSysteGoogle特有的數(shù)據(jù)和計算

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

爬取的網(wǎng)頁–

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

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

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

詞頻統(tǒng)計–

倒排索引–

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

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

特點–

單個計算簡單–

數(shù)量龐大–

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

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

CPU

+

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

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

–

抓取網(wǎng)頁并存儲：順序寫入，極少發(fā)生隨機寫的情況

–

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

GFS實現(xiàn)高吞吐量的兩個關鍵點：

①

順序寫入，順序讀取，避免隨機讀寫文件傳輸效率公式

SEEK

_TIMEblock

_

size/SPEED

SEEK

_TIME1

trans_timetrans_time

SEEK

_TIMEeffect

西數(shù)

80G

SATA硬盤

隨機讀55

8.2②

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

vs.

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

問題：大量廉價PC組件構成的集群作為硬件基礎，單節(jié)點故障率較高Google的第一臺服務器（1998）

Intel

CPU

+

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

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

②

①

③

④

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

Crawler從URL服務器提取地址進行遍歷查找2.

獲取文檔docs

,建立文檔docIDs

,進行分析、壓縮3.

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

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

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

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

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

非也！因為：–

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

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

海量的處理請求–

成本與控制力

BigTable的目標：–

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

隨時增加和減少處理節(jié)點的可擴展性和自動平衡能力–

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

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