Wednesday 16 April 2008

ACID and BASE

Here's a couple of classic ideas that are still good distributed system thinking exercises today - the ACID/BASE concepts are essentially a pair of acronyms describing two opposing extremes of system attributes.  ACID is a fairly established computer science principle from way back in the DB-centric days (it's what school taught us was important to systems) and BASE is what more and more of today's systems are being forced towards through web scalability problems.  Let's take a look at both:

ACID

ACID stands for Atomicity, Consistency, Isolation and Durability and usually describes the behavior of a tightly bound, data centric system.

DB people will have no trouble with atomicity, this is the property of a database operation which offers the "all or nothing" guarantee - for example we won't credit your account if we can't debit your credit card.  Works on the principle that you'd rather not do one without the other (like our banking example).

Consistency is a massive topic on its own but if forced into a one-liner I'd say it's a measurement of identicalness for any given data set no matter where or how many times it appears in a system.  Assuming ACID consistency means strong consistency (and from context that's a safe bet) an example here is an East-West replica set where if you change your password via a client of one DB our system dictates that change must appear in our other DB as instantly as the speed of light allows - because no matter when or where that unit of data is observed from every copy must always be the same.

The next property, isolation, can almost be described as locking (but can't the whole thing?).  It is the process by which data being updated is hidden away from other processes/nodes until it whatever value-changing operation is completed and the changes are committed.  Isolation ensures integrity (for example I can't spend the same money twice from my back account no matter how quickly I put my card in another ATM) but is the enemy of concurrence.  A lot of people think durability is about availability and it kind of is, just not the sort of availability I settle for.

Durability is that property of a data store that promises to keep your information safe - in other words once the system has satisfied atomicity you will always be able to recall that data accurately.  This is usually about writing to persistent storage and journalling changes in a transaction log.  If, for example, the disks that the database files reside on are destroyed then I should be able to replay said logs against my most recent copy (do backups or die) and end up right back where I was.

BASE

BASE stands for Basically Available, Soft state and Eventual consistency and describes the attributes of a loosely coupled system valuing availability and tolerance over strict consistency and isolated operations.

Basically available is recognizing that the availability of a system as a whole should never be the same as the availability of any individual node/feature/service within that system - your system should survive the death of it's component parts.  It's saying we never try to guarantee that a given data store will always be here (as ACID assumes) we just build a lot of tolerance into the system so that there is usually enough of it alive at any given point in time to present something usable.  More than that, basic availability is about saying we'd rather deal with conflict resolution and versioning issues than pay a scalability and availability price with isolation.

State [in this context] is essentially whether we're required to track, remember and somehow use preceding events in a flow of activity (stateful) or whether we can provide the right responses to requests without knowing what the immediately preceding activities and their results were (stateless).  Stateful operations tend to be unique to individuals (or groups); for example account management - you want to make sure a user has successfully logged in before you let them edit their address or payment details.  Stateless operations tend to be wider in scope; for example pushing out price feeds or updating a product catalogue - you usually want everyone to see the same thing no matter where they are.  Traditional state management is about recording a series of values in a centralized storage point so that other processes or nodes can retrieve it whenever they need to make decisions based on what you did before.  Soft state is about pushing back the use of state until the last possible moment it's needed and using techniques like leasing/refreshing and partitioning to reduce dependencies created by a single source of truth.

Now we're left with eventual consistency which says that when a distributed/replicated item of data is created or changed in one location it will be changed everywhere else after a period of time rather than immediately in ACID's strong consistency model.  Continuing with our product catalogue example you'd want to have that set in a few locations so that it was close to where your customers were (performance) and you can be sure could always show a list/search result (availability).  When you add a new iron to your homeware section does it really matter if it doesn't show up in every location for 10 minutes?  Of course the benefits are based on the premise that we'd rather have a quick answer that isn't 100% up to date than a slow one that is (or no answer at all).

So...

Webscale systems are moving along towards BASE as we realize how valuable a commodity availability is and how difficult it is to scale systems to meet the demand the Internet creates.  We're suddenly faced with challenges that are impossible (or grossly unprofitable) to meet with traditional thinking and are forced to start making tradeoffs that just don't match ACID - relax consistency to buy availability?  Relax isolation to buy scale?

One last thing that's worth noting is different parts of the same system can occupy a different point along the ACID/BASE continuum.  Thinking about that iron we added to homeware we might not be bothered about it instantly showing in every replica of our catalogue (eventual) but what if we realise we made a mistake on the price and we're selling them for much less than they cost us?  We might want that sort of update to be immediately pushed out super quick (strong).

No comments: