Flotten

A F# implementation of the algorithm described in In Search of an Understandable Consensus Algorithm. Flotten is swedish for raft. The paper is authored by Diego Ongaro and John Ousterhout from Stanford University. The proof is being used to validate my implementation.

To have a look at the implementation, look at Raft.fs which is the algorithm implementation file. Comments abound; many searchable in the paper to find the reason for a certain piece of code.

Description of the Algorithm (paper abstract)

Raft is a consensus algorithm for managing a replicated log. It produces a result equivalent to Paxos, and it is as efficient as Paxos, but its structure is different from Paxos; this makes Raft more understandable than Paxos and also provides a better foundation for building practical systems. In order to enhance understandability, Raft separates the key elements of consensus, such as leader election and log replication, and it enforces a stronger degree of coherency to reduce the number of states that must be considered. Raft also includes a new mechanism for changing the cluster membership, which uses overlapping majorities to guarantee safety. Results from a user study demonstrate that Raft is easier for students to learn than Paxos.

Current Implementation Status

Very raw. When the TODOs have been scrubbed it can be considered pre-alpha. I also plan to do some work to allow remote communication between actors as to make the whole thing more realistic.

Large TODOs:

The Log
Complete AppendEntries for all states
Complete leader state and all that the leader state means.
Supervisor actor
Application entry point
Reconfiguration
Tests, tests, tests.

Comparison with Jakob's implementation:

Separate TimeoutService (as opposed to timer), making timeouts explicit
and using a logical clock to discard invalid timeout entries.
Erlang implementation stores RPCs in dictionary explicitly,
I do it implicitly in parallel.
I should move my voting out to a common pure function
My vote count is done with a separate yield-harvest actor that acts in a
yield-harves fasion. The yield is the grouping function and the harvest the
collection of yays and nays - only enough to settle the vote.
The state is encoded as a mutually recursive asynchronous function in my F#
code but as an atom in the erlang implementation
The Erlang implementation implements RPC primitives, I haven't handled things
such as message duplication, sequencing (will do both on Actor level) yet.

Since I'm using a logical clock to keep track of what timeout notifications to ignore, it might be a good idea to implement the pid/ActorRef as a core feature of the extended actor library, and then let each receive, fork, join, send and internal event update the clock component and having forks and the creation of new actors create new ids. See the paper on Interval Tree Clocks and my initial hacks at implementing them.

Moving parts:

Each RaftActor, in Raft.fs
A single TimeoutService. Preferrably hosted on the same node as the
RaftActor is.
The voting which is done in parallel with Actors.yieldHarvest.

The MIT License

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.