Tech Dive on the CAP Theorem

We'll talk about the CAP Theorem and why it's useful. Plus, we'll delve into common misconceptions and then classify real world databases (MongoDB, DynamoDB and Cassandra) in terms of the CAP Theorem.

February 28, 2024

Hey Everyone!

Today we’ll be talking about

  • Tech Dive on the CAP Theorem

    • What is the CAP Theorem and why is it used

    • Common Misconceptions with Consistency, Availability and Partition Tolerance

    • Evaluation the CAP Theorem with Real World Examples (DynamoDB, MongoDB and Cassandra)

    • The PACELC Theorem and it’s improvements on CAP

  • Tech Snippets

    • Advice for Negotiating Job Offers with Meta

    • Different Ways of Implementing Authorization

    • Using Wide Events for Observability

    • How I turned my Open Source project into a Business

    • Benchmarking Databases with Graphs

Tech Dive on CAP Theorem

If you look into distributed databases, you’ll quickly come across The CAP Theorem with people throwing around terms like CP/AP databases, BASE, PACELC and more.

The CAP Theorem is fundamental to distributed databases and is extremely important to be aware of. However, its use is also controversial with many distributed systems developers. Many argue that it can be misleading as a way of describing databases and that there are better alternatives available.

What is the CAP Theorem

In the layman’s definition, the CAP Theorem describes a trade off your distributed system must make between 3 possible guarantees.

  • Consistency - every read operation will always return the most up-to-date data regardless of which node you read the data from. This means that all nodes in the distributed database must store the most up-to-date data.

  • Availability - every read/write operation to a node in the distributed database will give you “an answer”. However, for reads, this answer might be stale data. For write requests, the write might not propagate to all the other nodes in the distributed database (meaning other nodes may return stale data to reads).

  • Partition Tolerance - The system will continue to operate even if there are network partitions and nodes in the distributed database aren’t able to talk to each other. You might have a scenario where the nodes in Europe are separated from the nodes in the US due to a network failure. A partition tolerance guarantee means that the database will continue to operate; each partition will operate independently and continue to process requests from clients within their partition.

The layman’s definition is that of these 3 guarantees, you can only pick 2. It’s not possible to have a database that gives all 3 of these guarantees.

Then, you can use this to label certain databases as “CP” (picks consistency and partition tolerance) and “AP” (picks availability and partition tolerance).

Frankly, you could probably get away with giving this definition in a technical interview. But… it’s wrong (if you’re being generous you might just call it extremely misleading).

To answer why, we’ll have to delve into each of these guarantees.

Partition Tolerance

We’ll start with the most frequent error, which is viewing partition tolerance as a choice. This is false.

If you’re creating a distributed database, you can’t just choose whether you want partition tolerance. Your database must do something when there is a network partition and nodes can’t communicate with each other (at some point there will be network issues between the nodes).

In that scenario, you can either design your system to optimize for availability and always respond with some data (even though this data might be out of date if there was an update on one of the partitioned nodes) or you can optimize for consistency and have your database respond with “error - there’s a network partition”.

(In practice, this is not a binary choice and you’ll pick something in between. We’ll delve into that further below.)

If you want a database where you don’t have to deal with partition tolerance, then you should go with a single, centralized database with something like Postgres or MySQL. However, you can only scale that database with vertical scaling (upgrading the hardware).

Consistency

With consistency, there’s a huge number of different consistency models that you can adhere to. Here’s an awesome map that goes through the different models and how strong each one is.

In the CAP Theorem, Consistency actually refers to a specific consistency model called Linearizability.

A TLDR of linearizability is just that your distributed system will behave like a single machine in terms of reads/writes (from the point of view of the clients). Each operation appears to take effect at a single moment in time, and all the other operations appear to take effect either before or after that point. This ordering is the same across all database nodes.

You can have multiple clients accessing your distributed database, with each modifying state with write requests or querying state with reads. These requests will be sent to different nodes in your database.

If the database provides a linearizability guarantee, then the responses the clients receive will make it seem like all these clients are talking to the same node (a singular node instead of a distributed system).

Martin Kleppmann (author of Designing Data Intensive Applications) has a great video on his YouTube channel where he delves into Linearizability.

Availability

The actual definition of availability is a bit different from how the term availability is typically used in computing (with an SLA, SLOs, nines, etc.).

Under a network issue, the CAP theorem assumes that the database will break up into partitions, where each partition contains database nodes and clients.

Clients in a certain partition can’t talk to nodes in a different partition. Database nodes can only talk to other nodes in the same partition.

CAP Availability means that the nodes in your partition (assuming you’re a client) will always give you a non-error response.

However, this response can be stale data for read requests. For write requests, it has to accept the write, but it won’t guarantee that all the nodes in the database will get updated on the write. The nodes in the other partitions may not see the write and send stale data to their users who query for it.

This is the first part of our tech dive on the CAP theorem.

In the full article, we’ll delve into

  • Commonly used Distributed Databases (DynamoDB, MongoDB, Cassandra) and why classifying them as CP/AP is misleading.

  • Consistency options for Reads/Writes offered by DynamoDB, MongoDB and Cassandra

  • The PACELC Theorem and it’s improvements on CAP

Thanks a ton for supporting Quastor. I really appreciate it!

Tech Snippets

Advice for Negotiating Job offers with Meta

Meta is one of the few big tech companies that is hiring aggressively right now. While this is great if you’re looking for a job, this can give Meta quite a bit more leverage in negotiations (especially if you don’t have other offers).

This is a really interesting blog post with many useful tips on how you can improve your position with negotiating a job offer.

One great piece of advice in the blog post is to ask the hiring manager for their email when you interview with them. After the offer-stage, if the recruiter is pressuring you to sign on quickly, then you can just email the hiring manager and ask for a few more days of time. They almost always say yes.

interviewing.io/blog/how-to-negotiate-with-meta

Different Ways of Implementing Authorization

There’s tons of different strategies/technologies for authenticating users. You can use a standard password, an email magic link, SMS message, YubiKey and much more.

This is a great blog post that delves into different methods and talks about their pros/cons. It includes a discussion of OpenID Connect, WebAuthn, standard passwords and more.

apuchitnis.substack.com/p/identity-authentication-and-authorisation

Using Wide Events for Observability

There’s a lot of confusion around Observability in terms of what best practices are. The current advice is to implement “Metrics, Logs and Traces“ and we’ve spent past Quastor articles delving into how many companies have done that.

Ivan Burmistrov is a Principal Engineer at ShareChat and he was previously a software engineer at Meta.

He wrote a great blog about Meta’s Observability tooling and how they do it. They rely on Wide Events, which are similar to JSON documents.

isburmistrov.substack.com/p/all-you-need-is-wide-events-not-metrics

How I turned my Open Source project into a Business

Andris Reinman is the founder of EmailEngine, a bootstrapped business he’s building that makes it easier to integrate email management in your code. He’s also the creator of Nodemailer (a open source project to easily integrate email into nodejs apps).

He wrote a great post about mistakes he made and how he scaled his business to give him a full-time income (~6100 euros per month with steady growth).

He experimented with open source models of business but quickly found that it was extremely difficult to get users to pay. Instead, he pivoted to requiring users to purchase a license key.

He talks about how revenue quickly scaled from the change.

docs.emailengine.app/how-i-turned-my-open-source-project-into

Benchmarking Databases with Graphs

Many of the common database benchmarks you see are known to be poor representations of real-world workloads. They’re mainly just used because they’re easy to run and repeatable.

In this blog post, Marc Brooker proposes a new way of benchmarking databases by using graphs to model database transactions

brooker.co.za/blog/2024/02/12/parameters.html