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

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)


Is Eventual Consistency Useful?

As a continuation to The NoSQL Partition Tolerance Myth, Jeff Darcy:

Every once in a while, somebody comes up with the “new” idea that eventually consistent systems (or AP in CAP terminology) are useless. Of course, it’s not really new at all; the SQL RDBMS neanderthals have been making this claim-without-proof ever since NoSQL databases brought other models back into the spotlight. In the usual formulation, banks must have immediate consistency and would never rely on resolving conflicts after the fact … except that they do and have for centuries.

Original title and link: Is Eventual Consistency Useful? (NoSQL database©myNoSQL)


Introducing Highly Available Transactions: The Relationship Between CAP and ACID Transactions

Learning from Peter Bailis:

While the CAP Theorem is fairly well understood, the relationship between CAP and ACID transactions is not. If we consider the current lack of highly available systems providing arbitrary multi-object operations with ACID-like semantics, it appears that CAP and transactions are incompatible. This is partly due to the historical design of distributed database systems, which typically chose consistency over high availability. Standard database techniques like two-phase locking and multi-version concurrency control do not typically perform well in the event of partial failure, and the master-based (i.e., master-per-shard) and overlapping quorum-based techniques often adopted by many distributed database designs are similarly unavailable if users are partitioned from the anointed primary copies.

There’s also a paper (PDF) authored by Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph m. Hellerstein, Ion Stoica. These names should tell you something.

Original title and link: Introducing Highly Available Transactions: The Relationship Between CAP and ACID Transactions (NoSQL database©myNoSQL)


Summary and Links for CAP Articles on IEEE Computer Issue

Daniel Abadi has posted a quick summary of the articles signed by Eric Brewer, Seth Gilbert and Nancy Lynch, Daniel Abadi, Raghu Ramakrishnan, Ken Birman, Daniel Freedman, Qi Huang, and Patrick Dowell for the IEEE Computer issue dedicated to the CAP theorem. Plus links to most of them:

  1. Eric Brewer’s article republished by InfoQ
  2. Seth Gilbert and Nancy A. Lynch: Perspectives on the CAP theorem (PDF)
  3. Daniel Abadi: Consistency Tradeoffs in Modern Distributed Database System Design (PDF)
  4. Ken Birman, Daniel Freedman, Qi Huang, and Patrick Dowell: Overcaming CAP with Consistent Soft-State Replication (PDF)

Original title and link: Summary and Links for CAP Articles on IEEE Computer Issue (NoSQL database©myNoSQL)