LMDB (Lightning Memory-Mapped Database)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:47, 11 ноября 2017.
OpenLDAP Lightning Memory-Mapped Database
Создатели: Howard Chu
Разработчики: Symas
Постоянный выпуск: 0.9.21
Состояние разработки: production
Написана на: C
Операционная система: Unix, Linux, Windows, AIX, Sun Solaris, SCO Unix, macOS, iOS
Размер дистрибутива: 64KB, 7KLOC
Тип ПО: Embedded database
Лицензия: OpenLDAP Public License
Веб-сайт URL

Lightning Memory-Mapped Database - программная библиотека, представляющая собой высоко-производительную встроенную транзакционную базу данных, в основе которой - хранилище "ключ-значение". LMDB была написана на C, но имеет API для работы с несколькими языками программирования. LMDB хранит произвольные пары "ключ-данные" как массивы байтов, поддерживает возможность записи нескольких блоков данных по одному ключу, имеет диапазонно-ориентированный поиск и специальный режим, который позволяет добавлять записи в конец базы данных (MDB_APPEND), который позволяет получить впечетляющую разницу в скорости записи по сравнению с похожими хранилищами. LMDB это не реляционная база данных, это строгое "ключ-значение" хранилище, на подобии Berkeley DB и dbm.

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

История

Проект LMDB был впервые обсужден в сообщении 2009 года в списке рассылки разработчиков OpenLDAP в контексте изучения решений проблемы управления кэшем, вызванной зависимостью проекта от Berkeley DB. Конкретной целью было заменить несколько уровней конфигурации и кэширования, присущих проекту Berkeley DB, с одним, автоматически управляемым кешем под управлением операционной системы хоста. Разработка впоследствии началась, первоначально как ответвление аналогичной реализации из проекта OpenBSD ldapd. Первая общедоступная версия появилась в исходном репозитории OpenLDAP в июне 2011 года. Проект был известен под названием MDB до ноября 2012 года, после чего он был переименован, во избежание конфликтов с существующим программным обеспечением.

Техническое описание

LMDB использует структуру данных дерева B+. Эффективность его строения и малая занимаемая площадь имели непреднамеренный побочный эффект, обеспечивающий хорошую производительность записи. LMDB имеет API, похожий на DB Berkeley и dbm. LMDB рассматривает память компьютера как одно адресное пространство, разделяемое несколькими процессами или потоками, используя разделяемую память с семантикой копирования на запись (исторически известной как одноуровневое хранилище). Из-за большинства прежних вычислительных архитектур, имеющих 32-битные ограничения адресного пространства памяти, которые накладывают жесткий размер 4 ГБ на размер любой базы данных с использованием таких технологий, эффективность метода прямого сопоставления базы данных в одноуровневом хранилище была строго ограничена. Однако сегодняшние 64-разрядные процессоры теперь в основном реализуют 48-битные адресные пространства, предоставляя доступ к 47-битным адресам или 128 терабайтам размера базы данных, что снова делает базы данных с использованием общей памяти полезными в реальных приложениях.

Особенно интересными техническими характеристиками LMDB являются:

  • Использование дерева B+[1]. Если экземпляр LMDB находится в общей памяти, а размер блока дерева B+ устанавливается на размер страницы ОС, доступ к хранилищу LMDB чрезвычайно эффективен с точки зрения памяти.
  • Новые данные записываются без перезаписи или перемещения существующих данных. Это гарантирует целостность и надежность данных без использования журналов транзакций или служб очистки.
  • Предоставление уникального режима добавления-записи (MDB_APPEND), который реализуется, позволяя добавлять новую запись непосредственно в конец дерева B+. Это уменьшает количество операций чтения и записи страниц, что приводит к значительному повышению производительности, но требует, чтобы программист отвечал за сортировку ключей при хранении в БД.
  • Семантика копирования при записи помогает обеспечить целостность данных, а также обеспечивает транзакционные гарантии и одновременный доступ читателей, не требуя блокировки даже нынешним автором. Новые страницы памяти, необходимые для внутренней модификации данных, выделяются семантикой копирования при записи базовой ОС: сама библиотека LMDB никогда не модифицирует старые данные, к которым обращаются читатели, потому что она просто не может этого сделать: любые обновления в общей памяти автоматически создают полностью независимую копию страницы памяти, которая изменяется.
  • Поскольку LMDB отображается в память, он может возвращать прямые указатели на адреса памяти ключей и значений через свой API, тем самым избегая ненужного и дорогого копирования памяти. Это приводит к значительному повышению производительности (особенно когда хранимые значения чрезвычайно велики) и расширяет возможности использования LMDB.
  • LMDB также отслеживает неиспользуемые страницы памяти, используя дерево B+. Благодаря отслеживанию неиспользуемых страниц, потребность в сборке мусора (и фазе сбора мусора, которая будет потреблять процессорное время) полностью исключается. Транзакция, которые нуждаются в новых страницах, сначала получают страницы из этого неиспользуемых страниц; только после того, как они будут использованы, она расширится на ранее неиспользуемые области базового файла с отображением памяти. В современной файловой системе с разреженной поддержкой файлов это помогает минимизировать фактическое использование диска.

Одновременный доступ

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

Производительность

В 2011 году Google опубликовала программное обеспечение, которое позволило пользователям создавать микротесты, сравнивающие производительность LevelDB с SQLite и Kyoto Cabinet в различных сценариях. В 2012 году Symas добавила поддержку LMDB и Berkeley DB и выпустила обновленное программное обеспечение для тестирования. Полученные результаты показали, что LMDB превзошел все остальные базы данных в операциях чтения и пакетной записи. SQLite с LMDB преуспел в операциях записи, и особенно в синхронной/транзакционной записи.

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

Надежность

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

Две академические работы симпозиума USENIX OSDI описывали отказ механизмов баз данных (включая LMDB) при внезапной потере мощности или сбое системы[2]. В работе Пиллай и др. не обнаружен сбой в LMDB, который произошел бы в рассматриваемых реальных файловых системах; единственный отказ, выявленный в исследовании в LMDB, относится только к гипотетическим файловым системам. Работа Май Чжэн и др. указывает на сбои в LMDB, но наличие этих уязвимостей зависит от использования fsync или fdatasync. Использование fsync устраняет проблему. Выбор fsync или fdatasync - это переключатель времени компиляции, который не является поведением по умолчанию в текущих сборках LMDB GNU/Linux, но по умолчанию используется для macOS, * BSD, Android и Windows. По умолчанию GNU / Linux сборки LMDB являются единственными, уязвимыми для проблемы, обнаруженной исследователями, однако LMDB может быть просто перестроен пользователями GNU/Linux для использования fsync.

Лицензия

В июне 2013 года Oracle изменила лицензию Berkeley DB с Sleepycat на General Public License Affero, тем самым ограничив ее использование в самых разных приложениях. Это заставило проект Debian исключить эту библиотеку, начиная с версии 6.0. Также критиковали, что эта лицензия не является дружественной к коммерческим перераспределителям. Дискуссия была вызвана тем фактом, что с LMDB могут произойти такие же изменения лицензии. Автор Говард Чу дал понять, что LMDB является частью проекта OpenLDAP, у которого была лицензия на стиль BSD, прежде чем он присоединился, и лицензия останется прежней[3].

Проблема с лицензией Berkeley DB привела к тому, что основные дистрибутивы GNU/Linux, такие как Debian, полностью прекратили использование Berkeley DB, отдав предпочтение LMDB.

API и использование

Существуют "обертки" для некоторых языков программирования, таких как C++[4], Python [5], Lua, Ruby, JS, C#, Perl, PHP, Tcl and Common Lisp. Полный список доступных языков на официальном сайте LMDB.

Говард Чу портировал SQLite 3.7.7.1, чтобы использовать LMDB вместо встроенного B-дерева, вызывая конечный результат SQLightning. Один цитированный тест вставки 1000 записей был в 20 раз быстрее (чем исходный SQLite с его реализацией B-дерева). LMDB доступен в качестве резервного хранилища для других проектов с открытым исходным кодом, включая Cyrus SASL, Heimdal Kerberos и OpenDKIM. Он также доступен в некоторых других проектах NoSQL, таких как MemcacheDB и Mapkeeper. LMDB использовался для того, чтобы хранилище в памяти Redis сохраняло данные на диске. Существующий back-end в Redis проявлял патологическое поведение в редких случаях, и требовалась замена. Однако барочный API LMDB подвергся критике, заставив писать много кода, для того чтобы выполнить простые вещи, однако его производительность и надежность во время тестирования были значительно лучше, чем у альтернативных серверов резервного копирования, которые были опробованы.

Независимый сторонний разработчик программного обеспечения использовал Python и LMDB в высокопроизводительной среде и опубликовал на известном техническом новостном сайте Slashdot статью о том, что система смогла успешно поддерживать 200 000 одновременных операций чтения, записи и удаления в секунду (в общей сложности 600 000 операций с базой данных в секунду).

Поддерживаемые приложения

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

  • The Debian, Ubuntu, Fedora, OpenSuSE
  • OpenLDAP
  • Postfix
  • PowerDNS
  • CFEngine
  • Shopify
  • Caffe
  • FineDB
  • Extenium
  • GNU Guile
  • InfluxDB
  • urbackup
  • Knot DNS
  • Knot Resolver
  • Monero

Литература

  1. B+-дерево [Электронный ресурс] :Материал из https://ru.wikipedia.org: - Режим доступа: https://ru.wikipedia.org/wiki/B%2B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE B+-дерево
  2. USENIX [Электронный ресурс] :Материал из https://www.usenix.org: - Режим доступа: https://www.usenix.org/conference/osdi14/technical-sessions/presentation/pillai All File Systems Are Not Created Equal
  3. Berkeley DB [Электронный ресурс] :Материал из http://programmers-in-ua.blogspot.ru: - Режим доступа: http://programmers-in-ua.blogspot.ru/2013/07/oracle-berkeley-db.html Oracle меняет лицензию Berkeley DB
  4. LMDB C++11 wrapper [Электронный ресурс] :Материал из https://github.com: - Режим доступа: https://github.com/bendiken/lmdbxx LMDB C++11 wrapper
  5. LMDB Python wrapper [Электронный ресурс] :Материал из https://github.com: - Режим доступа: https://github.com/dw/py-lmdb/ LMDB Python wrapper