Блеск и нищета key-value базы данных LMDB в приложениях для iOS05.06.2020 11:47

Осенью 2019 года в iOS команде Облака Mail.ru произошло долгожданное событие. Основной базой данных для персистентного хранения состояния приложения стала весьма экзотическая для мобильного мира Lightning Memory-Mapped Database (LMDB). Под катом вашему вниманию предлагается её подробный обзор в четырех частях. Сначала поговорим о причинах столь нетривиального и трудного выбора. Затем перейдем к рассмотрению трёх китов в основе архитектуры LMDB: отображённые в память файлы, B±дерево, copy-on-write подход для реализации транзакционности и мультиверсионности. Наконец, на сладкое — практическая часть. В ней рассмотрим, как поверх низкоуровневого key-value API спроектировать и реализовать схему базы с несколькими таблицами, включая индексную.​

1. Мотивация внедрения
2. Позиционирование LMDB
3. Три кита LMDB
   3.1 Кит №1. Memory-mapped files
   3.2 Кит №2. B±дерево
   3.3 Кит №3. Copy-on-write
4. Проектирование схемы данных поверх key-value API
   4.1 Базовые абстракции
   4.2 Моделирование таблиц
   4.4 Моделирование связей между таблицами

Однажды году так в 2015 мы озаботились снятием метрики, как часто интерфейс нашего приложения лагает. Занялись мы этим не просто так. У нас участились жалобы на то, что иногда приложение перестаёт реагировать на действия пользователя: кнопки не нажимаются, списки не скролятся и т.п. О механике измерений я рассказывал на AvitoTech, поэтому здесь привожу лишь порядок цифр.

Результаты измерений стали для нас холодным душем. Оказалось, что проблем, вызванных зависаниями, гораздо больше, чем каких-либо других. Если до осознания этого факта главным техническим показателем качества был crash free, то после фокус сместился на freeze free.

Построив дашборд с зависаниями и проведя количественный и качественный анализ их причин, стал понятен главный враг — тяжёлая бизнес-логика, исполняющаяся в главном потоке приложения. Естественной реакцией на это безобразие стало жгучее желание распихать её по рабочим потокам. Для системного решения этой задачи мы прибегли к многопоточной архитектуре на основе легковесных акторов. Её адаптации для мира iOS я посвятил два тредика в коллективном твиттере и статью на Хабре. В рамках же текущего повествования хочу подчеркнуть те аспекты решения, которые повлияли на выбор базы данных.​

​Акторная модель организации системы предполагает, что многопоточность становится её второй сутью. Объекты модели в ней любят пересекать границы потоков. И делают они это не иногда и кое-где, а практически постоянно и везде.​

​База данных является одним из краеугольных компонентов на представленной схеме. Её основной задачей является реализация макропаттерна Shared Database. Если в энтерпрайзном мире с его помощью организовывают синхронизацию данных между сервисами, то в случае акторной архитектуры — данные между потоками. Таким образом, нам понадобилась такая база данных, работа с которой в многопоточной среде не вызывает даже минимальных сложностей. В частности, это означает, что полученные из неё объекты должны быть как минимум потокобезопасными, а в идеале и вовсе немутабельными. Как известно, последние можно использовать одновременно из нескольких потоков, не прибегая к каким бы то ни было блокировкам, что благостно сказывается на производительности.

Вторым значимым фактором, повлиявшим на выбор базы данных, стало наше облачное API. Оно было вдохновлено подходом к синхронизации, принятой на вооружение в git. Как и он мы целились в offline-first API, которое для облачных клиентов выглядит более чем уместно. Предполагалось, что они будут лишь однажды выкачивать полное состояние облака, а затем синхронизация в подавляющем числе случаев будет происходить через накатывание изменений. Увы, эта возможность всё ещё находится лишь в теоретической зоне, а на практике работать с патчами клиенты так и не научились. Тому есть ряд объективных причин, которые, дабы не затягивать введение, оставим за скобками. Сейчас же гораздо больший интерес представляют поучительные итоги урока о том, что происходит когда API сказало «А», а его потребитель не сказал «Б».

Так вот, если вы представите себе git, который при выполнении команды pull вместо применения патчей к локальному снапшоту сравнивает его полное состояние с полным же серверным, то у вас будет достаточно точное представление, как происходит синхронизация в облачных клиентах. Несложно догадаться, что для её осуществления необходимо аллоцировать в памяти два DOM-дерева с метаинформацией обо всех серверных и локальных файлах. Получается, что если пользователь хранит в облаке 500 тысяч файлов, то для его синхронизации необходимо воссоздать и уничтожить два дерева с 1 миллионом узлов. А ведь каждый узел — это агрегат, содержащий в себе граф подобъектов. В этом свете итоги профилирования оказались ожидаемы. Обнаружилось, что даже без учёта алгоритмики слияния в копеечку влетает уже сама процедура создания и последующего разрушения огромного количества мелких объектов.​ Положение усугубляется тем, что базовая операция синхронизации включена в большое количество пользовательских сценариев. Как итог фиксируем второй важный критерий в выборе базы данных — возможность реализации операций CRUD без динамической аллокации объектов.

Другие требования более традиционны и их список целиком выглядит следующим образом.

1. Потокобезопасность.
2. Мультипроцессность. Продиктована желанием использовать один и тот же инстанс базы данных для синхронизации состояния не только между потоками, но и между основным приложением и экстеншенами iOS.
3. Возможность представлять хранимые сущности в виде немутабельных объектов.​
4. Отсутствие динамических аллокаций в рамках операций CRUD.
5. Поддержка транзакциями базовых свойств ACID: атомарность, консистентность, изолированность и надёжность.
6. Скорость на наиболее популярных кейсах.

Хорошим выбором с таким набором требований был и остаётся SQLite. Однако в рамках изучения альтернатив, мне под руку попалась книжка «Getting Started with LevelDB». Под её руководством был написан бенчмарк, сравнивающий скорость работы с разными базами данных в рамках реальных облачных сценариев. Результат превзошёл самые смелые ожидания. На самых популярных кейсах — получение курсора на сортированный список всех файлов и сортированный список всех файлов для заданной директории — LMDB оказалась быстрее SQLite в 10 раз. Выбор стал очевиден.

LMDB — это библиотечка, очень небольшая (всего 10К строк), реализующая самый нижний основополагающий слой баз данных — хранилище.

Приведенная схема показывает, что сравнивать LMDB с SQLite, который реализует ещё и более высокие уровни, в общем-то не корректнее, чем SQLite с Core Data. В качестве равноправных конкурентов будет более справедливым приводить такие же движки-хранилища — BerkeleyDB, LevelDB, Sophia, RocksDB и др. Есть даже разработки, где LMDB выступает в качестве компонента storage engine для SQLite. Первым такой эксперимент в 2012 году провел автор LMDB Howard Chu. Результаты оказались настолько интригующими, что его начинание было подхвачено энтузиастами OSS, и нашло своё продолжение в лице LumoSQL. В январе 2020 автор этого проекта Den Shearer презентовал его на LinuxConfAu.

Главное применение LMDB находит в качестве движка для прикладных баз данных. Своим появлением библиотека обязана разработчикам OpenLDAP, которые были сильно не удовлетворены BerkeleyDB в качестве основы своего проекта. Оттолкнувшись от скромной библиотечки btree, Howard Chu смог создать одну из самых популярных в наше время альтернатив. Этой истории, а также внутреннему устройству LMDB он посвятил свой очень крутой доклад «The Lightning Memory-mapped Database». Хорошим примером покорения хранилища поделился Леонид Юрьев (aka yleo) из Positive Technologies в своём докладе на Highload 2015 «Движок LMDB — особенный чемпион». В нём он рассказывает об LMDB в контексте похожей задачи реализации ReOpenLDAP, а сравнительной критике подверглась уже LevelDB. По итогам внедрения у Positive Technologies даже появился активно развивающийся форк MDBX с очень вкусными фичами, оптимизациями и багфиксами.

LMDB нередко используется и в качестве хранилища as is. Например, браузер Mozilla Firefox выбрал его для целого ряда нужд, а, начиная с 9 версии, Xcode предпочёл его SQLite для хранения индексов.

Движок засветился и в мире мобильной разработки. Следы его использования можно найти в iOS клиенте для Telegram. LinkedIn пошёл ещё дальше и выбрал LMDB хранилищем по умолчанию для доморощенного фреймворка кеширования данных Rocket Data, о чём поведал в своей статье в 2016 году.

LMDB успешно борется за место под солнцем в нише, оставленной BerkeleyDB после перехода под контроль Oracle. Библиотеку любят за скорость и надёжность даже в сравнении с себе подобными. Как известно, бесплатных обедов не бывает, и хочется подчеркнуть trade-off, с которым придётся столкнуться при выборе между LMDB и SQLite. Схема выше наглядно демонстрирует, за счёт чего достигается повышенная скорость. Во-первых, мы не платим за дополнительные слои абстракции поверх дискового хранилища. Понятное дело, в хорошей архитектуре без них всё равно не обойтись, и они неизбежно появятся в коде приложения, однако они будут гораздо тоньше. В них не будет фич, которые не востребованы конкретным приложением, например, поддержки запросов на языке SQL. Во-вторых, появляется возможность оптимально реализовать маппинг прикладных операций на запросы к дисковому хранилищу. Если SQLite в своей работе исходит из среднестатистических потребностей среднестатистического приложения, то вы как прикладной разработчик прекрасно осведомлены об основных сценариях нагрузки. За более производительное решение придётся заплатить возросшим ценником как на разработку первоначального решения, так и на его последующую поддержку.

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

1. Отображённые в память файлы в качестве механизма работы с диском и синхронизации внутренних структур данных.
2. B±дерево в качестве организации структуры хранимых данных.
3. Copy-on-write в качестве подхода для обеспечения ACID-свойств транзакций и мультиверсионности.

Кит №1. Memory-mapped files

Отображённые в память файлы — настолько важный архитектурный элемент, что они даже фигурируют в названии хранилища. Вопросы кеширования и синхронизации доступа к хранимой информации целиком и полностью отданы на откуп операционной системе. LMDB не содержит внутри себя каких бы то ни было кешей. Это осознанное решение автора, поскольку чтение данных напрямую из отображённых файлов позволяет срезать множество углов в реализации движка. Ниже привожу далеко не полный список некоторых из них.

1. Поддержание консистентности данных в хранилище при работе с ним из нескольких процессов становится обязанностью операционной системы. В следующем разделе данная механика рассмотрена в подробностях и с картинками.
2. Отсутствие кешей полностью избавляет LMDB от накладных расходов, связанных с динамическими аллокациями. Чтение данных на практике представляет собой установку указателя на правильный адрес в виртуальной памяти и не более. Звучит как фантастика, но в исходниках хранилища все вызовы сalloc сосредоточены в функции конфигурирования хранилища.
3. Отсутствие кешей означает и отсутствие блокировок, связанных с синхронизацией к их доступу. Читатели, которых одновременно может существовать произвольное количество, не встречают на своём пути к данным ни единого мьютекса. За счёт этого скорость чтения имеет идеальную линейную масштабируемость по количеству CPU. В LMDB синхронизации подвергаются лишь модифицирующие операции. Писатель в каждый момент времени может быть только один.
4. Минимум логики кеширования и синхронизации избавляет код от крайне сложного вида ошибок, связанных с работой в многопоточной среде. На конференции Usenix OSDI 2014 было два интересных исследования баз данных: «All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications» и «Torturing Databases for Fun and Profit». Из них можно почерпнуть информацию как о беспрецедентной надёжности LMDB, так и о практически безупречной реализации ACID-свойств транзакций, превосходящей оную в том же SQLite.
5. Минималистичность LMDB позволяет машинному представлению её кода полностью размещаться в L1-кэше процессора с вытекающими отсюда скоростными характеристиками.

К сожалению, в iOS с отображёнными в память файлами всё не так безоблачно, как хотелось бы. Чтобы поговорить о связанных с ними недостатках более осознанно, необходимо вспомнить общие принципы реализации этого механизма в операционных системах.

Общие сведения об отображённых в память файлах

С каждым исполняемым приложением операционная система ассоциирует сущность под названием процесс. Каждому процессу выделяется непрерывный интервал адресов, в котором он размещает всё необходимое ему для работы. В самых нижних адресах располагаются секции с кодом и захардкоженными данными и ресурсами. Далее идет растущий вверх блок динамического адресного пространства, хорошо известный нам под именем heap. В нём содержаться адреса сущностей, которые появляются в процессе работы программы. Вверху располагается область памяти, используемая стеком приложения. Он то растет, то сжимается, другими словами его размер также имеет динамическую природу. Чтобы стек и heap не толкались и не мешали друг другу, они разведены по разным концам адресного пространства.​ Между двумя динамическими секциями вверху и внизу есть дырка. Адреса в этом срединном участке операционная система использует для ассоциации с процессом самых разных сущностей. В частности, она может поставить в соответствие некому непрерывному набору адресов — файл на диске. Такой файл называется отображённым в память.​

Выделенное процессу адресное пространство огромно. Теоретически количество адресов ограничено лишь размером указателя, определяющегося битностью системы. Если бы ему 1-в-1 была сопоставлена физическая память, то первый же процесс сожрал бы всю оперативу, и ни о какой многозадачности не могло бы идти и речи.​

​Однако из своего опыта мы знаем, что современные операционные системы могут одновременно исполнять сколь угодно много процессов. Это возможно благодаря тому, что они только лишь на бумаге выделяют процессам кучу памяти, а на деле загружают в основную физическую память только лишь ту часть, которая востребована здесь и сейчас. Поэтому проассоциированная с процессом память называется виртуальной.

Операционная система организует виртуальную и физическую память в виде страниц определенного размера. Как только некая страница виртуальной памяти оказалась востребована, операционная система загружает её в физическую память и проставляет между ними соответствие в специальной таблице. Если свободные слоты отсутствуют, то одна из ранее загруженных страниц копируется на диск, а востребованная встаёт на её место. Эта процедура, к которой мы вскоре вернёмся, называется свопингом (swapping). Рисунок ниже иллюстрирует описанный процесс. На нём страница А с адресом 0 была загружена и размещена на странице основной памяти с адресом 4. Сей факт нашёл свое отражение в таблице соответствий в ячейке номер 0.​

С отображёнными в память файлами история ровно такая же. Логически они якобы непрерывно и целиком размещаются в виртуальном адресном пространстве. Однако в физическую память они попадают постранично и лишь по требованию. Модификация таких страниц синхронизируется с файлом на диске. Таким образом можно выполнять файловый ввод/вывод, просто работая с байтами в памяти, — все изменения будут автоматически перенесены ядром операционки к исходному файлу.​
​
Изображение ниже демонстрирует, как LMDB синхронизирует своё состояние при работе с базой данных из разных процессов. Замапливая виртуальную память разных процессов на один и тот же файл, де-факто мы обязуем операционную систему транзитивно синхронизировать между собой определенные блоки их адресных пространств, куда и смотрит LMDB.​
​

Важный нюанс состоит в том, что LMDB по умолчанию модифицирует файл с данными через механизм системного вызова write, а сам файл отображает в режиме read-only. У такого подхода есть два важных следствия.

Первое следствие — общее для всех операционных систем. Его суть в добавлении защиты от непреднамеренного повреждения базы данных некорректным кодом. Как известно, исполняемые инструкции процесса вольны обращаться к данным из любого места его адресного пространства. В то же время, как мы только что вспомнили, отображение файла в режиме read-write означает, что любая инструкция может его вдобавок ещё и модифицировать. Если она сделает это по ошибке, пытаясь, например, на самом деле перезаписать элемент массива по несуществующему индексу, то таким образом она может случайно изменить замапленный на этот адрес файл, что приведёт к порче базы данных. Если же файл отображён в режиме read-only, то попытка изменить соответствующее ему адресное пространство приведёт к аварийному завершению программы с сигналом SIGSEGV, и файл останется в целостности.

Второе следствие уже специфично для iOS. Ни автор, ни какие бы то ни было другие источники о нём явно не упоминают, но без него LMDB была бы непригодна для работы в этой мобильной операционной системе. Его рассмотрению посвящён следующий раздел.

Специфика отображённых в память файлов в iOS

В 2018 году на WWDC был замечательный доклад «iOS Memory Deep Dive». В нём рассказывается, что в iOS все страницы, расположенные в физической памяти, относятся к одному из 3 типов: dirty, compressed и clean.

Clean memory — это совокупность страниц, которые могут быть безболезненно выгружены из физической памяти. Находящиеся в них данные можно по мере необходимости загрузить заново из их первоначальных источников. Read-only memory-mapped файлы попадают именно в эту категорию. iOS не боится в любой момент выгружать отображённые на файл страницы из памяти, поскольку они гарантированно синхронизированы с файлом на диске.
​
В dirty memory попадают все модифицированные страницы, где бы они изначально не располагались. В частности, так будут классифицированы и memory-mapped файлы, изменённые через запись в проассоциированную с ними виртуальную память. Открыв LMDB с флагом MDB_WRITEMAP, после внесения в неё изменений в этом можно убедится лично.​

​Как только приложение начинает занимать слишком много физической памяти, iOS подвергает его dirty станицы компрессии. Совокупность памяти, занимаемая dirty и compressed страницами, составляет так называемый memory footprint приложения. По достижении им некого порогового значения, за процессом приходит системный демон OOM killer и принудительно его завершает. В этом состоит особенность iOS по сравнению с десктопными операционными системами. В отличие от них понижение memory footprint посредством свопинга страниц из физической памяти на диск в iOS не предусмотрено.​ О причинах можно лишь гадать. Возможно процедура интенсивного перемещения страниц на диск и обратно слишком энергозатратна для мобильных устройств или iOS экономит ресурс перезаписи ячеек на SSD дисках, а может быть проектировщиков не удовлетворяла общая производительность системы, где всё постоянно свопится. Как бы то ни было, факт остаётся фактом.

Хорошая новость, уже упомянутая ранее, состоит в том, что LMDB по умолчанию не использует механизм mmap для обновления файлов. Из этого следует, что отображённые данные ​классифицируются iOS как clean memory и не вносят вклада в memory footprint. В этом можно убедиться с помощью инструмента Xcode под названием VM Tracker. На скриншоте ниже отображено состояние виртуальной памяти iOS приложения Облака во время работы. На старте в нём было инициализировано 2 инстанса LMDB. Первому было разрешено отобразить свой файл на 1GiB виртуальной памяти, второму — 512МiB. Несмотря на то, что оба хранилища занимают определенный объем резидентной памяти, ни один из них не контрибутит в dirty size.

А теперь время плохих новостей. Благодаря механизму свопинга в 64-битных настольных операционных системах каждый процесс может занять столько виртуального адресного пространства, сколько позволяет свободное место на жестком диске под его потенциальный своп. Замена свопинга на компрессию в iOS радикально снижает теоретический максимум. Теперь все живущие процессы должны влезть в основную (читай оперативную) память, а все не поместившиеся подлежат принудительному завершению. Об этом говорится как в упомянутом выше докладе, так и в официальной документации. Как следствие, iOS жёстко ограничивает размер памяти, доступной для выделения через mmap. Вот тут можно посмотреть на эмпирические пределы объёмов памяти, которые удалось аллоцировать на разных устройствах с помощью этого системного вызова. На самых современных моделях смартфонов iOS расщедрилась на 2 гигабайта, а на топовых версиях iPad — на 4. На практике, конечно же, приходится ориентироваться на самые младшие поддерживаемые модели устройств, где все очень грустно. Хуже того, посмотрев на состояние памяти приложения в VM Tracker, можно обнаружить, что LMDB далеко не единственная, кто претендует на memory-mapped память. Хорошие куски отъедают системные аллокаторы, файлы с ресурсами, фреймворки для работы с изображениями и другие хищники помельче.

По итогам экспериментов в Облаке мы пришли к следующим компромиссным значениям выделяемой LMDB памяти: 384 мегабайт для 32-битных устройств и 768 — для 64-битных. После израсходования этого объёма любые модифицирующие операции начинают завершаться с кодом MDB_MAP_FULL. Такие ошибки мы наблюдаем в нашем мониторинге, но их достаточно мало, чтобы на данном этапе ими можно было пренебречь.

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

Кит №2. B±дерево

Для эмулирования таблиц поверх key-value хранилища необходимо, чтобы в его API присутствовали следующие операции:

1. Вставка нового элемента​.
2. Поиск элемента с заданным ключом​.
3. Удаление элемента​.
4. Итерирование по интервалам ключей в порядке их сортировки.

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

У бинарных деревьев есть два фундаментальных недостатка, которые не позволяют им быть эффективными в качестве дисковой структуры данных. Во-первых, степень их сбалансированности непредсказуема. Есть немалый риск получить деревья, в которых высота разных веток может сильно отличаться, что значительно ухудшает алгоритмическую сложность поиска по сравнению с ожидаемой. Во-вторых, обилие кросс-ссылок между узлами лишает бинарные деревья локальности в памяти.​ Близкие узлы (с точки зрения связей между ними) могут находиться на совершенно разных страницах в виртуальной памяти. Как следствие, даже для простого обхода нескольких соседних узлов в дереве может потребоваться посетить сопоставимое количество страниц. Это является проблемой даже когда мы рассуждаем об эффективности бинарных деревьев в качестве in-memory структуры данных, так как постоянная ротация страниц в кеше процессора — недешёвое удовольствие. Когда же речь заходит о частом поднятии связанных с узлами страниц с диска, то положение дел становится совсем уж плачевным.​

B-деревья, будучи эволюцией бинарных деревьев, решают обозначенные в предыдущем абзаце проблемы. Во-первых, они самобалансирующиеся. Во-вторых, каждый их узел разбивает множество дочерних ключей не на 2, а на M упорядоченных подмножеств, причем число M может быть довольно большим, порядка нескольких сотен, а то и тысяч.

За счёт этого:

1. В каждом узле находится большое количество уже упорядоченных ключей и деревья получаются очень низкими.
2. Дерево приобретает свойство локальности размещения в памяти, поскольку близкие по значению ключи естественным образом располагаются рядом друг с другом на одном или соседних узлах.
3. Уменьшается количество транзитных узлов при спуске по дереву во время операции поиска.
4. Уменьшается количество считываемых целевых узлов при range-запросах, поскольку в каждом из них уже содержится большое количество упорядоченных ключей.

В LMDB для хранения данных используется одна из вариаций B-дерева под названием B±дерево. На схеме выше изображены три типа узлов, которые в нём бывают:

1. В вершине расположен корень (root). Он материализует собой ни что иное, как концепцию базы данных внутри хранилища. Внутри одного инстанса LMDB можно создавать несколько баз данных, разделяющих между собой замапленное виртуальное адресное пространство. Каждая из них начинается со своего собственного корня.
2. На самом нижнем уровне находятся листья (leaf). Именно они и только они содержат хранящиеся в базе данных пары ключ-значение. К слову, в этом и заключается особенность B±деревьев. Если обычное B-дерево хранит value-части в узлах всех уровней, то B±вариация только на самом нижнем. Зафиксировав этот факт, далее будем называть подтип используемого в LMDB дерева просто B-деревом.
3. Между корнем и листьями размещается 0 и более технических уровней c навигационными (branch) узлами. Их задача — поделить сортированное множество ключей между листьями.

Физически узлы — это блоки памяти заранее определенной длины. Их размер кратен размеру страниц памяти в операционной системе, о которых мы говорили выше. Ниже отображена структура узла. В хедере находится метаинформация, самая очевидная из которых для примера — это контрольная сумма. Далее идет информация об офсетах, по которым располагаются ячейки с данными. В роли данных могут выступать либо ключи, если мы говорим о навигационных узлах, либо целиком пары ключ-значение в случае листьев.​ Более подробно о структуре страниц можно почитать в работе «Evaluation of High Performance Key-Value Stores».

Разобравшись с внутренним наполнением узлов-страниц, далее B-дерево LMDB будем представлять упрощенно в следующем виде.

Страницы с узлами последовательно располагаются на диске. Страницы с большим номером расположены ближе к концу файла. Так называемая мета-страница (meta page) содержит информацию о смещениях, по которым можно найти корни всех деревьев. При открытии файла LMDB постранично сканирует файл от конца к началу в поисках валидной мета-страницы и уже через неё находит существующие базы данных.​

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

Кит №3. Copy-on-write

Некоторые операции с B-деревом предполагают внесение целой серии изменений в его узлах. Одним из примеров является добавление нового ключа в узел, в котором уже достигнута максимальная вместимость. В таком случае необходимо, во-первых, разделить узел на два, а во-вторых, добавить ссылку на новый отпочковавшийся дочерний узел в его родителе. Данная процедура потенциально очень опасна. Если по каким-то причинам (краш, отключение питания, и т.п.) случится только часть изменений из серии, то дерево останется в неконсистентном состоянии.

Одним из традиционных решений для обеспечения базы данных устойчивостью к сбоям является добавление рядом с B-деревом дополнительной дисковой структуры данных — лога транзакций, известного также под именем write-ahead log (WAL). Он представляет собой файл, в конец которого строго до модификации самого B-дерева записывается предполагаемая операция. Таким образом, если во время самодиагностики обнаруживается порча данных, база данных консультируется с логом для приведения себя в порядок.

LMDB в качестве механизма обеспечения устойчивости к сбоям выбрала другой способ, который называется copy-on-write. Его суть в том, что вместо обновления данных на существующей странице она сначала целиком её копирует и все модификации производит уже в копии.​

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

Если вдруг во время процедуры обновления произойдет аварийное завершение процесса, то либо не создастся новая мета-страница, либо она не будет записана на диск до конца, и её контрольная сумма будет некорректной. В любом из этих двух случаев новые страницы будут недостижимы, а старые не пострадают. Это избавляет LMDB от необходимости вести write ahead log для поддержания консистентности данных. Де-факто структура хранения данных на диске, описанная выше, одновременно берёт на себя и его функцию. Отсутствие лога транзакций в явном виде — одна из фишек LMDB, обеспечивающая высокую скорость чтения данных.​

Получившаяся конструкция под названием append-only B-tree естественным образом обеспечивает изоляцию транзакций и мультиверсионность. В LMDB с каждой открытой транзакцией ассоциируется актуальный на данный момент корень дерева. До тех пор, пока транзакция не завершена, страницы связанного с ней дерева никогда не будут изменены или повторно использованы под новые версии данных.​ Таким образом, можно сколь угодно долго работать ровно с тем набором данных, который был актуален на момент открытия транзакции, даже если хранилище в это время продолжает активно обновляться. В этом и заключается суть мультиверсионности, делающая LMDB идеальным источником данных для всеми нами любимого UICollectionView. Открыв транзакцию, не нужно повышать memory footprint приложения, спешно выкачивая актуальные данные в какую-нибудь in-memory структуру, боясь остаться у разбитого корыта. Данная особенность выгодно отличает LMDB от того же SQLite, который такой тотальной изоляцией похвастаться не может. Открыв в последнем две транзакции и удалив некую запись в рамках одной из них, эту же запись уже не получится получить и в рамках второй оставшейся.

​Оборотной стороной медали является потенциально значительно больший расход виртуальной памяти. На слайде изображено, как будет выглядеть структура базы данных, если происходит её модификация одновременно с 3 открытыми транзакциями на чтение, смотрящими на разные версии базы данных. Поскольку LMDB не может повторно использовать узлы, достижимые из корней, связанных с актуальными транзакциями, хранилищу не остаётся ничего иного, кроме как разместить в памяти ещё один четвёртый корень и в очередной раз расклонировать под ним модифицируемые страницы.​

Здесь не лишним будет вспомнить раздел о memory-mapped файлах. Вроде бы дополнительный расход виртуальной памяти не должен нас сильно беспокоить, поскольку она не вносит вклада в memory footprint приложения. Однако в то же время было отмечено, что iOS очень скупа на её выделение, и мы не можем как на сервере или десктопе с барского плеча предоставить LMDB регион в 1 терабайт и не думать об этой особенности вовсе. По возможности нужно стараться делать время жизни транзакций как можно более коротким.

Разбор API начнём с рассмотрения базовых абстракций, предоставляемых LMDB: окружение и базы данных, ключи и значения, транзакции и курсоры.