Теорема PACELC

В теории баз данных теорема PACELC является расширением теоремы CAP . В нем говорится, что в случае разделения сети (P) в распределенной компьютерной системе приходится выбирать между доступностью (A) и согласованностью (C) (согласно теореме CAP), а в остальном (E), даже если система нормально работая при отсутствии разделов, приходится выбирать между задержкой (L) и потерей согласованности (C).

Обзор

PACELC основывается на теореме CAP . Обе теоремы описывают, как распределенные базы данных имеют ограничения и компромиссы в отношении согласованности, доступности и устойчивости к разделению. PACELC идет дальше и утверждает, что существует дополнительный компромисс : между задержкой и потерей согласованности, даже при отсутствии разделов, что обеспечивает более полное представление о потенциальных компромиссах согласованности для распределенных систем. ^[1]

Требование высокой доступности подразумевает, что система должна реплицировать данные. Как только распределенная система реплицирует данные, возникает компромисс между согласованностью и задержкой.

Теорема PACELC была впервые описана Дэниелом Абади из Йельского университета в 2010 году в сообщении в блоге: ^[2] что он позже пояснил в статье в 2012 году. ^[1] Целью PACELC является рассмотрение его тезиса о том, что «Игнорирование компромисса между согласованностью и задержкой реплицируемых систем является серьезным упущением [в CAP], поскольку оно присутствует всегда во время работы системы, тогда как CAP актуален только в спорных случаях». редкий случай сетевого раздела». Теорема PACELC была формально доказана в 2018 году в статье SIGACT News. ^[3]

База данных рейтингов PACELC

^[1]Из оригинальной базы данных рейтингов PACELC. ^[4] Последующие обновления предоставлены сообществом Википедии.

Версии от Amazon ранних (внутренних) Dynamo , Cassandra , Riak и Cosmos DB по умолчанию представляют собой системы PA/EL: при возникновении разделения они отказываются от согласованности ради доступности, а при нормальной работе они отказываются от согласованности ради меньшей задержки.
Полностью ACID-системы, такие как VoltDB /H-Store, Megastore, MySQL Cluster и PostgreSQL , являются PC/EC: они отказываются отказываться от согласованности и готовы платить за ее доступность и задержку. Bigtable и связанные с ней системы, такие как HBase, также являются PC/EC.
Amazon DynamoDB (запущенный в январе 2012 г.) сильно отличается от ранней (внутренней версии Amazon) Dynamo, которая рассматривалась в статье PACELC. ^[4] DynamoDB следует модели сильного лидера, в которой каждая запись строго сериализована (и условные записи не несут никаких штрафов) и поддерживает согласованность чтения после записи. Эта гарантия не распространяется на «Глобальные таблицы». ^[5]" в разных регионах. Пакеты SDK DynamoDB по умолчанию используют согласованное чтение (повышенная доступность и пропускная способность), но когда запрашивается согласованное чтение, служба возвращает либо текущее представление элемента, либо ошибку.
Couchbase предоставляет ряд вариантов согласованности и доступности во время раздела, а также ряд вариантов задержки и согласованности без разделения. В отличие от большинства других баз данных, Couchbase не имеет единого набора API и не масштабирует/реплицирует все службы данных однородно. При записи Couchbase отдает предпочтение согласованности, а не доступности, что формально делает его CP, но при чтении существует больше управляемой пользователем изменчивости в зависимости от репликации индекса, желаемого уровня согласованности и типа доступа (поиск отдельного документа, сканирование диапазона, полнотекстовый поиск и т. д.). ). Кроме того, существует дополнительная вариативность в зависимости от репликации между центрами обработки данных (XDCR), которая использует несколько кластеров CP и соединяет их с помощью асинхронной репликации, и Couchbase Lite, которая представляет собой встроенную базу данных и создает полностью мультимастерную (с отслеживанием изменений) ) распределенная топология.
Cosmos DB поддерживает пять настраиваемых уровней согласованности, которые позволяют находить компромисс между C/A во время P и L/C во время E. Cosmos DB никогда не нарушает указанный уровень согласованности, поэтому формально это CP.
MongoDB можно классифицировать как систему PA/EC. В базовом случае система гарантирует согласованность операций чтения и записи.
PNUTS — это система ПК/EL.
Hazelcast IMDG и большинство таблиц данных в памяти представляют собой реализацию системы PA/EC; Hazelcast можно настроить как EL, а не EC. ^[6] Примитивы параллелизма (Lock, AtomicReference, CountDownLatch и т. д.) могут быть либо PC/EC, либо PA/EC. ^[7]
FaunaDB реализует Calvin, протокол транзакций, созданный доктором Дэниелом Абади, автором. ^[1] теоремы PACELC и предлагает пользователям настраиваемые элементы управления для компромисса LC. Это PC/EC для строго сериализуемых транзакций и EL для сериализуемых операций чтения.

ДДБС	П+К	Э+Л
Аэроспайк ^[8]	заплатил только	необязательный
Bigtable/HBase
Кассандра		^[а]
Космос БД		^[б]
Коучбейс
Динамо		^[а]
ДинамоДБ
ФаунаБД ^[10]
Хейзелкаст IMDG ^[6]^[7]
Мегамаркет
МонгоБД
Кластер MySQL
ПНУТС
PostgreSQL
Пульсация		^[а]
SpiceDB ^[11]
VoltDB/H-магазин

См. также

Примечания

^ Jump up to: ^а ^б ^с Dynamo, Cassandra и Riak имеют настраиваемые пользователем настройки для управления компромиссом LC. ^[4]
^ Cosmos DB имеет пять выбираемых уровней согласованности для управления компромиссом LC. ^[9]

Ссылки

^ Jump up to: ^а ^б ^с ^д Абади, Дэниел Дж. «Компромиссы согласованности при проектировании современных систем распределенных баз данных» (PDF) . Йельский университет.
^ Абади, Дэниел Дж. (23 апреля 2010 г.). «Размышления о СУБД: проблемы с CAP и малоизвестной системой NoSQL Yahoo» . Проверено 11 сентября 2016 г.
^ Голаб, Войцех (2018). «Доказательство PACELC» . Новости ACM SIGACT . 49 (1): 73–81. дои : 10.1145/3197406.3197420 . S2CID 3989621 .
^ Jump up to: ^а ^б ^с Абади, Дэниел Дж.; Мурдопо, Аринто (17 апреля 2012 г.). «Компромиссы согласованности в современном проектировании систем распределенных баз данных» . Проверено 18 июля 2022 г.
^ «Глобальные таблицы — репликация нескольких регионов для DynamoDB» . Документация АВС . Проверено 4 января 2023 г.
^ Jump up to: ^а ^б Абади, Дэниел (08 октября 2017 г.). «Размышления о СУБД: Hazelcast и мифическая система PA/EC» . Размышления о СУБД . Проверено 20 октября 2017 г.
^ Jump up to: ^а ^б «Справочное руководство Hazelcast IMDG» . docs.hazelcast.org . Проверено 17 сентября 2020 г.
^ Портер, Кевин (29 марта 2023 г.). «Где находится аэроспайк в PACELC?» . Форум сообщества Aerospike . Проверено 30 марта 2023 г.
^ «Уровни согласованности в Azure Cosmos DB» . Проверено 21 июня 2021 г.
^ Абади, Дэниел (21 сентября 2018 г.). «Размышления о СУБД: системы баз данных NewSQL не могут гарантировать согласованность, и я виню в этом Спаннера» . Размышления о СУБД . Проверено 23 февраля 2019 г.
^ Зелински, Джимми (23 апреля 2024 г.). «Концепции SpiceDB: согласованность» . Документация SpiceDB . Проверено 2 мая 2024 г.

Внешние ссылки

«Компромиссы согласованности в современном проектировании систем распределенных баз данных», Дэниел Дж. Абади, Йельский университет. Оригинальная статья, формализовавшая PACELC.
«Проблемы с CAP и малоизвестной системой NoSQL Yahoo», Дэниел Дж. Абади, Йельский университет . Исходное сообщение в блоге, в котором впервые описывается PACELC
«Доказательство PACELC», Войцех Голаб, Университет Ватерлоо. Формальное доказательство теоремы PACELC.

[lctradeoff-9] Jump up to: ^а ^б ^с Dynamo, Cassandra и Riak имеют настраиваемые пользователем настройки для управления компромиссом LC. ^[4]

[csmsclvl-11] Cosmos DB имеет пять выбираемых уровней согласованности для управления компромиссом LC. ^[9]

[Abadi-1] Jump up to: ^а ^б ^с ^д Абади, Дэниел Дж. «Компромиссы согласованности при проектировании современных систем распределенных баз данных» (PDF) . Йельский университет.

[2] Абади, Дэниел Дж. (23 апреля 2010 г.). «Размышления о СУБД: проблемы с CAP и малоизвестной системой NoSQL Yahoo» . Проверено 11 сентября 2016 г.

[Golab-3] Голаб, Войцех (2018). «Доказательство PACELC» . Новости ACM SIGACT . 49 (1): 73–81. дои : 10.1145/3197406.3197420 . S2CID 3989621 .

[ctmddsd-4] Jump up to: ^а ^б ^с Абади, Дэниел Дж.; Мурдопо, Аринто (17 апреля 2012 г.). «Компромиссы согласованности в современном проектировании систем распределенных баз данных» . Проверено 18 июля 2022 г.

[5] «Глобальные таблицы — репликация нескольких регионов для DynamoDB» . Документация АВС . Проверено 4 января 2023 г.

[dbmsmusings201710-6] Jump up to: ^а ^б Абади, Дэниел (08 октября 2017 г.). «Размышления о СУБД: Hazelcast и мифическая система PA/EC» . Размышления о СУБД . Проверено 20 октября 2017 г.

[:0-7] Jump up to: ^а ^б «Справочное руководство Hazelcast IMDG» . docs.hazelcast.org . Проверено 17 сентября 2020 г.

[8] Портер, Кевин (29 марта 2023 г.). «Где находится аэроспайк в PACELC?» . Форум сообщества Aerospike . Проверено 30 марта 2023 г.

[10] «Уровни согласованности в Azure Cosmos DB» . Проверено 21 июня 2021 г.

[12] Абади, Дэниел (21 сентября 2018 г.). «Размышления о СУБД: системы баз данных NewSQL не могут гарантировать согласованность, и я виню в этом Спаннера» . Размышления о СУБД . Проверено 23 февраля 2019 г.

[13] Зелински, Джимми (23 апреля 2024 г.). «Концепции SpiceDB: согласованность» . Документация SpiceDB . Проверено 2 мая 2024 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[а]

[б]

[10]

[11]

[9]