Daniel Lemire's blog

, 3 min read

Not even eventually consistent

Many databases engines ensure consistency: at any given time, the database state is logically consistent. For example, even if you receive purchase requests by the thousands, you will always have an accurate count of how many products you have sold, and how many remain in stock. Accountants are especially concerned with consistency: they have invented techniques such as the double-entry systems to favor consistency. Inconsistencies cause problems:

  • The user bought a product, a purchase record has been added, but the user account has not yet been charged. This could allow a user to buy more than he can afford.
  • All items in stock have been sold, but a customer is being told that a few items remain in stock. Thus, a vendor could make sales it cannot fulfill.

Yet, in practice, requiring consistency means that your system will become unavailable from time to time. Thus, many NoSQL databases have adopted an eventual consistency approach. That is, while at any point in time the system might be logically inconsistent, it will eventually recover:

  • The user account will be charged prior to the delivery of the product.
  • A customer who ordered a product that is no longer in stock will be told prior to finishing his order.

Even though it give headaches to the developers, eventual consistency is good enough. In any case, robust systems have to deal with exceptions. Even if your systems tell you that there enough items on stock, it could be that one item was damaged in the warehouse, or that another vendor is willing to quickly provide you with missing items. That is, at best, the data in your database is a logically consistent abstraction. But all non-trivial abstractions, to some degree, are leaky. And that is why we pay accountants: they chase down the leaks.

Maybe we should keep in mind that the largest, most powerful, information system ever designed is logically inconsistent: the Web is full of dangling and misdirected hyperlinks. And it would be extremely hard to debug the Web. Thankfully, we do not need to. My own Web site is probably filled with mistakes. I am sure that I link to pages that no longer exist. Still, it works. The cost of maintaining the integrity would be too high. The errors are acceptable.

As an analogy, security experts rarely try to fully secure systems. Instead, they identify components that must be secured, and they determine the risk tolerance. Complete security is simply too expensive in practice, unless you are willing to live in an isolated bunker.

Thus, maybe the solution will be to accept that information systems that are not even eventually consistent. If I run a business, all that matters to me is that my customers are happy, and I am making a healthy profit. Everything else is secondary. I might be willing to tolerate that some customers are never charged for an item they receive. I might be willing to slightly overstock on some items.

Sure, some might describe a not even eventually consistent system as an abomination, something impossible to program for… but the Web would have been described this way in the 1980s. The key is that the Web is not inconsistent in any random way: it has its own viable logic.

Further reading: The CALM Conjecture: Reasoning about Consistency