The ICONIC Database Consensus Algorithm

Added: 2026-05-07

[00:00:00]Paxos is a very important algorithm in distributed databases. It's probably the most popular distributed consensus algorithm. Raft is kind of the new kid on the block, the contender, and that's become very popular, but for many years Paxos was the thing.

[00:00:17]So, [snorts] how does it work? You have a couple of different categories of nodes and labels that you can place on these. So, one category of node is your proposer. A proposer is responsible for receiving a request from a client, like, "Hey, insert this new key-value pair, insert this new row in the database."

[00:00:34]And so, then it's going to be responsible for being the one to say, "Okay, I've gotten this request. Now I'm going to coordinate amongst the other nodes and see if we can commit this."

[00:00:42]Next, we have acceptors, and these are servers in the group that are able to accept commands from a proposer, basically, where a proposer can say, "I want to commit this," and it has to get consensus from some number of acceptors.

[00:00:56]And then there's another class that officially is a part of Paxos called the followers, which are members that we will pass on confirmations to. They're essentially just following the acceptors and the proposers. So, we're going to have a request come in, and we're going to say, like, "What do we want this to be?" We'll We'll insert um ID 10, the name Joe, right? So, we're we're thinking about this database like key-value pairs. So, what the proposer is going to do, it has received this request, and it needs to say, "Okay, before we commit this, I'm just going to ask all of the acceptors that it is aware of in this group and say, 'Are you willing to accept this?'" And we're going to pass along a special identifier. So, as time progresses in Paxos uh commit, every request or every round that comes from a proposer has to have an ID, and this is like a monotonically increasing ID, so that we can properly sequence things, and we'll see why that's important in a bit. We're going to send out five uh messages, or four, I guess, but the the five total nodes, and we're going to ask it to prepare for ID Uh we'll just give it ID two. So, we're going to give this insert ID two, and we don't even actually have to yet tell it this is the thing that we want to insert yet. We're just letting the acceptors know, "Hey, I want to get a consensus from you. Given this ID number two, are you okay with committing it?"

[00:02:22]We're sticking with best-case scenario, so all of these are going to come back and say, "I promise I'm willing to ignore any other messages that come in with prior IDs." Kind of like, "You get the priority, because I know that you're going to You're about to request to commit something." All of these respond back at some point, right? The the time that it takes depends on network latencies and all that. But basically, at this point in time, this green line here, we know that, "Okay, our prepare phase is complete. We know that I have a majority of acceptors ready to accept."

[00:02:54]And I technically don't even have to wait until all of these do. I only have to wait for a majority. So, then in the accept phase, this sounds really silly, but we'll see why this matters. This is where we actually put the request out.

[00:03:05]We say, "Request for that ID two that I had told you before, let's insert Oh, what happened to my name? 10 Joe, right? This is what we're going to insert.

[00:03:17]So, accept uh ID two and then the the key-value pair 10 Joe. This is what I'm inserting.

[00:03:24]So, then all of these get sent out.

[00:03:27]Pretty basic. Eventually, once we get a response back from two, like we might even only get a response back from two, and then we know we have a majority, so we can go ahead and commit. Obviously, the others eventually will come back as well, but even if maybe [snorts] one of them doesn't come back till after, we can go ahead and say, "We have a successful commit once there's a majority." And the reason why that majority is important is because later on, we might get a request that comes in from a client, "Select the user with uh ID 10, right?" And so, in order for me to know for sure whether or not I actually have this user committed to the database, I would have to get agreement when I go to do this search from a majority of them. So, I couldn't just go look at a single acceptor and say, "Hey, do you happen to know whether there's a user with ID 10?"

[00:04:19]Because at this point in time, it's possible that that request, you know, would go and look only down at acceptor four, which I guess technically has it, but let's say Let's say it didn't even receive the message yet. Um so, there would have to be at this acceptor a chance for it to go look around and get a majority from the others to decide, "Hey, is it correct that we don't have a user with ID 10, or is there actually a majority out there that agrees that we do?" I mentioned before, every time you do one of those prepare requests or those commit requests, you have these monotonically increasing identifiers.

[00:04:55]And the way that you generate those is you actually have there's like an epic in time, so there's different epics that pass where there can be different proposers, and then from there you have a sequential ID, but it's simplest just to think about like an auto-incrementing integer. But we had a scenario like this, where I have a proposer, and this proposer is going to say, "Hey, we're going to start the preparation round to insert a new row, and the ID for this round is four." But it could be the case that for whatever reason, it's farther away, it's in a different data center, there's some network lag, like two of them are very quick, and I'll even show the response message in here, right? So, like two of those get back to the requestor very quickly. While that is hasn't even completed yet, somehow, maybe it's from a different proposer, even though I have this all in the same line, or maybe just somehow things got out of sync because of a delay of a request, in that interim, there's a request that goes out for, "Hey, I have something that I want to insert, but my ID somehow is three." So, in this case, I've sent all of these out, and this last one down, or actually I guess this middle one down here, this acceptor hasn't even seen ID number four yet. So, it was probably going to reply with, "Okay, yeah, that looks great. It's fine. We can go ahead and confirm that." But for acceptor number one and acceptor number three, both of these have already received a command with prep four, and we labeled this earlier, but the response, you can think of it as promise. So, it promises four, it promises four. That means that it will not accept a prep or a commit command from anything with a lower ID than that, because this is a part of consistency. An aspect of consistency is the ordering of elements and when they got inserted, because if you're trying to insert two rows that potentially overwrite or conflict with each other, you have to know which order to write them in in order to know like what takes precedence over what. Otherwise, you don't have a consistent database. Because of this, a majority already replied with, "I promise I won't accept anything beyond four." And so, these other two are going to get a response of essentially no. Response back.

[00:07:01]>> [snorts] >> So, they're going to say, "I reject this request." And so, I got one back, but then it knows, "Okay, I got these these failure modes back from here."

[00:07:10]So, what is it going to do? It could just give up, or it could like send a message back to the application, ask it to retry, but eventually, this prep round is going to complete, right? And then maybe for this prep four round, maybe it continues and it does the commit. So, then at some point later on in this database, there probably would be a retry for this same one, cuz presumably it's something we do need to commit and insert into the database. So, we'd go and we do a retry round, try this again, and then hopefully this time around it would get successes back with promises, and then it could carry on to the next stage of the algorithm, right? Part of the reason why consensus algorithms they are complicated is because things can fail, or because systems are highly parallel and you can have different computers doing different things at the same time, you need a way to ensure that ordering stays consistent, and you stay consistent in the case of failures. Part of the reason why you need majority, right? It's like, "Okay, you could have this node right here." Like, maybe you All of the nodes say, "Hey, I accept," but then some point along the line, acceptor number three, in fact, we could have two things fail. So, let's say acceptor number three dies right here, and acceptor number two dies right here, right? So, now those can't function anymore. The nice thing is, because our total number of nodes in the set is five in this case, we can actually still be successful. So, uh that request is going to fail, right?

[00:08:36]Because these two nodes failed, but then we're going to get notified of that, and this one can reply back with I accept, and this can reply back with I accept, and we can still commit. So, yeah, Paxos is a little bit um complicated, a little bit hard to wrap your head around. There are like a bunch of different scenarios you could potentially run through. So, if you're really interested in like learning this deeply, what I would recommend is go get a whiteboard, watch the Google talk, watch this talk, but build some of these diagrams yourself, and then literally just walk through different scenarios, right? Like, once you feel like you have a pretty good understanding of the pseudo code of the algorithm, then go, like, "Okay, what happens if that request just failed instead, right?"

[00:09:18]Well, in this case, maybe not that big a deal, cuz that just means, "Okay, maybe maybe this acceptor three node actually failed all the way back here." But if it failed at that point in time, technically, we still got consensus at this phase.

[00:09:32]And then this next phase here, too, we had lost another one, but thankfully, we still had enough to get consensus.

[00:09:38]But then you could say, "Okay, what happens if, like, this one also failed?

[00:09:42]Somehow there's some catastrophic thing where right around the same time, three of my servers all went down."

[00:09:47]Well, in that case, we've now reached a point where we actually cannot even accept new writes, because we have to have a a majority to accept new writes.

[00:09:55]So, basically, this database is in a state where it's just in limbo until an engineer can go and spin up a new node, or if it's like in the cloud, right? You'd have to create a new node and add it to the group, and there's probably a time period where data replication has to get caught up so that it is ready to actually start receiving new requests.

[00:10:14]So, that's like a more significant problem, right? And that's also this balance of whenever you're doing these kinds of databases, you can have like a replication factor of three, which can basically only tolerate a single failure. Bumping up to five means you can tolerate two failures. Bumping up to seven means you can tolerate three failures. So, trade-offs, right? More machines, you can tolerate more failures, but it also costs more money, and you probably will see more failures because you have more machines in your cluster.

[00:10:43]So, the the perpetual trade-off of running of designing data-intensive applications.