Batch processing

Small programs that each do one thing well, composed with pipes into larger jobs.

Because every tool reads and writes the same thing, tools written decades apart compose freely, and you can inspect any intermediate stage by cutting the pipe. MapReduce is the same idea spread over many machines.

Every program takes stdin and writes stdout as a stream of newline-separated records; MapReduce uses files in a distributed filesystem the same way.

A shared interface is what makes composition possible. It also separates logic from wiring: a program does not care where its input came from or where its output goes.

Counting by sorting so equal keys are adjacent, as opposed to holding a hash table of counts in memory.

A hash table is fast while the distinct keys fit in RAM. Sorting can spill to disk and merge sorted runs, so it scales past memory, which is why MapReduce is built around sorting.

A shared-nothing filesystem: a daemon on each machine stores blocks, a central NameNode tracks where they are, and blocks are replicated.

It is the stdin/stdout of MapReduce. Jobs read input and write output as files in it, and the scheduler runs each map task on a machine that already holds that block (data locality).

A programming model and framework: a user-defined mapper extracts key-value pairs from each record, the framework sorts and groups them by key, and a reducer processes all the values for each key.

You write two callbacks that each see a small piece of the data, and the framework handles parallelism, moving data between machines and retrying failures. Each job is a single map-sort-reduce, so real work is chained into workflows.

Partitioning mapper output by a hash of the key, sorting it, and copying each partition from every mapper to its reducer.

It guarantees every value for a key reaches the same reducer, and it is the most expensive part of most jobs: an all-to-all copy over the network. Combiners shrink it by pre-aggregating on the mapper.

Mappers emit the join key from both inputs, the shuffle brings all records with that key to one reducer, and the reducer joins them.

It needs no assumptions about the inputs, and each reducer only holds one key's records at a time. The price is sorting, copying and merging every input record.

Arranging reducer input so that, within one key, records arrive in a chosen order, e.g. the profile record first and then events by timestamp.

With the record you join against arriving first, the reducer can stream the rest past it with constant memory instead of buffering them.

A few keys (a celebrity's user id) have far more records than the rest, so one reducer gets much more work.

The job finishes only when the slowest reducer does. Skewed joins sample for hot keys, spread their records across several reducers, and copy the other side of the join to each of them.

A map-side join: the small input is loaded entirely into an in-memory hash table in every mapper, which then streams its block of the large input and looks keys up.

No reducers, no sort and no shuffle, so it is much faster. It only works when one side is small enough to fit in each mapper's memory.

A map-side join for two inputs already partitioned the same way on the join key: mapper i joins partition i of each input.

Each mapper only needs one partition of the smaller side in memory. It relies on how the inputs were written earlier, so it needs the partitioning recorded as metadata (Hive bucketed map joins).

Batch jobs write fresh files (search indexes, key-value database files) rather than mutating a live database; readers switch to the new output atomically.

Bad code costs a re-run or a rollback, not corrupted data (human fault tolerance). Building files in bulk is also far faster than one network write per record, and it doesn't overload production databases.

A chain of jobs where each job's output directory is the next one's input, managed by a scheduler that runs them in dependency order.

Most real analyses take dozens of MapReduce jobs. Since each output is a file, any stage can be rerun or inspected on its own.

Writing each job's full output to the distributed filesystem, replicated, before the next job may start.

It makes fault tolerance simple (just rerun the failed task), but every intermediate dataset is written and replicated, and a stage cannot start until the slowest task of the previous one is done.

An engine that runs a whole workflow as one job: a graph of operators that hand data to each other directly, sorting only where needed.

Operators can start as soon as input arrives, intermediate data stays in memory or on local disk, and there is no repeated task start-up. That makes it much faster than a chain of MapReduce jobs.

Fault tolerance without materialization: lost data is rebuilt by rerunning the operators that produced it, starting from input that is still available.

Avoids writing intermediate state at all, but a failure late in a long pipeline can mean a lot of recomputation, and operators must be deterministic so the rebuilt data matches what was lost. Checkpoints bound the cost.

A graph processing model: in each superstep every vertex processes messages sent to it, updates its state, and sends messages along its edges.

Iterative graph algorithms like PageRank don't fit one MapReduce pass. Pregel keeps vertex state in memory between iterations, and a checkpoint after each superstep gives fault tolerance.

Relational-style operators (join, filter, group by) and SQL on top of the engines, instead of hand-written map and reduce functions.

Less code, and a query optimizer can choose the join algorithm (broadcast vs sort-merge) and push filters down. Unlike an MPP database, it still lets you run arbitrary code over arbitrary file formats.