What is committed
A Raft leader in term T holds a log of L entries; each entry has its own term, and the terms do not decrease along the log. As replication proceeds, followers report to the leader how many entries of their log already agree with its log: “follower f has acknowledged m entries”. The leader counts itself too: it has all L.
Entry number i is committed if a majority of servers (more than half of n, counting the leader) have acknowledged at least i entries and entry i was made in the current term T. All the entries before it are committed with it. The commit boundary never decreases. After each acknowledgement print the number of the last committed entry.
Input
The first line holds n, L, T and the initial commit boundary c (n odd, 3 ≤ n ≤ 9, 1 ≤ L ≤ 105, 0 ≤ c ≤ L). The second holds the terms of the log entries in order: L numbers, non-decreasing, each from 1 to T. The third holds the number of acknowledgements q (1 ≤ q ≤ 2·105), followed by q lines “f m”: follower f (from 1 to n − 1; the leader is server 0) has acknowledged m entries (0 ≤ m ≤ L). The acknowledgements of one follower do not decrease. Initially every follower has acknowledged 0.
Output
q lines: the commit boundary after each acknowledgement.
The first example is the end of Figure 8 of the Raft paper. The entry of term 2 is already on three servers out of five but is not committed: the leader of term 4 commits it only together with its own entry, once that reaches a majority.
Examples
Example 1
5 3 4 1 1 2 4 4 1 2 2 2 1 3 2 3
1 1 1 3
Example 2
3 4 3 2 1 1 2 2 3 1 3 2 4 1 4
2 2 2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 6 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
An entry held by a majority is an entry with a number no greater than the (n/2 + 1)-th largest acknowledgement count. Which of these entries is the last one made in the current term?
2The idea
Terms along the log do not decrease, and T is the largest possible, so the entries of the current term are the tail of the log from some number first on (or there are none). Let M be the (⌊n/2⌋ + 1)-th largest acknowledgement count, counting the leader with its L: exactly that many entries are held by a majority. If M ≥ first, entry M is of the current term and held by a majority, and the boundary becomes max(c, M). If M < first, there are no newly committed entries, even if M is greater than c.
3Walkthrough
There are at most nine servers, and after each acknowledgement it is enough to sort nine numbers. Why the rule is exactly this is shown by the second scene of the article. An entry of an old term held by a majority can still be overwritten: a server whose last entry is newer by term wins an election with the votes of those whose last entry is that old one, and makes their logs match its own. But an entry of the current term held by a majority will never be overwritten: a future leader must get the vote of at least one member of that majority, and that member votes only for a log no worse than its own, so the winner’s log has the entry. That is why old entries are committed only “under cover” of a new one.
3+Solution
4Complexity
O(L + q·n log n).
5Common mistakes
- Counting only copies. The boundary M without the term check is exactly the mistake Figure 8 dissects: in the first example such a solution prints 2 already at the second acknowledgement.
- Forgetting the leader. Its log counts towards the majority too, and it has all L entries.
- The boundary going back. If the acknowledgements fall short of the previous boundary, it does not decrease.