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-теорему", согласно которой:

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

• согласованность данных (consistency) — данные на разных узлах (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);

• БД не предоставляет гарантии изоляции. Это может означать, например, что БД запишет данные не в том порядке, в котором они поступили на запись.

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

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

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

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

Самый простой способ сохранять данные – это добавление операций в конец файла по принципу журнала (то есть, всегда происходит операция append): неважно, хотим ли мы добавить, изменить или удалить данные – все операции CRUD просто записываются в журнал. Искать по журналу – занятие неэффективное, и вот где на помощь приходит индекс – особая структура данных, которая хранит метаданные о том, где именно хранятся данные. Простейшая стратегия индексация для журналов – хэш-таблица (hash map), которая отслеживает ключи и значения. Значениями будут ссылки на байтовое смещение для данных, записанных внутрь файла, которая и представляет из себя журнал (log) и хранится на диске. Эта структура данных целиком хранится в памяти, в то время как сами данные – на диске, и называется LSM-деревом (log structured merge).

Вы, наверное, задались вопросом: если мы всё время пишем наши операции в журнал, то он же будет непомерно расти? Да, и поэтому была придумана техника уплотнения (“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; если нет и там, то мы смотрим в предпоследнюю SSTable и т.д. Если запрашиваемый ключ не существует, то при LSM мы это узнаем в последнюю очередь. LSM-деревья используются, например, в: LevelDB, RocksDB, Cassandra и HBase.

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

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

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

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

Дело в том, что память RAM долгое время была дороже, чем диски, но в последнее время она начала стремительно дешеветь, что и породило новый вид БД – что логично, учитывая быстроту чтения и записи данных из RAM. Но вы справедливо спросите: а что с сохранностью данных у этих БД? Тут опять-таки нужно смотреть на детали реализации. В целом, разработчики таких БД предлагают следующие механизмы:

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

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

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