Overview
Brewer’s CAP Theorem says that a distributed application has to relax at least one of three properties - Consistency, Availability and Partition Tolerance.It is often Consistency that is relaxed in favor of Availability and Partitioning. For example, several popular database engines provide for geographically distributed instances, each of which commits its transactions locally, and then replicates to one or more remote instances. In the event these updates collide with (or conflict with) updates made locally, corrective action can be initiated, either with a blanket rule such as “local always wins”, “remote always wins” or “ignore”; or with something more sophisticated, such as invoking application logic to take corrective action.
However, there are applications where detection of colliding updates does not suffice to ensure Consistency (where Consistency is defined as the database always being within the design parameters of the application logic – for example, the “in balance” guarantee that the sums of the assets and liabilities columns of a balance sheet are always equal). There are applications where Consistency may require that the data read by application logic, not just the updates. must also be validated when checking for collisions.
I refer to collision detection by validating updates alone as Eventual State Consistency, and collision detection by also validating data read as Eventual Path Consistency.
Example
A and B are two instances. Users initiate financial transactions on two accounts, P and Q, as well as a transaction to change a service charge rate. The service charge rate affects the result of the transactions on P and Q. The business requires that after a service charge rate change, transactions must reflect the new rate or have exceptions logged against them as requiring further action.| Instance A | Instance B | Comments |
| Change service rate | ||
| Transaction on Q | Transaction on Q uses new service charge rate. | |
| Transaction on P | Transaction on P uses old rate since the rate change has not propagated to A. | |
| Apply replicated service rate change | Change applied. There is no collision in A, and Consistency is maintained since the transaction on P precedes the rate change. | |
| Apply replicated transaction on Q | Change applied. There is no collision detected by A in either the update, or any data read by logic to compute the update. | |
| Attempt to apply replicated transaction on P | Instance B should detect a collision, since it should observe that the data that was read by the application logic on A to compute the result of transaction P has changed on B, and therefore Consistency of B cannot be guaranteed. Corrective action should be required. |
Although applying updates would result in the two instances A and B having the same state, they would not have the same path through state space. There are situations where having the same end state may be acceptable, but other situations where it is not – consider, for example, the case where the path through state space resembles a short-term interest-free loan! In some applications, an audit (e.g., from an examination of the archived journal files of the database) must show that the path through state space is Consistent at the point when each transaction is committed.
The situation when there are three instances, A, B and C is significantly more complicated. There are scenarios when transactions processed on A and B can replicate to each other without colliding, but where C is unable to maintain Consistency with respect to transactions processed and committed on A and B, and replicated successfully to each other, because of timing differences between replication to C from A and B.
Corrective Action
In a future post, I will discuss one way to take corrective action to restore Consistency, at least in the case of two instances.
Is it possible to have the discrete database instances made to follow a specific order? For example if different instances would commit a set of transactions in a pre-determined order, all instances will have the same result eventually and otherwise. Concurrent systems (operating systems) do not have good means to address this challenge. However, if databases could provide sufficient means so that transactions can be ordered externally -say at commit times, couldn't we address the scalability along with reliability? Although ordering leads to performance concerns, overall we will come out far ahead, given the distribution of transactions across several machines?
ReplyDeleteThanks in advance
Anil
I don't think the example really illustrates the problem. In the last step, how is B able to observe that the data used for the transaction on A has changed on B? It could only know that if it knew either the value or the exact replication state on A when P was originally processed, and if it knows either then it has all the information it needs to apply the replicated transaction consistently. The problem, rather, occurs when B doesn't know whether the rate change had propagated to A yet or not - two states which would need to be handled differently but which could not be distinguished from one another. That problem can be trivially avoided either by including the currently applicable service rate in the replicated transaction P, or by treating the service-rate charge as a separate replicated operation which does not need to use the value at B. Either way, the "in balance" consistency guarantee is always maintained without the need for further corrective action.
ReplyDeleteThe rule here is that the replication code in this kind of system should never pass a *reference* to a value which is required for consistency (in this case the service rate). That's using a shared-state model in a no-shared-state system. Instead, one should either pass the value itself, or do calculations involving the local value before initiating replication of the semantically higher-level result. Which you choose depends on exactly what consistency guarantees you're trying to provide, but passing a pointer from one address space to a process in another should never be expected to work.
Bhaskar,
ReplyDeleteI assume you already know about Seth Gilbert and Nancy Lynch formal proof of the CAP theorem, so I wonder what you mean by your first sentence of the post.
Anil, in the general case, it is not possible to order transaction commits. Consider a case where I make a withdrawal at an ATM in New York at the same time that my wife makes a withdrawal in San Francisco. If you require an East Coast and a West Coast instance to communicate to post the transactions, then you will lose availability if the network is down.
ReplyDeleteAlex: it should be noted that what Gilbert and Lynch proved was a particularly precise mathematical interpretation of CAP. It can quite reasonably be argued that their definitions or assumptions (e.g. C = serializable) might make their proof inapplicable to real-world systems where the operative definitions are different. It's still an interesting and valuable result, but it has to be taken with a grain of salt.
ReplyDeleteJeff Darcy commented on this post, but for some reason his comments did not show up here (I received an alert about, but didn't see anything from him here and assumed he had deleted it; evidently he did not). His (more detailed) comment is at http://pl.atyp.us/wordpress/?p=3215 - I will try to digest his words and respond later this weekend.
ReplyDelete