Replication, partitioning, and consistency contracts

Prerequisites: Transactions, logs, failures, and network messages.

Learning objectives

• Distinguish replicas from partitions.
• Trace stale reads after asynchronous replication.
• Explain quorum intersection assumptions and cross-shard work.

Replication maintains copies of the same logical data. Partitioning, or sharding, divides data ownership across groups. A system can use both: customer identifiers determine shards, and each shard has several replicas. Replication can improve availability and read capacity; partitioning can increase total capacity. Neither automatically provides the other benefit, and both add coordination and failure cases.

Consider a primary with two followers. The primary commits version 7 of a profile and acknowledges a write. An asynchronous follower still stores version 6. A subsequent read routed to that follower can return the older profile even to the user who just changed it. This is replication lag, not necessarily data corruption. A read-your-writes contract requires an additional mechanism, such as routing to an appropriate replica or carrying a version requirement and waiting until it is satisfied.

Synchronous replication changes the acknowledgement boundary. Waiting for durable receipt on a suitable set of replicas can protect acknowledged writes against specified failures, but increases latency and can reject writes when that set is unavailable. State exactly what an acknowledgement means: received in memory, persisted in a log, applied to queryable state, or agreed as committed. These stages are not interchangeable.

Quorum arithmetic is useful but insufficient as a consistency proof. With N=3 replicas, write quorum W=2 and read quorum R=2 intersect because R+W>N. That means at least one replica may carry information about an acknowledged write. A reader still needs a correct version-selection and repair protocol; concurrent writes, failed writes, membership changes, and sloppy quorums complicate the argument. Intersection alone does not establish linearizability.

Partitioning by a hash can spread keys relatively evenly, but a single extremely hot key remains hot. Range partitioning supports ordered scans yet can concentrate writes at the newest boundary. Moving a partition requires tracking ownership while requests are in flight, copying a consistent state, and transferring subsequent updates. Without a protocol, two owners may both accept writes or neither may serve a key.

A query touching several shards becomes distributed work. Global uniqueness, foreign keys, joins, and transactions may need coordination or explicit restrictions. A transfer between accounts on separate shards cannot be made atomic simply by running one local transaction on each shard and hoping both succeed. Design the transaction boundary before choosing the partition key.

During a network partition, some communication is unavailable. A consistency contract requiring agreement can force part of the system to stop accepting particular operations. Define which operations remain available and how clients observe retries, stale data, or rejection. Evaluate a design with failure traces and business invariants, not just a replica count.

Practice problem

A three-replica shard acknowledges writes after two replicas durably store them. A client then reads one arbitrary replica. Construct a stale-read execution. Repeat with two read responses and explain why taking the first response still fails to use quorum intersection correctly. Finally, describe the additional ownership problem introduced when a hot customer moves from shard X to shard Y while writes continue.

Worked solution

Write version 8 to replicas A and B while C remains at 7. The write is acknowledged, but a one-replica read from C returns 7. A two-response read from C and A intersects the completed write quorum at A; blindly returning C’s faster response still returns stale data. The protocol must inspect suitable version metadata and satisfy its required consistency rules, not just issue two requests. During a shard move, requests may reach both X and Y with old routing information. The migration must establish which owner can accept writes, transfer updates consistently, and fence stale owners or redirect requests. Otherwise copied data can diverge even though each shard replicates perfectly internally.

Check your understanding

N=3, W=2, R=2 with fixed membership. A read waits for two replies but returns the first value without comparing versions. What follows from quorum intersection alone?

• Both responses must contain identical values.
• The returned value is automatically linearizable.
• At least one responding replica intersects the write quorum, but the read logic can still choose a stale value.
• A failed write can never be observed.

Explanation

Intersection establishes shared membership; a correct read protocol must interpret versions and incomplete writes appropriately.

A customer shard is copied from X to Y while X still accepts writes. What additional problem must migration solve?

• Establishing authoritative ownership and transferring or fencing in-flight updates.
• Ensuring every customer has the same number of records.
• Selecting a new hash function for every existing key.
• Removing all replicas so there is only one disk.

Explanation

Copying bytes alone does not coordinate concurrent writers or prevent stale owners from accepting divergent updates.

Primary reading

• Database Systems: lectures, notes, and projects: Carnegie Mellon University
• Transaction isolation: PostgreSQL Global Development Group

Open the study and save your work →