Replication and Partitioning

Replication serves two distinct goals that are often conflated:

• Fault tolerance: if one node dies, another holds the data. Even a single replica raises durability from one hard drive's MTBF to the product of two independent failures.
• Read throughput: serving reads from multiple replicas linearly scales read capacity. Writes still require coordination.

These goals pull in different directions. Maximizing fault tolerance (many replicas, synchronous) adds write latency. Maximizing read throughput (many replicas, async) risks serving stale data. Every replication strategy is a trade-off between these two axes. Before choosing a topology, decide which failure scenarios you're designing for and what staleness the application can tolerate.

The dominant approach: one node is the leader (primary), all others are followers (replicas). Writes go to the leader; the leader ships a replication stream (WAL, binlog, or logical log) to followers.

Client → Leader → [replication stream] → Follower 1
                                        → Follower 2

Synchronous replication: the leader waits for at least one follower to confirm before acknowledging the write. Durability guarantee: survives leader crash. Cost: write latency is bound to the slowest sync follower.

Asynchronous replication: leader acknowledges immediately, ships to followers in the background. Throughput is high; a leader crash before replication completes loses committed writes.

Semi-sync (MySQL default): exactly one follower is synchronous, the rest are async. Balances durability and latency. Most production MySQL and PostgreSQL streaming setups use this.

Multi-leader (active-active) allows writes at multiple nodes — typically one per datacenter — and replicates asynchronously between them.

Advantages:

• Writes go to a local datacenter: low latency for geographically distributed users.
• Survives a full datacenter outage with no failover needed.

The fundamental problem: write conflicts. If two leaders accept concurrent writes to the same key, there's no total order. You must have a conflict resolution policy:

• Last-write-wins (LWW): use timestamps. Lossy when clocks skew.
• Application-level merge: expose the conflict to the application (CouchDB, Riak). Correct but complex.
• CRDT types: limit writes to CRDT-compatible operations (counters, sets, maps). Conflict-free by construction.

For most applications, the complexity of multi-leader conflict resolution outweighs its benefits. Use it only when cross-datacenter write latency is an explicit SLA requirement.

In leaderless systems (Dynamo-style: Cassandra, Riak, DynamoDB), any node accepts reads and writes. Consistency is achieved via quorum rules.

Given $N$ replicas, write to $W$, read from $R$:

$W + R > N \implies \text{quorum overlap} \ge 1$

Common configurations for $N=3$:

Caution: $W + R > N$ does not guarantee linearizability. If a write and a read execute concurrently, the quorum may not overlap in the right nodes. Cassandra's QUORUM gives strong eventual consistency, not linearizability. For linearizability you need SERIAL consistency (per-key Paxos).

Partitioning (sharding) splits data across nodes so each node holds a subset. Two main strategies:

Range partitioning: assign contiguous key ranges to each partition (e.g., [A–F], [G–M], [N–Z]).

• Pro: range scans are efficient — all keys in a range are co-located.
• Con: hot partitions if writes cluster in a range (e.g., all new records have today's timestamp prefix).

Hash partitioning: partition = hash(key) % num_partitions.

• Pro: distributes load uniformly across partitions.
• Con: range scans require querying all partitions. Cassandra uses this; range queries are scatter-gather.

# Hash partitioning assignment
def get_partition(key: str, num_partitions: int) -> int:
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % num_partitions

A common hybrid: hash the first part of a compound key, range-sort the second. Cassandra's partition key + clustering key does exactly this: hash gets you to a node, the clustering key gives you sorted access within the partition.

Naive hash partitioning has a fatal flaw: adding or removing a node requires rehashing and moving $\approx N/M$ of all keys (where $N$ = keys, $M$ = nodes). Consistent hashing solves this.

The algorithm:

1. Map both nodes and keys onto a conceptual ring of hashes (typically $[0, 2^{32})$).
2. Each key belongs to the first node clockwise from its hash position.
3. Adding a node: only keys between the new node and its predecessor migrate — roughly $1/M$ of total keys.
4. Removing a node: its keys move to its successor — again roughly $1/M$.

Virtual nodes (vnodes): assigning each physical node multiple ring positions (e.g., 256 tokens in Cassandra) improves load balance and makes the migration on node changes even smaller. Without vnodes, unlucky ring positions can create hot spots.

Consistent hashing is used in Cassandra, Dynamo, Amazon S3, and most CDN key distribution systems.

Even with perfect initial distribution, two operational hazards emerge over time:

Hot partitions: a single partition receives disproportionate traffic. Common causes:

• Celebrity/viral data (all reads go to one key).
• Monotonically increasing keys (all writes go to the last partition).
• Poor partition key choice.

Fixes: add a random prefix to hot keys (shard the hot partition), use a secondary fan-out write path, or add a caching layer in front.

Rebalancing: when you add nodes, data must move. Strategies:

• Fixed number of partitions (Elasticsearch): pre-shard into many more partitions than nodes (e.g., 1000 shards, 10 nodes); add a node → reassign whole shards. Simple, but shard size must be tuned upfront.
• Dynamic partitioning (HBase, RethinkDB): split a partition when it exceeds a size threshold; merge when it shrinks. Adapts automatically but adds metadata complexity.
• Proportional to nodes (Cassandra vnodes): fixed partitions per node; adding a node steals evenly from existing nodes.

Monitor partition size and request-rate skew in production — imbalance compounds quickly under write pressure.

Three topologies and their write paths:

A decision framework:

The biggest mistakes in practice: (1) using eventual consistency for data that requires strong consistency, (2) choosing a partition key that creates hot spots at launch, (3) under-provisioning shard count so rebalancing becomes painful at scale. Test with production-like key distributions before launch.