Transactions [2]: What about NoSQL?

My quick introduction to transactions may seem harsh to people who love NoSQL, because I more or less brush this approach to the side.  What's my problem?

To get the lay of the land straight, here's a quick explanation of what NoSQL is about.  The idea is mostly associated with key-value storage (also called DHTs, because we hash the keys and implement a distributed hash table): systems that offer a way to do put/get operations with keys of your own design, and values that fit your programming model.  We'll talk about transactional key-value stores separately, but the NoSQL community focuses on non-transactional ones.

Given a DHT but no transactions, what do transactions add to the mix?  The ACID properties are atomicity, consistency, isolation and durability.  Well, if we treat each put or get as a single operation, atomicity comes down to the policy for handling conflicting updates on a single key.  Here, it turns out that cloud systems often solve the problem with a finesse: many don't allow updates and operate in an insert-only model, with automatic garbage collection after a specified delay.  Thus, for many DHTs, there can't be conflicting updates at the level of a single put: end of story!

Even when there could be updates, if our key maps to a specific node and that node does operations one by one, concurrent updates would still be done in some sequentialized order. 

Let's jump past consistency and isolation.  What about durability?  Well, most DHTs do worry about failures, typically by replicating each data item on the node to which the data maps, but also onto the next k nodes along the key-value mapping space.  This way, if k or fewer nodes happen to crash, data won't be lost.  But most commonly, the updates are done by routing the request to the first node in the list of k+1, which then forwards it along the side of the DHT structure (normally, a ring).  So if the first node performs operations in some deterministic order and a small amount of care is taken to forward data in a way that preserves order, the replicas will be consistent with the primary node.

In a nutshell, we've already summarized the NoSQL concept.  Now if you know me at all, you'll know that I really worry when someone expresses a "problem" by describing a "solution".  In some sense, this is what happens with NoSQL: given a key-value system that is almost always able to offer ACID guarantees with no extra effort at all, NoSQL systems often stop there and say "look, this is pretty close to transactional, don't fret about it." 

Historically, the NoSQL movement originated when transactional database systems started to hit serious scalability limits (read the wonderful little paper by Jim Gray, Pat Helland, Patrick O'Neil and Dennis Shasha on this if you haven't yet seen it: they discuss "The Dangers of Database Replication, and a Solution").  Eric Brewer put Jim's point into a very pithy form and proposed a principle he calls CAP, claiming that consistency, availability and partition tolerance are deeply at odds, so much so that you can only get 2 out of the 3.  Eric recommended giving up on consistency: just say no to acid!

And this turns out to work, at least sometimes.  The eBay folks, and Werner Vogels at Amazon, came up with BASE: a methodology for coding with a NoSQL DHT.  Basically, go ahead and design a transactional system, just as you were taught to do at Cornell (if you opted for some other school, well, hopefully they did a good job too...).  But now, get rid of the transaction begin and commit.  Go ahead: just do it!   

Well, without transactions, you'll see a mostly ACID execution for individual put or get operations (mostly, not always), and of course multi-operation sequences can overlap, or be disrupted by a crash.  So the next step is to just pause and think hard about the surprises you might encounter.  The whole point of BASE is that for many web applications, such as shopping on Amazon or picking a movie from Netflix, or bidding on eBay auctions, those surprises won't be so hard to anticipate, or to fix.

So, having thought deeply and identified all the possible oddities... just fix your code to not crash when surprises happen -- instead, just do what you can to hide them from the user.  End of story!  Your system will scale, and nobody will be the wiser about any nasty little inconsistencies that might arise.  In some systems, one also adds a background fixer-upper to check for oddities in the database and repair them (you need to come up with a plan for that too). 

Don't get me wrong: BASE works incredibly well for most web systems, and you can scale a NoSQL DHT pretty much without limits.  So if you are able to follow this route, you will get super performance, amazing scalability, and your users will see the magic sub-100ms response times the web uses as its main design point.  Indeed, since a NoSQL system is potentially inconsistent by design, you can toss caching in anywhere you like, for further speedups.  NoSQL storage systems and the BASE methodology were a home run for the web, without any question.

The issue arises if you work on mission-critical applications with strong safety needs, like medical care systems for use in a hospital, or self-driving cars.  Bankers tend to think money is a life-or-death matter, so they might put financial applications on the list.  Sales people get upset if the customer relationship data is messed up.   So when these kinds of critical computing uses are layered over the NoSQL/BASE model, we have an issue: inconsistency might not be so easy to sweep under the rug.

For example:

• Doctor Smith noticed that patient Sally Jones was having a reaction to a medication, and took her off it.  But the BASE/NoSQL system misfiled the update and now the nursing station just gave her another dose.  Oops!
• The self-driving car you are in just registered its plan to turn left up on Main Street.  But the car planning database dropped that update, and the bus on Main Street believes that the intersection will be completely clear.  Nasty fender-bender...
• The smart power grid just configured itself for an unusually low demand period, but that was a mistake; actually the database system was in a forgetful mood, and neglected to log ten thousand kilowatt hours of demand.  Blackout!

The point being this: not every application can manage with weak consistency.  CAP is fine, for web browsing (the proof being that people use it very successfully, Eric Brewer's company Inktomi was an immense success, and CAP seems like a religion in some communities). But CAP isn't a theorem and in fact there are cases where we need more.

What should we do about this?  One option is to mix ACID with BASE:  you get SALT, my colleague Lorenzo Alvisi's  cool new system.  The basic idea is to study the transactions in isolation, offline, and form groupings: if transactions of flavors A, B and C are all in use at the same time, perhaps we need a costly form of transactional concurrency control, but if we are only running class A transactions, we might be able to manage safely using a NoSQL model, and perhaps when B and C run but not A, there is some small trick that suffices to give full ACID properties, etc.  Lorenzo gets remarkably far this way.  I should have come up with this idea myself!

Another option is to build a transactional DHT.  There are several exciting research demonstrations of this concept by now: FaRM from Microsoft (I visited with the FaRM group for a few months in fall of 2016), HERD from CMU, and there are others too.  For example, my colleague Gun Sirer has an amazing multi-dimensional DHT called Hyperdex that scales incredibly well and has full ACID properties.  In fact all of these solutions work well, and if your application matches their guarantees, they can work so well that you are left puzzled by CAP: is it even more false than we thought?  Could it be that we really can have all three properties, and cheaply?  I think that more and more, the answer is yes!

For me, the bottom line is this: NoSQL and BASE aren't a terrible idea, if your application didn't need ACID in any case.  Eliminating unneeded synchronization delays, without breaking correctness, is a very useful form of optimization.  But the whole point is that if you didn't need ACID, then in some sense, you aren't sacrificing anything when you optimize this way. 

On the other hand, if you actually do need strong properties, you would be a dangerous fool to assume that CAP is a theorem and that the right answer is to sweep inconsistency under the rug.  That self-driving car, or the patient in that ICU -- they might notice, and could be harmed.  NoSQL is fine, for those who don't need the full ACID and SQL model.  But if you do need the model, use one of these transactional DHTs.  They really work, and they scale extremely well too.