Parallel and Distributed Databases: Optimize Data Movement First

A query does not become fast merely because it has more machines. In a distributed database, the scarce resource often changes from disk I/O to network movement, coordination, or the slowest partition. Good design begins by deciding where data lives and which operations can remain local.

Parallel and distributed are related, not identical

• Parallel execution divides one operation across workers to reduce elapsed time.
• Distributed storage places data across independently failing nodes, often to scale capacity or improve availability.
• Replication keeps multiple copies for read scale or fault tolerance.

A system may run parallel queries on one shared cluster, distribute data without parallelizing a small query, or do both.

In plain terms: more workers help only when the work splits evenly and the cost of coordinating them is smaller than the time saved.

Partitioning decides what stays local

Choose a partition key from the dominant access path, join path, and write distribution—not from the column that merely looks unique. A tenant identifier can colocate tenant-local transactions; a timestamp can prune archival queries but concentrate current writes.

Distributed join choices

Suppose orders is partitioned and must join countries.

1. Colocated join: both tables share compatible partitioning. Each worker joins locally.
2. Broadcast join: send the small table to every worker.
3. Repartition join: shuffle both inputs by the join key.
4. Semijoin reduction: send keys first, then move only matching rows.

The optimizer needs row count, byte size, selectivity, and distribution. Average partition size is insufficient: one hot key can make a single worker dominate wall-clock time.

elapsed time ≈ max(worker time) + shuffle + coordination

This is why a plan with excellent total CPU can still have poor latency.

Replication changes the correctness problem

Replication asks how copies agree and what happens during failure. Synchronous replication can reduce acknowledged data loss but adds write latency and may reduce availability during a partition. Asynchronous replication returns earlier but permits lag and stale reads.

The CAP result is often oversimplified. It matters specifically when the network is partitioned: the system cannot guarantee both that every response reflects a single up-to-date copy and that every request receives a successful response. Outside a partition, latency and consistency choices still matter, but “pick two” is not a complete design method.

2PC and consensus solve different problems

Two-phase commit (2PC) coordinates one atomic transaction across participants:

1. Prepare: each participant promises it can commit and records that promise durably.
2. Commit/abort: the coordinator announces the final outcome.

If the coordinator disappears after participants prepare, they may remain blocked until the decision is recovered.

Consensus protocols instead let a group agree on an ordered value despite some failures. A system may use consensus to replicate each shard and still use 2PC for a transaction spanning several shards. One does not automatically replace the other.

A practical design sequence

1. Define the unit that must update atomically.
2. Pick a partition key that keeps that unit local when possible.
3. Measure data and request skew, including the hottest key.
4. Price network bytes and tail latency, not only average CPU.
5. State the read-consistency and data-loss contract.
6. Test node loss, coordinator loss, retries, and duplicate delivery.

Review card

• Partitioning is primarily a locality decision.
• A distributed join chooses between colocation, broadcast, shuffle, and reduction.
• Tail latency follows the slowest worker, so skew matters.
• Replication adds a consistency and failure contract.
• 2PC coordinates atomic commit; consensus agrees on replicated state.
• Distribution pays off only after network and coordination costs are counted.