illumium.org

Главная › Блоги › Блог kayo

Организуем индексы на движке 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.

  • LMDB
  • Lua
  • OpenLDAP
  • Бортовой журнал Иллюмиума

Отправить комментарий

Содержимое этого поля является приватным и не будет отображаться публично.
  • Доступные HTML теги: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Syntax highlight code surrounded by the {syntaxhighlighter SPEC}...{/syntaxhighlighter} tags, where SPEC is a Syntaxhighlighter options string or "class="OPTIONS" title="the title".

Подробнее о форматировании

CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.
   ___    _  _             _      _   _   _ 
/ _ \ | || | _ _ | | __ | \ | | / |
| | | | | || |_ | | | | | |/ / | \| | | |
| |_| | |__ _| | |_| | | < | |\ | | |
\__\_\ |_| \__,_| |_|\_\ |_| \_| |_|
Введите код, изображенный в стиле ASCII-арт.
RSS-материал

Навигация

  • Подшивки
  • Фотоальбомы

«Иллюмиум» на якоре.

Работает на Drupal, система с открытым исходным кодом.

(L) 2010, Illumium.Org. All rights reversed ^_~