Introduction

A few months ago, I was starting to write code for my new startup, Postabon, which helps people find and share local discounts. One of the most important decisions I had to make was deciding what technology I should use for persisting data. I'd traditionally been a PostgreSQL guy for historical reasons (several of the past products I'd worked on had decided to use Postgres back when MySQL was missing a lot of really important features). I was willing to consider MySQL since all the concerns I had years ago seemed to be addressed - although I was a little scared by the recent Oracle/Sun acquisition. I'd also been hearing a lot about a 'NoSQL' movement ...

NoSQL

There's been a lot of talk these days about non-relational databases. The moniker 'NoSQL' explains what this trend is not - but doesn't do a good job explaining what it is. There is a reason for that: NoSQL encompasses many vastly different technologies (each of which is arguably as distinct from each other as from traditional relational databases) such key-value stores, document stores, graph databases, and so on.

A lot of big companies that operate at the sort of scale most of us only dream about had built their internal infrastructure on (often custom) key-value stores - which is what piqued my interest about the topic in the first place. When Amazon, Facebook, Digg, LinkedIn, and many other big names all start relying on similar technologies, it's a good idea to ask 'Why?' (yes, their datastores aren't exactly or exclusively Key-Value stores - but it's one of the most salient common threads).

Key Value Store

The core feature a key-value store should support must support is associating one object with another (where these objects can be as simple as 'binary blob' that the database has no semantic understanding of). This provides a persistent Associative Array (like the hashtables or associative lists we all know and love). Many key-value stores also provide some way to order/sort the keys they are storing. Obviously, this is all much simpler and lower level than a full relational database (particularly when used with an ORM or DSL).

By giving a programmer more direct control, and providing less safety, key-value stores can often provide better performance. They also allow for easier and automatic horizontal scalaiblity, since it's much simpler to partition your data across multiple servers when your database never has to do JOINs. On the down side, KV-stores almost all of safety guarantees that a good relational database can provide - foreign key and unique key constraints are difficult to enforce - and they encourage data denormilization (which can lead to inconsistency/corruption if you aren't careful). KV-stores are also often slower to develop with (the programmer has to manually decide which indexes to use, keep his denormalized data consistent, write his own 'joins', etc).

Language Wars

If you follow the programming language wars, this might all sound mighty familiar to you. In his essay Beating the Averages, Paul Graham argued that under a wide range of circumstances companies should use 'high level' programming languages that allow developers to create better software more rapidly. High Level Languages are often safer (e.g., no pointers),  take care of a lot of details for you (e.g., garbage collection), and are less verbose to allow for more rapid developement. For most common use cases the run-time performance hit of a 'high level' language is more than outweighed by the shortened developement time. That's why you'll almost never see a web startup using C, C++, Assembler, etc.

There's a pretty obvious analogy between high level languages and relational databases  - so the obvious question is that if high level languages are so great, then what's wrong with relational databases? Basically, the problem boils down to fact that the performance profile for most web applications is that they'll spend roughly 20% of their time processing - but 80% of their time waiting on I/O (database, disk, etc). The reason for this is that modern processors are unbelievably fast. A 3GHz CPU can add two numbers together in less time than it takes for a photon to travel from your monitor to your eye (speed of light / 3GHz ~ 10cm). But your disk is really slow - your hard disk seek time is probably on the order of 8 milliseconds - which means it takes over 20 Million CPU Cycles for your disk to get a random piece of data! Even your fancy SSD's seek time is probably around half a million CPU cycles.

Because of the huge disparity in CPU and disk speed, many applications are disk or I/O bound. If rewriting their application in C makes your code run twice as fast, it may only buy you an absolute performance boost of 10%. On the other hand, if you could make your database go twice as fast, it might buy you a net 30% performance boost - which is huge (and still far easier to do than rewriting your app in C).

Benchmarks

As a simple example of the sort of performance gains you might see from a key value store, I designed a trivial problem that's fairly representive of the sort of problem my  webapps deal with. I then wrote two solutions to it - one based on MySQL and the other on BerkeleyDB (a relatively simple key-value store from Oracle).

This benchmark comes with the usual caveats - the problem may not be representative of what you work with, both my solutions are grossly sub-optimal, my hardware or software (my Macbook, running Debian in VMWare, Common Lisp (SBCL) as my programming language, Elepahnt and CL-SQL as my persistence libraries, unoptimized databases, etc) may not be representative of yours. All the tests were run with a cold cache - which is probably not very realistic.

The problem I decided to tackle deals with a simple class with 3 notable instance variables:

1. A unique identifier (an integer, hereafter referred to as the UID)
2. A 'score' which can go up or down (an integer)
3. A 'category' which is stored as a string

Based on this class, I envisioned 5 simple tests I could perform to test out the two databases:

1. Populate the database with 100,000 randomly created instances
2. Randomly increment or decrement the 'score' of each instance 20 times
3. Get the UIDs of the items with the 10, 100, and 1000 highest scores
4. Get the UIDs of the items with the 10, 100, and 1000 highest scores in a given category
5. Delete all 100,000 instances from the database.

You can see the full code of my two solutions below: MySQL Solution and BerkeleyDB Solution

The benchmark results speak for themselves:

BerkelyDB was about 2x-3x faster than MySQL. As expected, the code for the key value store was considerably more complex. For example compare the code to fetch the the objects with 10, 100, and 1000 the highest scores:

Conclusion

I'm not here to make a hard sell of key value stores. I just wanted to let people know there's a new game in town - and if your application is I/O bound, you might want to write your own small benchmark to see if the benefit is worth the cost. Especially on the next project you start from scratch.