Consistency and the CAP theorem

When you keep copies of data on different machines, those copies can disagree. The CAP theorem says that if the machines can't talk to each other, you have to pick: either every read gets the latest data (consistency) or every request gets some answer (availability).

Networks do fail, so you can't really opt out of that. The question is what you want to happen when it does.

A common way to control this is with quorums. Say you keep three copies. You might need two of them to confirm each write, and read from two on every request. Any two copies overlap with any other two, so a read always reaches at least one copy with the latest write.

Even when the network's fine, waiting for more copies to agree takes longer, so you're also trading speed for consistency. You don't have to make one choice for your whole product, either. Different data can work differently.

• Don't call a whole system "CP" or "AP." Decide for each kind of data.
• Say what the user actually sees when copies disagree.
• Tie your choice back to what it'd cost the business.

Booking the last hotel room

A hotel has one room left. Two people click 'book' at the same moment, one in London and one in New York. Your data is copied to servers in both places.

1. If each region accepts bookings locally and syncs later, both people get a confirmation. When the copies sync, you find out you've sold the room twice.
2. That's unacceptable for bookings, so this data needs strong consistency: one place decides. For example, the hotel's inventory has a single primary region, and both bookings go there.
3. There, a transaction checks there's a room and takes it. Only one booking can win. The other person gets 'sorry, just sold out'.
4. The New York user waits an extra 70 ms or so for the round trip to London. That's fine for a booking.
5. If the network between regions is down, New York can't book that hotel until it's back. You chose correctness over availability for this data.
6. The hotel's photos, reviews and description don't have this problem. Those are copied everywhere and can be a few minutes stale.

Things interviewers tend to ask once you've brought this up.

What's the difference between CAP consistency and ACID consistency?

They're different things with the same name. CAP consistency means every read sees the latest write. ACID consistency means a transaction leaves the data valid by your rules, like no negative balances.

What's PACELC?

An extension of CAP. During a partition you choose availability or consistency, and Else, when things are normal, you still choose between latency and consistency.

How do you handle two copies that disagree after a partition?

Last write wins is simple but loses data. You can keep both versions and let the app merge them, or use data types designed to merge, like counters that only add.

What does 'read your writes' look like in practice?

After a user changes something, send their reads to the primary for a short time, or include a version so a replica waits until it's caught up.

• Labeling the whole system CP or AP.
• Saying 'I'll use eventual consistency' without saying what the user sees in the meantime.
• Forgetting that strong consistency costs latency even when nothing's broken.
• Using last-write-wins for something like a balance or inventory count.
• Mixing up replication lag with a network partition.

• Relational vs non-relational databasesPick a database based on how you'll actually use it.
• Sharding and consistent hashingSplit data across machines and keep it balanced.
• Caching strategiesMake reads faster, and figure out what to do when data changes.