Distributed Systems Basics for Data Engineers

Spark, Kafka, cloud warehouses and object stores are all distributed systems: many machines cooperating over a network and presenting themselves as one. You can use them without studying distributed systems, until a job is mysteriously slow, a pipeline double-counts after a retry, or two systems disagree about the same number. A handful of ideas explain most of those situations. This guide covers them, with one idea tested on real data.

Partitioning: splitting data across machines

Data too big for one machine is split into partitions, and each machine owns some of them. Two strategies dominate:

• Hash partitioning assigns each key by a hash of it. Keys spread evenly, but a range query such as "all of January" touches every machine.
• Range partitioning assigns contiguous key ranges, such as dates, to machines. Range queries touch few machines, but recent data can pile onto one.

Either way, partitioning by a key makes every row with that key land together, which is what makes grouping and joining possible, and why skewed keys hurt: if a few keys hold most of the data, the machines that own them do most of the work. Spark performance tuning shows skew in real Spark partitions.

Rebalancing: what happens when you add a machine

Clusters grow. The naive way to place a key is hash(key) modulo the number of machines, but changing the number of machines changes almost every assignment. Consistent hashing fixes this: machines and keys are both placed on a circle of hash values, and each key belongs to the next machine clockwise, so a new machine takes over only the keys just before its positions. Amazon's Dynamo paper describes the principal advantage: a node's arrival or departure affects only its immediate neighbours, and each node gets many positions, virtual nodes, to spread load more evenly (Dynamo paper, SOSP 2007).

A simulation shows the difference on real data: January 2024 New York yellow taxi trips (NYC TLC: trip record data), with each pickup zone's trips stored on one of four nodes, then a fifth node added:

import bisect
import hashlib
import urllib.request
from collections import Counter
from pathlib import Path
import pyarrow.parquet as pq

name = "yellow_tripdata_2024-01.parquet"
if not Path(name).exists():
    urllib.request.urlretrieve(f"https://d37ci6vzurychx.cloudfront.net/trip-data/{name}", name)
trips = Counter(pq.read_table(name, columns=["PULocationID"]).column(0).to_pylist())
total = sum(trips.values())
print(f"{len(trips)} zones, {total} trips")

def h(text):
    return int(hashlib.md5(str(text).encode()).hexdigest(), 16)      # stable across runs and machines

def modulo(nodes):
    return {zone: f"node{h(zone) % nodes}" for zone in trips}

def ring(nodes, vnodes=100):
    points = sorted((h(f"node{n}#{v}"), f"node{n}") for n in range(nodes) for v in range(vnodes))
    keys = [p for p, _ in points]
    return {zone: points[bisect.bisect(keys, h(zone)) % len(points)][1] for zone in trips}

def load(assign):
    per_node = Counter()
    for zone, node in assign.items():
        per_node[node] += trips[zone]
    return sorted(round(100 * v / total, 1) for v in per_node.values())

def moved(before, after):
    return sum(trips[z] for z in trips if before[z] != after[z]) / total

for name, scheme in [("modulo hashing", modulo), ("consistent hashing", ring)]:
    four, five = scheme(4), scheme(5)
    print(f"{name}: share of trips per node with 4 nodes {load(four)}; moved when a 5th node joins: {moved(four, five):.1%}")

260 zones, 2964624 trips
modulo hashing: share of trips per node with 4 nodes [14.3, 18.9, 29.0, 37.8]; moved when a 5th node joins: 74.0%
consistent hashing: share of trips per node with 4 nodes [16.5, 18.4, 29.8, 35.3]; moved when a 5th node joins: 23.0%

Two lessons. Adding one machine under modulo hashing moved 74% of the data, a huge, slow reshuffle; consistent hashing moved 23%, close to the ideal of a fifth, since the new node should own about a fifth. And neither scheme balanced the load: with only 260 zones and a few very busy ones, one node held over a third of the trips either way. Hashing spreads keys evenly, not data; when a few keys are hot, the fix is a finer key, not a better hash.

Replication: copies for safety and speed

Machines fail, so data is copied. HDFS keeps three replicas of each block by default, spread across machines and racks (Hadoop docs: HDFS); Kafka replicates each partition across brokers; cloud object stores replicate behind the scenes. Replicas also serve reads, but keeping copies in agreement is where the hard problems start.

Consistency and what CAP really says

The CAP theorem is often quoted as "choose two of consistency, availability and partition tolerance". Eric Brewer, who proposed it, later called that framing misleading: network partitions are rare, and the choice between consistency and availability arises only while a partition lasts (Brewer: CAP twelve years later). The practical question for a data engineer is narrower: after a write, when will every reader see it? A warehouse table read immediately after a load, a replica that lags its leader, and a cache that has not refreshed all produce the same symptom, two numbers that disagree for a while.

Failure is normal

At cluster scale, some task, disk or network link is always failing. Distributed systems respond by retrying, which creates the data engineer's central problem: a retried step may run twice. A load that appends rows will duplicate them on retry, and a message consumer that crashes after processing but before recording its progress will process the message again. Systems therefore promise at-most-once, at-least-once or, with care, exactly-once delivery, and pipelines are built to be idempotent, so running a step twice gives the same result as once; idempotency in data pipelines shows how.

Time is unreliable

Each machine has its own clock, and clocks drift. Events also arrive late: a phone offline for an hour sends yesterday's events today. That is why streaming systems distinguish event time, when something happened, from processing time, when the system saw it, and why ordering by timestamps across machines is only approximate. Handling late-arriving data covers the pipeline side.

Where these ideas show up

• Spark: partitions, shuffles, skew and task retries; Spark vs Hadoop traces how its design emerged.
• Kafka: partitioned, replicated logs with delivery guarantees, where the choice of message key decides both ordering and partition balance; Apache Kafka explained covers it.
• Warehouses and lakes: distributed storage, eventual visibility of loads, and transaction logs to make writes atomic.

Distributed computing concepts are part of the big data fundamentals module of the Data Engineering course.

Sources

• Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007) — Amazon (SOSP 2007)
• CAP Twelve Years Later: How the Rules Have Changed (Eric Brewer, InfoQ) — InfoQ
• HDFS architecture (Apache Hadoop documentation) — Apache Hadoop
• TLC Trip Record Data (NYC Taxi and Limousine Commission) — NYC Taxi and Limousine Commission