Maintaining Eventual Path Consistency

In an earlier post (Eventual State Consistency vs. Eventual Path Consistency), I wrote about the difference between two types of Eventual Consistency. While Eventual State Consistency is the more familiar variety, there are applications that require Eventual Path Consistency.

We are of course discussing Eventually Consistent application configurations that relax Consistency in favor of Availability and Partition tolerance per the CAP theorem. If either of Availability and Partition tolerance can be relaxed, Consistency is easily provided, for example, by ensuring that a transaction is committed at the remote instance as part of committing it at the local instance.  The case where Consistency can be relaxed is not just more desirable in an “always on” business environment where the competition is just mouse clicks away - it is also technically more challenging (and hence more interesting to a geek like me).

In order to provide Eventual Consistency, an application has to (a) detect when two instances have diverged - i.e., are mutually Inconsistent - and (b) bring them back to a Consistent state.

Eagle Scout Tracking Sheet

There is a lot to do for a boy scout to go from the rank of Life to the rank of Eagle.  On Google docs I have created a spreadsheet that a boy scout troop can use to track the progress towards the rank of Eagle of Life scouts.  My intention is for this to be a tool for scouts themselves to use, rather than having their parents or troop adult leaders using this.  In addition to helping them see where they are in the process, I think seeing where their peers stand helps to motivate scouts!

Software Compared to Cities

(I have previously posted earlier versions of this write up elsewhere.)

Why should a system that is working well need to be replaced?

Successful software systems are like cities.  There are cities in Europe that have been continuously inhabited for thousands of years.  London or Rome today would be unrecognizable to Julius Caesar, yet the old cities were never abandoned and replaced - they were just continuously re-developed over the centuries.  Although we like to discuss replacing major software systems because their quirks annoy us, perhaps we should think of these as limitations that must be lived with, just as in these days of the automobile, we still deal with streets in Boston that were engineered for horses and wagons, and we have no intention of razing and rebuilding downtown.

Eventual State Consistency vs. Eventual Path Consistency

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.

From 44 seconds to 27 seconds - Simple Tuning of the 3n+1 Benchmark on GT.M

The bottom line first: with a little simple tuning, I was able to improve the performance on my laptop of my benchmark of the 1 to 1,000,000 3n+1 problem.

• For four worker processes:
• from 44 to 27 seconds
• from to 72,026 to 109,311 reads/second
• from to 49,298 to 74,828 updates/second
• For eight worker processes:
• from 248 to 30 seconds
• from 12,782 to 109,285 reads/second
• from 8,750 to 74,802 updates/second

Responses to Dan Weinreb's comments of February 1, 2011

I am responding to Dan Weinreb's comments to my post Comments in response to Don Anderson's 3n+1 benchmark with another blog entry because this was too long to post as a reply.

Comments in response to Don Anderson's 3n+1 benchmark

I am thrilled that Don Anderson has responded to a benchmarking problem I proposed aimed at apples to apples benchmarks of databases and platforms.