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.
Bron has been doing email since before it was dead. He moved back from the USA in 2004 to run operations for FastMail, and for his sins writes C for a codebase nearly as old and clunky as Linux - the Cyrus IMAPd server.
Like everyone who knows they can do it better than everyone else, Bron wrote a single file embedded key-value store, and people's email still arrives, so apparently it works.
Bron has found some interesting bugs in the Linux kernel over the years, and even had one patch accepted. Yay.
Geelong is Victoria's second largest city, located on Corio Bay, and within a short drive from popular beach-front communities on the Bellarine Peninsula as well as being the gateway to the famous Great Ocean Road
linux.conf.au is widely regarded by delegates as one of the best community run Linux conferences worldwide and is the largest Linux and Open Source Software conference in the Asia-Pacific.
Our Sponsors help make linux.conf.au become the awesome conference everyone comes back to year after year. Come see who's on board this year, or find out how to get in contact with us