La lliçó anterior va acabar amb una taula en què Quilòmetre Zero assignava un model de consistència diferent a cada dada: linealitzabilitat per a l'última unitat de formatge-curat, garanties de sessió per al cistell de l'Anna, consistència eventual per al comptador de visites. Va quedar pendent la pregunta òbvia: si la linealitzabilitat és la garantia més còmoda per al programador, per què no donar-la a tot? La resposta és que té un preu que no es paga en euros sinó en disponibilitat quan la xarxa falla i en latència quan no falla, i aquest preu està formalitzat en dos resultats: el teorema CAP i la seva extensió PACELC.

Pocs resultats de la informàtica se citen tant i s'entenen tan poc com CAP. Aquesta lliçó l'enuncia amb la precisió amb què el van demostrar Gilbert i Lynch, explica per què la "P" no és una opció que es pugui descartar i per què l'elecció real és què sacrificar durant una partició, i desmunta els malentesos més estesos ("tria'n dos de tres", "AP vol dir sense consistència"). Després presentarem PACELC, que afegeix el que a CAP li falta (el compromís entre latència i consistència quan tot funciona), i classificarem amb ell els sistemes que apareixeran a la resta del curs. Aplicarem tots dos a les dades de Quilòmetre Zero amb una taula de decisions justificades, i una simulació en Python mostrarà el mateix parell de rèpliques inv-bcn/inv-vlc comportant-se en mode CP (rebutjant escriptures sense quòrum) i en mode AP (acceptant, divergint i perdent una reserva en reconciliar). Acabarem amb les crítiques modernes al teorema, que no l'invaliden però sí que obliguen a fer-lo servir amb més cura. Els mecanismes concrets amb què un sistema CP es posa d'acord (consens) i els quòrums de lectura i escriptura són les dues lliçons següents.

1. L'enunciat precís de CAP
2. Per què la partició no és opcional
3. L'elecció real: CP o AP durant una partició
4. Malentesos comuns
5. PACELC: què passa quan no hi ha partició
6. Taula de sistemes classificats
7. Decidir per cas d'ús a Quilòmetre Zero
8. Simulació: el mateix sistema en mode CP i en mode AP
9. Crítiques i matisos: harvest, yield i "deixeu de dir CP o AP a les bases de dades"
10. Errors comuns i consells
11. Exercicis
12. Conclusió

Eric Brewer va presentar CAP com a conjectura en una xerrada de l'any 2000; Seth Gilbert i Nancy Lynch el van demostrar formalment el 2002. La demostració és senzilla, però només si les tres lletres estan ben definides, i aquí és on comença la confusió, perquè en l'ús col·loquial cadascuna significa alguna cosa més vaga del que diu el teorema:

Amb aquestes definicions, el teorema diu: en un sistema distribuït asíncron en què hi pot haver particions, és impossible garantir simultàniament linealitzabilitat i disponibilitat.

La demostració cap en un paràgraf. Sigui un registre amb valor inicial v0 replicat en dos nodes, N1 i N2, i una partició que els separa. Un client escriu v1 a N1. Per disponibilitat, N1 ha de respondre "fet" sense esperar N2 (amb qui no pot parlar). Un altre client llegeix després a N2. Per disponibilitat, N2 ha de respondre; però N2 no ha rebut res de N1, així que només pot respondre v0. Aquest historial (escriptura de v1 acabada, lectura posterior que retorna v0) és exactament l'historial 1 de 03-01: no és linealitzable. Per tant, o N1 no respon (sacrifica A), o N2 retorna un valor antic (sacrifica C). No hi ha una tercera opció.

Una lectura ingènua del teorema ("tria'n dos de C, A i P") suggereix que es pot renunciar a P i quedar-se amb C i A. En un sistema distribuït real aquesta opció no existeix, per dues raons que ja coneixem del Mòdul 1:

• La xarxa és imperfecta (fal·làcia 1 de 01-04). Cables tallats, switches que es reinicien, taules de rutes mal aplicades, un firewall que descarta paquets, un node tan sobrecarregat que no respon a temps (recorda que en un sistema asíncron, 01-02, "lent" i "particionat" són indistingibles). La pregunta no és si hi haurà particions sinó quantes vegades l'any.
• Renunciar a P vol dir que, quan passa una partició, el sistema deixa de complir C, A o totes dues de manera no controlada. És a dir, "CA" no és una elecció de disseny sinó l'absència d'una: el sistema es comportarà d'alguna manera durant la partició, i si el dissenyador no l'ha decidida, serà la pitjor.

L'únic que sí que es pot fer és reduir la probabilitat i l'abast de les particions: nodes al mateix rack, xarxes redundants, o directament un sol node. Una base de dades PostgreSQL en una sola màquina és "CA" en el sentit trivial que no hi ha res a particionar, i per això el monòlit de Quilòmetre Zero de 01-06 mai no va haver de pensar en això. Tan bon punt inventari té inv-bcn a Barcelona i inv-vlc a València, unides per 350 km de fibra que no controla, P està decidida.

Amb P fixada, el teorema es redueix a una decisió: quan la partició passa, què fa un node que no pot parlar amb els altres?

• CP (consistència per sobre de disponibilitat): el node que no es pot coordinar rebutja l'operació (o la bloqueja fins que la partició es curi). Al diagrama, N1 respondria a l'Anna "ara no puc confirmar la reserva", i N2 respondria a en Marc "no et puc garantir un valor actual". Ningú no llegeix dades antigues, però part del sistema, o tot, deixa de servir. A la pràctica, un sistema CP acostuma a deixar operatiu el costat de la partició que té majoria (quòrum) i apagar el minoritari; com es decideix qui té majoria és el consens de 03-03.
• AP (disponibilitat per sobre de consistència): tots dos nodes continuen responent amb el que tenen. L'Anna reserva a N1, en Marc llegeix (i potser reserva) a N2, cada costat acumula escriptures que l'altre no veu, i quan la partició es cura cal reconciliar: decidir què passa amb dues reserves del mateix últim formatge. La reconciliació pot ser tan simple com "guanya l'última" (amb pèrdua de dades) o tan sofisticada com un CRDT de 03-01 (sense pèrdua, però sense invariants).

Fixa't que l'elecció no és global ni permanent: és per operació i durant la partició. Un sistema pot ser CP per a les escriptures i AP per a les lectures; pot ser CP per a l'estoc i AP per al cistell; i fora de la partició, totes dues lletres es compleixen sense conflicte. Un sistema ben dissenyat es comporta de manera idèntica el 99,9 % del temps sigui CP o AP; l'etiqueta només descriu què fa en el 0,1 % restant.

Daniel Abadi va observar el 2012 que CAP ignora l'estat normal del sistema. La major part del temps no hi ha cap partició, i tanmateix els sistemes continuen prenent decisions de compromís: cada escriptura linealitzable s'ha de coordinar amb altres rèpliques abans de respondre, i aquesta coordinació costa un o diversos viatges de xarxa. PACELC ho formula així:

Si hi ha Partició, triar entre Availability i Consistency; Else (si no n'hi ha), triar entre Latency i Consistency.

La segona meitat és la que descriu el dia a dia. Amb inv-bcn i inv-vlc connectades i sanes, una reserva linealitzable (EC) requereix que inv-bcn esperi la confirmació d'inv-vlc abans de dir "fet" a l'Anna: uns 10 ms d'anada i tornada Barcelona-València, més al percentil 99. Una reserva en mode EL respon tan bon punt s'escriu localment i replica en segon pla; l'Anna veu una resposta en 1 ms, a canvi que inv-vlc pugui anar uns mil·lisegons per darrere (la propagació retardada de la simulació de 03-01). Les quatre combinacions resultants:

PACELC no és un teorema sinó un marc de classificació, però converteix la discussió abstracta en una pregunta concreta que es pot fer a qualsevol magatzem: "què fas durant una partició, i quants viatges de xarxa fas per escriptura quan no n'hi ha?".

Els sistemes que apareixeran a la resta del curs, classificats amb PACELC. Molts són configurables, i per això la classificació indica la configuració:

Dues observacions sobre la taula. Primera: la mateixa base de dades apareix en files diferents, perquè l'elecció es fa per configuració i sovint per operació; això és el que Kleppmann critica a l'apartat 9. Segona: els sistemes de coordinació (etcd, ZooKeeper) són sempre PC/EC i accepten el cost de bon grat, perquè la seva funció és precisament ser la font de veritat sobre qui és líder o quina és la configuració vigent; un sistema de coordinació AP seria inútil.

Amb el marc a la mà, tornem a la taula de 03-01 i justifiquem cada elecció pensant en què passa durant una partició entre Barcelona i València (o entre el núvol on viuen els serveis i les botigues físiques dels productors) i en la latència acceptable la resta del temps:

La regla que emergeix: CP per a allò que és irreversible o disputat (diners, última unitat, lideratge); AP per a allò que es pot corregir, unir o simplement ignorar (cistells, posicions, comptadors, catàleg). I la fila de tomaquet-rosa mostra que la decisió pot dependre de l'estat de la dada, no només del seu tipus.

Construirem dues rèpliques d'inventari que poden operar en qualsevol dels dos modes, i una xarxa que es pot partir. En mode CP, una reserva només es confirma si l'accepten totes dues rèpliques (amb dos nodes, el "quòrum" és la unanimitat; a 03-04 veurem quòrums majoritaris amb N=3). En mode AP, cada rèplica accepta localment i anota la marca de temps; en curar-se la partició, es reconcilia amb last-write-wins.

Sortida:

Què està passant, pas a pas:

• Mode CP: durant la partició, reservar comprova si arriba a l'altra rèplica abans de tocar res. No hi arriba, i llança SenseQuorum: ni l'Anna ni en Marc poden reservar. El sistema ha sacrificat disponibilitat (dos nodes vius que responen amb error) i ha conservat la linealitzabilitat: no hi ha cap historial anòmal possible perquè no hi ha hagut escriptures. En curar-se la partició no hi ha res a reconciliar. Amb N=2, aquest mode és fràgil: qualsevol partició apaga tot el sistema. Amb N=3 i quòrum de majoria (03-03 i 03-04), el costat amb dos nodes continuaria reservant.
• Mode AP: cada rèplica accepta la reserva del seu client i descompta la seva còpia local. Totes dues responen, totes dues queden a zero, i totes dues creuen haver venut l'últim formatge: la lectura "0 / 0" sembla coherent però amaga dues reserves. En reconciliar amb LWW, el sistema compara marques, es queda amb l'escriptura d'inv-vlc (marca 2) i descarta la d'inv-bcn. L'estoc final (0) és incorrecte (hauria de ser -1, cosa que vol dir que un dels dos clients no rebrà el seu formatge) i, pitjor, la reserva de l'Anna ha desaparegut de l'estat de l'estoc encara que continua a la llista de reserves d'inv-bcn. Ningú no se n'assabentarà fins que la Formatgeria Montblanc rebi dues comandes per a una unitat.

L'experiment mostra les dues cares del teorema amb cruesa: CP protegeix l'invariant al preu de rebutjar clients; AP manté tots els clients contents durant la partició i els trenca l'invariant després. I mostra també que LWW és la pitjor reconciliació possible per a dades que es disputen: descarta silenciosament una escriptura sencera. Una reconciliació per operacions (sumar els descomptes de tots dos costats: 1 - 1 - 1 = -1, detectar el negatiu i compensar la comanda d'en Marc) o un llindar que canviï a mode CP en quedar poques unitats, com suggeria la taula de l'apartat 7, serien les alternatives; les estratègies de resolució de conflictes es tracten a 03-04, i la compensació de la comanda d'en Marc, a 03-05.

CAP és correcte com a teorema, però el seu ús com a etiqueta de sistemes ha rebut crítiques serioses que convé conèixer:

• És massa estret. Només cobreix un model de consistència (linealitzabilitat), un tipus de fallada (partició) i una noció de disponibilitat molt particular. No diu res de latència (per això Abadi va proposar PACELC), de fallades de nodes que no són particions, de transaccions ni de particionament de dades. Un sistema pot ser irreprotxablement "CP" i tot i així perdre dades per un disc corrupte, o ser "AP" i estar caigut per un error de desplegament.
• Kleppmann (2015), "Please stop calling databases CP or AP". Martin Kleppmann argumenta que les definicions de CAP són tan específiques que gairebé cap sistema real no hi encaixa netament: MongoDB no és "CP" perquè les lectures de secundaris no són linealitzables ni les escriptures w:1 sobreviuen a un failover; Cassandra no és "AP" en el sentit formal quan es fa servir amb quòrum; i "disponible" en el sentit de Gilbert-Lynch (tot node viu respon) és una propietat que gairebé ningú no vol literalment (un node aïllat que respon amb dades de fa una hora és "disponible" en algun sentit útil?). La seva proposta: descriure els sistemes per les garanties concretes que ofereixen (el vocabulari de 03-01) i pel seu comportament davant fallades concretes, en lloc de per una lletra. La taula de l'apartat 6 s'ha construït amb aquest esperit: cada fila indica la configuració i el comportament, no només l'etiqueta.
• Brewer (2012), "CAP twelve years later". El mateix Brewer va matisar que "dos de tres" és enganyós, que l'elecció és per operació i durant la partició, i que l'interessant és dissenyar la gestió de la partició: detectar-la, entrar en un mode explícit de partició (limitar operacions, registrar el que es fa), i en curar-se, recuperar (reconciliar, compensar). La simulació de l'apartat 8 en mode AP no té precisament aquesta tercera fase ben feta.
• Harvest i yield (Fox i Brewer, 1999). Una manera més fina de pensar la disponibilitat. Yield és la fracció de peticions que es responen; harvest és la fracció de les dades que reflecteix la resposta. Un cercador amb l'índex en 10 fragments que en perd un pot respondre el 100 % de les consultes (yield 1) amb el 90 % de les dades (harvest 0,9). Aplicat a Quilòmetre Zero: durant una partició, la pàgina d'un mercat pot mostrar els productors abastables i ometre els altres amb un avís, en lloc de fallar sencera. És una forma de degradació elegant que CAP, amb la seva A binària, no sap descriure.

La lliçó d'aquestes crítiques no és abandonar CAP sinó fer-lo servir com el que és: un recordatori formal que la coordinació té un preu i que aquest preu s'ha de decidir per dada i per operació, amb el vocabulari precís de 03-01 i no amb dues lletres.

• Presentar un sistema com a "CA". Si algú ho diu d'un sistema amb més d'un node, o no ha pensat en la partició o està descrivint un sol servidor. Pregunta què fa cada node quan no pot parlar amb els altres.
• Etiquetar tota la plataforma amb una lletra. Quilòmetre Zero no és CP ni AP; l'estoc de l'última unitat és CP i el cistell és AP. La decisió és per dada i per operació, i de vegades per estat de la dada.
• Triar AP i reconciliar amb LWW sense mirar què es perd. LWW és l'estratègia per defecte de molts magatzems (Cassandra, entre d'altres) i és correcta per a dades on l'última escriptura realment és la bona (posició d'un repartidor, perfil d'usuari editat per una sola persona). Per a dades que s'acumulen o es disputen, descarta escriptures senceres. Comprova-ho amb una simulació com la de l'apartat 8 abans d'acceptar la configuració per defecte.
• Confondre un node lent amb una partició... o no confondre'ls. En un sistema asíncron no hi ha cap diferència observable. Un sistema CP tractarà un node molt lent com a aïllat i deixarà de comptar-hi; això és correcte, però vol dir que els timeouts (02-03, 07-04) formen part de la decisió CAP, i uns timeouts massa curts converteixen la congestió en particions freqüents.
• Oblidar l'E de PACELC. El cost de la consistència es paga cada dia en latència, no només durant particions. Si la reserva linealitzable de formatge-curat requereix coordinació Barcelona-València, el percentil 99 de ReservarEstoc ho reflectirà. Mesura abans de decidir (07-01).
• Consell: dissenya explícitament les tres fases de Brewer per a cada dada AP: com es detecta la partició, quines operacions es permeten mentre dura i com es reconcilia després. Si no pots descriure la tercera fase, aquesta dada hauria de ser CP.
• Consell: quan algú et pregunti "això és CP o AP?", respon amb les garanties concretes: "les reserves són linealitzables via quòrum i es rebutgen si no hi ha majoria; les lectures del catàleg són eventualment consistents amb un retard típic de 200 ms".

Per a cadascuna de les dades següents de Quilòmetre Zero, decideix CP o AP durant una partició, indica l'elecció L o C en absència de partició i justifica-ho en dues frases. Després, indica quina estratègia de reconciliació faries servir en les AP.

1. La llista de desitjos de la Llúcia (productes marcats per a més tard).
2. El nombre de reserves actives d'un repartidor (que limita quantes comandes més se li poden assignar; màxim 8).
3. La valoració mitjana (1-5 estrelles) del Celler Roure Alt.
4. L'estat d'una comanda (creada → pagada → en_repartiment → lliurada).

Modifica Inventari perquè el mode es decideixi per producte i per estat: si l'estoc del producte a la rèplica local és més gran que un llindar (per exemple 5), la reserva es processa en mode AP; si és menor o igual, en mode CP. Carrega tomaquet-rosa amb 20 unitats i formatge-curat amb 1, parteix la xarxa i fes que l'Anna i en Marc reservin tots dos productes des de rèpliques diferents. Mostra la sortida i explica què s'ha guanyat respecte dels dos modes purs.

Substitueix reconciliar_lww per reconciliar_per_operacions, que en lloc de triar una escriptura calculi l'estoc real com estoc_inicial - reserves_a_bcn - reserves_a_vlc i, si el resultat és negatiu, retorni la llista de reserves que s'han de compensar (les últimes acceptades, per marca de temps). Executa l'escenari AP amb 1 unitat i amb 2 unitats i comenta la diferència amb LWW. Quina informació necessita aquesta reconciliació que LWW no necessitava?

Solució 1:

1. Llista de desitjos: AP / EL. Una llista de desitjos indisponible és una molèstia sense cost, i un article que apareix dues vegades és trivial d'arreglar. Reconciliació per unió (OR-Set, un CRDT de conjunt: mai no es perd un "afegir"; un "treure" només elimina els "afegir" que havia vist).
2. Reserves actives d'un repartidor: CP / EC. El límit de 8 és un invariant del tipus "no descomptar per sota de zero": si dos costats de la partició assignen comandes al mateix repartidor, pot acabar amb 10. Com que és una decisió d'assignació (no de cara al client final), un rebuig temporal és acceptable: la comanda queda "pendent d'assignació" com a l'cas 5 de l'exercici 3 de 02-05.
3. Valoració mitjana: AP / EL. És un agregat estadístic; una dècima d'estrella de diferència entre rèpliques durant uns segons és irrellevant. Reconciliació amb dos GCounter (suma de puntuacions i nombre de vots), que convergeixen sense pèrdua.
4. Estat d'una comanda: CP / EC per a les transicions, encara que amb matís. L'estat avança per una màquina d'estats amb transicions irreversibles (una comanda lliurada no torna a "pagada") i cada transició la fa un únic servei (pagaments marca pagada, repartiment marca lliurada), així que el conflicte real és rar; però dos costats acceptant transicions diferents (cancellada en un, en_repartiment en l'altre) crearien un estat sense sentit. Les escriptures han d'anar al líder de km0_comandes amb quòrum; les lectures de "les meves comandes" poden ser AP amb garanties de sessió.

Solució 2:

(Reanomenant el reservar original a _reservar_amb_mode.) Amb tomaquet-rosa a 20 unitats, totes dues reserves durant la partició s'accepten en mode AP i, en reconciliar per operacions, l'estoc queda a 18 sense sobrevenda; amb formatge-curat a 1, totes dues es rebutgen en mode CP. S'ha guanyat disponibilitat per al 99 % dels productes (que tenen estoc de sobres) mantenint la protecció de l'invariant només quan importa. El cost: la decisió es pren amb l'estoc local, que durant la partició pot ser més gran que el real (l'altre costat ha descomptat sense que ho sapiguem), així que el llindar ha de ser més gran que el nombre de reserves plausibles durant la partició més llarga esperada. És un exemple del que Brewer anomena "gestionar la partició" en lloc de patir-la.

Solució 3:

Primer, reservar ha de conservar la marca de cada reserva acceptada (l'estoc només desa l'última escriptura, així que l'historial cal anotar-lo a part). Canvia el camp de Replica a reserves: list[tuple[int, str, str]] (marca, client, producte) i els dos append a local.reserves.append((self.rellotge, client, producte)) (i, a escenari, la comprensió que llista les reserves passa a for _, c, _ in r.reserves). Després:

Amb 1 unitat: estoc real=-1; a compensar: [('Marc', 'inv-vlc')]. Es conserva la reserva de l'Anna (marca 1), l'estoc queda a 0 i comandes rep l'ordre de cancel·lar la comanda d'en Marc (la compensació d'una saga, 03-05). Amb 2 unitats: estoc real=0; a compensar: []. Davant de LWW, que deixava l'estoc a 0 "per casualitat" i perdia una reserva sense que ningú ho sabés, aquesta reconciliació produeix un estat correcte i una llista explícita de danys a reparar. El que necessita, i LWW no, és l'historial d'operacions de cada costat (no només l'últim valor) i una regla de negoci per decidir a qui compensar. És la diferència entre replicar estats i replicar operacions, que reapareixerà a 03-04.

El teorema CAP, enunciat amb precisió, diu que un sistema distribuït no pot garantir alhora linealitzabilitat i que tot node viu respongui mentre la xarxa està partida; i com que la partició no és opcional tan bon punt hi ha dos nodes i un cable, l'elecció real és què sacrificar durant la partició: CP rebutja les operacions que no pot coordinar, AP les accepta i reconcilia després. Hem desmuntat els malentesos habituals (no se'n "trien dos de tres"; AP no és "sense consistència" sinó sense linealitzabilitat, i admet garanties causals i de sessió; CP no vol dir caiguda total), i hem afegit PACELC per descriure el cost diari de la consistència en latència quan no hi ha partició, amb una taula que classifica PostgreSQL, Cassandra, DynamoDB, MongoDB, Spanner i etcd per configuració. Aplicat a Quilòmetre Zero, el criteri ha estat clar: CP per a allò irreversible o disputat (pagaments, última unitat, lideratge), AP per a allò que es pot unir, corregir o ignorar (cistell, posicions, comptadors, catàleg), amb la subtilesa que una mateixa dada pot canviar de mode segons el seu estat. La simulació ha fet visibles totes dues cares: el mode CP va rebutjar l'Anna i en Marc durant la partició, i el mode AP els va acceptar tots dos i va perdre silenciosament una reserva en reconciliar amb last-write-wins. Les crítiques de Kleppmann i els conceptes de harvest i yield ens recorden que les dues lletres són un punt de partida, no una descripció, i que el que cal documentar són les garanties concretes i les tres fases de la gestió de la partició.

Hem dit diverses vegades que un sistema CP "rebutja les escriptures sense quòrum" i que "el costat amb majoria continua funcionant", com si fos evident com un grup de nodes, amb missatges que es perden i sense rellotge global, decideix quina és la majoria, qui mana i quin valor és el definitiu. No és gens evident: és un dels problemes més difícils de la informàtica distribuïda, resolt per algorismes amb nom propi que Quilòmetre Zero necessitarà, entre altres coses, perquè una sola instància del relay outbox de 02-05 publiqui en cada moment. Aquest problema és el consens, i Paxos i Raft són el tema de la lliçó següent.