Essential storage tradeoff: Simple Reads vs. Simple Writes

Photo by Robert Scoble

When I studied computer science with a focus on databases, the holy scripture said only to use normalized data. For my exam I had to study 2NF and 3NF. And now it seems this is all wrong for large scale operations. From my education, I still have a strong feeling towards the pureness of normalized databases - and detect this feeling in many developers. In reality denormalized schemas are the way to go.

Why the former rise of normalized schemas for relational databases? Normalized data is pure. There are no repetitions, no duplication and data can easily be added, changed and removed. The database enforces a consistent state. But to read data from several tables you need to join them, which means complex and - often - slow reads. The tradeoff.

The rise of NoSQL storages

Joining doesn't scale to millions of concurrent users, and it's rumored that some companies ban joins completely. NoSQL databases, which include key/value stores and document databases, drop the notion of normalized data. Those with the biggest momentum are Cassandra, Project Voldemort, Tokyo Tyrant, Redis and CouchDB.  They store data or documents in denormalized chunks which leads to easy reads. But if the data needs to be present in several documents, this means complex writes.

Simple Reads vs. Simple Writes

Essentially you exchange simple-writes/complex-reads with complex-writes/simple-reads. In most modern web architectures with many more reads than writes - depending on your business model - it's no wonder people prefer the second tradeoff.

An example

Let's take a look at an - contrived - example. Suppose we want to store a shopping list. Each shopping list can be tagged and also have friends who can see the shopping list. With a normalized database one would perhaps model this problem like this:

Normalized example for databases

Compare the normalized form with a document schema:

Document based example for NoSQL
We added the tags and friends (in human readable form) to the shopping list, and the friends to the user document.

Read and write use cases

Let's examine two use cases:

  1. Adding, removing and changing the name of a friend
  2. Reading the shopping list

With the normalized schema, adding and removing a friend to a shopping list is easy: Just insert a row or remove a row in the Friends table. Changing the name of a friend is also easy, just change it in the User table. Reading the shopping list at least involves a join with Tags and so isn't a one-chunck read access. If we want to display the friends for a shopping list too, there even will be a second join.

With the document schema, adding and removing a friend is more complex. We need to read and write the shopping list document. We also need to read and write the user document. Reading is simple though. Just read the shopping list document, there is all the information to display a shopping list with the tags and the friends. Changing names is most difficult, we would need to change all shopping lists. This is the primary argument for normalized databases. But in reality, how often do users change their name compared to viewing a shopping list? And most of those slow operations can be done in a second, asynchronous step (see picture above).

Be aware of this tradeoff and plan or change your architecture accordingly. But what do you think?

Sharding destroys the goals of your relational database

Sharding does destroy your relational database - which is a good thing. The idea behind sharding is to distribute data to several databases based on certain criterias. This could for example be the primary key. All entities that keys begin with 1 go to one database, with 2 to another and so on (often modulo functions on the key are used, or groups based on business data like customer location, or function). Several reasons exists for sharding, the main two being better performance and lower impact of crashed databases - only persons with a name that starts with S will be affected by a database crash.

Relational databases were the tool of choice for several decades when it comes to data storage. But they do more than store data. Even reading operations can be split into several functions. There are at least three kinds of database read queries:

  • Data graph building queries: With these you get your data out of the database, customers together with adresses etc.
  • Aggregation queries: How many orders have been stored in the August, aggregated by product category
  • Search queries: Give me all customers who live in New York

Sharding now does away with the second and third query and reduces databases to data storage. Because the shards are different databases on different systems you can't aggregate queries (compared to a cluster) without custom code across systems and you cannot search with one query (only several ones - one to each database). Databases have lead to the notion that search and retrieval are linked together and should be dealt together. Most people think as retrieval and search as the same thing. This has blocked development on technologies. Sharding, S3, Dynamo, Memcached have changed this preception recently. I've written about splitting search and retrieval in "The unholy legacy of databases". There I quote Rickard from Qi4j fame:

Entities are really cool. We have decided to split the storage from the indexing/querying, sort of like how the internet works with websites vs Google, which makes it possible to implement really simple storages. Not having to deal with queries makes things a whole lot easier.

and have concluded

Free your mind! Storage and search are two different things, if you split them, you gain flexibility.

People talked about splitting storage and search for some time now. Search engines like Lucene have driven searching out of databases. But mainly the notion of store&search is prevalent. Sharding as a mechanism for more perfomance and lower risk will move into many web companies and reduce databases to storage mechanism and drop the aggreation (data warehouse and reporting) and search parts. Those can be better filled with real data warehouse servers like Mondrian and search services based on Lucene or semantic enginse like Sesame. And storage might move from databases to simple storages like Amazon Elastic Block Storage or JDBM.

Thanks for listening, and think about your databases.