谷歌MapReduce工作原理详解

需积分: 10 3 浏览量更新于2024-09-09 收藏 203KB PDF 举报

"本文介绍了Google MapReduce的工作原理，这是一种简化大型集群上大规模数据处理的方法。" 在21世纪初，随着互联网的快速发展，Google面临着处理海量数据的挑战，这些数据包括爬取的文档、Web请求日志等。为了计算各种衍生数据，如倒排索引、Web文档的图结构表示、特定主机的抓取页面数量以及每日最频繁的查询等，Google的工程师们开发了数百种特殊目的的计算程序。尽管这些计算在概念上相对简单，但由于数据量巨大，通常需要在成百上千台机器上分布式执行，以在合理的时间内完成。这一过程涉及到并行化计算、数据分布以及故障处理等复杂问题，导致原本简单的计算任务被大量的复杂代码所掩盖。为了解决这个问题，Google的Jeffrey Dean和Sanjay Ghemawat提出了MapReduce的概念。MapReduce是一种编程模型，旨在简化大规模数据集上的并行计算。它由两个主要阶段组成：Map阶段和Reduce阶段。 Map阶段负责将原始输入数据分解为较小的键值对，这个过程通常涉及数据过滤和转换。例如，对于一个搜索引擎，Map阶段可能将每个文档拆分成单词，并为每个单词及其出现次数生成键值对。 Reduce阶段接着处理Map阶段产生的键值对，它将具有相同键的值聚合在一起，执行必要的计算，然后输出最终的结果。在上面的搜索引擎例子中，Reduce阶段会收集所有相同的单词键，对其出现次数求和，生成每个单词的总频率。 MapReduce框架还包含了一个中间步骤，即Shuffle和Sort，它整理Map阶段的输出，按键排序，确保相同键的值会被传递到同一个Reduce任务，从而优化数据处理效率。此外，MapReduce设计时考虑了容错性。如果某个工作节点在执行过程中失败，系统会自动重新调度任务到其他可用节点，确保整个计算过程的完整性。这种机制使得MapReduce能够处理大规模数据集时的硬件故障，提高了系统的可靠性。 MapReduce的成功在于其抽象程度高，让开发者可以专注于实现业务逻辑，而无需关心底层的分布式系统细节。这一模型已被广泛应用在大数据处理领域，成为了Hadoop等开源框架的基础，极大地推动了大数据分析和处理的发展。通过使用MapReduce，复杂的分布式计算任务变得更容易理解和实现，极大地降低了大规模数据处理的门槛。

MapReduce: Simplified Data Processing

on Large Clusters

by Jeffrey Dean and Sanjay Ghemawat

1 Introduction

Prior to our development of MapReduce, the authors and many others

at Google implemented hundreds of special-purpose computations that

process large amounts of raw data, such as crawled documents, Web

request logs, etc., to compute various kinds of derived data, such as

inverted indices, various representations of the graph structure of Web

documents, summaries of the number of pages crawled per host, and

the set of most frequent queries in a given day. Most such computa-

tions are conceptually straightforward. However, the input data is usu-

ally large and the computations have to be distributed across hundreds

or thousands of machines in order to finish in a reasonable amount of

time. The issues of how to parallelize the computation, distribute the

data, and handle failures conspire to obscure the original simple com-

putation with large amounts of complex code to deal with these issues.

As a reaction to this complexity, we designed a new abstraction that

allows us to express the simple computations we were trying to perform

but hides the messy details of parallelization, fault tolerance, data distri-

bution and load balancing in a library. Our abstraction is inspired by the

map and reduce primitives present in Lisp and many other functional lan-

guages. We realized that most of our computations involved applying a

map operation to each logical record’ in our input in order to compute a

set of intermediate key/value pairs, and then applying a reduce operation

to all the values that shared the same key in order to combine the derived

data appropriately. Our use of a functional model with user-specified map

and reduce operations allows us to parallelize large computations easily

and to use reexecution as the primary mechanism for fault tolerance.

The major contributions of this work are a simple and powerful

interface that enables automatic parallelization and distribution of

large-scale computations, combined with an implementation of this

interface that achieves high performance on large clusters of com-

modity PCs. The programming model can also be used to parallelize

computations across multiple cores of the same machine.

Section 2 describes the basic programming model and gives several

examples. In Sec tion 3, we describe an implementation of the Map Reduce

interface tailored towards our cluster-based computing environment.

Sec tion 4 describes several refinements of the programming model that

we have found useful. Sec tion 5 has performance measurements of our

implementation for a variety of tasks. In Section 6, we explore the use of

MapReduce within Google including our experiences in using it as the ba-

sis for a rewrite of our production indexing system. Section 7 discusses re-

lated and future work.

2 Programming Model

The computation takes a set of input key/value pairs, and produces a

set of output key/value pairs. The user of the MapReduce library

expresses the computation as two functions: map and reduce.

Map, written by the user, takes an input pair and produces a set of

intermediate key/value pairs. The MapReduce library groups together

all intermediate values associated with the same intermediate key I

and passes them to the reduce function.

The reduce function, also written by the user, accepts an interme-

diate key I and a set of values for that key. It merges these values

together to form a possibly smaller set of values. Typically just zero or

one output value is produced per reduce invocation. The intermediate

values are supplied to the user’s reduce function via an iterator. This

allows us to handle lists of values that are too large to fit in memory.

2.1 Example

Consider the problem of counting the number of occurrences of each

word in a large collection of documents. The user would write code

similar to the following pseudocode.

Abstract

apReduce is a programming model and an associated implementation for processing

and generating large datasets that is amenable to a broad variety of real-world tasks.

Users specify the computation in terms of a map and a reduce function, and the under-

lying runtime system automatically parallelizes the computation across large-scale clusters of

machines, handles machine failures, and schedules inter-machine communication to make effi-

cient use of the network and disks. Programmers find the system easy to use: more than ten

thousand distinct MapReduce programs have been implemented internally at Google over the

past four years, and an average of one hundred thousand MapReduce jobs are executed on

Google’s clusters every day, processing a total of more than twenty petabytes of data per day.

Biographies

Jeff Dean (jeff@google.com) is a Google Fellow and is currently work-

ing on a large variety of large-scale distributed systems at Google’s Moun -

tain View, CA, facility.

Sanjay Ghemawat (sanjay@google.com) is a Google Fellow and works

on the distributed computing infrastructure used by most the company’s

products. He is based at Google’s Mountain View, CA, facility.

COMMUNICATIONS OF THE ACM January 2008/Vol. 51, No. 1 107

再执行

适合的

调用

伪代码

下载后可阅读完整内容，剩余6页未读，立即下载

Future-Miracle

粉丝: 28
资源: 11

谷歌MapReduce工作原理详解

Google MapReduce中文版：并行处理与大规模数据的编程框架

VmWare中Hadoop2.6.5全分布式集群搭建教程

MapReduce编程模型：海量数据处理的关键

GoogleMapReduce中文版

GoogleMapReduce中文版.pdf

Google MapReduce：大规模数据处理的编程模型与实现

Hadoop：解决海量数据存储与计算的革命

[net毕业设计]ASP.NET基于BS结构的实验室预约模型系统（源代码+论文）.zip

中医诊所系统，WPF.zip

[net毕业设计]ASP.NET淘宝店主交易管理系统的设计与实现（源代码+论文）.zip

最新资源