CRDT: Конфлі́йні безредундантні репліковані типи даних

Основна проблема: Координація дорога

У розподіленій системі копії або репліки одних і тих самих даних часто живуть на різних машинах: телефон, ноутбук, сервер одного дата-центру, сервер іншого. Якщо дві репліки оновлюються одночасно, будучи відключеними, просте злиття може давати різні результати залежно від того, яка з оновлень застосовується першою. Класичні рішення змушують репліки координуватися перед прийняттям запису, використовуючи блокування, консенсусні протоколи або єдиного лідера, через якого повинні проходити всі записи. Координація гарантує єдиний узгоджений порядок оновлень, але це коштує дорого: кожен запис повинен чекати на міжвидову подорож до координатора, і якщо мережа розділяється, координатор стає недоступним, і записи повністю відхиляються. Ця напруга відображена в теоремі CAP, яка спостерігає, що розподілена система не може одночасно гарантувати повноту узгодженості та доступності під час мережевого розділення. CRDTs обходять цей компроміс для певної категорії проблем, відмовившись від вимоги, щоб репліки погодилися на порядок операцій. Замість того, щоб запитувати в реальному часі, яке оновлення відбулося першим, CRDT розроблений таким чином, щоб кінцевий результат не залежав від порядку взагалі. Кожна репліка може приймати записи негайно, локально, без координації, без очікування та без ризику блокування через мережеву відключення. Ціна, яку платиться, полягає в тому, що CRDTs працюють лише для структур даних, чия операція злиття може бути визначена з правильними математичними властивостями, і набір можливих операцій над даними є більш обмеженим, ніж у загально призначевій базі даних із будь-якими транзакціями. Але для багатьох реальних застосунків лічильники, множини, регістри, впорядковані послідовності, текстові документи – це обмеження цілком прийнятне, а вигода полягає в тому, що система продовжує працювати плавно навіть тоді, коли частини мережі відключені на кілька годин або днів, пізніше автоматично та правильно узгоджуються.

Математика: Об'єднання з'єднаних лабіринтесів

Гарантія узгодженості, що лежить в основі кожного CRDT, базується на галузі алгебри під назвою теорія лабіринтів. З’єднаний півлабіринт — це множина можливих станів, оснащена бінарною операцією злиття, часто позначається як об'єднання, яка комбінує будь-які дві стани в нову статтю, що представляє їхню найменшу верхню межу. Для того щоб функція злиття працювала для CRDT, вона повинна задовольняти три властивості. По-перше, вона повинна бути комутативною: злиття стану A зі станом B дає той самий результат, що й злиття стану B із станом A. Це важливо, оскільки повідомлення між репліками можуть надходити в будь-якому порядку, і кінцевий стан не повинен залежати від того, який реплік першим отримав оновлення. По-друге, вона повинна бути асоціативною: злиття A з B, а потім злиття результату з C дає той самий результат, що й злиття B із C спочатку і потім злиття з A. Це дозволяє реплікам об'єднувати оновлення пакетами або отримувати їх через різні мережеві шляхи без зміни результату. По-третє, вона повинна бути ідемпотентною: злиття стану зі станом собою або застосування того ж оновлення двічі не змінює стан. Це дуже важливо в реальних мережах, де повідомлення можуть бути дубліковані або повторно відправлені, і система, яка не є ідемпотентною, подвоїть підрахунок повторної доставки. Разом ці три властивості означають, що незалежно від того, скільки разів, в якому порядку або скільки копій кожного оновлення отримує кожен реплік, послідовність злиттів завжди досягає однакового кінцевого стану. Це іноді називається Сильна Остаточна узгодженість: не тільки те, що репліки врешті-решт погодяться, але й те, що будь-які дві репліки, які отримали один і той же набір оновлень, гарантовано перебуватимуть в одному стані зараз, без будь-якого періоду очікування та без можливості затримки конфлікту.

Дві родини: Станово-орієнтовані та Операційно-орієнтовані

CRDTs приходять у двох основних варіантах, які забезпечують однакову гарантію збіжності за допомогою різних механізмів. Перша з них – станово-орієнтований або конвергентний CRDT, часто скорочено CvRDT. У цьому дизайні кожна реplica підтримує весь свій локальний стан і періодично надсилає цей повний стан іншим replica, наприклад, за допомогою протоколу gossip. Отримуючи стан іншої replica, вона об'єднує їх за допомогою операції join-semilattice, описаної раніше, що ефективно приймає комбіноване максимальне значення для кожного відстежуваного значення. Оскільки злиття комутативне, асоціативне та ідемпотентне, не має значення, наскільки частковим, застарілим або дублікованим є ці передачі стану; повторні або позарядкові злиття просто сходяться до одного й того ж результату. Торгівля – це пропускна спроможність: передача повного стану може бути дорогою, оскільки дані збільшуються, хоча дельти та вектори версій часто використовуються на практиці для зменшення обсягу даних. Друга сім’я – операційно-орієнтований або комутативний CRDT, іноді званий CmRDT або CoRDT. Тут replica не передають повні стани; замість цього вони трансляють окремі операції, застосовані локально, такі як збільшення цього лічильника або додавання цього елемента до цієї множини. Кожна replica застосовує кожну отриману операцію до свого власного локального копію. Для того, щоб це правильно збіглося, самі операції повинні комутувати одна з одною, тобто застосування операції X потім операції Y має дати той самий результат, що й застосування Y потім X, принаймні для будь-яких операцій, які могли б потенційно надходити в нестандартному порядку. Операційно-орієнтовані CRDTs зазвичай передбачають надійний канал точно одного разу доставки або потребують додаткового обліку, такого як номери послідовностей, щоб захиститися від втрачених або дублікованих повідомлень, оскільки на відміну від станово-орієнтованого підходу повторне виконання однієї й тієї ж операції двічі може порушити правильність, якщо вона була спеціально розроблена як ідемпотентна також.

Конкретний приклад: Лічильник ‘Always Growing’

Найпростіший CRDT для розуміння – це лічильник ‘Always Growing’ (G-Counter), який підтримує лише збільшення, ніколи не зменшує. Замість зберігати одну спільну числову величину, кожна копія підтримує свій власний приватний лічильник, індексований унікальним ідентифікатором цієї копії. Коли копія A збільшує лічильник локально, вона лише збільшує свій слот у своєму локальному масиві; вона ніколи не торкається слотів, що належать іншим копіям. Щоб прочитати поточний загальний рахунок, копія просто сумує всі слоти в усіх копіях, про які вона знає. Операція злиття двох масивів копій визначається слотом за слотом: для кожного ідентифікатора копії приймати максимальне значення з двох записаних значень. Оскільки операція «прийняти максимум» комутативна, асоціативна та ідемпотентна, злиття двох G-Counter в будь-якому порядку, будь-яку кількість разів завжди дає однаковий об'єднаний масив, і тому однаковий загальний рахунок, навіть якщо обидві копії збільшували лічильник одночасно та ніколи не спілкувалися протягом цього періоду. Розглянемо три копії: A, B і C. Копія A збільшує свій слот двічі, досягаючи локального значення 2, повністю відключившись. Копія B, також відключена, збільшує свій слот тричі, досягаючи 3. Коли A та B врешті-решт з’єднуються та зливаються, кожна бере максимальне значення кожного слоту: слот слота A стає 2, слот слота B стає 3, а загальний рахунок становить 5, правильно відображаючи всі п'ять збільшень від обох копій, навіть якщо обидві копії збільшували лічильник одночасно та ніколи не спілкувалися протягом цього періоду. Ще один приклад – LWW-Register (Реєстр ‘Last Write Wins’), який зберігає одне значення разом із часом його запису; правило злиття просто тримає значення, яке має пізніший час запису, використовуючи ідентифікатор копії як розв’язувач зв’язків для рівних часу запису.”]}**

CRDTs у реальному світі

CRDTs не просто теоретична цікавість; вони лежать в основі систем, які використовують люди щодня. Найчастіше цитується приклад спільних редакторів документів, і основна ідея – дозволити кільком людям одночасно друкувати та автоматично об'єднувати їхні редагування – це саме проблема, яку розробляли CRDTs. Варто відзначити, що багато відомих спільних редакторів, включаючи Google Docs, історично будували свою реальну злиття в режимі реального часу за допомогою іншої техніки під назвою Operational Transformation, не ніж CRDTs, хоча новіші редактори та бібліотеки все частіше використовують послідовні CRDTs, такі як RGA або Logoot, особливо тому що вони спрощують міжвузлову співпрацю без центрального сервера. Розповсюджені бази даних також є великими прихильниками. Redis пропонує типи даних на основі CRDT у своїй функції георозподілу Active-Active, яка дозволяє кільком кластерам Redis в різних регіонах незалежно приймати записки та автоматично їх об'єднувати без конфліктів. Riak, ранній розподілений ключ-значення зберігання даних, побудував власну підтримку CRDT лічильників, наборів, карт і реєстрів безпосередньо в своїй моделі даних, дозволяючи програмам отримати міцну поступову узгодженість без написаного з нуля розв’язання конфліктів. Більший рух програмного забезпечення «зроблено локально» значною мірою покладається на CRDTs як на спосіб забезпечити, щоб пристрій користувача залишався повністю чутливим та функціональним без будь-якого підключення до мережі, синхронізуючи та правильно об’єднуючись, коли з’являється підключення, будь то секунди або дні пізніше.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте CRDT: Conflict-Free Replicated Data Types і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.