Parallelism at Scale - More Machines, More Coordination Problems

Helpful context:

• Real-Time Systems - When Missing a Deadline Is a Bug
• GPU vs TPU - Different Bets on the Shape of Computation

Count Every Word in Wikipedia

Here is a concrete problem. Wikipedia is roughly 22 GB of text. You need to count the frequency of every word. You have 2 hours and 1,000 machines. How do you split the work?

The naive answer - read the whole thing on one machine - takes several hours even with fast I/O, and one machine doesn’t have 2 hours. You need to parallelize. But parallelizing isn’t free: if each machine counts words independently and reports results, you have 1,000 partial counts that still need to be combined. How do you merge them? Who coordinates the merge? What happens if three machines crash midway?

This problem - how to apply computation to data that is too large to fit on one machine, reliably, at scale - is the fundamental problem of distributed computing. Google’s 2004 MapReduce paper was the first widely adopted answer. Everything since is a variation on the same theme.

The MapReduce Insight

The Google MapReduce paper (Dean and Ghemawat, 2004) made a specific observation: a huge fraction of large-scale data processing can be decomposed into two operations.

Map: apply a function to each element of the input independently, producing zero or more key-value pairs. For word count: input is a line of text; output is one (word, 1) pair per word. Each mapper handles a chunk of input independently. No coordination needed.

Reduce: for each unique key, aggregate all the values associated with that key. For word count: for every unique word, sum all the 1s. Each reducer handles one key (or a range of keys). No coordination needed - within a reducer.

The brilliance is what happens in between. The shuffle phase collects all the output from all mappers and routes each key’s values to the correct reducer. The MapReduce framework handles this automatically: sorting, partitioning, network transfer, and fault tolerance. The programmer writes map and reduce functions; the framework handles the rest.

For word count:

1. Split Wikipedia across 1,000 mappers. Each mapper reads its chunk and emits (word, 1) pairs.
2. The framework shuffles: it sorts all intermediate (word, 1) pairs by key and routes each word’s pairs to one reducer. All (the, 1) pairs go to the same reducer.
3. Each reducer sums its values: (the, 1), (the, 1), (the, 1)... becomes (the, 4,523,821).

The programmer wrote roughly 10 lines of code. The framework handled fault tolerance (if a mapper crashes, re-run that task on another machine), data locality (try to run mappers on machines that already have the data), and the entire network transfer. This was genuinely revolutionary in 2004.

Why Hadoop Lost to Spark

Hadoop was the open-source reimplementation of MapReduce that became the dominant big data platform from roughly 2008 to 2015. It worked. Thousands of organizations ran production Hadoop clusters. And then Spark came along and largely replaced it.

The reason is disk. Hadoop MapReduce writes intermediate results to disk after every step. A pipeline with ten MapReduce stages - ETL, filtering, aggregation, joining, more aggregation - writes to disk ten times and reads from disk ten times. Disk I/O is slow. The latency of a complex Hadoop job was measured in hours.

Apache Spark (developed at UC Berkeley AMPLab, 2009-2012) asked: what if the intermediate results live in memory instead? The Resilient Distributed Dataset (RDD) is Spark’s core abstraction: a distributed, immutable collection partitioned across a cluster, computed lazily. Intermediate RDDs live in memory; only the final output hits disk. For iterative algorithms - machine learning, graph algorithms, anything that processes the same data repeatedly - this makes Spark 10-100x faster than Hadoop MapReduce.

Spark also introduced a richer API. MapReduce has two operations. Spark has map, filter, flatMap, groupByKey, reduceByKey, join, union, sort, and dozens more, composable in arbitrary pipelines. The Spark SQL interface allows analysts to write SQL and get distributed execution automatically. DataFrame and Dataset APIs added columnar processing with schema awareness.

Hadoop didn’t die. HDFS (the Hadoop Distributed File System) is still the storage layer for many Spark clusters. But Hadoop MapReduce as a compute engine is effectively obsolete.

The Shuffle: Where Distributed Computing Gets Hard

The shuffle is the most expensive operation in distributed data processing, and understanding why is essential for diagnosing performance problems.

After the map phase, intermediate data exists on each mapper’s local disk. The reduce phase needs all pairs with the same key on the same machine. This requires network transfer of potentially all intermediate data. If your mappers produce 1 TB of intermediate data and you have 1,000 reducers, each reducer pulls 1 GB over the network on average.

The fundamental problem: network is the bottleneck. A typical cluster has 10 - 25 Gbps per node, but the aggregate shuffle traffic across all nodes can saturate the network fabric. A cross-datacenter shuffle is worse by orders of magnitude - which is why distributed compute jobs should almost never span availability zones, let alone regions.

Data skew makes the shuffle catastrophic. If 30% of your records have key = "USA" and each unique key goes to one reducer, the USA reducer gets 300x more data than average. The entire job waits for that one reducer. This is called the straggler problem. Solutions include salting (append a random suffix to hot keys and split the reduce), pre-aggregation in the map phase (reduce locally before shuffling), and manual repartitioning.

In Spark specifically, the shuffle partition count (spark.sql.shuffle.partitions, defaulting to 200) is one of the most important tuning parameters. Too few partitions: each is large and the shuffle is slow. Too many partitions: overhead from task scheduling and small file problems. The right value depends on your data volume and cluster size, and getting it wrong by a factor of 10 in either direction can make a job run 5x slower.

Data Parallelism vs. Task Parallelism

Data parallelism applies the same operation to different chunks of data simultaneously. Word count is data parallelism: the map function is identical on every machine; only the data differs. This is also how distributed ML training works: each GPU processes a different batch, all running the same forward-backward pass. Workers rarely need to coordinate.

Task parallelism runs different operations concurrently. A web server handling one request that queries a database while another request fetches from a cache is task parallelism. The tasks are heterogeneous; coordination is the challenge, but the coordination points are predictable (request boundaries).

Pipeline parallelism chains stages like an assembly line. Stage 1 preprocesses data and hands it to Stage 2 for feature extraction, which hands it to Stage 3 for inference. At steady state, all stages run concurrently on different items. Pipeline parallelism is a natural fit for streaming processing and for large model inference where the model is split across layers.

Embarrassingly parallel workloads - where workers never need to coordinate - scale linearly. Each additional machine adds proportional capacity. Rendering frames in a movie is embarrassingly parallel. Amdahl’s Law captures the fundamental limit: if a fraction $p$ of the computation is parallelizable, the maximum speedup across $n$ workers is:

$$S(n) \leq \frac{1}{(1 - p) + \frac{p}{n}}$$

If 10% of the computation is sequential, the maximum possible speedup is 10x, regardless of how many machines you add. The sequential fraction is the ceiling. Most real distributed systems have a sequential fraction somewhere between 5% and 20%, which puts their practical scaling ceiling between 5x and 20x - sobering when you’re provisioning 100-node clusters.

Cloud-Managed Distributed Computing

Running your own Hadoop or Spark cluster is operational work that most teams don’t need to do. The cloud providers offer managed equivalents that remove the cluster management burden while retaining the programming model.

AWS EMR (Elastic MapReduce) runs managed Spark, Hive, and Hadoop clusters on EC2. You specify the instance types and count; EMR handles cluster bootstrapping, configuration, and HDFS or S3-backed storage. Spot instances (unused EC2 capacity available at 60-90% discount) are commonly used for EMR workloads because jobs can be checkpointed and restarted. EMR Serverless removes even the cluster provisioning step: you submit a Spark job and the service handles capacity automatically.

AWS Glue is serverless Spark with additional ETL tooling: a data catalog, a visual job editor, and native integration with S3, Redshift, and RDS. Glue is the right choice for straightforward ETL pipelines that fit the Spark model. It’s more expensive per compute-hour than EMR but eliminates all cluster management.

BigQuery (GCP) is a different philosophy: instead of bringing your Spark code to managed infrastructure, you write SQL and the service executes it on Google’s Colossus distributed file system using a massive-scale query execution engine (Dremel). There are no clusters, no tuning parameters exposed to users, and no shuffle partitions to configure. You pay per byte scanned. For SQL-expressible analytics at scale, BigQuery has made explicit Spark code unnecessary for many use cases.

Athena (AWS) is the S3-based equivalent: SQL over data in S3, using Presto under the hood. Like BigQuery, it’s serverless and pay-per-query.

The trend is clear: for analytics workloads that fit a SQL model, serverless SQL (BigQuery, Athena) has replaced Spark for many teams. Spark’s value proposition is strongest for ML pipelines, complex graph algorithms, and workloads that can’t be expressed in SQL.

MapReduce and ML: The Connection

Distributed ML training is MapReduce applied to gradient computation.

In synchronous data parallelism, the model is replicated on each GPU (or machine). Each replica processes a different shard of the training batch, computes the forward pass and the gradient. Then an AllReduce operation aggregates gradients across all replicas - each device sends its gradients and receives the global sum. Each replica updates its weights identically. The model stays synchronized.

The AllReduce is the reduce step of MapReduce. The map step is the per-device gradient computation. The “shuffle” is the gradient communication - and like the Spark shuffle, it can be the bottleneck at scale.

At the scale of GPT-3 or larger models, gradient communication alone takes a significant fraction of training time. This drives the investment in high-bandwidth interconnects (NVLink within a node, InfiniBand between nodes, Google’s proprietary TPU interconnect within a pod). It also drives the algorithmic work on gradient compression, asynchronous SGD, and communication-efficient distributed training schemes.

Spark in Practice: Where It Gets Complex

Spark is not simple to tune well. The common failure modes:

Executor memory configuration is where most newcomers struggle. Each Spark executor has a fixed memory budget divided between execution (shuffle buffers, sort buffers, aggregation hash tables) and storage (cached RDDs). Getting the ratio wrong causes either excessive spilling to disk (OOM on execution) or cache thrashing (the data you cached gets evicted before you need it).

Skew shows up constantly in real data. Any groupBy or join operation on a column with a highly non-uniform distribution - customer IDs where 1% of customers generate 50% of transactions - will produce skewed partitions. The standard debugging signal is a Spark UI that shows 999 tasks completing in 30 seconds and 1 task running for 45 minutes.

Small file problems are the inverse of skew. If your upstream data is stored as millions of tiny files in S3, each Spark task processes one file, and the task overhead dominates the compute time. Coalescing upstream data (combining small files into larger ones before processing) is often the most impactful optimization.

Structured Streaming extends Spark’s batch model to streaming data. A streaming query processes micro-batches of data from Kafka or Kinesis and maintains state across batches. The state management (for windowed aggregations, for example) is sophisticated, but watermarking semantics for late data are subtle and easy to get wrong.

Ray: The Python-Native Alternative

Ray is the most significant alternative to Spark for ML workloads, developed at the same UC Berkeley AMPLab that produced Spark. Where Spark’s origins are in the JVM big-data world, Ray is Python-native from the start.

The core model: a @ray.remote decorator turns a Python function into a distributed task, and a @ray.remote class into an actor with persistent state. Ray’s scheduler handles placement, fault tolerance, and memory management across the cluster.

import ray

ray.init()

@ray.remote
def train_model(config: dict) -> float:
    model = build_model(config)
    return cross_validate(model)

# Launch 100 hyperparameter search jobs in parallel
configs = generate_search_space(n=100)
futures = [train_model.remote(cfg) for cfg in configs]
results = ray.get(futures)

Ray Tune builds hyperparameter search on top of Ray, with support for Bayesian optimization, Hyperband early stopping, and distributed trial execution. Ray Train provides distributed ML training abstractions for PyTorch and TensorFlow. Ray Data handles distributed data preprocessing pipelines with deep integration with PyArrow and Parquet.

Where Spark excels at SQL-expressible batch analytics, Ray excels at Python-native ML pipelines: data preprocessing into model training into hyperparameter search into deployment, all in one framework, all in Python, without requiring Spark’s JVM or its SQL mental model.

On AWS, Ray clusters run on EC2 (often using the Ray Cluster Launcher or KubeRay on EKS). Anyscale provides a managed Ray platform. For ML workloads that currently use Spark for preprocessing before training on a separate GPU cluster, Ray’s unified model is often more efficient.

When Parallelism Hurts

Not every problem benefits from parallelization. The coordination overhead can exceed the compute savings.

False sharing in shared-memory parallelism: two cores write to different variables that share a cache line (typically 64 bytes). Each write invalidates the other’s cache line. The cores thrash even though they’re logically independent. Padding data structures to cache line boundaries eliminates false sharing, at the cost of memory.

Coordination-heavy workloads - where workers frequently need results from each other before proceeding - are poor fits for distributed computing. Iterative graph algorithms where every node’s next value depends on all its neighbors' current values require a global synchronization step per iteration. This is the AllReduce pattern, and it works, but the synchronization cost scales with cluster size.

Stragglers are unavoidable at scale. In a cluster of 1,000 machines, at any given time, some machines are slower than average due to network contention, garbage collection, noisy neighbors in cloud environments, or hardware wear. A job that waits for all workers to complete before moving to the next stage is limited by its slowest worker. At 1,000 machines, the slowest machine is very slow. Speculative execution (re-running slow tasks on other machines and using whichever completes first) is one mitigation; designing jobs to tolerate stragglers is another.

Data locality matters more at scale. Moving computation to the data is faster than moving data to the computation. A Spark job that reads 10 TB from S3 into a cluster that’s geographically distant from the S3 bucket pays cross-region data transfer costs (both in dollars and in latency) that can dominate the compute cost. Running EMR in the same region as the S3 bucket is the baseline; running it in the same AZ is better.

Future: Serverless and Ray

The trajectory for distributed compute is toward less visibility into infrastructure. BigQuery and Athena have already made cluster management invisible for SQL workloads. The same trajectory is underway for Spark: EMR Serverless and Glue remove cluster management for most ETL teams.

For ML, the consolidation is happening around Ray. The combination of Ray Data for preprocessing, Ray Train for distributed training, and Ray Serve for model serving is increasingly the standard ML platform architecture on AWS and GCP.

The fundamental trade-off has not changed: the shuffle is still the bottleneck; Amdahl’s Law still applies; data skew still causes stragglers. Understanding these limits makes you a better user of any distributed computing framework, regardless of what the framework calls itself.

Summary

Read Next:

• GPU vs TPU - Different Bets on the Shape of Computation