Twoskip - a robust single-file key-value database
Bron Gondwana
https://linux.conf.au/schedule/30190/...
They Cyrus IMAPd server uses key-value stores a lot inside, and it needs absolute robustness and consistent performance more than it needs raw speed. The skiplist implementation sometimes took hours to recover large files as it rebuilt the entire database after a process or server crash.
After evaluating other options, I decided to extend skiplist to provide fast recovery, 64 bit support and extra robustness with checksums throughout. Using only POSIX guarantees, here's a single-file database format that's extremely robust, if not the fastest thing in the world.
This talk explains how the skiplist data structure works, and how twoskip creates a flat file representation of a skiplist with an intertwined single linked list to provide fast recovery of corrupted databases while requiring nothing more than a guarantee of fsync ordering and atomic single block writes.