BASE vs ACID

6.1 Битва абревіатур: BASE vs. ACID

Популярні реляційні БД, такі як MySQL, з'явабося якраз на грунті ACID. Але за останні десять років так звані бази NoSQL, які об'єднують під цією назвою кілька дуже різних типів БД, досить непогано справляються і без ACID. Насправді є велика кількість розробників, які працюють з БД NoSQL і анітрохи не запарюються з приводу транзакцій та їх надійності. Давайте розберемося, чи мають рацію вони.

Не можна загалом говорити про БД NoSQL, адже це просто вдала абстракція. БД NoSQL розрізняються між собою і за дизайном підсистем зберігання даних, і навіть за моделями даних: NoSQL - це документо-орієнтована CouchDB, і графова Neo4J. Але якщо говорити про них у контексті транзакцій, то всі вони зазвичай схожі в одному: вони надають обмежені версії атомарності та ізоляції, а значить, не надають гарантії ACID. Щоб зрозуміти, що це означає, відповімо на запитання: а що ж вони пропонують, якщо не ACID? Нічого?

Не зовсім. Адже їм, як і реляційним БД, теж потрібно продавати себе у гарній упаковці. І вони вигадали свою «хімічну» абревіатуру – BASE.

6.2 BASE як антагоніст

І тут я знову піду не по порядку літер, а почну з основного терміну - consistency. Мені доведеться нівелювати ваш ефект впізнавання, бо ця узгодженість має мало спільного з узгодженістю ACID. Проблема з терміном узгодженості полягає в тому, що він використовується в дуже великій кількості контекстів. Натомість ця узгодженість має значно ширший контекст вживання, та й взагалі це саме та узгодженість, про яку йдеться під час обговорення розподілених систем.

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

Багато NoSQL БД відмовляються від гарантії ізоляції та пропонують «узгодженість в кінцевому рахунку» (eventual consistency), згідно з якою ви врешті-решт побачите дійсні дані, але є ймовірність, що ваша транзакція прочитає недійсні значення – тобто тимчасові або частково оновлені, чи застарілі. Можливо, дані стануть узгодженими у «лінивому» режимі під час читання ("lazily at read time").

NoSQL були задумані як БД для аналітики в режимі реального часу, і щоб досягти більшої швидкості, вони пожертвували узгодженістю. А Eric Brewer, той самий хлопець, що вигадав термін BASE, сформулював так звану "CAP-теорему", згідно з якою:

Для будь-якої реалізації розподілених обчислень можливо забезпечити не більше двох із трьох наступних властивостей:

• узгодженість даних ( consistncy ) - дані на різних вузлах (instances) не суперечать один одному;
• доступність ( availability ) - будь-який запит до розподіленої системи завершується коректним відгуком, проте без гарантії, що відповіді всіх вузлів системи збігаються;
• стійкість до поділу (розподілу) (partition tolerance ) — Навіть якщо між вузлами немає зв'язку, вони продовжують працювати незалежно один від одного.

Якщо вам потрібно дуже просте пояснення CAP, то тримайте.

Є думки про те, що теорема CAP не працює, і взагалі сформульована надто абстрактно. Так чи інакше, бази NoSQL найчастіше відмовляються від узгодженості в контексті теореми CAP, що описує таку ситуацію: дані були оновлені в кластері з кількома instances, але зміни були синхронізовані ще не на всіх instances. Пам'ятайте, я згадував приклад з DynamoDB, яка сказала мені: твої зміни стали durable – ось тобі HTTP 200 – але зміни я побачив лише через 10 секунд? Ще один приклад із повсякденного життя розробника – DNS, система доменних імен. Якщо хтось не знає, то це саме той «словник», який переводить http(s)-адресаи в IP-адресаи.

Оновлений DNS-запис поширюється серверами відповідно до налаштувань інтервалів кешування – тому оновлення стають помітними не моментально. Так от, подібна тимчасова неузгодженість (тобто узгодженість у кінцевому рахунку) може статися і з кластером реляційної БД (скажімо, MySQL) – адже ця узгодженість не має нічого спільного з узгодженістю з ACID. Тому важливо розуміти, що в цьому сенсі БД SQL і NoSQL навряд чи сильно відрізнятимуться, якщо мова йде про кілька instances в кластері.

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

Бази даних, що не надають гарантії ACID, NoSQL мають так званий «м'який стан» (“soft state”) внаслідок моделі узгодженості в кінцевому рахунку, що означає наступне: стан системи може змінюватися з часом, навіть без вступних даних (“input”). Проте такі системи прагнуть забезпечити більшу доступність. Забезпечити стовідсоткову доступність – нетривіальне завдання, тому йдеться про «базову доступність». А разом ці три поняття: "базова доступність" ("basically available"), "м'який стан" ("soft state") і "узгодженість в кінцевому рахунку" ("eventual consistency") формують абревіатуру BASE.

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

6.3 Виходить, бази даних BASE зовсім не виконують критерії ACID?

По суті, чим відрізняються БД ACID від не ACID, так це тим, що не ACID фактично відмовляються від забезпечення ізоляції. Це важливо розуміти. Але ще важливіше читати документацію БД та тестувати їх так, як це роблять хлопці із проекту Hermitage. Не так важливо, як саме називають своє дітище творці тієї чи іншої БД - ACID або BASE, CAP або CAP. Важливо те, що надає та чи інша БД.

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

• БД не надає гарантії атомарності. Хоча деякі бази даних NoSQL пропонують окрему API для атомарних операцій (наприклад, DynamoDB);

• БД не надає гарантії ізоляції. Це може означати, наприклад, що БД запише дані не в порядку, в якому вони надійшли на запис.

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

Щоб порівнювати різні БД, окрім іншого, потрібно знати, які структури даних лежать в основі підсистеми зберігання та отримання даних конкретної БД. Коротко: різні БД мають різні реалізації індексації, тобто організації доступу до даних. Деякі їх дозволяють швидше писати дані, інші – швидше їх читати. Але не можна сказати, що якісь структури даних роблять тривалість вище або нижче.

6.4 як різні БД індексують дані, і як це впливає на тривалість, і не тільки

Є два основні підходи до зберігання та пошуку даних.

Найпростіший спосіб зберігати дані – це додавання операцій до кінця файлу за принципом журналу (тобто, завжди відбувається операція append): неважливо, хочемо ми додати, змінити чи видалити дані – всі операції CRUD просто записуються у журнал. Шукати за журналом – заняття неефективне, і ось де на допомогу приходить індекс – особлива структура даних, яка зберігає метадані про те, де зберігаються дані. Найпростіша стратегія індексації для журналів – хеш-таблиця (hash map), яка відстежує ключі та значення. Значеннями будуть посилання на байтове зміщення для даних, записаних всередину файлу, яка і є журналом (log) і зберігається на диску. Ця структура даних повністю зберігається у пам'яті, тоді як самі дані – на диску, і називається LSM-деревом (log structured merge).

Ви, мабуть, запитали себе: якщо ми весь час пишемо наші операції в журнал, то він же непомірно зростатиме? Так, і тому була придумана техніка ущільнення (“compaction”), яка з якоюсь періодичністю «підчищає» дані, а саме – залишає для кожного ключа лише найбільш актуальне значення або видаляє його. А якщо мати не один журнал на диску, а кілька, і всі вони будуть відсортовані, то ми отримаємо нову структуру даних під назвою SSTable (“sorted string table”), і це, безсумнівно, покращить нашу продуктивність. Якщо ж ми захочемо сортувати в пам'яті, то отримаємо схожу структуру - так звану таблицю MemTable, але з нею проблема в тому, що якщо відбувається фатальний збій БД, записані пізніше всього дані (що знаходяться в MemTable, але ще не записані на диск) губляться . Власне,

Інший підхід до індексації ґрунтується на B-деревах (“B-trees”). У B-дереві дані записуються на диск сторінками фіксованого розміру. Ці блоки даних часто мають розмір близько 4 КБ і мають пари ключ-значення відсортовані за ключом. Один вузол B-дерева схожий на масив із посиланнями на діапазон сторінок. Макс. кількість посилань у масиві називається фактором розгалуження. Кожен діапазон сторінок – це ще один вузол B-дерева із посиланнями на інші діапазони сторінок.

Зрештою, на рівні аркуша ви знайдете окремі сторінки. Ця ідея подібна до вказівників у мовах програмування низького рівня, за винятком того, що ці посилання на сторінки зберігаються на диску, а не в пам'яті. Коли в БД відбуваються INSERTs і DELETEs, то якийсь вузол може розбитися на два піддерева, щоб відповідати коефіцієнту розгалуження. Якщо база даних вийде з ладу з будь-якої причини в середині процесу, цілісність даних може порушитися. Щоб запобігти такому випадку, використовуючі B-дерева БД ведуть журнал попереджувального запису (write-ahead log, або WAL), в якому записується кожна окрема транзакція. Цей WAL використовується для відновлення стану B-дерева у разі його пошкодження. І здається, що саме це робить B-дерева БД, що використовують, краще в плані durability. Але заснованих на LSM БД також можуть вести файл, що по суті виконує таку ж функцію, як WAL. Тому я повторю те, що вже говорив, і, можливо, неодноразово: розбирайтеся в механізмах роботи обраної вами БД.

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

Водночас дизайн індексу безпосередньо відбивається на продуктивності БД. При LSM-дереві запис на диск здійснюється послідовно, а B-дерева викликають множинні випадкові доступи до диска, тому операції запису відбуваються у LSM швидше, ніж у B-дерев. Різниця особливо істотна для жорстких жорстких дисків (HDD), на яких послідовні операції запису працюють набагато швидше, ніж довільні. Читання виконується повільніше на LSM-деревах тому, що доводиться переглядати кілька різних структур даних і SS-таблиць, що знаходяться на різних стадіях ущільнення. Більш детально це виглядає так. Якщо ми зробимо простий запит до бази даних з LSM, ми спочатку знайдемо ключ у MemTable. Якщо його там немає, ми дивимося в останню SSTable; якщо немає і там, то ми дивимося в передостанню SSTable і т.д. Якщо ключ, що запитується, не існує, то при LSM ми це дізнаємося в останню чергу. LSM-дерева використовуються, наприклад, у: LevelDB, RocksDB, Cassandra та HBase.

Я так докладно це описую, щоб ви зрозуміли, що при виборі БД потрібно враховувати багато різних речей: наприклад, чи розраховуєте ви більше писати або читати дані. І це я ще не згадав різницю в моделях даних (чи потрібно вам робити обхід даних, як дозволяє графова модель? Чи є у ваших даних взагалі якісь відносини між різними одиницями – тоді вам на виручку прийдуть реляційні БД?), і 2 види схеми даних – при записі (як у багатьох NoSQL) та читанні (як у реляційних).

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

6.5 Як працюють in-memory DB

Між іншим, окрім БД, що записують на диск, є ще так звані "in-memory" БД, які працюють переважно з RAM. Коротко: наявні в пам'яті БД зазвичай пропонують нижчу тривалість для більшої швидкості запису і читання, але це може підходити для деяких додатків.

Справа в тому, що пам'ять RAM довгий час була дорожчою, ніж диски, але останнім часом вона почала стрімко дешевшати, що і породило новий вид БД - що логічно, враховуючи швидкість читання та запису даних з RAM. Але ви справедливо запитаєте: а що із збереженням даних у цих БД? Тут знову ж таки треба дивитися на деталі реалізації. Загалом розробники таких БД пропонують такі механізми:

• Можна використовувати RAM, що живиться від акумуляторів;
• Можна записувати на диск журнали змін (щось на кшталт згаданих вище WAL), але з самі дані;
• Можна періодично записувати на диск копії стану БД (що без використання інших опцій не дає гарантії, а лише покращує тривалість);
• Можна проводити реплікацію стану оперативної пам'яті інші машини.

Наприклад, in-memory БД Redis, яка в основному використовується як черга повідомлень або кеш, бракує саме durability з ACID: вона не гарантує, що успішно виконана команда збережеться на диску, оскільки Redis скидає дані на диск (якщо у вас включена збереженість) тільки асинхронно через певні інтервали.

Втім, не для всіх програм це критично: я знайшов приклад кооперативного онлайн-редактора EtherPad, який робив flush раз на 1-2 секунди, і потенційно користувач міг втратити пару літер або слово, що навряд чи було критичним. В іншому ж, оскільки наявні в пам'яті БД хороші тим, що вони надають моделі даних, які було б важко реалізувати за допомогою дискових індексів, Redis можна використовувати для реалізації транзакцій - її черга за пріоритетом дозволяє це зробити.