Repository navigation
Recovery roadmap #236
Description
Activity
Here is my first draft of this roadmap. Comments welcome.
SplinterDB Checkpoint and Recovery Plan
The high-level design of data recovery is based upon the classical checkpoint
with logical logging framework.Incoming write operations are logged logically. In order to reclaim space from
the logs, periodically durable snapshots (called checkpoints) are taken, which
allows for any prior logs to be reclaimed. It is convenient in SplinterDB to
associate logs with memtables, so snapshots will be performed at the time of
memtable rotation, and then upon completion (including sync), any logs
associated with older memtables can be reclaimed.The proposed method to implement snapshots is to make the trunk copy-on-write.
Then a snapshot simply consists of a prior version of the data structure, and
the implementation will consist of ensuring that that version is durable and
preventing it from being garbage-collected.- Copy on Write Trunk
a. Remove sibling pointers in trunk
- Remove from trunk_hdr
- Add page_handle *trunk_get_node_at_height_with_key(trunk_handle *spl, uint16 height, const char *key)
- Modify splinter_compact_bundle to use this function
- Modify splinter_build_filters to use this function
b. Trunk Modification Lock
- Add the mutex, this may end up being the incorporation lock (memtable lookup lock).
- Modify memtable_incorporate to serialize on the TML
- Modify split_index to serialize on the TML
- Modify split_leaf to serialize on the TML
- Modify compact_bundle to serialize on the TML
- Modify build_filters to serialize on the TML
c. Copy on Write Itself
- Add trunk_change_root(...)
- Coordinate point/range queries with trunk CoWs. This may be straightforward if the the TML ends up being the incorporation lock.
- Modify memtable_incorporate to CoW
- Move all flushing to memtable_incorporate: Add memtable, apply all flushes, then CoW in new root. Note this also moves all splitting to memtable_incorporate. Should probably rename to memtable_incorporate_and_flush.
- Modify compact_bundle to CoW
- Modify build_filters to Cow - Garbage Collection for CoW
a. Modify trunk to use a single mini_allocator batch
b. Use reference counting by distinct ancestors
c. Add trunk_dec_ref(...) function which decrements the ref count of the given page, and if it becomes 0, garbage collect its descendents.
b. Modify trunk_change_root to use trunk_dec_ref on the old root - Durable Snapshots Based on CoW
a. Ensure cache_flush (rename to sync?) is thread-safe
b. Add trunk_snapshot(...): increment root ref count and sync cache
c. How to store snapshots? - Log Reclamation
a. Have separate logs for each memtable (?)
b. Have some durable system for storing the logs
c. Reclaim logs on snapshot completion - Recovery
a. Read and correctly order entries from the log[s]
b. Replay into the system and generate a durable snapshot of the latest state (?)
- Copy on Write Trunk
There should be a way to recover from a crash, and this should be covered by tests that run in CI.
Write up roadmap for how this would come together.