SD7.3 · LESSON 3 OF 6

Network partitions

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

THE IDEA

Network partitions

When the network splits a cluster, the two sides cannot talk. A system that stays consistent lets only a side with a majority (3 of 5) accept writes and makes the other side refuse: it gives up availability for those nodes. A system that stays available lets both sides accept writes: it gives up a single agreed order, and the sides hold different values until they merge. That forced choice exists only while the partition lasts, which is why "pick any two" is a poor summary of CAP.

nodes on the left of the partition3

left 3 node(s): serve writes right 2 node(s): refuse writes writing nodes: 3 of 5, refusing: 2 only a side with more than half of the nodes (3 or more) may accept writes, so two sides never both commit

While the network is partitioned, a system cannot promise both linearizable behaviour and a successful response from every non-failed node (the CAP result). Outside a partition you need not give either up, so "pick two" is not a free choice. State what happens to the affected operations.

Move the partition and pick the policy.

Predict first. Is CAP a rule to pick any two properties regardless of network conditions?

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

Decide who serves during a split by hand, then write both policies.

nodes on the left of the partition3

nodes that accept writes (3|2 split) nodes that refuse distinct values if both sides write CAP = pick two regardless of the network? (yes/no)

To do: Five nodes are split by a partition into groups of 3 and 2. A system that keeps strong consistency lets only a group holding a majority (more than half of 5) accept writes. How many nodes can accept writes?
To do: How many nodes refuse writes (the consistency-preserving choice)?
To do: An availability-first system accepts writes on BOTH sides: one side writes "a", the other "b". Distinct values the replicas hold until the partition heals?
To do: Is CAP a rule to pick any two properties regardless of network conditions? Type yes or no

Part 2. Do it in code

majority(n): the smallest group size that is more than half of n.
cp_serving(groups, n): groups is a list of group sizes (a partition of n nodes). Return the number of nodes that can accept writes if only a majority group may (at most one group qualifies).
cp_refusing(groups, n): n minus cp_serving.
ap_values(groups, writes): writes maps a group index to the value written on that side; groups without a write keep "old". Return the sorted list of DISTINCT values the replicas hold across the partition.
reconcile_lww(values): values is a list of (value, timestamp); keep the latest timestamp (ties: the greater value). Return (kept, lost) where lost is the list of other values.
must_choose(partitioned): True only while a partition exists: that is when consistency and availability conflict.

def majority(n):
    pass

def cp_serving(groups, n):
    pass

def cp_refusing(groups, n):
    pass

def ap_values(groups, writes):
    pass

def reconcile_lww(values):
    pass

def must_choose(partitioned):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Is CAP a rule to pick any two properties regardless of network conditions?

ANoBYes

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.