SD7.6 · LESSON 6 OF 6

Rebalancing and conflict handling

Compare consistency contracts and distribute data while tracing stale reads, partitions and hot keys.

THE IDEA

Rebalancing and conflict handling

Growing a cluster means moving data. Placing keys by key mod shards and going from 4 to 5 shards moves 16 of 20 keys; a scheme such as rendezvous or consistent hashing moves only the keys that belong on the new node (about 4). Moving needs routing updates, version checks and a plan for failures mid-move. And when replicas accept concurrent writes they must converge by a conflict policy: last-write-wins keeps {pear} and silently loses {apple}; a union merge keeps both.

shards before adding one4

20 keys placed by key mod 4, then by key mod 5: 16 keys change shard (80%) an ideal scheme moves only the keys that belong on the new shard: about 4 rebalancing also needs routing updates, versions and a plan for failures during the move

replica A set the cart to {apple} at 10:00:05 replica B set the cart to {pear} at 10:00:06 (concurrently, neither saw the other) result with last-write-wins: {pear} → the apple is silently lost

Eventual convergence needs an explicit conflict policy. Wall-clock timestamps only say which write is later by the clocks, not which is right, and last-write-wins can discard meaningful concurrent changes.

Grow the cluster and choose a merge policy.

Predict first. Do wall-clock timestamps alone establish a correct application merge?

Chapter context

Replication copies data for resilience or read capacity; partitioning assigns different data to different owners. Both introduce coordination and failure behavior that an application must explicitly account for.

TRY IT YOURSELF

Part 1. Do it hands-on

Count moved keys and merge results by hand, then write minimal-movement placement and two merge policies.

shards before adding one4

replica A set the cart to {apple} at 10:00:05 replica B set the cart to {pear} at 10:00:06 (concurrently, neither saw the other) result with last-write-wins: {pear} → the apple is silently lost

keys moved, mod 4 → mod 5 (of 20) ideal keys moved items kept by last-write-wins items kept by a union merge timestamps alone give a correct merge? (yes/no)

To do: 20 keys (0–19) are placed with key mod 4. The cluster grows to 5 shards and keys are re-placed with key mod 5. How many keys change shard?
To do: An ideal scheme moves only the keys that belong on the NEW shard: one fifth of 20. Keys moved?
To do: Two replicas accept concurrent updates to a cart: A sets {apple} at 10:00:05, B sets {pear} at 10:00:06. Last-write-wins keeps how many items?
To do: A merge policy that takes the union keeps how many items?
To do: Do wall-clock timestamps alone establish a correct application merge? Type yes or no

Part 2. Do it in code

mod_moved(n_keys, old_shards, new_shards): how many of the keys 0…n_keys−1 change shard when placement changes from key % old to key % new.
owner(key, nodes): rendezvous (highest-random-weight) hashing: the node with the largest int(md5(f"{key}|{node}").hexdigest()[:8], 16).
moved_on_add(keys, nodes, new_node): the keys whose owner changes when new_node joins; every one of them must now be owned by new_node.
lww(updates): updates is a list of (value, timestamp); return the value with the latest timestamp (ties: greater value).
union_merge(updates): updates are lists of items; return the sorted union.
lost_by_lww(updates): the values of updates that last-write-wins discards (as a list in input order).

import hashlib

def mod_moved(n_keys, old_shards, new_shards):
    pass

def owner(key, nodes):
    pass

def moved_on_add(keys, nodes, new_node):
    pass

def lww(updates):
    pass

def union_merge(updates):
    pass

def lost_by_lww(updates):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Do wall-clock timestamps alone establish a correct application merge?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For fixed sets over N replicas, $|R\cap W|\ge |R|+|W|-N$ . Thus R=W=3 with N=5 forces at least one shared member. This is a set fact, not a complete consistency proof. Shard and replication counts describe different dimensions of the layout.

Worked example

Five replicas use read sets and write sets of size three. The lower bound on overlap is 3+3−5=1. Enumerating all three-member sets confirms every pair overlaps. A read still needs the right version-selection and concurrency rules; intersection alone does not tell which stored value is newest or committed.

Reference code

The following example uses the Python standard library and does not call a remote service.

from itertools import combinations
replicas=set(range(5))
sets=[set(x) for x in combinations(replicas,3)]
assert min(len(r&w) for r in sets for w in sets) == 1
assert 3+3-5 == 1
assert all(r&w for r in sets for w in sets)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Quorum arithmetic does not establish a full consistency contract. Sharding is not replication. CAP availability is a precise failure-model property, not the same as an ordinary monthly uptime percentage.