company_banner

Блеск и нищета key-value базы данных LMDB в приложениях для iOS

    image


    Осенью 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.3. Моделирование связей между таблицами


    1. Мотивация внедрения


    Однажды году так в 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 раз. Выбор стал очевиден.




    2. Позиционирование LMDB


    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 в своей работе исходит из среднестатистических потребностей среднестатистического приложения, то вы как прикладной разработчик прекрасно осведомлены об основных сценариях нагрузки. За более производительное решение придётся заплатить возросшим ценником как на разработку первоначального решения, так и на его последующую поддержку.



    3. Три кита LMDB


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


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


    3.1. Кит №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.



    3.2. Кит №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.3. Кит №3. Copy-on-write


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


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


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



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



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



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


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



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



    4. Проектирование схемы данных поверх key-value API


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


    Замечание о листингах кода

    Все функции в публичном API LMDB возвращают результат своей работы в виде кода ошибки, но на всех последующих листингах его проверка опущена в угоду лаконичности.​ На практике мы и вовсе для взаимодействия с хранилищем использовали свой форк C++ обёртки lmdbxx, в котором ошибки материализуются в виде исключений C++.


    В качестве наиболее быстрого способа подключения LMDB к проекту для iOS или macOS предлагаю свой CocoaPod POSLMDB.



    4.1. Базовые абстракции


    Окружение (environment)


    Структура MDB_env является является вместилищем внутреннего состояния LMDB. Семейство функций с префиксом mdb_env позволяет сконфигурировать некоторые его свойства. В простейшем случае инициализация движка выглядит следующим образом.


    mdb_env_create(env);​
    mdb_env_set_map_size(*env, 1024 * 1024 * 512)​
    mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);

    В приложении Облака Mail.ru значения по умолчанию мы меняли только у двух параметров.


    Первый из них — это размер виртуального адресного пространства, на которое отображается файл хранилища. К сожалению, даже на одном и том же устройстве конкретное значение может существенно отличаться от запуска к запуску. Чтобы учесть эту особенность iOS, максимальный объём хранилища у нас подбирается динамически. Стартуя с некого значения, он последовательно ополовинивается до тех пор, пока функция mdb_env_open не вернет результат отличный от ENOMEM. В теории существует и противоположный путь — сначала выделить движку минимум памяти, а затем, при получении ошибок MDB_MAP_FULL, увеличивать её. Однако он гораздо более тернист. Причина в том, что процедура перевыделения памяти (remap) с помощью функции mdb_env_set_map_size инвалидирует все сущности (курсоры, транзакции, ключи и значения), полученные от движка ранее. Учёт такого поворота событий в коде приведёт к его существенному усложнению. Если, тем не менее, виртуальная память вам очень дорога, то это может быть поводом присмотреться к ушедшему далеко вперед форку MDBX, где среди заявленных фич есть «automatic on-the-fly database size adjustment».


    Второй параметр, дефолтное значение которого нам не подошло, регулирует механику обеспечения потокобезопасности. К сожалению, как минимум в iOS 10 есть проблемы с поддержкой thread local storage. По этой причине в примере выше хранилище открывается с флагом MDB_NOTLS. Кроме этого понадобилось ещё и форкать C++ обёртку lmdbxx, чтобы вырезать переменные с этим атрибутом и в ней.


    Базы данных


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


    MDB_txn *txn;​
    MDB_dbi dbi;​
    mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);​
    mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);​
    mdb_txn_abort(txn);

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


    Ключи и значения


    Структура MDB_val моделирует концепцию как ключа, так и значения. Хранилище не имеет ни малейшего представления об их семантике. Для неё что то, что другое — это просто массив байт заданного размера. Максимальный размер ключа — 512 байт.


    typedef struct MDB_val {​
        size_t mv_size;​
        void *mv_data;​
    } MDB_val;​​

    С помощью компаратора хранилище упорядочивает ключи по возрастанию. Если не заменить его собственным, то будет использоваться дефолтный, который сортирует их побайтово в лексикографическом порядке.​


    Транзакции


    Устройство транзакций подробно описано в предыдущей главе, поэтому здесь короткой строкой повторю их основные свойства:


    1. Поддержка всех базовых свойств ACID: атомарность, консистентность, изолированность и надёжность. Не могу не отметить, что в части durability на macOS и iOS есть баг, исправленный в MDBX. Подробнее можно почитать в их README.
    2. Подход к многопоточности описывается схемой «single writer / multiple readers». Писатели блокируют друг друга, но не блокируют читателей. Читатели не блокируют ни писателей, ни друг друга.
    3. Поддержка вложенных транзакций.
    4. Поддержка мультиверсионности.

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


    Добавление тестовой записи
    MDB_env *env;
    MDB_dbi dbi;
    MDB_txn *txn;
    
    mdb_env_create(&env);
    mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);
    
    mdb_txn_begin(env, NULL, 0, &txn);
    mdb_dbi_open(txn, NULL, 0, &dbi);
    mdb_txn_abort(txn);
    
    char k = 'k';
    MDB_val key;
    key.mv_size = sizeof(k);
    key.mv_data = (void *)&k;
    
    int v = 997;
    MDB_val value;
    value.mv_size = sizeof(v);
    value.mv_data = (void *)&v;
    
    mdb_txn_begin(env, NULL, 0, &txn);
    mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
    mdb_txn_commit(txn);

    MDB_txn *txn1, *txn2, *txn3;
    MDB_val val;
    
    // Открываем 2 транзакции, каждая из которых смотрит
    // на версию базы данных с одной записью.
    mdb_txn_begin(env, NULL, 0, &txn1); // read-write
    mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only
    
    // В рамках первой транзакции удаляем из базы данных существующую в ней запись.
    mdb_del(txn1, dbi, &key, NULL);
    // Фиксируем удаление.
    mdb_txn_commit(txn1);
    
    // Открываем третью транзакцию, которая смотрит на
    // актуальную версию базы данных, где записи уже нет.
    mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
    // Убеждаемся, что запись по искомому ключу уже не существует.
    assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
    // Завершаем транзакцию.
    mdb_txn_abort(txn3);
    
    // Убеждаемся, что в рамках второй транзакции, открытой на момент
    // существования записи в базе данных, её всё ещё можно найти по ключу.
    assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
    // Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
    assert(*(int *)val.mv_data == 997);
    // Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
    mdb_txn_abort(txn2);

    Факультативно рекомендую попробовать провернуть такой же фокус с SQLite и посмотреть, что получится.


    Мультиверсионность привносит очень приятные плюшки в жизнь iOS-разработчика. С помощью этого свойства можно легко и непринужденно регулировать скорость обновления источника данных (data source) для экранных форм, исходя из соображений пользовательского опыта. Для примера возьмём такую фичу приложения Облака Mail.ru как автозагрузка контента из системной медиагалереи. При хорошем соединении клиент способен добавлять на сервер несколько фотографий в секунду. Если после каждой загрузки актуализировать UICollectionView с медиаконтентом в облаке пользователя, то можно забыть о 60 fps и плавном скроллинге во время этого процесса. Чтобы предотвратить частые обновления экрана, необходимо как-то ограничить скорость изменения данных в основе UICollectionViewDataSource.


    Если база данных не поддерживает мультиверсионность и позволяет работать лишь с текущим актуальным состоянием, то для создания стабильного во времени снапшота данных необходимо произвести его копирование либо в некую in-memory структуру данных, либо во временную таблицу. Любой из этих подходов очень накладен. В случае in-memory хранилища получаем расходы как по памяти, вызванные хранением сконструированных объектов, так и по времени, связанные с избыточными ORM-преобразованиями. Что касается временной таблицы, то это ещё более дорогое удовольствие, имеющее смысл только в нетривиальных кейсах.


    Мультиверсионность LMDB решает задачу поддержания стабильного источника данных очень элегантно. Достаточно просто открыть транзакцию и вуа-ля — пока мы её не завершим набор данных у нас гарантированно зафиксирован. Логика скорости его обновления теперь целиком и полность находится в руках презентационного слоя при полном отсутствии накладных расходов значимых ресурсов.


    Курсоры


    Курсоры предоставляют механизм для упорядоченного итерирования по парам ключ-значение посредством обхода B-дерева. Без них было бы невозможно эффективно моделировать таблицы в базе данных, к рассмотрению которых мы и переходим.



    4.2. Моделирование таблиц


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


    Схема таблицы


    Одним из частых сценариев, под который должна быть заточена структура таблицы с деревом папок — выборка всех элементов, расположенных внутри заданной директории.​ Хорошей моделью организации данных для эффективных запросов такого рода является Adjacency List. Для её воплощения поверх key-value хранилища необходимо отсортировать ключи файлов и папок таким образом, чтобы они группировались на основании принадлежности к родительской директории. Кроме того, чтобы отображать содержимое директории в привычном пользователю Windows виде (сначала папки, потом файлы, и те и другие отсортированы по алфавиту), необходимо включить в ключ соответствующие дополнительные поля.


    ​На картинке ниже показано, как, исходя из поставленной задачи, может выглядеть представление ключей в виде массива байт. Вначале размещаются байты с идентификатором родительской директории (красные), потом — с типом (зелёные) и уже в хвосте — с именем (синие).​ Будучи отсортированными дефолтным компаратором LMDB в лексикографическом порядке, они упорядочиваются требуемым образом. Последовательный обход ключей с одним и тем же красным префиксом даёт нам связанные с ними значения в той последовательности, в которой они должны быть выведены в интерфейсе пользователя (справа), не требуя как-то дополнительной постобработки.



    Сериализация ключей и значений


    В мире придумано множество методов сериализации объектов. Поскольку у нас никакого иного требования кроме скорости не было, для себя мы выбрали самый быстрый из возможных — дамп памяти, занимаемой инстансом структуры языка C. Так, ключ элемента директории можно смоделировать следующей структурой NodeKey.


    typedef struct NodeKey {​
        EntityId parentId;​
        uint8_t type;​
        uint8_t nameBuffer[256];​
    } NodeKey;

    Для сохранения NodeKey в хранилище нужно в объекте MDB_val спозиционировать указатель на данные на адрес начала структуры, а их размер вычислить функцией sizeof.


    MDB_val serialize(NodeKey * const key) {
        return MDB_val {
            .mv_size = sizeof(NodeKey),
            .mv_data = (void *)key
        };
    }

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


    Упорядочивание ключей бинарным компаратором


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


    Первое, о чём необходимо помнить — это представление в памяти примитивных типов данных. Так, на всех устройствах Apple целочисленные переменные хранятся в формате Little Endian. Это означает, что наименее значимый байт будет находится слева, и отсортировать целые числа, используя их побайтовое сравнение, не получится. Например, попытка сделать это с набором чисел от 0 до 511 приведёт к следующему результату.


    // value (hex dump)
    000 (0000)
    256 (0001)
    001 (0100)
    257 (0101)
    ...
    254 (fe00)
    510 (fe01)
    255 (ff00)
    511 (ff01)

    Для решения этой проблемы целые числа должны храниться в ключе в подходящем для побайтового компаратора формате. Осуществить необходимое преобразование помогут функции из семейства hton* (в частности htons для двухбайтовых чисел из примера).


    Формат представления строк в программировании — это, как известно, целая история. Если семантика строк а также используемая для их представления в памяти кодировка предполагает, что на символ может приходится больше одного байта, то от идеи использования дефолтного компаратора лучше сразу отказаться.


    Второе, что нужно держать в голове — принципы выравнивания компилятором полей структуры. Из-за них в памяти между полями могут образовываться байты с мусорными значениями, что, конечно же, ломает побайтовую сортировку. Для ликвидации мусора нужно либо объявлять поля в строго определённом порядке, держа в голове правила выравнивания, либо использовать в объявлении структуры атрибут packed.


    Упорядочивание ключей внешним компаратором


    Логика сравнения ключей может отказаться слишком сложной для бинарного компаратора. Одна из множества причин — наличие внутри структур технических полей. Проиллюстрирую их возникновение на примере уже знакомого нам ключа для элемента директории.


    typedef struct NodeKey {​
        EntityId parentId;​
        uint8_t type;​
        uint8_t nameBuffer[256];​
    } NodeKey;

    При всей своей простоте в подавляющем большинстве случаев он потребляет слишком много памяти. Буфер под название занимает 256 байт, хотя в среднем имена файлов и папок редко превышают 20-30 символов.


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


    typedef struct NodeKey {​
        EntityId parentId;​
        uint8_t type;​
        uint8_t nameLength;​
        uint8_t nameBuffer[256];​
    } NodeKey;

    Далее при сериализации в качестве размера данных указывается не sizeof всей структуры, а размер всех полей фиксированной длины плюс размер реально используемой части буфера.


    MDB_val serialize(NodeKey * const key) {
        return MDB_val {
            .mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
            .mv_data = (void *)key
        };
    }

    В результате произведённого рефакторинга мы получили значительную экономию занимаемого ключами места. Однако из-за технического поля nameLength, дефолтный бинарный компаратор более не годится для сравнения ключей. Если мы его не заменим на свой, то длина имени будет более приоритетным фактором при сортировке, нежели само имя.


    LMDB позволяет задать каждой базе данных свою функцию сравнения ключей. Делается это с помощью функции mdb_set_compare строго до открытия. По очевидным причинам, на протяжении всей жизни базы данных менять её нельзя. На вход компаратор получает два ключа в бинарном формате, а на выходе возвращает результат сравнения: меньше (-1), больше (1) или равны (0). Псевдокод для NodeKey выглядит так.


    int compare(MDB_val * const a, MDB_val * const b) {​
        NodeKey * const aKey = (NodeKey * const)a->mv_data;​
        NodeKey * const bKey = (NodeKey * const)b->mv_data;​
        return // ...
    }​

    До тех пор, пока в базе данных все ключи имеют один и тот же тип, безусловное приведение их байтового представления к типу прикладной структуры ключа является законным. Тут есть один нюанс, но он будет рассмотрен чуть ниже в подразделе «Чтение записей».


    Сериализация значений


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


    Value-частью записи (значением) база данных особо не интересуется. Её преобразование из байтового представления в объект происходит только тогда, когда это уже требуется прикладному коду, например, для его отображения на экране. Поскольку происходит это относительно редко, то требования к скорости этой процедуры не столь критичны, и в её реализации мы в гораздо большей степени вольны ориентироваться на удобство.​ Например, для сериализации метаданных о ещё не загруженных файлах у нас используется NSKeyedArchiver.


    NSData *data = serialize(object);​
    MDB_val value = {​
        .mv_size = data.length,​
        .mv_data = (void *)data.bytes​
    };

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



    Для её реализации на языке C специфические поля наследников выносятся в отдельные структуры, а их связь с базовой задаётся через поле типа union. Актуальное содержимое объединения задаётся через технический атрибут type.


    typedef struct NodeValue {​
        EntityId localId;​
        EntityType type;​
        union {​
            FileInfo file;​
            DirectoryInfo directory;​
        } info;​
        uint8_t nameLength;​
        uint8_t nameBuffer[256];​
    } NodeValue;​

    Добавление и обновление записей


    Сериализованные ключ и значение можно добавлять хранилище. Для этого используется функция mdb_put.


    // key и value имеют тип MDB_val​
    mdb_put(..., &key, &value, MDB_NOOVERWRITE);

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


    Чтение записей


    Для чтения записей в LMDB предназначена функция mdb_get. Если пара ключ-значение представлена ранее сдампленными структурами, то выглядит эта процедура следующим образом.


    NodeValue * const readNode(..., NodeKey * const key) {​
        MDB_val rawKey = serialize(key);​
        MDB_val rawValue;​
        mdb_get(..., &rawKey, &rawValue);​
        return (NodeValue * const)rawValue.mv_data;​
    }

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


    1. Для readonly транзакции указатель на структуру-значение будет гарантированно оставаться валидным лишь до тех пор, пока транзакция не будет закрыта. Как было отмечено ранее, страницы B-дерева, на которых располагается объект, благодаря принципу copy-on-write остаются неизменными пока на них ссылается хотя бы одна транзакция. В то же время, как только последняя связанная с ними транзакция завершается, страницы могут быть повторно использованы для новых данных. Если необходимо, чтобы объекты переживали породившую их транзакцию, то их всё-таки придётся скопировать.
    2. ​​Для readwrite транзакции указатель на полученную структуру-значение будет валидным лишь до первой модифицирующей процедуры (запись или удаление данных).
    3. Несмотря на то, что структура NodeValue не полноценная, а подрезанная (см. подраздел «Упорядочивание ключей внешним компаратором»), через указатель можно спокойно обращаться к её полям. Главное его не разыменовывать!
    4. Ни в коем случае нельзя модифицировать структуру через полученный указатель. Все изменения должны осуществляться только через метод mdb_put. Впрочем, при всём желании сделать это и не получится, поскольку область памяти, где эта структура располагается, замаплена в режиме readonly.
    5. Remap файла на адресное пространство процесса с целью, например, увеличения максимального размера хранилища с помощью функции mdb_env_set_map_size полностью инвалидирует все транзакции и связанные с ними сущности вообще и указатели на считанные объекты в частности.

    Наконец, ещё одна особенность настолько коварна, что раскрытие её сути никак не влезает просто в ещё один пункт. В главе про B-дерево я приводил схему устройства его страниц в памяти. Из неё следует, что адрес начала буфера с сериализованными данными может быть абсолютно произвольным. Из-за этого указатель на них, получаемый в структуре MDB_val и приводимый к указателю на структуру, получается в общем случае не выровненным. В то же время архитектуры некоторых чипов (в случае iOS это armv7) требуют, чтобы адрес любых данных был кратен размеру машинного слова или, иначе говоря, битности системы (для armv7 — это 32 бита). Иными словами операция вроде *(int *foo)0x800002 на них приравнивается к побегу и приводит к расстрелу с вердиктом EXC_ARM_DA_ALIGN. Избежать столь печальной участи можно двумя способами.


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


    int compare(MDB_val * const a, MDB_val * const b) {
        NodeKey aKey, bKey;
        memcpy(&aKey, a->mv_data, a->mv_size);
        memcpy(&bKey, b->mv_data, b->mv_size);
        return // ...
    }

    Альтернативный путь — заранее уведомить компилятор, что структуры с ключом и значением могут быть не выровненными с помощью атрибута aligned(1). На ARM такого же эффекта можно добиться и с помощью атрибута packed. Учитывая, что он к тому же ещё и способствует оптимизации занимаемого структурой места, данный способ мне видится предпочтительным, хоть и приводит к удорожанию операций доступа к данным.


    typedef struct __attribute__((packed)) NodeKey {
        uint8_t parentId;
        uint8_t type;
        uint8_t nameLength;
        uint8_t nameBuffer[256];
    } NodeKey;

    Range-запросы


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


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



    Найти верхнюю границу можно "в лоб" последовательным поиском. Для этого курсор устанавливается в начало всего списка ключей в базе данных и далее инкрементируется до тех пор, пока не под ним не окажется ключ с идентификатором родительской директории. У этого подхода есть 2 очевидных недостатка:


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

    К счастью в API LMDB предусмотрен эффективный способ начального позиционирования курсора.​ Для этого нужно сформировать такой ключ, значение которого будет заведомо меньше либо равно ключу, находящегося на верхней границе интервала. Например, применительно к списку на рисунке выше, мы можем сделать такой ключ, в котором поле parentId будет равно 2, а все остальные заполнены нулями. Такой частично заполненный ключ подается на вход функции mdb_cursor_get с указанием операция MDB_SET_RANGE.​


    NodeKey upperBoundSearchKey = {​
        .parentId = 2,​
        .type = 0,​
        .nameLength = 0​
    };​
    MDB_val value, key = serialize(upperBoundSearchKey);​
    MDB_cursor *cursor;​
    mdb_cursor_open(..., &cursor);​
    mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

    Если верхняя граница группы ключей найдена, то далее итерируемся по ней пока либо не встретиться либо ключ с другим parentId, либо ключи вовсе не закончатся.​


    do {​
        rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
        // processing...​
    } while (MDB_NOTFOUND != rc && // check end of table​
             IsTargetKey(key));    // check end of keys group​​

    Что приятно, в рамках итерирования с помощью mdb_cursor_get мы получаем не только ключ, но и значение. Если для выполнения условий выборки нужно проверить в том числе поля из value-части записи, то они вполне себе доступны без дополнительных телодвижений.



    4.3. Моделирование связей между таблицами


    К текущему моменту нам удалось рассмотреть все аспекты проектирования и работы с однотабличной базой данных. Можно сказать, что таблица — это набор отсортированных записей, состоящих из однотипных пар ключ-значение. Если отобразить ключ в виде прямоугольника, а связанное с ним значение в виде параллелепипеда, то получится визуальная схема базы данных.



    Однако в реальной жизни редко удается обойтись столь малой кровью. Зачастую в базе данных требуется, во-первых, иметь несколько таблиц, а во-вторых, осуществлять в них выборки в порядке, отличном от первичного ключа. Вопросам их создания и связывания между собой и посвящен данный последний раздел.


    Индексные таблицы


    В облачном приложении есть раздел «Галерея». В нём отображается медиаконтент из всего облака, отсортированный по дате. Для оптимальной реализации такой выборки рядом с основной таблицей нужно завести ещё одну с новым типом ключей. В них будет содержаться поле с датой создания файла, которое будет выступать в качестве первичного критерия сортировки. Поскольку новые ключи ссылаются на те же самые данные, что и ключи в основной таблице, они называются индексными. На картинке ниже они выделены оранжевым цветом.



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


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


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

    Далее рассмотрим как ликвидировать эти недостатки.


    Организация связей между таблицами


    Для связи индексной таблицы с основной хорошо подходит паттерн «ключ как значение». Как следует из его названия в качестве value-части индексной записи выступает копия значения первичного ключа. Этот подход нивелирует все перечисленные выше недостатки, связанные с хранением копии value-части первичной записи. Единственная плата — для получения значения по индексному ключу нужно сделать 2 запроса в базу данных вместо одного. Схематично получившаяся схема базы данных выглядит следующим образом.



    Ещё одним паттерном организации связи между таблицами является «избыточный ключ». Его суть в добавлении в ключ дополнительных атрибутов, которые нужны не для сортировки, а для воссоздания связанного ключа.​ В приложении Облака Mail.ru есть реальные примеры его использования, однако во избежании глубокого погружения в контекст специфических iOS-фреймворков, приведу вымышленный, но зато более понятный пример.​


    В облачных мобильных клиентах есть страница, где отображаются все файлы и папки, к которым пользователь предоставил доступ другим людям. Поскольку таких файлов относительно мало, а разного рода связанной с ними специфической информации о публичности много (кому предоставлен доступ, с какими правами и т.п.) будет не рационально утяжелять ей value-часть записи в основной таблице. Однако если захотеть отображать такие файлы в офлайне, то хранить её где-то всё-таки нужно. Естественным вариантом решения является заведение под неё отдельной таблицы. На схеме ниже её ключ имеет префикс «P», а плейсхолдер «propname» может быть заменён на более конкретное значение «public info».​



    Все уникальные метаданные, ради хранения которых и заводилась новая таблица, выносятся в value-часть записи. В то же время, те данные о файлах и папках, которые уже хранятся в основной таблице, дублировать не хочется. Вместо этого в ключ «P» добавляются избыточные данные в лице полей «node ID» и «timestamp». Благодаря ним можно сконструировать индексный ключ, по которому получить первичный ключ, по которому, наконец, получить метаданные ноды.


    Заключение​


    Итоги внедрения LMDB мы оцениваем позитивно. После него количество зависаний приложения уменьшилось на 30%.



    Результаты проделанной работы нашли отклик за пределами команды iOS. На текущий момент один из главных разделов «Файлы» в приложении для Android также перешёл на использование LMDB, а другие части на подходе. Язык C, на котором реализовано key-value хранилище, явился хорошим подспорьем, чтобы изначально сделать прикладную обвязку вокруг него кроссплатформенно на языке С++. Для бесшовного соединения получившейся C++ библиотеки с платформенным кодом на Objective-C и Kotlin был использован кодогенератор Djinni от Dropbox, но это уже совсем другая история.

    Mail.ru Group
    Строим Интернет

    Комментарии 47

      +1
      Меня давно мучает вопрос. Интересно как на него ответят такой гигант как Меил ру. Вот вы запустили приложение Юла, и по-первой на сколько я понял после каждого тыка она лезла обновляться в интернет. И всё прекрасно работало. Да и сейчас оно тоже постоянно подгружает данные на чистый экран. Вопрос в следующем, зачем мобильным приложением вообще нужны базы данных? Окупает ли количество юзер экспиеренса тонны попоболи которые надо затратить для их внедрения в систему?
        +3

        Отличная "мясистая" статья!


        Несколько комментариев относительно упомянутого движка MDBX:


        • Настоятельно советую мигрировать с LMDB на MDBX, пока не "бомбанули" ошибки LMDB. Кроме этого вы получите автокомпактификацию и изменяемый размер файла БД.
        • MDBX появилась внутри ReOpenLDAP в ходе доработок для использования в инфраструктуре ПАО Мегафон, и произошла эта история в компании Петер-Сервис (ныне Nexign).
        • Об MDBX скоро будет отдельная статья, как только я закончу основную работу над C++ биндингами.
        • При необходимости хранить "табличные данные" с колонками и вторичными индексами рекомендую посмотреть на libfpta, а не мучиться с голым key-value.
          0
          Спасибо за ссылки, Юра, и вообще за вклад в развитие LMDB!

          Пользуясь случаем, хочу поинтересоваться, автоадаптация размеров хранилища не приводит к инвалидации разного рода сущностей, полученных ранее от движка. Вот получил я указатель на данные в MDB_val, какой-то кусок кода продолжает им пользоваться и тут бац и база поресайзилась. Как транзакции переживают этот момент? В этом свете, предполагает ли работа с MDBX обязательное копирование ранее полученных из неё данных?
            +2

            Не Юра, но почти привык ;)


            Данные лежание внутри БД (внутри mmap-файла) валидны пока вы находитесь в рамках транзакции. Соответственно, если упростить, то libmdbx не уменьшает размер файла меньше чем используется хотя-бы одним из читателей.


            Кстати, две характерные ошибки при использовании LMDB/MDBX — это обращение к данным вне пределов транзакции, когда эти данные могут быть перезаписаны. Причем есть отдельный подвид таких ошибок внутри пишущих транзакций, когда данные могут располагаться в грязной страницы и меняться в ходе операций внутри текущей транзакции. Это достаточно частые "грабли" при организации различных индексов или отношений поверх MDBX, поэтому:


            • в MDBX есть mdbx_is_dirty();
            • есть смысл посмотреть на libfpta, чтобы не ходить по этим граблям.
              +1

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


              Так вот, автокомпактификация основывается на простом "трюке":


              • Внутри БД есть значение, отмечающее границу выделенных страниц от начала файла БД (сколько страниц находится в обороте, включая как данные, так и GC).
              • При освобождении страниц внутри БД проверяется примыкают ли они к этой границе, и если примыкают, то граница сдвигается к началу. Эта очень дешево, почти бесплатно.
              • Такими образом, libmdbx стремиться вытолкнуть максимум страниц в не-распределенный/неиспользуемый хвост файла БД, при необходимости больше "пережевав" GC.

              В результате, реально используемый набор страниц БД стремится к уменьшению (что уменьшает объем используемой памяти и общее давление на подсистему управлением виртуальной памятью).


              Как видите, это достаточно простой, надежный и эффективный механизм. Не понимаю, почему Howard Chu не реализовал подобное в LMDB исходно и даже сейчас (спустя почти три года, как автокомпактификация появилась в libmdbx).


              Соответственно, динамическое изменение размера БД основывает на этой авто-компактификации, и (если сильно упростить) сводится к добавлению/отрезанию файла БД рациональными (не мелкими) кусками (ибо это относительно дорогая операция).

                0

                Ок, вы выталкиваете данные в конец файла, а как обрезаете его начало-то? Или не обрезаете и он растёт неограниченно?

                  0

                  Эмм, перечитайте внимательно.


                  Данные не выталкиваются в конец файла, а примерно наоборот — неиспользуемое место "выталкивается" в конец файла.
                  Соответственно, при наличии излишков свободного места в конце файла он обрезается.

                    0
                    Если я правильно понимаю, стоит одной странице с неизменяемыми данными оказаться в конце файла, и файл ни когда не станет меньше. Верно?
                      0

                      Если страница полностью именно с "неизменяемыми данными", то да — бесплатной компактификации не получится, только явная.

            0

            Классная библиотека, особенно когда у тебя 1 writer.
            Для генерации ключа мы использовали код из FoundationDb

              0
              Звучит интригующе. Было бы здорово хоть ссылкой, хоть как подсветить как код из FoundationDb помогает в деле генерации ключа.
                0

                В свое время я из интереса написал универсальный сериализатор ключей LRE когда работал с Berkeley DB, поскольку аналогичных библиотек в сети я не нашел. Сериализатор из FDB не позволяет сравнивать целые и флоаты, потому что использует для них разные представления.

                  0
                  Спасибо, посмотрю. Вообще, если фантазировать вокруг да около, у меня еще витает мысль попробовать flatbuffers для сериализации, благо согласно их бенчмаркам она не так уж сильно проигрывает голым структурам.
                    0

                    Надо мне будет сделать бенчмарк, чтобы сравнить с fptu. Предположительно должно-быть где-то между "Raw structs" и "FlatBuffers (binary)".


                    Независимо от этого хотелось-бы узнать ваше мнение, так сказать при взгляде со стороны. Тем более если что-нибудь попробуете/пощупаете.

                      0

                      Кастомный компаратор все равно проиграет memcmp. Так что самое быстро решение — сериализовать составной ключ в строку, поддерживающую правильный порядок при лексикографическом сравнении.

                        0
                        В этом сомнений, конечно, нет никаких. Но я больше размышляю о flatbuffers в контексте value-части записи. Меня в свое время очень порадовала статья об оптимизации Android приложения Facebook на основе flatbuffers. С тех пор думаю, а что если положить приехавшие объекты сразу в LMDB as is а потом читать их напрямую оттуда, благо формат провернуть такой фокус позволяет. Такая экономия времени была бы…
                    0

                    На всякий — в MDBX есть примитивные функции формирования ключей, которые решают близкую задачу. Например, составной ключ из double и integer легко получить просто перевернув байты в BigEndian и записав последовательно. Причем при сборке с использованием LTO/IPO это будет максимально дешево (без накладных расходов).


                    И еще на всякий — в libfpta поддерживаются составные индексы (по нескольким колонкам), в которых всё необходимое делается автоматически (а в готовящемся С++ API еще и удобнее).

                      +1
                      Прям заинтриговали готовящимся C++ API от души!

                      Пользуясь случаем, хотел спросить ещё следующее. В мобилках отсутствие места на диске является вполне себе заурядной ситуацией, особенно в контексте облачного приложения, которое и устанавливают, чтобы это место освободить. Насколько сложным вам видится поддержка работы хранилища в in memory режиме, без привязки к файлу. По идее поддержать mmap поверх анонимной памяти не должно быть сильно сложной задачей. Много ли внутри LMDB или сильно продвинувшейся вперед MDBX завязок на то, что под mmap обязательно лежит именно файл?
                        +1
                        Прям заинтриговали готовящимся C++ API от души!

                        Плюсовое API для libmdbx будет без особых чудес, но с RAII и т.п. В свою очередь, у libfpta будет свое С++ API — и вот тут изменений и удобств будет существенно больше, но это два разных проекта (хотя и взаимосвязанных).


                        Насколько сложным вам видится поддержка работы хранилища в in memory режиме, без привязки к файлу.

                        Эта задача уже сейчас полностью решается под Linux/Android (и некоторых BSD-системах) путем размещения БД в tmpfs (/dev/shm).


                        Для других платформ (OSX/iOS, Windows) эта задача не является технически сложной, но требует доработки/расширения API и допиливания внутренних интерфейсов с риском внесения багов. Причем имплементить и тестировать это нужно так, чтобы работало везде. Поэтому варианта примерно три:


                        • вы можете сделать это разумно-костыльным способом своими силами в своем форке.
                        • вы можете итеративно по-хорошему реализовать такую фичу и оформить pull-request.
                        • вы можете как-то задонатить такую доработку, если она вам действительно нужна.

                        Моя же собственная мотивация по libmdbx — довести проект до максимальной готовности (зарелизить v1.0), что предполагает консервативный подход к добавлению новых features.

                          0

                          На всякий, "разумно-костыльно" — это значит (например) просто задефайнить часть используемых в libmdbx функций POSIX на собственные реализации, пересадив таким образом БД в ОЗУ. Причем если собрать с LTO (clang из яблочного SDK давно умеет), то вы еще и выиграете по производительности.

                            0
                            подскажите чем будет вызван прирост? использованием своих функций вместо системных? так почему они будут быстрее, если они же будут упираться те же системные, но с доп логикой и параметрами?
                              0

                              Такая пересадка БД в ОЗУ предполагает что все функции, работающие с файловой системой (кроме открытия-создания и закрытия БД), становятся пустотелыми заглушками.
                              Соответственно, при сборке с LTO компилятор выкинет всё что связано с дисковым обменом и подготовкой к нему.

                                0
                                Если выкинет то выходит что они и до того не вызывались, ну и выкинет он их из бинаря — все равно не понятно, откуда прирост?
                                  0

                                  Речь об эффекте от удаления мертвого кода, что на стоит путать (например) с удалением недостижимого кода.


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

                      +1

                      https://github.com/abdullin/foundationdb-1/blob/master/fdbclient/Tuple.cpp вот тут исходники Tuple. Доки здесь поищите, мы на C# переписали, там один маленький файл получился. Код не могу сходу найти.


                      На вопрос почему это использовали: код простой, быстрый и передаешь методу например так
                      Fdb.CreateKey(tableId, authorId,bookName)
                      и получаешь байты, которые уже отсортированы, т.е. если tableId1<tableId2 то каким бы authorId не был, все равно 2 строка будет позже чем первая.
                      Что касается того что int и double будут там разными байтами, мы по факту элемент ключа использовали как index column, поэтому если tableId — это int, то он был таким для всех таблиц.

                    +3

                    При всех достоинствах LMDB (главным образом астрономическая скорость), существует много ограничений, особенно если сравнивать с её "медленным старшим братом" Berkeley DB. Вот некоторые из тех, с которыми я сталкивался:


                    • Длина ключа ограничена 511 байтами. Этот #define внутри библиотеки может быть переопределён, но его значение не может быть больше, чем 1/2 размера страницы
                    • Только пишущие транзакции могут быть вложенными. Родительские транзакции не могут выполнять никаких операций кроме mdb_txn_commit и mdb_txn_abort. Вложенные транзакции несовместимы с MDB_WRITEMAP
                    • Курсоры не имеют возможностей эффективного смещения, только последовательная перемотка записей или MDB_SET_RANGE
                    • База данных непрерывно растет
                    • Нет репликации
                    • Нет очередей
                      +1

                      Всё совершенно верно, но я бы хотел дать пояснения (почему так) и показать что исправлено/улучшено у меня в MDBX (потомке LMDB).


                      Длина ключа ограничена 511 байтами. Этот #define внутри библиотеки может быть переопределён, но его значение не может быть больше, чем 1/2 размера страницы.

                      Хуже, не 1/2, а скорее 1/4 размера страницы. Причина в том, что в "простом" b+tree в branch-странице должно быть минимум 2 ключа и для возможности эффективного split+rebalance это правило должно выполняться после разделения страницы пополам. Соответственно 2*2 = 4.
                      Поддержка более длинных ключей требует существенного усложнения кода (сжатие префиксов, вынос ключей в отдельные страницы), но при этом всё равно сильно страдает производительность.


                      В MDBX указанное ограничение "из каробки" увеличено до максимального уровня (не нужно править #define и пересобирать). Кроме этого, также "из каробки" при создании БД возможен выбор размера страницы вплоть до 64К, т.е. в MDBX максимальный размер ключа примерно в 42 раза больше (21780 байт вместо 511).


                      Только пишущие транзакции могут быть вложенными.

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


                      Аналогично нет смысла вкладывать читающие транзакции в пишущие, и опять-таки это легко эмулировать в коде-обертке.


                      Родительские транзакции не могут выполнять никаких операций кроме mdb_txn_commit и mdb_txn_abort.

                      В MDBX/LMDB сознательно явно сериализуются все пишущие транзакции, это дает массу бонусов. Если же от этого отказаться, то начнется ад с блокировками и/или проблемы с изоляцией транзакций. Поэтому активной (с возможностью операций) может быть только одна (самая вложенная) транзакция, а изменения в родительских становятся возможными после завершения (commit или abort) всех дочерних.


                      Вложенные транзакции несовместимы с MDB_WRITEMAP.

                      Вложенные транзакции требуют формирования в памяти набора/кэша всех измененных станиц, причем смотреть на все данные через этот кэш. Это ровно тоже самое, что происходит без опции MDBX_WRITEMAP.
                      Со своей стороны, опция MDBX_WRITEMAP позволяет избавиться от накладных расходов на формирования образов страниц в памяти и их последующей записи через файловой API.
                      Если же реализовать вложенные транзакции в режиме MDBX_WRITEMAP, то при этом вернется назад существенная часть накладных расходов.
                      Поэтому предлагается выбрать между двумя вариантами: быстро (в режиме MDBX_WRITEMAP) и без вложенных транзакций, либо с дополнительными накладными расходами и вложенными транзакциями.


                      Курсоры не имеют возможностей эффективного смещения, только последовательная перемотка записей или MDB_SET_RANGE.

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


                      Со своей стороны, мне в MDBX в начале этого также не требовалось, а сейчас это проблематично добавить, ибо требуется переработка формата БД. А вот в MithrilDB я склоняюсь к решению реализовать эту фичу.


                      Тем не менее, в MDBX сейчас есть быстрая оценка range-выборок.


                      База данных непрерывно растет.

                      Да, это одна из проблем LMDB, которая полностью решена в MDBX — есть авто-компактификация и автоматической изменение размера БД "на лету", см. mdbx_env_set_geometry().


                      Нет репликации.

                      Полезная фича с точки зрения пользователя, но очень сомнительная с точки зрения движка хранения.
                      "Репликация" требует принятия ряда архитектурных решений и их последующее навязывание пользователю, в частности использование WAL.
                      Сам движок хранения при этом становится подглючивающим "швейцарским ножом" с "большими батарейками", примерно как Berkeley DB.
                      Я склоняюсь к варианту предоставления в MithrilDB доступа к части внутреннего API, так чтобы необходимый вариант репликации мог быть реализован рядом (плагином), без дополнительных накладных расходов и без "протечки абстракции" внутрь движка хранения.


                      Нет очередей.

                      Технически очередь (FIFO или с приоритетами) тривиально реализуется поверх key-value. В случае LMDB при этом в качестве ключа можно использовать номер транзакции (если требуется FIFO), а в MDBX также есть генераторы последовательностей.


                      Если же требуется "тупая" очередь в виде максимально эффективного FIFO с полной durability, то специализированные решения на базе кольцевых буферов будут все равно эффективнее.
                      Однако, если это тянуть в key-value движок хранения, то снова получится "швейцарский нож", но не действительно надежный охотничий или удобный перочинный.

                        0
                        Полезная фича с точки зрения пользователя, но очень сомнительная с точки зрения движка хранения.
                        "Репликация" требует принятия ряда архитектурных решений и их последующее навязывание пользователю, в частности использование WAL.

                        Зачем тут WAL? Кажется для репликации достаточно реализовать 2 шага:


                        1. Первичная репликация. При подключении реплики читать базу от корня сверяя со значениями в реплике. Обнаружив не изменённое поддерево — дальше не идём.
                        2. Рилтайм репликация. С начала первичной репликации пишем все изменения в очередь. По завершении первичной репликации — просто читаем очередь и накладываем изменения в свою копию.
                          0
                          Зачем тут WAL?

                          Начну с "конца". WAL — это по-сути и есть "пишем все изменения в очередь". Разница лишь в том, что если у вас отдельная очередь, то вероятно потребуется WAL и на саму очередь.


                          Без WAL вам потребуется делать "первичную репликацию" (синхронизацию содержимого) при каждом запуске после любой разсинхронизации (когда в мастер были внесены изменения, а реплика была в off-line). В принципе так тоже можно, но при большой БД (скажем в 100 гигов) это потребует чтения этих данных с обоих сторон.


                          На всякий — в MithrilDB будет B+Tree совмещенное с Merkle Tree, как для контроля целостности (включая криптографическую надежность), так и для синхронизации (грубо говоря, а-ля rsync рекурсивно от корня дерева).

                            0

                            WAL — это всё же "сначала пишем, что будем менять, дожидаемся подтверждения записи, потом меняем". Тут же речь про "меняем и асинхронно пишем, что поменяли".


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


                            Вот, кстати, тут интересный вопрос: как с такой схемой работы, как у LMDB реализовать мастер-мастер репликацию?


                            Касательно Merkle Tree меня смущают накладные расходы на постоянное хеширование всего и вся. И хранение длинных хешей. А если хеши не длинные, то любая коллизия — это сломанная база.


                            А что вы будете делать в случае нарушения целостности? Писать "ваша база сломана, несите следующую"? Тут скорее наоборот избыточность нужна для восстановления.

                              0
                              WAL — это всё же "сначала пишем, что будем менять, дожидаемся подтверждения записи, потом меняем". Тут же речь про "меняем и асинхронно пишем, что поменяли".

                              Это не важно.
                              Суть же в том, что в WAL у вас есть история операций (тот самый аналог очереди).
                              Т.е. если у вас уже есть WAL, но рациональнее его доработать для возможности remote replay в целях репликации, нежели чем делать отдельную очередь (см. репликацию в Tarantool).


                              Опять-таки, проблема отдельной очереди в разрастании её размере.
                              Для MDBX/LMDB достаточно обычный кейс — несколько сотен/тысяч транзакций в секунду, очередь будет расти с огромной скоростью.


                              время первичной репликации не от размера ДБ зависит, а от размера разницы.
                              В общем случае, вам потребуется прочитать и сверить данные с обоих сторон (прочитать replication scope в обоих БД почти полностью), либо держать/обслуживать какие-то вспомогательные индексы/данные.

                              интересный вопрос: как с такой схемой работы, как у LMDB реализовать мастер-мастер репликацию?

                              Принципиально/кардинально сильно зависит что на самом деле надо.
                              В качестве работающего примера погуглите multi-master репликацию в ReOpenLDAP.


                              Касательно Merkle Tree меня смущают накладные расходы на постоянное хеширование всего и вся. И хранение длинных хешей. А если хеши не длинные, то любая коллизия — это сломанная база.

                              Хм, вы видимо не умеет его готовить.
                              Хешировать требуется только каждую изменяемую страницу и только при фиксации транзакции. Т.е. накладных расходов конечно всё-таки больше, но поддержка MVCC через Shadow paging при изменении листовой страницы всё равно требует апдейта всех родительских включая корневую.


                              Что касается размера хеша, то 128 бит обеспечат вероятность пропуска ошибки намного порядков меньше чем чтение неверных данных из-за попадания заряженной частицы в транзистор и т.п.


                              А что вы будете делать в случае нарушения целостности? Писать "ваша база сломана, несите следующую"? Тут скорее наоборот избыточность нужна для восстановления.

                              А что вы делали когда вам в крайний раз такое сказала ваша файловая система или БД?

                                0
                                Это не важно.

                                Ну это как называть человеками всех человекообразных обезьян. Write Ahead Log — частный случай Log. Но если называть любой лог WAL-ом — никто вас не поймёт.


                                если у вас уже есть WAL

                                В том-то и дело, что у нас с вами нет WAL by design.) К тому же репликация на уровне WAL как в Postgre — не самая эффективная штука.


                                Для MDBX/LMDB достаточно обычный кейс — несколько сотен/тысяч транзакций в секунду, очередь будет расти с огромной скоростью.

                                Тут, кстати, можно посмотреть в сторону чего-нибудь типа delta-crdt, позволяющего мёржить несколько баз в одну. То есть при репликации писать не просто в очередь, а во временную базу имеющую ту же структуру, которую можно подклеить к реплике минимальными телодвижениями.


                                В качестве работающего примера погуглите multi-master репликацию в ReOpenLDAP.

                                Не нашёл как они это реализовали.


                                А что вы делали когда вам в крайний раз такое сказала ваша файловая система или БД?

                                Файловая система мне выдаёт несколько битых файлов.


                                PavelOsipov Варианты, что можно тут сделать, ограничиваются лишь вашей фантазией. Все они сводятся к ручному или автоматическому переименованию на клиенте или на сервере.

                                Вот именно, что одна версия переименовывается, но остаётся тем же самым файлом, а не выкачивается как новый файл.

                                  0
                                  В том-то и дело, что у нас с вами нет WAL by design.) К тому же репликация на уровне WAL как в Postgre — не самая эффективная штука.

                                  В частности поэтому (и еще массе других причин) я не хочу делать репликацию в MDBX.


                                  Тут, кстати, можно посмотреть в сторону чего-нибудь типа delta-crdt, позволяющего мёржить несколько баз в одну. То есть при репликации писать не просто в очередь, а во временную базу имеющую ту же структуру, которую можно подклеить к реплике минимальными телодвижениями.

                                  Это все частные случаи из моря возможных потребностей и их реализаций. В 80% случаев пользовательские данные не натягиваются на CRDT, либо превращаются в снежный ком. Аналогично с отдельной очередью в виде базы (или наоборот).


                                  Не нашёл как они это реализовали.

                                  https://pro-ldap.ru/tr/rfc/rfc4533.html


                                  Файловая система мне выдаёт несколько битых файлов.

                                  Это если нет контроля и повреждены файлы, а не структуры ФС.
                                  Но в принципе может не выдать ничего или просто мусор.
                                  А еще можно (мысленно) разбить диск молотком или вообще не устанавливать, а на запросы отвечать случайными данными.


                                  Какой вариант вам кажется наиболее правильным?

                                    0
                                    Вот именно, что одна версия переименовывается, но остаётся тем же самым файлом, а не выкачивается как новый файл.

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

                            0

                            Воу, благодарю за развернутый текст. Я отвечу по мере своего опыта.


                            Хуже, не 1/2, а скорее 1/4 размера страницы. Причина в том, что в "простом" b+tree в branch-странице должно быть минимум 2 ключа и для возможности эффективного split+rebalance это правило должно выполняться после разделения страницы пополам. Соответственно 2*2 = 4.

                            Howard Chu писал, что Keys must be small enough to fit on a page, and a page must contain at least two keys in order for the B-tree structure to be maintained. So the absolute max is 1/2 the page size; we use 1/3 to avoid size issues when using DUPSORT mixed with other data. https://bugzilla.redhat.com/show_bug.cgi?id=1086784#c5


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

                            Прекрасно это понимаю, но это неудобно. Так, я не могу абстрагировавшись создать "сверху" родительскую транзакцию (например, в декораторе) и просто передать ее в подчиненную функцию. Мне нужно знать, пишет ли код "снизу" или только читает.


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

                            Это было вообще киллер-фичей для меня. Молниеносная пагинация и вычисление total по диапазону BTree только один из примеров.


                            Технически очередь (FIFO или с приоритетами) тривиально реализуется поверх key-value. В случае LMDB при этом в качестве ключа можно использовать номер транзакции (если требуется FIFO), а в MDBX также есть генераторы последовательностей.

                            Да. Верно. Но технически это не будет дотягивать до DB_QUEUE в Berkeley DB. Во-первых,
                            процесс может ожидать следующую запись с помощью DB_CONSUME_WAIT, не требуя постоянного опроса БД. В противном случае придется делать опрос и сигнализацию (через ZMQ или сырой UDP-мультикаст). Во-вторых, репликация очереди происходит специальным образом: put реплицируется, а consume — нет (поэтому реплики тоже могут делать локальный consume). Наконец, очередь легко заоптимизировать. В Berkeley DB очереди работают с огромной скоростью.


                            Если же требуется "тупая" очередь в виде максимально эффективного FIFO с полной durability, то специализированные решения на базе кольцевых буферов будут все равно эффективнее.

                            Но мы не сможем делать операции с внешней очередью и базой данных атомарно.


                            Однако, если это тянуть в key-value движок хранения, то снова получится "швейцарский нож", но не действительно надежный охотничий или удобный перочинный.

                            Проблемы с надежностью у Berkeley DB вызваны главным образом из-за её хрупкой подсистемы блокировок, которая требует внешнего разрешения дедлоков и восстановления. Для DB_BTREE дедлоки иногда возникают вообще by design.

                              0
                              Howard Chu писаk Howard Chu писал, что Keys must be small enough to fit on a page...

                              Да, максимальная длина ключа завит от типа БД. У себя я в итоге просто добавил соответствующие функции. Кроме этого, точные значения указаны в соответствующем разделе README.


                              я не могу абстрагировавшись создать "сверху" родительскую транзакцию (например, в декораторе) и просто передать ее в подчиненную функцию. Мне нужно знать, пишет ли код "снизу" или только читает.

                              Оно так не может работать, точнее может но совсем не всегда.


                              Если у вас все начинается с читающей транзакции, то начать "дочернюю" пишущую возможно только если после старта родительской читающей не было изменений в данных.
                              Чтобы устранить это ограничение требуется и/или:
                              а. отказаться от single writer концепта (и войти в ад блокировок), т.е. сделать еще одну Berkeley DB или PostreSQL (у Константина Осипова было отличное выступление на Highload++, где оно пояснял что стоит за не-single writer).
                              б. сделать некую среду исполняющую формальный язык (SQL с хранимыми процедурами), чтобы она автоматически могла отменять, рестартовать транзакции чтобы повторно выполнять application код.


                              Если же у вас все начинается с пишущей транзакции, то опять-таки, либо отказ от single-writer (и все как выше), либо все вложенные транзакции также пишущие.


                              Это было вообще киллер-фичей для меня. Молниеносная пагинация и вычисление total по диапазону BTree только один из примеров.

                              Вот мне сейчас тоже потребовалась для оценки костов с целью выбора варианта выполнения запросов, но поздно пить боржоми (


                              технически это не будет дотягивать до DB_QUEUE в Berkeley DB. Во-первых,
                              процесс может ожидать следующую запись с помощью DB_CONSUME_WAIT.

                              Согласен, если нужен WAIT, то при существующем API потребуется полинг, т.е. тут центральная "проблема" в том, что исходно такие сценарии использования (ожидания данных) не рассматривались (и меня уже просили что-нибудь прибить "хотя-бы гвоздями").


                              Но мы не сможем делать операции с внешней очередью и базой данных атомарно.

                              Это можно если очередь допускает соответствующие блокировки и commit/revert, но в одном флаконе конечно удобнее (Tarantool).


                              Проблемы с надежностью у Berkeley DB вызваны главным образом из-за её хрупкой подсистемы блокировок, которая требует внешнего разрешения дедлоков и восстановления. Для DB_BTREE дедлоки иногда возникают вообще by design.

                              Тут вот есть принципиальная вещь — Проблемы "by design" начинаются если не-single writer.
                              Поэтому поэтому в MDBX/LMDB сознательно этой проблемы просто не создается, вместо того чтобы героически с ней биться.

                          0

                          Круто, ребята в LMDB реализовали почти все мои идеи. Но есть пара нюансов:


                          1. Глобальное key-value дерево это дико не удобно и не особо быстро. Из-за чего у вас куча костылей с компаратором. Моя идея в том, чтобы иметь в качестве значений другие деревья. Таким образом файловая иерархия отобразится наиболее естественным образом. Массивы, словари, любые структуры можно описать таким образом.


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


                          3. Индексы должны быть всё же в СУБД, чтобы она сама гарантированно обновляла все связанные деревья при обновлении данных. Полагаться на прикладной код в этом вопросе — стрелять себе в ногу. Жаль, что в LMDB этот вопрос не продуман изначально.


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


                            Это не ошибка, а осознанное архитектурное решение. Если я вас правильно понимаю, речь о том, что гораздо красивее было бы решение, где в качестве первичного ключа выступает примитивная структура, где есть только суррогатный идентификатор и всё. А все вторичные и индексные ключи просто ссылаются на него, держа его в своей value-части. Таким образом то же переименование не провоцирует большого количества изменений, максимум – перезапись индексных ключей, ориентированных на имя.

                            Но тут всё дело в нашем API. К сожалению у нод в дереве нет никакого идентификатора, который всегда существует и никогда не изменяется. Единственно на что можно рассчитывать – уникальность имени внутри одной папки. Таким образом процедура вычисления изменений внутри папки, о которой я упоминал в первой главе, строится на сравнении сортированных по имени списков дочерних элементов из локального папки и её серверного аналога. Поскольку эта процедура крайне частая и при полном слиянии двух деревьев (локального и серверного) в ней участвуют все элементы основной таблицы, то именно она должна быть максимально перфомансной, и именно под неё у нас и заточен первичный ключ. Ну а переименование – это суперредкая процедура, в рамках которой трогается перезаписывается крайне небольшое количество записей.
                              0

                              Как с такими ключами вы решаете такую ситуацию: пользователь на двух разных девайсах под одним и тем же именем сохранил разные файлы? И таких файлов >9000.

                                0
                                Если речь про файлы с одинаковым именем внутри одной папки, то сервер такое сделать не даст. Если про разные, то нет проблем. В составном ключе есть не только имя, но и суррогатный идентификатор родительской директории.
                                  0

                                  Пользователь уже поменял данные на клиенте. Задача сервера синхронизовать эти два клиента. Сервер тут вообще ничего не решает. Как пользователь я не хочу терять ни тот ни другой файл. И уж точно не хочу любоваться на ошибку "этот пользователь неправильный, несите следующего".

                                    0

                                    Предложите ваше (идеальное/лучшее) решение?

                                      +1

                                      Варианты, что можно тут сделать, ограничиваются лишь вашей фантазией. Все они сводятся к ручному или автоматическому переименованию на клиенте или на сервере.

                                0
                                Глобальное key-value дерево это дико не удобно и не особо быстро. Из-за чего у вас куча костылей с компаратором. Моя идея в том, чтобы иметь в качестве значений другие деревья. Таким образом файловая иерархия отобразится наиболее естественным образом. Массивы, словари, любые структуры можно описать таким образом.

                                Не стоит делать выводы по одной статье, которая не совсем про саму БД.
                                В MDBX/LMDB собственно и есть "другие деревья в качестве значений":


                                • внутри одной "большой БД" (файла на диске) может быть куча вложенных именованных БД (пространства) key-value.
                                • Отдельная фишка в поддержке массивных multi-value, когда одному ключу соответствует несколько (даже очень много) значений. Исторически (начиная с Berkeley DB) такие кейсы называются "duplicates" и/или "sorted duplicates", т.е. имеется в виду что multi-value можно рассматривать как несколько записей с одинаковым ключом.
                                  Так вот, multi-value в MDBX/LMDB хранятся во вложенных деревьях. При этом экономится как место (один экземпляр ключа на все multi-value), так и обеспечивается Olog(N) для всех операций, включая поиск конкретных значений. Для вторичных индексов это просто killer feature.

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

                                Это продолжение holly war между индексами "как в PostgreSQL" и "как в MySQL". В разных кейсах один из вариантов обычно выигрывает, но не более того (оба варианта не серебряная пуля).


                                Индексы должны быть всё же в СУБД, чтобы она сама гарантированно обновляла все связанные деревья при обновлении данных. Полагаться на прикладной код в этом вопросе — стрелять себе в ногу. Жаль, что в LMDB этот вопрос не продуман изначально.

                                Эмм, MDBX/LMDB — это key-value, Карл!
                                Никто не запрещает (при должной сноровке) забивать шурупы этими молотками.
                                Автор(ы) статьи сами решили реализовать нужные индексы поверх модели key-value — это их решение, никак не связанное с ограничениями MDBX/LMDB.
                                Если не хочется так заморачиваться (и пару раз попасть в ногу) с собственными индексами, то следует смотреть на libfpta или всё тот-же SQLite.

                                  –2
                                  внутри одной "большой БД" (файла на диске) может быть куча вложенных именованных БД (пространства) key-value.

                                  Вот, кстати, тоже спорный момент. Я склоняюсь к тому, как это сделано в OrientDB: есть N кластеров (файлов), куда по определённым правилам раскидываются узлы. И эти кластеры могут независимо реплицироваться на разные ноды (сервера). Это позволяет связанные подграфы держать рядом, при этом не держа на одном сервере вообще всю бд. Вот, кстати, партицирования у LMDB я так понимаю тоже нет. Я вот думаю раскидывать так же по файлам. Плюс мета-кластер для хранения мета-страниц в вашей терминологии. Плюс это могло бы дать такую фичу, как параллельная запись. Например, отдельный поток мог бы спокойно писать в свой кластер, не блокируя записи в другие кластеры. И только мета-кластер писался бы одним выделенным потоком, но там записи тривиальные.


                                  Эмм, MDBX/LMDB — это key-value, Карл!

                                  А, ну если так и собираетесь оставаться в детском саду, то вы мне не конкурент.)


                                  следует смотреть на libfpta или всё тот-же SQLite

                                  Спасибо, конечно, но табличками я сыт по горло. Вы работали когда-нибудь с графовыми СУБД?

                                    +1
                                    Я склоняюсь к тому, как это сделано в OrientDB: есть N кластеров (файлов), куда по определённым правилам раскидываются узлы…
                                    Вот, кстати, партицирования у LMDB я так понимаю тоже нет.

                                    А причем тут OrientDB и партиционирование?
                                    MDBX/LMDB — это встраиваемые движки key-value для совместной работы с БД несколькими локальными процессами. В этих целевых сценариях MDBX обеспечивает до 1M пишущих транзакций в секунду и примерно линейно масштабирутся в производительности чтения по ядрам CPU (десятки миллионов запросов в секунду, пока не упирается в memory bandwidth).
                                    Никакому OrientDB в таких сценариях подобное и не снилось.
                                    А для других (не целевых для MDBX) сценариев использования есть другие движки или СУБД, в том числе со всяческим партиционированием и SQL с блекджеком.


                                    А, ну если так и собираетесь оставаться в детском саду, то вы мне не конкурент.)

                                    Хм, а после "детского сада" сколько СУБД (в широком смысле) вы написали (или приняли участие) и довели до production?


                                    Спасибо, конечно, но табличками я сыт по горло.

                                    Каждый "сыт" тем что ему не нужно, и наоборот.
                                    Т.е. "таблички" не в чем не виноваты, это решение предназначенное для некоторого подмножества сценариев использования.


                                    Вы работали когда-нибудь с графовыми СУБД?

                                    Ну делал я их, и видимо скоро снова продолжу (варианты для RDF).

                                0

                                Интересно, вы сравниваете с sqlite, но правильно возможно сравнивать с например leveldb. Есть у вас особенности почему например lmdb будет лучше чем leveldb в вашем случае?

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое