На сегодняшний день две мои самые любимые темы — SQLite и key-value базы данных. И в этот раз я пишу сразу про обе: этот пост посвящён Python-обёртке для используемого в SQLite 4 key-value хранилища на основе LSM.
Я не слишком внимательно отслеживаю релизы SQLite, но версия 3.8.11 привлекла моё внимание, поскольку в её описании заявлено серьёзное увеличение производительности по сравнению с 3.8.0. В сопроводительной информации я наткнулся на упоминание о новом экспериментальном расширении для полнотекстового поиска (о котором писал когда-то), и потому мне стало интересно, какая складывается ситуация с SQLite 4.
Изучив доступную информацию, я обратил внимание, что одной из задач разработчиков было обеспечить в новых версиях интерфейс для подключаемых движков баз данных. На момент написания этого поста в SQLite 4 уже было два встроенных бэкенда, один из которых — key-value хранилище на основе LSM. В последние пару месяцев мне доводилось поиграться с Cython, пока я писал Python-обёртку для встроенных k-v хранилищ UnQLite и Vedis. И я подумал, что было бы неплохо применить Cython для создания интерфейса движка БД на основе LSM, используемого в SQLite 4.
Разобравшись с исходным кодом SQLite 4 и крохотным заголовочным файлом LSM, я написал python-lsm-db (документация).
Что такое LSM-дерево?
Насколько я понимаю теорию, LSM-деревья состоят из:
- расположенного в памяти дерева, работающего в качестве буфера,
- и одного или нескольких хранимых (persistent) деревьев, размещённых на диске.
Буква М в аббревиатуре LSM означает merge: операцию по объединению буферизированных записей с деревом (деревьями) на диске. Эта процедура позволяет сильно уменьшить стоимость seek по диску, что означает одно — быструю запись. С другой стороны, произвольное чтение может оказаться более медленным, поскольку система будет искать по нескольким деревьям. А LSM-дерево может быть длиннее, чем сравнимое с ним B-дерево. Полагаю, что ещё одним преимуществом LSM-деревьев является меньшая фрагментированность хранимых данных, что ускоряет чтение диапазонов ключей.
Ещё раз подчеркну: таково моё понимание теории. Я мог в чём-то ошибиться или упустить важные моменты.
Свойства
Реализация LSM в SQLite 4 обладает рядом очень интересных свойств:
- Embedded БД, используемая вашим приложением.
- Задание порядка просмотра ключей с помощью курсоров.
- Транзакционность (включая вложенные транзакции).
- Транзакционная модель распараллеливания на базе MVCC с поддержкой режима «один пишет / несколько читают».
- Хранимая на диске база в виде одного файла.
- Устойчивость данных при сбоях приложения или питания.
- Возможность гибкой настройки под свои нужды.
Создание Python-библиотеки
Итак, приступим. Для начала создадим virtualenv и воспользуемся pip для установки Cython и lsm-db:
$ virtualenv test_lsm
$ cd test_lsm
$ source bin/activate
(test_lsm) $ pip install Cython lsm-db
Для проверки установки можно выполнить строку:
(test_lsm) $ python -c "import lsm, tempfile; lsm.LSM(tempfile.mktemp())"
Если всё установлено и работает корректно, то выполнение этой команды ничего за собой не повлечёт. Но имейте в виду, я тестировал её только на Python 2.7 под Linux. Так что если вы пользуетесь Python 3.4 под Windows, то вам может потребоваться отладить этот код.
Небольшое отступление
Далее будет пример интерактивного консольного сеанса, который отражает основные особенности и возможности библиотеки lsm-db. В документации API содержится полный список классов, методов и описаний параметров и возвращаемых значений.
Для начала запустите в виртуальном окружении интерпретатор Python и создайте экземпляр объекта LSM, указав путь к файлу базы данных:
>>> from lsm import LSM
>>> db = LSM('test.ldb')
В классе LSM есть ещё ряд параметров, помимо filename, которые вы можете настроить: размер блока, размер страницы и т. д.
Особенности key-value
LSM-движок SQLite 4 является key/value-хранилищем, что делает его отчасти похожим на объект dict в Python. Воспользуемся dict-like API.
>>> db['foo'] = 'bar'
>>> print db['foo']
bar
>>> for i in range(4):
... db['k%s' % i] = str(i)
...
>>> 'k3' in db
True
>>> 'k4' in db
False
>>> del db['k3']
>>> db['k3']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "lsm.pyx", line 973, in lsm.LSM.__getitem__ (lsm.c:7142)
File "lsm.pyx", line 777, in lsm.LSM.fetch (lsm.c:5756)
File "lsm.pyx", line 778, in lsm.LSM.fetch (lsm.c:5679)
File "lsm.pyx", line 1289, in lsm.Cursor.seek (lsm.c:12122)
File "lsm.pyx", line 1311, in lsm.Cursor.seek (lsm.c:12008)
KeyError: 'k3'
Обратите внимание: когда мы попытались получить доступ к только что удалённому ключу, сразу выскочила KeyError. По умолчанию, когда мы ищем ключ, библиотека сначала ищет полное совпадение. В SQLite 4 LSM может также искать наиболее близкий ключ лексикографически, если искомое нами значение не существует. В дополнение к поиску по совпадению есть ещё два метода поиска, возвращающих следующий ближайший ключ: SEEK_LE и SEEK_GE. Если полное совпадение не обнаружено, то SEEK_LE возвращает самый верхний из ключей (highest key), значение которого меньше искомого, а SEEK_GE — самый нижний из ключей (lowest key), чьё значение больше искомого. Допустим, k1.5 не существует:
>>> from lsm import SEEK_LE, SEEK_GE
>>> # Здесь будет выбран "k1", самый верхний из всех, что меньше k1.5
>>> db['k1.5', SEEK_LE]
'1'
>>> # Здесь будет выбран "k2", самый нижний из всех, что больше k1.5
>>> db['k1.5', SEEK_GE]
'2'
Помимо этих, LSM поддерживает и ряд других методов: keys(), values() и update().
Слайсы и итерации
В SQLite 4 LSM можно итерироваться напрямую по данным либо делать выборку по подмножеству ключей. Интересный момент заключается в том, что при запросе диапазона ключей его начало и конец могут не существовать. Если какой-то ключ отсутствует, то база воспользуется одним из seek-методов чтобы найти следующий близкий ключ (next-closest key):
>>> [item for item in db]
[('foo', 'bar'), ('k0', '0'), ('k1', '1'), ('k2', '2')]
>>> db['k0':'k99']
<generator object at 0x7f2ae93072f8>
>>> list(db['k0':'k99'])
[('k0', '0'), ('k1', '1'), ('k2', '2')]
Для возврата всех ключей в заданном направлении можно воспользоваться открытыми (open-ended) слайсами:
>>> list(db['k0':])
[('k0', '0'), ('k1', '1'), ('k2', '2')]
>>> list(db[:'k1'])
[('foo', 'bar'), ('k0', '0'), ('k1', '1')]
Если верхняя(upper bound) или нижняя(lower bound) граница за пределами диапазона ключей, то возвращается пустой список.
>>> list(db[:'aaa'])
[]
>>> list(db['z':])
[]
Для извлечения ключей в обратном порядке достаточно просто указать в качестве первого параметра слайса верхний ключ. Если вы извлекаете открытый слайс, то в качестве его step-параметра можно указать True.
>>> list(db['k1':'aaa']) # Поскольку 'k1' > 'aaa', то ключи извлекаются в обратном порядке:
[('k1', '1'), ('k0', '0'), ('foo', 'bar')]
>>> list(db['k1'::True]) # В открытых слайсах True указывается в качестве step:
[('k1', '1'), ('k0', '0'), ('foo', 'bar')]
При необходимости вы можете <b>удалять</b> слайсы, но сами ключи при этом не будут затронуты:
>>> del db['k0':'k99']
>>> list(db) # 'k0' всё ещё существует.
[('foo', 'bar'), ('k0', '0')]
Если вас интересует более подробная информация о работе seek-методов, обратитесь к документации LSM.fetch_range().
Курсоры
Хотя в большинстве случаев слайсов вполне достаточно, иногда нужен более тонкий контроль процесса поиска и просмотра записей.
>>> with db.cursor() as cursor:
... for key, value in cursor:
... print key, '=>', value
...
foo => bar
k0 => 0
>>> db.update({'k1': '1', 'k2': '2', 'k3': '3'})
>>> with db.cursor() as cursor:
... cursor.first()
... print cursor.key()
... cursor.last()
... print cursor.key()
... cursor.previous()
... print cursor.key()
...
foo
k3
k2
>>> with db.cursor() as cursor:
... cursor.seek('k0', SEEK_GE)
... print list(cursor.fetch_until('k99'))
...
[('k0', '0'), ('k1', '1'), ('k2', '2'), ('k3', '3')]
Применяя курсоры, ни в коем случае не оставляйте их открытыми. На первых порах можете воспользоваться менеджером контекста LSM.cursor(), который поможет закрывать курсоры.
Транзакции
LSM-база SQLite 4 поддерживает вложенные транзакции. Проще всего их использовать вместе с методом LSM.transaction(), выступающим также в роли менеджера контекста или декоратора.
>>> with db.transaction() as txn:
... db['k1'] = '1-mod'
... with db.transaction() as txn2:
... db['k2'] = '2-mod'
... txn2.rollback()
...
True
>>> print db['k1'], db['k2']
1-mod 2
Вы можете частично закоммитить или откатить транзакции с помощью изолированной блокировки (wrapped block), и новая транзакция начнётся со старого места:
>>> with db.transaction() as txn:
... db['k1'] = 'outer txn'
... txn.commit() # Запись закоммичена.
...
... db['k1'] = 'outer txn-2'
... with db.transaction() as txn2:
... db['k1'] = 'inner-txn' # Закоммичено после снятия блокировки.
... print db['k1'] # Печатает "inner-txn".
... txn.rollback() # Откатывает из txn2 оба изменения и предыдущую запись.
... print db['k1']
...
1 <- Return value from call to commit().
inner-txn <- Printed after end of txn2.
True <- Return value of call to rollback().
outer txn <- Printed after rollback.
Если хотите, можете явным образом вызвать LSM.begin(), LSM.commit()и LSM.rollback().
>>> db.begin()
>>> db['foo'] = 'baze'
>>> print db['foo']
baze
>>> db.rollback()
True
>>> print db['foo']
bar
Производительность
Хоть я и не могу терпеть все эти бенчмарки, мне было очень интересно, какова производительность у LSM-базы. Поэтому я с помощью небольшого бенчмарка сравнил SQLite 4 LSM с LevelDB, Berkeley DB и Kyoto Cabinet. По-хорошему, их нельзя было сравнивать, поскольку Kyoto Cabinet и Berkeley DB являются встроенными В-деревьями, а Kyoto Cabinet и LevelDB не поддерживают множественный доступ процессов к базе. Также я не уверен, есть ли поддержка транзакций в LevelDB. Помимо прочего, бенчмарк использует библиотеки баз не напрямую, а через доступный драйвер Python. Так что на результат могли повлиять какие-то ограничения и особенности питоновских библиотек.
Результаты бенчмарка (чем меньше, тем лучше):
Testing with N = 100000
------------------------------------
BDBBTree
~~~~~~~~
Writes: 0.469
Reads: 0.479
Range (10%): 0.212
Range (20%): 0.192
Range (40%): 0.185
Range (80%): 0.186
KyotoBTree
~~~~~~~~~~
Writes: 0.208
Reads: 0.203
Range (10%): 0.219
Range (20%): 0.188
Range (40%): 0.188
Range (80%): 0.187
LevelDB
~~~~~~~
Writes: 0.227
Reads: 0.225
Range (10%): 0.031
Range (20%): 0.027
Range (40%): 0.028
Range (80%): 0.027
LSM
~~~
Writes: 0.282
Reads: 0.239
Range (10%): 0.059
Range (20%): 0.052
Range (40%): 0.052
Range (80%): 0.052
Я интерпретирую эти данные так: производительность Berkeley DB и Kyoto Cabinet при получении диапазонов ключей оказалась вполне ожидаемой, то есть примерно такой, как и при произвольном чтении. А LevelDB и LSM, напротив, оказались гораздо быстрее при чтении диапазонов, да и запись у них производится довольно быстро.
LevelDB превзошёл SQLite 4 LSM, но последний считывает диапазоны куда шустрее, чем В-деревья. Надо будет продебажить бенчмарк LSM’а, потому что чтение у него оказалось в четыре раза медленнее, чем запись! Сначала я подумал, что просто есть какие-то проблемы с чтением, но потом сообразил, что всё дело в Python-обёртке курсора для каждого fetch(). После замены кода Python на пару прямых вызовов API языка С скорость чтения сильно выросла. Если захотите попробовать биндинги LSM Python, то удостоверьтесь, что вы пользуетесь версией 0.1.4 или выше, поскольку в предыдущих версиях очень медленная реализация fetch().
Заметки об SQLite 4
Если хотите сами собрать SQLite 4, то можете клонировать устаревший репозиторий и скомпилировать его.
$ fossil clone http://www.sqlite.org/src4/ sqlite4.fossil
$ mkdir sqlite4-build
$ cd sqlite4-build
$ fossil open ../sqlite4.fossil
$ ln -s Makefile.linux-gcc Makefile
$ export CFLAGS="$CFLAGS -DSQLITE_ENABLE_FTS3=1 -DSQLITE_ENABLE_COLUMN_METADATA=1 -DSQLITE_ENABLE_UNLOCK_NOTIFY -DSQLITE_SECURE_DELETE
$ make
По завершении у вас будет бинарный файл sqlite4, libsqlite4.a и sqlite4.h.
Также для упрощения процесса встраивания можно создать собственные копии исходного объединённого файла:
make sqlite4.c
Должен также отметить, что текущий статус SQLite 4… неизвестен. Доктор Хипп обмолвился, что он планирует продолжать поддержку SQLite 3. Трудно его за это винить. Но на месте конечных пользователей я бы поэкспериментировал с четвёртой версией. Возможно, за ней будущее, но не факт. А даже если и да, то, возможно, не в текущем виде.
Дополнительные материалы
Если вам нужны грязные подробности, то вот список полезных ссылок:
- Документация Python LSM-db
- Введение в SQLite4 LSM
- Описание LSM C-API
- Quora: «Как работает дерево LSM?»
- Мой бенчмарк-скрипт
Другие мои посты, которые могут вам понравиться:
- Using the SQLite JSON1 and FTS5 extensions with Python
- Using SQLite full-text search with Python
- Introduction to the fast, new UnQLite bindings
- My list of Python and SQLite resources
Если вас интересуют другие встраиваемые NoSQL-базы, то обратите внимание на unqlite-python и vedis-python. Они очень похожи на MongoDB и Redis соответственно, используют обёртки, легковесные расширения на С и могут встраиваться в проекты на Python.
Автор: Mail.Ru Group
