CAP teorem - CAP theorem

I teoretisk informatikk , den CAP teorem , også kalt Brewer teorem etter datamaskin vitenskapsmann Eric Brewer , sier at noen distribuerte datalager kan bare gi to av følgende tre garantier:

Konsistens
Hver lesing mottar den siste skrivingen eller en feil.
Tilgjengelighet
Hver forespørsel mottar et (ikke-feil) svar, uten garanti for at den inneholder den siste skrivingen.
Partisjonstoleranse
Systemet fortsetter å fungere til tross for at et vilkårlig antall meldinger slippes (eller forsinkes) av nettverket mellom noder.

Når en nettverkspartisjonsfeil oppstår, må det avgjøres om det skal

  • avbryte operasjonen og dermed redusere tilgjengeligheten, men sikre konsistens eller til
  • fortsette med operasjonen og dermed gi tilgjengelighet, men risikoinkonsekvens.

Så hvis det er en nettverkspartisjon, må man velge mellom konsistens og tilgjengelighet. Vær oppmerksom på at konsistens som definert i CAP -teoremet er ganske forskjellig fra konsistensen som garanteres i ACID -databasetransaksjoner .

Eric Brewer hevder at det ofte brukte "to av tre" -konseptet kan være noe misvisende fordi systemdesignere bare trenger å ofre konsistens eller tilgjengelighet i nærvær av partisjoner, men at i mange systempartisjoner er sjeldne.

Forklaring

Ingen distribuert system er trygge mot nettverksfeil, derfor må partisjonering av nettverk generelt tolereres. I nærvær av en partisjon sitter den ene igjen med to alternativer: konsistens eller tilgjengelighet . Når du velger konsistens fremfor tilgjengelighet, vil systemet returnere en feil eller en timeout hvis bestemt informasjon ikke kan garanteres å være oppdatert på grunn av nettverkspartisjonering. Når du velger tilgjengelighet fremfor konsistens, vil systemet alltid behandle spørringen og prøve å returnere den siste tilgjengelige versjonen av informasjonen, selv om den ikke kan garantere at den er oppdatert på grunn av nettverkspartisjonering.

CAP blir ofte misforstått som et valg til enhver tid hvorav en av de tre garanterer å forlate. Faktisk er valget mellom konsistens og tilgjengelighet bare når en nettverkspartisjon eller feil oppstår. Når det ikke er noen nettverksfeil, kan både tilgjengelighet og konsistens tilfredsstilles.

CAP har blitt brukt av mange NoSQL -databaseleverandører som en begrunnelse for ikke å gi transaksjonell syre -konsistens, og hevder at CAP -teoremet "beviser" at det er umulig å gi skalerbarhet og ACID -konsistens samtidig. En nærmere titt på CAP -teoremet og spesielt formaliseringen av Gilbert & Lynch avslører imidlertid at CAP -teoremet ikke refererer til skalerbarhet, men bare tilgjengelighet (A i CAP).

Databasesystemer designet med tradisjonelle ACID -garantier i tankene, for eksempel RDBMS, velger konsistens fremfor tilgjengelighet, mens systemer designet rundt BASE -filosofien, som for eksempel er vanlige i NoSQL -bevegelsen, velger tilgjengelighet fremfor konsistens.

Den PACELC teoremet bygger på CAP ved å si at selv i fravær av partisjonering, det er en annen avveining mellom ventetid og konsistens.

Historie

Ifølge University of California, Berkeley datavitenskapsmann Eric Brewer , kom teoremet første gang høsten 1998. Det ble utgitt som CAP -prinsippet i 1999 og presentert som en formodning av Brewer på Symposium on Principles of Distributed Computing (PODC) i 2000 . I 2002 publiserte Seth Gilbert og Nancy Lynch fra MIT et formelt bevis på Brewer's formodning, noe som gjorde det til et teorem .

I 2012 presiserte Brewer noen av sine posisjoner, inkludert hvorfor det ofte brukte "to av tre" -konseptet kan være noe misvisende fordi systemdesignere bare trenger å ofre konsistens eller tilgjengelighet i nærvær av partisjoner; partisjonhåndtering og gjenopprettingsteknikker finnes. Brewer bemerket også den forskjellige definisjonen av konsistens som ble brukt i CAP -teoremet i forhold til definisjonen som ble brukt i ACID .

En lignende teorem om kompromiss mellom konsistens og tilgjengelighet i distribuerte systemer ble utgitt av Birman og Friedman i 1996. Birman og Friedmans resultat begrenset denne nedre grensen til operasjoner uten pendling.

Den Blockchain teknologi ofrer konsistens for tilgjengelighet og skillevegg toleranse, men er oppnådd gjennom validerings blant de noder over tid med den resulterende inntrykk av at teorem er ikke gyldig.

Se også

Referanser

Eksterne linker