C.A.P.-sætning

CAP - sætningen (også kendt som Brewers sætning ) er et heuristisk udsagn om, at ikke mere end to af følgende tre egenskaber kan leveres i enhver implementering af distribueret databehandling :

Akronymet CAP i navnet på sætningen er dannet ud fra de første bogstaver i de engelske navne på disse tre egenskaber.

Princippet blev foreslået af UC Berkeley professor Eric Brewer i juli 2000 [1] [2] og vandt efterfølgende bred popularitet og anerkendelse blandt distribuerede computerspecialister [3] [4] . NoSQL- konceptet , inden for hvilket distribuerede ikke- transaktionelle databasestyringssystemer skabes , bruger ofte dette princip som en begrundelse for uundgåeligheden af ​​datakonsistensfejl [5] [6] [7] . Imidlertid kritiserer mange videnskabsmænd [8] og praktikere [9] CAP-sætningen for dens løse fortolkning og endda upålidelighed i den forstand, som den er almindelig i samfundet.

Begrundelser

I 2002 udvalgte Seth Gilbert og Nancy Lynch fra Massachusetts Institute of Technology formelle modeller for asynkron og synkron distribueret databehandling, som viser opfyldelsen af ​​CAP-sætningen i fravær af synkronisering (fælles ur) ved knudepunkterne i et distribueret system og grundlæggende mulighed for et kompromis i delvist synkrone systemer [10] . I dette arbejde er "konsistens" i betydningen af ​​CAP-sætningen korreleret med opfyldelsen af ​​de to første krav om ACID  - atomicitet og konsistens . I fremtiden henviste mange praktikere til dette arbejde som et bevis på CAP-sætningen [4] [11] [3] .

Konsekvenser

Fra CAP-sætningens synspunkt falder distribuerede systemer, afhængigt af et par praktisk understøttede egenskaber, ud af tre mulige, i tre klasser - CA, CP, AP.

I et CA-klassesystem er data konsistente og tilgængelige på tværs af alle noder, samtidig med at det ofrer robusthed til partitionering. Sådanne systemer er mulige baseret på teknologisk software, der understøtter transaktionalitet i betydningen ACID , eksempler på sådanne systemer kan være løsninger baseret på clustered database management systemer eller en distribueret directory service LDAP [12] .

Et CP-klasse system giver til enhver tid et holistisk resultat og er i stand til at fungere under henfaldsforhold, men opnår dette på bekostning af tilgængelighed: det reagerer muligvis ikke på en anmodning. Modstandsdygtighed over for opdeling i sektioner kræver duplikering af ændringer i alle systemets noder, i forbindelse hermed bemærkes den praktiske fordelagtighed ved at bruge distribuerede pessimistiske låse i sådanne systemer for at bevare integriteten [13] .

I et AP-klasse system er integriteten ikke garanteret, men betingelserne for tilgængelighed og modstand mod opdeling er opfyldt. Selvom systemer af denne art har været kendt længe før formuleringen af ​​CAP-princippet (f.eks. distribuerede webcaches eller DNS ) [14] , hænger den voksende popularitet af løsninger med dette sæt egenskaber netop sammen med udbredelsen af ​​CAP-sætningen . De fleste NoSQL-systemer garanterer således grundlæggende ikke dataintegritet, og henviser til CAP-sætningen som motivet for en sådan begrænsning [5] . Opgaven i at bygge AP-systemer er at give et praktisk hensigtsmæssigt niveau af dataintegritet, i denne forstand siges AP-systemer at være "efterhånden konsistente " [ 15] eller "svagt konsistente" ( eng  . weak consistent ) [16] .  

BASE arkitektur

I anden halvdel af 2000'erne blev der formuleret en tilgang til at bygge distribuerede systemer, hvor integritets- og tilgængelighedskravene ikke er fuldt opfyldt, kaldet BASE akronymet (fra det engelske  Basically Available, Soft-state, Eventually consistent  - basic available, unstable tilstand, konsistens i sidste ende), mens denne tilgang er direkte i modsætning til ACID [17] . Grundlæggende tilgængelighed refererer til en tilgang til at designe en applikation, således at en fejl i nogle noder kun fører til et lammelsesangreb for en lille del af sessionerne, mens tilgængeligheden opretholdes i de fleste tilfælde [18] . Flygtig tilstand indebærer evnen til at ofre langtidslagring af sessionstilstand (såsom mellemresultater af valg, information om navigation, kontekst), mens man koncentrerer sig om kun at foretage opdateringer til kritiske operationer. Konsistens, som i sidste ende tolkes som muligheden for datainkonsistens i nogle tilfælde, men samtidig med at man sikrer enighed i en praktisk overskuelig tid, er en betydelig mængde uafhængig forskning afsat til [19] [20] .

Noter

  1. ↑ Brewer, 2000 .
  2. ↑ Gilbert, Lynch, 2002 , Ved PODC 2000 fremsatte Brewer i en inviteret tale følgende formodning: Det er umuligt for en webtjeneste at give følgende tre garantier: • Konsistens • Tilgængelighed • Partitionstolerance, s. 55.
  3. ↑ 1 2 White Paper Beat the CAP Theorem  (engelsk) ( PDF )  (link ikke tilgængeligt) . genedb.com (17. april 2011). Hentet 7. juni 2011. Arkiveret fra originalen 28. juni 2011.
  4. ↑ 1 2 Browne, Julian Brewers CAP-sætning  ( 11. januar 2009). Hentet 7. juni 2011. Arkiveret fra originalen 1. august 2012.
  5. ↑ 1 2 Brewer, 2010 , Designere af wide-area-systemer, hvor netværkspartitioner anses for uundgåelige, ved, at de ikke kan have både tilgængelighed og konsistens, og kan derfor nu retfærdiggøre svagere konsistens. Fremkomsten af ​​"NoSQL"-bevægelsen ("Not Only SQL") er et udtryk for denne frihed, s. 335.
  6. ↑ Rice, 2011 , Denne formodning er nu almindeligt kendt som CAP-sætningen og er et af hovedargumenterne for, at traditionel relationsdatabase, der giver stærke ACID-garantier (atomare transaktioner, transaktionskonsistens og isolering, og dataholdbarhedsteknikker) ikke kan levere både partitionen tolerance og tilgængelighed påkrævet af distribuerede applikationer i stor skala, s. 49.
  7. ↑ Kuznetsov, 2011 , Et mere seriøst "teoretisk" grundlag for NoSQL-udviklinger, hvor de generelt accepterede nyttige egenskaber ved datastyringssystemer ofres for tilgængeligheden af ​​disse systemer, er den såkaldte "CAP-sætning", først formuleret af Eric Brygger, s. 191.
  8. ↑ Kuznetsov, 2011 , jeg sætter ordet sætning i anførselstegn, da jeg ikke kan genkende sætningen kaldet Brewer som en sætning på grund af manglen på nogen klar og i det mindste lidt formel erklæring om problemet ... men det er en udbredt opfattelse, at det betyder umuligheden af ​​i ét distribueret datastyringssystem at understøtte egenskaberne datakonsistens (konsistens), tilgængelighed (tilgængelighed) og modstand mod netværksadskillelse (partitionering), s. 191-192.
  9. ↑ Rice, 2011 , Så hvorfor er mange af de førende sociale netværkssider (Facebook, MySpace, Twitter), e-handelswebsteder (hotelreservationssystemer og shoppingwebsteder) og store bankapplikationer stadig implementeret ved hjælp af traditionelle databasesystemer såsom MySQL (Facebook, Twitter) eller SQL Server (MySpace, Choice Hotels International, Bank Itau) i stedet for at bruge de nye NoSQL-systemer? … Svaret på højt niveau er, at applikationsarkitekturen stadig vejer de samme afvejninger, som kræves af CAP-sætningen, s. halvtreds.
  10. ↑ Gilbert, Lynch, 2002 , I en asynkron model, når ingen ure er tilgængelige, er umulighedsresultatet ret stærkt: det er umuligt at levere konsistente data, selv at tillade, at forældede data returneres, når meddelelser går tabt. Men i delvist synkrone modeller er det muligt at opnå et praktisk kompromis mellem konsistens og tilgængelighed, s. 59.
  11. ↑ Grigorik, 2010 , Problemet er, at CAP-sætningen foreslået af Eric Brewer og senere bevist af Seth Gilbert og Nancy Lynch, viser, at disse tre krav tilsammen er umulige at opnå på samme tid.
  12. ↑ Carter, 2011 , Nogle CA-systemer inkluderer: enkeltstedsdatabaser, klyngedatabaser og LDAP.
  13. ↑ Demidov, 2010 , CP (denial of service) er en tilgang med duplikering, streng ACID-konsistens og synkron replikering af ændringer ved hjælp af den pessimistiske blokeringsmetode.
  14. ↑ Carter, 2011 , Nogle AP-systemer inkluderer: Webcachesystemer og Domain Name System (DNS).
  15. ↑ Carter, 2011 , Eventuel konsistens – udførelse af en læseoperation kan give forældede data til klienten, men alle skrivninger vil til sidst forplante sig gennem hele systemet.
  16. ↑ Grigorik, 2010 , CAP impliserer svag konsistens.
  17. ↑ Pritchett, 2008 , Hvis ACID giver konsistensvalget for partitionerede databaser, hvordan opnår man så tilgængelighed i stedet? Et svar er BASE (grundlæggende tilgængelig, blød tilstand, til sidst konsistent). BASE er diametralt modsat ACID.
  18. ↑ Pritchett, 2008 , Tilgængeligheden af ​​BASE opnås ved at understøtte delvise fejl uden total systemfejl. Her er et simpelt eksempel: Hvis brugere er opdelt på tværs af fem databaseservere, tilskynder BASE-designet til at lave operationer på en sådan måde, at en brugerdatabasefejl kun påvirker de 20 procent af brugerne på den pågældende vært.
  19. ↑ Stonebreaker, 2010 .
  20. ↑ Vogels, 2008 .

Litteratur