You are here

Home > The Elastic DBMS Blog
Subscribe to RSS RSS

The Elastic DBMS Blog

October 27, 2011

Cap Theorem Part 6: Conclusion

This is the sixth and final part of a multi-part blog post about the CAP Theorem. You can read the first part here. You can download all six parts in one document here.

Conclusion

Curt Monash begins his post on “Transparent relational OLTP scale-out” (http://www.dbms2.com/2011/10/23/transparent-relational-oltp-scale-out/) by saying that

There’s a perception that, if you want (relatively) worry-free database scale-out, you need a non-relational/NoSQL strategy. That perception is false.

As more and more people try NoSQL solutions, we are beginning to see that they are not the universal “cure-all” that they are often made out to be. As we show here in this series of blog posts, the CAP Theorem does not say that in “picking two”, you have to entirely forsake the third.

As Daniel Abadi has pointed out in his PACELC blog post (http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html), a normally running system must make some tradeoffs between latency and consistency and what becomes interesting is how the system reacts to a network partition, does it favor availability or consistency? [...]

Read More

CAP Theorem | Permalink | 0 Comments

October 27, 2011

CAP Theorem Part 5: Implications of the relationship between Consistency, Availability, and Partition Tolerance

This is the fifth of a six part blog post about the CAP Theorem. You can read the first part here. You can download all six parts in one document here.

Implications

We now consider the practical implications of the relationship that was established above.

Brewer’s Conjecture

An immediate implication of the relationship between TC, TA, and TP is an alternate validation of the Brewer Conjecture.

As TC + TA ≥ TP, we can conclude the following.

  • If a service is Strictly Consistent (TC = 0) and Perfectly Available (TA = 0), then it is not partition tolerant (TP = 0). In other words, a Strictly Consistent and Perfectly Available service cannot also be Partition Tolerant (TP > 0).
  • If a service is Partition Tolerant (TP > 0) then either it is not Strictly Consistent (TC > 0) or the service is not Perfectly Available (TP > 0). In other words, a Partition Tolerant service must compromise either Consistency or Availability.

That is Brewer’s Conjecture. [...]

Read More

CAP Theorem | Permalink | 0 Comments

October 27, 2011

CAP Theorem Part 4: The relationship between Consistency, Availability, and Partition Tolerance

This is the fourth of a six part blog post about the CAP Theorem. You can read the first part here. You can download all six parts in one document here.

Relationship between TC, TA, and TP

Assertion

We assert that in a service as described in the previous post,
TC + TA ≥ TP
In other words, a distributed service that guarantees TC Consistency, and guarantees a response in less than TA, cannot tolerate network partitions lasting longer than (TC + TA).

Proof

The proof of the assertion is provided by contradiction. Assume for the purposes of this proof that,

TP > TC + TA

In other words we assume that a distributed service that guarantees results that are TC Consistent, and guarantees a response in less than TA, can tolerate network partitions lasting longer than (TC + TA).

We show that this is impossible.

[...]

Read More

CAP Theorem | Permalink | 0 Comments

October 27, 2011

CAP Theorem Part 3: Definitions and terminology

This is the third of a six part blog post about the CAP Theorem. You can read the first part here. You can download all six parts in one document here.

Definitions

For the purposes of this series of blog posts, we consider a distributed service consisting of multiple nodes, servicing requests from some repository. Client applications may submit requests to any node that is part of the distributed service.

In characterizing a service, we have focused on the attributes Consistency, Availability and Partition Tolerance. Other factors such as the amount of time taken to transmit a message from one node to another, the time taken to process a message, or the time taken waiting for some resource to become available also influence the overall performance of the service. We assume for the sake of simplicity and clarity that messages are delivered instantaneously, and that they can be processed instantaneously. [...]

Read More

CAP Theorem | Permalink | 0 Comments

October 27, 2011

CAP Theorem Part 2: What is the CAP Theorem?

This is the second of a six part blog post about the CAP Theorem. You can read the first part here. You can download all six parts in one document here.

In designing a distributed service, three desirable attributes are Consistency, Availability and Partition Tolerance. In this series of blog posts we explore a framework for characterizing these three in a manner that establishes definite limits and relationships between them, and explore some implications of this characterization.

Background

At PODC 2000, Brewer [1] presented the conjecture that it is impossible to develop a web service that provides all three of the following guarantees:

  • Consistency
  • Availability
  • Partition Tolerance.

In 2002, Nancy Lynch and Seth Gilbert presented a formal proof [2] of this conjecture and established the “CAP Theorem”.

All three of these attributes are highly desirable in distributed service, and it would be ideal if one were to deliver all three guarantees. However, as demonstrated by Lynch and Gilbert, and as we shall further demonstrate here, it is not possible to develop a service that can in fact deliver all three guarantees. [...]

Read More

CAP Theorem | Permalink | 0 Comments

October 27, 2011

An analysis of the CAP Theorem

This is the first of a six part blog post about the CAP Theorem (Brewer’s Conjecture). In this series of posts, we provide a detailed explanation of the CAP Theorem from the perspective of an application developer, and a system architect. It sets forth a framework within which to understand the implications of CAP Theorem, and quantify the implications of various choices on Consistency, Availability and Partition Tolerance.

The first post (this post) provides a brief background, and introduces the CAP Theorem. You can download all six parts in one document here.

Part 1: Background

In having conversations with advisers, investors, prospects and friends about ParElastic and our Elastic Transparent Sharding ArchitectureTM, the conversation very often finds its way to the CAP Theorem.

Some people we speak with are concerned about the future of the relational database itself and cite articles that they have read by well-respected database experts who predict the imminent demise of the relational database. Most database users and ParElastic prospects readily admit their own incredible pain with using databases in the cloud, and some tell us about their nightmares experimenting with NoSQL solutions. [...]

Read More

CAP Theorem | Permalink | 0 Comments

parelastic-video-thumb.jpeg

Watch Video
Learn how to Flex Your Database with ParElastic.

Watch Demo

Download White Paper:

Flexibility: The Future of Database Technology

Download White Paper
download_whitepaper_thumb.png

Take the next step