大数据存储与处理

大数据存储与处理第1页/共51页三大关键问题存储计算容错第2页/共50页第2页/共51页存储问题

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

容量–

吞吐量

容量–

单硬盘容量提升：MB

→

GB

→

TB

→

┈–

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

吞吐量

=

传输数据量

/

传输时间–

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

节点吞吐量提升：RAID、专用数据库机第3页/共50页第3页/共51页提升吞吐量

RAID：Redundant

Array

of

Inexpensive

Disks，冗余磁盘阵列–

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

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

/第4页/共50页第4页/共51页三大关键问题存储计算容错第5页/共50页第5页/共51页多核技术

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

采用多核（Multi-core）技术提升IPC，从而突破性能提升瓶颈。指令数主频第6页/共50页第6页/共51页IPS

MF

IPC

多处理器技术

多处理器技术的核心：

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

1

F

1

F/

N

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

→

Sort

→

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

Scan

→

Merge第8页/共50页第8页/共51页并行系统架构共享内存（Shared

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

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

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

RAID单节点数据冗余存储–

RAID0：并行磁盘–

RAID1：镜像冗余–

RAID10：RAID1+RAID0–

RAID5：校验冗余

Source:

/

集群多节点数据冗余存储第11页/共50页第11页/共51页计算任务容错

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

故障监测–

计算数据定位与获取–

任务迁移第12页/共50页第12页/共51页Google是如何解决其大数据处理的三个关键性问题的?我们需要先了解Google的业务特点。13Google的大数据技术第13页/共50页第13页/共51页1995199619971999200120032005200720092011...19982000200220042006200820102012当佩奇遇见

布林

合作开发BackRub

搜索引擎

命名Google

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

引图片搜索+30亿网

址索引商品+新闻+API

开始收购+Google

图书

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

地图+Talk+

分析YouTube+Google

Apps

Gmail+

街景+AndroidHealth+

iPhone

应用

社交网络搜索+实时

地图导航+

搜索

收购Moto手机+投

平板电脑资能源+

+Google应用商店

眼镜Google

Google最重要的业务？

搜索

AdWords

Google发展史第14页/共50页第14页/共51页Google之前的搜索

目录型搜索：Yahoo!–

收集：人工分类–

索引：主题–

使用：目录结构–

优点：准确率高–

缺点：覆盖率低

索引型搜索：AltaVista–

收集：自动爬取（Scooter）–

索引：自动标记–

使用：输入关键词搜索–

优点：覆盖率高–

缺点：准确率低

覆盖率

VS.

准确率：鱼与熊掌不可兼得？第15页/共50页第15页/共51页Google第16页/共50页第16页/共51页

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)灵魂血肉第17页/共50页第17页/共51页第18页/共50页第18页/共51页

搜索结果如何排序！第19页/共50页第19页/共51页第20页/共50页第20页/共51页

佩奇（Page），斯坦福–

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

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

图或者矩阵描述，我也许可以用这个发现做篇博士论文。第21页/共50页第21页/共51页

算法的图论表述第22页/共50页第22页/共51页

01/2

01/2

0

0

01/2

01/200010000011/31/31/3

0

0n1n2n3

n4

n5第23页/共50页第23页/共51页PageRank（9）–

算法的计算问题如何计算10亿、100亿个网页？行列数以亿为单位的矩阵相乘！第24页/共50页第24页/共51页Google三大法宝之一：MapReduce第25页/共50页第25页/共51页矩阵乘法串行实现

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？第26页/共50页第26页/共51页想办法解决大规模矩阵相乘问题：我拆

Cm

=

Am

ⅹ

B

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

Cm,n

=

Am

ⅹ

Bn

M

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

CABA1AmAM=ⅹC1,1Cm,1CM,1B1BnBM第28页/共50页第28页/共51页子任务子任务子任务…拆的本质－

分而治之

分而治之

–

Divide

and

Conquer

–

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

–

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

计算任务

DivideConquer

计算结果第29页/共50页第29页/共51页MapReduce的来源

编程模型：–

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操作第30页/共50页第30页/共51页MapReduce原理Source：sun.fim.uni-passau.de/cl/MapReduceFoundation/第31页/共50页第31页/共51页MapReduce机制

主控程序（Master）：将Map和Reduce分配到合适的工作机上

工作机（Worker）：执行Map或Reduce任务第32页/共50页第32页/共51页MapReduce不仅仅是编程模型!

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

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

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

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

如何同步任务？–

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

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

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

程序员只需要编写少量的程序实现应用层逻辑第33页/共50页第33页/共51页程序示例：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;}第34页/共50页第34页/共51页Google三大法宝之二：GFS第35页/共50页第35页/共51页GFS简介

GFS

–

Google

File

System，Google自有的分布式文件系统

为什么需要GFS？–

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

Google特有的环境与负载需要第36页/共50页第36页/共51页Google特有的数据和计算

Google处理的主要数据–

爬取的网页–

网站访问日志–

其他相对独立的数据

数据计算的期望结果–

词频统计–

倒排索引–

网页文档的链接图–

网站页面数量统计

特点–

单个计算简单–

数量庞大–

数据相对独立第37页/共50页第37页/共51页GFS支持大容量

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

CPU

+

IDE硬盘x第38页/共50页第38页/共51页GFS支持高吞吐量

Google处理的数据特点

–

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

–

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

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

①

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

SEEK

_TIMEblock

_

size/SPEED

SEEK

_TIME1

trans_timetrans_time

SEEK

_TIMEeffect

西数

80G

SATA硬盘

随机读55

8.2②

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

vs.

512B）第39页/共50页第39页/共51页GFS支持容错

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

Intel

CPU

+

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

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

②

①

③

④

⑤第42页/共50页第42页/共51页Google三大法宝之三：BigTable第43页/共50页第43页/共51页简单搜索框背后的复杂工作1.

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

获取文档docs

,建立文档docIDs

,进行分析、压缩3.

存储到文档数据库4.

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

索引数据存储到集群中建立索引响应请求1.2.3.4.5.对请求进行预处理，包括拼写检查、附加广告等GWS向索引服务器发送查询关键字索引服务器根据关键字查找匹配文档并向GWS返回docIDsGWS将docIDs传给文档服务器，获得文档GWS将查询结果文档以HTML形式返回给用户第44页/共50页第44页/共51页为什么需要BigTable？

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

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

非也！因为：–

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

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

海量的处理请求–

成本与控制力

BigTable的目标：–

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

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

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

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

架构与使用的简洁性第45页/共50页