The kivaloo data store
Just over a year ago, I sat down to a late breakfast with Patrick Collison to discuss his latest startup. At some point over the next couple of hours, we started talking about my online backup service, Tarsnap, and I mentioned that I was keeping my eye on some server-side scalability issues. "I'm OK for the next year at the current growth rate, but then I'll need to get a more sophisticated data store in place to handle block metadata; right now I'm using a very simple, obviously correct, but rather slow data structure.""I'm impressed with what the rethinks are doing, but it feels like they're doing too much — my data store needs are very minimal," I continued. "Maybe I should just write my own data store; it can't take more than a few months."
I'm very pleased to finally announce the availability of version 1.0.0 of the kivaloo data store as BSD-licensed open source software.
To be fair, kivaloo has been almost-released for a long time. Five months ago I wrote here that the first release of my data store would "be soon" and asked people to suggest possible names for it (the winner: Tim Fletcher, who suggested "kivalu", pronounced "key value"; I changed the spelling slightly, but the essential idea was his). Shortly after writing that blog post, however, I was distracted by porting FreeBSD to EC2 and then by a critical bug in Tarsnap, so it's only recently that I've had a chance to do the last few bits of work needed before kivaloo could be released.
So what is kivaloo? It is a durable, consistent, high-performance key-value data store built out of a background-garbage-collected log-structured B+Tree. Perhaps it's easier to describe what kivaloo isn't:
- It is not a key-blob store like memcached or a key-object store like Redis; each key has a single value of at most 255 bytes associated with it.
- It does not support queries like SimpleDB does; the basic operations are SET, GET, DELETE, and RANGE (which returns all key-value pairs between two specified keys).
- It does not support transactions like ACID databases do; if you want transactions, you can synthesize them at a higher level (kivaloo provides atomic compare-and-set and compare-and-delete operations, so locking can be performed through it).
- It does not provide fast random updates for large data stores like Cassandra; those are incompatible with a high data store : RAM size ratio, and I wanted efficient storage of cold data.
- It is not merely "eventually" consistent like many nosql data stores; kivaloo does not acknowledge a request until data has been written to disk and fsync has returned.
- It doesn't have any concept of users or authorization like most databases do; if you can connect to a listening socket, you can issue requests. (UNIX sockets and firewalls are your friends!)
In short, kivaloo is designed to be exactly what I need for Tarsnap. This is open source software in the time-honoured tradition of scratching an itch; I hope other people will find kivaloo useful and possibly even contribute back, but even if nobody else ever uses kivaloo, it will make a big difference to the Tarsnap server performance and scalability.
Take a look and let me know what you think.