3. Data and Consistency

How data is spread across machines and how to keep copies agreeing. Background: CAP theorem and its implications, Key-value stores, Power of Indexing, SQL vs NoSQL. Back to Fundamentals.

Replication

flowchart LR
    APP[App] -- writes --> P[(Primary)]
    P -- replicate --> R1[(Replica 1)]
    P -- replicate --> R2[(Replica 2)]
    APP -- reads --> R1
    APP -- reads --> R2

• Primary/replica: all writes to one node, copies serve reads. Scales reads and gives a failover target.
• If the primary dies, promote a replica. Async replication can lose the last few writes; sync replication is safer but slower.
• Replication lag: a user writes, then reads from a stale replica and sees old data. Fix: read your own writes from the primary for a short time.
• Multi-primary accepts writes in several places (e.g. one per region) but needs conflict resolution (last write wins, version vectors).

Sharding (partitioning)

Split one big dataset across many databases, each holding a shard.

flowchart TD
    APP[App] --> R{Shard router user_id mod 3}
    R -- 0 --> S0[(Shard 0)]
    R -- 1 --> S1[(Shard 1)]
    R -- 2 --> S2[(Shard 2)]

• Choose the shard key carefully: it should spread load evenly and match how you query (user_id is a good key for a per-user app).
• Sharded caches and hot-shard handling (replicate only the busy shard) are in Distributed Patterns.
• Problems to plan for:
• Hot shards (a celebrity user floods one shard).
• Resharding when you add nodes: with mod N, changing N moves almost every key.
• Joins across shards are expensive; denormalise or query in the app.

Consistent hashing

Fixes the resharding problem: adding or removing a node moves only a small share of keys.

flowchart LR
    subgraph Ring["Hash ring 0 to 2^32"]
    direction LR
    A((Node A)) --- k1[key1] --- B((Node B)) --- k2[key2] --- C((Node C)) --- k3[key3] --- A
    end

• Hash both nodes and keys onto the same ring. A key belongs to the first node clockwise from it.
• Add a node: it takes over only the keys between it and its predecessor. Remove a node: its keys go to the next node.
• Virtual nodes: each physical node appears at many points on the ring so load spreads evenly.
• Used by Cassandra, DynamoDB, memcached client libraries and CDNs.

import bisect, hashlib

def h(x): return int(hashlib.md5(x.encode()).hexdigest(), 16)

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.ring = sorted((h(f"{n}#{i}"), n) for n in nodes for i in range(vnodes))
        self.keys = [k for k, _ in self.ring]
    def get(self, key):
        i = bisect.bisect(self.keys, h(key)) % len(self.ring)
        return self.ring[i][1]

print(Ring(["a", "b", "c"]).get("user:42"))

Consistency models

• CAP: during a network partition choose consistency (reject some requests) or availability (answer, maybe stale).
• Quorum: with N replicas, write to W and read from R. If W + R > N, a read overlaps the latest write.

$ N=3 W=2 R=2   -> 2 + 2 > 3  -> strongly consistent reads
$ N=3 W=1 R=1   -> fast, but may read stale data

Resolving conflicting writes: vector clocks

When two replicas accept writes to the same key at the same time, which value wins? A vector clock is a list of (server, counter) pairs stored with each value.

$ write on A: D1 [A:1]
$ write on A: D2 [A:2]        # descends from D1, so D1 is simply replaced
$ write on B (from D2): D3 [A:2, B:1]
$ write on C (from D2): D4 [A:2, C:1]
$ D3 vs D4: neither contains the other -> CONFLICT, client must merge

Key-value store design (the idea)

flowchart LR
    C[Client] --> CO[Coordinator node]
    CO --> N1[(Node 1)]
    CO --> N2[(Node 2)]
    CO --> N3[(Node 3)]

• Spread keys by consistent hashing; replicate each key to the next N nodes on the ring.
• Writes go to memory plus an append-only commit log, then flush to sorted files on disk (LSM tree); Bloom filters skip files that cannot contain a key.
• Detect failed nodes by gossip (nodes swap heartbeat lists), and repair stale replicas by comparing Merkle trees or when reading.
• Temporary failure: a neighbour holds writes (hinted handoff) and passes them on when the node returns.

Unique ID generation

Auto-increment breaks once you have many database servers. Options:

Snowflake ID (64 bits)
| 1 bit sign | 41 bits timestamp (ms) | 5 bits datacentre | 5 bits machine | 12 bits sequence |