Забудьте САР теорему як більш не актуальну

або «Припиніть характеризувати сховища даних як CP або AP»

capДжеф Ходжес у своєму прекрасному пості «Нотатки про розподілених системах для новачків» рекомендує використовувати САР теорему для критики знайдених рішень. Багато хто, схоже, сприйняли цей рада занадто близько до серця, описуючи свої системи як «СР» (узгодженість даних, але без постійної доступності при мережевий роздрібненості), «АР» (доступність без погодженого стану при мережевий роздрібненості), або іноді «СА» (означає «Я все ще не читав статтю Коди (Coda Hale) майже 5-річної давності»).

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

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

САР використовує занадто вузьке визначення
Якщо ви хочете посилатися на САР як на теорему (а не на розпливчастий концепт в маркетингових матеріалах до вашої бази даних), ви повинні бути точними. Математика вимагає точності. Доказ зберігається тільки якщо ви вкладається в слова, те ж саме значення, що було використано при доказі. І воно спирається на дуже точні визначення:
  • Узгодженість (Consistency) в САР насправді означає линеаризуемость, що є (і дуже сильним) принципу узгодженості. Зокрема, це не має нічого спільного з «З» з ACID, навіть якщо ця так само означає «узгодженість». Я на пальцях поясню, що таке линеаризуемость трохи пізніше.
  • Доступність (Availability) в САР визначено як «кожен запит, отриманий працюючим вузлом [базою даних] у системі повинен призводити до відповіді [не містить помилок]». Недостатньо щоб деякі вузли могли обробити запит: будь працює вузол повинен бути здатний обробити запит. Безліч так званих «високодоступних» (high abailability), тобто з низьким рівнем простою, систем в реальності не відповідають визначенню доступності.
  • Стійкість до поділу (Partitiontolerance) жахливе назва – в загальних словах означає що ви для зв'язку використовуєте асинхронну мережа, яка може втрачати чи затримувати повідомлення. Інтернет і все датацентри володіють цією властивістю, так що в реальності у вас немає вибору в цьому контексті.
Ще хочу зауважити, що САР теорема описує не просто будь-яку стару систему, але систему дуже певної моделі:
  • Модель системи у просторі САР це єдиний вузол\лічильник (register) для читання – і все. Наприклад, нічого не говориться про транзакції, які зачіпають кілька об'єктів. Вони просто за межами умов теореми, до тих пір, поки ви не ужмете якимось чином ті об'єкти до єдиного об'єкта.
  • Єдиний тип збою про який згадує САР теорема – мережеве поділ, тобто вузли залишаються активні, але мережа між деякими з них не працює. Такий вид помилки так чи інакше відбувається, але це не єдина річ, яка може піти не так: вузли можуть бути зламані або перезавантаження, може закінчитися місце на диску, можете зловити баг З, і тд і тп. У процесі створення розподіленої системи вам треба мати на увазі набагато більший спектр можливих помилок і компромісів, до яких вони ведуть. Занадто сильна фокусування на САР теоремі веде до ігнорування інших важливих проблем.
  • Більш того, САР теорема нічого не говорить про латентності, яка турбує більшість розробників набагато більше, ніж доступність. Фактично, САР-сумісні системи можуть бути як завгодно повільними і все одно називатися «доступними». Якщо доводити все до крайності, я впевнений, що ваші користувачі не будуть схильні називати вашу систему «доступною», якщо для отримання веб-сторінки потрібно 2 хвилини.
Якщо ваше визначення збігається з формальним значенням термінів в САР теоремі, тоді вона підходить вам. Але якщо ви даєте інше визначення термінам узгодженості і доступності, то не можна очікувати того, що САР теорема застосовується до вас. Звичайно, це не означає, що шляхом зміни значень ви раптово зможете зробити неможливі речі! Просто ви не можете керуватися САР теоремою і використовувати її для аргументації на підтримку вашої точки зору.

Линеаризуемость
У разі, якщо ви не знайомі з линеаризуемостью (в сенсі «цілісністю» в контексті САР), дозвольте мені коротко розповісти про це. Формальне визначення не те щоб дуже зрозуміле, але ключова ідея, якщо по-простому, така:

Якщо операція почалася після успішного завершення операції А, тоді операція повинна бачити стан системи в момент завершення А або в новому стані.

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

alice_bob

Діаграма ілюструє наступну ситуацію: Боб і Аліса знаходяться в одній кімнаті, обидва перевіряють свої телефони, щоб перевірити результати фінальної гри на чемпіонаті світу з футболу 2014 року. Відразу після того, як рахунок був оголошений, Аліса оновлює сторінку, бачить переможця і радісно повідомляє про це Бобу. Він тут же тисне Оновити на своєму телефоні, але його запит потрапляє на репліковану базу, яка злегка лагает, тому його телефон каже, що гра все ще йде.

Якби Аліса і Боб оновили сторінку в телефоні одночасно, було б не дивно, що вони отримали різні результати, бо вони не знають в який саме час були оброблені їх запити. Однак Боб знає, що він оновлює сторінку (ініціює запит) після того, як почув вигук Аліси про фінальному рахунку і, таким чином, він очікує, що його дані будуть як мінімум з тієї ж давністю, що і у Аліси. Той факт, що він отримав протухнув результат запиту є порушенням лінеаризації.

Знання про те, що запит Боба стався строго після запиту Аліси (що вони не були одночасними) ґрунтується на тому, що Боб почув результат запиту від Аліси через інший канал зв'язку (в нашому випадку вербально). Якби Боб не почув результату від Аліси, що гра закінчилася, тоді б він не знав про те, що його результат застарів.

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

Дуже дорого і проблематично надати гарантії линеаризуемости, тому що це вимагає великої кількості координаційних операцій. Навіть CPU у вашому комп'ютері не надає линеаризованный доступ до оперативної пам'яті! Для отримання линеаризуемости в сучасних CPU необхідно використовувати memory barrier інструкції. І навіть протестувати линеаризуемость системи дуже навіть не просто.

САР-доступність
Поговоримо трохи про те, чи потрібно жертвувати линеаризованностью доступністю у випадку з мережевим поділом.

Припустимо у нас є копії бази даних в двох різних датацентрах. Конкретний метод реплікації в даному випадку неважливий – це може бути single-leader (master/slave), multi-leader (master/master) або quorum-based реплікація (Dynamo-style). Загальний сенс реплікації в тому, щоб при зміні даних в одному датацентрі вони відображалися в іншому. Уявімо, що клієнти пов'язані тільки з одним датацентром і має бути ще одне з'єднання між датацентрами для реплицирования даних.

Тепер нехай з'єднання між ДЦ було перервано – це те, що ми розуміємо під мережевим поділом. Що тоді станеться?

dc

Очевидно, що ви можете вибрати один з двох варіантів:
  1. Додаток продовжує працювати і дозволяє запис в базу даних, воно повністю доступно для обох датацентрів. Але так як зв'язок між ДЦ перервана, всі зміни в одному ДЦ не будуть доступні в іншому. Це порушує линеаризуемость (в термінах попереднього прикладу, Аліса може бути віднесена до ДЦ1, а Боб до ДЦ2).
  2. Якщо ви не хочете втрачати линеаризуемость, ви повинні бути впевнені, що ви здійснюєте всі читання і запис в одному датацентрі, який ви можете називати ведучим. В іншому ДЦ, дані якого не можуть бути в актуальному стані із-за втрати з'єднання, база даних повинна припинити обслуговувати клієнтів на читання і запис до відновлення синхронізації. Так як залежна база даних в другому ДЦ не може обробляти запити, то вона не САР-доступна.
До речі, це по суті доказ САР теореми. У прикладі використовуються два ДЦ, але все може бути застосовано і до одного ДЦ, так як мережеві проблеми можуть бути всередині теж. Просто я подумав, що приклад з двома ДЦ більш простий і наочний.

Зауважте, що в нашій умовно «недоступною» ситуації у другому варіанті, ми цілком успішно можемо обробляти запити в одному з ДЦ. Так що якщо система побудована з упором на линеаризуемость (тобто не САР-доступна), то це не обов'язково означає що мережева розділеність автоматично веде до простою програми. Якщо ви зможете перевести всіх клієнтів на використання провідного ДЦ, клієнти не помітять падіння взагалі.

Доступність (availability) на практиці не те щоб посилається на САР-доступність. Доступність вашого додатки швидше за все вимірюється в SLA (наприклад, 99,9% правильних запитів повинні повертати результат протягом 1 секунди), але така угода може бути реалізовано в системах CAP-доступних і САР-недоступних.

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

Багато системи линеаризуемые, ні САР-доступні
Як створювати системи з урахуванням строгих визначень в САР-теоремою для цілісності (линеаризованности) і доступності?

Наприклад, візьміть будь-яку БД з реплікацією і одним ведучим (single leader), що є стандартним налаштуванням для більшості реляційних баз даних. У такій конфігурації клієнт не може писати в базу, якщо він відділений від ведучого. Навіть якщо клієнт може читати з копій (read-only recplica), той факт, що він не може писати дані означає що будь-яка настройка з єдиним ведучим не САР-доступна. І неважливо, що такі системи часто позиціонуються як «системи з високою доступністю».

Якщо реплікація з одним ведучим не САР-доступна, то робить це її «СР»? Стривайте, не так швидко! Якщо ви дозволите додатком читати з реплік, а репліки асинхронні (за замовчуванням для більшості БД), тоді залежна БД може бути злегка застарілої під час читання. У цьому випадку читання буде не линеаризованным, тобто не CAP-узгодженим.

Більш того, бази даних рівнем ізоляції snapshot/MVCC навмисно нелинеаризованны, тому що вимога лінеаризації зменшить кількість одночасно виконуваних операцій (concurrency). Наприклад, PostgreSQL SSI дає сериализуемость, але не линеаризуемость, Оракл така ж ситуація. Тільки тому що база даних маркована як ACID не означає, що БД задовольняє визначенню узгодженості\несуперечності CAP в теоремі.

Виходить, що ці системи не CAP-узгоджені, ні САР-доступні. Вони ні «СР», ні «АР», вони просто «Р», щоб це не значило. Так, формулювання «два з трьох» дозволяє вам вибрати тільки одну опцію з трьох, або навіть жодної!

А щодо «NoSQL»? Для прикладу можна взяти MongoDB: вона має одного ведучого на шард (принаймні так передбачається, якщо це не режим split-brain), так що з огляду на все сказане вище, вже немає САР-доступності. І Кайл (Kyle) нещодавно показав, що це дозволяє робити нелинеаризованное читання навіть при найвищому рівні налаштувань узгодженості, так що САР-узгодженості немає так само.

Похідні від Dynamo, такі як Riak, Cassandra і Voldemort, часто звуться «АР» тому що оптимізовані для високого рівня доступності? Ну, це залежить від ваших налаштувань. Якщо репліки можна писати і читати дані (R=W=1) – вони дійсно CAP-available. Однак, якщо читання та запис здійснюються кворумом (R+W>N) і у вас поділ по мережі, клієнти знаходяться на боці меншини не можуть достукатися до кворуму, виходить що кворум операції так само не САР-доступні (як мінімум тимчасово, поки база даних не підніме додаткові репліки на боці меншини).

Часом ви можете зустрічатися з людьми, які стверджують, що читання і запис на основі кворуму гарантує лінеаризацію, але я думаю це буде не дуже розумно покладатися на це – тендітна комбінація функцій, таких як sloppy quorums і читання з відновленням (read repair) можуть призвести до крихкій межі, коли мертві повстануть видалені записи відновляться, або кількість реплік впаде менше оригінально числа письменників (порушення умов кворуму), або кількість реплік перевищить первісну N (знову порушення умов кворуму). Все це веде до нелинеаризованному отримання даних.

Всі згадані системи не погані: люди успішно використовують їх у бойовому оточенні. Однак, ми досі не змогли строго визначити як «AP» або «CP», в тому числі тому що це залежить від певної операції або конфігурації, або тому що система не задовольняє строгому визначенню несуперечності або доступності САР-теоремою.

Реальний приклад: ZooKeeper
Що щодо ZooKeeper? Ця система використовує алгоритм угод, тому багато сходяться на думці що це чистий приклад переваги узгодженості над доступністю (тобто «СР система»).

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

Взагалі зробити лінеаризоване читання в ZooKeeper можливо используя sync перед командою читання. Це не поведінка за замовчуванням, тому що отримуємо просідання по продуктивності. Команда sync використовується, але не весь час.

Що щодо доступності в ZooKeeper? Що ж, ZK вимагає рішення більшості для досягнення угоди для запису даних. Якщо у вас є поділ на більшість і меншість нод, то більшість буде функціонувати як раніше, однак ноди залишилися в меншості не зможуть обробляти запити на запис, незважаючи на те, що всі вони справні. Виходить, функція запису в ZK не САР-доступна в розділеному (partition) режимі функціонування (навіть з урахуванням того, що більшість нсд може записувати дані).

Щоб додати у все це ще більше веселощів, у версії ZooKeeper 3.4.0 додали режим тільки для читання, в якому ноди, що залишилися в меншості можуть продовжувати обслуговувати запити читання – кворум не потрібно! Тобто режим для читання САР-доступним. Таким чином, ZK за замовчуванням не є ні САР-узгодженим («СР»), ні САР-доступним («АР») – це реально просто «Р». Втім, ви можете зробити систему «СР» використовуючи метод sync, і тільки для операції читання система «AP», якщо включити вірні опції.

Але ось що дратує: називати ZooKeeper «не узгодженою системою, просто тому що вона нелинеаризуемая за замовчуванням – справді жахлива інтерпретація фіч. ZK насправді дає чудову ступінь несуперечності! Він підтримує atomic broadcast спільно з гарантованою casual consistency сильне умова, ніж read your writes, monotonic reads і consistent prefix reads разом узяті. Документація говорить, що система дає послідовну несуперечність, але це недооцінка самих себе, тому що ZooKeeper гарантує більш сильне визначення, ніж послідовна несуперечність.

СР/АР: помилкова дихотомія
Той обставина, що ми не змогли однозначно класифікувати навіть одне сховище як «АР» або «СР» повинно наводити на певні думки: це просто невідповідні визначення для описуваних систем.

Я впевнений, що ми повинні припинити намагатися визначити різні сховища в категорії «АР» або «СР» тому, що:
  • В рамках одне програми може існувати кілька різних операцій з різними характеристиками узгодженості даних.
  • Безліч систем не відповідають визначенню узгодженості і доступності в рамках САР-теореми. Однак я ніколи не чув, щоб хтось називав свою систему просто «Р», напевно тому що це погано звучить. Але це не погано – це може бути ідеально спланована архітектура, яка просто не потрапляє до категорії СР/АР.
  • Навіть якщо більшість не потрапляють точно в згадані категорії, люди все одно намагаються втиснути його в одну з категорій, і виходить, що неминуче змінюється сенс «узгодженості» або «доступності» до того, що вони хочуть під цим розуміти. На жаль, якщо значення слів змінюється – САР теорема більше не може застосовуватись, і поділ на СР/АР не має значення.
  • Величезна кількість нюансів втрачається при спробі втиснути систему в одну з двох категорій. Існує величезна кількість аспектів щодо стійкості до збоїв, латентності, простоти моделі програмування, взаємодії і так далі, що може бути використано в проектуванні розподілених систем. Фізично неможливо закодувати всі ці нюанси в одному біті інформації. Наприклад, навіть ZooKeeper підтримує «AP» в режимі тільки для читання, і цей режим дає можливість читати запис в тому ж самому порядку, як вони були записані – це набагато сильніше, ніж «АР» у таких системах як Riak або Cassandra – так що було б безглуздо складати їх в одну купу.
  • Навіть Ерік Брюер (Eric Brewer) визнає, що САР вводить в оману і занадто все спрощує. У 2000 році було важливо почати обговорення компромісів в розподілених системах, і це спрацювало. Не було наміру створити якийсь проривний формальний документ або сувору класифікацію схем для сховищ даних. 15 років тому у нас з'явився набагато більш багатий набір інструментів з різними підходами до забезпечення цілісності даних і захистом до помилок. САР зробила свою задачу і тепер час рухатися далі.


Вчіться думати самостійно
Якщо «СР» і «АР» не підходять для опису і критики систем, що слід використовувати замість? Не думаю, що у мене є єдиний правильний відповідь. Багато людей провели чимало часу напружено розмірковуючи про проблеми розподілених систем, і запропонували термінологію і моделі, які нам допомагають зрозуміти проблеми. Щоб дізнатися про велику цих ідеях вам треба самостійно покопирсатися в літературі:
  • Гарною відправною точкою буде стаття Дуга Террі де він роз'яснює відмінності між різними рівнями часткової узгодженості використовуючи бейсбол для прикладу. Дуже легко читається і розуміється, навіть якщо ви (як і я) не американець і нічого не розумієте в бейсболі.
  • Якщо ви хочете дізнатися більше про моделі транзакційний ізоляції (що не те ж саме що і узгодженість в розподілених репліках, але близько), мій маленький проект Hermitage може допомогти.
  • Зв'язок між узгодженістю реплік, транзакціями і доступністю досліджено Пітером Баилисом (Peter Bailis). Документ пояснює значення ієрархії рівнів узгодженості які так любить показувати Кайл Кінгсбері (Kyle Kingsbury).
  • Коли ви все це прочитаєте, ви будете готові копнути глибше. Я перелопатив купу посилань і документів для цього поста – почитайте їх, експерти вже чудово описали багато речей для вас.
  • В якості останнього аргументу, якщо ви не можете читати першоджерела, я пропоную вам поглянути на мою книгу, яка містить і підсумовує найбільш важливі ідеї в зручному вигляді. Бачите, я намагався дуже не зробити з поста рекламну мова.
  • Якщо вас зацікавила тема ZooKeeper і ви хочете звернути на нього більш детальний погляд, Flavio Junqueira і Benjamin Reed написали гарну книгу.
Незалежно від того, який шлях вивчення ви оберете, я закликаю вас зберігати цікавість і терпіння – це непросто. Але ви будете винагороджені, тому що ви будете розуміти причини компромісів і зможете визначити який тип архітектури у вашому конкретному випадку. Але щоб ви не робили, припиніть.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.