4 ms·

Fun fact: in the extremely highly cited "In Search of an Understandable Consensus Algorithm (Extended Version)" there's a gap. In the otherwise very good figur

Fun fact: in the extremely highly cited "In Search of an Understandable Consensus Algorithm (Extended Version)" there's a gap. In the otherwise very good figure 2: >If successful: update `nextIndex` and `matchIndex` for follower but it is never stated how either `matchIndex` or `nextIndex` should be updated (on successful response). In section 5.3 it's only stated that "Eventually `nextIndex` will reach a point where the leader and follower logs match." I went to the TLA spec in Diego's github repo for his dissertation and found the answer to be HandleAppendEntriesResponse(i, j, m) == /\ m.mterm = currentTerm[i] /\ \/ /\ m.msuccess \* successful /\ nextIndex' = [nextIndex EXCEPT ![i][j] = m.mmatchIndex + 1] /\ matchIndex' = [matchIndex EXCEPT ![i][j] = m.mmatchIndex] but this is predicated on followers responding with `mmatchIndex`, which is not included in the response as stated in the "In Search of" paper. I discovered this while TAing a class on consensus protocols, during which I built an implementation (in rust) and though I was confused about `matchIndex` as well, I just did what I thought was the natural thing, i.e. on receipt of a successful `AppendEntries` response I do *(self.leader_state.next_index.get_mut(node_id)) = self.get_last_log_index() + 1; *(self.leader_state.match_index.get_mut(node_id) = self.get_last_log_index(); I emailed Diego to find out if this was a reasonable solution but he told me he didn't remember the protocol clearly enough to advise. Nice to know everyone forgets things sometimes :)

valzam 5y ago
I took the MIT Distributed Systems course and also got stuck several times on how exactly something should be done. The Raft paper is good but in practice I found it quite difficult to reason about when certain things should be allowed to happen. I.e. when a "supposed" leader receives a ping from another leader in a newer epoch, how often do I check that? Should I just interrupt what I was doing? Only after I finished processing a command? I am probably overthinking it and should just keep it simple and have the leader produce "wasted" entries until it realises that there is another accepted leader. I tried implementing Raft without looking at any existing implementations, but that is probably not a good idea. It's very easy to get lost in the weeds.
- jimsimmons 5y ago
  The moment you see another leader with higher epoch you cecede and become a follower. This should be part of message recieve logic and has highest priority. Any actions you might take are moot anyway because higher epoch leader always the source of truth
  - valzam 5y ago
    That is what I was thinking. But does that mean you just pepper your command processing logic with guards that you are still actually the leader? I think one mistake I made is trying to run the different parts of the protocol in parallel, i.e. processing a message, accepting messages, sending heartbeats etc. It probably makes more sense for the raft part to basically be single threaded.
    - jimsimmons 5y ago
      > That is what I was thinking. But does that mean you just pepper your command processing logic with guards that you are still actually the leader? Yep. It's annoying to code it this way but you have to. One way to make this relatively clean is via throwing and catching exceptions if your language has good support for it. Also agree re single-threadedness. In some ways raft assumes a single state machine loop running on a node at any point. Concurrency introduces additional non determinism to the state machine and isn't really accounted for in the formal spec. I've heard great things about etcd source and how clean it is. I've never studied it but it might give you some pointers on best practices.
    - _vvhw 5y ago
      If you can avoid multithreading in the design of your consensus protocol, this also means that your implementation becomes more deterministic. If you can have the design fully deterministic by stubbing out the message passing, storage and time source (by representing time as ticks), then you can do deterministic simulation fuzzing like we do in TigerBeetle, which is a high velocity testing technique for finding/reproducing/fixing interesting (and rare) distributed systems bugs: https://github.com/coilhq/tigerbeetle#simulation-tests https://github.com/coilhq/tigerbeetle#simulation-tests
ditsing 5y ago
In my implementation, in each AppendEntries request, the leader includes X commits starting from nextIndex. The follower either accepts all X commits, or reject all of them. If the follower accepted all commits, the leader moves nextIndex to (X + nextIndex when the request was sent). See code here (matchIndex = nextIndex + X - 1): https://github.com/ditsing/ruaft/blob/master/src/sync_log_entries.rs#L205 https://github.com/ditsing/ruaft/blob/master/src/sync_log_en....

valzam 5y ago

I took the MIT Distributed Systems course and also got stuck several times on how exactly something should be done. The Raft paper is good but in practice I found it quite difficult to reason about when certain things should be allowed to happen. I.e. when a "supposed" leader receives a ping from another leader in a newer epoch, how often do I check that? Should I just interrupt what I was doing? Only after I finished processing a command? I am probably overthinking it and should just keep it simple and have the leader produce "wasted" entries until it realises that there is another accepted leader. I tried implementing Raft without looking at any existing implementations, but that is probably not a good idea. It's very easy to get lost in the weeds.

jimsimmons 5y ago
The moment you see another leader with higher epoch you cecede and become a follower. This should be part of message recieve logic and has highest priority. Any actions you might take are moot anyway because higher epoch leader always the source of truth
- valzam 5y ago
  That is what I was thinking. But does that mean you just pepper your command processing logic with guards that you are still actually the leader? I think one mistake I made is trying to run the different parts of the protocol in parallel, i.e. processing a message, accepting messages, sending heartbeats etc. It probably makes more sense for the raft part to basically be single threaded.
  - jimsimmons 5y ago
    > That is what I was thinking. But does that mean you just pepper your command processing logic with guards that you are still actually the leader? Yep. It's annoying to code it this way but you have to. One way to make this relatively clean is via throwing and catching exceptions if your language has good support for it. Also agree re single-threadedness. In some ways raft assumes a single state machine loop running on a node at any point. Concurrency introduces additional non determinism to the state machine and isn't really accounted for in the formal spec. I've heard great things about etcd source and how clean it is. I've never studied it but it might give you some pointers on best practices.
  - _vvhw 5y ago
    If you can avoid multithreading in the design of your consensus protocol, this also means that your implementation becomes more deterministic. If you can have the design fully deterministic by stubbing out the message passing, storage and time source (by representing time as ticks), then you can do deterministic simulation fuzzing like we do in TigerBeetle, which is a high velocity testing technique for finding/reproducing/fixing interesting (and rare) distributed systems bugs: https://github.com/coilhq/tigerbeetle#simulation-tests https://github.com/coilhq/tigerbeetle#simulation-tests

ditsing 5y ago

In my implementation, in each AppendEntries request, the leader includes X commits starting from nextIndex. The follower either accepts all X commits, or reject all of them. If the follower accepted all commits, the leader moves nextIndex to (X + nextIndex when the request was sent). See code here (matchIndex = nextIndex + X - 1): https://github.com/ditsing/ruaft/blob/master/src/sync_log_entries.rs#L205 https://github.com/ditsing/ruaft/blob/master/src/sync_log_en....