CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 6 of 7 · 5 min read

What batch jobs produce, and what came after MapReduce

Output is built as whole new files and swapped in. Newer engines avoid writing every step to disk.

What batch jobs produce, and what came after MapReduce

Think of a printing press. A new edition is printed in full, checked, and then swapped for the old one on the shelves. The old edition stays in the warehouse in case the new one has errors.

DDIA explains what batch output is for. It is not usually a report. Google's first use of MapReduce was to build the search index, a workflow of 5 to 10 jobs. Mappers split the documents and reducers build the index for each partition. Index files are immutable once written. When documents change, the simplest approach is to rerun the whole job and replace the old index. It costs a lot if few documents changed, but it is very easy to reason about: documents in, index out.

Another output is a key-value store for the web application, for example suggested friends per user. The book calls the obvious approach, writing from inside each mapper to the live database record by record, a bad idea for three reasons:

  • One network request per record is far slower than the task's natural speed.
  • Many tasks in parallel can overwhelm the database.
  • A batch job gives an all-or-nothing result, but writes to an outside system are visible at once, even from a job that later fails or is retried.

The better way is to build a brand new database as files inside the job, copy the files to the servers, and switch to them atomically. The old files remain, so switching back is easy.

This reflects a philosophy: inputs are immutable, there are no side effects, and the output replaces the old. DDIA lists the gains. A bug can be undone by rolling back the code and rerunning. The old output can be kept in another folder and switched back. Failed tasks are retried safely. The same input can feed monitoring jobs that compare each run's output with the last. The book calls the ability to recover from buggy code human fault tolerance.

Materialization

Materialization is writing the intermediate result of a computation out to storage, instead of passing it directly to the next step.

Example: the first MapReduce job writes its output to a folder in HDFS, and the second job reads that folder.

Dataflow engines. MapReduce writes every intermediate result to HDFS, where it is copied to several machines. The book lists the problems: a job cannot start until all tasks of the previous job are done, so a few slow tasks (stragglers) hold everything back; mappers often only read back what a reducer just wrote; and temporary data does not need so many copies. Engines such as Spark, Tez and Flink treat a whole workflow as one job. They are dataflow engines. Their steps (operators) can be connected in flexible ways, the expensive sort happens only where needed, operators start as soon as their input is ready, and intermediate data can stay in memory or on local disk.

Their fault tolerance differs: since intermediate data is not on HDFS, a lost piece is recomputed from earlier data. To do that, the engine must record how each piece was computed. Spark does this with an abstraction called the resilient distributed dataset (RDD). The recomputation must be deterministic. If it is not, the recomputed data may differ from what downstream operators already used.

MapReduce Dataflow engine
Unit of work One map and one reduce A whole workflow
Intermediate data Written to HDFS and replicated Memory or local disk
Sort Always between map and reduce Only where needed
Failure Rerun the task, read the stored input Recompute lost data from earlier stages

Interview angle

Answer in your head first, then open it.

What is MapReduce?

Map extracts keys and values, the shuffle groups equal keys together, and reduce processes each group. It scales by partitioning and retries failed tasks.

How do you join two huge datasets?

Sort-merge join by key. If one side is small, broadcast it. If both are partitioned the same way, use a partitioned hash join.

What is data skew?

One key with far more data than the rest. Fix with sampling and spreading hot keys over several reducers.

Why not write batch results straight into the live database?

It is slow, can overload the database, and partial results become visible. Build new files and swap.

Batch or stream?

Batch for large, periodic, repeatable computations. Stream when results are needed within seconds.

Check yourself:

  • Why does a batch job rebuild a search index instead of updating it in place?
  • Name two things dataflow engines improve over MapReduce.

Words you will meet

Word Plain meaning
Batch processing Running a job over a large fixed input and producing output
Throughput Work done per unit of time
Working set Data a job must hold in memory for random access
Pipe A link that feeds one program's output to the next
HDFS A distributed file system that stores blocks on many machines
Mapper Extracts a key and value from each record
Reducer Processes all the values of one key
Shuffle Sending mapper output to the right reducer, sorted by key
Workflow A chain of jobs where one output feeds the next
Sort-merge join Join by sorting both inputs on the key
Broadcast hash join Copy a small input to every worker as a hash table
Skew, hot key One key with far more data than others
Sessionization Grouping a user's events into sessions
Materialization Writing intermediate results to storage
Dataflow engine A system such as Spark or Flink that runs a whole workflow as one job
Human fault tolerance Recovering from buggy code by rerunning with fixed code