Strong Consistency in Distributed Systems: The Paxos Algorithm

In the world of algorithms, Paxos stands out like a sore thumb.

Distributed Consensus with multiple servers and databases for a log line.

Most real-world systems implement algorithms based on three factors:

1. Usefulness
2. Ease of implementation
3. Testability

Paxos has been a rare case for over a decade where the first factor has outweighed the other two.

It is extremely useful, very hard to understand, even harder to implement, and even harder to test.

In this article, we understand the motivation behind Paxos, what makes it complex, and how it works.

Wait! Why am I reading this?

You may have heard of eventually consistent data. (Different parts of your system have different states. These parts are expected to fall in line eventually. Hence the name.)

This could be a cache holding a stale value or a downstream system waiting for an update. In most cases, eventual consistency is tolerable.

But sometimes, it's not tolerable. Imagine a booking system for movie tickets. Customers expect to get a seat after making a payment.

They'll be furious to see someone else sitting in their seat on reaching the venue. Expect a Popcorn plus Nacho fight.

What's a simple solution?

The best way to avoid this is to make your system strongly consistent through transactions. The fundamental unit of performing transactions is a lock.

You could use a 2-phase commit for this. Unfortunately, it doesn't scale well.

You could also try Quorum, used often in distributed databases. But this doesn't work, since a Quorum is an agreed-upon value, not a lock on the value.

Okay. How does Paxos help?

Paxos is a hybrid between quorum-based systems and two-phase locking. Here is the basic idea.

1. Paxos expects most nodes to first note a proposed value. This can be thought of as the first phase of a 2-phase commit.
2. It then commits the transaction, where a majority of the nodes must acknowledge the commit.
3. If anything goes wrong in the above steps, the system works fine. (Lock failures result in restarting the above two attempts).

That sounds simple. Where is the complex bit?

You asked for it.

1. What if multiple machines try to commit a value together?
2. How long will you hold locks, if at all? Should we override values every time we get a new proposed value?
3. How do you ensure that the above algorithm terminates in a reasonable amount of time?
4. Isn't the above algorithm inefficient? What can you do to speed up read and write queries?
5. What if a new machine were to be added to the system? How would you notify the rest of the cluster? Would you just restart the entire system instead?

These are some of the challenges when it comes to implementing the algorithm. Even if you can work through the edge cases of the algorithm, the above points will haunt any software engineer's implementation and test cases.

But there is some good news: It shouldn't matter!

Paxos has been implemented in popular open-source projects like Apache ZooKeeper. It also forms the heart of Google Chubby. Instead of reinventing the wheel (a very complex wheel), we can use these systems as a black box to take distributed locks.

So, what should I do?

1. If you are not a back-end engineer, this blog is sufficient to know how Paxos works at a high level.
2. If you are a back-end engineer, you may want to dive deeper into the algorithm here.

As always, let me know your thoughts and suggestions in the comments below.

Cheers!