PACELC-sats

Inom teoretisk datavetenskap är PACELC -satsen en förlängning av CAP-satsen . Den anger att vid nätverkspartitionering (P) i ett distribuerat datorsystem måste man välja mellan tillgänglighet (A) och konsistens (C) (enligt CAP-satsen), men annars (E), även när systemet är körs normalt i frånvaro av partitioner måste man välja mellan latens (L) och konsistens (C).

Översikt

PACELC bygger på CAP-satsen . Båda satserna beskriver hur distribuerade databaser har begränsningar och avvägningar vad gäller konsistens, tillgänglighet och partitionstolerans. PACELC går dock längre och konstaterar att det finns en ytterligare kompromiss: mellan latens och konsistens, även i frånvaro av partitioner, vilket ger en mer komplett skildring av de potentiella kompromisserna för konsistens för distribuerade system.

Ett högt tillgänglighetskrav innebär att systemet måste replikera data. Så fort ett distribuerat system replikerar data uppstår en avvägning mellan konsekvens och latens.

PACELC-satsen beskrevs först av Daniel J. Abadi från Yale University 2010 i ett blogginlägg, vilket han senare förtydligade i en artikel 2012. Syftet med PACELC är att ta itu med hans tes att "Ignoring the consistentency/latency trade-off av replikerade system är en stor förbiseende [i CAP], eftersom den är närvarande vid alla tillfällen under systemdrift, medan CAP endast är relevant i det kanske sällsynta fallet med en nätverkspartition." PACELC-satsen bevisades formellt 2018 i en SIGACT News-artikel.

Databas PACELC-betyg

Originaldatabas PACELC-betyg kommer från. Efterföljande uppdateringar bidragit från wikipedia-gemenskapen.

Standardversionerna av Amazons tidiga (interna) Dynamo , Cassandra , Riak och Cosmos DB är PA/EL-system: om en partition uppstår ger de upp konsistens för tillgänglighet, och under normal drift ger de upp konsekvens för lägre latens.
Helt ACID-system som VoltDB /H-Store, Megastore, MySQL Cluster och PostgreSQL är PC/EC: de vägrar att ge upp konsekvens och kommer att betala tillgänglighets- och latenskostnader för att uppnå det. BigTable och relaterade system som HBase är också PC/EC.
Amazon DynamoDB (lanserade i januari 2012) skiljer sig ganska mycket från den tidiga (interna Amazon) Dynamo som övervägdes för PACELC-papperet. DynamoDB följer en stark ledarmodell, där varje skrivning är strikt serialiserad (och villkorliga skrivningar ger inget straff) och stöder läs-efter-skriv-konsistens. Denna garanti gäller inte för "Globala tabeller" över regioner. DynamoDB SDK:erna använder slutligen konsekventa läsningar som standard (förbättrad tillgänglighet och genomströmning), men när en konsekvent läsning begärs kommer tjänsten att returnera antingen en aktuell vy till objektet eller ett fel.
Couchbase tillhandahåller en rad konsistens- och tillgänglighetsalternativ under en partition, och lika många latens- och konsistensalternativ utan partition. Till skillnad från de flesta andra databaser har Couchbase inte en enda API-uppsättning och den skalar/replikerar inte heller alla datatjänster homogent. För skrivningar föredrar Couchbase konsistens framför tillgänglighet vilket gör det formellt CP, men vid läsning finns det mer användarkontrollerad variation beroende på indexreplikering, önskad konsistensnivå och typ av åtkomst (uppslagning av enstaka dokument vs intervallskanning vs fulltextsökning, etc. ). Utöver det finns det sedan ytterligare variabilitet beroende på cross-datacenter-replikering (XDCR) som tar flera CP-kluster och kopplar dem med asynkron replikering och Couchbase Lite som är en inbäddad databas och skapar en helt multi-master (med revisionsspårning) ) distribuerad topologi.
Cosmos DB stöder fem inställbara konsistensnivåer som tillåter avvägningar mellan C/A under P och L/C under E. Cosmos DB bryter aldrig mot den angivna konsistensnivån, så det är formellt CP.
MongoDB kan klassificeras som ett PA/EC-system. I grundfallet garanterar systemet att läsning och skrivning är konsekvent.
PNUTS är ett PC/EL-system.
Hazelcast IMDG och faktiskt de flesta datanät i minnet är en implementering av ett PA/EC-system; Hazelcast kan konfigureras för att vara EL snarare än EC. Samtidighetsprimitiver (Lock, AtomicReference, CountDownLatch, etc.) kan vara antingen PC/EC eller PA/EC.
FaunaDB implementerar Calvin, ett transaktionsprotokoll skapat av Dr Daniel Abadi, författaren till PACELC-teoremet, och erbjuder användarna justerbara kontroller för LC-avvägning. Det är PC/EC för strikt serialiserbara transaktioner och EL för serialiserbara läsningar.

DDBS	P+A	P+C	E+L	E+C
BigTable/HBase
Cassandra
Cosmos DB
Couchbase
Dynamo
DynamoDB
FaunaDB
Hazelcast IMDG
Megastore
MongoDB
MySQL Cluster
PNUTS
PostgreSQL
Riak
VoltDB/H-Store

Se även

Anteckningar

externa länkar

"Consistency Tradeoffs in Modern Distributed Database System Design", av Daniel J. Abadi, Yale University Originaluppsats som formaliserade PACELC
"Problem med CAP, och Yahoos föga kända NoSQL-system", av Daniel J. Abadi, Yale University . Ursprungligt blogginlägg som först beskrev PACELC
"Proving PACELC", av Wojciech Golab, University of Waterloo Formella bevis för PACELC-teoremet