Batch Processing

Chapter 1: Unix Philosophy

Before MapReduce, before Hadoop, before Spark — there was the Unix command line. The original batch processing system. And it embodies design principles that every modern data processing framework copied, whether they admit it or not.

The Four Tenets

Doug McIlroy, the inventor of Unix pipes, described the philosophy in 1978:

The uniform interface is the crucial innovation. Every program reads from stdin (standard input) and writes to stdout (standard output). The pipe (|) connects one program's stdout to another's stdin. No serialization format negotiation, no protocol handshakes, no schema definitions — just bytes flowing through a pipeline.

A Complete Example: Analyzing Access Logs

A standard Apache access log looks like this:

text
216.58.214.206 - - [17/May/2026:10:05:03 +0000] "GET /api/users HTTP/1.1" 200 3428
192.168.1.42  - - [17/May/2026:10:05:04 +0000] "GET /index.html HTTP/1.1" 200 12054
10.0.0.15     - - [17/May/2026:10:05:04 +0000] "POST /api/login HTTP/1.1" 302 0
216.58.214.206 - - [17/May/2026:10:05:05 +0000] "GET /api/users HTTP/1.1" 200 3428
192.168.1.42  - - [17/May/2026:10:05:06 +0000] "GET /about.html HTTP/1.1" 200 8192

To find the top 5 most-visited URLs:

bash
cat access.log       \  # Read all lines
  | awk '{print $7}' \  # Extract field 7 (the URL path)
  | sort              \  # Sort alphabetically: groups identical URLs together
  | uniq -c           \  # Count consecutive identical lines
  | sort -rn          \  # Sort numerically (-n), reversed (-r) = highest first
  | head -5           \  # Take the first 5 lines

Let us trace the data through every stage:

Why sort Can Handle Datasets Bigger Than RAM

The sort command does not load the entire file into memory. It uses external merge sort:

This algorithm reads and writes the data exactly twice: once to create sorted chunks, once to merge them. The total I/O is 2N, and it works for arbitrarily large files. The same idea appears in MapReduce's shuffle phase.

Why Unix Pipes Do Not Scale Beyond One Machine

The Unix pipeline is elegant but limited in three fundamental ways:

Worked Example: External Merge Sort With Numbers

Let us trace through an external merge sort with a concrete example to make the algorithm crystal clear. Say we have 12 numbers to sort but only enough memory for 4 at a time.

This exact algorithm runs inside sort when you pipe a 100 GB file through it. Instead of 4 numbers, it sorts 4 GB chunks. Instead of 3 files, it might merge 25. But the logic is identical.

Chapter 2: MapReduce Basics

In 2004, Jeff Dean and Sanjay Ghemawat at Google published the paper that changed data processing forever. Their insight was simple: most batch computations can be expressed as two functions — map and reduce — and if you constrain yourself to this API, the framework can handle all the hard parts (parallelism, fault tolerance, data distribution) automatically.

The Two Functions

Map takes one input record and emits zero or more key-value pairs. It runs independently on each input record with no shared state between records. This is what makes it trivially parallelizable — if you have 1000 input records and 10 machines, each machine can map 100 records with zero coordination.

Reduce takes a key and all the values associated with that key, and combines them into a single output. Every value with the same key is guaranteed to go to the same reducer. This is the aggregation step.

Between map and reduce sits the shuffle: the framework sorts and groups all map output by key, sending each key's values to the appropriate reducer. This is the expensive part — it requires network transfer across the cluster.

The Canonical Example: Word Count

Count how many times each word appears in a set of documents. This is the "Hello World" of MapReduce.

Let us trace this through a concrete example with three input documents (three map tasks):

Interactive MapReduce

Why This API Is Powerful

The map/reduce constraint seems limiting — you can only express computations as stateless transformations (map) followed by keyed aggregations (reduce). But this constraint is exactly what enables the framework to:

Python Implementation

python
from collections import defaultdict

# ── Map function: takes a document string, yields (key, value) pairs ──
def mapper(document):
    for word in document.lower().split():
        yield (word, 1)

# ── Reduce function: takes a key and list of values, yields (key, result) ──
def reducer(word, counts):
    return (word, sum(counts))

# ── Simulate MapReduce locally ──
documents = [
    "the cat sat on the mat",
    "the dog sat on the log",
    "the cat and the dog",
]

# MAP PHASE: run mapper on each document (in parallel in real MR)
map_output = []
for doc in documents:
    map_output.extend(mapper(doc))
# map_output = [('the',1), ('cat',1), ('sat',1), ('on',1), ...]

# SHUFFLE PHASE: group by key
shuffled = defaultdict(list)
for key, value in map_output:
    shuffled[key].append(value)
# shuffled = {'the': [1,1,1,1,1,1], 'cat': [1,1], ...}

# REDUCE PHASE: aggregate each group (in parallel in real MR)
results = []
for word, counts in sorted(shuffled.items()):
    results.append(reducer(word, counts))
# results = [('and',1), ('cat',2), ('dog',2), ('log',1),
#            ('mat',1), ('on',2), ('sat',2), ('the',6)]

for word, count in sorted(results, key=lambda x: -x[1]):
    print(f"{word}: {count}")

Chapter 3: MapReduce in Depth

The word count example shows the API. Now let us look under the hood at how the framework actually executes a MapReduce job across a cluster of machines.

HDFS: Where the Data Lives

MapReduce is tightly coupled with the Hadoop Distributed File System (HDFS). HDFS splits every file into blocks (default 128 MB each) and replicates each block to 3 different machines. A 1 TB file becomes ~8,000 blocks spread across the cluster.

The key property: HDFS knows which machine holds which block. The MapReduce scheduler uses this to achieve data locality — it assigns each map task to a machine that already holds the input block. The data does not cross the network. The code goes to the data, not the other way around.

Anatomy of a MapReduce Job

The Cluster in Action

Failure Handling: The Three Cases

Speculative Execution: Dealing with Stragglers

In a cluster of 1,000 machines, some will be slow. A failing disk, a noisy neighbor (another process stealing CPU), or a hot CPU throttling can make one task take 10x longer than the rest. The entire job waits for the slowest task.

Speculative execution detects tasks that are running much slower than average and launches a duplicate copy on another machine. Whichever copy finishes first is used; the other is killed. This wastes a small amount of cluster resources but can dramatically reduce job completion time.

Python MapReduce: Complete Implementation

python
import os, sys, hashlib, json, multiprocessing
from collections import defaultdict
from functools import reduce as functools_reduce

class MapReduceFramework:
    """A simplified MapReduce framework running on a single machine
    using multiprocessing to simulate distributed execution."""

    def __init__(self, num_mappers=4, num_reducers=2):
        self.num_mappers = num_mappers
        self.num_reducers = num_reducers

    def _partition(self, key):
        # Deterministic partition: same key always goes to same reducer
        return int(hashlib.md5(key.encode()).hexdigest(), 16) % self.num_reducers

    def _map_worker(self, split, mapper_fn):
        # Group map output by target reducer
        partitions = defaultdict(list)
        for record in split:
            for key, value in mapper_fn(record):
                r = self._partition(key)
                partitions[r].append((key, value))
        # Sort each partition by key (simulates map-side sort)
        for r in partitions:
            partitions[r].sort(key=lambda x: x[0])
        return dict(partitions)

    def run(self, data, mapper_fn, reducer_fn):
        # Split data across mappers
        splits = [[] for _ in range(self.num_mappers)]
        for i, record in enumerate(data):
            splits[i % self.num_mappers].append(record)

        # MAP phase (would be parallel on a real cluster)
        map_outputs = [self._map_worker(s, mapper_fn) for s in splits]

        # SHUFFLE phase: collect each reducer's data from all mappers
        reducer_inputs = defaultdict(list)
        for mo in map_outputs:
            for r, pairs in mo.items():
                reducer_inputs[r].extend(pairs)

        # Sort each reducer's input by key (merge phase)
        for r in reducer_inputs:
            reducer_inputs[r].sort(key=lambda x: x[0])

        # REDUCE phase: group by key, call reducer
        results = []
        for r in sorted(reducer_inputs.keys()):
            groups = defaultdict(list)
            for key, value in reducer_inputs[r]:
                groups[key].append(value)
            for key in sorted(groups.keys()):
                result = reducer_fn(key, groups[key])
                if result is not None:
                    results.append(result)
        return results

# ── Usage ──
def word_mapper(line):
    for word in line.lower().split():
        yield (word, 1)

def word_reducer(word, counts):
    return (word, sum(counts))

mr = MapReduceFramework(num_mappers=3, num_reducers=2)
data = ["the cat sat on the mat",
        "the dog sat on the log",
        "the cat and the dog"]
results = mr.run(data, word_mapper, word_reducer)
for word, count in sorted(results, key=lambda x: -x[1]):
    print(f"{word}: {count}")
# Output: the: 6, cat: 2, dog: 2, on: 2, sat: 2, and: 1, log: 1, mat: 1

Worked Example: The Combiner in Action

The combiner is one of the most important optimizations in MapReduce. Let us trace its effect on a concrete word count example to see exactly how much data it saves during the shuffle.

The Combiner in Python

python
from collections import defaultdict

def map_with_combiner(document, combiner_fn=None):
    """Simulate a mapper with optional local combiner."""
    # Map phase: emit (word, 1) for each word
    map_output = []
    for word in document.lower().split():
        map_output.append((word, 1))

    if combiner_fn is None:
        return map_output  # No combiner: send all pairs

    # Combiner: group locally and apply combiner function
    local_groups = defaultdict(list)
    for key, value in map_output:
        local_groups[key].append(value)

    combined = []
    for key, values in local_groups.items():
        combined.append((key, combiner_fn(values)))
    return combined

# Without combiner
doc = "the cat sat on the mat the cat sat on the mat"
no_combiner = map_with_combiner(doc)
print(f"Without combiner: {len(no_combiner)} pairs")
# 12 pairs: (the,1)(cat,1)(sat,1)(on,1)(the,1)(mat,1)...

# With combiner (sum)
with_combiner = map_with_combiner(doc, combiner_fn=sum)
print(f"With combiner: {len(with_combiner)} pairs")
# 5 pairs: (the,4)(cat,2)(sat,2)(on,2)(mat,2)
print(f"Shuffle data reduced by {100*(1-len(with_combiner)/len(no_combiner)):.0f}%")
# Shuffle data reduced by 58%

Chapter 4: Joins in MapReduce

Word count is nice for tutorials. In the real world, the hard problem is joins. You have a table of user click events (billions of rows: user_id, timestamp, url, ...) and a table of user profiles (millions of rows: user_id, name, country, signup_date, ...). You need to produce a combined dataset: each click event enriched with the user's country. This is a join on user_id.

In SQL, you just write SELECT * FROM events JOIN profiles ON events.user_id = profiles.user_id. In MapReduce, you have to implement the join yourself. There are three strategies, each with different tradeoffs.

Strategy 1: Reduce-Side Join (Sort-Merge Join)

The most general approach. Both datasets go through the same MapReduce job. Mappers tag each record with its source (events vs profiles), and the shuffle brings all records with the same user_id to the same reducer.

Strategy 2: Map-Side Join (Broadcast Join)

If one dataset is small enough to fit in memory (the profiles table at a few hundred MB), you can skip the shuffle entirely. Load the small table into a hash map in every mapper. For each event, look up the user_id in the hash map.

This is vastly faster because there is no shuffle (no network transfer of the large events table). The tradeoff: the small table must fit in memory on every mapper node.

Strategy 3: Map-Side Merge Join

If both datasets are already sorted by the join key and partitioned the same way (e.g., both are output of a previous MapReduce job with the same number of reducers and same partitioning function), you can do a merge join in the mapper with no shuffle. Each mapper reads the corresponding partition of both datasets and merges them in sorted order. This is the fastest join but requires the most stringent preconditions.

The Skew Problem

A reduce-side join works beautifully until one key has massively more values than the rest. Imagine a social network where user_id = "taylor_swift" has 500 million follower events. All 500 million records go to one reducer, while other reducers handle 10,000 records each. That one reducer runs for hours while the others finish in minutes.

This is data skew, and it is the single most common cause of slow MapReduce jobs in production.

Worked Example: Join Events with Profiles

python
from collections import defaultdict

# ── Sample data ──
events = [
    {"user_id": 1, "url": "/home",  "ts": "10:05"},
    {"user_id": 2, "url": "/buy",   "ts": "10:06"},
    {"user_id": 1, "url": "/about", "ts": "10:07"},
    {"user_id": 3, "url": "/home",  "ts": "10:08"},
    {"user_id": 2, "url": "/cart",  "ts": "10:09"},
]
profiles = [
    {"user_id": 1, "name": "Alice", "country": "US"},
    {"user_id": 2, "name": "Bob",   "country": "UK"},
    {"user_id": 3, "name": "Carol", "country": "JP"},
]

# ── REDUCE-SIDE JOIN ──
# Map phase: tag each record with its source
map_output = []
for e in events:
    map_output.append((e["user_id"], ("event", e)))
for p in profiles:
    map_output.append((p["user_id"], ("profile", p)))

# Shuffle: group by user_id
groups = defaultdict(list)
for uid, record in map_output:
    groups[uid].append(record)

# Reduce: join
for uid in sorted(groups.keys()):
    records = groups[uid]
    profile = None
    user_events = []
    for tag, data in records:
        if tag == "profile":
            profile = data
        else:
            user_events.append(data)
    for ev in user_events:
        print({**ev, "name": profile["name"], "country": profile["country"]})
# {user_id:1, url:/home, ts:10:05, name:Alice, country:US}
# {user_id:1, url:/about, ts:10:07, name:Alice, country:US}
# {user_id:2, url:/buy, ts:10:06, name:Bob, country:UK}
# ... etc

# ── MAP-SIDE JOIN (broadcast) ──
profile_map = {p["user_id"]: p for p in profiles}
for ev in events:
    p = profile_map.get(ev["user_id"])
    if p:
        print({**ev, "name": p["name"], "country": p["country"]})
# Same output, but no shuffle needed!

Chapter 5: Beyond MapReduce

MapReduce launched the big data revolution in 2004. By 2012, its limitations were painfully clear. The industry moved on to dataflow engines — Spark, Flink, and Tez — that kept MapReduce's strengths (fault tolerance, horizontal scaling) while fixing its worst inefficiencies.

MapReduce's Three Pain Points

Pain 1: Materialization between stages. A real-world computation rarely fits into one MapReduce job. Finding the top URLs per country requires: Job 1 (extract URL + country, count), Job 2 (find top per country). Between jobs, the intermediate results are written to HDFS. That means: serialize to disk, replicate 3x across the network, then read back from disk for the next job. For a pipeline with 5 stages, the intermediate data is written and read 4 times unnecessarily.

Pain 2: No support for iteration. Machine learning algorithms (gradient descent, PageRank, k-means) iterate: apply a transformation, check convergence, repeat. In MapReduce, each iteration is a separate job. Each job writes to HDFS and the next reads from HDFS. Training a model for 100 iterations means 100 rounds of disk I/O for data that could just stay in memory.

Pain 3: Rigid Map-then-Reduce structure. Not every computation fits the two-stage pattern. What if you need map → reduce → map → reduce → map? Each arrow is a separate job with full HDFS materialization. MapReduce chains are awkward and slow.

Dataflow Engines: The Big Idea

Instead of the rigid map → shuffle → reduce pipeline, dataflow engines model computation as a directed acyclic graph (DAG) of operators. Any operator can connect to any other. Data flows through the graph, pipelined in memory when possible.

Spark's Key Abstraction: RDDs

Apache Spark (Zaharia et al., 2012) introduced the Resilient Distributed Dataset (RDD). An RDD is a read-only, partitioned collection of records with a recorded lineage — the sequence of transformations that produced it from the original input data.

Lineage is the secret to fault tolerance without HDFS writes. If a partition of an RDD is lost (because a node crashes), Spark recomputes it by replaying the lineage from the last materialized ancestor. It only recomputes the lost partition, not the entire dataset.

Fault Tolerance: Lineage vs Replication

MapReduce achieves fault tolerance through replication: intermediate data is written to disk (and HDFS replicates the input 3x). If anything fails, the data is still there.

Spark achieves fault tolerance through lineage: intermediate data is NOT written to disk (it stays in memory). If a partition is lost, Spark reconstructs it by replaying the transformations from the last materialized point (usually the original HDFS input). This is cheaper than replication as long as the lineage is short. For very long lineages (100+ transformations), Spark provides checkpointing: manually write an RDD to HDFS to truncate the lineage chain.

Chapter 6: Spark Deep Dive

Spark is not just "faster MapReduce." It is a complete rethinking of how distributed data processing should work. Let us dig into the mechanics.

Transformations vs Actions

Transformations are lazy — they define a computation but do not execute it. They return a new RDD (or DataFrame). Actions are eager — they trigger execution of the entire lineage DAG and return a result or write to storage.

The DAG and Stage Execution

When you call an action, Spark's DAG scheduler examines the lineage graph and breaks it into stages at every wide dependency (shuffle boundary). Within a stage, all narrow transformations are fused into a single task that processes one partition end-to-end without writing intermediate data.

Caching and Persistence

If you use an RDD multiple times (e.g., iterate over it in a loop), Spark recomputes it from scratch each time by default. To avoid this, you can cache (or persist) an RDD in memory. The first action materializes it; subsequent actions read from the cache.

Persistence levels control where cached data goes:

Broadcast Variables and Accumulators

Broadcast variables are Spark's version of the map-side broadcast join. You take a small dataset on the driver, broadcast it to all executors, and each task can look it up locally.

Accumulators are write-only shared variables for distributed counters and sums. Each task can add to an accumulator, but only the driver can read the final value.

The groupByKey vs reduceByKey Trap

This is probably the single most common performance mistake in Spark. Both operations group data by key, but they do it very differently.

groupByKey shuffles ALL values for each key to the same executor, then hands you the complete list. If key "the" appears 10 million times, a single executor receives a list of 10 million values. It must all fit in memory.

reduceByKey applies the reduce function on the map side first (like a combiner), then shuffles the partial results. If key "the" appears 10 million times across 100 partitions, each partition locally reduces its portion (100,000 occurrences each become a single count), and only 100 partial results are shuffled — not 10 million.

Complete PySpark Example

python
from pyspark.sql import SparkSession

spark = SparkSession.builder.appName("BatchProcessing").getOrCreate()
sc = spark.sparkContext

# ── 1. Word count (the basics) ──
lines = sc.textFile("hdfs://logs/access.log")
word_counts = (
    lines
    .flatMap(lambda line: line.split())  # narrow: flatMap
    .map(lambda word: (word, 1))          # narrow: map
    .reduceByKey(lambda a, b: a + b)     # wide: shuffle + reduce
)
# Stage 1: textFile → flatMap → map (pipelined, no disk)
# Stage 2: reduceByKey (shuffle boundary)

top_10 = word_counts.sortBy(lambda x: -x[1]).take(10)

# ── 2. Join with broadcast (map-side join) ──
profiles = {1: "US", 2: "UK", 3: "JP"}  # small lookup table
bc_profiles = sc.broadcast(profiles)       # send to all executors

events = sc.parallelize([
    (1, "/home"), (2, "/buy"), (1, "/about"),
    (3, "/home"), (2, "/cart"),
])

enriched = events.map(
    lambda x: (x[0], x[1], bc_profiles.value.get(x[0], "?"))
)
# (1, '/home', 'US'), (2, '/buy', 'UK'), ...
# No shuffle! The broadcast variable is on every executor.

# ── 3. Multi-stage aggregation ──
# Top 5 URLs per country
from pyspark.sql import functions as F
from pyspark.sql.window import Window

df = spark.createDataFrame(
    enriched.collect(),
    ["user_id", "url", "country"]
)
url_counts = df.groupBy("country", "url").count()
w = Window.partitionBy("country").orderBy(F.desc("count"))
top_urls = url_counts.withColumn("rank", F.row_number().over(w))
top_urls.filter(F.col("rank") <= 5).show()

Chapter 7: Graph Processing — The Showcase

Not all data is tables and key-value pairs. Many of the most important batch processing problems are graphs: the web link graph (PageRank), social networks (friend recommendations), road networks (shortest paths), and knowledge graphs (entity resolution). These require iterative algorithms that MapReduce handles poorly.

PageRank: The Algorithm That Built Google

Larry Page's insight: a web page is important if many important pages link to it. This circular definition becomes a linear algebra problem. Assign each page a rank. On each iteration, each page distributes its rank equally among all pages it links to. After enough iterations, the ranks converge.

The damping factor d = 0.85 models a random web surfer who follows links 85% of the time and jumps to a random page 15% of the time. Without it, pages with no outgoing links (sink nodes) would absorb all the rank.

The Pregel Model: Thinking Like a Vertex

Google's Pregel framework (2010) introduced a vertex-centric programming model. Instead of thinking about the global graph, you write code from the perspective of a single vertex:

This is the Bulk Synchronous Parallel (BSP) model: all vertices execute in lockstep. Superstep k completes before superstep k+1 begins. Messages sent in superstep k are delivered in superstep k+1.

PageRank in Pregel

Interactive PageRank Simulation

This is the showcase. You have a small graph of 8 pages with directed links between them. Click "Step" to run one Pregel superstep. Watch the PageRank values converge. The node with the highest rank grows larger. Messages (rank shares) animate along edges between supersteps.

Python PageRank Implementation

python
import numpy as np

def pagerank(edges, num_nodes, damping=0.85, iterations=30):
    """Compute PageRank using power iteration.

    Args:
        edges: list of (source, target) pairs
        num_nodes: total number of nodes
        damping: probability of following a link (vs random jump)
        iterations: number of iterations

    Returns:
        ranks: array of PageRank values (sum = 1.0)
    """
    # Build adjacency: out_neighbors[u] = list of nodes u links to
    out_neighbors = [[] for _ in range(num_nodes)]
    for src, dst in edges:
        out_neighbors[src].append(dst)

    # Initialize: uniform rank
    ranks = np.full(num_nodes, 1.0 / num_nodes)

    for iteration in range(iterations):
        new_ranks = np.full(num_nodes, (1.0 - damping) / num_nodes)

        for u in range(num_nodes):
            if len(out_neighbors[u]) > 0:
                share = ranks[u] / len(out_neighbors[u])
                for v in out_neighbors[u]:
                    new_ranks[v] += damping * share
            else:
                # Sink node: distribute rank to ALL nodes (random jump)
                new_ranks += damping * ranks[u] / num_nodes

        ranks = new_ranks
        print(f"Iter {iteration}: max={ranks.max():.4f}, "
              f"node={ranks.argmax()}, sum={ranks.sum():.4f}")

    return ranks

# Example: 5-node web graph
edges = [
    (0, 1), (0, 2),  # page 0 links to 1 and 2
    (1, 2),          # page 1 links to 2
    (2, 0),          # page 2 links to 0
    (3, 2),          # page 3 links to 2
    (4, 0), (4, 2),  # page 4 links to 0 and 2
]
ranks = pagerank(edges, num_nodes=5, damping=0.85, iterations=20)
# Node 2 gets the highest rank: many pages link to it
for i, r in enumerate(ranks):
    print(f"Page {i}: {r:.4f}")

PageRank in Spark

python
# Spark PageRank: iterative computation with caching
links = sc.parallelize([
    (0, [1, 2]), (1, [2]), (2, [0]),
    (3, [2]), (4, [0, 2]),
]).cache()  # CRITICAL: cache the graph structure. Without this,
           # Spark re-reads from HDFS every iteration.

N = 5
ranks = sc.parallelize([(i, 1.0 / N) for i in range(N)])

for _ in range(20):
    # Join ranks with links: (node, (rank, neighbors))
    contribs = links.join(ranks).flatMap(
        lambda x: [(n, x[1][0][1] / len(x[1][0][0])) for n in x[1][0][0]]
    )  # Error: this is getting complex. Use clear variable names:

# Cleaner version with named operations:
for _ in range(20):
    contribs = (
        links.join(ranks)
        # Each element: (node, ([neighbors], rank))
        .flatMap(lambda node_data: [
            (neighbor, node_data[1][1] / len(node_data[1][0]))
            for neighbor in node_data[1][0]
        ])
    )
    ranks = contribs.reduceByKey(lambda a, b: a + b).mapValues(
        lambda r: 0.15 / N + 0.85 * r
    )

results = ranks.collect()

Chapter 8: Batch Processing in Practice

Theory is nice. Now let us talk about the real-world problems you will face building and operating batch pipelines at scale.

Common Batch Processing Use Cases

Framework Comparison

Design Challenge: Daily Clickstream ETL

You are designing an ETL pipeline that processes 100 TB of clickstream data daily. The raw data arrives as compressed JSON in S3, one file per web server per hour (500 servers × 24 hours = 12,000 files). The output is a cleaned, partitioned Parquet dataset in a data lake, partitioned by date and country.

Common Failure Modes and Debugging

File Formats: The Hidden Performance Lever

The choice of file format can make a 10x difference in batch job performance. Most teams do not think about this enough.

Anti-Patterns: What Not to Do

Chapter 9: Interview Arsenal

This chapter distills everything into interview-ready formats: cheat sheets, system design skeletons, and coding drills.

Five-Dimensional Cheat Sheet

System Design Templates

Coding Drills

python
# DRILL 1: Implement MapReduce word count from scratch
# (See Chapter 2 for the full implementation)

# DRILL 2: Implement a basic inverted index
from collections import defaultdict

def build_inverted_index(documents):
    """Build an inverted index from a dict of {doc_id: text}.

    Returns: {word: [(doc_id, term_frequency), ...]}
    """
    index = defaultdict(list)
    for doc_id, text in documents.items():
        words = text.lower().split()
        tf = defaultdict(int)
        for w in words:
            tf[w] += 1
        for word, count in tf.items():
            index[word].append((doc_id, count))
    # Sort posting lists by term frequency (descending)
    for word in index:
        index[word].sort(key=lambda x: -x[1])
    return dict(index)

docs = {
    "d1": "the cat sat on the mat",
    "d2": "the dog sat on the log",
    "d3": "the cat and the dog",
}
idx = build_inverted_index(docs)
print(idx["the"])   # [('d1', 2), ('d2', 2), ('d3', 2)]
print(idx["cat"])   # [('d1', 1), ('d3', 1)]
print(idx["dog"])   # [('d2', 1), ('d3', 1)]

# DRILL 3: Implement PageRank
# (See Chapter 7 for the full implementation)

The "Design a Batch Pipeline" Interview Framework

When you get a system design question involving batch processing, follow this structure:

Quick-Fire Interview Q&A

Recommended Reading

Chapter 10: Connections

Batch processing does not exist in isolation. It connects to every other part of the data infrastructure.

Where Batch Fits in the Data Landscape

The Evolution of Batch Processing

The Lambda and Kappa Architectures

Two competing approaches to combining batch and stream processing:

The Big Picture

When to Use What: A Decision Framework

"The art of programming is the art of organizing complexity." — Edsger W. Dijkstra