1. The problem: why can't every replica always agree?

Instagram keeps several copies (replicas) of almost every piece of data — across machines, across availability zones, across regions — so that it survives failures and serves users nearby (see Core Principles). The moment there are two copies, a question appears: when one copy changes, what do readers of the other copy see, and when?

Copies are kept in sync by sending messages over a network. Messages take time (0.5 ms inside a data centre, ~100 ms between continents), and sometimes they don't arrive at all: a switch fails, a fibre is cut, a misconfigured firewall drops traffic, a garbage-collection pause makes a node look dead. Now consider two Instagram scenarios during such a network failure between the US and EU data centres:

• Alice (US) and Bob (EU) both try to register the username @sunset at the same moment. If both data centres say "yes", Instagram now has two accounts with the same username — a correctness bug that is painful to fix. If one data centre says "sorry, try again later", a user sees an error.
• Carol (EU) likes a post, and Dan (US) looks at the like count. If Dan sees 1,203 instead of 1,204 for a few seconds, nobody is harmed. Refusing to show Dan the post until the data centres can talk again would be absurd.

The same infrastructure, two opposite right answers. The CAP theorem explains why you must choose, PACELC explains the cost even when nothing is broken, and consistency models give you precise words for what you are choosing.

2. The CAP theorem, precisely

The CAP theorem was proposed as a conjecture by Eric Brewer (2000) and proved by Seth Gilbert and Nancy Lynch (2002). It is about a distributed data store with replicated data, and it uses three precise definitions:

The theorem: no distributed system can guarantee all three at once. More usefully: when a partition happens, you must give up either C or A.

2.1 Why it's really "CP or AP", not "pick any two"

The popular phrasing "pick two of three" is misleading. Partitions aren't a feature you can decline; in any system that spans more than one machine, networks will fail. A "CA" system — consistent and available but not partition tolerant — only exists on a single node (or a network that never fails, which doesn't exist). So in practice:

• CP: during a partition, nodes that can't confirm they have the latest data refuse (error or timeout) rather than risk returning stale data or accepting conflicting writes.
• AP: during a partition, every node keeps answering using whatever data it has, accepting that reads may be stale and writes may conflict; replicas reconcile after the partition heals.

When there is no partition, a well-built system can provide both C and A. CAP only tells you what must give during the failure.

2.2 A partition scenario, step by step

The proof is essentially this picture. Suppose a partition separates node US from node EU. A client writes to US; then another client reads from EU. EU has two options: answer with whatever it has (possibly stale — violating C), or wait/refuse until it can talk to US (violating A). Since the partition may last arbitrarily long, there is no way to do both.

2.3 Common misconceptions about CAP

• "CAP's C is ACID's C." No. ACID consistency means "transactions preserve application invariants" (e.g. balances never negative). CAP's C means linearizability — a statement about replicas and recency.
• "A CP system is usually unavailable." No. CAP's A is extremely strict: every non-failed node must answer. A CP system like etcd stays fully available on the majority side of a partition; only the minority side refuses. And partitions are rare — most of the time CP systems answer everything.
• "A whole database is CP or AP." Often it's per operation. Cassandra lets you choose consistency level per query; DynamoDB offers eventually consistent and strongly consistent reads; you can mix them within one application.
• "AP means no consistency at all." AP systems typically provide eventual consistency plus useful session guarantees, and often converge within milliseconds when the network is healthy.
• "CAP covers everything." It only describes behaviour during partitions and only one consistency model. It says nothing about latency in normal operation — which is why PACELC exists.

3. Examples of CP and AP systems

4. PACELC: consistency costs latency even without partitions

Daniel Abadi proposed PACELC (2010, published 2012) to fix CAP's blind spot: partitions are rare, but the trade-off between consistency and latency is paid on every single request.

if (Partition) { choose Availability or Consistency }
else           { choose Latency     or Consistency }

Why does consistency cost latency without partitions? To guarantee a read sees the latest write, either the write must be synchronously copied to other replicas before it's acknowledged, or the read must consult several replicas (or the leader). Both add round trips. Within a data centre that's ~0.5–2 ms; across regions it's ~50–150 ms per round trip. A globally linearizable write from Mumbai with a quorum spanning Virginia and Ireland costs hundreds of milliseconds — a huge price for a like.

Most modern systems are tunable, so treat these labels as defaults, not laws. The useful habit is to ask, for each feature: during a partition, would I rather return an error or stale data? And normally, is the extra latency of coordination worth it?

5. The consistency models spectrum

"Consistent or not" is too coarse. A consistency model is a contract between the data store and its users that says which values a read may return given the history of writes. Models range from strong (easy to reason about, expensive) to weak (cheap and available, harder to reason about).

5.1 Linearizable (strong) consistency

Definition: every operation appears to take effect atomically at a single instant between its start and its end, and all clients agree on that order, which respects real time. Equivalently: the system behaves as if there were one copy of the data. If a write completes before a read starts, the read must see that write (or something newer).

Instagram scenario — username uniqueness: Alice's sign-up request claims @sunset and gets "success". From that instant, any other sign-up anywhere in the world must see @sunset as taken. If even one replica could answer "available" after Alice's success, two accounts could get the name.

 time ──────────────────────────────────────────────────────────▶
 Alice:  |── claim @sunset ──| ✔ success
 Bob:                            |── is @sunset free? ──|  must answer "taken"
 Carol:          |──── is @sunset free? ────|            may answer either: it overlaps
                                                         Alice's write (concurrent)

How it's implemented: a single leader for the key (a PostgreSQL primary with a UNIQUE constraint) or a consensus protocol (Raft/Paxos, as in etcd or Spanner). Cost: every write coordinates with a leader/majority; unavailable on the minority side of a partition.

5.2 Sequential consistency

Definition: all clients see all operations in the same single order, and each client's own operations appear in the order it issued them — but that global order need not match real time. (A read may return an older value as long as everyone agrees on the sequence.)

Instagram scenario — DM conversation ordering: in a group chat, Ann sends "Dinner at 8?", then Ben replies "Yes!" and Cat replies "Can't, sorry". All three participants must see the messages in the same order on every device; it doesn't matter if Cat's phone receives the latest message a second later than Ann's. Implementation: a per-conversation sequence number assigned by one owner (the conversation's partition leader), so the total order is per conversation, not global — see Direct Messaging.

5.3 Causal consistency

Definition: operations that are causally related (one could have influenced the other — e.g. you read X then wrote Y) are seen by everyone in that order. Operations that are concurrent (neither knew about the other) may be seen in different orders by different clients.

Instagram scenario — comments and replies: Dan comments "Where is this?" on a photo; the author replies "Lisbon!". The reply was caused by the comment. Under causal consistency, no viewer can ever see "Lisbon!" without "Where is this?". Similarly, if Eve blocks Frank and then posts, Frank must never see that post — the block causally precedes the post. Two unrelated comments by strangers, however, may appear in different orders for different viewers.

 Dan:     write C1 "Where is this?"
 Author:            read C1 ──▶ write C2 "Lisbon!"      (C1 → C2: causal)
 Viewer X sees:  C1, C2            ✔
 Viewer Y sees:  C2 only           ✘ forbidden under causal consistency
 Viewer Z sees:  nothing yet       ✔ allowed (just not caught up)

Causal consistency is the strongest model that remains available during partitions (it can be served from local replicas), which makes it attractive for geo-distributed systems. Implementation: track dependencies (version vectors, or "this write depends on version v of that item") and delay making a write visible until its dependencies are visible.

5.4 Session guarantees: read-your-writes, monotonic reads, monotonic writes

These are weaker, per-client guarantees that fix the most user-visible anomalies of eventual consistency cheaply:

5.5 Eventual consistency

Definition: if no new writes are made to an item, all replicas will eventually return the same value. No promise about when, and no promise about what you see in the meantime. In healthy systems "eventually" usually means milliseconds to seconds.

Instagram scenarios: your friend's new post appears in your feed a few seconds after it was published (asynchronous fan-out through Kafka); a post's like count lags by a second; a celebrity's follower count is approximate; a new account becomes searchable after the indexer catches up. None of these hurt users, and all of them would be expensive to make strongly consistent at Instagram's write rates.

A stronger variant, strong eventual consistency, adds: any two replicas that have received the same set of updates are in the same state — no matter the order received. That's what CRDTs provide (section 8.3).

6. Quorums: tuning consistency with R + W > N

Leaderless stores like Cassandra and Dynamo-style systems let you tune consistency per request with quorums. Each key is stored on N replicas. A write is acknowledged once W replicas confirm it; a read queries R replicas and returns the newest version among their answers.

If R + W > N, every read set overlaps every write set in at least one replica,
so a read always contacts at least one replica holding the latest acknowledged write.

Across regions, Cassandra offers LOCAL_QUORUM (majority within the local data centre — low latency, PA/EL behaviour across regions) vs EACH_QUORUM (majority in every data centre — consistent across regions, but pays cross-region latency and fails if a region is cut off).

7. ACID vs BASE

Two philosophies for data stores, often contrasted:

Note that isolation (the I in ACID) has its own spectrum: read committed → repeatable read / snapshot isolation → serializable. Many databases default to weaker levels than serializable for performance, which allows anomalies like lost updates or write skew — a reminder that "ACID" is not a binary label. (Details in Databases.)

8. Conflict resolution: when replicas disagree

In AP (and multi-leader) systems, two replicas can accept concurrent writes to the same item. After the partition heals, the system must decide the final value. Three main approaches:

8.1 Last-write-wins (LWW)

Attach a timestamp to every write; when versions conflict, keep the one with the highest timestamp and discard the rest. Simple, and the default in Cassandra (per column).

Replica US: bio = "Photographer 📷"   ts = 10:00:00.120
Replica EU: bio = "Traveller ✈️"       ts = 10:00:00.115
After merge → "Photographer 📷"  (EU's write is silently discarded)

Problems: concurrent writes are lost, not merged; and clocks on different machines drift — if the EU server's clock is 50 ms ahead, its earlier write wins. LWW is fine when losing a concurrent write is acceptable (a profile bio edited from two devices at the same instant) or when writes are naturally unique (each like is its own row keyed by (post_id, user_id), so there's nothing to overwrite).

8.2 Vector clocks (version vectors)

A vector clock stores, per item, a counter for each replica that has modified it. Comparing two vectors tells you whether one version happened before the other or whether they are concurrent (a true conflict).

 start:       bio v = {US:1}                          "Photographer"
 US updates:  {US:2}          "Photographer 📷"
 EU updates (concurrently, from {US:1}):  {US:1, EU:1}  "Traveller ✈️"

 compare {US:2} vs {US:1, EU:1}:
   US: 2 > 1   but   EU: 0 < 1   → neither dominates → CONCURRENT → conflict!
   → keep both "siblings" and let the application (or user) merge them

 compare {US:2, EU:1} vs {US:1, EU:1}:
   every entry ≥  → the first is strictly newer → safe to discard the second

Vector clocks never lose a concurrent write silently, but they push merge logic to the application and add metadata per item. The original Amazon Dynamo used them (for shopping carts, merging by union — which famously could resurrect deleted items).

8.3 CRDTs (Conflict-free Replicated Data Types)

CRDTs are data structures designed so that concurrent updates can always be merged automatically and deterministically: the merge is commutative, associative and idempotent, so replicas that have seen the same updates converge to the same state regardless of order (strong eventual consistency).

• G-Counter (grow-only counter): each replica keeps its own count; merge = element-wise max; value = sum. A view counter incremented in US and EU never loses increments.
• PN-Counter: two G-counters, one for increments and one for decrements (likes and unlikes); value = P − N.
• OR-Set (observed-remove set): supports add and remove with "add wins" semantics for concurrent add/remove — e.g. the set of users who liked a post, or members of a group chat.
• LWW-Register, multi-value register, sequence CRDTs (for collaborative text editing).

# G-Counter for a post's view count, replicated in two regions
US = {"US": 1000, "EU": 0}       # US has counted 1,000 views locally
EU = {"US": 0,    "EU": 500}     # EU has counted 500 views locally

merge(a, b) = {r: max(a[r], b[r]) for r in a | b}
merge(US, EU) = {"US": 1000, "EU": 500}   → value = 1,500   (no lost increments,
                                             and merging twice changes nothing)

Redis Enterprise (active-active), Riak and Azure Cosmos DB offer CRDT-based types. The trade-off: only certain operations fit the CRDT mould (you can't enforce "username unique" with a CRDT — uniqueness is inherently a coordination problem), and metadata can grow.

9. Practical techniques: getting "consistent enough" cheaply

Most real systems run on eventually consistent replicas and add targeted techniques where users would notice anomalies.

9.1 Read-your-writes by reading from the leader after a write

With leader–follower replication, followers lag the leader by milliseconds to seconds. To make sure a user sees their own changes:

def update_profile(user_id, fields):
    leader_db.update(user_id, fields)
    session.set("recent_write_until", now() + 10s)      # remember this user just wrote

def get_profile(viewer_id, profile_id):
    # the author sees their own profile from the leader for a short window;
    # everyone else (and the author after the window) reads from a nearby replica
    if viewer_id == profile_id and now() < session.get("recent_write_until", 0):
        return leader_db.get(profile_id)
    return replica_db.get(profile_id)

Variations:

• Version/LSN tokens: the write returns the leader's log position (e.g. PostgreSQL LSN); the client sends it with its next read; the server reads from any replica that has replayed past that position, or waits briefly, or falls back to the leader. More precise than a fixed time window.
• Always read "own" data from the leader: e.g. your own settings page. Cheap if such reads are a small fraction of traffic.
• Client-side read-your-writes: the app inserts your new post or comment into the UI locally (optimistic UI) and reconciles with the server later. Instagram's heart turning red instantly is exactly this — the UI doesn't wait for the server, let alone for replicas.
• Write-through cache update: after writing a post, the Upload Service also updates the author's cached profile grid directly, so the author's next read hits fresh data even if the fan-out pipeline is behind.

9.2 Monotonic reads via stickiness

Route a given user's reads to the same replica (hash the user ID to a replica) so they never "go back in time" by bouncing between replicas with different lag. If that replica fails, re-pinning may cause one backwards step — acceptable for counts.

9.3 Strong consistency only where it's needed

• Unique claims (usernames, email addresses): a single-leader database with a UNIQUE constraint, or a compare-and-set via consensus. Keep the strongly consistent part tiny — just the claim — and replicate the rest asynchronously.
• Leases and fencing tokens for exclusive ownership (e.g. which WebSocket gateway "owns" a user's connection; which worker processes a partition).
• Idempotency keys make retries safe under at-least-once delivery, so duplicates don't become inconsistencies (one like per (user, post), one message per client-generated message ID).

9.4 Bounded staleness and invalidation

Caches are another source of staleness. Use short TTLs for data that changes, explicit invalidation on writes (delete the cache key after updating the DB), and versioned keys for immutable data (as with CDN URLs). Public papers from Facebook describe techniques such as leases in memcache to prevent stale sets and thundering herds — see Caching.

10. How Instagram chooses consistency per feature

This table is the heart of the lesson — the answer interviewers want when they ask "what consistency does your design provide?"

11. Trade-offs & common pitfalls

Common pitfalls

• "We'll be CA." Not an option for a distributed system — partitions happen. Say what happens during a partition.
• One consistency level for everything. Strong everywhere is slow and fragile; eventual everywhere leaks into correctness bugs (duplicate usernames). Choose per feature.
• Confusing CAP-C with ACID-C, or "eventual" with "never".
• Assuming R + W > N means linearizable. Sloppy quorums, LWW with clock skew and partial failures break it.
• Trusting wall clocks to order events across machines. Use logical clocks, version vectors, sequence numbers from a single owner, or bounded-uncertainty clocks (Spanner's TrueTime).
• Forgetting the read path after a write: a user writes to the leader then reads from a lagging replica → "my change disappeared". Add read-your-writes.
• Forgetting caches and search indexes are replicas too — they have their own staleness.
• Silent data loss via LWW for data where concurrent updates are meaningful (counters as a single overwritten field instead of increments/CRDTs).

12. Real-world technologies

13. Interview corner

14. Check your understanding

Related lessons

• Replication — leader/follower, multi-leader, leaderless quorums and replication lag in depth
• Databases: SQL vs NoSQL — ACID, isolation levels and choosing a store
• Sharding — how partitioning interacts with consistency (cross-shard operations)
• Core Principles — availability, redundancy and failover
• Likes, Comments & Counters — eventual counters in practice
• Direct Messaging — per-conversation ordering and delivery guarantees
• Multi-Region Architecture — consistency across regions and active-active writes
• Caching — cache staleness, invalidation and leases