Replication, Partitioning, and State Placement

By the end of this lesson, you will be able to...

• explain the difference between a copy of state and the authority to change it.

• trace how one key moves from one shard to another without creating two owners.

• identify signals for hot keys, stale routing, replica lag, and unsafe failover.

Idea in one sentence: Replication and partitioning are safe only when a placement rule says where each key lives, who may write it, and how that authority changes.

Core Insight

A project-management app stores each team's board as a key:

board/acme-launch

The board has cards, comments, assignments, and an activity log. During a launch review, the whole company opens the board. Reads spike. Comments spike. Card moves spike. The shard that owns board/acme-launch starts falling behind.

A tempting fix is:

Copy the board to a bigger shard.
Send new traffic to the bigger shard.

Copying sounds like the important part. It is not enough.

While the copy is running, people are still moving cards. If the old shard and the new shard both accept writes, the board can split into two histories. If routers switch too early, the new shard may be missing a card move that a user already saw as saved. If a replica answers a read without knowing its lag, the app can show an old board and call it current.

The hard part is not only where bytes are stored. The hard part is authority.

Plain meaning:

A system needs a visible rule for where a key belongs and which copy is allowed to make official changes.

In this scenario:

board/acme-launch may have several copies, but only one owner should accept official card moves at a time.

Technical name:

The rule is state placement. It combines partitioning, replication, routing, ownership, and a versioned handoff protocol.

The Moving Parts

Start with one key. A whole cluster is too much to inspect at once.

key:             board/acme-launch
partition rule:  boards by hash(board_id)
shard:           boards-03
write owner:     Madrid leader
read replicas:   Madrid follower, Dublin follower
log position:    1840
placement epoch: 12

Each word has a job.

A key is the item being located. It might be a board id, order id, account id, document id, tenant id, or room id.

A partition or shard is a group of keys managed together. Partitioning gives the system a unit for routing, ownership, movement, and load measurement.

A replica is a copy of a shard's state. It may be useful for reads, recovery, or failover.

An owner is the copy, or the leader for a group of copies, that may accept official writes.

A placement epoch is a version number for the placement rule. It tells the system whether a router or writer is using an old view of ownership.

These pieces answer different questions:

Where should this request go?
Which copy may write?
Which copy may read?
How fresh must that read be?
What happens if ownership moves?

The Naive Copy

Suppose boards-03 is overloaded. The team creates boards-09, a new shard with more capacity.

The naive plan is:

1. copy board/acme-launch from boards-03 to boards-09
2. update routers to send new traffic to boards-09
3. delete the old copy later

This works only if the board is frozen during the copy. Real systems often cannot freeze a busy board for long.

Imagine the copy starts at log position 1840.

boards-03:
  position 1840
  card "Deploy API" is in Doing

boards-09:
  imports snapshot at position 1840

Then three users act before the router switch finishes:

1841: Lina moves "Deploy API" to Review
1842: Arun adds comment "Waiting on smoke tests"
1843: Bea assigns herself to the rollback card

If boards-09 accepts writes after only the snapshot, it may create entry 1841 with a different card move. Now both shards have entry numbers that look official, but they do not describe the same history.

The problem is not copying. The problem is changing authority without a handoff.

Check: If boards-09 has a complete snapshot at position 1840, can it safely accept official write 1841?

Think first, then reveal.

Answer: No. A snapshot gives it data through position 1840. It does not give it authority to create the next official entry. The old owner may already be accepting entry 1841.

The Mechanism: Placement With Epochs

A safer system treats placement as a protocol.

The placement map says:

epoch 12:
  key range:    boards hash bucket 03
  write owner:  boards-03 Madrid leader
  followers:    boards-03 Madrid follower, boards-03 Dublin follower

Routers attach the epoch they used:

update card:
  key = board/acme-launch
  placement_epoch = 12
  idempotency_key = move-7f3

The owner rejects writes with an epoch that is too old or too new for its authority. That check is a fence. It prevents a delayed request from quietly writing to the wrong owner after a move.

Replication gives copies a job description:

leader:
  may accept writes for epoch 12
  produces ordered log entries

follower:
  applies log entries from the leader
  may serve reads only within the product's allowed lag
  may become a candidate owner only after it catches up and is chosen

A replica is not a backup owner by default. It is a copy with specific permissions.

A Worked Trace: Move One Board

The controller will move board/acme-launch from boards-03 to boards-09.

1. Prepare A Destination That Cannot Write

The active placement map remains unchanged:

active map:
  epoch 12 -> boards-03 owns board/acme-launch

source:
  boards-03 at log position 1840

destination:
  boards-09 imports snapshot at position 1840
  boards-09 is not allowed to write

New user edits still go to boards-03. The source streams entries 1841, 1842, 1843, and later entries to boards-09.

This gives the destination a copy without creating a second authority.

2. Catch Up And Verify

At one moment:

source position:       1860
destination position:  1856

The move is not ready. The destination is behind.

Later:

source position:       1872
destination position:  1872
verification:          checksums and log order match
still authoritative:   boards-03, epoch 12

Being caught up is necessary. It is still not enough. The destination has the same history, but it still needs a placement change before it can create entry 1873.

3. Fence The Old Owner And Commit The New Epoch

The controller chooses a handoff point.

final source entry: 1873
destination applied: 1873

Then it commits a new placement map:

epoch 13:
  key range:    boards hash bucket 03
  write owner:  boards-09 Madrid leader
  old owner:    boards-03 may forward or reject old-epoch writes

After this point, a write using epoch 12 cannot create a new official entry. It must be rejected, redirected, or retried after refreshing the map. The client can safely retry with the same idempotency key so the user does not create a duplicate card move.

old request arrives:
  key = board/acme-launch
  epoch = 12
  idempotency_key = move-7f3

boards-03 response:
  stale placement; refresh and retry

This is fencing. The old owner is prevented from acting as owner after its authority expires.

4. Drain And Watch

After routers use epoch 13, boards-03 stays around for a while.

It may forward old requests, serve as a repair source, or provide a rollback path. It should not accept new official writes for the moved key.

The move is complete when three things agree:

requests route to boards-09
boards-09 has the required state
epoch 13 is the only write authority

So far, we have seen that moving state is not "copy then switch." It is copy, catch up, verify, hand off authority, fence stale writers, and observe the drain.

Partitioning And Replication Do Different Jobs

Partitioning spreads keys across owners.

shard = hash(board_id) mod 32

That helps when many ordinary boards exist. It does not automatically solve a single hot board. If one board receives most of the writes, that key can still overload one owner.

Replication creates copies.

Copies can help with nearby reads, recovery, and failover. They do not automatically increase write capacity for a key that needs one official order. If every card move for board/acme-launch must appear in one ordered activity log, one owner still serializes those writes.

The design options depend on the product promise. The team might split one huge board into sections with separate owners. It might keep one owner for writes but add read replicas. It might rate-limit comments during an incident. It might move the board to stronger hardware. Each option changes cost, locality, and the meaning of "saved."

Failover Uses The Same Discipline

Movement is planned. Failure is not.

If the Madrid leader for boards-09 disappears, the system may want to promote a follower. The unsafe version says:

nearest follower becomes leader immediately

That can lose recent writes if the follower is behind. It can also create split ownership if the old leader is only slow or disconnected, not dead.

A safer failover checks:

which replicas have the needed log position?
who is allowed to decide promotion?
what new epoch fences the old leader?
what should old clients do when they retry?

The trade-off is visible. Conservative failover waits for evidence and may reject writes for a while. Aggressive failover restores service faster but may expose stale state or require repair.

Check: A follower has applied through 1868. The old leader may have accepted entries through 1873. Should the follower become owner without extra evidence?

Think first, then reveal.

Answer: Not for a workflow that cannot lose writes. The follower is missing possible official entries. Promotion needs a rule that proves the chosen owner has the required history or that missing writes are safe to repair.

Trade-offs And Limits

Placement rules improve routing, movement, failover, and ownership clarity.

They cost metadata, controller logic, epoch checks, monitoring, and operational care. More shards increase flexibility, but also increase map size and rebalancing work. More replicas improve read locality and recovery options, but create lag and failover decisions.

Placement does not solve every load problem. A hot key can still bottleneck. A shard move can still fail halfway. A stale router can still send traffic to the wrong place if the system does not fence old epochs. A read replica can still be too stale for a promise that requires fresh state.

Useful signals include:

• per-shard read rate, write rate, queue depth, and tail latency;
• top hot keys or tenants by traffic;
• placement-map age at routers;
• old-epoch write attempts after a handoff;
• replication lag by shard and replica;
• time spent copying, catching up, and draining during moves; and
• failed verification or checksum counts.

You can see the boundary when adding copies no longer improves the bottleneck. If the bottleneck is one write owner for one hot key, replication alone will not fix it.

Common Confusions

Confusion: A replica is a backup owner

Why it is tempting:

The replica has the data, so it feels ready to take over.

Better model:

A replica is a copy with a job description. It becomes an owner only after the system proves enough state, chooses it, and fences the old authority.

Confusion: More shards always fix hotspots

Why it is tempting:

Partitioning spreads many keys, so more partitions sound like more balance.

Better model:

More shards help when load is spread across many keys. A single hot key may need a different data model, rate limit, specialized placement, or a split inside the key.

Confusion: Copying state is the same as moving state

Why it is tempting:

The visible work looks like moving bytes.

Better model:

Moving state also moves authority. The safe handoff must say when the old owner stops, when the new owner starts, and what stale clients must do.

Practice

Pick one key from a system:

order_id
tenant_id
document_id
room_id
account_id
board_id

Write a placement record:

key:
partition rule:
current shard:
write owner:
read replicas and allowed lag:
placement epoch:
signal that would show this key is hot:

Then write a move plan:

snapshot position:
catch-up condition:
handoff entry:
new epoch:
how old owners are fenced:
how old clients retry safely:
metric that proves the drain is complete:

Model answer for document_id:

key:
  document/spec-14

partition rule:
  hash(document_id) mod 64

current shard:
  docs-18

write owner:
  docs-18 leader, because it owns epoch 44

read replicas and allowed lag:
  Dublin follower can serve reads up to 2 seconds stale for viewers;
  editors require version >= last saved version

move plan:
  copy snapshot at position 9800;
  stream log until destination reaches chosen handoff 9842;
  commit epoch 45 to make docs-27 the owner;
  reject or redirect epoch 44 writes;
  retry edits with idempotency keys

Resources

• [PAPER] Dynamo: Amazon's Highly Available Key-value Store - Focus: Partitioning, replication, versioning, and repair in a highly available key-value store.
• [PAPER] Bigtable: A Distributed Storage System for Structured Data - Focus: Tablet assignment, serving, splitting, and operational movement of structured data.
• [BOOK] Designing Data-Intensive Applications - Focus: Partitioning, replication, leader/follower replication, and rebalancing trade-offs.

Key Takeaways

• Partitioning chooses which group of keys belongs together; replication creates copies; placement assigns routing and authority.
• A replica can read, recover, or become a candidate owner only according to its job description.
• A safe move copies state, catches up, verifies history, changes epoch, fences the old owner, and drains old traffic.
• More replicas do not automatically fix a hot write owner.
• Hot keys, stale routing, replica lag, and old-epoch writes are signals that placement rules need attention.