Теорема CAP

1. Узгодженість за Брювером

Почнемо з того, що Ерік Брювер не є і ніколи не оголошував себе фахівцем у галузі баз даних. Він належить до спільноти розподілених систем, і його знаменита доповідь, в якій з'явилася "теорема" CAP, була зроблена на конференції "Принципи розподілених обчислень". (До речі, через десять років, у 2010 р. він ще раз виступив із запрошеною доповіддю на тій самій конференції, і в доповіді навів, зокрема, низку прикладів розподілених систем, у розробці яких враховувалася "теорема" CAP.) У цій галузі є своє тлумачення термінів, що використовуються в області баз даних.

Зокрема термін миттєва узгодженість (immediate consistency) означає, що після того, як користувач отримує від системи повідомлення про успішне виконання певної операції оновлення даних, результат цієї операції стає миттєво видимим для всіх спостерігачів.

Узгодженість в кінцевому підсумку (eventual consistency) означає, що якщо протягом достатньо довгого часу до системи не надходять нові операції оновлення даних, то можна очікувати, що результати всіх попередніх операцій оновлення даних зрештою поширяться по всіх вузлах системи, і всі репліки даних узгоджуються (мабуть, це потрібно розуміти як "у всіх реплік буде один і той самий стан".

Маючи на увазі цей сенс поняття узгодженість, можна вважати "теорему" Брювера цілком зрозумілою та очевидною: у будь-якій розподіленій системі з розділеними даними можна одночасно забезпечити лише будь-які дві властивості з узгодженості, доступності та стійкості до поділу мережі. У зв'язку з цим Брювер навіть протиставляє набір властивостей ACID запропонованого ним набору властивостей BASE (Basically Available, Soft-state, Eventual consistency — доступність у більшості випадків; нестійкий стан; узгодженість зрештою). Але це протиставлення, на мою думку, є неправомірним, оскільки в першому випадку йдеться про логічні характеристики транзакцій, а в другому — про фізичні властивості розподілених систем.

2. Доказ «теореми»

Багато хто вважає, що "теорема" Брювера формально доведена. Справді, у статті Сета Гільберта (Seth Gilbert) і Ненсі Лінч (Nancy Lynch) запроваджуються деякі (майже) формальні визначення, у яких "теорема" справді стає теоремою і доводиться. Однак давай розберемося, як визначаються ті три властивості розподіленої системи, з яких за "теоремою" Брювера можна одночасно забезпечити підтримку тільки двох властивостей.

Узгодженістю називається атомарна, або лінеарізована узгодженість (Atomic, or linearizable consistency), що є властивістю системи, всі індивідуальні об'єкти даних якої є атомарними (лінеаризуються). У свою чергу, атомарним об'єктом називається об'єкт з декількома операціями: такими, що виклик операції та отримання даних у відповідь відбуваються ніби миттєво. Тобто, об'єкт не приймає виклик наступної операції до завершення попередньої операції. Водночас порядок прийому операцій повинен бути таким, щоб якщо операція типу читання надходить після виконання деякої операції типу запису, то операція читання повинна повернути значення, записане цією або будь-якою пізнішою операцією запису.

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

На основі цих визначень Гільберт та Лінч формулюють таку теорему (в асинхронній моделі мережі відсутні години, і у вузлах повинні прийматися рішення лише на основі отримуваних повідомлень і локальних обчислень):

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

Ця теорема дійсно досить просто формально доводиться методом "від протилежного". Далі у статті виводиться слідство, що:

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

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

Так, можна вважати, що в певному сенсі (не обов'язково) Гільберт і Лінч довели неможливість одночасного забезпечення в одній розподіленій системі властивостей атомарної узгодженості, доступності та стійкості до поділу мережі. Але яке відношення це має до транзакцій баз даних взагалі і до ACID-транзакцій зокрема?

3. ACID-транзакції

Ось що пише з цього приводу в своїй нотатці, присвяченій обговоренню "теореми" CAP, Джуліан Браун (Julian Browne):

У своєму доказі Гільберт і Лінч використовують замість терміну узгодженість термін атомарність, що з технічної точки зору більш осмислено, тому що, відверто кажучи, узгодженість у сенсі ACID відноситься до ідеальних властивостей транзакцій баз даних і означає, що жодні дані не стануть довгостроковими, якщо вони порушують деякі заздалегідь встановлені обмеження. Але якщо вважати, що заздалегідь встановленим обмеженням розподілених систем є заборона наявності кількох різних значень в одного й того самого елемента даних, то, на мою думку, ця вада в абстракції узгодженості може вважатися несуттєвою (до того ж, якби Брювер використовував термін атомарність, то з'явилася б теорема AAP, назва якої було б надзвичайно незручно вимовляти).

Це написано не дуже серйозно, але чесно. І насправді вимогу атомарної узгодженості не можна перемішувати з вимогами узгодженості транзакцій у сенсі ACID. Обмеження цілісності бази даних — це логічні бізнес-вимоги. Вони походять із логіки прикладної області. Вимога атомарної узгодженості — зовсім іншого роду. Це реалізаційна вимога, що стосується тієї категорії, яку традиційно в області баз даних називали фізичною узгодженістю (наприклад, під час виконання будь-якої операції зміни індексу всі блоки відповідного B+-дерева повинні містити коректні значення та бути пов'язані коректними посиланнями).

А ось що вже зовсім серйозно пишуть у своїй нотатці представники спільноти баз даних Деніель Абаді (Daniel Abadi) та Александер Томсон (Alexander Thomson):

... все більш критичною стає вимога до доступності масштабованих транзакційних систем, і зазвичай вона задовольняється за рахунок реплікації та автоматичного перенаправлення запитів у разі збою одного з вузлів. Тому розробники застосунків очікують, що гарантії узгодженості (Consistency) ACID-систем (спочатку полягали в локальній підтримці певних користувачами інваріантів) будуть поширені на забезпечення строгої узгодженості (того, що всі репліки тих самих даних у будь-який момент часу будуть ідентичними копіями, отже в цьому випадку узгодженість мається на увазі в сенсі CAP/PACELC).

Іншими словами, узгодженість за Брювером не має нічого спільного з узгодженістю в сенсі ACID, але саме в системах, орієнтованих на забезпечення високого рівня доступності за рахунок реплікації даних, бажано підтримувати строгу узгодженість реплік, це не властивість ACID, а технічна (фізична) особливість масивно-паралельних СУБД, що полегшує розробку застосунків.

Як вважає Майкл Стоунбрейкер, запорукою побудови якісної СУБД є правильний вибір технічних компромісів. У виборі конкретного інженерного рішення потрібно враховувати безліч факторів: вимоги майбутніх користувачів, ймовірності виникнення різних збійних ситуацій тощо, а не керуватися догматичним чином будь-якими загальними теоретичними вказівками (в тому числі і "теоремою" CAP).

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

Таким чином, висока активність представників табору NoSQL (читай NoACID), які часто посилаються на "теорему" Брювера, пов'язана не з теоретичною неможливістю побудови масивно-паралельних транзакційних СУБД, що підтримують ACID-транзакції, а з тим, що спрощені системи, що не підтримують не тільки ACID-транзакції, а й узгодженість реплік, створюються простіше та швидше. Через свою спрощену організацію вони здатні забезпечувати дуже швидку обробку даних, і для низки програм це виявляється важливішим, ніж усі зручності, властиві технології баз даних.

Подивимося, як відповідає на цей виклик спільнота баз даних.