My take on CAP

The CAP the­o­rem (Con­sis­ten­cy, Avail­abil­i­ty, Par­ti­tion­ing) has been re­ceiv­ing quite a lot of in­ter­est late­ly, just to men­tion one of the many ref­er­ences.

What is CAP about?

First let me give cred­its here: I am de­riv­ing my in­spi­ra­tion from the the­o­ret­i­cal in­sights found in this pa­per co-au­thored by one of my fa­vorite woman sci­en­tists, Nan­cy Lynch from MIT. If you get a chance to read this pa­per, go ahead it will bring you some very use­ful fun­da­men­tal un­der­stand­ing...

The CAP the­o­rem is es­sen­tial­ly a lim­i­ta­tion on what you can do with clus­tered (web) ser­vices in the fash­ion­able con­text of SOA.

The word 'clus­ter' is im­por­tant here since that is what it is all about. In par­tic­u­lar, the the­o­rem states that you can't have all three prop­er­ties (Con­sis­ten­cy, Avail­abil­i­ty, Par­ti­tion­ing) in one and the same sys­tem (read: ser­vice). This im­plies that there is no per­fect so­lu­tion to build­ing a high-through­put pop­u­lar ser­vice, or is there? Let's first ex­plore what each thing means...

Con­sis­ten­cy

By con­sis­ten­cy, the the­o­rem refers to the prop­er­ty that changes (up­dates) to the ser­vice back-end are vis­i­ble to lat­er queries. Sim­pli­fy­ing: if you add some­thing to your shop­ping bas­ket then it will ap­pear there next time you re­trieve your bas­ket sta­tus. That sounds triv­ial, but it is not if the bas­ket is spread over mul­ti­ple phys­i­cal serv­er process­es... Con­sis­ten­cy is com­mon­ly en­sured (be­tween process­es) by hav­ing some sort of dis­trib­uted trans­ac­tion co­or­di­na­tor, or (as­sum­ing a cen­tral back-end) a sin­gle cen­tral­ized data­base.

Avail­abil­i­ty

The Lynch pa­per uses a very sim­ple but suf­fi­cient de­f­i­n­i­tion of "avail­abil­i­ty": a sys­tem is avail­able if every re­quest to it re­turns. In oth­er words: there is no in­fi­nite block­ing.

Par­ti­tion­ing

Par­ti­tion­ing means the cut-off be­tween two seg­ments of the clus­ter. In oth­er words, one or more nodes be­come un­reach­able for at least some time.

What is the The­o­rem say­ing?

You can't have all three of the above qual­i­ties, pe­ri­od. How­ev­er, you can com­bine any two of them if you like. This is proven in the pa­per by Lynch et al. Also (and this is im­por­tant) you can ap­ply dif­fer­ent com­bi­na­tions of qual­i­ties to parts of your sys­tem. Mean­ing: you can stress con­sis­ten­cy in one part, avail­abil­i­ty in an­oth­er part, and so on. For in­stance, or­der pro­cess­ing or pay­ment pro­cess­ing can be done con­sis­tent­ly and avail­able (sac­ri­fic­ing par­ti­tion tol­er­ance) where­as query­ing the prod­uct cat­a­log can be done dif­fer­ent­ly (stress­ing par­ti­tion tol­er­ance in fa­vor of con­sis­ten­cy).

Does this con­tra­dict or in­val­i­date Atomikos?

Not at all, quite the con­trary: it makes Atomikos (and its third gen­er­a­tion of TP mon­i­tors) all the more rel­e­vant. Why? Be­cause Atomikos prod­ucts can help you in mak­ing those parts con­sis­tent when you want them to be.

Vir­tu­al­ly achiev­ing all three qual­i­ties

If you em­brace asyn­chro­nous mes­sag­ing (a la JMS or email) and ex­treme trans­ac­tion pro­cess­ing (XTP) then it is pos­si­ble to as­ymp­tot­i­cal­ly re­al­ize all three qual­i­ties (con­sis­ten­cy, avail­abil­i­ty, par­ti­tion-tol­er­ance) pro­vid­ed that you do use a call­back mech­a­nism to com­mu­ni­cate re­sults (e.g., by send­ing a con­fir­ma­tion email). Here is how:

• Queue re­quests in JMS.
• Pro­cess each re­quest trans­ac­tion­al­ly (so fail­ures will leave the re­quest queued for re­tries).
• The process that di­gests each re­quest can be ar­bi­trar­i­ly com­plex and use trans­ac­tions (con­sis­ten­cy) and re­turn when­ev­er it likes (thanks to the queu­ing, no re­ply is ex­pect­ed with­in a pre­set time frame).
• Any lack of avail­abil­i­ty of the pro­cess­ing is re­cov­ered by the queues: failed re­quests will stay queued un­til the process in the back-end is in fact avail­able again.

Now did I just break the CAP im­pos­si­bil­i­ty? More on this in a next post...