Wiki

Clone wiki

Ottoman / Home

Ottoman

version 0.2 — 1 October 2009

Ottoman is a lightweight, reliable key-value store with multi-version concurrency control.

ottoman.jpg

A key-value store is a persistent on-disk dictionary that maps arbitrary keys (usually short text strings) to arbitrary values (binary data of any length). There's already a large and venerable family of libraries that do this, often referred to by the name "db". Notable members include dbm, Berkeley DB, cdb and Tokyo Cabinet. What makes Ottoman different?

  1. It tries to provide extremely reliable storage, immune to file corruption caused by operating system crashes or power failure while writing.
  2. It stores past versions of the database, as a useful side-effect of the way it works. Applications can use this to provide features like snapshots, timelines or persistent undo. (You can prune old versions, for space or privacy reasons, by writing a fresh copy of the file.)
  3. It has very low memory overhead. The file and its contents are memory-mapped, so even large values can be accessed without having to copy them into the heap. (Opening a database only mallocs a few hundred bytes!)
  4. It allows concurrent read/write access by multiple processes. Optimistic concurrency — as used by version-control systems like Subversion — keeps file locking to a minimum: readers are never blocked at all, and writers are only blocked briefly (clients can't lock the database for arbitrary periods, only for as long as it takes the accumulated changes to be written to disk.)

Why is it named after a footstool? First, as an homage to CouchDB. Secondly, it turns out ottomans can be used for storage. Third, because I have a mild fascination with Asian and Islamic history.

API Concepts

Ottoman's C++ API is based on an abstract Dictionary base class.

Keys and values are represented by a trivial data structure called a Blob, which is just a pointer with a byte count. This means you can store arbitrary binary data in keys or values, not just strings. Keys can be up to 65534 bytes long, and values up to gigabytes, although the entire file is limited to 4GB.

The Ottoman class represents the entire file. It contains a time-ordered series of immutable Dictionary objects, one for each available version, plus a special currentVersion that represents the current changes you're making. The currentVersion dictionary is mutable: it starts out looking identical to the lastVersion, but you can freely add/modify/remove values using the MutableDictionary API. These changes are kept in memory. (You can also easily revert changes by getting the old values from the lastVersion.) When you explicitly call Ottoman::save it locks the file, appends all the changes, unlocks it, and discards the in-memory change data since it's now in the file. From your perspective all that happens is that a new immutable lastVersion object appears, as a snapshot of the changes you made. You can continue to make new changes to the currentVersion.

If there are multiple writers, then someone else can save changes to the file at any time. You don't need to worry about this till you save, although you can check for changes at any time by calling Ottoman::sync. But when you call save, it might return false to indicate that there are one or more new versions in the way. In that case you need to call sync, compare your current changes with the newly-added version(s), resolve any conflicts, and call save again. (If this sounds like working with Subversion or Git or Mercurial, you're right.)

There is also an Objective-C binding that's, naturally, based on Cocoa's NSDictionary and NSData; but the higher-level concepts are the same.

Implementation & License

Ottoman is implemented in C++. I've tried to keep the code straightforward: it makes only minimal use of templates, and avoids fancy C++ libraries like the STL. (There is also an Objective-C wrapper for Cocoa programmers.)

Ottoman is made available under a liberal BSD license. Please feel free to use it in commercial or open-source software, just give credit.

Current Status

Currently (as of 3 October 2009) Ottoman runs only on Mac OS X. Thanks to Josh Myer it now builds on Linux, but the unit tests don't pass yet. Windows compatibility might be a little harder, not so much for API reasons but due to differences in the semantics of locking and deleting files.

Ottoman is NOT yet ready for general use. It should be considered pre-alpha, experimental. It has some unit and integration tests, but has not yet been used in any real-life apps. It's very likely to contain bugs. It's also still under development, new features will be added, and I'm not yet ready to lock down the file format.

By all means try it out, but don't ship anything that uses it, or put your important data into it!

[The handsome file storage ottoman featured in the logo is available from Ballard Designs.]

Updated