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

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

Обзор

Теорему CAP можно сформулировать как «PAC», теорему невозможности , согласно которой ни одно распределенное хранилище данных не может быть одновременно согласованным и доступным в исполнениях, содержащих разделы. Это можно доказать, изучив задержку: если система обеспечивает согласованность, то задержки операций растут с задержками сообщений, и, следовательно, операции не могут в конечном итоге завершиться, если сеть разделена, т. е. система не может гарантировать доступность. [1]

При отсутствии разделов могут быть удовлетворены как согласованность, так и доступность. [2] Поэтому PACELC идет дальше и исследует, как система реплицирует данные. В частности, при отсутствии разделов существует дополнительный компромисс (ELC) между задержкой и согласованностью. [3] Если хранилище атомарно согласовано, то сумма задержки чтения и записи составляет по крайней мере задержку сообщения. На практике большинство систем полагаются на явные подтверждения, а не на временные задержки для обеспечения доставки, требуя полного кругового обхода сети и, следовательно, задержки сообщения как при чтении, так и при записи для обеспечения согласованности. [1] В системах с низкой задержкой, напротив, согласованность ослаблена для уменьшения задержки. [2]

В пространстве PACELC существует четыре конфигурации или компромисса:

  • PA/EL — приоритет доступности и задержки над согласованностью
  • PA/EC — если есть раздел, выбираем доступность; в противном случае выбираем согласованность
  • PC/EL — если есть раздел, выбрать согласованность; в противном случае выбрать задержку
  • PC/EC — выбирайте последовательность всегда

PC/EC и PA/EL предоставляют естественные когнитивные модели для разработчика приложений. Система PC/EC обеспечивает надежную гарантию атомарной согласованности, как в ACID, в то время как PA/EL обеспечивает высокую доступность и низкую задержку с более сложной моделью согласованности. Напротив, системы PA/EC и PC/EL дают только условные гарантии согласованности. Разработчику все равно приходится писать код для обработки случаев, когда гарантия не соблюдается. Системы PA/EC редки за пределами отрасли in-memory data grid, где системы локализованы в географических регионах, а компромисс между задержкой и согласованностью незначителен. [4] PC/EL еще сложнее для понимания. PC не указывает, что система полностью согласована; скорее, она указывает, что система не снижает согласованность за пределами базового уровня согласованности, когда происходит разделение сети — вместо этого она снижает доступность. [3]

Некоторые эксперты, такие как Марк Брукер, утверждают, что теорема CAP особенно актуальна в периодически подключаемых средах, например, связанных с Интернетом вещей (IoT) и мобильными приложениями . В этих контекстах устройства могут стать разделенными из-за сложных физических условий, таких как отключение электроэнергии или при входе в замкнутые пространства, такие как лифты. Для распределенных систем , таких как облачные приложения , более целесообразно использовать теорему PACELC, которая является более всеобъемлющей и учитывает компромиссы, такие как задержка и согласованность, даже при отсутствии сетевых разделов. [5]

История

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

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

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

  • Стандартные версии ранних (внутренних) баз данных Dynamo, Cassandra , Riak и Cosmos DB от Amazon представляют собой системы PA/EL: в случае возникновения раздела они отказываются от согласованности ради доступности, а при нормальной работе они отказываются от согласованности ради меньшей задержки.
  • Полностью ACID-системы, такие как VoltDB / H-Store, Megastore, MySQL Cluster и PostgreSQL , являются PC/EC: они отказываются от согласованности и будут платить за доступность и задержки, чтобы достичь ее. Bigtable и связанные с ними системы, такие как HBase, также являются PC/EC.
  • Amazon DynamoDB (запущен в январе 2012 г.) существенно отличается от раннего (внутреннего) Dynamo, который рассматривался для статьи PACELC. [6] DynamoDB следует модели сильного лидера, где каждая запись строго сериализована (и условные записи не влекут за собой штрафа) и поддерживает согласованность чтения после записи. Эта гарантия не распространяется на «глобальные таблицы [7] » в регионах. 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 — это система ПК/ЭЛ.
  • Hazelcast IMDG и, конечно, большинство сеток данных в памяти являются реализацией системы PA/EC; Hazelcast можно настроить как EL, а не EC. [8] Примитивы параллелизма (Lock, AtomicReference, CountDownLatch и т. д.) могут быть как PC/EC, так и PA/EC. [9]
  • FaunaDB реализует Calvin, протокол транзакций, созданный доктором Дэниелом Абади, автором [3] теоремы PACELC, и предлагает пользователям регулируемые элементы управления для компромисса LC. Это PC/EC для строго сериализуемых транзакций и EL для сериализуемых чтений.
ДДБСП+АП+СЭ+ЛЭ+С
Аэроспайк [10]Датолько платнонеобязательныйДа
Bigtable/HBaseДаДа
КассандраДаДа[а]Да[а]
Космос БДДаДа [б]
Диванная базаДаДаДа
ДинамоДаДа[а]
DynamoDBДаДаДа
ФаунаБД [12]ДаДаДа
Hazelcast IMDG [8] [9]ДаДаДаДа
МегамаркетДаДа
MongoDBДаДа
MySQL-кластерДаДа
ПНУТСДаДа
PostgreSQLДаДаДаДа
РиакДаДа[а]
SpiceDB [13]ДаДаДа
VoltDB/H-StoreДаДа

Смотрите также

Примечания

  1. ^ abcd Dynamo, Cassandra и Riak имеют настраиваемые пользователем параметры для управления компромиссом LC. [6]
  2. ^ Cosmos DB имеет пять выбираемых уровней согласованности для управления компромиссом LC. [11]

Ссылки

  1. ^ abc Golab, Wojciech (2018). «Доказательство PACELC». ACM SIGACT News . 49 (1): 73–81. doi :10.1145/3197406.3197420. S2CID  3989621.
  2. ^ abc Abadi, Daniel J. (2010-04-23). ​​"Размышления о СУБД: Проблемы с CAP и малоизвестная система NoSQL от Yahoo" . Получено 11 сентября 2016 г.
  3. ^ abcde Абади, Дэниел Дж. «Компромиссы согласованности при проектировании современных распределенных систем баз данных» (PDF) . Йельский университет.
  4. ^ Абади, Дэниел (15 июля 2019 г.). «Опасности гарантий условной согласованности». DBMS Musings . Получено 29 августа 2024 г. .
  5. ^ Проектирование приложений с интенсивным использованием данных: Великие идеи, лежащие в основе надежных, масштабируемых и обслуживаемых систем . O'Reilly Media. ISBN 978-1449373320.
  6. ^ abc Abadi, Daniel J.; Murdopo, Arinto (2012-04-17). "Компромиссы согласованности в проектировании современных распределенных систем баз данных" . Получено 2022-07-18 .
  7. ^ "Глобальные таблицы - репликация нескольких регионов для DynamoDB". Документация AWS . Получено 4 января 2023 г.
  8. ^ ab Abadi, Daniel (2017-10-08). "DBMS Musings: Hazelcast и мифическая система PA/EC". DBMS Musings . Получено 20-10-2017 .
  9. ^ ab "Справочное руководство Hazelcast IMDG". docs.hazelcast.org . Получено 17.09.2020 .
  10. ^ Портер, Кевин (29 марта 2023 г.). «Где Aerospike падает в PACELC?». Форум сообщества Aerospike . Получено 30 марта 2023 г.
  11. ^ "Уровни согласованности в Azure Cosmos DB" . Получено 2021-06-21 .
  12. ^ Абади, Дэниел (21.09.2018). «DBMS Musings: Системы баз данных NewSQL не гарантируют согласованность, и я виню в этом Spanner». DBMS Musings . Получено 23.02.2019 .
  13. ^ Зелински, Джимми (2024-04-23). ​​"SpiceDB Concepts: Consistency". Документация SpiceDB . Получено 2024-05-02 .
  • «Компромиссы согласованности в проектировании современных распределенных систем баз данных», Дэниел Дж. Абади, Йельский университет. Оригинальная статья, формализующая PACELC.
  • "Проблемы с CAP и малоизвестная система NoSQL от Yahoo", Дэниел Дж. Абади, Йельский университет. Оригинальная запись в блоге, в которой впервые описан PACELC
  • «Доказательство теоремы PACELC», Войцех Голаб, Университет Ватерлоо Формальное доказательство теоремы PACELC
Получено с "https://en.wikipedia.org/w/index.php?title=PACELC_theorem&oldid=1254051261"