NoSQL and eventual consistency - real world examples [closed]

Question

I'm looking for good examples of NoSQL apps that portray how to work with lack of transactionality as we know it in relational databases. I'm mostly interested in write-intensive code, as for mostly read-only code this is a much easier task. I've read a number of things about NoSQL in general, about CAP theorem, eventual consistency etc. However those things tend to concentrate on the database architecture for its own sake and not on the design patterns to use with it. I do understand that it's impossible to achieve full transactionality within a distributed app. This is exactly why I would like to understand where and how requirements should be lowered in order to make the task feasable.

EDIT:

It's not that eventual consistency is my goal on it's own. For the time being I don't really see how to use NoSQL to certain things that are write-intensive. Say: I have a simplistic auction system, where there are offers. In theory the first person to accept an offer wins. In practice I would like at least to guarantee that there is only a single winner and that people get their results in the same request. It's probably not feasable. But how to solve it in practice - maybe some requests could take longer than usual, because something went wrong. Maybe some requests should be automatically refreshed. It's just an example.

Answer 1

Let me explain CAP in purely intuitive terms. First, what C, A and P mean:

• Consistency: From the standpoint of an external observer, each "transaction" either fully completed or is fully rolled back. For example, when making an amazon purchase the purchase confirmation, order status update, inventory reduction etc should all appear 'in sync' regardless of the internal partitioning into sub-systems

• Availablility: 100% of requests are completed successfully.

• Partition Tolerance: Any given request can be completed even if a subset of nodes in the system are unavailable.

What do these imply from a system design standpoint? what is the tension which CAP defines?

To achieve P, we needs replicas. Lots of em! The more replicas we keep, the better the chances are that any piece of data we need will be available even if some nodes are offline. For absolute "P" we should replicate every single data item to every node in the system. (Obviously in real life we compromise on 2, 3, etc)

To achieve A, we need no single point of failure. That means that "primary/secondary" or "master/slave" replication configurations go out the window since the master/primary is a single point of failure. We need to go with multiple master configurations. To achieve absolute "A", any single replica must be able to handle reads and writes independently of the other replicas. (in reality we compromise on async, queue based, quorums, etc)

To achieve C, we need a "single version of truth" in the system. Meaning that if I write to node A and then immediately read back from node B, node B should return the up-to-date value. Obviously this can't happen in a truly distributed multi-master system.

So, what is the solution to your question? Probably to loosen up some of the constraints, and to compromise on the others.

For example, to achieve a "full write consistency" guarantee in a system with n replicas, the # of reads + the # of writes must be greater or equal to n : r + w >= n. This is easy to explain with an example: if I store each item on 3 replicas, then I have a few options to guarantee consistency:

A) I can write the item to all 3 replicas and then read from any one of the 3 and be confident I'm getting the latest version B) I can write item to one of the replicas, and then read all 3 replicas and choose the last of the 3 results C) I can write to 2 out of the 3 replicas, and read from 2 out of the 3 replicas, and I am guaranteed that I'll have the latest version on one of them.

Of course, the rule above assumes that no nodes have gone down in the meantime. To ensure P + C you will need to be even more paranoid...

There are also a near-infinite number of 'implementation' hacks - for example the storage layer might fail the call if it can't write to a minimal quorum, but might continue to propagate the updates to additional nodes even after returning success. Or, it might loosen the semantic guarantees and push the responsibility of merging versioning conflicts up to the business layer (this is what Amazon's Dynamo did).

Different subsets of data can have different guarantees (ie single point of failure might be OK for critical data, or it might be OK to block on your write request until the minimal # of write replicas have successfully written the new version)

There is more to talk about, but let me know if this was helpful and if you have any followup questions, we can continue from there...

[Continued...]

The patterns for solving the 90% case already exist, but each NoSQL solution applies them in different configurations. The patterns are things like partitioning (stable/hash-based or variable/lookup-based), redundancy and replication, in memory-caches, distributed algorithms such as map/reduce.

When you drill down into those patterns, the underlying algorithms are also fairly universal: version vectors, merckle trees, DHTs, gossip protocols, etc.

The same can be said for most SQL solutions: they all implement indexes (which use b-trees under the hood), have relatively smart query optimizers which are based on known CS algorithms, all use in-memory caching to reduce disk IO. The differences are mostly in implementation, management experience, toolset support, etc

unfortunately I can't point to some central repository of wisdom which contains all you will need to know. In general, start with asking yourself what NoSQL characteristics you really need. That will guide you to choosing between a key-value store, a document store or a column store. (those are the 3 main categories of NoSQL offerings). And from there you can start comparing the various implementations.

[Updated again 4/14/2011]

OK here's the part which actually justifies the bounty.. I just found the following 120 page whitepaper on NoSQL systems. This is very close to being the "NoSQL bible" which I told you earlier doesn't exist. Read it and rejoice :-)

NoSQL Databases, Christof Strauch

Answer 2

There are many applications where eventual consistency is fine. Consider Twitter as a rather famous example. There's no reason that your "tweets" have to go out to all of your "followers" instantaneously. If it takes several seconds (or even minutes?) for your "tweet" to be distributed, who would even notice?

If you want non-web examples, any store-and-forward service (like email and USENET) would be require eventual consistency.

Answer 3

It's not impossible to get transactions or consistency in NoSQL. A lot of people define NoSQL in terms of a lack of transactions or as requiring eventual consistency at best, but this isn't accurate. There are transactional nosql products out there - consider tuple spaces, for example - that scale very well even while providing app consistency.