The book DDIA is really cool.

Lately, I've been diving deep into the book Designing Data-Intensive Applications by Martin Kleppmann.

Why am I doing this? The ideas in this book are classic system design concepts, foundational building blocks of modern large-scale distributed software systems that allow them to be reliable, scalable, and maintainable. I've always wanted to understand them in a deeper way, as I find the topic incredibly fascinating. I'm seeing many of these concepts come up in my day job as well, so I thought it would be a worthwhile investment to really understand them.

It's a really good read. It's the best combination of breadth and depth when it comes to system design content. I want to share my notes on what I thought was one of the most interesting chapters in the book: Chapter 9, Consistency & Consensus.

Linearizable Consistency

This chapter, along with the previous one, The Trouble with Distributed Systems, gave me further proof that software systems will continue to need trusted human shepherds who know exactly how they work so that they can be managed well.

For instance, take the all-too-common need for a uniqueness constraint on certain columns in your database, like a user's username. You need to make sure that when two users concurrently try to sign up with the same username, only one of them wins. If you're going to store your user data in a distributed, replicated data store for fault tolerance and scalability, how are you going to make sure that once one client claims a username in one part of the world, no client in another part of the world is able to claim that same username if they are using a replica of the database that doesn't yet know that another user already claimed it?

This kind of uniqueness constraint requires what's called a linearizable data store: a storage service that provides clients with the illusion that there is only one copy of the data, even though, in reality, the data is replicated across many nodes for fault tolerance and distributed geographically for scalability. This essentially enforces a total ordering of all operations across all replicas: to a client, it seems as though every read and write atomically happened at one point in time. This means that for any two operations, we can say which one happened first. This is perfect for our unique username problem: if one client asks the database to claim a username and the write is acknowledged to the client by the database, every read from then on by any client should reflect this fact.

How do you implement linearizable storage?

To guarantee linearizability, you could literally just have one node holding the entire database and serving all clients' requests. The problem with this approach is that it is not fault-tolerant or scalable. Network problems, high load, and the database crashing will all make your application go down. The previous chapter, The Trouble with Distributed Systems, describes all the painful and incredibly frustrating ways that distributed systems can go wrong.

So we must use replication for fault tolerance and scalability. There are three main types of replication schemes: single-leader, multi-leader, and leaderless (click on these links to understand them; they are fairly easy to understand at a high level).

Only single-leader has the potential to be linearizable. In a single-leader setup, there is one leader node that serves both reads and writes and a bunch of followers that accept the replication of the database state from the leader. The followers only serve reads. But the problem with this setup is that if the leader acknowledges a write but crashes before that write is replicated to the followers, then any read that occurs from then on is not linearizable. If your single-leader setup is such that the leader is in one datacenter and some of the followers are in another, then a network interruption between the two datacenters can also render reads non-linearizable.

This is essentially what the famous "CAP theorem" says: under network partitions (P), application designers must choose between consistency (C) and availability (A). Availability, in the context of the CAP theorem, simply means that the storage service eventually gives clients a response, whether that response contains a linearizable read or not.

Although it is a popular concept when learning system design, Martin Kleppmann does not like the CAP theorem, and this sentiment is shared by many others in the software engineering community, including Navdeep Singh of Neetcode. This is because it's incomplete, and is sometimes presented as Consistency, Availability, Partition tolerance: pick two out of the three. That is not accurate, because network partitions are unavoidable. It also doesn't talk about another kind of network problem: even if you don't have network partitions, you can still have unbounded network delays between nodes. A more complete version of the idea that the CAP theorem is trying to capture is the acronym PACELC: under network (P)artitions, choose between (A)vailability or (C)onsistency; else, choose between (L)atency or (C)onsistency.

Consensus

So how can we build a linearizable storage system that is able to handle network faults? The answer is consensus. Consensus algorithms allow multiple nodes in a distributed system to come to an agreement on the total ordering of all operations in the database. These algorithms are beasts, and trying to understand them is not for the faint of heart.

There are many of these algorithms, the most famous ones being Raft and Paxos.

Formally, a consensus algorithm must satisfy the following four properties:

Uniform Agreement

• No two nodes decide differently.

Integrity

• No node decides twice.

Validity

• If a node decides a value v, then v was proposed by some node.

Termination

• Every node that does not crash eventually decides some value.

As we saw earlier, a leader node might die or be partitioned from the network. When using consensus, nodes in a distributed system typically send regular "heartbeat" signals to one another. If a follower thinks the leader might be dead because it is no longer receiving any communication from the leader, it promotes itself to a "candidate" for leader election, increments the global election term number, and casts a vote for itself. A vote among the nodes is started. All nodes typically only vote for the first candidate that asks them in a given election term.

Even after the leader is elected, before deciding on a write, the leader has to first propose the new value to be written and collect votes from the other nodes. Only then is the decision made to commit the write. A node votes in favor of a proposal only if it is not aware of any other node from a higher election term. Thus, if the vote on a proposal doesn't reveal that any higher-numbered election occurred, then the write is committed and acknowledged to the client.

If that was confusing to you, don't worry. I don't fully understand the ins and outs of what I wrote above myself either. But I think that's just the nature of consensus. There are so many edge cases that one can think about to question what I wrote. But I believe I have provided the best summary I can without introducing all of the auxiliary concepts like total order broadcast and two-phase commit that would bring a lot of context \ and make it a lot easier to understand. My suggestion: just read DDIA.

You can also check out those original papers on Raft and Paxos. I plan on doing so myself.

Conclusion

DDIA is making me really appreciate how many difficult trade-offs software engineers have to make when designing systems that meet the requirements of the business. It exposes how even many "obvious" features, like uniqueness constraints, have so many problems if you want to be able to provide low latency to your users while also maintaining consistency within your datastores.

I highly suggest everyone read this book if they're working with large-scale distributed data systems. It will enable you to better understand all of the trade-offs you're going to have to make to achieve the goals you want. It will also effectively remove from your brain the idea that AI has the potential to replace you as a software engineer. If you focus on the difficult problems like these, you won't be replaced.