CAP-stelling

All lectures for NL purposes
Niveau 1 , Les 885
Beschikbaar

4.1 Consistentie over Brewera

Om te beginnen is Eric Brewer geen database-expert en heeft hij dat ook nooit beweerd. Hij behoort tot de gemeenschap van gedistribueerde systemen, en zijn beroemde lezing, waarin de CAP "stelling" verscheen, werd gegeven op de conferentie "Principles of Distributed Computing". (Tussen haakjes, tien jaar later, in 2010, hield hij opnieuw een uitgenodigde lezing op dezelfde conferentie, en in deze toespraak gaf hij met name een aantal voorbeelden van gedistribueerde systemen, waarvan de ontwikkeling rekening hield met de " stelling" van CAP.) In dit gebied heeft zijn eigen interpretatie van de termen die worden gebruikt op het gebied van databases.

In het bijzonder betekent de term "onmiddellijke consistentie" dat nadat de gebruiker een melding van het systeem heeft ontvangen over de succesvolle voltooiing van een bepaalde gegevensupdatebewerking, het resultaat van deze bewerking onmiddellijk zichtbaar wordt voor alle waarnemers.

Uiteindelijke consistentie betekent dat als er gedurende een voldoende lange periode geen nieuwe gegevensupdatebewerkingen het systeem binnenkomen, kan worden verwacht dat de resultaten van alle eerdere gegevensupdatebewerkingen zich uiteindelijk zullen verspreiden naar alle knooppunten van het systeem, en dat alle replicagegevens zijn consistent (blijkbaar moet dit worden opgevat als "alle replica's hebben dezelfde status".

Met dit gevoel van consistentie in gedachten kan de "stelling" van Brewer als redelijk begrijpelijk en voor de hand liggend worden beschouwd: in elk gedistribueerd systeem met gedeelde gegevens kunnen slechts twee eigenschappen van consistentie, beschikbaarheid en partitietolerantie van het netwerk tegelijkertijd worden gegarandeerd. In dit opzicht contrasteert Brewer zelfs de reeks ACID-eigenschappen met zijn voorgestelde reeks BASE-eigenschappen (Basis Beschikbaar, Soft-state, Uiteindelijke consistentie - beschikbaarheid in de meeste gevallen; onstabiele toestand; uiteindelijke consistentie). Maar deze oppositie is naar mijn mening ongerechtvaardigd, aangezien we het in het eerste geval hebben over de logische kenmerken van transacties en in het tweede geval over de fysieke eigenschappen van gedistribueerde systemen.

4.2 Bewijs van de "stelling"

Velen geloven dat de "stelling" van Brewer formeel bewezen is. Inderdaad, het artikel van Seth Gilbert en Nancy Lynch introduceert enkele (bijna) formele definities waarin de "stelling" echt een stelling wordt en wordt bewezen. Laten we echter eens kijken hoe die drie eigenschappen van een gedistribueerd systeem worden bepaald, waarvan volgens de "stelling" van Brewer slechts twee eigenschappen tegelijkertijd kunnen worden ondersteund.

Consistentie wordt atomaire of lineariseerbare consistentie (atomaire of lineariseerbare consistentie) genoemd, wat een eigenschap is van het systeem, waarvan alle individuele gegevensobjecten atomair (lineariseerbaar) zijn. Een atomair object is op zijn beurt een object met verschillende bewerkingen, zodat de oproep van de bewerking en de ontvangst van antwoordgegevens als ogenblikkelijk plaatsvinden, d.w.z. het object accepteert de oproep van de volgende bewerking pas als de vorige bewerking volledig is voltooid. De volgorde waarin bewerkingen worden ontvangen, moet zodanig zijn dat als een leesbewerking arriveert nadat een schrijfbewerking is uitgevoerd, de leesbewerking de waarde moet retourneren die door deze of een latere schrijfbewerking is geschreven.

Een gedistribueerd systeem is altijd beschikbaar als elk verzoek dat door een niet-mislukte node wordt ontvangen, moet worden beantwoord. De veerkracht van het systeem tegen netwerkpartitie wordt gemodelleerd als het behoud van de levensvatbaarheid van het systeem in het geval van het verlies van een willekeurig aantal berichten dat van het ene knooppunt naar het andere wordt verzonden.

Op basis van deze definities formuleren Hilbert en Lynch de volgende stelling (er is geen klok in het asynchrone netwerkmodel en knooppunten zouden alleen beslissingen moeten nemen op basis van ontvangen berichten en lokale berekeningen):

In een asynchroon netwerkmodel is het niet mogelijk om een ​​lees/schrijf-gegevensobject te implementeren dat beschikbaarheid en atomaire consistentie-eigenschappen garandeert voor alle geldige uitvoeringen (inclusief die waarbij berichten verloren gaan).

Deze stelling wordt eigenlijk heel eenvoudig formeel bewezen door de methode "door tegenspraak". Het artikel concludeert verder dat:

In een asynchroon netwerkmodel is het niet mogelijk om een ​​lees/schrijf-dataobject te implementeren dat toegankelijkheidseigenschappen garandeert voor alle geldige uitvoeringen en atomaire consistentie voor geldige uitvoeringen waarbij berichten niet verloren gaan.

Bovendien wordt de waarheid van de hoofdstelling bewezen voor een gedeeltelijk synchroon netwerkmodel, waarin elk knooppunt een klok heeft, waarvan de getoonde tijd met dezelfde snelheid toeneemt, maar die niet gesynchroniseerd zijn, d.w.z. kan verschillende tijden op hetzelfde echte moment weergeven. Er wordt aangetoond dat voor dit geval een soortgelijk gevolg niet wordt afgeleid, en daarom zijn er voor gedeeltelijk synchrone netwerken meer mogelijkheden om gedistribueerde systemen met "goede" eigenschappen te organiseren.

Ja, in zekere zin (niet noodzakelijkerwijs hetzelfde als de bedoeling van Brewer) kan worden aangenomen dat Gilbert en Lynch hebben bewezen dat het onmogelijk is om tegelijkertijd de eigenschappen van atomaire consistentie, beschikbaarheid en partitietolerantie van een netwerk in een enkel gedistribueerd systeem te waarborgen. Maar wat heeft dit te maken met databasetransacties in het algemeen en ACID-transacties in het bijzonder?

4.3 ACID-transacties

Dit is wat Julian Browne hierover schrijft in zijn notitie over de bespreking van de "stelling" van CAP:

In hun bewijs gebruiken Hilbert en Lynch de term atomiciteit in plaats van consistentie, wat vanuit technisch oogpunt logischer is omdat consistentie in de zin van ACID strikt genomen verwijst naar de ideale eigenschappen van databasetransacties en betekent dat geen gegevens persistent worden als ze een aantal vooraf vastgestelde beperkingen schenden. Maar als we aannemen dat een vooraf vastgestelde beperking van gedistribueerde systemen het verbod is op de aanwezigheid van verschillende waarden voor hetzelfde gegevenselement, dan kan naar mijn mening deze fout in de abstractie van consistentie worden overwogen onbeduidend (bovendien, als Brewer de term atomiciteit zou gebruiken, zou de AAP-stelling verschijnen, waarvan de naam buitengewoon onhandig zou zijn om uit te spreken).

Dit is niet erg serieus geschreven, maar eerlijk gezegd. En in feite mag de eis van atomaire consistentie niet worden vermengd met de eis van transactionele consistentie in de zin van ACID. Beperkingen op de database-integriteit zijn logisch, zo u wilt, zakelijke vereisten. Ze komen uit de logica van het toepassingsdomein. De eis van atomaire consistentie is van een heel ander soort. Dit is een implementatievereiste die valt in de categorie die traditioneel in de database-industrie wordt aangeduid als fysieke consistentie (bijvoorbeeld bij het uitvoeren van een indexwijzigingsoperatie moeten alle blokken van de overeenkomstige B+-boom geldige waarden bevatten en gekoppeld zijn door geldige referenties ).

En dit is wat vertegenwoordigers van de databasegemeenschap Daniel Abadi en Alexander Thomson vrij serieus schrijven in hun notitie:

... de behoefte aan beschikbaarheid van schaalbare transactiesystemen wordt steeds belangrijker, en hieraan wordt meestal voldaan door replicatie en automatische omleiding van verzoeken in het geval van een storing van een van de knooppunten. Daarom verwachten applicatieontwikkelaars dat de consistentiegaranties van ACID-systemen (oorspronkelijk bestaande uit lokale ondersteuning voor door de gebruiker gedefinieerde invarianten) zullen worden uitgebreid om een ​​sterke consistentie te garanderen (dat alle replica's van dezelfde gegevens op elk moment identieke kopieën zullen zijn, d.w.z. in deze casusconsistentie wordt geïmpliceerd in de zin van CAP/PACELC.

Met andere woorden, Brewer-consistentie heeft niets te maken met consistentie in de zin van ACID, maar het is in systemen die zijn gericht op het bieden van hoge beschikbaarheid door gegevensreplicatie dat het wenselijk is om een ​​sterke replica-consistentie te behouden. Dit is geen ACID-eigenschap, maar een technisch (fysiek) kenmerk van massaal parallel DBMS dat applicatie-ontwikkeling vergemakkelijkt.

Volgens Michael Stonebreaker is de sleutel tot het bouwen van een modern DBMS van hoge kwaliteit de juiste keuze van technische compromissen. Bij het kiezen van een specifieke technische oplossing moet met veel factoren rekening worden gehouden - de eisen van toekomstige gebruikers, de waarschijnlijkheid van verschillende storingssituaties, enz.

Stonebreaker is van mening dat op het gebied van transactionele parallelle databasesystemen het opgeven van de consistentie van Brewer ten gunste van ondersteuning van hoge beschikbaarheid en netwerkpartitietolerantie een slechte afweging is, omdat (a) replica-consistentie een zeer nuttige eigenschap van het systeem is; (b) massaal parallelle DBMS voor transacties hebben geen clusters met een zeer groot aantal knooppunten nodig, dus situaties met netwerksplitsing zijn onwaarschijnlijk; (c) het systeem kan gemakkelijk onbeschikbaar worden, niet door een netwerkpartitie, maar bijvoorbeeld door de aanwezigheid van regelmatig voorkomende softwarefouten.

De hoge activiteit van vertegenwoordigers van het NoSQL-kamp (lees NoACID), die vaak verwijzen naar de "stelling" van Brewer, houdt dus geen verband met de theoretische onmogelijkheid om massaal parallelle transactionele DBMS te bouwen die ACID-transacties ondersteunen, maar met het feit dat vereenvoudigde systemen die niet alleen ACID-transacties ondersteunen, maar ook replica-consistentie, worden gemakkelijker en sneller gemaakt. Door hun simplistische organisatie zijn ze in staat tot zeer snelle gegevensverwerking, en voor sommige toepassingen is dit belangrijker dan alle gemakken die inherent zijn aan databasetechnologie.

Laten we eens kijken hoe de databasegemeenschap op deze uitdaging reageert.

Opmerkingen
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION