Addressing an issue where when next_index for a peer is discovered to be 0, the heartbeat message sending call of the leader will panic when trying to set prev_log_index to -1. Fix by setting prev_log_index to 0 when next_index is 0.

This PR implements section 7 of the Raft paper, i.e. Log Compaction. Now, Replicas will merge logs into snapshots to avoid accumulating too many logs that hoard memory. Replicas now support InstallSnapshot RPCs, meaning that a Leader can detect when a Follower is so far behind that the logs it's missing have already been compacted, and then transmit the snapshot to the follower instead of transmitting a particular log entry. Non-leader nodes now know how to treat and respond to InstallSnapshot RPCs.

The StateMachine trait has been extended to provide Little Raft user with ability to save and load state to and from permanent storage. The raft_unstable test has been updated to randomly drop and shuffle messages, causing Replicas to retransmit snapshots, asserting the behavior of the new InstallSnapshot RPC.

Currently the enum is

pub enum TransitionAbandonedReason {
    // NotLeader transitions have been abandoned because the replica is not
    // the cluster leader.
    NotLeader,
}

However, transitions can also be dropped by a replica if at some point it gets disconnected from majority of the cluster thinking it is still a leader accepting transitions; upon reconnecting to the rest of the cluster, such a replica will drop uncommitted transitions due to a discrepancy with consensus achieved by the cluster majority.

Raft is an asynchronous protocol, so one of the challenges when using it is getting feedback on whether a particular transition has or hasn't been applied. To solve this problem, Little Raft calls the user-defined register_transition_state hook every time any transition changes its state. This way the library user can keep track of transitions as they move through the Queued -> Committed -> Applied pipeline.

However, a transition could be ignored by the replica it has been submitted to. The most likely reason for that is because the replica is not the cluster leader. Another possible reason is that the replica used to be the leader, then got disconnected from the rest of the cluster, kept accepting transitions for processing for a while and then had to drop them when connecting back to the cluster that in the meanwhile elected another, newer leader (the stale leader dropping uncommitted transitions is the desired behavior in this case).

To let the user know when a transition got dropped, we should add Abandoned state to the TransitionState enum. We could also have that Abandoned state wrap around another type so that we could signal the particular reason why a transition has been abandoned -- NotLeader vs UncommittedUnsynced. Naming could be improved.

Heap-allocated things like Strings and Vecs are not copyable so don't require Copy trait for StateMachineTransition to simplify state machine transition implementation.

I am seeing a deadlock where process_append_entry_request_as_follower() is unable to grab cluster.lock() when attempting to send an append entry response.

I am not sure if the scenario matters, but I am seeing this during initial leader election where two nodes first become candidates, then the other one wins, but the other one -- after becoming a follower -- never manages to register the other one as a leader and send a response to heartbeat because it just waits indefinitely for cluster.lock() to be released.

I don't understand why but reducing the scope of state_machine.lock() seems to cure the issue:

diff --git a/little_raft/src/replica.rs b/little_raft/src/replica.rs
index c13219e..5168743 100644
--- a/little_raft/src/replica.rs
+++ b/little_raft/src/replica.rs
@@ -705,23 +705,28 @@ where
             return;
@@ -705,23 +705,28 @@ where
             return;
         }

-        let mut state_machine = self.state_machine.lock().unwrap();
-        for entry in entries {
-            // Drop local inconsistent logs.
-            if entry.index <= self.get_last_log_index()
-            && entry.term != self.get_term_at_index(entry.index).unwrap() {
-                for i in entry.index..self.log.len() {
-                    state_machine.register_transition_state(
-                        self.log[i].transition.get_id(),
-                        TransitionState::Abandoned(TransitionAbandonedReason::ConflictWithLeader)
-                    );
-                }
-                self.log.truncate(entry.index);
-            }
+        {
+            let mut state_machine = self.state_machine.lock().unwrap();
+            for entry in entries {
+                // Drop local inconsistent logs.
+                if entry.index <= self.get_last_log_index()
+                    && entry.term != self.get_term_at_index(entry.index).unwrap()
+                {
+                    for i in entry.index..self.log.len() {
+                        state_machine.register_transition_state(
+                            self.log[i].transition.get_id(),
+                            TransitionState::Abandoned(
+                                TransitionAbandonedReason::ConflictWithLeader,
+                            ),
+                        );
+                    }
+                    self.log.truncate(entry.index);
+                }

-            // Push received logs.
-            if entry.index == self.log.len() + self.index_offset {
-                self.log.push(entry);
+                // Push received logs.
+                if entry.index == self.log.len() + self.index_offset {
+                    self.log.push(entry);
+                }
             }
         }

Section 7 of the Raft paper describes a much-needed optimization: log compaction. With it, the cluster will be able to snapshot its state from time to time so that replicas in the future don't have to replicate the entire transition log and so that storage space is preserved.

Implementing this in Little Raft according to the paper is a good way to make Little Raft a production-grade library. This is a good feasible challenge for people that want to build important functionality of a real distributed system following a clear specification (the Raft paper section 7, in this case).

In my project, I have a struct that implements both the Cluster and StateMachine traits, and, therefore, also share the same Mutex that's passed to Replica.

However, process_append_entry_request_as_follower is holding on to the state machine lock while attempting to acquire the cluster lock, which results in re-entrancy that causes a deadlock (as reported by no_deadlocks crate):

A reentrance has been attempted, but `std::sync`'s locks are not reentrant. This results in a deadlock. dependence cycle: [Thread(ThreadId(11)), Lock(20)]
Lock taken at:
   0: little_raft::replica::Replica<C,M,T,D>::process_append_entry_request_as_follower
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:709:33
   1: little_raft::replica::Replica<C,M,T,D>::process_message_as_follower
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:766:18
   2: little_raft::replica::Replica<C,M,T,D>::process_message
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:352:32
   3: little_raft::replica::Replica<C,M,T,D>::poll_as_follower
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:332:21
   4: little_raft::replica::Replica<C,M,T,D>::start
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:233:36

Reentrace at:
   0: little_raft::replica::Replica<C,M,T,D>::process_append_entry_request_as_follower
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:735:27
   1: little_raft::replica::Replica<C,M,T,D>::process_message_as_follower
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:766:18
   2: little_raft::replica::Replica<C,M,T,D>::process_message
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:352:32
   3: little_raft::replica::Replica<C,M,T,D>::poll_as_follower
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:332:21
   4: little_raft::replica::Replica<C,M,T,D>::start
             at /Users/penberg/src/database/little-raft/little_raft/src/replica.rs:233:36

Fix the deadlock by moving entry processing to a separate function, which reduces the scope of the state machine lock so that it is no longer held when we attempt to acquire the cluster lock.

Fixes #42.

Raft Leader doesn't have to wait for the heartbeat timer to broadcast a pending transition. Let's broadcast as soon as transitions are queued up.

Closes #24

The only way a panic on line 419 can occur is if all of the following is true:

• the leader gets a response with success: false
• the response was sent due to the leader's term being behind the follower's term
• the leader itself is no longer behind the follower's term

If the message takes too long to deliver (for example while the same leader gets re-elected), the leader theoretically might have enough time to advance ahead of the term specified in the follower's term. In this case Little Raft panics. Let's not panic by checking that mismatch_index is set to Some(...), and if not, ignore the follower's response.

Closes #22

thread 'tokio-runtime-worker' panicked at 'called Option::unwrap() on a None value', /Users/penberg/.cargo/registry/src/github.com-1ecc6299db9ec823/little_raft-0.1.4/src/replica.rs:416:57 note: run with RUST_BACKTRACE=1 environment variable to display a backtrace Error: panic

Snapshotting in Raft is optional. However, Little Raft enforces that all users of the StateMachine trait implement get_snapshot, create_snapshot, and set_snapshot; the implementation can be a no-op if the user doesn't want to use snapshotting, but the code doesn't make that clear.

We should figure out how to move snapshot-related methods into a separate trait that has a default no-op implementation that Little Raft users can use if they choose to avoid shapshotting.

This is section 6 of the Raft paper. We need to stop assuming that the cluster configuration is fixed and add support for nodes joining / leaving the cluster. Implementing this implies adding support for joint consensus.

Pull request #18 fixes an issue with out-of-order or stray AppendEntries rejects, which is only trigger able when Little Raft is wired up with networked servers.

Let's improve the tests to simulate network delay and partitioning to attempt to catch bugs like these.

What happens when a new replica is added to the cluster? In the current design, other replicas won't learn about it unless they are restarted with the new peer_ids. But upon restart, the replicas and their state machines will lose their state unless the user builds some persistence themselves.

To make this simpler for the user, we should add functionality for the replica to preserve some permanent state. This should exposed to the Little Raft user via a trait that they can implement as they wish. The Raft paper has a lot of good info on what state needs to be preserved and how, so a good first step would be implementing that, and then adding functionality to snapshot the state of the state machine.

Tests in this project serve two goals: testing functionality and offering usage examples. There's a lot of meaningful work that can be done by adding good tests to Little Raft.

Specifically, you'll want to test Little Raft functionality when replicas go down and up, when messages get lost on the network, and leaders get reelected. You might find it challenging to simulate nodes going up or down or getting connected and disconnected, but remember that in the tests the developer has control over how messages are passing between nodes -- emulating a disconnected node is as simple as not delivering any messages to it; simulating packet loss is as simple as dropping some packets randomly.

You could also add integration tests where replicas are actual separate processes communicating over the network. The possibilities are endless.