Nati Shalom's Blog

NoCAP – Part III – GigaSpaces clustering explained..

In part-I of this post I tried to suggest a scalable architecture that can  deal all three properties of CAP. Part II goes back to the definition of Availability and Partition tolerance and the different views on that regard. In this post I would like to elaborate more specifically on how the suggested architecture from part-I works in the context of all three CAP properties.

Recap from previous posts

According to the CAP theorem, one should choose two out of the three CAP properties: consistency (C), availability (A), and partition tolerance (P). Some suggest to choose AP and compromise on consistency. Others like Stonebreaker suggest CA as a better set of tradeoffs:

There is enough redundancy engineered into today’s WANs that a partition is quite rare. My experience is that local failures and application errors are way more likely. Moreover, the most likely WAN failure is to separate a small portion of the network from the majority. In this case, the majority can continue with straightforward algorithms, and only the small portion must block. Hence, it seems unwise to give up consistency all the time in exchange for availability of a small subset of the nodes in a fairly rare scenario

My suggestion followed a similar line of thought as presented by Dr. Stonebreaker, with the addition that I argued that we don’t necessarily need to give away partition tolerance completely when we choose CA.

I suggested an alternative approach where, instead of looking at each of the CAP properties in absolute terms and selecting only two out of the three, we could use a more relaxed version where we could apply various degrees of all three and compromise on the degree in which we apply each property based on the business requirements of our applications.

We will address the most likelihood scenario in which we expect to experience failure or partition tolerance and compromise in areas which are less likely to happen.

In Part I, I used one of the common GigaSpaces clustering topologies as a reference to that model. In the next section I’ll explain how that specific topology applies to all three CAP properties.

GigaSpaces clustering explained..

The following diagram taken from part-I of this series of posts describes a clustering topology that was designed to deal with scalability, throughput as well as consistency, availability and partition-tolerance.

How it works (Quoting from the original post…)

..we break our data into partitions to handle our write scaling between nodes. To achieve high throughput we use in-memory storage instead of disk. As in-memory devices tend to be significantly faster and concurrent than disk and since network speed is no longer a bottleneck we can achieve high throughput and low latency even when we use synchronous write to the replica.

The only place in which we’ll use asynchronous write is the write to the long-term-storage (disk).  As the user transaction doesn’t access the long-term storage directly through the read or write path, they are not exposed to the potential inconsistency between the memory storage and the long-term storage. The long-term storage can be any of the disk based alternatives starting from a standard SQL databases ending with any of the existing

Now let’s examine how we can apply the various CAP properties into that architecture.

1. Consistency 

• Consistency under concurrent updates. To ensure consistency  in the case of concurrent updates on the same data record each individual record is mapped to a single logical-partition at each given point in time.  To ensure scalability, different records of the same logical table are written to multiple partitions in parallel as described in the diagram above. Each partition support the various locking semantics (pessimistic, optimistic (versioning), dirty-read) etc.. to control the concurrent access of the same record within the context of a single partition.
• Consistency between two or more replicas. To ensure the continuous high availability we keep one or more copies of our data. In asynchronous replication, we may end up with scenarios where read and write operations would hit two different nodes at the same time and end up reading two separate versions of that same data. There are various algorithms that were developed to handle that situation. In our case we chose to avoid getting into that situation in the first place through the use of synchronous backup.  The performance overhead of the synchronous replication is fixed and is not proportional to the size of the cluster (each partition replicates data only to its backup replica). The replication to the database is kept asynchronous to reduce the overhead of writing to disk.
• Transaction consistency. Single operations or groups of operations can be executed under transactions. This ensures the ACID properties. Transactions can be made local to each partition. In this case, they will bound to the scope of a single partition and would be highly optimized in terms of performance. Transaction can also span between nodes (in this case the overhead is obviously going to be higher).
• Ordering – All operations are ordered based on the time they were written. This is specifically relevant to ensure the consistency between the in-memory cluster and the long-term storage which is being updated asynchronously.

2. Availability 

• Primary failure. We always keep one or more replica nodes as a hot backup. The hot backup will take over immediately in case a primary node fails. The hot backup nodes uses synchronous replication to ensure no data loss before fail-over took place.
• Backup failure. When a backup node fails, the primary continues to serve requests and log the operation in a redo-log.  In parallel, a new backup is being provisioned on demand to take over from the failed one. That process involves a provisioning process (in which a new backup is created) and a recovery process (during which the backup gets its state).
• Failure of multiple nodes.  To increase availability, some of the NoSQL variants suggest at least three or more replicas per partition. In this way, we can handle simultaneous failure of multiple nodes. That obviously comes with a huge overhead – for each terabyte of data, we would have two terabytes of redundant information for backup purposes, and - equally important - we would also have the consistent overhead of keeping all of them up to date. An alternative approach is to use on-demand backups. On-demand backups are provisioned automatically as soon as one of the nodes fail. If spare capacity exists within the current pool of machines the backup will be provisioned into an alternate machine within the existing pool – this process can take a few seconds (depending on the amount of data per partition). If no machine is available, it will start a completely new machine.A new backup will be providioned into that new machine. The process of starting a new machine with its backup can take few minutes.  As soon the node starts it will first use a primary election protocol to find the master node within its group and only then it boots up. The startup process include a recovery stage in which the node recovers its state from either the master node or the available replicas. The source node will also store all the updates since the recovery started in a redo log and would replay all updates to fill in the gap since the node started its recovery process.
• Client failure.  Clients use a cluster-aware proxy to communicate with the cluster. The smart proxy ensures that a write or read operation is always routed to one of the available partitions. The routing happens implicitly thus the client is not exposed to a fail-over scenario.
• Discovery protocol. The GigaSpaces cluster discovery mechanism is based on the Jini specification. Services use the discovery protocol to find nodes within the cluster and share cluster state amongst all nodes.

3. Partition Tolerance

• Network partition between primary and backup. When the connection between two nodes fails, the primary node logs all the transactions into a fifo queue known as the redo-log. As soon as the communication gets re-established all the data gets replayed to the backup. If the backup fails completely, the system will start a new instance as described above.
• Network partition with the long term persistency. If the communication with the long-term persistency datastore fails, the replica will log all the operations till the connection gets re-established. The log is also replicated to a backup node to ensure that the data won’t be lost in case the primary partition fails before the data was successfully committed to the long-term storage. 
• Network partition between two or more data center sites. Most people referred to scenarios where two sites can live in two separate locations and continue to work independently in a case of network partition as THE reference scenario for partition tolerance. It is important to note that there are two class of multi-site deployments that are fundamentally different as it relates to the network partition:
  • Disaster recovery site – is often located in close geographical proximity to the primary site and is backed by high  bandwidth and redundant  network. 
  • Geographically distributed sites over internet WAN – in this case we have multiple sites that are spread over the globe. Unlike disaster recovery sites those sites tend to operate under lower SLA’s and significantly higher latency.

The recommended approach for dealing with multisite network partition would be fairly different in each of the categories that are mentioned above:

Disaster recover site. Disaster recovery sites are very much like any node in a local network but often live in different network segments and with higher latency than local networks. Nodes within a cluster can be tagged with a zones tag to mark their data-center affinity. The system can use this information to automatically provision primary and backup nodes between the two sites. It will use the zone tag to ensure that primary and backup are always spread between two data centers.

• Consistency & Availability - The consistency and availability mode would be just the same as LAN based deployment as described above but the performance and throughput per partition would be lower due to the higher latency associated with the synchronous replication.
• Partition tolerance – The system will continue to function even in a case where entire site fails or become disconnected. The system will continue to work through the available site.  The system will also rebalance itself as soon as the communication between both sites gets re-established in order that the load will be evenly distributed between the sites.

Geographically distributed sites over internet WAN. In this scenario, nodes are spread over internet connections where the SLAs are lower and latency is significantly higher. In that case, it would be impractical to treat all of the nodes as a single cluster as in the previous case. It would be more practical to use a federated cluster deployment (a cluster of clusters) where we will use asynchronous replication to synchronize the multiple sites and therefore avoid the extreme latency overhead. In this mode, we can’t achieve all three CAP properties. In most cases it would be more common to choose AP over CA. Having said that even when we choose AP we don’t necessarily need to give away consistency completely. Here is a suggested architecture that can provides reasonable degree of consistency with slight compromise on absolute availability and partition tolerance:

•  
  • Consistency: Each site is the sole owner of its data – i.e. all updates on the data that belong to this site needs to be delegated to this site. In more extreme scenario we can define a master site which will own all the updates to the data by all other satellite sites. In that case we can ensure consistency and read availability over write availability.
  • Partition tolerance: All sites use asynchronous replication to maintain local copies of the entire data set. In a case of a network partition between the sites each site can continue to read/write its own data even when other sites are not available. It can also read other sites data but will not be able to change any data that is owned by other sites. In that context we give away some level of partition tolerance for consistency.
  • Availability: Local failures are dealt with through the same model as described above. Updates on data that belong to other sites will be blocked. In that context we give away some degree of availability for consistency.

Note – Another option to deal with consistency under concurrent updates between two sites can be based on versioning. In that case it is assumed that the latest version wins or the system will delegate the decision for resolution on conflicting updates to the application.  This is a more complex scenario that goes beyond the scope of this post.

Handling Extreme Failure:

Multiple node failures at the same time. In cases where both the primary and backup of a given partition fails at the same time, we will consider this cluster as non functional and block operations to that cluster until the cluster becomes functional again. In that case we will compromise on certain aspects of Availability for the sake of Consistency. If your application can tolerate the potential consistency issues associated with such failure, you could configure the cluster to route all  operations to currently available partitions. In that case we will trade Availability over Consistency – this behavior can be useful in streaming scenarios where the system is used to pass through events.

Note that if we choose to use a proper disaster recovery site setup where we ensure that primaries and their backups never run on the same site the chances for having such a failure is close to zero in the first place and can be considered equal for having the two sites down at the same time.

Recovery from total failure. When the entire system crashes, it will boot itself from the long-term persistent storage or from a snapshot (new). In that case we may lose some of the data that was kept in memory and wasn’t yet delivered to the  long term persistent storage. It is important to note that in a disaster recovery setup that event can happen only when both sites goes down at the same time.  In that case the system would recover itself from the data that was last updated in the long-term storage.

Final words

In many of the recent discussions on the design of large scale systems (a.k.a. Web Scale) it was argued that the right set of tradeoffs for building large scale systems would be to give away Consistency for Availability and Partition tolerance. Those arguments relied on the foundation of the CAP theorem developed in early 2000-2002. One of the core principals behind the CAP theorem is that you must choose two out of the three CAP properties. In many of the transactional systems giving away consistency is either impossible or yields a huge complexity in the design of those systems. In this series of posts, I've tried to suggest a different set of tradeoffs in which we could achieve scalability without compromising on consistency. I also argued that rather than choosing only two out of the three CAP properties we could choose various degrees of all three. The degrees would be determined by the most likely availability and partition tolerance scenarios in our specific application.  The suggested model was based on the experience we had in GigaSpaces over the course of the past years and was successfully deployed in many mission critical systems today in Finance, Telco and ecommerce business. I hope that through the sharing of this experience we could come up with a broader set of patterns on how to build large scale systems that would fit also to mission critical transactional systems.

References

• NoCAP – Part I

• NoCAP – Part II Availability and Partition tolerance

• Elasticity for the Enterprise -- Ensuring Continuous High Availability in a Disaster Failure Scenario

The Tera-Scale Effect -- Part II

GigaSpaces Tera-Scale Computing over Cisco UCS

General Architecture Overview:

GigaSpaces' Tera-Scale Computing architecture follows the exact principles that I outlined  in Part I of this post.

Unlike alternative approaches that are built from a fusion of different products that are pre-packaged and branded together, GigaSpaces was designed with a holistic approach in mind that consists of a single and consistent clustering architecture across the entire stack.

In addition, the entire stack was designed to run completely in-memory and support highly concurrent workloads.

The other interesting benefit that comes with this approach in comparison with the alternatives is the fact that there is no reliance on any other expensive hardware (infiniband, high-end storage…) other than the one that comes out of the box with the UCS machine. The use of a single clustering mechanism saves a lot of redundant synchronization overhead and makes the entire platform more efficient and reliable. The use of a complete in-memory stack yields extreme utilization and low latency.

GigaSpaces-UCS Integration:

The actual integration work with Cisco UCS was based on two main parts:

1. Built-in automation and provisioning to enable zero configuration

One of the unique characteristics of the Cisco UCS machine is that it exposes an API that is backed by the low-level bare metal components. This makes it possible to interact with the lower layers of the hardware and set up a complete network of blades programmatically and without reliance on a hypervisor or an operating system as a middleman.

In addition, the integration with the UCS manager enables managing and allocating a pool of blades dynamically. We can turn machines on and off on demand, and discover new machines as they are plugged into the rack mount, and use their capacity immediately without any human intervention.

A blade doesn’t need to have any GigaSpaces or Java installation to join the pool. The provisioning of the JVM and GigaSpaces is taken care of by a provisioning agent that installs GigaSpaces onto the machine remotely as soon as it is discovered and allocated.

The diagram below shows the various components that comprise this Tera-Scale Computing system.

 

The SLA Driven Container and Data & Messaging services are the services that come with the standard GigaSpaces XAP installation. The GigaSpaces UCS Scaling Adaptor is the service that is responsible all the communication with the physical UCS pool and turning it into a GigaSpaces pool.

You can find more details on how this integration works, including a downloadable version of the scaling and provisioning agent, here.

2. Performance tuning and optimization

The second part of the work is around performance optimization and tuning of GigaSpaces on the UCS platform.

You can find below some of the first benchmark reports we published. The benchmark was specifically geared for real-time analytics applications. In the benchmark we were able to tune the system to reach to roughly 300GB per single node with a record throughput of 7.5M reads/sec in an embedded (scale-up) scenario and 300k ops/sec in a remote (scale-out) scenario.

The table below shows the history of the performance optimization process that we carried out throughout the various stages of tuning. It also includes comparison with other similar benchmarks that were done with older versions of UCS and with other platforms.

What we could see is that we were able to continuously improve the performance through optimization of the GigaSpaces platform as well as to the hardware itself.

We are working these days on another set of optimizations that are targeted for latency-sensitive applications.

With this effort we could save the majority of the performance tuning cycles and come up with pre-defined configuration profiles that are backed into our platform and the hardware and get closer to our zero configuration goal.

How does GigaSpaces Tera-Scale Plug into Existing Applications?

There are basically two modes of operation in which existing applications can plug into this solution.

1. Virtual Appliance mode –- In the appliance mode, GigaSpaces and the UCS machine are used as a service that exposes any of the APIs that are currently supported (SQL, Memcached, JMS, MapReduce...). The application remains unchanged and sees the joint solution as a better implementation of any of those services.

The interesting aspect of this mode is that even though the services that are exposed are used as a service, a user can still use our executor API to offload pieces of the application code into the appliance and run it within the box.

This is particularly useful in cases where the application wants to leverage the processing power of the UCS machine without necessarily moving the entire application into the platform.

2. Complete pre-engineered platform –- In this mode, both GigaSpaces and the application run on the UCS platform. GigaSpaces acts as the container for the application services and the application can exploit the full capacity of the UCS machine through the GigaSpaces in-memory middleware stack. For java-based applications, GigaSpaces supports a standard deployment model that enables seamless deployment into the platform.

 

 

Final words

These are exciting days in the industry, with lots of new breakthrough technologies being introduced on a daily basis. Having been at the cutting edge of that curve for many years, I feel really excited about the work with Cisco UCS. Not just because of the elegance in the design of its hardware but also because the Cisco team that worked with us through this entire process has been a great partner to work with.

Going forward, I see a great potential here as we can finally break the hardware and software wall. On one hand, the fact that the hardware can finally interact with the software that runs on top of it with no middleman puts a lot of power in our hands. On the other hand, we see a shift where application developers can focus on the business while the platform distributes work, maintains consistency, availability, performance and security of the underlying resources including CPU, Memory, Disk and Network. In doing so they become completely abstracted from the underlying operating system and hardware.

With that in mind, we are no longer limited to the services that are provided by the operating system or even by the JVM.

As platform providers we can call directly into the network interface, we can use deep inspection into resource capacity and the traffic matrix in order to proactively respond to demand surge in an effective way and take an immediate benefit from it, while at the same time keep the application unchanged.  We can also create much more robust platforms as we can get immediate alerts directly from the device when something goes wrong. I can only imagine how robust our platform can become just by getting rid of all the loops that we need to maintain today through the entire software stack, to detect failure.

We are only scratching the surface with this offering and there are probably more areas for innovation that we have not yet explored. This could be a great opportunity to send us your wish list and be part of this project.

References

• Intel - Terascale overview
• Mating Grid And Cloud Software With Hardware (Forbes)
• GigaSpaces UCS integration (GigaSpaces wiki)
• GigaSpaces-Cisco Joint Solution Whitepaper 
• GigaSpaces-Cisco solution page 
• Nahlem Micro Architecture
• Cisco UCS B-Series M2 Blade Servers

The Tera-Scale Effect -- Part I

In the past year, Intel issued a series of powerful chips under the new Nehalem microarchitecture, with large numbers of cores and extensive memory capacity. This new class of chips is is part of a bigger Intel initiative referred to as Tera-Scale Computing. Cisco has released their Unified Computing System (UCS) equipped with a unique extended memory and high speed network within the box, which is specifically geared to take advantage of this type of CPU architecture .

This new class of hardware has the potential to revolutionize the IT landscape as we know it.

In  Part-I of this post, I want to focus primarily on the potential implications on application architecture, more specifically on the application platform landscape.

In Part-II of this post I will use the new GigaSpaces offering on top of Cisco UCS  as a reference implementation of the concept from Part-I.

What is Tera-Scale Computing?

Quoting Intel’s Tera-Scale Computing Research Vision:

By scaling multi-core architectures to 10s to 100s of cores and embracing a shift to parallel programming, we aim to improve performance and increase energy-efficiency.

"Tera" means 1 trillion, or 1,000,000,000,000. Our vision is to create platforms capable of performing trillions of calculations per second (teraflops) on trillions of bytes of data (terabytes).

To put in simple words, Tera-scale is a commoditized version of the mainframe. With this new technology, we could easily create supercomputers at an affordable price.

What are the potential implications on current deployments?

One of the more trivial and probably more common use cases that comes with the introduction of these new powerful machines is the ability to condense more applications and virtual machines on less hardware. In this specific post, however, I'll refer mostly to the implications for the large-scale distributed applications that are becoming more popular these days, as the demand for scaling continues to grow, while cloud-based deployments are becoming more common and affordable.

Is it the end of distributed systems?

For anyone who deals with large scale deployments, it might feel at first impression that we're back to the mainframe days. However, a closer look can yield a completely different picture.

Quoting from my previous post Scale out vs Scale up:

The increased hardware capacity will enable us to manage more data in a shorter amount of time. In addition, the demand for more reliability through redundancy, as well as the need for better utilization through the sharing of resources driven by SaaS/Cloud environments, will force us even more than before towards scale-out and distributed architecture.

So, in essence, what we can expect to see is an evolution where the predominant architecture will be scale-out, but the resources in that architecture will get bigger and bigger, thus making it simpler to manage more data without increasing the complexity of managing it. To maximize the utilization of these bigger resources, we will have to combine a scale-up approach as well.

More specifically, the implications can be broken into two categories:

• Density – we can serve the same capacity and workload of our existing applications on significantly less hardware. This obviously yields an immediate benefit in terms of operational cost associated with the reduced maintenance, cooling and power, space, cabling etc.
• Capacity – we could get tens or hundreds times over the capacity and processing power from the same size and cost of today’s cluster.

The second point is where I see the greater potential. Imagine running your entire application completely in-memory, i.e. -- the disk will become the new tape. The fact that we can now get terabytes of data in-memory with only a few boxes means that we can do things that we couldn’t have dreamt of before -- we can process complex analytics that used to take hours in real time, run new classes of complex fraud detection algorithms, and recognize malicious attacks before they happen. We could correlate customer trends and increase the conversion trend from our visitors in our e-commerce sites. As a Telco provider, we could serve multi-media and social networking activities, process and render videos and images quickly, and provide more targeted and personalized commercials. We can build online gaming applications that could run 3D animation at a fraction of the cost. And the list can go on and on…

The Challenge

As with any new technology, exploiting its full potential involves change. The main challenge is with existing applications. Existing (large scale) applications were not built to utilize new multi-core, network, and memory capacity, simply because they were written at a time when memory was expensive and available at lower capacity of only a few GBs at most, network was considered a bottleneck, and multi-core didn’t exist or was just beginning to emerge. In addition, most of these  application were designed to run against a centralized database or some sort of centralized storage, which makes it even harder to take advantage of the power behind this new class of machines.

 

So while this new class of hardware holds tremendous promise, there is a small caveat that is worth noting in Intel's vision:

By scaling multi-core architectures from tens to hundreds of cores and embracing a shift to parallel programming...

In other words, Intel recognizes the fact that to take full advantage of this new class of hardware, we need to embrace a new architecture that better lends itself to parallel programming.

Tera-Scale Reference-Architecture:

The diagram below, taken from the Intel reference architecture, points to the fact that in order to take advantage of the new underlying multi-core architecture we need a specialized software platform that is thread-aware and can abstract the application from the details of the underlying infrastructure.

 

In other words, we rely on the application platform to become the glue that enables us to migrate our existing applications from the current centralized model into a a more parallel and decentralized model. To make the transition simple, the platform will need to continue and support the existing interfaces and APIs, but replace them with more scalable implementations. At the same time, the platform needs to expose new capabilities that will enable development of new services that are designed with parallel distribution in mind.

There are two fundamental requirements of such a platform:

Scalable Software Infrastructure

• Highly parallel – The platform itself needs to be designed with extreme parallelism in its internal engine as well as expose parallel programming and event-driven semantics to the application.
• In-Memory – Memory is the only physical device that can manage highly concurrent transactions. To achieve maximum utilization the platform must not rely on disk or devices that do not lend themselves to concurrent processing.
• Scale-up and Out – The platform needs to support seamless transition between scale-up within a machine and scale-out between machines without changing the application code.

Simple – Pre-Integrated

The complexity often associated with tuning of the software and hardware together is going to increase exponentially in this highly parallel environment. Therefore, we can’t afford to think of the software platform and hardware infrastructure as two separate things. Instead, it must be responsibility of the platform to provide a pre-integrated and tuned environment, which includes:

• Hardware and Software tightly integrated – As the application is only exposed to the platform and not to the operating system, a tightly integrated platform can have much more room to use proprietary optimization of the hardware than the application itself. It can integrate with lower-level pieces of the hardware such as tuning network routing, moving the execution environment to the right core to minimize the NUMA effect and take full advantage of the CPU cache. 
• Zero configuration – The platform should come pre-tuned and expose a simple setup that can be applied to the entire platform in a consistent way.
• Fully automated deployment – Deploying even the most complex application should involve a single deploy command that could in turn wire all the pieces together programmatically without exposing any manual step to the end user. This includes also the ability to deal with post deployment events, such as recovery processes and auto-scaling. This implies that the platform needs to have built-in integration for Dev-Ops APIs that are backed into the core of the platform and expose full control over the infrastructure services -- Memory, Machine, CPU, Network and middleware services (data, messaging and processing, web, etc.).

In  Part-II of this post, I discuss the specific implementation of this concept in our new GigaSpaces Tera-Scale solution for Cisco UCS.

 

References

• The Tera Scale Effect Part II
• Mating Grid And Cloud Software With Hardware (Forbes)
• Intel - Terascale overview
• Memory is the New Disk for the Enterprise

NoCAP - Part II Availability and Partition tolerance

Abstract

Eric Brewer's CAP theorem is one of the foundations behind the design and architecture of many of the large scale systems architectures. According to the one form of the CAP theorem, “You either choose availability or consistency. You cannot choose both.” 

Is this our only choice?

In this post I'll try to provide an aggregated view of the different perspectives on this question and plant the seeds for an alternative approach.

Availability vs Partition tolerance.

One of the thing that comes up repetitively through the various debates is the lack of clarity behind the definition between Availability and Partition Tolerance.

To set the stage I’ll  start by referring to the original definitions by Gilbert and Lynch . I’ll use Coda Hale's You Can't Sacrifice Partition Tolerance - a "must-read" that provides a good summary.

Brief history  (By Coda Hale):

In 2000, Dr. Eric Brewer gave a keynote at the Proceedings of the Annual ACM Symposium on Principles of Distributed Computing¹ in which he laid out his famous CAP Theorem: a shared-data system can have at most two of the three following properties:Consistency,Availability, and tolerance to network Partitions. In 2002, Gilbert and Lynch²converted “Brewer’s conjecture” into a more formal definition with an informal proof.

The original definition by Gilbert and Lynch:

Availability

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. That is, any algorithm used by the service must eventually terminate … [When] qualified by the need for partition tolerance, this can be seen as a strong definition of availability: even when severe network failures occur, every request must terminate.

Partition tolerance

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another. When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost. (And any pattern of message loss can be modeled as a temporary partition separating the communicating nodes at the exact instant the message is lost.)

Dr. Stonebraker’s "Consistency over Partition Tolerance"

Dr. Michael Stonebraker’s post Errors in Database Systems, Eventual Consistency, and the CAP Theorem argues that since partition failures are rare you might sacrifice partition tolerance for consistency and availability:

Obviously, one should write software that can deal with load spikes without failing; for example, by shedding load or operating in a degraded mode. Also, good monitoring software will help identify such problems early, since the real solution is to add more capacity. Lastly, self-reconfiguring software that can absorb additional resources quickly is obviously a good idea.

In summary, one should not throw out the [Consistency aspect] so quickly, since there are real error scenarios where CAP does not apply and it seems like a bad tradeoff in many of the other situations.

Henry Robinson (Cloudera) describes "CAP Confusion"

Henry Robinson, in his response to Dr. Stonebraker entitled Problems with ‘partition tolerance’, argues that failure are inevitable and therefore you can’t give away partition tolerance:

..Partition tolerance is not something we have a choice about designing into our systems. If you have a partition in your network, you lose either consistency (because you allow updates to both sides of the partition) or you lose availability (because you detect the error and shutdown the system until the error condition is resolved). Partition tolerance means simply developing a coping strategy by choosing which of the other system properties to drop. This is the real lesson of the CAP theorem – if you have a network that may drop messages, then you cannot have both availability and consistency, you must choose one..

Coda Hale : "You Can't Sacrifice Partition Tolerance"

Coda Hale also argues that you can’t give away partition tolerance in his response, You Can't Sacrifice Partition Tolerance. Mr. Hale suggest a more relaxed version of availability through graceful degradation that is based on the yield and harvest model from  Eric A. Brewer's ACM article, Lessons from Giant-Scale Services:

You cannot ... choose both consistency and availability in a distributed system.

Of the CAP theorem’s Consistency, Availability, and Partition Tolerance, Partition Tolerance is mandatory in distributed systems. You cannot not choose it. Instead of CAP, you should think about your availability in terms of yield (percent of requests answered successfully) and harvest (percent of required data actually included in the responses) and which of these two your system will sacrifice when failures happen.

Dr. Stonebraker - Partition tolerance and Machine failure are two separate things

Both Henry Robinson and Coda Hale reffed to a Machine failure as part of their argument that you can't avoid partition tolerance . Dr. Stonebraker provides clarification on that point on his response to Coda Hale: 

.., the dead node is in one partition and the remaining N-1 nodes are in the other one. The guidance from the CAP theorem is that you must choose either A or C, when a network partition is present. As is obvious in the real world, it is possible to achieve both C and A in this failure mode. You simply failover to a replica in a transactionally consistent way. Notably, at least Tandem and Vertica have been doing exactly this for years. Therefore, considering a node failure as a partition results in an obviously inappropriate CAP theorem conclusion.

Daniel Abadi - Problems with CAP

Daniel Abadi Assistant Professor of Computer Science at Yale University outlines four issues in the current definition of CAP in Problems with CAP, and Yahoo’s little known NoSQL system:

• ..The definition of CP looks a little strange --- “consistent and tolerant of network partitions, but not available” --- the way that this is written makes it look like such as system is never available --- a clearly useless system

• ..the roles of the A and C in CAP are asymmetric. Systems that sacrifice consistency (AP systems) tend to do so all the time, not just when there is a network partition

• ..What if there is a network partition? What does “not tolerant” mean? In practice, it means that they lose availability if there is a partition. Hence CP and CA are essentially identical

• Lack of latency considerations in CAP significantly reduces its utility.

Daniel suggest an alternative definition to CAP:

..CAP should really be PACELC --- if there is a partition (P) how does the system tradeoff between availability and consistency (A and C); else (E) when the system is running as normal in the absence of partitions, how does the system tradeoff between latency (L) and consistency (C)?

My Take

The main issue that I see with the current definition of CAP is that it describes each of the properties of CAP in absolute terms. In reality, however, each of the properties can be applied in various degrees. Eric Brewer's definition of yield and harvest is one example of a more relaxed version of availability. Interestingly enough the last note in Gilbert and Lynch is also an interesting recognition that it may be possible to achieve different tradeoffs that provides both Availability and Consistency:

..in partially synchronous models it is possible to achieve a 
practical compromise between consistency and availability. In particular, 
most real-world systems today are forced to settle with returning “most of 
the data, most of the time.” Formalizing this idea and studying algorithms 
for achieving it is an interesting subject for future theoretical research.

The same applies to Partition Tolerance – there are various degrees of partition tolerance. Probably the most extreme one are the one suggested by some of the commenters which is to do with WAN. As Dr. Stonebraker argues, even that is not necessarily a high likelihood scenario for most applications:

There is enough redundancy engineered into today’s WANs that a partition is quite rare. My experience is that local failures and application errors are way more likely. Moreover, the most likely WAN failure is to separate a small portion of the network from the majority. In this case, the majority can continue with straightforward algorithms, and only the small portion must block. Hence, it seems unwise to give up consistency all the time in exchange for availability of a small subset of the nodes in a fairly rare scenario.

So the question whether or not you can address partition tolerance shouldn’t be measured in absolute terms but against the most likely scenario for your application. The answer as to what is a most likely partition tolerance scenario really comes down to common sense and may vary over a course of time and application business needs. 

The introduction of the cloud may also change some of our core assumptions on how we deal with failure. With cloud, we can easily bring an alternate machine up to deal with a failure in matters of minutes, and we can also assume that we have a fairly robust underlying infrastructure with lots of built-in redundancy. That in itself changes the scenario where failures can happen as well as the way to deal with them, compared to the time when the original CAP Theorem was written. 

Another source for confusion is the use of Amazon, Google and Facebook as a reference to justify the eventual consistency model. What we often tend to forget is that Amazon, Facebook and Google face fairly unique challenges that are not that common and even those three still rely on strongly consistent systems for the majority of their applications. As noted in Will Scalable Data Stores Make NoSQL a Non-Starter?:

Facebook famously invented the NoSQL Cassandra database but still relies on the venerable MySQL-plus-memcached combination for the brunt of its critical operations.

The bottom line of my argument is that giving up consistency should be our last resort. Rather then giving up Consistency for Partition Tolerance we could consider a different set of tradeoffs that deals with various degrees of Consistency, Availability, and Partition tolerance that fit our business needs and also take the performance and latency tradeoffs into account.

In the next post on that subject I’ll outline how that can be achieved using the reference architecture that I outlined in the previous post.

Special thanks

I would like to thank Ron Pressler for the constructive debate and for the useful references 

References:

• Errors in Database Systems, Eventual Consistency, and the CAP Theorem (Dr. Michael Stonebraker)

• You Can't Sacrifice Partition Tolerance - (Coda Hale)

•  Will Scalable Data Stores Make NoSQL a Non-Starter?

• Problems with CAP, and Yahoo’s little known NoSQL system

• You Can't Sacrifice Partition Tolerance