Теорема CAP
Теорема CAP (також відома як теорема Брюера, на честь науковця Еріка Брюера) — твердження, що для будь-якої розподіленої комп'ютерної системи неможливо одночасно забезпечити виконання більше двох із перелічених трьох властивостей:
- узгодженість даних (усі вузли бачать однакові дані у будь-який момент часу);
- доступність (гарантія того, що кожен запит отримає коректну відповідь);
- стійкість до розділення (попри розділення на ізольовані секції або втрати зв'язку з частиною вузлів, система не втрачає стабільність і здатність коректно відповідати на запити).
Акронім CAP утворений з перших букв англомовних іменувань цих трьох властивостей (Consistency, Availability, Partition tolerance).[1][2]
Історія
Згідно Еріком Брюером теорема вперше виникла восени 1998, а опублікована під назвою «CAP-правило» в 1999.
В 2000 Брюер презентував свою гіпотезу на симпозіумі по розподіленим обчисленням що призвело до її широкої популярності та визнання серед спеціалістів по розподіленим обчисленням.
Згодом, в 2002 Сет Джилберт та Ненсі Лінч із Масачусетського технологічного інституту опублікували формальне доведення цієї теореми.[3]
Наслідки
З точки зору теореми, розподілені системи в залежності від пари забезпечених властивостей діляться на три класи:
CA
Розподілена система в якій забезпечена доступність та узгодженість даних не може забезпечувати стійкість до розділення.
Прикладом такої системи є програмне забезпечення що підтримує ACID вимоги, наприклад реляційні бази даних.
AP
Розподілена система в якій не гарантується цілісність результату, зате висока доступність і збереження працездатності при розділенні.
Звісно такі системи з'явилися значно раніше формулювання CAP теореми, як то наприклад DNS, але ріст популярності збігається з розповсюдженням даного принципу (зокрема деякі NoSQL системи не гарантують цілісність результату, посилаючись на дану теорему).
CP
Система що забезпечує цілісність даних на всіх вузлах і здатність працювати при розділенні, але не гарантує доступність і може не відповідати на запити.
Прикладами таких систем є розподілене програмне забезпечення фінансових систем, де узгодженість даних має найвищий пріоритет, це наприклад, мережа банкоматів.