The Storage Layer — CAP, PACELC & Replication

1 Why one database isn't enough

Everything we've built in earlier sessions — the load balancers, the application servers from Session 6 — eventually has to read and write data that outlives a single request: user accounts, messages, orders. That permanent home for data is the storage layer, usually a database. For a while, a single powerful database server handles it all. But a single server hits three hard walls.

The three walls of a single database

The fix for all three is the same big move: use more than one machine. We call each machine a node. A database spread across many nodes is a distributed database, and the whole collection working together is a cluster. There are two fundamentally different ways to spread data across nodes, and they solve different walls:

• Make copies of the same data on several nodes — called replication. This mainly helps the durability/availability and read throughput walls (Topic 8).
• Split the data into pieces, each piece on a different node — called sharding (or partitioning). This mainly helps the capacity and write throughput walls (Topic 8).

2 Consistency & the kinds of consistency

When can we even talk about consistency?

Consistency is always about data. A few consequences fall straight out of that:

• Stateless app servers cannot be consistent or inconsistent — they're stateless, they hold no data, so there's nothing to be in or out of sync. Asking "is this app server consistent?" is like asking "at how many km/hr is your door cooking the colour 9?" or the classic IIT ragging question, "what's the colour of an electron?" — the answer is simply undefined. The question doesn't apply.
• Consistency is typically discussed in the context of a database or a cache.
• There must be multiple copies of the same data (replication / caching). If there's only one copy, it's guaranteed up to date — you read and write the same place. The only way data goes stale is having multiple copies (database + cache, or database replicas).
• There must be a read after a write/update. If the data is static/immutable, there's no way to read stale data — it's never updated.

The kinds of consistency (a spectrum)

Immediate consistency (aka "Consistent")

• It is impossible for stale reads to happen — every read is guaranteed to read the latest data.
• Only possible when all the copies are always kept in sync, all the time (or you use a quorum).
• Always nice to have, but very hard to achieve — typically requires 2-phase commit, which means high latency and low availability. Because it's so costly, we do not always go with immediate consistency.

Eventual consistency (aka "Not Consistent")

• It is possible for some reads to be stale for some time. But if we wait long enough, eventually we'll be able to read the updated data.
• In 99% of cases, eventual consistency is good enough.

Data loss — no consistency whatsoever

• If it's possible for some data to be permanently lost, then there are updates that will never reflect — no matter how long we wait, the data never becomes consistent.
• Very rare. Only relevant for analytics, where the overall trend matters more than any individual data point.

3 Availability

Availability refers to whether a server can deny a request or not. If a server can deny a request, the system is "not available" / has low availability. If a server always satisfies the request, the system is "available" / has high availability. But the details matter — two classic interview questions:

4 Partition tolerance & the bank (A vs P)

What is partition tolerance?

A system is partition tolerant if it can continue functioning seamlessly in the face of network partitions. When a partition happens, if the system continues working at least partially (some availability might be lost, some consistency might be lost, but the entire system doesn't go down), it's partition tolerant. If any loss of communication between nodes brings the whole system down, it's not partition tolerant. Partition tolerance is very highly desired.

What is a network partition?

In a network of servers (a distributed system), if some subset of servers cannot communicate with the other subset, we have a network partition.

Availability vs Partition tolerance — the bank/ATM story

Tarun wants to withdraw money from his bank account via the ATM. In the backend, the bank replicates the account information — we don't want to lose account data if a server/hard disk crashes. When Tarun withdraws, the bank must update both copies to reflect the new balance. Now imagine a network partition happens and the two bank database servers can't communicate. Two cases arise:

When is a system NOT partition tolerant?

When any network partition brings down the entire system. This is very, very rare — about 99.99% of backend systems are designed to be partition tolerant.

5 The CAP theorem

The CAP theorem (proposed by Eric Brewer in 2000, later proven) is the most famous rule about distributed data stores. It gives you a fundamental limit of what you can achieve with distributed systems: a system can offer at most two of these three guarantees at the same time:

The three categories of system (with real percentages)

CAP — two ways to state it

1st definition: pick any 2. 2nd definition (the better one): when there's a network partition, you must choose between Availability or Consistency — you cannot have both. As long as there's no partition, you don't have to worry. The moment one happens, you choose C or A, not both.

Why you can't have all three during a partition

Picture two nodes, A and B, that normally sync. The network breaks — the partition. A write arrives at A. Node A faces an impossible choice:

• Accept the write (stay Available) → but B doesn't know about it, so a read from B is stale → you gave up Consistency.
• Refuse the write / make it wait until it can reach B (stay Consistent) → but now A isn't answering → you gave up Availability.

There's no third option while the cable is cut. That's the theorem in one breath.

6 The PACELC theorem

CAP has a blind spot: it only describes behaviour during a partition — a rare event. But a distributed database makes a consistency-vs-speed trade-off on every single request, all the time, even when the network is perfectly healthy. The PACELC theorem (Daniel Abadi, 2010) is an extension to CAP that fills that gap. Read it as a sentence:

The first half (P → A/C) is just CAP. The new, important half is the "ELC": latency (how long a request takes) is traded against consistency even when everything is healthy. To be strongly consistent, a node must wait to confirm the other copies agree before answering — and waiting is latency.

The four PACELC personalities

Each system gets a two-part label: its partition choice (PA or PC) and its normal-time choice (EL or EC).

7 Proof by story — Aditi's Reminder Service

Scaling up, then out

• Vertical scaling (scaling up): at first Aditi runs the reminder service alongside her day job; as requests grow, she quits and does it full time.
• Horizontal scaling (scaling out): she can't handle all the calls alone, so she hires Sanjana.

The angry customer (a consistency issue)

Customer: "Yesterday I called to remind me of my 11am flight. Then I called at 8am to ask my flight time and you said you don't remember. You lost my data and I missed my flight." Why? The write went to Sanjana, but the read came to Aditi, and Aditi's data was not in sync with Sanjana's. A consistency issue.

Protocol 1 — sync eventually (at night)

They copy each other's data each night before closing, so in the morning both have the same copy.

PROTOCOL 1 — Sync eventually (at night)

on WRITE(data):
    write data to MY diary only
    return SUCCESS                # fast: write in one place

every NIGHT (before closing):
    copy MY diary  -> OTHER diary
    copy OTHER diary -> MY diary  # both diaries now match

Q: Can there still be stale reads / angry calls? Yes — until the nightly sync, any read before the sync can be stale. But wait long enough and the data syncs (eventual consistency). Data can be stale (low consistency), but a write only touches one place (low latency).

Protocol 2 — sync immediately

Whenever one gets a call, they write to their own diary, put the customer on hold, call the other person, get them to write it too, and only return success when the other confirms. If the other returns an error, roll back (delete from own diary) and return error.

PROTOCOL 2 — Sync immediately (synchronous replication)

on WRITE(data):
    write data to MY diary
    put customer ON HOLD
    call OTHER person, ask them to write data
    if OTHER responds SUCCESS:
        return SUCCESS
    else:                         # OTHER returned error
        delete data from MY diary  # ROLLBACK
        return ERROR

on READ(query):
    answer from MY diary directly   # no waiting — both have all data

This gives immediate consistency — data is always in sync because every write goes to both diaries. But latency is higher (the client waits on hold while Aditi calls Sanjana), and throughput suffers — every call is now effectively made twice (to both Aditi and Sanjana), which undercuts the horizontal scaling we did.

Q: Does Protocol 2 apply to reads too? No — only writes. On a read, Aditi and Sanjana each respond independently from their own diary (both have all the data). So no waiting on reads (low latency for reads).

Vacation time (a server is down — but no partition)

Sanjana goes on vacation. No availability issue — calls just route to Aditi. No network partition — Sanjana is simply on leave. When she returns, she syncs with Aditi's diary before taking calls — no consistency issue. This holds for both protocols: since Sanjana is absent, Aditi keeps writing to her own diary (even in Protocol 2), and Sanjana syncs up on return. So no availability and no consistency issue — because there's no partition; it's just that a server (Sanjana) is down.

The big fight (a real network partition)

Aditi & Sanjana have a big fight and refuse to talk — a network partition.

8 Replication vs Sharding

Replication means explicitly, by choice, having multiple copies of the same data, stored on different servers. These are the two foundational techniques for scaling the storage layer, and they are not the same thing — confusing them is a classic beginner trap.

Isn't replication bad? (the normalization angle)

In RDBMS we study normalization, which says redundancy (duplicate data) is bad because it leads to anomalies (read / write / delete). Consider an un-normalized table:

• Update anomaly: rename HLD → "High Level Design" but miss a row → the two rows now disagree, effectively creating an extra course.
• Delete anomaly: delete Sanjana and you accidentally delete the course DBMS (she was its only entry).

The normalized design removes these anomalies by splitting into separate tables:

Why do we need replication? Durability ≠ replication

Replication vs Sharding — the core distinction

Pros & cons

How replication works (leader–follower)

The most common pattern is leader–follower (master–slave / primary–replica): one leader accepts all writes and streams changes to several read-only followers. We go deep on this — sync vs async, failover, lag — in Session 8.

How sharding works (the shard key)

The rule that decides which row goes to which shard is the shard key (partition key). Range-based splits by key ranges (A–H, I–P, Q–Z) — easy range scans but risks hot spots. Hash-based hashes the key — even load, but range scans become hard.

# pick which shard a user lives on
def shard_for(user_id, num_shards=4):
    return hash(user_id) % num_shards   # 0, 1, 2, or 3

shard_for("alice")   # -> 2  (alice's row lives on node 2)
shard_for("bob")     # -> 0  (bob's row lives on node 0)
shard_for("carol")   # -> 1

What about caching? Caching is kind-of like replication

In caching, your data lives in 2 places: the database and the cache. So it resembles replication — but it's not pure replication.

★ Putting it all together

Today we left the comfort of a single machine and entered the world of distributed storage. Here's the one-paragraph story tying all the topics together:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original class notes / handout (Google Doc) — open the shared class material for this session.
• Class handout: "[SST-2028] CAP-PACELC".

Papers, docs & deep dives

• Eric Brewer — CAP Twelve Years Later — the author of the CAP theorem revisits and clarifies what it actually claims.
• Daniel Abadi — PACELC — extends CAP to reason about latency vs consistency when there is no partition.
• Designing Data-Intensive Applications (Kleppmann) — chapters on replication and consistency models that ground both theorems.