Compaction

Warning: these are design notes from initial stages of LogCabin and are are probably not relevant any longer.

The Raft log cannot grow without bound. This document discusses the design of various solutions to this problem: compaction.pdf 

Excuse me for linking to a PDF, but I'd rather write it in LaTeX than wiki. Let me know if you want to collaborate on the git repo. Or for small stuff, leave ideas, comments, questions on this page.

Some additional notes from the implementation:

• Implementing snapshotting makes for a fairly awkward patch set. First you have to be able to save them, then you can start to load them, then you have to be able to transfer them (but this won't get invoked yet), then you have to eliminate every place log entries are accessed unsafely, then you can start to discard log entries (and now transferring snapshots gets invoked).
• I think it's necessary to be able to discard newly created snapshots that are already stale, for example if a follower begins a snapshot, receives a better snapshot from a leader, then completes the stale snapshot it had started previously.
• I had originally tried to retain the last entry from the latest snapshot in the log, so there'd always be one entry of overlap between the snapshot and the log. The hope was that this would simplify some code (for example, getting the last log term). However, it's hard to maintain the property that every server has a complete log this way. If it saves the snapshot first, then it doesn't have an overlapping entry, and if it saves the overlapping entry first, then it has a gap before its log that no snapshot fills. So it seems better not to do this: a snapshot goes through entry n; the log starts at entry n + 1 (inclusive).