Организуем индексы на движке LMDB
kayo — Втр, 24/11/2015 - 16:40
Системы управления каталогами, вроде LDAP, и прочие иерархические СУБД нуждаются в хранилищах значений по ключу с быстрой выборкой и транзакционностью. Традиционно для организации встроенных баз данных использовалась Berkeley Database (BDB). Однако, в настоящий момент этот движок БД столкнулся с существенными ограничениями своей внутренней архитектуры, которые не могут быть преодолены эволюционным путём. В этой заметке мы коснёмся нового движка баз данных LMDB, который может послужить серьёзной альтернативой BDB во многих проектах.
Проблемы берклиевской базы данных
Появилась она достаточно давно, во времена, когда многопоточность была бесполезна ввиду присутствия лишь одного вычислительного блока в системе. Все процессоры были одноядерными, а системы почти повсеместно позволяли устанавливать лишь один процессор. С тех пор аппаратные и программные платформы значительно эволюционировали, однако на архитектуре BDB это сказалось незначительно. Но потребности в работе с данными множеством потоков имелись, и движок базы приходилось как-то адаптировать. Для синхронизации операций выборки и модификации были использованы примитивы блокировок, но вместе с тем снижалась общая производительность из-за вносимых задержек. Параллельно развивалась подсистема кэширования, которая позволила ускорить выборку данных, но вместе с тем внесла свой оверхед в виде нескольких уровней кэша. Всё это привело к тому, что в поточно-безопасной версии BDB существуют конфликтные ситуации, связанные с блокировками, которые могут быть разрешены только на уровне приложения.
Молниеносная отображенная в память база данных
Однажды люди из команды OpenLDAP пришли к выводу, что архитектура BDB ограничивает производительность работы с данными, и они решили разработать свою встраиваемую базу данных на иных принципах. Это должна была быть встраиваемая СУБД ключ-значение, но реализованная с учетом текущего уровня развития операционных систем и наиболее оптимально использующая аппаратные ресурсы.
Наряду с появлением механизма отображения файлов в оперативную память (mamory mapping или кратко mmap), операционные системы научились достаточно эффективно кэшировать дисковый ввод-вывод. Отображение файлов в память организовано так, что данные подгружаются не целиком а страницами по мере надобности, поэтому для отображения больших файлов вовсе не требуется столь же огромный объём оперативной памяти. Эксперименты показали, что скорость чтения возрастает более чем на порядок. Поэтому отпадала необходимость в подсистеме кэширования на уровне приложения.
Другим краеугольным камнем были блокировки. Некие механизмы синхронизации безусловно необходимы в многопоточных приложениях. Но блокировки неизбежно вносят задержки, и снижают общую скорость выборки и модификации данных. Каждый читающий поток обязан ждать, пока другой поток изменит данные. При этом уменьшение атомарности блокировок не решает проблему, хоть и даёт выигрыш в некоторых случаях. То есть, если блокировать отдельные записи вместо всей базы целиком, можно осуществить чтение тех данных, которые ни один поток не изменяет в данный момент, но как только в выборку попали изменяющиеся данные, сразу же читающие процессы будут заблокированы до окончания записи.
Механизм отображения в память делает довольно дешевым копирование во время записи (copy-on-write или кратко cow), что позволяет полностью избежать блокировок читающих процессов введением так называемого механизма снимков (snapshots). Для приложения это означает буквально следующее: при модификации создаётся лёгкая копия базы данных, с которой работает модифицирующий процесс, тогда как читающие процессы продолжают работать со старой копией до тех пор пока транзакция не будет применена. В этот момент новая копия станет текущей, а старая будет отброшена. Отмена транзакции просто отбросит всё, что мы изменили.
На уровне операционной системы и в частности подсистемы ввода-вывода легковесность этого механизма копирования при записи осуществляется копированием блоков в страницы памяти и обратно. Со стороны ОС, у которой есть представление об организации данных на низком уровне, достаточно просто выделить новые блоки в файловой системе и пометить более не использующиеся как свободные.
Этот новый движок баз данных был впоследствии назван Lightning Memory-mapped Database (мой вольный перевод: молниеносная отображенная в память база данных). В общем-то название соответствует действительности. Выборка значений по ключу необычайно быстрое. С модификацией всё обстоит не так однозначно и скорость зависит от варианта использования. Это может быть не медленнее, чем в случае использования BDB, либо значительно медленнее. Объяснение достаточно простое: сам по себе выбранный механизм mmap заточен больше на чтение, чем на запись. Однако, разработчики всё ещё ведут исследования в данном направлении. Хоть для класса задач, которые решает OpenLDAP, запись не является критическим местом.
Пробуем LMDB
Чтобы побыстрому попробовать и понять, что к чему, ничего не компилируя, воспользуемся привязками LMDB API для языка Lua. Я использовал модуль lightningmdb.
Целочисленный индекс типа «первичный ключ»
Первое, что мы попытаемся реализовать — это такой тип целочисленного индекса который обычно используется в качестве уникального идентификатора записей в реляционных базах данных, обычно называемый первичным ключом.
-- подключаем модуль с биндингами
local lmdb = require 'lightningmdb'
-- упаковка числового идентификатора в бинарную строку
local function toID(n)
return string.pack('L', n)
end
-- извлечение числового идентификатора из бинарной строки
local function fromID(s, ...)
if s ~= nil then
local p, n = string.unpack(s, 'L')
return n, unpack(arg)
end
return s, unpack(arg)
end
-- вставка идентифицированных значений из таблицы
local function putIDs(env, db, ids)
print "begin write txn"
-- начинаем транзакцию
local txn = env:txn_begin(nil, 0)
for id, val in pairs(ids) do
print("put id", id, "with", val)
-- вставляем элемент
txn:put(db, toID(id), val, 0)
end
print "commit write txn"
-- применяем транзакцию
txn:commit()
end
-- удаление значений по идентификаторам из таблицы
local function delIDs(env, db, ids)
print "begin write txn"
-- начинаем транзакцию
local txn = env:txn_begin(nil, 0)
for _, id in pairs(ids) do
print("del id", id)
-- удаляем значение по идентификатору
txn:del(db, toID(id), nil, 0)
end
print "commit write txn"
-- применяем транзакцию
txn:commit()
end
-- получение значений по идентификаторам из таблицы
local function getIDs(env, db, ids)
print "begin read txn"
-- начинаем читающую транзакцию
local txn = env:txn_begin(nil, lmdb.MDB_RDONLY)
for _, id in pairs(ids) do
-- извлекаем значение по идентификатору
print("get id", id, txn:get(db, toID(id)))
end
print "reset read txn"
-- сбрасываем читающую транзакцию
txn:reset()
end
print "create env"
-- создаём "среду"
local env = lmdb.env_create()
-- настраиваем
env:set_maxreaders(100)
env:set_maxdbs(10000)
env:set_mapsize(1024*1024*1024)
print "open db"
-- открываем базу данных в файловой системе
env:open('./pki', 0, 420)
print "begin txn"
-- начинаем транзакцию инициализации
local txn = env:txn_begin(nil, 0)
print "open id db"
-- объявляем базу данных для нашего индекса
local id_db = txn:dbi_open('primary_key', lmdb.MDB_INTEGERKEY + lmdb.MDB_CREATE)
print "commit txn"
-- завершаем транзакцию инициализации
txn:commit()
-- вставляем значения
putIDs(env, id_db, {
[1] = "a",
[2] = "b",
[5] = "d",
[7] = "c",
[4] = "c",
[10] = "d",
[276] = "a",
})
-- извлекаем некоторые значения
getIDs(env, id_db, {1, 7, 3, 11, 12, 276})
-- удаляем некоторые значения
delIDs(env, id_db, {1, 12})
После создания среды желательно открыть все используемые базы данных (dbi) в первой же транзакции, чтобы впоследствии иметь возможность выполнять операции над ними. В транзакциях могут быть задействовано несколько баз данных одновременно. Транзакции также могут быть вложенными, в этом случае транзакция верхнего уровня указывается в качестве первого аргумента в функции txn_begin.
Важное замечание: перед тем, как запускать, создайте каталог для базы данных, который указали в вызове env:open. Вот, что будет выведено после запуска примера:
create env open db begin txn open id db commit txn begin write txn put id 276 with a put id 2 with b put id 10 with d put id 1 with a put id 4 with c put id 5 with d put id 7 with c commit write txn begin read txn get id 1 a get id 7 c get id 3 nil get id 11 nil get id 12 nil get id 276 a reset read txn begin write txn del id 1 del id 12 commit write txn
Это лишь простой пример использования, более сложные выборки делаются с применением курсоров, что будет показано ниже.
-- ставим курсор на первый идентификатор
-- и возвращаем его
local function curFirst(cur)
return fromID(cur:get(nil, lmdb.MDB_FIRST))
end
-- ставим курсор на следующий идентификатор
-- и возвращаем его
local function curNext(cur)
return fromID(cur:get(nil, lmdb.MDB_NEXT))
end
-- ставим курсор на последний идентификатор
-- и возвращаем его
local function curLast(cur)
return fromID(cur:get(nil, lmdb.MDB_LAST))
end
-- ставим курсор на предыдущий идентификатор
-- и возвращаем его
local function curPrev(cur)
return fromID(cur:get(nil, lmdb.MDB_PREV))
end
-- ставим курсор на идентификатор,
-- который равен или больше выбранного,
-- и возвращаем его
local function curFrom(cur, id)
return fromID(cur:get(toID(id), lmdb.MDB_SET_RANGE))
end
print "begin read txn"
-- начинаем транзакцию чтения
local txn = env:txn_begin(nil, lmdb.MDB_RDONLY)
print "open id cursor"
-- открываем курсор
local cur = txn:cursor_open(id_db)
print "get first item"
-- получаем первый элемент
print(curFirst(cur))
print "get last item"
-- получаем последний элемент
print(curLast(cur))
-- выведем все элементы с первого
-- по порядку
print "get all items"
-- получаем первый элемент
print(curFirst(cur))
-- проходим до конца индекса
for k, v in curNext, cur do
print(k, v)
end
-- выведем все элементы с последнего
-- в обратном порядке
print "get all items reverse"
-- получаем последний элемент
print(curLast(cur))
-- проходим до начала индекса
for k, v in curPrev, cur do
print(k, v)
end
print("get item after 3")
-- встаём на ближайший идентификатор после 3
print(curFrom(cur, 3))
-- проходим до конца индекса
for k,v in curNext, cur, 0 do
print(k,v)
end
print("get item before 3")
-- встаём на ближайший идентификатор после 3
curFrom(cur, 3)
-- делаем шаг назад, чтобы
-- встать на ближайший идентификатор перед 3
print(curPrev(cur))
-- проходим до начала индекса
for k,v in curPrev, cur, 0 do
print(k,v)
end
-- комбинируя эти приёмы,
-- можно делать любые выборки
print "close id cursor"
-- закрываем курсор
cur:close()
print "reset read txn"
-- завершаем транзакцию чтения
txn:reset()
print "close db"
-- и не забываем закрыть "среду"
env:close()
-- закрывать открытые dbi не требуется,
-- это будет сделано автоматическиКак видим, курсоры позволяют быстро перемещаться по всему индексу и делать произвольные выборки. Вот что выведет продолжение примера:
begin read txn open id cursor get first item 2 b get last item 276 a get all items 2 b 4 c 5 d 7 c 10 d 276 a get all items reverse 276 a 10 d 7 c 5 d 4 c 2 b get item after 3 4 c 5 d 7 c 10 d 276 a get item before 3 2 b close id cursor reset read txn close db
Далее рассмотрим больше возможностей.
Множественный лексический индекс
Выборки по целочисленному индексу, конечно, вещь нужная, но применяется не так широко, как выборка по ключевым словам или тегам и прочим лексическим элементам, вроде корней не общеупотребительных слов в системах полнотекстового поиска. LMDB также предоставляет возможность хранить не уникальные ключи в базе данных, или, другими словами, связывать несколько значений с одним ключом.
Допустим, у нас есть база данных устройств на микроконтроллерах и некоторый тег, который указывает тип примененных микроконтроллеров в устройствах. В терминах реляционной модели данных можно сказать, что тип отношения: многие ко многим, то есть в одном устройстве могут применяться разные типы микроконтроллеров, а один и тот же тип может присутствовать в разных устройствах. Допустим, что каждое устройство уже пронумеровано первичным ключом из первого примера, то есть в качестве значений мы можем использовать целочисленные идентификаторы, чем упростим реализацию и значительно повысим производительность нашего индекса.
Итак, вот моя реализация данной системы:
local lmdb = require 'lightningmdb'
local function toID(n)
return string.pack('L', n)
end
local function fromID(k, s, ...)
if s ~= nil then
local p, n = string.unpack(s, 'L')
return k, n, unpack(arg)
end
return k, s, unpack(arg)
end
-- вставка пар ключ-значение
local function putKWs(env, db, kws)
print "begin write txn"
local txn = env:txn_begin(nil, 0)
for _, x in pairs(kws) do
local k, v = x[1], x[2]
print("put id", k, "with", v)
txn:put(db, k, toID(v), 0)
end
print "commit write txn"
txn:commit()
end
-- удаление пар ключ-значение
local function delKWs(env, db, kws)
print "begin write txn"
local txn = env:txn_begin(nil, 0)
for _, x in pairs(kws) do
local k, v = x[1], x[2]
print("del id", k)
txn:del(db, k, toID(v), 0)
end
print "commit write txn"
txn:commit()
end
-- установка курсора в начало базы
local function curFirst(cur)
return fromID(cur:get(nil, lmdb.MDB_FIRST))
end
-- установка курсора на требуемый ключ
local function curFind(cur, key)
return fromID(cur:get(key, lmdb.MDB_SET))
end
-- перемещение курсора на следующий ключ
local function curNext(cur)
return fromID(cur:get(nil, lmdb.MDB_NEXT))
end
-- выборка значений для требуемых ключей
local function getKWs(env, db, kws)
print "begin read txn"
local txn = env:txn_begin(nil, lmdb.MDB_RDONLY)
if kws then
for _, x in pairs(kws) do
local cur = txn:cursor_open(db)
print("get id", x)
print(curFind(cur, x))
for k,v in curNext, cur do
if k ~= x then break end
print(k,v)
end
cur:close()
end
else
print "get all items"
local cur = txn:cursor_open(db)
print(curFirst(cur))
for k, v in curNext, cur do
print(k, v)
end
cur:close()
end
print "reset read txn"
txn:reset()
end
print "create env"
local env = lmdb.env_create()
env:set_maxreaders(100)
env:set_maxdbs(10000)
env:set_mapsize(1024*1024*1024)
print "open db"
env:open('./kwi', 0, 420)
print "begin txn"
local txn = env:txn_begin(nil, 0)
print "open kw db"
-- объявляем базу данных
local kw_db = txn:dbi_open('keywords',
lmdb.MDB_DUPSORT +
lmdb.MDB_DUPFIXED +
lmdb.MDB_INTEGERDUP +
lmdb.MDB_CREATE)
print "commit txn"
txn:commit()
-- заполняем базу
putKWs(env, kw_db, {
{"stm32", 1},
{"xmega", 2},
{"pic16", 2},
{"stm32", 3},
{"msp430", 1},
{"atmega", 4},
{"msp430", 2},
{"stm32", 7},
{"pic16", 3},
})
-- выводим все записи
getKWs(env, kw_db)
-- удаляем записи
delKWs(env, kw_db, {
{"pic16", 2}
})
-- снова выводим все записи
getKWs(env, kw_db)
-- выводим требуемые записи
getKWs(env, kw_db, {"stm32", "msp430"})
print "close db"
env:close()Вот как отработает пример:
create env open db begin txn open kw db commit txn begin write txn put id stm32 with 1 put id xmega with 2 put id pic16 with 2 put id stm32 with 3 put id msp430 with 1 put id atmega with 4 put id msp430 with 2 put id stm32 with 7 put id pic16 with 3 commit write txn begin read txn get all items atmega 4 msp430 1 msp430 2 pic16 2 pic16 3 stm32 1 stm32 3 stm32 7 xmega 2 reset read txn begin write txn del id pic16 commit write txn begin read txn get all items atmega 4 msp430 1 msp430 2 pic16 3 stm32 1 stm32 3 stm32 7 xmega 2 reset read txn begin read txn get id stm32 stm32 1 stm32 3 stm32 7 get id msp430 msp430 1 msp430 2 reset read txn close db
Думаю, тут нужны некоторые пояснения касательно флагов, выбранных при инициализации базы данных для индекса. Давайте обо всех по порядку:
- MDB_DUPSORT - позволяет хранить не уникальные ключи в базе данных
- MDB_DUPFIXED - заявляет о том, что значения будут фиксированного размера
- MDB_INTEGERDUP - заявляет о том, что значения будут целочисленными
Заключение
LMDB активно развивается, и наряду с оптимизацией появляются новые возможности. С другой стороны этот движок постепенно находит всё больше применений там, где традиционно использовался BDB, а также и в новых проектах. К примеру, есть интересный порт SQLite3 на LMDB. Его я пока не тестировал, на пригодность в продакшне, но теоретически скорость выборки данных должна быть существенно выше чем в штатном движке btree от SQLite3.
Отправить комментарий