Innovations in client communication and log compaction in Copycat
Jordan Halterman (kuujo)
As some of you know, I've been around the Raft community and working on Copycat (http://github.com/atomix/copycat) for a few years now and Atomix (http://github.com/atomix/atomix) for the last year or so (Copycat is a Raft implementation and Atomix is a distributed coordination framework built on top of it). Over the years, Copycat has evolved significantly into a fully featured Raft implementation that covers all aspects of the algorithm. In fact, in many areas it builds upon it. The most notable areas in which Copycat extends the Raft algorithm is in client communication and log compaction. Since Copycat is now prepared to be released, I want to share the extensive documentation on the algorithms behind Copycat with the Raft community.
Copycat builds upon sessions in Raft to allow state machines to publish sequentially consistent and/or linearizable events to clients in a fault-tolerant manner. This allows event-driven state machines to be implemented without long polling. This is described in the session events section of the documentation:
http://atomix.io/copycat/user-manual/internals#session-events
Copycat also implements a custom incremental log compaction algorithm that facilitates both log cleaning and snapshotting to provide greater flexibility to state machines. Parts of the algorithm are similar to log cleaning as described in the Raft dissertation, except Copycat retains the positions of entries in the log even after compaction - rather than copying live entries to the head of the log - to reduce the complexity of managing the compacted log. This algorithm allows Copycat to reduce the number of entries that need to be replicated to slower followers while retaining the ability to snapshot part or all of a state machine's state. The algorithm is described in the log compaction section of the documentation:
http://atomix.io/copycat/user-manual/internals#log-compaction
Atomix uses both algorithms for a variety of state machines. Session events are used to facilitate locks, membership groups, and leader elections, incremental compaction is used for message oriented state machines, and snapshots are required where incremental compaction does not suffice, such as is the case with a counting state machine. This results in significant flexibility for state machines in Copycat and Atomix.
Comments, questions, and constructive criticism welcome!
Jordan Halterman
Jordan Halterman (kuujo)
Session events:
http://atomix.io/copycat/user-manual/internals/#session-events
Log compaction:
http://atomix.io/copycat/user-manual/internals/#log-compaction
Jordan Halterman
jordan.h...@gmail.com
--
You received this message because you are subscribed to a topic in the Google Groups "raft-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/raft-dev/Ve3b7jEX108/unsubscribe.
To unsubscribe from this group and all its topics, send an email to raft-dev+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.