Теорема CAP

4.1 Узгодженість для Брюверу

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.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-транзакції, а й узгодженість реплік, створюються простіше та швидше. Через свою спрощену організацію вони здатні забезпечувати дуже швидку обробку даних, і для низки додатків це виявляється важливішим, ніж усі зручності, властиві технології баз даних.

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