NoSQL Benchmarks NoSQL use cases NoSQL Videos NoSQL Hybrid Solutions NoSQL Presentations Big Data Hadoop MapReduce Pig Hive Flume Oozie Sqoop HDFS ZooKeeper Cascading Cascalog BigTable Cassandra HBase Hypertable Couchbase CouchDB MongoDB OrientDB RavenDB Jackrabbit Terrastore Amazon DynamoDB Redis Riak Project Voldemort Tokyo Cabinet Kyoto Cabinet memcached Amazon SimpleDB Datomic MemcacheDB M/DB GT.M Amazon Dynamo Dynomite Mnesia Yahoo! PNUTS/Sherpa Neo4j InfoGrid Sones GraphDB InfiniteGraph AllegroGraph MarkLogic Clustrix CouchDB Case Studies MongoDB Case Studies NoSQL at Adobe NoSQL at Facebook NoSQL at Twitter



cap: All content tagged as cap in NoSQL databases and polyglot persistence

Beating the CAP Theorem Checklist

Your ( ) tweet ( ) blog post ( ) marketing material ( ) online comment advocates a way to beat the CAP theorem. Your idea will not work. Here is why it won’t work:

Andrei Savu

Original title and link: Beating the CAP Theorem Checklist (NoSQL database©myNoSQL)


Don't Settle for Eventual Consistency - Causal consistency

An ACM article on consistency and replication:

Causal consistency ensures that operations appear in the order the user intuitively expects. More precisely, it enforces a partial order over operations that agrees with the notion of potential causality. If operation A happens before operation B, then any data center that sees operation B must see operation A first.

Three rules define potential causality:

  1. Thread of execution. If a and b are two operations in a single thread of execution, then a -> b if operation a happens before operation b.

  2. Reads-from. If a is a write operation and b is a read operation that returns the value written by a, then a -> b.

  3. Transitivity. For operations a, b, and c, if a -> b and b -> c, then a -> c. Thus, the causal relationship between operations is the transitive closure of the first two rules.

Causal consistency ensures that operations appear in an order that agrees with these rules. This makes users happy because their operations are applied everywhere in the order they intended. It makes programmers happy because they no longer have to reason about out-of-order operations.

I’ve read this article at a small hour and I’m still digesting it, but for now my impression is that it describes a single-client ordering of operations:

  1. Is it always necessary to have serializability of single thread operations? I think this is useful only if there is a non-empty intersection of the data sets affected
  2. For “Read-from” rule there must be more assumptions (e.g. both operations are originating from the same client)
  3. What’s the connection between these rules (dictating single client ordering of operations) and replication?

Original title and link: Don’t Settle for Eventual Consistency - Causal consistency (NoSQL database©myNoSQL)


Eventual consistency models: release consistency

William Sharp:

In order to write data, a node must acquire a memory object. When the write is complete, the node releases the memory object.

The model is implemented by distributing all the writes across the system before another node can acquire the memory object.

Sounds like distributed locks. In a distributed system.

Original title and link: Eventual consistency models: release consistency (NoSQL database©myNoSQL)


NoSQL meets Bitcoin and brings down two exchanges

Most of Emin Gün Sirer’s posts end up linked here, as I usually enjoy the way he combines a real-life story with something technical, all that ending with a pitch for HyperDex.

The problem here stemmed from the broken-by-design interface and semantics offered by MongoDB. And the situation would not have been any different if we had used Cassandra or Riak. All of these first-generation NoSQL datastores were early because they are easy to build. When the datastore does not provide any tangible guarantees besides “best effort,” building it is simple. Any masters student in a top school can build an eventually consistent datastore over a weekend, and students in our courses at Cornell routinely do. What they don’t do is go from door to door in the valley, peddling the resulting code as if it could or should be deployed.

Unfortunately in this case, the jump from the real problem, which was caused only by the pure incompetence, to declaring “first-generation NoSQL databases” as being bad and pitching HyperDex’s features is both too quick and incorrect1.

  1. 1) ACID guarantees wouldn’t have solved the issue; 2) All 3 NoSQL databases mentioned, actually offer a solution for this particular scenario. 

Original title and link: NoSQL meets Bitcoin and brings down two exchanges (NoSQL database©myNoSQL)


Scalable Atomic Visibility with RAMP Transactions

We’ve developed three new algorithms—called Read Atomic Multi-Partition (RAMP) Transactions—for ensuring atomic visibility in partitioned (sharded) databases: either all of a transaction’s updates are observed, or none are.

Still digesting Peter Bailis’s post and the accompanying Scalable Atomic Visibility with RAMP Transactions paper.

Original title and link: Scalable Atomic Visibility with RAMP Transactions (NoSQL database©myNoSQL)


The dual sense of consistency

Michael Nygard in an article that looks at the 2, completely unrelated, definitions of consistency; the one in ACID and the one from CAP:

So it turns out that “consistency (predicate)” and “consistency (history)” are two distinct ideas that happen to share a word. It is always an error to substitute the distributed systems definition of “consistency” for the C in ACID.

Original title and link: The dual sense of consistency (NoSQL database©myNoSQL)


Watching a presentation on Byzantine fault tolerance is similar to watching a foreign film

James Mickens in “The saddest moment“:

In conclusion, I think that humanity should stop publishing papers about Byzantine fault tolerance. I do not blame my fellow researchers for trying to publish in this area, in the same limited sense that I do not blame crackheads for wanting to acquire and then consume cocaine. The desire to make systems more reliable is a powerful one; unfortunately, this addiction, if left unchecked, will inescapably lead to madness and/or tech reports that contain 167 pages of diagrams and proofs. Even if we break the will of the machines with formalism and cryptography, we will never be able to put Ted inside of an encrypted, nested log, and while the datacenter burns and we frantically call Ted’s pager, we will realize that Ted has already left for the cafeteria.

One of the shortest and delightful articles about the complexity of distributed systems.

Aphyr’s Partitions for Everyone presentation

I’ve been reading Kyle Kingsbury’s (@aphyr) Jepsen series since the first post was published; actually I’ve saved them all and I’m re-reading some of them again and again.

Now I’ve had a chance to see live Kyle Kingsbury’s “Partitions for Everyone!” presentation at Cassandra SF meetup. The majority of good presentations can be characterized as highly informative or very entertaining. But “Partitions for Everyone!” is one of those rare ones that is both entertaining and informative.

InfoQ has the video of Kyle Kingsbury’s presentation at strangeloop 2013. Take the 45 minutes to watch it!

Original title and link: Aphyr’s Partitions for Everyone presentation (NoSQL database©myNoSQL)

Papers on transactions and consistency from SOSP’13

Thanks to Murat Demirbas, I got a link to the SOSP‘13 papers. Maybe is because of my myopic interest, but it seems like quite a few papers this year were focus on the topic of transactions and consistency:

  • Speedy Transactions in Multicore In-Memory Databases by Stephen Tu, Wenting Zheng (MIT), Eddie Kohler (Harvard), Barbara Liskov, Samuel Madden (MIT)
  • From ARIES to MARS: Transaction Support for Next-Generation, Solid-State Drives by Joel Coburn, Trevor Bunker, Meir Schwarz, Rajesh K. Gupta, Steven Swanson (University of California, San Diego)
  • Transaction Chains: Achieving Serializability with Low Latency in Geo-Distributed Storage Systems1 by Yang Zhang, Russell Power, Siyuan Zhou, Yair Sovran (NYU), Marcos K. Aguilera (Microsoft Research), Jinyang Li (NYU)
  • Consistency-Based Service Level Agreement for Cloud Storage by Douglas B. Terry, Vijayan Prabhakaran, Ramakrishna Kotla, Mahesh Balakrishnan, Marcos K. Aguilera (Microsoft Research), Hussam Abu-Libdeh (Cornell University)
  • Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask by Tudor David, Rachid Guerraoui, Vasileios Trigonakis (EPFL)

This SOSP‘13 page has download links for all papers.

  1. There’s an updated version of the paper here

Original title and link: Papers on transactions and consistency from SOSP’13 (NoSQL database©myNoSQL)

The demise of eventual consistency?

A well written article by FoundationDB’s founder Dave Rosenthal about eventual consistency:

The concept of eventual consistency comes up frequently in the context of distributed databases. Leading NoSQL databases like Riak, Couchbase, and DynamoDB provide client applications with a guarantee of “eventual consistency”. Others, like MongoDB and Cassandra are eventually consistent in some configurations.

I could ignore some smart word choices and agree that dealing with eventual consistency is not a familiar area to many developers.

What I cannot agree with though, are weak statements like (what does unreliable writes mean?) :

Eventual consistency pushes the pain and confusion of inconsistent reads and unreliable writes onto software developers.

And definitely I cannot agree with unproved statements used solely to prove your point:

A system that keeps some, but not all, of its nodes able to read and write during a partition is not available in the CAP sense but is still available in the sense that clients can talk to the nodes that are still connected. In this way fault-tolerant databases with no single point of failure can be built without resorting to eventual consistency.

By changing the definitions, you are not proving a theorem is incorrect. Nor do you prove a different theorem.

Original title and link: The demise of eventual consistency? (NoSQL database©myNoSQL)


Non-blocking transactional atomicity

Peter Bailis:

tl;dr: You can perform non-blocking multi-object atomic reads and writes across arbitrary data partitions via some simple multi-versioning and by storing metadata regarding related items.

Without the time to go through all the details of the algorithm proposed by Peter Bailis and the various scenarios of a distributed system where the algorithm would have to work, my head was cycling between:

  1. could this actually be expanded to a read/write scenario? at what costs?
  2. isn’t this a form of a (weaker) XA implementation?

Luckly, Peter Bailis is already answering some of these questions in his post1:

If you’re a distributed systems or database weenie like me, you may be curious how NBTA related to well-known problems like two-phase commit.

In case you are familiar with XA, you could start reading the post with the “So what just happened?” section and then dive into the details of the algorithm and possible extensions.

  1. Thanks Peter for stopping my head spin! 

Original title and link: Non-blocking transactional atomicity (NoSQL database©myNoSQL)


WAN vs. Datacenter Link Reliability

Colin Scott extracted some data about WAN vs datacenter networks reliability:

According to a study by Turner et al. [1], wide area network links have an average of 1.2 to 2.7 days of downtime per year. […] The results are interesting: out of all links types, the average downtime was 0.3 days. […] Intuitively this makes sense. WAN links are much more prone to drunken hunters, bulldozers, wild dogs, ships dropping anchor and the like than links within a secure datacenter.

I’ve been able to find the two papers online:

  1. California Fault Lines: Understanding the Causes and Impact of Network Failures - Daniel Turner, Kirill Levchenko, Alex C. Snoeren, Stefan Savage
  2. Understanding Network Failures in Data Centers: Measurement, Analysis, and Implications - Phillipa Gill, Navendu Jain, Nachiappan Nagappan

Original title and link: WAN vs. Datacenter Link Reliability (NoSQL database©myNoSQL)