Bug: Fixed term / index comparison on voting

[undecidedapollo]

Moving the conversation from this PR #6

Original Comment: In the logic for when a node receives a vote request, it goes through a set of comparisons to know how to vote. If a candidate matches one of these failure conditions, the node votes "false" on that candidate. If all of the checks pass, the nodes vote "true", placing their vote for the candidate to be a leader. In terms of placing votes, specifically in the first term, if a candidate comes through and says they are term A, index B, the nodes that receive this vote request will only vote no if the term AND the index is greater. This causes data loss issues for when the term is the same but the nodes receiving the candidate request have a newer index.

Outcome: The PR contained no tests and once merged broke the tests, the PR was subsequently reverted.

[undecidedapollo]

@markwylde Thanks for the callout on the test, I should have looked into that on my original PR. After looking at the failing test, "removes conflicted entries", the test expects that node 1 is elected a leader after some sort of disconnect between the two nodes. Node 1 asks to be voted for but the check for whether a vote should succeed checks the current index and term vs. the last written index and term. Node 1 has the term set (artificially) to two but doesn't have any committed data for term two so that is effectively ignored in the voting process, since the comparison checks the .last.term property. Node 2 then asks for a vote because it does have written data newer in the same "written" term as node 1 so it is elected leader.

I'm not super familiar with the Raft implementation but after chatting w/ GPT and thinking about correctness of data, this seems like the correct behavior. Let me know your thoughts. If you think this is correct, I'll update the test and make a new PR.

[undecidedapollo]

I think it is also important to think about the scenario leading up to this state in the test. The only scenario that I am aware of where this could occur is that Node2 was the leader, Node1 got disconnected, and during this disconnection, Node2 continued to process new requests. These requests were added to its log but couldn't be committed because committing requires a majority (which was not possible due to the disconnection of Node1). Upon reconnection, Node2 should be elected the leader as it has newer data. Node1 would never have newer data as it couldn't become a leader on its own and since not being the leader wouldn't have uncommitted records in its log. The same applies for Node2 if it wasn't the leader before the disconnect, there isn't a way for it to become leader on it's own and therefore wouldn't have uncommitted log entries as it does in the test.

[undecidedapollo]

Here would be an updated copy of the test. Each commit should be written in order on node1 to bring it back up to date with node2.

  it('brings cluster up to date', (next) => {
    const command1 = { first: 'command' };
    const command2 = { second: 'command2' };
    const commandNotCommitted1 = { wrong: 'command' };
    const commandNotCommitted2 = { wrong: 'command2' };
    // node1 = new WoodenRaft({address: 8111, Log, adapter: require('memdown')});
    // node2 = new WoodenRaft({address: 8112, Log, adapter: require('memdown')});
    // node1 = new WoodenRaft({address: 8111, Log, path: './tmp/8111'});
    // node2 = new WoodenRaft({address: 8112, Log, path: './tmp/8112'});

    // add log entries
    node1.log.put({
      term: 1,
      index: 1,
      committed: true,
      responses: [{ address: 8111, ack: true }, { address: 8000, ack: true }],
      command: command1,
    });

    node2.log.put({
      term: 1,
      index: 1,
      committed: true,
      responses: [{ address: 8111, ack: true }, { address: 8000, ack: true }],
      command: command1,
    });

    node2.log.put({
      term: 1,
      index: 2,
      committed: false,
      responses: [{ address: 8112, ack: true }],
      command: commandNotCommitted1,
    });

    node2.log.put({
      term: 1,
      index: 3,
      committed: false,
      responses: [{ address: 8112, ack: true }],
      command: commandNotCommitted2,
    });

    node1.log.committedIndex = 1;
    node2.log.committedIndex = 1;

    node1.term = 2;
    node2.term = 1;
    node1.join(8112);
    node2.join(8111);

    node2.once('leader', () => {
      node2.command(command2);

      let timesChecked = 0;
      async function checkNodeCommit(command) {
        try {
          let newCommand;
          if (timesChecked === 0) newCommand = commandNotCommitted1;
          if (timesChecked === 1) newCommand = commandNotCommitted2;
          if (timesChecked === 2) newCommand = command2;
          timesChecked++;
          assume(command).deep.equals(newCommand);
          assume(node1.log.committedIndex).equals(1 + timesChecked);

          if (timesChecked === 3) {
            next();
          }
        } catch (ex) {
          next(ex);
        }
      }

      node1.on('commit', checkNodeCommit);
      node1.once('leader', () =>  next(new Error('Node1 should not have become leader')));
      node1.promote(); // Try to promote node1 but it should not become leader as it has a lower written index
    });
  });

[undecidedapollo]

@markwylde curious what the best next steps would be for this issue in your opinion. Do you think the bug is an issue and is the above helpful, or is there another approach we should take.

[markwylde]

Hi @undecidedapollo sorry for the delay.

I'm not really sure what to do this with to be honest. I've tried playing with your code, and asking ChatGPT back and forth but I always end up with the tests hanging or breaking.

[undecidedapollo]

Hey @markwylde, no worries. I'd be glad to go through and debug different tests to ensure the change above doesn't cause any unintended behavioral changes and update tests / document if there are any changes in behavior. Are the tests hanging for you with the above test code updated? If so, which tests are hanging for you?