This chapter is from the book
This chapter is from the book
This chapter is from the book
Followers Commit Based on a High-Water Mark
As we’ve seen, leaders commit when they get acknowledgments from a Majority Quorum—but when do followers commit their log entries? In the three node example we’ve been using, it’s obvious. Since we know the leader must have added the log entry before it replicates, any node knows that it can commit since it and the leader form a Majority Quorum. But that isn’t true for larger clusters. In a five-node cluster, a single follower and a leader are only two of five.
A High-Water Mark solves this conundrum. Simply put, the High-Water Mark is maintained by the leader and is equal to the index of the latest update to be committed. The leader then adds the High-Water Mark to its HeartBeat. Whenever a follower receives a HeartBeat, it knows it can commit all its log entries up to the High-Water Mark.
Let’s look at an example of this (Figure 2.22). Bob sends a request (B1) to Neptune. Neptune replicates the request to Jupiter and Saturn. Jupiter acknowledges first, allowing Neptune to increase its High-Water Mark to 1, execute the update against its data store, and return success to Bob. Saturn’s acknowledgment is late, and since it’s not higher than the High-Water Mark, Neptune takes no action on it.
)
Figure 2.22 Leader tracks High-Water Mark.
Neptune now gets three requests from Alice (A1, A2, and A3). Neptune puts all of these into its log and starts sending replication messages. The link between Neptune and Saturn, however, gets tangled and Saturn doesn’t get them (Figure 2.23).
)
Figure 2.23 Nodes missing replication of log entries
After the first two messages, Neptune coincidentally sends out heartbeats, which alert followers to update their High-Water Mark. Jupiter acknowledges A1, allowing Neptune to update its High-Water Mark to 2, execute the update, and notify Alice. But then Neptune crashes before it’s able to replicate A3, as shown in Figure 2.24.
)
Figure 2.24 The High-Water Mark is propagated using HeartBeat.
At this point, here are the states of the nodes:
|
Jupiter |
Saturn |
Neptune |
|---|---|---|---|
gen |
1 |
1 |
1 |
hwm |
1 |
0 |
2 |
log |
B1 A1 A2 |
B1 |
B1 A1 A2 A3 |
Jupiter and Saturn fail to get HeartBeat from Neptune and thus hold an election for a new leader. Jupiter wins and gathers log entries. In doing this it accepts that A2 reached Majority Quorum and sets its High-Water Mark to 3. Jupiter replicates its log to Saturn, and when Saturn gets a HeartBeat with High-Water Mark of 3 it’s able to update its High-Water Mark and execute the updates against its store (Figure 2.25).
)
Figure 2.25 New leader replicates missing log entries and High-Water Mark.
Now, the state of the nodes is:
|
Jupiter |
Saturn |
Neptune |
|---|---|---|---|
gen |
2 |
2 |
1 |
hwm |
3 |
3 |
2 |
log |
B1 A1 A2 |
B1 A1 A2 |
B1 A1 A2 A3 |
At this point Alice times out of her A3 request and resends it (A3.2), which routes to Jupiter as the new leader. Just as this happens, Neptune starts back up again. Neptune tries to replicate A3, and is told that there’s a new generation of leader, so Neptune accepts that it’s now a follower of Jupiter and discards its log down to its High-Water Mark. Jupiter sends replication messages for A2 and A3.2. Once Jupiter gets an acknowledgment for A3.2, it can update its High-Water Mark, execute the update, and respond to Alice (Figure 2.26).
)
Figure 2.26 Old leader discards conflicting log entries.
Saturn and Neptune will update their states on the next HeartBeat from Jupiter.