Monday, July 22, 2013

HAT, not CAP: Introducing Highly Available Transactions

Distributed systems designers face hard trade-offs between factors like latency, availability, and consistency. Perhaps most famously, the CAP Theorem dictates that it is impossible to achieve “consistency” while remaining available in the presence of network and system partitions.1 Further, even without partitions, there is a trade-off between response time and consistency. These fundamental limitations mean distributed databases can’t have it all, and the limitations aren’t simply theoretical: across datacenters, the penalties for strong consistency are on the order of hundreds of milliseconds (compared to single-digit latencies for weak consistency) and, in general, unavailability takes the form of a 404 or Fail Whale on a website. Over twelve years after Eric Brewer first stated the CAP Theorem (and after decades of building distributed database systems), data store designers have taken CAP to heart, some choosing consistency and others choosing availability and low latency.

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.

Read more here

Leave a Reply

All Tech News IN © 2011 & Main Blogger .