YaChudo

Теорема CAP

Переглядів: 0. Оновлено 24.10.2026.

Теорема CAP (від англ. Consistency, Availability, Partition tolerance; також теорема Брюера, за ім'ям Еріка Брюера) — твердження з теорії розподілених обчислень про принципову межу можливостей систем, які зберігають спільні дані на кількох вузлах. У формалізації Сета Гілберта та Ненсі Лінч (2002) за умов довільного розділення мережі неможливо одночасно гарантувати узгодженість у сенсі лінеаризовності й доступність кожного справного вузла для операцій над спільними даними.[1]

Традиційно назву CAP розшифровують як три бажані властивості: consistency (C, узгодженість), availability (A, доступність) і partition tolerance (P, стійкість до розділення мережі). Популярне формулювання «можна вибрати лише дві властивості з трьох» є спрощенням: принципове обмеження проявляється саме під час порушення зв'язку між вузлами; без такого порушення система може забезпечувати і C, і A.[2][3]

Визначення властивостей

Узгодженість (C)

Узгодженість у формальній теоремі відповідає атомарній узгодженості операцій читання та запису, або лінеаризовності: усі операції мають виглядати так, ніби вони виконуються над однією копією даних і кожна набуває чинності в певний момент між початком та завершенням. Зокрема, читання, розпочате після успішного завершення запису, повинне повертати записане значення або результат пізнішого запису.[1]

Це не означає, що фізичні копії даних на всіх вузлах завжди збігаються: система може мати застарілі репліки, але не допускати, щоб операції з ними порушували гарантовану клієнтові модель узгодженості. Також лінеаризовність не слід ототожнювати з послідовною узгодженістю або узгодженістю транзакцій в ACID.[3][2]

Доступність (A)

У доведенні Гілберта та Лінч доступність означає, що кожен запит, отриманий вузлом, який не зазнав відмови, зрештою завершується коректною відповіддю. Відмова в обслуговуванні або нескінченне очікування не задовольняють цю вимогу. Водночас це теоретичне визначення саме по собі не встановлює верхньої межі часу відповіді; отже, воно відрізняється від практичного показника доступності вебслужби, який зазвичай враховує час простою, помилки та обмеження часу очікування.[1][3]

Стійкість до розділення (P)

Розділення мережі (англ. network partition) виникає, коли частина вузлів не може обмінюватися повідомленнями з іншою частиною, хоча самі вузли продовжують працювати. Стійкість до розділення означає, що система має визначену поведінку та виконує обрані гарантії навіть за втрати повідомлень між частинами мережі. Вона не означає, що всі операції обов'язково залишаться доступними: це вже окрема властивість A.[1][3]

Суть теореми

Для доведення достатньо розглянути два вузли з копіями одного значення. Нехай спочатку на обох вузлах зберігається 0, після чого зв'язок між ними обривається. Клієнт успішно записує значення 1 на першому вузлі й тільки після завершення запису звертається із запитом читання до другого вузла. Оскільки повідомлення між вузлами не проходять, другий вузол не може дізнатися, чи відбувся запис. Якщо він поверне старе значення 0, буде порушено лінеаризовність; якщо відмовиться відповідати або чекатиме на відновлення зв'язку, буде порушено вимогу доступності. Отже, обидві гарантії для всіх допустимих сценаріїв розділення мережі неможливі.[1]

Теорема є твердженням про неможливість одночасних гарантій, а не про те, що під час кожного реального збою дані неодмінно стануть неузгодженими або сервіс неодмінно перестане відповідати. Вибір також може залежати від конкретної операції, об'єкта даних чи частини системи.[2]

Інтерпретація CA, CP та AP

Скорочення CA, CP та AP використовують для опису типових архітектурних компромісів. Проте вважати їх трьома вичерпними й незмінними класами розподілених баз даних некоректно: значення мають конкретні гарантії операцій, спосіб оброблення мережевих відмов і налаштування системи.[3][2]

CA — узгодженість і доступність

CA характеризує систему, яка підтримує C та A, якщо розділень мережі немає або їх виключено з моделі відмов. За довільного розділення не можна гарантувати обидві властивості для доступних з різних боків реплік. Одновузлова база даних може ілюструвати відсутність цього компромісу між кількома репліками, але не є прикладом стійкої до розділень розподіленої системи. Реляційні бази даних як клас не можна автоматично зараховувати до CA: реляційна модель і підтримка ACID самі по собі не визначають реакції на розділення мережі.[3][2]

CP — узгодженість за можливого обмеження доступності

У системі, що віддає перевагу C під час розділення, частина запитів може бути відхилена або заблокована, аби не допустити порушення лінеаризовності. Прикладом є сховище ключів і значень etcd, яке використовує протокол консенсусу Raft: після розділення кластеру його сторона з більшістю учасників може продовжити роботу, а сторона з меншістю стає недоступною для операцій, що потребують консенсусу.[4]

Термін «недоступна» у значенні CAP не обов'язково означає повну зупинку програми: наприклад, окремі локальні або нестрогі читання можуть залишатися можливими, якщо для них не обіцяно лінеаризовності.[3]

AP — доступність за слабших гарантій узгодженості

Системи, орієнтовані на A під час розділення, можуть приймати операції в ізольованих частинах мережі без очікування їх синхронізації. Це допускає тимчасову розбіжність між репліками. За моделі «узгодженості зрештою» (англ. eventual consistency) репліки сходяться до одного стану, якщо нові зміни припиняються, а необхідні оновлення згодом доставляються. Тому такі системи не можуть одночасно гарантувати лінеаризовність для всіх операцій. Проте слабша узгодженість не тотожна пошкодженню даних: системи можуть підтримувати інші моделі узгодженості, вести історію версій і узгоджувати зміни після відновлення зв'язку.[2]

Відомий приклад — розроблене в Amazon сховище Dynamo, спроєктоване для високої доступності. У ньому використовувалися версіонування об'єктів і механізми розв'язання конфліктів; за деяких відмов узгодженість послаблювалася заради можливості продовжити обслуговування.[5]

У Apache Cassandra гарантії читання і запису можна задавати для кожної операції окремо, зокрема вказуючи кількість реплік, від яких потрібно отримати підтвердження. Тому навіть систему, яку зазвичай описують як AP, не завжди коректно відносити до одного режиму незалежно від параметрів запиту.[6]

Практичні наслідки та обмеження

Затримки, тайм-аути й відновлення зв'язку

На практиці вузол часто не може відразу визначити, чи зв'язок з іншим вузлом втрачений, чи повідомлення лише затримується. Коли спливає час очікування, система має вирішити, чи припинити або відкласти операцію для збереження узгодженості, чи виконати її без зв'язку з іншими репліками, допускаючи слабшу узгодженість. Після відновлення мережі можуть знадобитися синхронізація версій, виявлення конфліктів і погодження розбіжних змін.[2]

Серед практичних підходів — робота з більшістю реплік (кворумом), вибір рівня узгодженості для окремих запитів, відкладене поширення оновлень і примирення конфліктів. Застосовність конкретного механізму залежить від моделі даних та гарантій системи.[5][6]

Для деяких типів даних можливе злиття паралельних оновлень без централізованого погодження. Такі структури, відомі як CRDT (англ. conflict-free replicated data types), за визначених умов забезпечують збіжність реплік після обміну оновленнями. Це не скасовує CAP: збіжність після відновлення зв'язку відрізняється від лінеаризовності під час розділення.[7]

Відмінність від ACID

Літера C у ACID означає, що транзакція зберігає правила цілісності бази даних, наприклад обмеження допустимих значень або унікальність ключів. Літера C у CAP стосується видимої поведінки операцій над реплікованими даними. Так само A в ACID означає атомарність транзакцій, а A в CAP — доступність відповідей. Тому висновок «ACID = CA» є помилковим.[2]

Теорема PACELC

У 2010 році модель PACELC запропонував Деніел Абаді; у 2012 році він описав її в науковій статті. Вона підкреслює, що за наявності розділення мережі (P) постає вибір між доступністю (A) та узгодженістю (C), а за звичайної роботи (E, англ. else) — часто між затримкою відповіді (L, англ. latency) та узгодженістю (C). Це доповнює CAP компромісом, який виникає не тільки під час мережевих відмов.[8][9]

Історія

Ще 1996 року Рой Фрідман і Кен Бірман опублікували дослідження Trading Consistency for Availability in Distributed Systems, у якому встановили обмеження на одночасне виконання певних некомутативних операцій у розділених частинах системи із серіалізовною поведінкою.[10]

За спогадами Еріка Брюера, ідея CAP сформувалася восени 1998 року. Споріднені міркування він разом з Армандо Фоксом виклав у публікації 1999 року про масштабовані відмовостійкі системи, а в 2000 році представив гіпотезу в доповіді Towards Robust Distributed Systems на симпозіумі ACM з принципів розподілених обчислень (PODC).[2][11][12]

У 2002 році Сет Гілберт і Ненсі Лінч опублікували формальне доведення гіпотези в моделі асинхронної мережі та розглянули її співвідношення з частково синхронними моделями. Після цього твердження стало відоме як теорема CAP.[1]

У 2012 році Брюер докладніше пояснив, чому формула «два з трьох» вводить в оману: за відсутності розділення системі не потрібно відмовлятися від узгодженості або доступності, а різні операції однієї системи можуть мати різні компроміси. Він запропонував приділяти більше уваги виявленню розділень, роботі під час них та відновленню.[2]

У 2015 році Мартін Клеппманн оприлюднив працю A Critique of the CAP Theorem, у якій звернув увагу на неоднозначності формальних визначень, обмежену практичну придатність простого поділу CA/AP/CP та важливість аналізу затримок мережі. Ця критика не заперечує реальності компромісу між строгими гарантіями узгодженості та можливістю обробляти запити за мережевих відмов, але закликає формулювати вимоги точніше.[3]

Див. також

Примітки

  1. ↑ а б в г д е Gilbert, Seth; Lynch, Nancy (2002). Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. ACM SIGACT News (англ.). 33 (2): 51—59. doi:10.1145/564585.564601.
  2. ↑ а б в г д е ж и к л Brewer, Eric (2012). CAP Twelve Years Later: How the “Rules” Have Changed. Computer (англ.). 45 (2): 23—29. doi:10.1109/MC.2012.37.
  3. ↑ а б в г д е ж и Kleppmann, Martin (2015). A Critique of the CAP Theorem. arXiv:1509.05393 [cs.DC].
  4. ↑ Failure modes. etcd documentation (англ.). Процитовано 13 жовтня 2026.
  5. ↑ а б DeCandia, Giuseppe; Hastorun, Deniz; Jampani, Madan (2007). Dynamo: Amazon's Highly Available Key-value Store. Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles (англ.): 205—220. doi:10.1145/1294261.1294281.
  6. ↑ а б Apache Cassandra. Apache Cassandra Documentation (англ.). Процитовано 13 жовтня 2026.
  7. ↑ Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek (2011). Conflict-Free Replicated Data Types. Stabilization, Safety, and Security of Distributed Systems (англ.). с. 386—400. doi:10.1007/978-3-642-24550-3_29.
  8. ↑ Abadi, Daniel (23 квітня 2010). Problems with CAP, and Yahoo's Little Known NoSQL System. DBMS Musings (англ.). Процитовано 13 жовтня 2026.
  9. ↑ Abadi, Daniel J. (2012). Consistency Tradeoffs in Modern Distributed Database System Design: CAP Is Only Part of the Story. Computer (англ.). 45 (2): 37—42. doi:10.1109/MC.2012.33.
  10. ↑ Friedman, Roy; Birman, Ken (1996–04). Trading Consistency for Availability in Distributed Systems. Cornell University, Technical Report TR96-1579 (англ.). Процитовано 13 жовтня 2026.{{cite web}}: Обслуговування CS1: Сторінки з неправильним форматом в діапазонах дат (посилання)
  11. ↑ Fox, Armando; Brewer, Eric (1999). Harvest, Yield, and Scalable Tolerant Systems. Proceedings of the Seventh Workshop on Hot Topics in Operating Systems (англ.). doi:10.1109/HOTOS.1999.798396.
  12. ↑ Brewer, Eric A. (2000). Towards Robust Distributed Systems. Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing (англ.). doi:10.1145/343477.343502.

Джерело: стаття у Вікіпедії та історія редагувань (автори).