Теорема CAP

Теорема CAP (також відома як теорема Брюера, на честь науковця ^[en]) — твердження, що для будь-якої розподіленої комп'ютерної системи неможливо одночасно забезпечити виконання більше двох із перелічених трьох властивостей:

• узгодженість даних (усі вузли бачать однакові дані у будь-який момент часу);
• доступність (гарантія того, що кожен запит отримає коректну відповідь);
• стійкість до розділення (попри розділення на ізольовані секції або втрати зв'язку з частиною вузлів, система не втрачає стабільність і здатність коректно відповідати на запити).

Коли відбувається розділення мережі, необхідно вирішити, що потрібно робити

• скасувати операцію і таким чином зменшити доступність, але забезпечити узгодженість
• продовжувати операцію і таким чином забезпечувати доступність, але ризикувати неузгодженістю.

Таким чином, якщо є розділення мережі, потрібно вибирати між узгодженістю та доступністю. Зауважте, що узгодженість, визначена в теоремі CAP, значно відрізняється від узгодженості, гарантованої в транзакціях ACID баз даних.

Ерік Брюер стверджує, що часто використовувана концепція «два з трьох» може дещо вводити в оману, оскільки розробникам систем потрібно лише пожертвувати узгодженістю або доступністю за наявності розділення, але в багатьох системах розділення зустрічаються рідко.

Акронім CAP утворений з перших букв англомовних іменувань цих трьох властивостей (Consistency, Availability, Partition tolerance).

Наслідки

З точки зору теореми, розподілені системи в залежності від пари забезпечених властивостей діляться на три класи:

CA

Розподілена система в якій забезпечена доступність та узгодженість даних не може забезпечувати стійкість до розділення.

Прикладом такої системи є програмне забезпечення що підтримує ACID вимоги, наприклад реляційні бази даних.

AP

Розподілена система в якій не гарантується цілісність результату, зате висока доступність і збереження працездатності при розділенні.

Звісно такі системи з'явилися значно раніше формулювання CAP теореми, як то наприклад DNS, але ріст популярності збігається з розповсюдженням даного принципу (зокрема деякі NoSQL системи не гарантують цілісність результату, посилаючись на дану теорему).

CP

Система що забезпечує цілісність даних на всіх вузлах і здатність працювати при розділенні, але не гарантує доступність і може не відповідати на запити.

Прикладами таких систем є розподілене програмне забезпечення фінансових систем, де узгодженість даних має найвищий пріоритет, це наприклад, мережа банкоматів.

Історія

Згідно Еріком Брюером теорема вперше виникла восени 1998, а опублікована під назвою «CAP-правило» в 1999. В 2000 Брюер презентував свою гіпотезу на симпозіумі по розподіленим обчисленням що призвело до її широкої популярності та визнання серед спеціалістів по розподіленим обчисленням. Згодом, в 2002 Сет Джилберт та Ненсі Лінч із Массачусетського технологічного інституту опублікували формальне доведення цієї теореми.

У 2012 році Брюер пояснив деякі зі своїх точок зору, зокрема, чому часто використовувана концепція «два з трьох» може бути дещо оманливою, оскільки розробникам систем потрібно лише пожертвувати узгодженістю або доступністю за наявності розділення; Існують методи керування розділеннями та техніки відновлення після розділення. Брюер також відзначив різне визначення узгодженості, що використовується в теоремі CAP, порівняно з визначенням, що використовується в ACID.

Подібну теорему про компроміс між узгодженістю та доступністю в розподілених системах опублікували Бірман і Фрідман у 1996 році. Вони обмежили цю нижню межу не комутативними операціями.

, представлена в 2010 році, базується на CAP, стверджуючи, що навіть за відсутності розподілу існує ще один компроміс між затримкою та узгодженістю.

Технологія Blockchain жертвує негайною узгодженістю заради доступності та стійкості до розділення, вимагаючи певної кількості «підтверджень», алгоритми консенсусу Blockchain в основному зводяться до кінцевої узгодженості.

Примітки

1. Liochon, Nicolas. The confusing CAP and ACID wording. This long run. Процитовано 1 лютого 2019.
2. Eric Brewer, "CAP twelve years later: How the 'rules' have changed", Computer, Volume 45, Issue 2 (2012), pg. 23–29. DOI:10.1109/MC.2012.37.
3. Carpenter, Jeff; Hewitt, Eben (July 2016). . www.oreilly.com (англ.). Архів оригіналу за 7 серпня 2020. Процитовано 21 грудня 2020. In February 2012, Eric Brewer provided an updated perspective on his CAP theorem [..] Brewer now describes the “2 out of 3” axiom as somewhat misleading. He notes that designers only need sacrifice consistency or availability in the presence of partitions, and that advances in partition recovery techniques have made it possible for designers to achieve high levels of both consistency and availability.
4. Brewer's CAP Theorem.
5. . Архів оригіналу за 4 лютого 2016.
6. CAP Twelve Years Later: How the "Rules" Have Changed.
7. Ken Birman and Roy Friedman, "Trading Consistency for Availability in Distributed Systems", April 1996. hdl:1813/7235.
8. Abadi, Daniel (23 квітня 2010). DBMS Musings: Problems with CAP, and Yahoo's little known NoSQL system. DBMS Musings. Процитовано 23 січня 2018.
9. Bashir, Imran. (2018). Mastering blockchain. Birmingham, England: Packt Publishing. p. 41. .

Див. також

• Розподілені обчислення
• Цілісність інформації