MapReduce课件

格式：ppt
大小：803.00 KB
文档页数：29

下载文档原格式

MapReduce幻灯片

≈ 20 Mrd. Webseiten x 20 KB ≈ 400TB Lesegeschwindigkeit eines Rechners von einer Festplatte ≈ 30-35 MB/s => 4 Monate, um Web zu lesen ≈ 1000 Festplatten, um das Web zu speichern Bearbeitung der Daten benötigt zusätzliche Ressourcen

Wie lässt sich das schneller machen?
Verteiltes System: gleiche Datenmenge mit 1000 Rechnern in weniger als 3 Stunden
Friedrich-Alexander-Universität Erlangen-Nürnberg Tobias Schwarzer, Michael Theil
6
Map Function
„document“,“to be or not to be“
map()
„to“, „1“ „be“, „1“ „or“, „1“ „not“,„1“ „to“, „1“ „be“, „1“
map(String key, String value): // key: document name // value: document contents for each word w in value: EmitIntermediate(w, „1“);
9
Übersicht
Motivation Programmiermodell Implementierung Erweiterungen

云计算Mapreduce简介PPT课件

google云计算的构成要素
• 谷歌文件系统GFS（海量的数据访问存储） • Chubby分布式锁服务（分布式环境下并发操作的同步） • MapReduce分布式编程模型的结构（并行数据处理） • BigTable结构化数据存储系统（管理组织海量的数据）
google云计算的构成要素
Google云计算应用
惊人，能容纳不计其数的网络数据拷贝，因此搜索速度能够更快，在眨眼之
间便能为数十亿的搜索提交答案。
• 向"云"规模的数据处理迈进标志着我们在信息处理方面发生了翻天覆地的转变。从最基本的层面讲，"云"的发展就如同100年前人类用电的进程演变，当时的农场和公司逐渐关闭了自己的发电机，转而从高效的发电厂购买电力。 Google的高管们很早前就开始展望这一转变并为之进行筹划准备。
强大的分布式处理能力
• 云计算：其概念是由Google提出的，这是一个美丽的网络应用模式。
• 主要目的：它旨在通过网络把多个成本相对较低的计算实体整合成一个具有强大计算能力的完美系统。
强大的分布式处理能力
•
由几十万甚至大约100万台廉价的服务器所组成的网络。这些机器单个
而论的话，其性能并不比家用台式机强大多少。但是这个网络存储的数据量
过程5master通知分配了reduce作业的worker它负责的分区在什么位置当reduceworker把所有它负责的中间键值对都读过来后先对它们进行排序使得相同键的键值对聚集在一起
Google云计算的强大处理能力
目录
• 1.为何云计算有强大的处理能力 • 2.云计算的构成要素 • 3.MapReduce分布式编程模型的结构 • 4.MapReduce对数据处理的流程 • 5.容错机制

Google云计算技术MapReduce国外课件

◦ Master pings workers, re-schedules failed tasks. ◦ Note: Completed map tasks are re-executed on
failure because their output is stored on the local disk. ◦ Master failure: redo ◦ Semantics in the presence of failures:
result += ParseInt(v); Emit(AsString(result));
More Examples
Distributed grep:
◦ Map: (key, whole doc/a line) (the matched line, key)
◦ Reduce: identity function
outputs to achieve this property.
MapReduce: Fault Tolerance
Handled via re-execution of tasks.
Task completion committed through master
What happens if Mapper fails ?
◦ Re-execute completed + in-progress map tasks
What happens if Reducer fails ?
◦ Re-execute in progress reduce tasks
What happens if Master fails ?
◦ Potential trouble !!
Thousands of machines read input at local disk speed

MapReduce工作原理图文详解

MapReduce⼯作原理图⽂详解前⾔：MapReduce是⼀种编程模型，⽤于⼤规模数据集（⼤于1TB）的并⾏运算。

概念"Map（映射）"和"Reduce（归约）"，和它们的主要思想，都是从函数式编程语⾔⾥借来的，还有从⽮量编程语⾔⾥借来的特性。

它极⼤地⽅便了编程⼈员在不会分布式并⾏编程的情况下，将⾃⼰的程序运⾏在上。

当前的软件实现是指定⼀个Map（映射）函数，⽤来把⼀组键值对映射成⼀组新的键值对，指定并发的Reduce（归约）函数，⽤来保证所有映射的键值对中的每⼀个共享相同的键组。

呵呵，下⾯我们进⼊正题，这篇⽂章主要分析以下两点内容：⽬录：1.MapReduce作业运⾏流程2.Map、Reduce任务中Shuffle和排序的过程正⽂：1.MapReduce作业运⾏流程下⾯贴出我⽤visio2010画出的流程⽰意图：流程分析：1.在客户端启动⼀个作业。

2.向JobTracker请求⼀个Job ID。

3.将运⾏作业所需要的资源⽂件复制到HDFS上，包括MapReduce程序打包的JAR⽂件、配置⽂件和客户端计算所得的输⼊划分信息。

这些⽂件都存放在JobTracker专门为该作业创建的⽂件夹中。

⽂件夹名为该作业的Job ID。

JAR⽂件默认会有10个副本（mapred.submit.replication属性控制）；输⼊划分信息告诉了JobTracker应该为这个作业启动多少个map任务等信息。

4.JobTracker接收到作业后，将其放在⼀个作业队列⾥，等待作业调度器对其进⾏调度（这⾥是不是很像微机中的进程调度呢，呵呵），当作业调度器根据⾃⼰的调度算法调度到该作业时，会根据输⼊划分信息为每个划分创建⼀个map任务，并将map任务分配给TaskTracker执⾏。

对于map和reduce任务，TaskTracker根据主机核的数量和内存的⼤⼩有固定数量的map 槽和reduce槽。

Hadoop及Mapreduce入门 PPT课件

• Yahoo！： 4000 nodes (2*4cpu boxes w 4*1TB disk & 16GB RAM)
• More on /hadoop/PoweredBy
Goals of HDFS
• 大数据集存储 – 10K nodes, 100 million files, 10 PB
}
/** * Called once at the end of the task. */
protected void cleanup(Context context) throws IOException, InterruptedException {}
}
Job Setup
public static void main(String[] args) throws Exception { String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs(); if (otherArgs.length != 2) { System.err.println("Usage: wordcount <in> <out>"); System.exit(2); } Job job = new Job(new Configuration(), "word count"); job.setJarByClass(WordCount.class);
• Meta-data记录了 – 文件列表信息 – 每个文件的块列表 – 每个块对应的DataNode – 文件属性，如创建时间、创建者、几份副本等
• Transaction Log (EditLog ) –记录了文件系统的每个变化，如创建文件、删除文件、修改文件的副本数等 – EditLog会被合并为FsImage并存入磁盘

培训PPTMapReduce_2

北京传智播客教育
—高级软件人才实作培训专家! 自定义计数器与实现

Context类调用方法getCounter()
计数器声明
1.通过枚举声明 context.getCounter(Enum enum) 2.动态声明 context.getCounter(String groupName,String counterName)
北京传智播客教育
—高级软件人才实作培训专家! MapReduce常见算法

单词计数数据去重排序 Top K 选择投影分组多表连接单表关联
北京传智播客教育
—高级软件人才实作培训专家! 面试题

北京传智播客教育
—高级软件人才实作培训专家! 了解计数器
hadoop计数器:可以让开发人员以全局的视角来审查程序的运行情况以及各项指标，及时做出错误诊断并进行相应处理。内置计数器（MapReduce相关、文件系统相关和作业调度相关） ... 也可以通过http://master:50030/jobdetails.jsp查看
计数器操作
counter.setValue(long value);//设置初始值 counter.increment(long incr);//增加计数
org.apache.hadoop.mapreduce.Counter
北京传智播客教育
—高级软件人才实作培训专家!
—高级软件人才实作培训专家!
Hadoop深入浅出
讲师: 吴超博客： Q Q: 3774 86624
北京传智播客教育
—高级软件人才实作培训专家! 课程安排
标准和自定义计数器* Combiner和Partitioner编程** 自定义排序和分组编程** 常见的MapReduce算法** ---------------------------加深拓展--------------------- 常见大数据处理方法*

Module4经典的MapReduce

© Spinnaker Labs, Inc.
Programming Model
• Borrows from functional programming • Users implement interface of two functions:
– map (in_key, in_value) -> (out_key, intermediate_value) list
f
f
© Spinnaker Labs, Inc.
f
f
f
f
Fold
fold f x0 lst: ('a*'b->'b)->'b->('a list)->'b Moves across a list, applying f to each element plus an accumulator. f returns the next accumulator value, which is combined with the next element of the list
© Spinnaker Labs, Inc.
MapReduce
• • • • Automatic parallelization & distribution Fault-tolerant Provides status and monitoring tools Clean abstraction for programmers
© Spinnaker Labs, Inc.
map Implementation
fun map f [] = [] | map f (x::xs) = (f x) :: (map f xs)

01-mapreduce

CS246: Mining Massive Datasets Jure Leskovec, Stanford University

1/6/2015
Jure Leskovec, Stanford CS246: Mining Massive Datasets,
We will post Hangout link on Piazza 1min before the OH
1/6/2015 Jure Leskovec, Stanford CS246: Mining Massive Datasets, 19

Use the 2nd edition for class readings Gradiance quizzes often refer to chapters of the 1st edition
1/6/2015
Jure Leskovec, Stanford CS246: Mining Massive Datasets,
Infinite data
Filtering data streams Web advertising
Machine learning
Apps
SVM
Recommen der systems
Clustering
Network Analysis
Decision Trees
Association Rules Duplicate document detection
1/6/2015
Jure Leskovec, Stanford CS246: Mining Massive Datasets,
7

Descriptive methods
Find human-interpretable patterns that describe the data

04-第四章 MapReduce

3.4 MapReduce数据流 - Partiton&Shuffle
Mapper output
0 buffer in ram
0.8
sort(, combine), write
spill
Mapper端 shuffle – spill 操作
3.4 MapReduce数据流 - Partiton&Shuffle

3.5 MapReduce数据流 - Reduce
<easy, {1, 1}> <good, {1, 1}> <hadoop, {1}> <hadoop, {1}> <is, {1, 1}> <is, {1, 1}> <learn, {1, 1}> <mapreduce, {1}> <mapreduce, {1}> <to, {1, 1}> <very, {1, 1}> input stream
3.2 MapReduce数据流 - 输入示例
hadoop is very good mapreduce is very good
Format
<0, hadoop is easy to learn> <23, mapreduce is easy to learn>
text1.txt
Split
InputSplit 1 hadoop is easy to learn mapreduce is easy to learn <0, hadoop is very good> <19, mapreduce is very good> data stream for Mapper

大数据课件1第5章--MapReduce分布式计算框架

5.2 MapReduce工作原理
➢ 5.2.1 MapReduce体系架构
MapReduce执行流程注意：不同的Map任务之间、不同的Reduce任务之间不会进行通信，用户不能显示地从一个计算节点向另一个计算节点发送消息，所有的数据交换都是通过MapReduce框架自身去实现的。
5.2 MapReduce工作原理
5.2 MapReduce工作原理
➢ 5.2.2 MapTask工作原理
MapTask作为MapReduce工作流程的前半部分，它主要经历了6个阶段：（4）为了让Reduce可以并行处理Map的结果，需要对Map输出的键值对按照一定的规则进行分区（partition）。分区是基于键进行的，比如键表示省份（如河北、河南、山东等），那么就可以按照不同省份进行分区，同一个省份的键值对划分到一个分区中，默认是只有一个分区。
（2）Merge阶段：在远程拷贝数据的同时，ReduceTask启动了两个后台线程对内存和磁盘上的文件进行合并，以防止内存使用过多或磁盘上文件过多。
（3）Sort阶段：用户自定义reduce函数，其接收的输入数据是按key进行聚集的一组数据。Hadoop采用了基于排序的策略将key相同的数据聚在一起。由于各个MapTask已经实现对自己的处理结果进行了局部排序，因此，ReduceTask只需对所有数据进行一次归并排序即可。归并排序是指将两个或两个以上的有序序列合并成一个有序序列。
>>> def add(x,y):
#定义一个求和的函数，函数名为add
return x+y >>> reduce(add, [1, 2, 3, 4, 5]) #计算列表和：1+2+3+4+5

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

MapReduce
Automatic parallelization & distribution Fault-tolerant Provides status and monitoring tools Clean abstraction for programmers
Programming Model
MapReduce课件
大连理工大学计算机科学与技术学院 2011春季
Outline
MapReduce overview Discussion Questions MapReduce
Motivation
200+ processors 200+ terabyte database 1010 total clock cycles 0.1 second response time 5¢ average advertising revenue
From: /~bryant/presentations/DISC-FCRC07.ppt
Motivation: Large Scale Data Processing
Want to process lots of data ( > 1 TB) Want to parallelize across hundreds/thousands of CPUs … Want to make this easy
"Google Earth uses 70.5 TB: 70 TB for the raw imagery and 500 GB for the index data." From: /2006/09/how-muchdata-does-google-store.html
Example
Page 1: the weather is good Page 2: today is good Page 3: good weather is good.
Map output Worker 1: (the 1), (weather 1), (is 1), (good 1). Worker 2: (today 1), (is 1), (good 1). Worker 3: (good 1), (weather 1), (is 1), (good 1).
Reduce Output
Worker 1:
(the 1)
Worker 2:
(is 3)
Worker 3:
(weather 2)
Worker 4:
(today 1)
Worker 5:
(good 4)
Some Other Real Examples
Term frequencies through the whole Web repository Count of URL access frequency Reverse web-link graph
Master redundantly executes “slow-moving” map tasks; uses results of first copy to finish, (one finishes first “wins”)
Slow workers significantly lengthen completion time Other jobs consuming resources on machine Bad disks with soft errors transfer data very slowly Weird things: processor caches disabled (!!) Why is it safe to redundantly execute map tasks? Wouldn’t this mess up the total computation?
Parallelism map() functions run in parallel, creating different intermediate values from different input data sets reduce() functions also run in parallel, each working on a different output key All values are processed independently Bottleneck: reduce phase can’t start until map phase is completely finished.
Fault Tolerance
On worker failure: Detect failure via periodic heartbeats Re-execute completed and in-progress map tasks Re-execute in progress reduce tasks Task completion committed through master Master failure: Could handle, but don't yet (master failure unlikely)
Optimizations
“Combiner” functions can run on same machine as a mapper Causes a mini-reduce phase to occur before the real reduce phase, to save bandwidth
Reduce Input
Worker 1:
(the 1)
Worker 2:
(is 1), (is 1), (is 1)
Worker 3:
(weather 1), (weather 1)
Worker 4:
(today 1)
Worker 5:
(good 1), (good 1), (good 1), (good 1)
Implementation is a C++ library linked into user programs
Architecture
Execution
Task Granularity
Fine granularity tasks: many more map tasks than machines
Performance
Tests run on cluster of 1800 machines: 4 GB of memory Dual-processor 2 GHz Xeons with Hyperthreading Dual 160 GB IDE disks Gigabit Ethernet per machine Bisection bandwidth approximately 1 Nhomakorabea0 Gbps
Example: Count word occurrences
map(String input_key, String input_value): // input_key: document name // input_value: document contents for each word w in input_value: EmitIntermediate(w, "1"); reduce(String output_key, Iterator intermediate_values): // output_key: a word // output_values: a list of counts int result = 0; for each v in intermediate_values: result += ParseInt(v); Emit(AsString(result));
Borrows from functional programming Users implement interface of two functions:
map (in_key, in_value) -> (out_key, intermediate_value) list reduce (out_key, intermediate_value list) -> out_value list
Master program divides up tasks based on location of data: (Asks GFS for locations of replicas of input file blocks) tries to have map() tasks on same machine as physical file data, or at least same rack
Robust: lost 1600 of 1800 machines once, but finished fine
Optimizations
No reduce can start until map is complete:
A single slow disk controller can rate-limit the whole process
Implementation Overview
Typical cluster:
100s/1000s of 2-CPU x86 machines, 2-4 GB of memory Limited bisection bandwidth Storage is on local IDE disks GFS: distributed file system manages data (SOSP'03) Job scheduling system: jobs made up of tasks, scheduler assigns tasks to machines