BASE vs ACID

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

В химии pH измеряет относительную кислотность водного раствора.
Шкала pH простирается от 0 (сильнокислые вещества) до 14 (сильнощелочные вещества);
чистая вода при температуре 25°C имеет pH 7 и является нейтральной.

Инженеры взяли эту метафору, чтобы сравнить базы данных по надёжности транзакций.
Чем ближе база данных к "щелочи" ("BASE"), тем менее надёжны транзакции.

Популярные реляционные базы данных, такие как MySQL, появились на почве ACID. За последние десять лет появились так называемые базы NoSQL, которые объединяют под себя несколько разных типов баз данных. Они хорошо работают и без ACID. Многие разработчики работают с NoSQL и не задумываются о транзакциях и их надёжности. Давайте разберёмся, правы ли они.

Нельзя общими словами говорить о NoSQL, так как это просто удачная абстракция. База данных NoSQL отличаются друг от друга по дизайну подсистем хранения данных и моделям данных: например, документо-ориентированная CouchDB и графовая Neo4J. Однако, если говорить о них в контексте транзакций, то обычно они похожи друг на друга в одном аспекте: они предоставляют ограниченные версии атомарности и изоляции, а значит, не предоставляют гарантий ACID. Чтобы понять, что это означает, давайте разберемся с вопросом: что же они предлагают, если не ACID? Ничего?

Не совсем. Так же им надо продать себя в привлекательном виде. Они придумали свою сокращенную название - BASE.

6.2 BASE как антагонист

И тут я снова не по порядку букв, а сразу с основополагающего термина – consistency. Этот термин имеет мало общего с согласованностью из ACID. Проблема заключается в том, что он употребляется в слишком большом количестве контекстов. Однако эта согласованность имеет более широкое применение и она именно та, о которой идёт речь при рассмотрении распределённых систем.

Реляционные базы данных, о которых мы говорили выше, предоставляют разные уровни изоляции транзакций. Самые строгие из них гарантируют, что одна транзакция не сможет увидеть недействительные изменения, осуществлённые другой транзакцией.

Например, если вы стоите на кассе в магазине, и в этот момент с вашего счёта снимутся деньги за квартплату, а транзакция с переводом денег за квартплату провалится, и ваш счёт снова примет прежнее значение (деньги не спишутся), то ваша транзакция оплаты на кассе не заметит всех этих телодвижений. Это связано с тем, что в соответствии с требованиями изоляции транзакций, временные изменения недействительной транзакции не могут быть замечены другими транзакциями.

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

NoSQL были разработаны для аналитики в режиме реального времени, и чтобы достичь большей скорости, они принесли в жертву согласованность. Эрик Бривер, тот же человек, который придумал термин BASE, сформулировал так называемую "CAP-теорему", согласно которой:

Для любой реализации распределённых вычислений можно обеспечить не более двух из трёх следующих свойств:

• согласованность данных (consistency) — данные на разных узлах (instances) не противоречат друг другу;
• доступность (availability) — любой запрос к распределённой системе завершается корректным откликом, однако без гарантии, что ответы всех узлов системы совпадают;
• устойчивость к разделению/распределению (partition tolerance) — Даже если между узлами нет связи, они продолжают работать независимо друг от друга.

Если вам нужно простое объяснение CAP, то вот оно:

Существуют мнения, что теорема CAP не работает или была сформулирована недостаточно конкретно. Тем не менее, базы данных NoSQL часто отказываются от согласованности в рамках теоремы CAP. Это означает, что данные были обновлены на нескольких экземплярах кластера, но изменения ещё не были синхронизированы на всех экземплярах. Например, DynamoDB может сообщить: ваши изменения стали durable, и вы получили HTTP 200, но изменения были видны лишь через 10 секунд. Другой пример из повседневной жизни разработчика – это система доменных имён (DNS), которая преобразует http(s)-адреса в IP-адреса.

Обновлённая DNS-запись распространяется по серверам согласно настройкам интервалов кэширования, поэтому обновления становятся заметными не моментально. Таким образом, временная несогласованность (которая в конечном счёте приводит к согласованности) может произойти и в кластере реляционной базы данных (например, MySQL), поскольку эта согласованность не связана с понятием ACID. Поэтому важно понимать, что в этом смысле SQL и NoSQL вряд ли будут значительно отличаться, если речь идёт о нескольких экземплярах в кластере.

Помимо этого, согласованность в конечном счёте означает, что запросы на запись будут осуществлены не в порядке поступления: то есть, все данные будут записаны, но значение, которое будет принято в конечном счёте, не будет тем, что поступило последним в очередь на запись.

Базы данных NoSQL, не предоставляющие гарантии ACID, имеют «мягкое состояние» (“soft state”) вследствие модели согласованности в конечном счёте. Это означает, что состояние системы может меняться без вводных данных. Однако такие системы стремятся обеспечить большую доступность, называемую «базовой доступностью». Эти три понятия - «базовая доступность» ("basically available"), «мягкое состояние» ("soft state") и «согласованность в конечном счёте» ("eventual consistency") - формируют аббревиатуру BASE. Однако это больше пустая маркетинговая обёртка, чем ACID, и может запутать разработчиков. Поэтому лучше вернуться к понятию изоляции.

6.3 Получается, базы данных BASE совсем не выполняют критерии ACID?

В основе отличия базы данных ACID от не-ACID лежит то, что не-ACID отказываются от изоляции. Важно понимать это. Но ещё важнее читать документацию и тестировать их, как это делают ребята из проекта Hermitage. Неважно, как называет своё детище создатель той или иной базы данных – ACID или BASE, CAP или не CAP. Важно, что предоставляет та или иная база данных.

Если создатели базы данных утверждают, что она предоставляет гарантии ACID, то, наверное, у этого есть основания. Но лучше самому протестировать, чтобы узнать, насколько это верно и в какой степени. Если же они заявляют, что их база данных не предоставляет такие гарантии, то это может означать разные вещи.

• База данных не гарантирует атомарность. Однако некоторые NoSQL базы данных предоставляют отдельный API для атомарных операций (например, DynamoDB).
• База данных не гарантирует изоляцию. Это может означать, например, что данные могут быть записаны в другом порядке, чем при их поступлении на запись.

Чтобы сравнить разные базы данных по гарантии durability, нужно знать, какие структуры данных используются для хранения и извлечения данных. Некоторые из них позволяют быстрее записывать данные, другие – быстрее читать. Но нельзя обще сказать, что определенные структуры данных делают durability выше или ниже.

6.4 Как разные базы данных индексируют данные, и как это влияет на durability, и не только

Существуют два основных подхода к хранению и поиску данных.

Для сохранения данных используется добавление операций в конец файла, так как все операции CRUD записываются в журнал. Для быстрого поиска используется индекс - структура данных, которая хранит метаданные. Самым простым индексом является хэш-таблица, которая связывает ключ и значение. Значения - это смещения данных в файле-журнале, который хранится на диске. Эта структура данных называется LSM-деревом и хранится в памяти, а данные на диске.

Возможно, вы спросили себя: если мы записываем действия в журнал, не будет ли он слишком большим? Да, поэтому была придумана техника сжатия ("compaction") для удаления или оставления лишь самого актуального значения для каждого ключа. Если мы будем использовать несколько журналов, отсортированных на диске, то создадим структуру данных, известную как SSTable («sorted string table»), что повысит производительность. Если же мы попытаемся сортировать данные в памяти, то получим так называемую таблицу MemTable. Но данные, записанные позже всего (находящиеся в MemTable, но еще не записанные на диск), будут потеряны при фатальном сбое базы. Вот и проблема с durability у базы данных, основанных на LSM-деревьях.

Другой подход к индексации основывается на 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. Если ключ не существует, то мы это узнаем последней.

LSM-деревья используются в:

• LevelDB
• RocksDB
• Cassandra
• HBase

Я так подробно описываю это всё, чтобы вы поняли, какие вещи нужно учитывать при выборе базы данных: например, больше писать или читать данные. Также необходимо рассмотреть различия в моделях данных (нужно ли делать обход данных, как позволяет графовая модель? Есть ли какие-то отношения между различными единицами данных? Нужно ли использовать при записи или чтении данных разные схемы?) и стойкость данных. Любая база данных, записывающая на диск, может предоставить хорошие гарантии стойкости данных, но нужно проанализировать каждую базу отдельно.

6.5 Как работают in-memory DB

Между прочим, помимо баз, записывающих данные на диск, есть также базы в памяти, иногда называемые "in-memory". Они работают преимущественно с RAM и предлагают более низкую durability в обмен на более высокую скорость записи и чтения. Это может стать полезным для многих приложений, для которых время отклика имеет значение. Например, это может использоваться для поисковых запросов или анализа больших объёмов данных, требующих быстрой обработки.

Дело в том, что память RAM долгое время была дороже, чем диски, но в последнее время стала дешевле. Это привело к появлению нового вида баз данных, благодаря быстрому чтению и записи данных из RAM. Вопрос: а как с сохранностью данных у этих баз данных? Разработчики предлагают различные механизмы для обеспечения сохранности.

• Использовать оперативную память, питаемую от аккумуляторов.
• Записывать на диск журналы изменений (например, такие как упомянутые выше WAL), но не сами данные.
• ериодически записывать на диск копии состояния базы данных (что без использования других опций не даёт гарантий, а лишь улучшает надёжность);
• Реплицировать состояние оперативной памяти на другие машины.

Например, база данных Redis в оперативной памяти, которая обычно используется как очередь сообщений или кэш, не обеспечивает долговременность из ACID: она не гарантирует, что успешно выполненная команда будет сохранена на диске, поскольку Redis сохраняет данные на диск (если это включено) только асинхронно, периодически..

Однако не для всех приложений это важно. Например, EtherPad - онлайн-редактор для коллективного использования - делал flush раз в 1-2 секунды. Это могло привести к потере нескольких букв или слов, но это не критично. Redis хороша тем, что предоставляет модель данных, которую трудно реализовать с помощью дисков. Она также позволяет выполнять транзакции через свою очередь по приоритетам.