Eventually consistent

In my first article here on Dagblog, I tried to cover the main ideas behind NoSQL (Not Only SQL) databases. I talked mostly about key-value databases. The NoSQL family is much broader, of course. We also have graph databases such as Neo4j and HyperGraphDB, which specialize in storing hierarchical structures, and document databases such as the fairly well-known CouchDB or MongoDB. Each kind of NoSQL database excels in a different area where conventional relational databases fall short for us, whether it’s data volume, speed, cost or efficiency.

All, or more accurately most, of these NoSQL databases (there may be exceptions) are characterized by what’s called eventual consistency. For most of us, data consistency is a sacred cow. It’s hardly surprising. We’ve spent twenty years writing applications on top of relational databases, in a world defined by ACID, maintaining consistency with referential integrity and wrapping it in transactions. We can barely imagine our data being inconsistent, or more accurately our view of it at a particular moment being inconsistent.

Eventual consistency

To get to what eventual consistency means, we need to start with the big picture. As internet applications grew enormously, so did the amount of data they use or need to process. You don’t have to think of giants like Facebook, Twitter and other social networks. Think of an ordinary service that aggregates articles, or a tool that analyzes data such as logs from an application we run. Put simply, trouble with relational databases starts when we pour in heaps of data we need to work with, especially when we write queries to get different views of it.

With a lot of data, we have to figure out how to scale reads and writes. The classic way to scale writes is sharding, physically separating data by some key. Unlike reads, writes always block one another at some level. One simple approach is to put data for everyone whose name begins with A in a different table from data for people whose names begin with B. Or split it into separate databases instead of tables. A technique called consistent hashing distributes the data by key. For reads, there’s a technique called replica reads. The database servers run in a master/slave configuration, and we route some reads (though not necessarily all) to the replica servers.

The CAP theorem — Pick two

The CAP theorem describes three basic properties of systems, availability, data consistency and partitioning (physical separation). According to the theorem, a distributed system can achieve only two of them. We’ve said that we need sharding to handle a large amount of data, so we have partitioning, with data on physically separate servers. That leaves us to choose between data consistency and availability.

If data consistency is our absolute priority at the expense of availability, the whole system can be unavailable at times. That’s the price we pay to avoid reading stale data, for example. If system availability is the absolute priority at the expense of data consistency, we can sometimes read stale data. This is called eventual consistency. NoSQL databases are characterized by this kind of consistency, in the sense that the data becomes consistent over time or in the end, along with a high level of availability.

It’s called eventual consistency because the client reads consistent data only under certain conditions the system can be in. Even eventual consistency has several levels, such as read-your-own-writes. As an example, one of the internet’s basic systems that works this way is DNS, which propagates changes through caches with a defined expiration time.

For your application, it means the data you’re working with may be out of date. Some tasks can tolerate this kind of consistency, while others can’t. The creators of CouchDB, for example, wouldn’t be afraid to use it to build a banking system. You just need a different recipe.

Sources

• Eventual consistency (well explained in the CouchDB book)
• CAP theorem (an explanation)
• Eventually Consistent (the original by Werner Vogels,
  CTO, Amazon.com)
• More on eventual consistency