Теорема PACELC

Теорема PACELC (також принцип PACELC; від англ. Partition, Availability, Consistency, Else, Latency, Consistency) — принцип проєктування розподілених систем, насамперед розподілених баз даних, який описує два різні компроміси між узгодженістю даних, доступністю системи та часом відповіді. Згідно з PACELC, за наявності розділення мережі (P, partition) система змушена робити вибір між доступністю (A, availability) та узгодженістю (C, consistency); за відсутності такого розділення (E, else) під час звичайної роботи реплікованої системи виникає компроміс між низькою затримкою (L, latency) та узгодженістю (C).^[1]

PACELC розширює теорему CAP, яка обмежує можливість одночасно гарантувати узгодженість і доступність саме під час мережевого розділення. На відміну від CAP, PACELC звертає увагу на витрати, пов'язані з узгодженням реплік навіть тоді, коли всі вузли можуть обмінюватися повідомленнями. Принцип запропонував дослідник баз даних Даніель Абаді у 2010 році; 2012 року він виклав його в науковій статті, а 2018 року Войцех Голаб запропонував формальне трактування відповідних обмежень.^[2][3]

Назва PACELC є мнемонічним записом англомовного правила if P, then A or C; else L or C («якщо є розділення мережі — доступність або узгодженість; інакше — низька затримка або узгодженість»). Літера E походить від англійського else («інакше») і не позначає окремої властивості системи.^[1]

У цьому формулюванні:

• P (partition) — розділення мережі, за якого деякі вузли не можуть обмінюватися повідомленнями;
• A (availability) — доступність операцій, тобто здатність відповідати на запити попри відмову зв'язку;
• C (consistency) — узгодженість результатів операцій читання і запису за визначеною моделлю;
• E (else) — випадок нормальної роботи без розділення мережі;
• L (latency) — затримка виконання операції, зокрема час відгуку клієнтові.

Першу частину, PA/PC, розглядають у контексті CAP: за розділення вузли або продовжують обслуговувати запити із ризиком порушення вимог узгодженості, або обмежують обслуговування частини запитів, щоб не допустити суперечливих результатів. Друга частина, EL/EC, стосується штатної роботи: підтвердження змін після координації з іншими репліками або очікування актуальних даних зазвичай збільшує час виконання операції; швидша локальна відповідь може вимагати слабшої моделі узгодженості.^[1]

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

Як і в класичному формальному викладі CAP, сильною формою узгодженості є лінеаризовність (атомарна узгодженість): усі завершені операції над спільним об'єктом мають виглядати так, наче вони відбулися в певному послідовному порядку, сумісному з їхнім порядком у реальному часі. Це не означає, що всі фізичні копії даних повинні змінюватися одночасно: система може відкласти відповідь або скеровувати читання до репліки, що має потрібний стан.^[4][1]

Слабші моделі допускають, наприклад, читання застарілих значень, але можуть гарантувати певний порядок оновлень або те, що після припинення записів і поширення всіх змін репліки зрештою збіжаться до спільного стану (eventual consistency, узгодженість у кінцевому підсумку). Вибір між ними залежить від того, які відхилення може прийняти застосунок.^[1]

Слід також розрізняти узгодженість у CAP/PACELC та властивість consistency у наборі ACID: остання стосується збереження визначених обмежень цілісності даних транзакціями, тоді як лінеаризовність визначає спостережуваний порядок конкурентних операцій.^[4][1]

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

Наприклад, нехай запис змінює значення з v₀ на v₁ у центрі даних A, а користувач зчитує його з репліки в центрі даних B. Якщо оновлення поширюється асинхронно, B може швидко повернути старе значення v₀, поки повідомлення з A ще передається. Щоб гарантувати, що читання після завершеного запису поверне v₁, системі потрібно застосувати додаткові механізми: очікування синхронізації, звернення до актуальної репліки або узгодження результату між вузлами. Це може збільшити затримку.^[1]

Коли між A і B відбувається розділення мережі, постає інша проблема: якщо обидві ізольовані частини можуть незалежно приймати суперечливі записи до одного об'єкта, збереження лінеаризовності не гарантоване. Якщо ж одна з частин відмовляється виконувати такі операції до відновлення зв'язку, порушується вимога доступності у відповідній частині мережі. Це ситуація, яку безпосередньо описує CAP.^[4]

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

Для ілюстрації проєктних рішень Абаді запропонував класифікувати системи за двома виборами: PA або PC під час розділення мережі та EL або EC під час штатної роботи. У такому наближенні отримують чотири групи.^[1]

Таблиця відтворює історичне, спрощене порівняння архітектур, описаних 2012 року; вона не є універсальною характеристикою всіх версій або налаштувань перелічених продуктів. Зокрема, Абаді застерігав, що у формальному розумінні CAP MongoDB не забезпечувала доступність усіх частин мережі під час розділення. Автор відносив її до PA/EC як практичний, а не строгий математичний приклад.^[1]

У системах PA/EL основними цілями є продовження обслуговування під час розділення та швидка відповідь без нього. До цієї групи Абаді зараховував початкові архітектури Amazon Dynamo, Cassandra і Riak. Вони допускали розходження реплік або читання не найновішого значення, використовуючи поширення оновлень і механізми подальшого узгодження даних.^[1]

Це не означає, що такі СКБД за жодних обставин не можуть надавати сильніші гарантії. Наприклад, Cassandra підтримує настроювані рівні узгодженості на рівні окремих операцій, зокрема ONE, QUORUM та ALL, які визначають потрібну кількість відповідей реплік. Вибір вищого рівня може поліпшити свіжість результатів, але також збільшити затримку та вірогідність неможливості завершити операцію під час відмов.^[5]

Модель PA/EC передбачає прагнення до сильнішої узгодженості у звичайному режимі та збереження максимально можливої доступності під час розділення, навіть ціною певних порушень узгодженості. Як приклад Абаді наводив тодішню архітектуру MongoDB, у якій при зміні головного вузла були можливі відкочування записів, не встиглих поширитися на інші репліки.^[1]

У сучасній MongoDB поведінка суттєво залежить від параметрів підтвердження запису (write concern) і читання (read concern). Документація описує, зокрема, підтвердження запису більшістю реплік (majority), яке впливає на гарантії збереження змін. Тому класифікацію 2012 року не варто застосовувати до сучасної конфігурації без уточнення потрібних гарантій.^[6]

У класі PC/EL система під час розділення обмежує доступність, щоб не допустити додаткової втрати узгодженості, але за нормальних умов надає перевагу швидким операціям, допускаючи слабшу модель узгодженості. Ключовий історичний приклад — PNUTS (також Sherpa), розподілене сховище Yahoo!. Для кожного запису воно визначало головну репліку, яка впорядковувала зміни, а потім асинхронно передавала їх іншим реплікам; читання з локальних копій дозволяло зменшувати затримку.^[2][1]

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

PC/EC позначає архітектури, що надають першочергову увагу узгодженості в обох ситуаціях. За розділення вони можуть припиняти певні операції, а за звичайної роботи витрачати додатковий час на координацію. Серед історичних прикладів Абаді називав VoltDB/H-Store, Megastore та Bigtable.^[1]

Конкретні гарантії й межі доступності залежать від одиниці узгодження: окремого ключа, розділу даних чи транзакції. Самої належності до класу PC/EC недостатньо, щоб зробити висновок про однакову поведінку всіх операцій системи.^[1]

Вибір у PACELC проявляється в різних способах організації реплікації та опрацювання запитів:^[1]

• Синхронна реплікація. Вузол очікує підтверджень від інших учасників до завершення запису. Це дає змогу забезпечувати сильніші гарантії, але збільшує час очікування, особливо між віддаленими центрами даних.
• Асинхронна реплікація. Запис може вважатися успішним до того, як його отримають усі репліки. Операція завершується швидше, проте інші вузли певний час можуть віддавати застарілі значення, а за певних відмов непідтверджені репліками записи можуть бути втрачені або відкочені.
• Головна репліка для запису. Визначений вузол упорядковує зміни, після чого розсилає їх іншим. Це спрощує впорядкування, але віддалені клієнти можуть зазнавати додаткової затримки звернення до головного вузла.
• Кворумне читання і запис. Потрібна кількість підтверджень читання та запису дає змогу регулювати баланс між доступністю, свіжістю даних і затримкою. Перетин кворумів є важливою умовою для низки протоколів, але сам по собі ще не доводить лінеаризовність будь-якої реалізації.
• Узгодження порядку операцій. Протоколи на зразок Паксос допомагають вузлам погоджувати спільний порядок дій або рішень; необхідні мережеві повідомлення та очікування впливають на час завершення операцій.

Ці способи можуть поєднуватися. Зокрема, Amazon DynamoDB не слід автоматично ототожнювати з внутрішньою системою Amazon Dynamo, яку аналізував Абаді. DynamoDB документує як читання з узгодженістю у кінцевому підсумку, так і можливість сильно узгодженого читання для підтримуваних типів об'єктів, тому її поведінку потрібно розглядати на рівні конкретної операції та режиму.^[7]

У 2018 році Войцех Голаб у праці Proving PACELC розвинув теоретичний зв'язок між CAP і нижніми межами часу виконання операцій у розподілених системах. Він розглянув модель асинхронної системи з щонайменше двома процесами, які реалізують спільний регістр із операціями читання та запису.^[3]

Для узгодженої реалізації, у якій операції запису та читання різними процесами перекриваються в часі, доведено нижню межу

${\displaystyle r+w\geq d,}$

де ${\displaystyle r}$ — затримка читання, ${\displaystyle w}$ — затримка запису, а ${\displaystyle d>0}$ — нижня межа затримки передавання одного повідомлення у розглянутому виконанні. Отже, неможливо гарантувати, що обидві операції завжди завершуватимуться швидше ніж за ${\displaystyle d/2}$, зберігаючи задану сильну узгодженість. Це твердження стосується конкретної математичної моделі та не є числовою оцінкою швидкодії будь-якої реальної бази даних.^[3]

Якщо повідомлення можуть не надходити взагалі через мережеве розділення, вимога завершувати кожну операцію несумісна із гарантією узгодженості для всіх можливих виконань — це складова CAP. Якщо ж повідомлення надходять, але для цього потрібен ненульовий час, діє нижня межа, що описує частину компромісу між узгодженістю та затримкою за нормальної роботи. Поєднання цих двох результатів Голаб подає як формальне трактування PACELC.^[3]

Передумовою появи PACELC стала теорема CAP, яку Ерік Брюер представив як гіпотезу 2000 року, а Сет Гілберт і Ненсі Лінч формально довели для асинхронної мережевої моделі 2002 року. CAP пояснювала неможливість одночасно забезпечувати лінеаризовність і доступність у разі довільного розділення мережі, але не визначала всіх компромісів, що впливають на звичайну роботу розподілених сховищ.^[4]

23 квітня 2010 року Даніель Абаді опублікував допис Problems with CAP, and Yahoo's little known NoSQL system, у якому критикував поширене тлумачення CAP як універсального поділу систем на «дві з трьох» властивостей. Він звернув увагу на PNUTS: хоча ця система не надавала найсильнішої моделі узгодженості, при недоступності головної репліки вона обмежувала записи, тобто не намагалася будь-якою ціною забезпечити доступність. Таке рішення було пов'язане з потребою зменшувати затримку у звичайному режимі, а не лише з поведінкою під час розділення.^[2]

У лютому 2012 року в журналі Computer (IEEE) Абаді опублікував статтю Consistency Tradeoffs in Modern Distributed Database System Design: CAP Is Only Part of the Story. У ній принцип дістав назву PACELC, було описано вплив реплікації на затримку та запропоновано чотири історичні класи систем — PA/EL, PA/EC, PC/EL і PC/EC.^[1]

У березні 2018 року в ACM SIGACT News вийшла праця Голаба Proving PACELC, яка пов'язала формальне доведення CAP із нижніми межами затримки розподілених операцій і запропонувала строгіше математичне тлумачення принципу. Таким чином, поширена назва «теорема PACELC» стосується як архітектурної класифікації Абаді, так і пізнішого формального результату; ці рівні викладу потрібно розрізняти.^[3]

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

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

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

• Теорема CAP
• Модель узгодженості
• Лінеаризовність
• Реплікація (інформатика)
• Розподілена база даних
• Алгоритм Паксос

• Problems with CAP, and Yahoo's little known NoSQL system — початковий допис Даніеля Абаді (2010, англ.).
• Consistency Tradeoffs in Modern Distributed Database System Design — оригінальна стаття про PACELC (2012, англ.).
• Proving PACELC — формальний розгляд Войцеха Голаба (2018, англ.).