Twierdzenie PACELC

W informatyce teoretycznej twierdzenie PACELC jest rozszerzeniem twierdzenia CAP . Stwierdza on, że w przypadku partycjonowania sieci (P) w rozproszonym systemie komputerowym trzeba wybierać między dostępnością (A) a spójnością (C) (zgodnie z twierdzeniem CAP), ale inaczej (E), nawet gdy system jest działa normalnie przy braku partycji, trzeba wybrać między opóźnieniem (L) a spójnością (C).

Przegląd

PACELC opiera się na twierdzeniu CAP . Oba twierdzenia opisują, w jaki sposób rozproszone bazy danych mają ograniczenia i kompromisy dotyczące spójności, dostępności i tolerancji partycji. PACELC idzie jednak dalej i stwierdza, że istnieje dodatkowy kompromis: między opóźnieniem a spójnością, nawet w przypadku braku partycji, zapewniając w ten sposób pełniejszy obraz potencjalnych kompromisów w zakresie spójności dla systemów rozproszonych.

Wymóg wysokiej dostępności oznacza, że system musi replikować dane. Gdy tylko system rozproszony replikuje dane, pojawia się kompromis między spójnością a opóźnieniem.

Twierdzenie PACELC zostało po raz pierwszy opisane przez Daniela J. Abadi z Yale University w 2010 roku w poście na blogu, który później wyjaśnił w artykule z 2012 roku. Celem PACELC jest odniesienie się do jego tezy, że „Ignorowanie kompromisu między konsystencją a opóźnieniem replikowanych systemów jest głównym niedopatrzeniem [w CAP], ponieważ jest obecny przez cały czas podczas działania systemu, podczas gdy CAP ma znaczenie tylko w prawdopodobnie rzadkim przypadku partycji sieciowej”. Twierdzenie PACELC zostało formalnie udowodnione w 2018 roku w artykule SIGACT News.

Oceny bazy danych PACELC

Oryginalna baza danych ocen PACELC pochodzi z. Kolejne aktualizacje dostarczane przez społeczność wikipedii.

Domyślne wersje wczesnych (wewnętrznych) Dynamo , Cassandra , Riak i Cosmos DB firmy Amazon to systemy PA/EL: jeśli wystąpi partycja, rezygnują ze spójności na rzecz dostępności, a podczas normalnego działania rezygnują ze spójności na rzecz mniejszych opóźnień.
Systemy w pełni ACID, takie jak VoltDB /H-Store, Megastore, MySQL Cluster i PostgreSQL , to PC/EC: nie chcą rezygnować ze spójności i płacą koszty dostępności i opóźnień, aby to osiągnąć. BigTable i powiązane systemy, takie jak HBase, są również PC/EC.
Amazon DynamoDB (uruchomiony w styczniu 2012 r.) różni się znacznie od wczesnego (wewnętrznego Amazona) Dynamo , które było rozważane w artykule PACELC. DynamoDB stosuje model silnego lidera, w którym każdy zapis jest ściśle serializowany (a zapisy warunkowe nie są karane) i obsługuje spójność odczytu po zapisie. Ta gwarancja nie dotyczy „stołów globalnych” w różnych regionach. Zestawy SDK DynamoDB domyślnie używają ostatecznie spójnych odczytów (poprawiona dostępność i przepustowość), ale gdy zażądany zostanie spójny odczyt, usługa zwróci bieżący widok elementu lub błąd.
Couchbase zapewnia szereg opcji spójności i dostępności podczas partycjonowania, a także szereg opcji opóźnień i spójności bez partycji. W przeciwieństwie do większości innych baz danych, Couchbase nie ma jednego zestawu API ani nie skaluje/replikuje wszystkich usług danych w sposób jednorodny. W przypadku zapisów Couchbase przedkłada Spójność nad Dostępność, czyniąc ją formalnie CP, ale przy odczycie istnieje większa zmienność kontrolowana przez użytkownika w zależności od replikacji indeksu, pożądanego poziomu spójności i rodzaju dostępu (wyszukiwanie pojedynczego dokumentu vs skanowanie zakresu vs wyszukiwanie pełnotekstowe itp. ). Ponadto istnieje dalsza zmienność w zależności od replikacji między centrami danych (XDCR), która bierze wiele klastrów CP i łączy je z replikacją asynchroniczną oraz Couchbase Lite, która jest wbudowaną bazą danych i tworzy w pełni multi-master (ze śledzeniem wersji ) topologia rozproszona.
Cosmos DB obsługuje pięć dostrajanych poziomów spójności, które umożliwiają kompromisy między C/A podczas P i L/C podczas E. Cosmos DB nigdy nie narusza określonego poziomu spójności, więc formalnie jest to CP.
MongoDB można sklasyfikować jako system PA/EC. W przypadku podstawowym system gwarantuje spójność odczytów i zapisów.
PNUTS to system PC/EL.
Hazelcast IMDG i rzeczywiście większość siatek danych w pamięci jest implementacją systemu PA/EC; Hazelcast można skonfigurować jako EL, a nie EC. Prymitywy współbieżności (Lock, AtomicReference, CountDownLatch itp.) mogą być PC/EC lub PA/EC.
FaunaDB implementuje Calvin, protokół transakcyjny stworzony przez dr Daniela Abadi, autora twierdzenia PACELC, i oferuje użytkownikom możliwość dostosowania kontroli kompromisu LC. Jest to PC/EC dla ściśle serializowalnych transakcji i EL dla odczytów możliwych do serializacji.

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

Zobacz też

Notatki

Linki zewnętrzne

„Consistency Tradeoffs in Modern Distributed Database System Design”, Daniel J. Abadi, Yale University Oryginalny artykuł, który sformalizował PACELC
„Problemy z CAP i mało znanym systemem NoSQL Yahoo”, Daniel J. Abadi, Yale University . Oryginalny post na blogu, w którym po raz pierwszy opisano PACELC
„Proving PACELC”, Wojciech Golab, University of Waterloo Formalny dowód twierdzenia PACELC