C.A.P.-sats

CAP - satsen (även känd som Brewers teorem ) är ett heuristiskt påstående att inte mer än två av följande tre egenskaper kan tillhandahållas i någon implementering av distribuerad beräkning :

Förkortningen CAP i namnet på satsen bildas av de första bokstäverna i de engelska namnen på dessa tre egenskaper.

Principen föreslogs av UC Berkeley- professorn Eric Brewer i juli 2000 [1] [2] och fick därefter stor popularitet och erkännande bland distribuerade datorspecialister [3] [4] . NoSQL - konceptet , inom vilket distribuerade icke- transaktionella databashanteringssystem skapas , använder ofta denna princip som en motivering för det oundvikliga av datakonsistensfel [5] [6] [7] . Men många vetenskapsmän [8] och utövare [9] kritiserar CAP-teoremet för dess lösa tolkning och till och med opålitlighet i den mening som den är vanlig i samhället.

Motiveringar

År 2002 valde Seth Gilbert och Nancy Lynch från Massachusetts Institute of Technology formella modeller för asynkron och synkron distribuerad datoranvändning, som visar uppfyllandet av CAP-teoremet i frånvaro av synkronisering (gemensam klocka) vid noderna i ett distribuerat system och grundläggande möjlighet till en kompromiss i delvis synkrona system [10] . I detta arbete är "konsistens" i betydelsen av CAP-satsen korrelerad med uppfyllandet av de två första kraven på ACID  - atomicitet och konsistens . I framtiden hänvisade många utövare till detta arbete som ett bevis på CAP-teoremet [4] [11] [3] .

Konsekvenser

Ur CAP-teoremets synvinkel faller distribuerade system, beroende på ett par praktiskt stödda egenskaper, av tre möjliga in i tre klasser - CA, CP, AP.

I ett CA-klasssystem är data konsekvent och tillgänglig över alla noder, samtidigt som det offras robusthet för partitionering. Sådana system är möjliga baserade på teknisk programvara som stöder transaktionalitet i betydelsen ACID , exempel på sådana system kan vara lösningar baserade på klustrade databashanteringssystem eller en distribuerad katalogtjänst LDAP [12] .

Ett CP-klasssystem ger i varje ögonblick ett holistiskt resultat och kan fungera under sönderfallsförhållanden, men uppnår detta på bekostnad av tillgänglighet: det kanske inte svarar på en förfrågan. Motståndskraft mot uppdelning i sektioner kräver dubblering av förändringar i alla noder i systemet, i samband med detta noteras den praktiska ändamålsenligheten med att använda distribuerade pessimistiska lås i sådana system för att upprätthålla integriteten [13] .

I ett AP-klasssystem garanteras inte integriteten, men villkoren för tillgänglighet och motstånd mot uppdelning är uppfyllda. Även om system av detta slag har varit kända långt före formuleringen av CAP-principen (till exempel distribuerade webbcacher eller DNS ) [14] , är den växande populariteten för lösningar med denna uppsättning egenskaper associerad just med spridningen av CAP-satsen . De flesta NoSQL-system garanterar alltså i grunden inte dataintegritet, och hänvisar till CAP-teoremet som motivet för en sådan begränsning [5] . Uppgiften med att bygga AP-system är att tillhandahålla någon praktiskt ändamålsenlig nivå av dataintegritet, i denna mening sägs AP-system vara "i slutändan konsekventa " [ 15] eller "svagt konsekventa" ( sv  . weak consistent ) [16] .  

BASE-arkitektur

Under andra hälften av 2000 -talet formulerades ett tillvägagångssätt för att bygga distribuerade system där integritets- och tillgänglighetskraven inte uppfylls fullt ut, kallad BASE -akronymen (från engelskan  Basically Available, Soft-state, Eventually consistent  - basic tillgänglighet, instabil tillstånd, konsistens i slutändan), medan detta tillvägagångssätt står i direkt motsats till ACID [17] . Grundläggande tillgänglighet hänvisar till ett tillvägagångssätt för att designa en applikation så att ett fel i vissa noder leder till ett överbelastningsskydd för endast en liten del av sessionerna samtidigt som tillgängligheten bibehålls i de flesta fall [18] . Flyktiga tillstånd innebär möjligheten att offra långtidslagring av sessionstillstånd (som mellanliggande resultat av val, information om navigering, sammanhang), samtidigt som man koncentrerar sig på att utföra uppdateringar endast för kritiska operationer. Konsistens, vilket i slutändan tolkas som möjligheten till datainkonsekvens i vissa fall, men samtidigt som man säkerställer enighet inom en praktiskt taget överskådlig tid, ägnas en betydande mängd oberoende forskning åt [19] [20] .

Anteckningar

  1. ↑ Brewer, 2000 .
  2. ↑ Gilbert, Lynch, 2002 , Vid PODC 2000, gjorde Brewer, i ett inbjudet föredrag, följande gissningar: det är omöjligt för en webbtjänst att tillhandahålla följande tre garantier: • Konsistens • Tillgänglighet • Partitionstolerans, sid. 55.
  3. ↑ 1 2 White Paper Beat the CAP Theorem  (engelska) ( PDF )  (länk ej tillgänglig) . genedb.com (17 april 2011). Hämtad 7 juni 2011. Arkiverad från originalet 28 juni 2011.
  4. ↑ 1 2 Browne, Julian Brewers CAP-sats  ( 11 januari 2009). Hämtad 7 juni 2011. Arkiverad från originalet 1 augusti 2012.
  5. ↑ 1 2 Brewer, 2010 , Designers av system med breda områden, där nätverkspartitioner anses oundvikliga, vet att de inte kan ha både tillgänglighet och konsistens, och kan därför nu motivera svagare konsistens. Framväxten av "NoSQL"-rörelsen ("Not Only SQL") är ett uttryck för denna frihet, sid. 335.
  6. ↑ Rice, 2011 , Denna gissning är nu allmänt känd som CAP-teoremet och är ett av huvudargumenten till varför traditionella relationsdatabas som ger starka ACID-garantier (atomära transaktioner, transaktionskonsistens och isolering, och datahållbarhetstekniker) inte kan tillhandahålla både partitionen tolerans och tillgänglighet som krävs av storskaliga distribuerade applikationer, sid. 49.
  7. ↑ Kuznetsov, 2011 , En mer seriös "teoretisk" grund för NoSQL-utvecklingen, där de allmänt accepterade användbara egenskaperna hos datahanteringssystem offras för tillgängligheten av dessa system, är det så kallade "CAP-teoremet", som först formulerades av Eric Brewer, sid. 191.
  8. ↑ Kuznetsov, 2011 , jag omger ordet sats inom citattecken, eftersom jag inte kan känna igen påståendet som kallas Brewer som ett sats på grund av avsaknaden av någon tydlig och åtminstone lite formell beskrivning av problemet ... men det är en allmän uppfattning att det betyder omöjligheten att i ett distribuerat datahanteringssystem stödja egenskaperna datakonsistens (Konsistens), tillgänglighet (Tillgänglighet) och motstånd mot nätverksseparation (Partitionering), sid. 191-192.
  9. ↑ Rice, 2011 , Så varför är många av de ledande sociala nätverkssajterna (Facebook, MySpace, Twitter), e-handelswebbplatser (hotellbokningssystem och shoppingsajter) och stora banktillämpningar fortfarande implementerade med traditionella databassystem som MySQL (Facebook, Twitter) eller SQL Server (MySpace, Choice Hotels International, Bank Itau) istället för att använda de nya NoSQL-systemen? … Svaret på hög nivå är att applikationsarkitekturen fortfarande väger samma avvägningar som krävs av CAP-teoremet, sid. femtio.
  10. ↑ Gilbert, Lynch, 2002 , I en asynkron modell, när inga klockor är tillgängliga, är omöjlighetsresultatet ganska starkt: det är omöjligt att tillhandahålla konsekventa data, även att tillåta inaktuella data att returneras när meddelanden går förlorade. Men i delvis synkrona modeller är det möjligt att uppnå en praktisk kompromiss mellan konsekvens och tillgänglighet, sid. 59.
  11. ↑ Grigorik, 2010 , Problemet är att CAP-satsen föreslagen av Eric Brewer och senare bevisad av Seth Gilbert och Nancy Lynch, visar att tillsammans är dessa tre krav omöjliga att uppnå samtidigt.
  12. ↑ Carter, 2011 , Vissa CA-system inkluderar: databaser för singelplats, klusterdatabaser och LDAP.
  13. ↑ Demidov, 2010 , CP (denial of service) är ett tillvägagångssätt med duplicering, strikt ACID-konsistens och synkron replikering av förändringar med den pessimistiska blockeringsmetoden.
  14. ↑ Carter, 2011 , Vissa AP-system inkluderar: Webbcachesystem och Domain Name System (DNS).
  15. ↑ Carter, 2011 , Eventuell konsistens – att utföra en läsoperation kan ge inaktuella data till klienten, men alla skrivningar kommer så småningom att spridas genom hela systemet.
  16. ↑ Grigorik, 2010 , CAP antyder svag konsistens.
  17. ↑ Pritchett, 2008 , Om ACID ger konsistensvalet för partitionerade databaser, hur uppnår man då tillgänglighet istället? Ett svar är BASE (baserat tillgängligt, mjukt tillstånd, så småningom konsekvent). BASE är diametralt motsatt till ACID.
  18. ↑ Pritchett, 2008 , Tillgängligheten av BASE uppnås genom att stödja partiella fel utan totalt systemfel. Här är ett enkelt exempel: om användare är uppdelade på fem databasservrar, uppmuntrar BASE-designen till att skapa operationer på ett sådant sätt att ett användardatabasfel endast påverkar 20 procent av användarna på den specifika värden.
  19. ↑ Stonebreaker, 2010 .
  20. ↑ Vogels, 2008 .

Litteratur