Range queries in key/value stores, part two

jwatte's picture

In my previous blog entry, I talked about cross-shard transactional integrity for key/value stores, and how SQL databases have solved this problem. I also poked fun at some of the best known key/value stores for not quite solving all of my problems for me, for free. Go read it, it's fun times!

In the post, I made the observation that a key/value store can treat the key/value pair as an atomic unit, much like how a traditional database can treat a disk block as an atomic unit. Thus, assuming you support atomic commit of multiple key/value pairs as part of a single transaction, you can build indices much like you would build them for a regular database, except using key/value blocks rather than disk blocks.

The drawback to that approach, though, is that you start getting contention for the blocks that make up popular indices -- writing to tables with lots of indices is a known bottleneck for relational databases, and would be the same for key/value stores.

An alternative is to define your system to support parallel updates. Riak, and CouchDB, take this in interesting directions. The entity stored at a given key may have multiple values. When a conflict is detected, the code can try to figure out how to resolve it, and if not able to, it can leave both versions in place. This changes how you build your system, and may put new UI requirements on the end user. For example, imagine if you went into "edit my account" and it asked you "which of these two email addresses did you really intend to use?"

I'll write more about this later, but I gotta run now!