# Ruaft: Raft implemented in Rust

Ruaft is a Rust version of [the Raft consensus protocol](https://raft.github.io/).

## Raft

Raft is the algorithm behind the famous key-value store [etcd](https://github.com/etcd-io/etcd). The algorithm helps
replicas of a distributed application to reach consensus on its internal state. Raft maintains an array of entries,
collectively known as the log. Each entry of the log carries one piece of data for the application. Once an entry is
committed to the log, it will never be changed or removed. Entries are appended to the end of the log linearly, which
guarantees that the log never diverges across replicas. The log as a whole, represents the internal state of the
application. Replicas of the same application agree on the log entries, and thus agree on the internal state.

## APIs

Each application replica has a Raft instance that runs side by side with it. To add a log entry to the Raft log, the
application calls `start()` with the data it wants to store (commonly referred to as a "command"). The log entry is not
committed immediately. Instead, when the Raft instance is sure that the log entry is agreed upon and committed, it calls
the application back via an `apply_command` callback, which is supplied by the application.

Internally, Raft talks to other replicas of the same application via an RPC interface. From time to time, Raft saves its
log (and other data) to a permanent storage via a `persister`. The log can grow without bound. To save storage space,
Raft periodically asks the application to take a snapshot of its internal state. Log entries contained in the snapshot
will be discarded.

An application creates a Raft instance with `new()`, with RPC interfaces for communication, a `persister`,
a `apply_command`
callback, and a `request_snapshot` callback. More details of those callbacks can be found in the comment of the modules.

### Raft RPCs

Ruaft has three RPC handlers: `append_entries()`, `request_vote()` and `install_snapshot()`, serving requests from other
Raft instances of the same application. These RPC handlers should be added to the RPC system that the application uses.

### Graceful shutdown

The `kill()` method provides a clean way to gracefully shutdown a Ruaft instance. It notifies all threads and wait for
all tasks to complete. `kill()` then checks if there are any panics or assertion failures during the execution. It
panics the main thread if there is any error. If there is no failure, `kill()` is guaranteed to return, assuming there
is no thread starvation.

## Code Quality

The implementation is thoroughly tested. I copied (and translated) the test sets from an obvious source. To avoid being
indexed by a search engine, I will not name the source. The testing framework from the same source is also translated
from the original Go version. The code can be found at the [`labrpc`](https://github.com/ditsing/labrpc) repo.

## KV Server

To test the snapshot functionality, I wrote a key-value store that supports `get()`, `put()` and `append()`. The
complexity of the key-value store is so high that it has its own set of tests. For Ruaft, integration tests in
`tests/snapshot_tests.rs` are all based on the KV server. The KV server is inspired by the equivalent Go version.

## Daemons

Ruaft uses both threads and async thread pools. There are 4 'daemon threads':

1. Election timer: watches the election timer, starts and cancels elections. Correctly implementing a versioned timer is
   one of the most difficult tasks in Ruaft;
1. Sync log entries: waits for new logs, talks to followers and marks contracts as 'agreed on';
1. Apply command daemon: sends consensus to the application. Communicates with the rest of `Ruaft` via a `Condvar`;
1. Snapshot daemon: requests and processes snapshots from the application. Communicates with the rest of `Ruaft` via
   A `Condvar` and a thread parker. Unlike other daemons, the snapshot daemon runs even if the current instance is a
   follower.

To avoid blocking, daemon threads never sends RPC directly. RPC-sending is offloaded to a dedicated thread pool that
supports `async/.await`. There is a global RPC timeout, so RPCs never block forever. The thread pool also handles
vote-counting in the elections, given the massive amount of waiting involved.

Last but not least, there is the heartbeat daemon. It is so simple that it is just a list of periodical tasks that run
forever in the thread pool.

## Running

It is close to impossible to run Ruaft outside of the testing setup under `tests`. One would have to supply an RPC
environment plus bridges, a `persister`, an `apply_command` callback and a `request_snapshot` callback.

Things would be better after I implement an RPC interface and improve the `persister` trait.

## Next steps

- [x] Split into multiple files
- [x] Add public documentation
- [x] Add a proper RPC interface to all public methods
- [x] Allow storing arbitrary information
- [x] Add more logging
- [ ] Benchmarks
- [ ] Support `Prevote`
- [ ] Run Ruaft on a Raspberry Pi cluster