Case 4:23-cv-01147-ALM Document 62-10 Filed 11/12/24 Page 1 of 14 PageID #:
`4568
`
`EXHIBIT 2
`
`

`

`Case 4:23-cv-01147-ALM Document 62-10 Filed 11/12/24 Page 2 of 14 PageID #:
`4569
`
`MapReduce: Simplified Data Processing on Large Clusters
`
`Jeffrey Dean and Sanjay Ghemawat
`
`jeff@google.com, sanjay@google.com
`
`Google, Inc.
`
`Abstract
`
`MapReduce is a programming model and an associ(cid:173)
`ated implementation for processing and generating large
`data sets. Users specify a map function that processes a
`key/value pair to generate a set of intermediate key/value
`pairs, and a reduce function that merges all intermediate
`values associated with the same intermediate key. Many
`real world tasks are expressible in this model, as shown
`in the paper.
`Programs written in this functional style are automati(cid:173)
`cally parallelized and executed on a large cluster of com(cid:173)
`modity machines. The run-time system takes care of the
`details of partitioning the input data, scheduling the pro(cid:173)
`gram's execution across a set of machines, handling ma(cid:173)
`chine failures , and managing the required inter-machine
`communication. This allows programmers without any
`experience with parallel and distributed systems to eas(cid:173)
`ily utilize the resources of a large distributed system.
`Our implementation of MapReduce runs on a large
`cluster of commodity machines and is highly scalable:
`a typical MapReduce computation processes many ter(cid:173)
`abytes of data on thousands of machines. Programmers
`find the system easy to use: hundreds ofMapReduce pro(cid:173)
`grams have been implemented and upwards of one thou(cid:173)
`sand MapReduce jobs are executed on Google's clusters
`every day.
`
`1 Introduction
`
`Over the past five years, the authors and many others at
`Google have 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, the set of most frequent queries in a
`
`I To appear in OSDI 2004 I
`
`given day, etc. Most such computations are conceptu(cid:173)
`ally straightforward. However, the input data is usually
`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 par(cid:173)
`allelize the computation, distribute the data, and handle
`failures conspire to obscure the original simple compu(cid:173)
`tation 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 computa(cid:173)
`tions we were trying to perform but hides the messy de(cid:173)
`tails of parallelization, fault-tolerance, data distribution
`and load balancing in a library. Our abstraction is in(cid:173)
`spired by the map and reduce primitives present in Lisp
`and many other functional languages. We realized that
`most of our computations involved applying a map op(cid:173)
`eration 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 ap(cid:173)
`propriately. Our use of a functional model with user(cid:173)
`specified map and reduce operations allows us to paral(cid:173)
`lelize large computations easily and to use re-execution
`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 commodity PCs.
`Section 2 describes the basic programming model and
`gives several examples. Section 3 describes an imple(cid:173)
`mentation of the MapReduce interface tailored towards
`our cluster-based computing environment. Section 4 de(cid:173)
`scribes several refinements of the programming model
`that we have found useful. Section 5 has performance
`measurements of our implementation for a variety of
`tasks. Section 6 explores the use of MapReduce within
`Google including our experiences in using it as the basis
`
`Databricks R2 PA 00000329
`-
`-
`-
`
`

`

`Case 4:23-cv-01147-ALM Document 62-10 Filed 11/12/24 Page 3 of 14 PageID #:
`4570
`
`for a rewrite of our production indexing system. Sec(cid:173)
`tion 7 discusses related 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 pro(cid:173)
`duces a set of intermediate key/value pairs. The MapRe(cid:173)
`duce library groups together all intermediate values asso(cid:173)
`ciated with the same intermediate key I and passes them
`to the Reduce function.
`The Reduce function , also written by the user, accepts
`an intermediate key I and a set of values for that key. It
`merges together these values to form a possibly smaller
`set of values. Typically just zero or one output value is
`produced per Reduce invocation. The intermediate val(cid:173)
`ues are supplied to the user's reduce function via an iter(cid:173)
`ator. 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 oc(cid:173)
`currences of each word in a large collection of docu(cid:173)
`ments. The user would write code similar to the follow(cid:173)
`ing pseudo-code:
`
`map ( String key , String v alue ):
`/ / key : document name
`/ / value : document content s
`for each word w in value :
`Emitinterme d iate (w,
`" 1 ");
`
`reduce (String key , Iterator value s):
`/ / key : a word
`/ / values : a li s t of count s
`int re s ult = O;
`for each v
`i n value s:
`re s ult+= Par s eint (v );
`Emit (As String ( re s ult ));
`
`The map function emits each word plus an associated
`count of occurrences (just ' 1' in this simple example).
`The r e d uc e function sums together all counts emitted
`for a particular word.
`In addition, the user writes code to fill in a mapreduce
`specification object with the names of the input and out(cid:173)
`put files , and optional tuning parameters. The user then
`invokes the MapReduce function, passing it the specifi(cid:173)
`cation object. The user's code is linked together with the
`MapReduce library (implemented in C++ ). Appendix A
`contains the full program text for this example.
`
`2.2 Types
`
`Even though the previous pseudo-code is written in terms
`of string inputs and outputs, conceptually the map and
`reduce functions supplied by the user have associated
`types:
`map
`-----+ l i s t (k 2 , v 2)
`(kl, vl)
`reduce
`-----+ l i s t (v 2 )
`(k2, l i s t (v 2))
`I.e., the input keys and values are drawn from a different
`domain than the output keys and values. Furthermore,
`the intermediate keys and values are from the same do(cid:173)
`main as the output keys and values.
`Our C++ implementation passes strings to and from
`the user-defined functions and leaves it to the user code
`to convert between strings and appropriate types.
`
`2.3 More Examples
`
`Here are a few simple examples of interesting programs
`that can be easily expressed as MapReduce computa(cid:173)
`tions.
`
`Distributed Grep: The map function emits a line if it
`matches a supplied pattern. The reduce function is an
`identity function that just copies the supplied intermedi(cid:173)
`ate data to the output.
`
`Count of URL Access Frequency: The map func(cid:173)
`tion processes logs of web page requests and outputs
`(URL , 1). The reduce function adds together all values
`for the same URL and emits a (URL, t o ta l co unt)
`pair.
`
`Reverse Web-Link Graph: The map function outputs
`(t a r g et , sou r ce) pairs for each link to a t arge t
`URL found in a page named sou r c e. The reduce
`function concatenates the list of all source URLs as(cid:173)
`sociated with a given target URL and emits the pair:
`(t a r g et , list (sour ce) )
`
`Term-Vector per Host: A term vector summarizes the
`most important words that occur in a document or a set
`of documents as a list of (word, fr equency ) pairs. The
`map function emits a (hostn ame , term v e c to r )
`pair for each input document (where the hostname is
`extracted from the URL of the document). The re(cid:173)
`duce function is passed all per-document term vectors
`for a given host.
`It adds these term vectors together,
`throwing away infrequent terms, and then emits a final
`(h os tn ame, t e r m v e c t o r ) pair.
`
`I To appear in OSDI 2004 I
`
`2
`
`Databricks R2 PA 00000330
`-
`-
`-
`
`

`

`Case 4:23-cv-01147-ALM Document 62-10 Filed 11/12/24 Page 4 of 14 PageID #:
`4571
`
`User
`Program
`
`(1) fork e (2)
`
`(I) fork_ . •
`
`(2) . ••
`. aSsign
`map
`
`ass_ign
`reduce .
`
`[I]
`
`------
`
`~
`
`--.
`
`----
`(3 ) read
`
`split 0
`
`split 1
`
`split 2
`
`split 3
`
`split 4
`
`(4) local write
`
`worker
`
`~ [I] 7
`
`(6) write
`
`output
`file 0
`
`output
`file 1
`
`Input
`files
`
`Map
`phase
`
`Intermediate files
`( on local disks)
`
`Reduce
`phase
`
`Output
`files
`
`Figure 1: Execution overview
`
`Inverted Index: The map function parses each docu(cid:173)
`ment, and emits a sequence of (word, document ID)
`pairs. The reduce function accepts all pairs for a given
`word, sorts the corresponding document IDs and emits a
`(word, list( document ID)) pair. The set of all output
`pairs forms a simple inverted index. It is easy to augment
`this computation to keep track of word positions.
`
`Distributed Sort: The map function extracts the key
`from each record, and emits a (key, record) pair. The
`reduce function emits all pairs unchanged. This compu(cid:173)
`tation depends on the partitioning facilities described in
`Section 4.1 and the ordering properties described in Sec(cid:173)
`tion 4.2.
`
`3 Implementation
`
`Many different implementations of the MapReduce in(cid:173)
`terface are possible. The right choice depends on the
`environment. For example, one implementation may be
`suitable for a small shared-memory machine, another for
`a large NUMA multi-processor, and yet another for an
`even larger collection of networked machines.
`This section describes an implementation targeted
`to the computing environment in wide use at Google:
`
`large clusters of commodity PCs connected together with
`switched Ethernet [4]. In our environment:
`( 1) Machines are typically dual-processor x86 processors
`running Linux, with 2-4 GB of memory per machine.
`(2) Commodity networking hardware is used - typically
`either 100 megabits/second or 1 gigabit/second at the
`machine level, but averaging considerably less in over(cid:173)
`all bisection bandwidth.
`(3) A cluster consists of hundreds or thousands of ma(cid:173)
`chines, and therefore machine failures are common.
`(4) Storage is provided by inexpensive IDE disks at(cid:173)
`tached directly to individual machines. A distributed file
`system [8] developed in-house is used to manage the data
`stored on these disks. The file system uses replication to
`provide availability and reliability on top of unreliable
`hardware.
`(5) Users submit jobs to a scheduling system. Each job
`consists of a set of tasks, and is mapped by the scheduler
`to a set of available machines within a cluster.
`
`3.1 Execution Overview
`
`The Map invocations are distributed across multiple
`machines by automatically partitioning the input data
`
`I To appear in OSDI 2004 I
`
`3
`
`Databricks R2 PA 00000331
`-
`-
`-
`
`

`

`Case 4:23-cv-01147-ALM Document 62-10 Filed 11/12/24 Page 5 of 14 PageID #:
`4572
`
`into a set of M splits. The input splits can be pro(cid:173)
`cessed in parallel by different machines. Reduce invoca(cid:173)
`tions are distributed by partitioning the intermediate key
`space into R pieces using a partitioning function (e.g.,
`hash(key) mod R). The number of partitions (R) and
`the partitioning function are specified by the user.
`Figure 1 shows the overall flow of a MapReduce op(cid:173)
`eration in our implementation. When the user program
`calls the MapReduce function , the following sequence
`of actions occurs (the numbered labels in Figure 1 corre(cid:173)
`spond to the numbers in the list below):
`
`1. The MapReduce library in the user program first
`splits the input files into M pieces of typically 16
`megabytes to 64 megabytes (MB) per piece (con(cid:173)
`trollable by the user via an optional parameter). It
`then starts up many copies of the program on a clus(cid:173)
`ter of machines.
`
`2. One of the copies of the program is special - the
`master. The rest are workers that are assigned work
`by the master. There are M map tasks and R reduce
`tasks to assign. The master picks idle workers and
`assigns each one a map task or a reduce task.
`
`3. A worker who is assigned a map task reads the
`contents of the corresponding input split. It parses
`key/value pairs out of the input data and passes each
`pair to the user-defined Map function. The interme(cid:173)
`diate key/value pairs produced by the Map function
`are buffered in memory.
`
`4. Periodically, the buffered pairs are written to local
`disk, partitioned into R regions by the partitioning
`function. The locations of these buffered pairs on
`the local disk are passed back to the master, who
`is responsible for forwarding these locations to the
`reduce workers.
`
`5. When a reduce worker is notified by the master
`about these locations, it uses remote procedure calls
`to read the buffered data from the local disks of the
`map workers. When a reduce worker has read all in(cid:173)
`termediate data, it sorts it by the intermediate keys
`so that all occurrences of the same key are grouped
`together. The sorting is needed because typically
`many different keys map to the same reduce task. If
`the amount of intermediate data is too large to fit in
`memory, an external sort is used.
`
`6. The reduce worker iterates over the sorted interme(cid:173)
`diate data and for each unique intermediate key en(cid:173)
`countered, it passes the key and the corresponding
`set of intermediate values to the user's Reduce func(cid:173)
`tion. The output of the Reduce function is appended
`to a final output file for this reduce partition.
`
`7. When all map tasks and reduce tasks have been
`completed, the master wakes up the user program.
`At this point, the MapReduce call in the user pro(cid:173)
`gram returns back to the user code.
`
`After successful completion, the output of the mapre(cid:173)
`duce execution is available in the R output files (one per
`reduce task, with file names as specified by the user).
`Typically, users do not need to combine these R output
`files into one file - they often pass these files as input to
`another MapReduce call, or use them from another dis(cid:173)
`tributed application that is able to deal with input that is
`partitioned into multiple files.
`
`3.2 Master Data Structures
`
`The master keeps several data structures. For each map
`task and reduce task, it stores the state (idle, in-progress,
`or completed), and the identity of the worker machine
`(for non-idle tasks).
`The master is the conduit through which the location
`of intermediate file regions is propagated from map tasks
`to reduce tasks. Therefore, for each completed map task,
`the master stores the locations and sizes of the R inter(cid:173)
`mediate file regions produced by the map task. Updates
`to this location and size information are received as map
`tasks are completed. The information is pushed incre(cid:173)
`mentally to workers that have in-progress reduce tasks.
`
`3.3 Fault Tolerance
`
`Since the MapReduce library is designed to help process
`very large amounts of data using hundreds or thousands
`of machines, the library must tolerate machine failures
`gracefully.
`
`Worker Failure
`
`The master pings every worker periodically. If no re(cid:173)
`sponse is received from a worker in a certain amount of
`time, the master marks the worker as failed. Any map
`tasks completed by the worker are reset back to their ini(cid:173)
`tial idle state, and therefore become eligible for schedul(cid:173)
`ing on other workers. Similarly, any map task or reduce
`task in progress on a failed worker is also reset to idle
`and becomes eligible for rescheduling.
`Completed map tasks are re-executed on a failure be(cid:173)
`cause their output is stored on the local disk(s) of the
`failed machine and is therefore inaccessible. Completed
`reduce tasks do not need to be re-executed since their
`output is stored in a global file system.
`When a map task is executed first by worker A and
`then later executed by worker B (because A failed) , all
`
`I To appear in OSDI 2004 I
`
`4
`
`Databricks R2 PA 00000332
`-
`-
`-
`
`

`

`Case 4:23-cv-01147-ALM Document 62-10 Filed 11/12/24 Page 6 of 14 PageID #:
`4573
`
`workers executing reduce tasks are notified of the re(cid:173)
`execution. Any reduce task that has not already read the
`data from worker A will read the data from worker B.
`
`MapReduce is resilient to large-scale worker failures.
`For example, during one MapReduce operation, network
`maintenance on a running cluster was causing groups of
`80 machines at a time to become unreachable for sev(cid:173)
`eral minutes. The MapReduce master simply re-executed
`the work done by the unreachable worker machines, and
`continued to make forward progress, eventually complet(cid:173)
`ing the MapReduce operation.
`
`Master Failure
`
`It is easy to make the master write periodic checkpoints
`of the master data structures described above. If the mas(cid:173)
`ter task dies, a new copy can be started from the last
`checkpointed state. However, given that there is only a
`single master, its failure is unlikely; therefore our cur(cid:173)
`rent implementation aborts the MapReduce computation
`if the master fails. Clients can check for this condition
`and retry the MapReduce operation if they desire.
`
`Semantics in the Presence of Failures
`
`When the user-supplied map and reduce operators are de(cid:173)
`terministic functions of their input values, our distributed
`implementation produces the same output as would have
`been produced by a non-faulting sequential execution of
`the entire program.
`
`We rely on atomic commits of map and reduce task
`outputs to achieve this property. Each in-progress task
`writes its output to private temporary files. A reduce task
`produces one such file, and a map task produces R such
`files (one per reduce task). When a map task completes,
`the worker sends a message to the master and includes
`the names of the R temporary files in the message. If
`the master receives a completion message for an already
`completed map task, it ignores the message. Otherwise,
`it records the names of R files in a master data structure.
`When a reduce task completes, the reduce worker
`atomically renames its temporary output file to the final
`output file. If the same reduce task is executed on multi(cid:173)
`ple machines, multiple rename calls will be executed for
`the same final output file. We rely on the atomic rename
`operation provided by the underlying file system to guar(cid:173)
`antee that the final file system state contains just the data
`produced by one execution of the reduce task.
`
`The vast majority of our map and reduce operators are
`deterministic, and the fact that our semantics are equiv(cid:173)
`alent to a sequential execution in this case makes it very
`
`easy for programmers to reason about their program's be(cid:173)
`havior. When the map and/or reduce operators are non(cid:173)
`deterministic, we provide weaker but still reasonable se(cid:173)
`mantics. In the presence of non-deterministic operators,
`the output of a particular reduce task R 1 is equivalent to
`the output for R 1 produced by a sequential execution of
`the non-deterministic program. However, the output for
`a different reduce task R 2 may correspond to the output
`for R 2 produced by a different sequential execution of
`the non-deterministic program.
`Consider map task M and reduce tasks R 1 and R 2 .
`Let e(Ri ) be the execution of R i that committed (there
`is exactly one such execution). The weaker semantics
`arise because e(R1 ) may have read the output produced
`by one execution of M and e(R2 ) may have read the
`output produced by a different execution of M.
`
`3.4 Locality
`
`Network bandwidth is a relatively scarce resource in our
`computing environment. We conserve network band(cid:173)
`width by taking advantage of the fact that the input data
`(managed by GFS [8]) is stored on the local disks of the
`machines that make up our cluster. GFS divides each
`file into 64 MB blocks, and stores several copies of each
`block (typically 3 copies) on different machines. The
`MapReduce master takes the location information of the
`input files into account and attempts to schedule a map
`task on a machine that contains a replica of the corre(cid:173)
`sponding input data. Failing that, it attempts to schedule
`a map task near a replica of that task's input data (e.g., on
`a worker machine that is on the same network switch as
`the machine containing the data). When running large
`MapReduce operations on a significant fraction of the
`workers in a cluster, most input data is read locally and
`consumes no network bandwidth.
`
`3.5 Task Granularity
`
`We subdivide the map phase into M pieces and the re(cid:173)
`duce phase into R pieces, as described above. Ideally, M
`and R should be much larger than the number of worker
`machines. Having each worker perform many different
`tasks improves dynamic load balancing, and also speeds
`up recovery when a worker fails: the many map tasks
`it has completed can be spread out across all the other
`worker machines.
`There are practical bounds on how large M and R can
`be in our implementation, since the master must make
`O(M + R) scheduling decisions and keeps O(M * R)
`state in memory as described above. (The constant fac(cid:173)
`tors for memory usage are small however: the O(M * R)
`piece of the state consists of approximately one byte of
`data per map task/reduce task pair.)
`
`I To appear in OSDI 2004 I
`
`5
`
`Databricks R2 PA 00000333
`-
`-
`-
`
`

`

`Case 4:23-cv-01147-ALM Document 62-10 Filed 11/12/24 Page 7 of 14 PageID #:
`4574
`
`Furthermore, R is often constrained by users because
`the output of each reduce task ends up in a separate out(cid:173)
`put file. In practice, we tend to choose M so that each
`individual task is roughly 16 MB to 64 MB of input data
`(so that the locality optimization described above is most
`effective), and we make Ra small multiple of the num(cid:173)
`ber of worker machines we expect to use. We often per(cid:173)
`form MapReduce computations with M = 200,000 and
`R = 5,000, using 2,000 worker machines.
`
`3.6 Backup Tasks
`
`One of the common causes that lengthens the total time
`taken for a MapReduce operation is a "straggler": a ma(cid:173)
`chine that takes an unusually long time to complete one
`of the last few map or reduce tasks in the computation.
`Stragglers can arise for a whole host of reasons. For ex(cid:173)
`ample, a machine with a bad disk may experience fre(cid:173)
`quent correctable errors that slow its read performance
`from 30 MB/s to 1 MB/s. The cluster scheduling sys(cid:173)
`tem may have scheduled other tasks on the machine,
`causing it to execute the MapReduce code more slowly
`due to competition for CPU, memory, local disk, or net(cid:173)
`work bandwidth. A recent problem we experienced was
`a bug in machine initialization code that caused proces(cid:173)
`sor caches to be disabled: computations on affected ma(cid:173)
`chines slowed down by over a factor of one hundred.
`We have a general mechanism to alleviate the prob(cid:173)
`lem of stragglers. When a MapReduce operation is close
`to completion, the master schedules backup executions
`of the remaining in-progress tasks. The task is marked
`as completed whenever either the primary or the backup
`execution completes. We have tuned this mechanism so
`that it typically increases the computational resources
`used by the operation by no more than a few percent.
`We have found that this significantly reduces the time
`to complete large MapReduce operations. As an exam(cid:173)
`ple, the sort program described in Section 5.3 takes 44%
`longer to complete when the backup task mechanism is
`disabled.
`
`4 Refinements
`
`Although the basic functionality provided by simply
`writing Map and Reduce functions is sufficient for most
`needs, we have found a few extensions useful. These are
`described in this section.
`
`4.1 Partitioning Function
`
`The users of MapReduce specify the number of reduce
`tasks/output files that they desire (R). Data gets parti(cid:173)
`tioned across these tasks using a partitioning function on
`
`the intermediate key. A default partitioning function is
`provided that uses hashing (e.g. "hash(key) mod R") .
`This tends to result in fairly well-balanced partitions. In
`some cases, however, it is useful to partition data by
`some other function of the key. For example, sometimes
`the output keys are URLs, and we want all entries for a
`single host to end up in the same output file. To support
`situations like this, the user of the MapReduce library
`can provide a special partitioning function. For example,
`using "hash(Hostname(urlkey)) mod R" as the par(cid:173)
`titioning function causes all URLs from the same host to
`end up in the same output file.
`
`4.2 Ordering Guarantees
`
`We guarantee that within a given partition, the interme(cid:173)
`diate key/value pairs are processed in increasing key or(cid:173)
`der. This ordering guarantee makes it easy to generate
`a sorted output file per partition, which is useful when
`the output file format needs to support efficient random
`access lookups by key, or users of the output find it con(cid:173)
`venient to have the data sorted.
`
`4.3 Combiner Function
`
`In some cases, there is significant repetition in the inter(cid:173)
`mediate keys produced by each map task, and the user(cid:173)
`specified Reduce function is commutative and associa(cid:173)
`tive. A good example of this is the word counting exam(cid:173)
`ple in Section 2.1. Since word frequencies tend to follow
`a Zipf distribution, each map task will produce hundreds
`or thousands of records of the form <the , 1 >. All of
`these counts will be sent over the network to a single re(cid:173)
`duce task and then added together by the Reduce function
`to produce one number. We allow the user to specify an
`optional Combiner function that does partial merging of
`this data before it is sent over the network.
`The Combiner function is executed on each machine
`that performs a map task. Typically the same code is used
`to implement both the combiner and the reduce func(cid:173)
`tions. The only difference between a reduce function and
`a combiner function is how the MapReduce library han(cid:173)
`dles the output of the function. The output of a reduce
`function is written to the final output file. The output of
`a combiner function is written to an intermediate file that
`will be sent to a reduce task.
`Partial combining significantly speeds up certain
`classes of MapReduce operations. Appendix A contains
`an example that uses a combiner.
`
`4.4
`
`Input and Output Types
`
`The MapReduce library provides support for reading in(cid:173)
`put data in several different formats. For example, "text"
`
`I To appear in OSDI 2004 I
`
`6
`
`Databricks R2 PA 00000334
`-
`-
`-
`
`

`

`Case 4:23-cv-01147-ALM Document 62-10 Filed 11/12/24 Page 8 of 14 PageID #:
`4575
`
`mode input treats each line as a key/value pair: the key
`is the offset in the file and the value is the contents of
`the line. Another common supported format stores a
`sequence of key/value pairs sorted by key. Each input
`type implementation knows how to split itself into mean(cid:173)
`ingful ranges for processing as separate map tasks (e.g.
`text mode's range splitting ensures that range splits oc(cid:173)
`cur only at line boundaries). Users can add support for a
`new input type by providing an implementation of a sim(cid:173)
`ple reader interface, though most users just use one of a
`small number of predefined input types.
`A reader does not necessarily need to provide data
`read from a file. For example, it is easy to define a reader
`that reads records from a database, or from data struc(cid:173)
`tures mapped in memory.
`In a similar fashion, we support a set of output types
`for producing data in different formats and it is easy for
`user code to add support for new output types.
`
`4.5 Side-effects
`
`In some cases, users of MapReduce have found it con(cid:173)
`venient to produce auxiliary files as additional outputs
`from their map and/or reduce operators. We rely on the
`application writer to make such side-effects atomic and
`idempotent. Typically the application writes to a tempo(cid:173)
`rary file and atomically renames this file once it has been
`fully generated.
`We do not provide support for atomic two-phase com(cid:173)
`mits of multiple output files produced by a single task.
`Therefore, tasks that produce multiple output files with
`cross-file consistency requirements should be determin(cid:173)
`istic. This restriction has never been an issue in practice.
`
`4.6 Skipping Bad Records
`
`Sometimes there are bugs in user code that cause the Map
`or Reduce functions to crash deterministically on certain
`records. Such bugs prevent a MapReduce operation from
`completing. The usual course of action is to fix the bug,
`but sometimes this is not feasible; perhaps the bug is in
`a third-party library for which source code is unavail(cid:173)
`able. Also, sometimes it is acceptable to ignore a few
`records, for example when doing statistical analysis on
`a large data set. We provide an optional mode of execu(cid:173)
`tion where the MapReduce library detects which records
`cause deterministic crashes and skips these records in or(cid:173)
`der to make forward progress.
`Each worker process installs a signal handler that
`catches segmentation violations and bus errors. Before
`invoking a user Map or Reduce operation, the MapRe(cid:173)
`duce library stores the sequence number of the argument
`in a global variable. If the user code generates a signal,
`
`the signal handler sends a "last gasp" UDP packet that
`contains the sequence number to the MapReduce mas(cid:173)
`ter. When the master has seen more than one failure on
`a particular record, it indicates that the record should be
`skipped when it issues the next re-execution of the corre(cid:173)
`sponding Map or Reduce task.
`
`4. 7 Local Execution
`
`Debugging problems in Map or Reduce functions can be
`tricky, since the actual computation happens in a dis(cid:173)
`tributed system, often on several thousand machines,
`with work assignment decisions made dynamically by
`the master. To help facilitate debugging, profiling, and
`small-scale testing, we have developed an alternative im(cid:173)
`plementation of the MapReduce library that sequentially
`executes all of the work for a MapReduce operation on
`the local machine. Controls are provided to the user so
`that the computation can be limited to particular map
`tasks. Users invoke their program with a special flag and
`can then easily use any debugging or testing tools they
`find useful (e.g. gdb).
`
`4.8 Status Information
`
`The master runs an internal HTTP server and exports
`a set of status pages for human consumption. The sta(cid:173)
`tus pages show the progress of the computation, such as
`how many tasks have been completed, how many are in
`progress, bytes of input, bytes of intermediate data, bytes
`of output, processing rates, etc. The pages also contain
`links to the standard error and standard output files gen(cid:173)
`erated by each task. The user can use this data to pre(cid:173)
`dict how long the computation will take, and whether or
`not more resources should be added to the computation.
`These pages can also be used to figure out when the com(cid:173)
`putation is much slower than expected.
`In addition, the top-level status page shows which
`workers have failed, and which map and reduce tasks
`they were processing when they failed. This informa(cid:173)
`tion is useful when attempting to diagnose bugs in the
`user code.
`
`4.9 Counters
`
`The MapReduce library provides a counter facility to
`count occurrences of various events. For example, user
`code may wan