CAP Theorem & Caching

SECTION 1Notebook Summary#

Hand-copy this. Dense and telegraphic; every line expands in the Detailed Notes below.

SECTION 2Detailed Study Notes#

Picture a bank running on one server. It works — until that server dies, and every customer is locked out of their money at once. So you add a second server with a copy of the data, and a third. Now nobody is locked out by a single failure. But you have quietly created a new problem: you deposited ₹5,000 on server one, and a moment later someone checks their balance on server two, which has not heard the news yet. Which number is correct — and which do you show? Every idea in this note grows out of that one uncomfortable moment.

2.1The CAP Theorem#

The CAP theorem says a distributed system can guarantee at most two of three properties at once: consistency, availability, and partition tolerance. "Distributed" just means your data lives on more than one machine that must talk over a network. Once that is true, CAP tells you that you cannot escape a trade-off — you only get to choose which pain you accept.

Let us define the three plainly before using the jargon.

Here is the part people miss. In a genuine distributed system, partitions are not optional — networks fail, and you must tolerate that. So P is effectively mandatory, and the real, live decision is always consistency versus availability. That reframing is the whole theorem.

2.1.1The three CAP choices in practice#

The third pairing, CA, only exists where there is no network to partition — a single server with a standalone database. It is consistent and available because there is nothing to fall out of sync. But it is not really a distributed system, and it carries a single point of failure: if that one machine dies, everything dies. It also cannot scale out. So in interviews, CA is the "technically true, practically irrelevant" corner.

2.2Strong vs Eventual Consistency#

Strong consistency means every read returns the latest write; eventual consistency means replicas may briefly disagree, then converge. The word "eventually" is doing real work — it names the gap between "master updated" and "all replicas caught up".

Go back to the two-server bank. You write ₹50 to a variable on the master (it was ₹40). The master now says 50. The replica still says 40 until the change is copied over. If a read lands on the replica during that window, it sees 40 — stale. A CP system refuses that read until the replica catches up; an AP system serves the 40 and lets you catch up later. That copy lag — maybe two or three minutes in a bad case — is the "eventual" in eventual consistency.

One clarification that resolves a lot of confusion: what actually needs replicating is the data, i.e. the database. Your backend services are just copies of the same application code — deploy the same container image to four servers and they are interchangeable, holding no unique state. The database is the shared source of truth, so keeping replicas in agreement is a database responsibility, not something your application logic handles. [+] This is also why locking (below) lives in the DB.

2.3Data Replication#

Replication is keeping copies of your database (and services) on multiple machines so no single failure takes you down. You designate one copy as the master (or primary), which takes writes, and one or more replicas (or slaves) that mirror it. The interesting question is how the master tells the replicas about a new write — and how long it waits for them.

The core mechanism is the same across modes: when the master commits a write, it records that committed transaction in a log. Replicas continuously tail that log, spot the new commit, and replay the identical operation on themselves. A commit cannot be rolled back, so replaying it is safe. The three modes differ only in when the master considers the write "done" for the client.

2.3.1Asynchronous replication#

The master commits and replies to the client immediately, without waiting for any replica. Replicas catch up later by reading the log. Fast for the client, but if the master dies before a replica has caught up, those writes are lost. This is the common default.

2.3.2Synchronous replication#

The master writes locally but does not commit or reply yet. It pushes the write to the replicas and waits for all of them to acknowledge they have saved it. Only then does the master finalise its own commit and return success to the client. This gives strong consistency — the client is not told "done" until every copy agrees — at the cost of latency, since the slowest replica sets the pace.

2.3.3Semi-synchronous replication#

The middle path, and the one most real systems pick. The master writes locally and pushes to all replicas, but waits for only at least one acknowledgement before confirming success to the client. The remaining replicas sync asynchronously afterwards. This cuts the risk of data loss (the write survives on at least two machines) without paying the full latency of waiting for everyone.

2.4Caching#

A cache stores frequently used data in fast memory (RAM) so repeated requests skip the slow trip to the database. Imagine 10,000 people opening the same product page in a minute. Without a cache, that is 10,000 identical read queries hammering your database. With one, the first request fills the cache and the other 9,999 are served straight from memory — the database sees roughly one query.

The read path has two outcomes. A cache hit means the data was in the cache — returned fast, straight from RAM. A cache miss means it was not: the app reads the database, stores the result in the cache, and returns it, so the next identical request will hit. The payoffs are faster responses, lower latency, less database load, and better scalability.

2.4.1Types of cache#

2.4.2Eviction, expiration, invalidation#

RAM is small, so a cache cannot keep everything. Three mechanisms manage that scarce space.

Eviction decides what to drop when the cache is full. LRU (least recently used) drops whatever has not been touched in the longest time — it keeps hot data around. LFU (least frequently used) drops whatever has been accessed the fewest times. FIFO drops the oldest entry regardless of use — simple, but weaker than LRU.

Expiration (TTL, time-to-live) stamps each entry with a lifespan. A user profile might live 10 minutes, a product list 30. When the TTL expires, the entry is removed and the next request refetches from the database. TTL stops the cache serving something forever-stale.

Invalidation handles the case where the underlying data changes before its TTL is up: when you write to the database, you also delete or update the matching cache entry so nobody reads the old value.

2.4.3Caching strategies#

These describe who talks to what, and in what order on reads and writes.

2.5Redis, and why it beats Memcached#

Redis is an in-memory database, most often used as the cache in system design. Because it keeps data in RAM, reads and writes are extremely fast — far faster than a disk-based store. RAM's weakness is that it is volatile: lose power and you lose the data. Redis answers that with persistence — periodically it takes a snapshot of its in-memory state and writes it to disk, so after a crash or restart it can reload. You get RAM speed and disk-backed recovery.

Beyond caching, Redis is horizontally scalable (run many instances across servers), supports rich data structures rather than plain key–value, and doubles as session storage, a rate limiter, a message queue, and a publish/subscribe bus. Memcached, by contrast, is a lightweight key–value cache: simpler and fine for basic lookups, but no persistence, no replication, no rich types.

2.6Interview & Practice Q&A#

2.7Key Takeaways#

• In a distributed system P is mandatory, so CAP is really a live C-vs-A choice made per partition.
• CP for correctness-critical data (banking), AP for uptime-critical data (social); CA only exists on a single server.
• Replication modes trade latency for durability: async (fast, lossy) → semi-sync (balanced, promotable) → sync (safe, slow, fails on a down replica).
• The commit log is the spine of all replication; locking and ACID are the database's job, not the app's.
• Caching trades a small stale-data risk for big wins in latency and DB load; manage it with eviction (LRU/LFU/FIFO), TTL, and invalidation.
• Strategy picks the read/write path: cache-aside (default), read-through, write-through (consistent), write-back (fast but crash-risky).
• Redis = RAM speed + disk persistence + rich features; the default cache over Memcached.

SECTION 3Microexercises#

Reading proves you recognise these ideas. These prove you can use them. Attempt each before opening the walkthrough.

3.1Exercise 1 — Diagnose the replication config#

replication:
  mode: synchronous        # master waits for replica acknowledgements
  wait_for: all            # every replica must ack before commit
  ack_timeout_seconds: 30  # then give up
  on_timeout: fail_write   # return an error to the client

replication:
  mode: semi_synchronous   # wait for at least one replica
  wait_for: 1              # >= 1 ack, not all
  ack_timeout_seconds: 30
  on_timeout: fail_write   # still fail rather than lose durability
# remaining replicas sync asynchronously afterwards;
# any ack'd replica is promotable on primary failure

3.2Exercise 2 — Build a cache-aside read#

cache = {}   # stand-in for Redis: key -> value (TTL handled by set_with_ttl)
db = {"p1": {"name": "Desk Lamp", "price": 1200}}

def set_with_ttl(key, value, ttl):
    cache[key] = value   # assume TTL expiry is handled for you

def db_read(id):
    return db.get(id)    # returns the row dict, or None

def get_product(id):
    # TODO: implement cache-aside
    ...

def get_product(id):
    if id in cache:              # cache hit
        return cache[id]
    row = db_read(id)            # cache miss -> go to DB
    if row is None:
        return None
    set_with_ttl(id, row, 300)   # fill cache for next time
    return row