All projects

MapReduce-Reloaded

In active development · big data & distributed systems · Go & Python

A from-scratch rebuild of Google’s MapReduce, as described by Dean and Ghemawat in MapReduce: Simplified Data Processing on Large Clusters⁠ (OSDI 2004). Go is the main implementation. Python is a second implementation of the shared contract and of single-machine mode, so the two can be checked against each other byte for byte.

At a glance

The problem

MapReduce is the paper that made large-scale data processing ordinary. You write a map function and a reduce function, and the system handles splitting the input, scheduling thousands of tasks, moving data between machines and surviving the machines that fail along the way. Spark, Hadoop and most modern batch systems descend from it.

I wanted to understand those guarantees by building them, not by reading about them. The aim is a faithful rebuild: every feature in the paper, each with a test that proves it works, then extended with what a 2026 system would use instead of 2004 infrastructure.

Approach

A single-machine oracle first. The first working version runs the whole job in one process (mr run -local). Every later version, distributed or fault tolerant, must produce exactly the same output files. The tests check each version against it.

One contract, two languages. Go and Python share a gRPC and protobuf message contract, a documented on-disk record format with a checksum on every block, and a partition hash written out by hand in both languages. The built-in hash functions of both languages use a random seed per process, so two workers would disagree about which reducer gets a key. Test vectors and golden files hold both implementations to the same bytes.

Small, reviewable steps. Each piece of work is one issue and one pull request, and each phase adds a short design record. A make check quality gate runs every linter and test before each push. There is no hosted CI.

What I built

• The programming model and the data path (§2–§4.4). Input splitting on record boundaries, partitioning by hash(key) mod R, a combiner, an external merge sort for data larger than memory, pluggable input and output formats, and atomic commits, so a half-written output file is never visible.
• A distributed cluster (§3.1–§3.2). A coordinator keeps the task table and the location of every intermediate file. Workers ask it for tasks over gRPC, map tasks write R partition files and serve them, and reducers stream their partition from every map task.
• Fault tolerance (§3.3, §3.6, §4.6, §4.9).
  • Workers send heartbeats. A worker that misses three is declared dead, and its finished map tasks run again, because their output was on its disk.
  • The coordinator logs every decision to a write-ahead log and resumes the job after a restart. The 2004 implementation aborted the job instead.
  • Backup copies of the last slow tasks run near the end of a job, and the first copy to finish wins.
  • A record that crashes user code twice is skipped on the next attempt.
  • Counters are counted only from the winning attempt of each task, so re-run tasks do not double-count.
• Locality and status (§3.4, §4.8). The scheduler prefers to run a map task on the host that holds its input. The coordinator serves a status page, the coordinator and workers export Prometheus metrics, an optional monitoring profile adds Prometheus and a Grafana dashboard, and logs can be written as structured JSON.
• The paper’s example programs (§2.3, §5). Grep, word count, URL access frequency, reverse web-link graph, term vectors, inverted index and distributed sort, each with a test.
• A Docker Compose cluster. One coordinator and four workers, with Prometheus and Grafana as an optional profile, and a memory limit on each service so the whole cluster fits on one 8 GB virtual machine. An end-to-end script checks the cluster’s output against the oracle.

What chaos testing found

The chaos test runs word count while, at random moments, workers die, new ones join, workers stall for 50–250 ms and the coordinator restarts from its log. A run passes only if the output files and the counters equal single-machine mode. Each run’s choices come from a seed, so a failure can be replayed.

Its first runs failed on seed 7. The output held an extra _temporary directory: a reduce attempt that had already lost, to a backup copy or because its worker was declared dead, kept running and recreated the directory after the job had cleaned it up. Now the job creates that directory when it starts, and attempts never do. An attempt that runs after the job has finished fails and leaves nothing behind.

The test runs in one process, so a “dead” worker behaves like a machine cut off from the network, not one that lost power. Killing containers and dropping packets need the Compose cluster, and that driver is not written yet.

What is planned

• S3-compatible object storage, run locally with MinIO, in place of the paper’s GFS.
• Compression for intermediate and output files.
• A benchmark tool, and small-scale reruns of the paper’s §5 experiments that compare the shapes of the graphs, not the absolute numbers.
• A final report.

Further extensions, such as a full Python coordinator and worker, a standby coordinator, skew handling and Parquet input, are stretch goals and may not be built.

What I’m learning

• Build the oracle first. Once a simple version defines the right answer, every harder version is a test against it, not a judgement call.
• Write the contract down before the code. The hand-written hash exists because both languages’ built-in hashes would have sent the same key to different reducers without any error.
• Random fault injection finds bugs that one-failure-at-a-time tests miss. The seed 7 bug appeared only when a losing attempt outlived the job’s cleanup.

Stack

Go Python gRPC Protocol Buffers Docker Compose Prometheus Grafana Distributed systems