OverviewBrewer’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.
ExampleA 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.
In a future post, I will discuss one way to take corrective action to restore Consistency, at least in the case of two instances.