AntidoteDB

Наукові передумови

На початку XXI століття зростання географічно розподілених вебслужб загострило суперечність між часом відповіді, доступністю сервісу під час мережевих збоїв та суворістю гарантій узгодженості. Якщо для кожного запису чекати підтвердження від віддалених центрів обробки даних, затримка може залежати від міжконтинентального мережевого зв'язку. Якщо ж дозволити незалежні зміни в кількох місцях, програмі потрібні зрозумілі правила їх подальшого об'єднання. Значна частина NoSQL-систем обирала доступність і слабші гарантії узгодженості, залишаючи розробникам завдання розв'язувати конфлікти на рівні застосунку.

Дослідження CRDT запропонували інший підхід: для певних типів даних можна математично визначити такі операції та правила об'єднання, щоб результати незалежних змін збігалися після надходження всіх необхідних оновлень. Однак коректне об'єднання значень окремих об'єктів саме собою не гарантує узгодженого читання кількох об'єктів, збереження причинного порядку чи дотримання правил предметної області. Саме поєднання цих рівнів стало одним із напрямів досліджень, на яких ґрунтується AntidoteDB.

SyncFree, Cure та AntidoteDB

Європейський проєкт SyncFree (жовтень 2013 — грудень 2016) був присвячений великомасштабним обчисленням без глобальної синхронізації із застосуванням CRDT. Його координувала французька дослідницька організація Inria. Серед результатів, які згадує Європейська комісія, були Antidote, Lasp, FMKe та інструменти добору гарантій узгодженості для конкретних операцій. Отже, AntidoteDB виникала не як ізольований комерційний продукт, а як частина ширшої програми дослідження програмування розподілених систем.

У 2016 році на конференції IEEE ICDCS розробники опублікували статтю «Cure: Strong Semantics Meets High Availability and Low Latency». Протокол Cure поєднував транзакції над кількома об'єктами, узгоджені причинно-наслідкові знімки даних і асинхронну реплікацію. Описана у статті експериментальна реалізація спиралася на платформу Antidote, Erlang/OTP і компоненти Riak, зокрема механізм розподілу ключів riak_core. Серед авторів — Діпті Девакі Аккоорат, Алехандро Томсич, Мануел Браво, Чжунмяо Лі, Тайлер Крейн, Аннетт Біньюза, Нуну Прегіса та Марк Шапіро; у публікації зазначені установи Німеччини, Франції, Бельгії й Португалії.

Наступний європейський дослідницький проєкт LightKone тривав від січня 2017 до грудня 2019 року й стосувався обчислень на периферії мережі — серед пристроїв, які можуть мати нестійкий зв'язок. Репозиторій AntidoteDB називає систему опорною платформою як SyncFree, так і LightKone. Це підтверджує наукову спадкоємність проєктів, але не означає, що AntidoteDB сама по собі стала універсальною платформою периферійних обчислень.

Публічні версії та стан проєкту

Програмний код AntidoteDB оприлюднено на GitHub під ліцензією Apache 2.0. У відкритому списку позначених випусків наявна, зокрема, версія 0.2.2; саме її досліджували автори праці Plume 2024 року. Наявність певного номера у списку випусків не тотожна твердженню, що він збігається з поточним станом основної гілки коду або що для нього існує довгострокова підтримка. Визначити надійно задокументовану дату першого загальнодоступного релізу та підтвердити масштаби промислової експлуатації за використаними джерелами не вдалося.

Реплікація та доступність

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

У контексті теореми CAP (теореми Брюера) йдеться про обмеження, яке виникає за розділення мережі: система не може одночасно гарантувати відповіді на всі запити від доступних клієнтів та одну глобально лінеаризовну картину даних, якщо частини мережі не можуть зв'язатися. Популярне скорочення «обрати будь-які дві з трьох властивостей» не описує цієї умови достатньо точно: розділення мережі є обставиною, а різні операції й режими можуть мати різні компроміси. У Cure пріоритетом є можливість локальних операцій без синхронного очікування на віддалені центри, але це не тотожне безвідмовності за будь-якого характеру пошкодження чи збоїв.

Моделі узгодженості

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

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

Ізоляція знімка (англ. snapshot isolation) передбачає, що транзакція читає стан, який відповідає певному узгодженому знімку даних, а конфлікти запису виявляють за визначеними правилами. Серіалізовність — сильніша загальна вимога: результат одночасного виконання транзакцій має відповідати певному їх послідовному виконанню. Причинна узгодженість і атомарна видимість змін не встановлюють автоматично серіалізовності.

Вузли, розділи та центри обробки даних

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

На рівні розділу документація виділяє чотири функціональні частини:

• Журнал (log) зберігає оновлення, забезпечуючи основу для відновлення після збоїв.
• Матеріалізатор (materializer) будує потрібні версії об'єктів із журналу, кешує результати й очищує застарілі проміжні дані.
• Менеджер транзакцій приймає запити, координує читання й запис та повертає результат клієнтові.
• Міжцентрова реплікація (InterDC replication) передає оновлення інших центрів обробки даних за розділами.

У науковому прототипі Cure, описаному 2016 року, локальний обмін між вузлами здійснювався засобами Erlang/OTP поверх TCP, а обмін між датацентрами — через ZeroMQ/TCP. Це характеристика саме дослідженої тоді реалізації; її не слід автоматично переносити на кожну наступну версію AntidoteDB. Erlang/OTP забезпечував виконання розподілених серверних компонентів, тоді як правила причинної видимості, транзакцій та злиття CRDT визначалися спеціалізованими алгоритмами бази даних.

Проходження транзакції та реплікація

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

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

Стійкість даних і відновлення

Відмовостійкість доступної служби та довговічність уже підтвердженого запису — різні властивості. В AntidoteDB журнал на диску використовується для відновлення операцій, а конфігурація дозволяє вмикати відновлення даних і метаданих після перезапуску вузла. Проте параметр sync_log має суттєве значення: за документацією, у типовому режимі false дані можуть бути передані операційній системі для запису, але до надсилання відповіді клієнтові їх фізичне збереження на диску ще не гарантоване. Режим true очікує синхронного запису, що збільшує накладні витрати. Тому твердження про безумовну довговічність кожної підтвердженої транзакції для всіх конфігурацій було б неправильним.

CRDT — це типи даних, для яких визначено, як незалежні операції або стани реплік можуть збігатися після обміну змінами. На відміну від загального механізму блокування, семантика CRDT задається самим типом даних: наприклад, паралельні додавання до лічильника підсумовуються, а одночасне додавання й вилучення елемента множини обробляються за наперед визначеним правилом. AntidoteDB надає набір таких типів; клієнт звертається не лише до ключа, а й до типу пов'язаного з ним об'єкта.

Лічильники, регістри та множини

Лічильник підтримує збільшення й зменшення. Якщо два незалежні центри, маючи значення 10, додають відповідно 2 і 3, після надходження обох змін узгоджений результат становитиме 15, а не 12 чи 13. Цей приклад ілюструє визначену семантику лічильника, а не результат вимірювання певного розгортання. Документація також описує «розширений лічильник» (fat counter), який підтримує скидання стану, але може потребувати більше пам'яті, пропорційно до кількості операцій після останнього скидання.

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

Множини дозволяють додавати та вилучати елементи з правилами для одночасних змін. У документації й нативному інтерфейсі наявні, зокрема, варіанти множин з перевагою додавання. Серед інших типів — прапорці з перевагою ввімкнення або вимкнення та цілі значення з окремою операцією призначення.

Вкладені структури

Карти (maps) зберігають за ключами вкладені CRDT-об'єкти. Документація розрізняє карту, до якої можна лише додавати записи (G-Map), карту з перевагою додавання в разі одночасного вилучення (AW-Map) та карту з операцією очищення вкладеного значення при вилученні (RR-Map). У цих типів різні вимоги до можливості скидання вкладених об'єктів і різна ціна зберігання допоміжних позначок. Зокрема, для AW-Map документація попереджає про позначки вилучених ключів, які можуть тривалий час залишатися в стані об'єкта.

Межі автоматичного розв'язання конфліктів

CRDT розв'язують конфлікти на рівні власних операцій, але не гарантують виконання довільного бізнес-правила. Наприклад, якщо два незалежні центри обробки даних одночасно резервують останнє доступне місце, об'єднання двох коректно записаних результатів не може саме собою довести, що загальне число бронювань не перевищило місткості. Для такого обмеження можуть знадобитися інша модель даних, спеціально розроблений обмежений лічильник із розподілом прав або координація між репліками. У документації AntidoteDB наведено приклад обмеженого лічильника; його поведінка не поширюється автоматично на звичайний лічильник чи довільні транзакції.

Причинно узгоджені транзакції Cure

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

У нативному Erlang-інтерфейсі AntidoteDB передбачено інтерактивні транзакції: клієнт відкриває транзакцію, виконує послідовність читань і змін та завершує її фіксацією. Є також статичні транзакції для операцій, які можна передати одним запитом. Під час фіксації інтерфейс може повертати часову позначку — векторний годинник, який клієнт використовує як вихідний знімок наступної транзакції. Отже, підтримання гарантій між послідовними клієнтськими сеансами залежить також від належного використання інтерфейсу.

Сертифікація конфліктів і межі ізоляції

У конфігурації AntidoteDB параметр txn_cert визначає, чи перевіряють конфлікти запису під час завершення транзакції. За типовим значенням true конфлікт може призвести до скасування транзакції; документація пов'язує це з ізоляцією знімка для записів у межах одного центру обробки даних. Прямо зазначено, що записи інших центрів при такій перевірці не враховують. За txn_cert=false сертифікацію не виконують, отже, гарантії щодо локальних конфліктів стають слабшими. Це не дві еквівалентні конфігурації однієї повністю серіалізовної СУБД.

Інший параметр, txn_prot, визначає спосіб формування причинних знімків: документація називає clocksi (Cure, типовий варіант) та gr (GentleRain). GentleRain — інший протокол причинної узгодженості, а не синонім Cure; порівнювати результати їх роботи коректно лише для певної конфігурації й навантаження.

У термінах ACID транзакційна атомарність, ізоляція та довговічність потребують окремого аналізу. Атомарна видимість реплікованих записів не гарантує серіалізовності; перевірка конфліктів в одному центрі не гарантує глобальної ізоляції знімка; а відкладений запис журналу на диск не гарантує довговічності підтвердженої транзакції за раптової втрати вузла. Заявляти про «повні ACID-транзакції» без визначення конкретного режиму AntidoteDB було б некоректно.

Основою доступу до даних є операції над адресованими ключами типізованими CRDT-об'єктами. У документації наведено нативний інтерфейс Erlang і клієнтський інтерфейс із використанням Protocol Buffers. У репозиторії проєкту розміщено або наведено посилання на клієнтські бібліотеки для інших мов, зокрема Python. Наявність клієнтської бібліотеки сама по собі не встановлює тотожних гарантій сеансу в усіх реалізаціях клієнтів.

Інтерфейс передбачає як одноразові операції, так і кілька читань та змін у межах інтерактивної транзакції. Розгортання кількох центрів потребує налаштування зв'язків між ними, а відновлення вузла — врахування параметрів журналу і метаданих. Це функції серверної системи; вони не перетворюють AntidoteDB на повноцінну реляційну СУБД із вбудованим загальним інтерфейсом SQL.

Antidote SQL

Antidote SQL — пов'язана з AntidoteDB дослідницька SQL-надбудова, описана у праці Педру Лопеса, Жуана Соузи, Валтера Балегаса, Карли Феррейри, Сержіу Дуарте, Аннетт Біньюзи, Родрігу Родрігеша та Нуну Прегіси (2019). Її метою було перенести деякі звичні реляційні правила, зокрема обмеження первинних і зовнішніх ключів та перевірки значень, у середовище із вибірковим послабленням узгодженості. Автори описали підходи, за яких частина обмежень забезпечується без глобальної координації, а для суворіших вимог допускається координація. Для надбудови існує окремий репозиторій antidote_aql. Саму наукову пропозицію та її прототип не можна вважати доказом того, що відповідні можливості вбудовані в кожен випуск базової AntidoteDB.

Розробники Cure опублікували вимірювання експериментальної реалізації в статті ICDCS 2016 року. Досліди проводили на платформі Grid'5000 у Ренні: сервери мали два восьмиядерні процесори Intel Xeon E5-2630 v3, по 126 ГБ оперативної пам'яті й підключення до локальної мережі 10 Гбіт/с. Кілька датацентрів моделювали всередині того самого обчислювального майданчика, штучно додаючи 50 мс до міжцентрового обміну; це не були випробування між реальними географічно віддаленими майданчиками. Тести використовували реєстри LWW і CRDT-множини, а навантаження для певних порівнянь становили транзакції з однією операцією.

У тесті масштабування одного центра збільшення кількості серверів із 5 до 25 дало зростання пропускної здатності приблизно у 4,8 раза. Для сценарію з 99 % читань два і три центри по 25 серверів забезпечили відповідно 1,8- і 2,8-кратну сумарну пропускну здатність проти одного центра з 25 серверами. У тих самих експериментах дослідники повідомляли про медіанну затримку читання близько 0,7 мс та затримку записів 1—2 мс. Ці значення характеризують конкретний прототип, апаратне середовище й локальні операції, а не гарантовані характеристики довільного сучасного розгортання AntidoteDB.

Порівняння протоколів у тій самій роботі показало ціну причинної узгодженості: для LWW-регістрів варіант із простою узгодженістю у кінцевому підсумку мав приблизно на 30 % більшу пропускну здатність, ніж Cure, в описаних навантаженнях. При порівнянні типів даних, які потребують об'єднання паралельних операцій, результат залежав від обсягу передаваних метаданих і характеристик оновлень. Отже, швидкість визначалася не лише числом серверів, а й семантикою об'єктів і вимогами до видимості оновлень.

Описані показники — вимірювання авторів протоколу. Праці незалежних дослідників 2019 і 2024 років використовували інші навантаження для перевірки узгодженості, а не для відтворення цих показників швидкодії. Пряме зіставлення їхніх результатів як одного тесту було б методично неправильним.

Дослідження Biswas і Enea (2019)

У рецензованій праці «On the Complexity of Checking Transactional Consistency» Ранадіп Бісвас і Константін Енеа запропонували алгоритми перевірки історій виконання транзакцій на відповідність різним моделям узгодженості й застосували їх, зокрема, до AntidoteDB. Для частини згенерованих історій алгоритм не виявив порушень причинної узгодженості. Проте за інших параметрів навантаження автори знайшли кілька історій, які порушували і причинну узгодженість, і слабшу вимогу атомарного читання (read atomicity).

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

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

Дослідження Plume (2024)

Незалежні дослідники Сі Лю, Лун Ґу, Хенфен Вей та Девід Бейзін розробили Plume — засіб перевірки слабких рівнів транзакційної ізоляції за спостережуваними історіями роботи системи. У статті для OOPSLA 2024 вони перевірили, серед інших систем, AntidoteDB версії 0.2.2 і знайшли нові аномалії, перевіряючи рівень транзакційної причинної узгодженості (TCC). Таблиця дослідження позначає найслабший порушений перевірений рівень як read committed; автори також описують чотири типи аномальних шаблонів для AntidoteDB (TAP-g, TAP-h, TAP-k, TAP-m).

У наведеному прикладі тестове навантаження мало шість сеансів, по 20 транзакцій у кожному й по 20 операцій у транзакції. Клієнтські потоки й сервер бази працювали на одному комп'ютері з процесором Intel Xeon E5-2620 v3 та 64 ГБ пам'яті. Автори повідомили, що команда AntidoteDB визначила джерело одного з виявлених відхилень як помилку клієнта, пов'язану з підтримкою гарантій сеансу; у публікації сказано, що цю проблему виправили. Проте на підставі самої статті не можна встановити точні версії всіх виправлених клієнтських бібліотек або зробити висновок, що будь-які подальші версії сервера за будь-яких умов більше не мають аномалій.

Обидва дослідження демонструють важливу межу між гарантією, визначеною протоколом, фактичною реалізацією сервера та поведінкою клієнтського інтерфейсу. Коректна модель причинної узгодженості не виключає помилок реалізації; навпаки, результати незалежної перевірки конкретної версії не дають підстав приписувати однакові помилки всім майбутнім або минулим версіям.

Інші архітектурні обмеження

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

AntidoteDB розробляли насамперед для застосунків зі спільним змінюваним станом, розподілених між майданчиками: соціальних сервісів, колективної роботи з даними та інших сценаріїв, у яких локальна доступність може бути важливішою за одну глобальну послідовність усіх операцій. У програмі SyncFree подібні класи застосунків наводили як дослідницькі цілі, а не як перелік підтверджених компаній — користувачів AntidoteDB.

Система використовувалася як експериментальна платформа в дослідженні Cure, а пізніше стала об'єктом незалежного тестування коректності. Окремими пов'язаними напрямами були надбудова Antidote SQL та файлові інтерфейси, зокрема Elmerfs, який каталог CRDT-проєктів описує як файлову систему на основі AntidoteDB. Той самий каталог відносить AntidoteDB до розподілених баз даних із підтримкою CRDT і транзакційної причинної узгодженості. Даних для надійної оцінки кількості її незалежних промислових упроваджень використані джерела не надають.

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

У порівнянні з Riak та Apache Cassandra AntidoteDB належить до ширшої родини розподілених NoSQL-систем, але робить особливий акцент на поєднанні CRDT з транзакціями над кількома об'єктами й причинними знімками. У Riak також розвивали підтримку CRDT; це свідчить про спільність одного технічного підходу, але не тотожність транзакційних гарантій. Redis застосовується насамперед як сховище структур даних і кеш, хоча окремі його продукти та конфігурації підтримують механізми розподіленого узгодження. Тому універсальне твердження, що одна з цих систем «краща», без визначеного навантаження та вимог не має змісту.

Інший полюс представляють розподілені SQL-системи, які за допомогою додаткової координації прагнуть сильніших гарантій ізоляції, зокрема CockroachDB. Порівняння з ними стосується насамперед архітектурного компромісу: AntidoteDB намагається зберегти можливість роботи під час розділення зв'язку, тоді як система із серіалізовними транзакціями може бути змушена затримати або відхилити частину операцій. У дослідженні Biswas та Enea системи CockroachDB і AntidoteDB розглядалися саме як об'єкти перевірки різних заявлених моделей узгодженості, а не як учасники одного порівняльного тесту швидкості.

• Akkoorath D. D., Tomsic A. Z., Bravo M., Li Z., Crain T., Bieniusa A., Preguiça N., Shapiro M. Cure: Strong Semantics Meets High Availability and Low Latency // ICDCS. — 2016. — С. 405—414.
• Biswas R., Enea C. On the Complexity of Checking Transactional Consistency // Proceedings of the ACM on Programming Languages. — 2019. — Том 3, OOPSLA, ст. 165.
• Liu S., Gu L., Wei H., Basin D. Plume: Efficient and Complete Black-Box Checking of Weak Isolation Levels // Proceedings of the ACM on Programming Languages. — 2024. — Том 8, OOPSLA2, ст. 302.
• Lopes P., Sousa J., Balegas V., Ferreira C., Duarte S., Bieniusa A., Rodrigues R., Preguiça N. Antidote SQL: Relaxed When Possible, Strict When Necessary. — 2019.