大数据存储与处理-第二讲5课件1

大数据的三个关键问题Google的大数据技术Google的业务：PageRank三大法宝1第二讲大数据的关键技术大数据的三个关键问题1第二讲大数据的关键技术文件存储数据分析数据计算数据存储平台管理数据集成数据源Database

Web

Log…现代数据处理

能力组件现代数据处理框架

三大关键问题

3V计算存储｝容错｝｝文件存储数据分析平数据集成数据源DatabaseWeb三大关键问题存储计算容错三大关键问题存储存储问题

解决大数据存储效率的两方面：–

容量–

吞吐量

容量–

单硬盘容量提升：MB

→

GB

→

TB

→

┈–

系统整体容量提升：DAS、NAS、SAN

吞吐量

=

传输数据量

/

传输时间–

单硬盘吞吐量提升：转速、接口、缓存等–

节点吞吐量提升：RAID、专用数据库机存储问题解决大数据存储效率的两方面：–容量–提升吞吐量

RAID：Redundant

Array

of

Inexpensive

Disks，冗余磁盘阵列–

把多块独立的硬盘按一定的方式组合起来形成一个硬盘组，从而实现高性能和高可靠性–

RAID0：连续以位或字节为单位分割数据，并行读/写于多个磁盘上，提升吞吐量Source:

/提升吞吐量RAID：RedundantArray三大关键问题存储计算容错三大关键问题存储多核技术

Moor定律：当价格不变时，集成电路上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍。

采用多核（Multi-core）技术提升IPC，从而突破性能提升瓶颈。指令数主频多核技术Moor定律：当价格不变时，集成电路上可容纳IPS

MF

IPC

多处理器技术

多处理器技术的核心：

按处理器之间的关系可以分为两类：

1

F

1

F/

N

非对称多处理器架构（ASMP）––––不同类型计算任务或进程由不同处理器执行简单，操作系统修改小低效早期过渡性架构对称多处理器架构（SMP）––––所有处理器完全对等计算任务按需分配高效普遍采用IPSMFIPC多处理器技术并行模式独立并行–两个数据操作间没有数据依赖关系––可以采用独立并行的方式分配给不同的处理器执行例：两个独立数据集的Scan操作流水线并行–多个操作间存在依赖关系，且后一个操作必须等待前一个操–作处理完后方可执行将多个操作分配给不同处理器，但处理器间以流水线方式执行–例：Scan

→

Sort

→

Group分割并行–数据操作的输入数据可以分解为多个子集，且子集之间相互独立–分割为若干独立的子操作，每个子操作只处理对应的部分数据，并将这些子操作配到不同的处理器上执行–例：

Scan

→

Merge并行模式独立并行–两个数据操作间没有数据依赖关系–可以采用独并行系统架构共享内存（Shared

Memory，SM）–多个处理器，多个磁盘，一个共享内存，通过数据总线相连–处理器间共享全部磁盘和内存–––结构简单，负载均衡数据总线成为瓶颈，可扩展性较差，共享内存单点故障适合处理器较少（≤8）的小规模并行数据库共享磁盘（Shared

Disk，SD）–多个处理器，每个处理器拥有独立内存，多个磁盘，处理器与磁盘通过数据总线相连–––处理器间共享全部磁盘容错性提高共享磁盘成为性能瓶颈，需要额外维护内存与磁盘间的数据一致性无共享（Shared

Nothing，SN）–每个处理器拥有独立的内存和若干磁盘，通过高速网络相连–处理器独立处理所管理的数据–––––数据传输量小，效率高可扩展性强节点间交换数据开销较大适合处理器数量较大的大规模并行系统后期发展的主流并行系统架构共享内存（SharedMemory，SM）–多三大关键问题存储计算容错三大关键问题存储数据容错

RAID单节点数据冗余存储–

RAID0：并行磁盘–

RAID1：镜像冗余–

RAID10：RAID1+RAID0–

RAID5：校验冗余

Source:

/

集群多节点数据冗余存储数据容错RAID单节点数据冗余存储–RAID0计算任务容错

计算任务容错的关键问题：–

故障监测–

计算数据定位与获取–

任务迁移计算任务容错计算任务容错的关键问题：–故障监测Google是如何解决其大数据处理的三个关键性问题的?我们需要先了解Google的业务特点。14Google的大数据技术Google是如何解决其大数据处理的三个关键性问题的?14G1995199619971999200120032005200720092011...19982000200220042006200820102012当佩奇遇见

布林

合作开发BackRub

搜索引擎

命名Google

Google公司成立首名专用厨师入职建立10亿网址的索

引图片搜索+30亿网

址索引商品+新闻+API

开始收购+Google

图书

80亿网址索引+上市+学术搜索

地图+Talk+

分析YouTube+Google

Apps

Gmail+

街景+AndroidHealth+

iPhone

应用

社交网络搜索+实时

地图导航+

搜索

收购Moto手机+投

平板电脑资能源+

+Google应用商店

眼镜Google

Google最重要的业务？

搜索

AdWords

Google发展史199519961997199920012003200520Google之前的搜索

目录型搜索：Yahoo!–

收集：人工分类–

索引：主题–

使用：目录结构–

优点：准确率高–

缺点：覆盖率低

索引型搜索：AltaVista–

收集：自动爬取（Scooter）–

索引：自动标记–

使用：输入关键词搜索–

优点：覆盖率高–

缺点：准确率低

覆盖率

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的自我揭秘！灵血大数据存储与处理-第二讲5课件1

搜索结果如何排序！搜索结果如何排序！大数据存储与处理-第二讲5课件1

佩奇（Page），斯坦福–

整个互联网就像一张大的图，每个网站就像一个节点，

每个网页的链接就像一个弧。我想，互联网可以用一个

图或者矩阵描述，我也许可以用这个发现做篇博士论文。佩奇（Page），斯坦福–整个互联网就像一张大的图，每

算法的图论表述算法的图论表述

01/2

01/2

0

0

01/2

01/200010000011/31/31/3

0

0n1n2n3

n4

n5 0 0001/3n1n2n3n4n5PageRank（9）–

算法的计算问题如何计算10亿、100亿个网页？行列数以亿为单位的矩阵相乘！PageRank（9）–算法的计算问题如何计算10亿、10Google三大法宝之一：MapReduceGoogle三大法宝之一：MapReduce矩阵乘法串行实现

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？矩阵乘法串行实现2:forj=1;j<=N;j++3: f想办法解决大规模矩阵相乘问题：我拆

Cm

=

Am

ⅹ

B

M台服务器并行计算，时间降低为1/MCABC1CmCMA1AmAM=ⅹ想办法解决大规模矩阵相乘问题：我拆Cm=AmⅹB想办法解决大规模矩阵相乘问题：我再拆

Cm,n

=

Am

ⅹ

Bn

M

ⅹM台服务器并行计算，时间降低为1/M2

CABA1AmAM=ⅹC1,1Cm,1CM,1B1BnBM想办法解决大规模矩阵相乘问题：我再拆Cm,n=Am子任务子任务子任务…拆的本质－

分而治之

分而治之

–

Divide

and

Conquer

–

一个大的计算任务分解为若干小计算任务

–

子任务计算结果合并后获得最终结果

计算任务

DivideConquer

计算结果子任务子任务子任务…拆的本质－分而治之ConquerMapReduce的来源

编程模型：–

1956年John

McCarthy（图灵奖获得者）提出的Lisp语言中的Map/Reduce方法–

Map输入是一个函数和n个列表，输出是一个新的列表，列表中的元素是将输入函数作用在n个输入列表中每个对应元素获得的计算结果。–

Reduce输入是一个函数和一个列表，输出是将函数依次作用于列表的每个元素后获得的计算结果(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）：执行Map或Reduce任务MapReduce机制主控程序（Master）：将MMapReduce不仅仅是编程模型!

让程序员在使用MapReduce时面对以下细节问题？–

大数据如何分割为小数据块？–

如何调度计算任务并分配和调度map和reduce任务节点？–

如何在任务节点间交换数据？–

如何同步任务？–

相互依赖的任务是否执行完成？–

任务节点失效时该如何处理？

Google的MapReduce是一个完整的计算框架–

程序员只需要编写少量的程序实现应用层逻辑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自有的分布式文件系统

为什么需要GFS？–

已有多种分布式文件系统（NFS、AFS、DFS、…）–

Google特有的环境与负载需要GFS简介GFS–GoogleFileSysteGoogle特有的数据和计算

Google处理的主要数据–

爬取的网页–

网站访问日志–

其他相对独立的数据

数据计算的期望结果–

词频统计–

倒排索引–

网页文档的链接图–

网站页面数量统计

特点–

单个计算简单–

数量庞大–

数据相对独立Google特有的数据和计算Google处理的主要数GFS支持大容量

用集群方式提升系统整体容量Google的第一台服务器（1998）Intel

CPU

+

IDE硬盘xGFS支持大容量用集群方式提升系统整体容量GooglGFS支持高吞吐量

Google处理的数据特点

–

抓取网页并存储：顺序写入，极少发生随机写的情况

–

分析网页内容：文件写入后，只会发生读的操作，不会再修改

GFS实现高吞吐量的两个关键点：

①

顺序写入，顺序读取，避免随机读写文件传输效率公式

SEEK

_TIMEblock

_

size/SPEED

SEEK

_TIME1

trans_timetrans_time

SEEK

_TIMEeffect

西数

80G

SATA硬盘

随机读55

8.2②

数据以远大于操作系统文件块的基本单元进行存储（64MB

vs.

512B）GFS支持高吞吐量文件传输效率公式 SEEK_TIME1GFS支持容错

问题：大量廉价PC组件构成的集群作为硬件基础，单节点故障率较高Google的第一台服务器（1998）

Intel

CPU

+

IDE硬盘集群多节点数据冗余存储GFS支持容错Google的第一台服务器（1998）集群多节GFS系统架构客户端（Client）GFS提供给上层应用使用的一组接口库上层应用通过调用接口库中的接口实现GFS系统中的文件管理适合自身应用的简单接口主控节点（Master）管理节点唯一性保存元数据调配块服务器块服务器（Chunk

Server）存储数据块（Chunk）多个固定块大小（默认64MB）数据库多节点冗余备份讨论：分析一下，GFS的文件读写流程大致应该是怎么样的？GFS系统架构客户端（Client）GFS提供给上层应用使①②③④⑤计算索引：客户端将应用提供的文件名和字节偏移通过固定文件块大小进行计算后获得块索引传递索引：客户端将文件名称和块索引发送给主控节点返回位置：主控节点将用于访问文件块的块句柄和文件块所在的块服务器位置返回给客户端访问数据：客户端将位置信息进行缓存，并访问离自己距离最近的块服务器返回数据：被访问的块服务器将数据返回给客户端GFS读数据流程

②

①

③

④

⑤①计算索引：客户端将应用提供的文件名和字节偏移通过固定文件块Google三大法宝之三：BigTableGoogle三大法宝之三：BigTable简单搜索框背后的复杂工作1.

Crawler从URL服务器提取地址进行遍历查找2.

获取文档docs

,建立文档docIDs

,进行分析、压缩3.

存储到文档数据库4.

索引器为docs建立顺排索引和倒排索引5.

索引数据存储到集群中建立索引响应请求.5.对请求进行预处理，包括拼写检查、附加广告等GWS向索引服务器发送查询关键字索引服务器根据关键字查找匹配文档并向GWS返回docIDsGWS将docIDs传给文档服务器，获得文档GWS将查询结果文档以HTML形式返回给用户简单搜索框背后的复杂工作1.Crawler从URL服务为什么需要BigTable？

GFS的局限性：文件系统，不适合结构化数据的存储和访问

结构化数据？使用DB2、SQLServer、MySQL之类的数据库系统？

非也！因为：–

存储数据的多样性与复杂性：

URL、网页内容、用户数据等–

海量的处理请求–

成本与控制力

BigTable的目标：–

适应各种不同类型的数据和应用–

随时增加和减少处理节点的可扩展性和自动平衡能力–

PB级数据环境下的高吞吐量和高并发（百万级TPS）–

连续服务的高可用性和容错