CAP Twelve Years Later: How the Rules Have Changed

Ideas you will meet

CAP Theorem

Consistency, availability and partition tolerance trade-offs.

Consistency Models

Linearizable, causal and eventual consistency explained.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• System Design Foundations · 12 minConsistency, availability and the CAP theoremWhat goes wrong when data lives on several machines, and the vocabulary for choosing what to guarantee.Read hereClose

  The problem

  On one machine, data has one value. Spread it over several machines and new questions appear:

  • If I write to machine A, when can machine B see it?
  • If A and B cannot talk to each other, should they keep serving requests?
  • If two people change the same item at the same moment, who wins?

  Consistency models are the answers to the first question. The CAP theorem frames the second.

  Consistency: what a read may return

  From strongest to weakest, in plain words:

  • Strong (linearizable): once a write completes, every later read anywhere sees it. It behaves like one copy. Easiest to reason about, slowest and least available.
  • Read-your-writes: you always see your own updates, though others may lag.
  • Eventual: if writes stop, all copies will eventually agree. Reads may be stale in between. Fast and highly available.

  100%

  Figure SDA-FND-07-1 · Replica lag and eventual consistency · © forcsguy.com

  Stronger guarantees cost latency (replicas must coordinate) and availability (some must be reachable). Weaker ones are cheaper but push complexity to the application.

  The CAP theorem

  For a distributed data store, three properties are in tension:

  • Consistency (C): every read sees the latest write (in the strong sense above).
  • Availability (A): every request to a working node gets a response.
  • Partition tolerance (P): the system keeps working even when messages between nodes are lost or delayed.

  Networks do fail, so P is not optional. The real choice is what to do when a partition happens:

  100%

  Figure SDA-FND-07-2 · Choosing C or A during a partition · © forcsguy.com

  • CP systems (for example many coordination stores and strongly consistent databases) may reject requests rather than risk a wrong answer.
  • AP systems (for example many Dynamo-style stores) stay up and let replicas diverge briefly, then merge.

  A more useful lens: latency too

  Even without partitions, strong consistency costs time because replicas must agree. The PACELC idea adds this: if there is a Partition choose A or C, Else (normal operation) choose between Latency and Consistency. It explains why a store may feel slower when configured to be strongly consistent.

  100%

  Figure SDA-FND-07-3 · How many copies must confirm a write · © forcsguy.com

  Resolving conflicts

  If two replicas accept different writes, the system needs a rule:

  • Last write wins: simple, but silently drops one update.
  • Version vectors or merge logic: detect that the writes were concurrent, then merge or ask the user.
  • CRDTs: data types designed so concurrent updates always merge cleanly (used for counters and collaborative editing).

  Choosing per feature, not per system

  You rarely need one consistency level for the whole product. Use strong consistency where wrong data is costly (payments, inventory, seat booking) and eventual consistency where speed and uptime matter more (counts, feeds, recommendations). Many databases let you pick per query.

  A worked example: quorums with numbers

  A key is stored on N = 3 replicas. A write must be acknowledged by W of them, and a read asks R of them and takes the newest version.

  Setting	W	R	R + W > N?	What you get
  Fast reads	3	1	yes (4 > 3)	Strong reads, but one dead replica blocks writes
  Balanced	2	2	yes (4 > 3)	Strong reads; survives one replica down for both reads and writes
  Fast writes	1	3	yes (4 > 3)	Quick writes, slow reads, reads fail if any replica is down
  Very fast	1	1	no (2 < 3)	Fastest, but a read can miss the latest write: eventual consistency

  The rule R + W > N guarantees the set of replicas read overlaps the set that acknowledged the last write, so at least one has the newest value. Concretely, with W = 2, R = 2: a write of version 5 reaches replicas A and B; C is still at version 4. A read that asks B and C sees versions 5 and 4 and returns 5. Whichever two replicas you ask, at least one has version 5.

  100%

  Figure SDA-FND-07-4 · Why read and write quorums overlap · © forcsguy.com

  A story: the comment that disappeared

  A user posts a comment. The write goes to the primary and the page reloads, but the read is served by a replica that is 300 ms behind. The comment is missing, the user posts it again, and now there are duplicates.

  This is a read-your-writes violation, the most common user-visible consistency bug. Fixes, from cheapest to strongest:

  1. For a short time after a user writes (say 5 seconds), route that user's reads to the primary.
  2. Return the new item in the write response and show it on the page without re-reading.
  3. Track a version or log position from the write, and have the replica serve the read only when it has caught up to it.
  4. Make that data strongly consistent end to end (higher latency, fewer failure modes tolerated).

  Not every read deserves strong consistency. A like counter that is a few seconds old is fine; a balance after a transfer is not.

  What a network partition actually does

  Imagine a three-node store split into two nodes on one side and one node on the other.

  • A CP system (consistency over availability) lets only the side with a majority accept writes. The lone node refuses requests, which is unavailable but correct.
  • An AP system (availability over consistency) lets both sides accept writes. Everyone gets an answer, but the two sides now hold different versions, and after the partition heals the system must merge: last-write-wins (simple, can lose data and trusts clocks), version vectors that keep both and ask the application, or data types designed to merge (CRDTs such as counters and sets).

  100%

  Figure SDA-FND-07-5 · Behaviour during a partition · © forcsguy.com

  Mistakes people make

  • Reading CAP as "pick any two". Partitions happen whether you like it or not, so the real choice is what to give up during a partition. Without partitions you can have both.
  • Assuming "eventual" means "soon enough". It means "if writes stop, replicas converge", with no bound. Measure the real lag.
  • Last-write-wins on unsynchronised clocks. A node with a clock a second ahead silently overwrites newer data. Prefer logical versions.
  • One setting for the whole system. Choose per feature: strong for payments and inventory, eventual for counters, feeds and recommendations.
  • Forgetting the latency side. Even without partitions, stronger consistency costs round trips between replicas, a trade-off often called PACELC.

  Try it yourself

  Use the CAP theorem playground to partition a cluster and watch CP and AP behave differently, and the replication playground to see stale reads and what a failover loses. Then try the System Builder with replicas.

  More on this site

  Related reading

  • Amazon Dynamo: Highly Available Key-Value StoreWerner Vogels · AmazonCase Studies
  • Please stop calling databases CP or APMartin Kleppmann · martin.kleppmann.comBlogs
  • CAP Twelve Years Later: How the Rules Have ChangedEric Brewer · InfoQBlogs
  • Martin Kleppmann's BlogMartin Kleppmann · martin.kleppmann.comBlogs

  Show 6 moreShow fewer

  • Martin Kleppmann: Distributed Systems LecturesMartin Kleppmann · University of CambridgeYouTube
  • Amazon S3 strong consistencyAmazon Web ServicesDocumentation
  • Designing Data-Intensive ApplicationsMartin Kleppmann · O'ReillyBooks
  • Read Consistency with Database Replicas at ShopifyShopify engineers · ShopifyCase Studies
  • All Things DistributedWerner Vogels · AmazonBlogs
  • Aurora BlogAurora engineers · AuroraBlogs

  Open this lesson with its quiz and exercise

• Classic System Designs · 11 minDesign a web crawlerDiscover and download billions of pages politely and efficiently: the URL frontier, deduplication and avoiding traps.Read hereClose

  The problem

  A web crawler starts from some known URLs, downloads each page, extracts the links and follows them. Search engines use crawlers to build their index, and others use them for archiving, price tracking or monitoring.

  Requirements

  • Scale: about a billion pages a month.
  • Polite: do not overload sites, follow robots.txt.
  • Robust: bad HTML, huge files, slow servers and traps must not break it.
  • Extensible: later add new content types (images, PDFs).
  • Avoid fetching the same page twice.

  Estimates

  1 billion pages a month is about 400 pages a second on average. At roughly 500 KB each (HTML plus metadata), that is around 500 TB a month, so storage and network are the big costs.

  High-level design

  100%

  Figure SDA-CSD-05-1 · Crawler pipeline · © forcsguy.com

  1. The URL frontier hands out URLs to crawl next.
  2. Fetchers download pages (resolving names with a local DNS cache, since DNS lookups can dominate time).
  3. The parser validates and processes the HTML.
  4. A content-seen check drops pages identical to ones already stored.
  5. Links are extracted, normalised, filtered, and checked against URL-seen before going back to the frontier.

  The web as a graph

  100%

  Figure SDA-CSD-05-2 · Crawling is graph traversal · © forcsguy.com

  The URL frontier

  The frontier is the brain. It decides what to fetch and when.

  • Priority: important or frequently changing pages first. Priority queues ordered by a score (for example link popularity or freshness).
  • Politeness: one queue per host, and each host is handled by one worker that waits between requests (for example one request per second to a given site).

  100%

  Figure SDA-CSD-05-3 · URL frontier: priority and politeness · © forcsguy.com

  Because the frontier is huge, keep most of it on disk with an in-memory buffer at the front.

  Keeping one polite worker per host

  100%

  Figure SDA-CSD-05-4 · Politeness queues · © forcsguy.com

  Not doing the same work twice

  • URL seen: before queueing a link, check it. A Bloom filter (or a hash set partitioned across servers) keeps this small and fast. Normalise URLs first (lowercase host, remove fragments, sort query parameters).
  • Content seen: pages often exist under many URLs. Compare a hash of the content, or a similarity fingerprint for near duplicates, and skip repeats.

  Staying out of trouble

  • robots.txt: fetch and cache it per host, and obey it.
  • Spider traps: endless generated URLs. Cap URL length, link depth and pages per host.
  • Timeouts and size limits so one slow or giant response cannot stall a worker.
  • Dynamic pages: content built by JavaScript needs a rendering step, which is much more expensive.
  • Harmful content: filter spam or illegal material before storing or indexing.

  More ways to make it fast and robust

  • Two-stage frontier. Front queues carry priority (each queue has a score band and is picked with a bias toward the higher bands); back queues carry politeness (one host per queue). A URL passes through both, so you get "important first" and "gentle per site" together.
  • Freshness. Recrawl by observed change history, and re-visit important pages more often. Recrawling everything is too costly.
  • DNS is a hidden bottleneck. Lookups can take tens to hundreds of milliseconds and many resolver interfaces block a thread, so keep your own DNS cache and refresh it on a schedule.
  • Locality and timeouts. Put crawl servers near the sites they fetch from, and give each fetch a short timeout so one slow host cannot stall a worker.
  • Robots rules are fetched once and cached, then obeyed before each fetch.
  • Resilience. Spread URLs over downloaders with consistent hashing, checkpoint the crawl state so a crash resumes instead of restarts, and validate pages before storing them.
  • Extensible by modules. New content types (images, a copyright monitor) plug in after the downloader without redesigning the pipeline.
  • Noise. Skip ad blocks, spam and low-value pages with a quality filter; cap URL length and per-site page counts to limit spider traps, and have a person exclude sites that still trap you.
  • Beyond search. The same engine serves archiving, mining and brand or copyright monitoring.

  100%

  Figure SDA-CSD-05-5 · Plugging new modules into the crawler · © forcsguy.com

  100%

  Figure SDA-CSD-05-6 · Distributing the crawl · © forcsguy.com

  Scaling and reliability

  • Add many fetcher workers, partitioned by host (consistent hashing keeps assignments stable).
  • Make workers stateless and checkpoint the frontier, so a crashed worker's URLs are re-queued.
  • Spread crawlers across regions to be closer to the sites being fetched.
  • Re-crawl by schedule: pages that change often (news) are revisited more often than static ones.

  Worked numbers: why it is about many hosts, not one fast fetcher

  Target: 1 billion pages a month, about 400 pages per second, at about 500 KB each.

  • Bandwidth: 400 x 500 KB = 200 MB/s, about 1.6 Gbit/s sustained, before retries and robots.txt fetches. Many machines in several places, not one big link.
  • Politeness sets the shape. If you allow one request per second per host, then to fetch 400 pages a second you must be talking to at least 400 different hosts at the same moment. A single site with 100,000 pages would take 100,000 seconds, nearly 28 hours, to crawl at that pace. So a crawler is a scheduler that interleaves thousands of hosts, which is exactly what the per-host queues do.
  • Seen-URL memory. With 10 billion known URLs, an exact set of 8-byte hashes is 80 GB. A Bloom filter at about 10 bits per URL (1% false positives) needs 12.5 GB, and a false positive only means skipping a page you could have crawled.
  • Storage: 1 billion x 500 KB = 500 TB a month raw. Compress and deduplicate, and keep only what you will index.

  100%

  Figure SDA-CSD-05-7 · Throughput comes from interleaving many hosts · © forcsguy.com

  Staying fresh: not every page needs the same schedule

  Re-crawling everything monthly wastes effort on pages that never change and misses news that changes hourly. Practical schedules:

  • Keep the observed change history per page (did the content hash change since the last visit?). Visit pages that change often more frequently, and stable pages less often, within limits.
  • Use hints: Last-Modified, ETag and conditional requests (If-None-Match) let the server answer "not modified" in a few bytes.
  • Give importance a vote: popular pages, and pages that many others link to, are revisited sooner.
  • Keep a small fast lane for news and feeds, driven by sitemaps and feed updates.

  100%

  Figure SDA-CSD-05-8 · Recrawl by how often a page changes · © forcsguy.com

  Walking through a spider trap

  A calendar page links to "next month", which links to the next month, forever. A naive crawler follows it, fetching millions of near-identical pages from one host. Defences, layered: cap URL length and path depth; cap pages per host per period; detect repeating patterns (the same path with only a number changing); skip pages whose content hash you have seen; and let an operator add a rule when a site still traps you. None is perfect, so budgets per host are the safety net.

  Mistakes people make

  • Ignoring robots.txt and crawl-delay. It gets you blocked, and it is rude.
  • Not normalising URLs. HTTP://Example.com/a?b=1&a=2#top and http://example.com/a?a=2&b=1 are the same page. Lowercase the host, drop fragments, sort parameters, remove tracking parameters.
  • One slow host stalling workers. Always use timeouts and size limits.
  • Treating the frontier as a plain FIFO. It ignores priority and politeness.
  • Fetching JavaScript-built pages as plain HTML. The content may be missing; rendering is a separate, costlier pipeline.
  • No deduplication of content. The same article under ten URLs wastes storage and pollutes the index.

  Try it yourself

  Build the Bloom filter lab and measure its false-positive rate and memory against an exact set, then read the seen filtering lesson. The consistent hash ring lab shows how to assign hosts to crawler workers so assignments stay stable.

  Real-world reading

  Related reading

  • System Design (Karan Pratap Singh)Karan Pratap Singh · karanpratapsinghGitHub
  • CAP Twelve Years Later: How the Rules Have ChangedEric Brewer · InfoQBlogs
  • Tech Dummies: System Design Case StudiesNarendra L · Tech DummiesYouTube
  • Tumblr Architecture - 15 Billion Page Views a Month and Harder to Scale than Twitter - High Scalability -High Scalability engineers · High ScalabilityCase Studies

  Show 6 moreShow fewer

  • Cloudflare Learning Center: What is a CDN?CloudflareDocumentation
  • Scaling Pinterest - From 0 to 10s of Billions of Page Views a Month in Two Years - High Scalability -High Scalability engineers · High ScalabilityCase Studies
  • The Site Reliability WorkbookGoogle SRE team · O'Reilly / GoogleBooks
  • Performance Optimization on Image, Video, Page LoadGoogle engineers · GoogleCase Studies
  • Site Reliability Engineering at Dropbox - Tammy Butow, Site Reliability Engineering Manager at DropboxDropboxYouTube
  • The WhatsApp Architecture Facebook Bought For $19 Billion - High Scalability -High Scalability engineers · High ScalabilityCase Studies

  Open this lesson with its quiz and exercise

• Classic System Designs · 12 minDesign cloud file storage and syncStore files for millions of users and keep devices in sync: block-level chunking, deduplication, metadata, conflicts and sharing.Read hereClose

  The problem

  A cloud file storage service (think of a personal drive) stores each user's files, makes them available on all their devices, keeps them in sync and lets them share.

  Requirements

  • Upload, download and sync files on web, desktop and mobile.
  • Sync quickly across devices; show file history and allow restore.
  • Sharing with permissions.
  • Reliable: never lose a file; handle large files and flaky connections.
  • Efficient in bandwidth and storage.

  Estimates

  Suppose 50 million users with 10 GB each: about 500 PB of data. That makes storage cost and upload bandwidth central. It also means you must avoid re-uploading unchanged data.

  High-level design

  Separate file content from file metadata:

  100%

  Figure SDA-CSD-11-1 · Metadata and block storage architecture · © forcsguy.com

  • Metadata (names, folders, versions, permissions, ordered list of block hashes): a relational database with strong consistency, since many operations need correct, ordered updates.
  • File content: stored as blocks in distributed object storage, replicated for durability.

  Growing from one server

  100%

  Figure SDA-CSD-11-2 · From one disk to a scalable storage design · © forcsguy.com

  100%

  Figure SDA-CSD-11-3 · Replication within and across regions · © forcsguy.com

  Blocks make everything better

  The client splits each file into fixed-size blocks (for example 4 MB), computes a hash per block, and uploads only the blocks the server does not already have.

  100%

  Figure SDA-CSD-11-4 · File as an ordered list of block hashes · © forcsguy.com

  Benefits:

  • Delta sync: after an edit only the changed blocks are uploaded.
  • Resumable uploads and downloads.
  • Deduplication: blocks with the same hash are stored once, even across users (with care for privacy).
  • Cheap versions: a version is just a list of block hashes, so history costs little.
  • Blocks can be compressed and encrypted before storage.

  Before: upload the whole file

  100%

  After: upload changed blocks only

  100%

  What changed

  • Editing one page of a large file sends a few megabytes, not all of it
  • Identical blocks are stored once
  • A broken upload can resume from the last block

  Sync flow

  1. The client detects a local change, splits, hashes and asks the server which blocks are missing.
  2. It uploads missing blocks, then commits a new file version in the metadata service.
  3. The notification service tells the user's other devices (through a long-lived connection or long polling) that something changed.
  4. Those devices fetch the new metadata and download only blocks they lack.

  100%

  Figure SDA-CSD-11-5 · A sync conflict · © forcsguy.com

  Conflicts

  If two devices change the same file from the same base version, the second commit finds the base is out of date. The safe rule is to keep both: accept the first, and save the second as a "conflicted copy" so nothing is lost. Never overwrite silently.

  Metadata, consistency and notifications

  Data model. A user has devices (each with a push id) and a root namespace; a file row holds the latest state; a file-version table keeps read-only history so past revisions stay trustworthy; a block table maps each version to its ordered blocks. Any version can be rebuilt by joining its blocks in order.

  Strong consistency for metadata. Two clients must never see different file lists. Caches default to eventual consistency, so keep cache replicas in step with the primary and invalidate the cache on every database write. A relational database gives atomic, isolated updates natively, which is why it suits metadata better than a store where you would have to build those guarantees yourself.

  Why long polling can be enough for notifications. Updates flow only server to client and are infrequent, so a persistent two-way channel is more than needed; a client holds a request open, gets told "something changed", fetches metadata, then reopens. (WebSocket is the better fit for chat-like two-way traffic.)

  Upload sequence. Two things happen at once: the client registers metadata (status pending, others are told a file is arriving) and sends blocks through the block servers; when storage confirms the upload, a callback flips the status to uploaded and others are notified so they can pull metadata and then the blocks.

  Failure notes. A notification server may hold a million connections; if it dies, all of them reconnect elsewhere at once, which is slow, so spread reconnects out. Offline clients are served from a backup queue of pending changes. Block servers' unfinished jobs are taken over by others.

  Trade-off: uploading straight to storage is faster (one hop) but means chunking, compression and encryption must be reimplemented and trusted on every client platform, and clients can be tampered with; a central block tier keeps that logic in one place.

  Image: U.S. Department of Agriculture · Public domain · Source · Wikimedia Commons: Magnetic tape library at USDA

  The block pipeline and delta sync

  100%

  Figure SDA-CSD-11-6 · Block server pipeline · © forcsguy.com

  100%

  Figure SDA-CSD-11-7 · Delta sync: only changed blocks · © forcsguy.com

  Reliability and cost

  • Durability: store blocks in several locations, with checksums verified on read and repaired by background scrubbing.
  • Hot and cold tiers: recent files on fast storage, old versions and rarely used data moved to cheaper cold storage.
  • Limit version history (by count or age) to control cost.
  • Metadata scale: shard the metadata database by user id; most operations touch one user's data.
  • Large files: parallel block uploads, resumable and retried independently.

  Upload and download as sequences

  100%

  Figure SDA-CSD-11-8 · Upload with notification to other devices · © forcsguy.com

  100%

  Figure SDA-CSD-11-9 · Download after a change elsewhere · © forcsguy.com

  Sharing and security

  • Permissions (view, edit) stored with the file or folder, checked on every request.
  • Share links with optional expiry and password.
  • Encrypt in transit and at rest; consider client-side encryption for stronger privacy (which limits server-side features such as search and dedup).
  • Audit logs for access and changes.

  Worked numbers: why blocks and deltas matter

  Files are cut into blocks of about 4 MB, each identified by a hash of its content.

  • Editing a large file: a user changes one paragraph in a 1 GB file. Only the block(s) that contain the change differ, so the client uploads about 4 MB instead of 1 GB, roughly 0.4% of the data, and the sync finishes in seconds.
  • Deduplication: if a block's hash already exists in storage (the same file uploaded by another user, or a copy within your account), the server stores nothing new and just records that this file version uses that block. Popular files cost almost nothing to store again.
  • Raw capacity: with 10 million users x 10 GB the system holds about 100 PB. Three full copies would need 300 PB; erasure coding (for example 10 data pieces plus 4 parity pieces, a 1.4x overhead) needs about 140 PB while surviving the loss of any 4 pieces. That difference is tens of millions of dollars a year, so cold data is usually erasure coded, and hot data may be replicated.
  • Metadata (file names, folder trees, versions, block lists) is tiny by comparison but is read and written constantly, so it lives in a separate, strongly consistent database, not with the blocks.

  100%

  Figure SDA-CSD-11-10 · Delta sync: upload only the changed block · © forcsguy.com

  When two devices edit the same file

  A laptop is offline and edits plan.docx; meanwhile a phone edits the same file and syncs first. When the laptop reconnects it has a version based on a now-outdated parent. The server notices because the upload says "I am based on version 7" while the latest is 8.

  For files in general the safe approach is: do not silently overwrite. Keep the first writer's version as current and save the second as a conflicted copy ("plan (Laptop's conflicted copy).docx"), then let the user merge. For real-time collaborative documents, a different technique (operational transforms or CRDTs) merges edits automatically, but that is a separate design.

  100%

  Figure SDA-CSD-11-11 · Detecting a conflict by version · © forcsguy.com

  Mistakes people make

  • Uploading whole files. It wastes bandwidth and makes large files unusable on poor connections. Use blocks, deltas and resumable uploads.
  • Trusting client timestamps to decide the winner. Clocks differ; compare versions, not times.
  • Treating a rename or move as delete plus create. It re-uploads the data. Metadata should record moves without touching blocks.
  • Polling for changes. It wastes battery and server capacity. Use a long-lived notification channel that says "something changed, pull your list".
  • Mixing metadata and block storage. They have different access patterns and consistency needs.
  • Forgetting security. Encrypt in transit and at rest, check permissions on every request, expire share links, and scan uploads for malware if you serve them to others.

  Try it yourself

  Read the consistent hashing lesson for placing blocks across servers, and build the consistent hash ring lab to place block ids on storage nodes. The Builder's write-burst challenge shows why uploads and metadata updates benefit from a queue.

  More on this site

  Related reading

  • How Discord Scaled Elixir to 5,000,000 Concurrent UsersDiscordCase Studies
  • CAP Twelve Years Later: How the Rules Have ChangedEric Brewer · InfoQBlogs
  • Amazon S3 strong consistencyAmazon Web ServicesDocumentation
  • Designing Data-Intensive ApplicationsMartin Kleppmann · O'ReillyBooks

  Show 6 moreShow fewer

  • Concourse: Generating Personalized Content Notifications in Near-Real-Time at LinkedInLinkedIn engineers · LinkedInCase Studies
  • Rewriting the heart of our sync engineDropboxCase Studies
  • Fast Order Search using Data Pipeline and Elasticsearch at YelpYelp engineers · YelpCase Studies
  • Pagelets Parallelize Server-side Processing at YelpYelp engineers · YelpCase Studies
  • Real-time Presence Platform at LinkedInLinkedIn engineers · LinkedInCase Studies
  • GitHub Engineering BlogGitHub engineers · GitHubBlogs

  Open this lesson with its quiz and exercise