Developers Club geek daily blog

1 year, 3 months ago
image

Today two of my most favourite subjects — SQLite and key-value of the database. And this time I write about both at once: this post is devoted to a Python-wrapper for the storage used in SQLite 4 key-value on the basis of LSM.

I not too attentively trace SQLite releases, but version 3.8.11 drew my attention as in its description serious increase in performance in comparison with 3.8.0 is declared. In accompanying information I came across mentioning of new experimental expansion for full-text search (about which wrote once) and therefore it became interesting to me what develops a situation with SQLite 4.

Having studied available information, I paid attention that one of tasks of developers was to provide in new versions the interface for the connected engines of databases. At the time of writing of this post in SQLite 4 there were already two built-in backends, one of which — key-value storage on the basis of LSM. Few months I happened to be played the last with Cython while I wrote a Python-wrapper for the built-in k-v of UnQLite and Vedis storages. And I thought that it would be quite good to apply Cython to creation of the interface of the DB engine on the basis of LSM used in SQLite 4.

Having dealt with the source code SQLite 4 and the tiny heading LSM file, I wrote python-lsm-db (documentation).

What is the LSM tree?


As far as I understand the theory, LSM trees consist from:

  • the tree located in memory working as the buffer
  • and one or several trees stored (persistent) placed on a disk.

The letter M in an abbreviation of LSM means merge: operation on consolidation of buferizirovanny records with a tree (trees) on a disk. This procedure allows to reduce strongly seek cost on a disk that means one — fast record. On the other hand, any reading can be slower as the system will look for on several trees. And the LSM tree can be longer, than a B-tree, comparable with it. I believe that one more benefit of LSM trees is the smaller fragmentirovannost of the stored data that accelerates reading key ranges.

Once again I will emphasize: such is my understanding of the theory. I could be mistaken or miss in something important points.

Properties


Implementation of LSM in SQLite 4 possesses a number of very interesting properties:

  • Embedded DB used by your application.
  • Task of an order of viewing of keys by means of cursors.
  • Tranzaktsionnost (including nested transactions).
  • Transactional model of parallelization based on MVCC with support of the mode "one writes / read a little".
  • The base kept on a disk in the form of one file.
  • Stability of data at failures of the application or power supply.
  • Possibility of flexible setup under the needs.

Creation of Python-library


So, we will start. For a start we will create virtualenv and we will use pip for the Cython and lsm-db installation:

$ virtualenv test_lsm
$ cd test_lsm
$ source bin/activate
(test_lsm) $ pip install Cython lsm-db

For check of installation it is possible to execute a line:

(test_lsm) $ python -c "import lsm, tempfile; lsm.LSM(tempfile.mktemp())"

If everything is set and works correctly, then execution of this command will cause nothing. But keep in mind, I tested it only for Python 2.7 under Linux. So if you use Python 3.4 under Windows, then to you can be required to debug this code.

Small retreat


Further there will be an example of an interactive console session which reflects the main features and possibilities of lsm-db library. Documentation of API contains the complete list of classes, methods and descriptions of parameters and returned values.

For a start start the Python interpreter in a virtual environment and create a copy of object of LSM, having specified a way to the file of the database:

>>> from lsm import LSM
>>> db = LSM('test.ldb')

In the class LSM there are some more parameters, in addition to filename which you can configure: block size, page size etc.

Features of key-value


The SQLite 4 LSM engine is key/value-storage that makes it partly similar to object of dict in Python. Let's use 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'

Pay attention: when we tried to get access to just remote key, KeyError jumped out at once. By default, when we look for a key, the library at first looks for complete coincidence. In SQLite 4 LSM can also look for the closest key lexicographic if required us value does not exist. In addition to search in coincidence there are two more methods of search returning the following next key: SEEK_LE and SEEK_GE. If complete coincidence is not revealed, then SEEK_LE returns the most upper of keys (highest key) which value is less required, and SEEK_GE — the lowermost of keys (lowest key), whose value is more required. Let's say k1.5 does not exist:

>>> 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'

In addition to these, LSM supports also some other methods: keys (), values () and update ().

Slices and iterations


In SQLite 4 LSM it is possible to be iterated directly by data or to do selection on a subset of keys. The interesting moment is that at range query of keys its beginning and the end can not exist. If any key is absent, then the base will use one of seek-methods to find the following close key (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')]

For return of all keys in the set direction it is possible to use open (open-ended) slices:

>>> list(db['k0':])
[('k0', '0'), ('k1', '1'), ('k2', '2')]

>>> list(db[:'k1'])
[('foo', 'bar'), ('k0', '0'), ('k1', '1')]

If upper (upper bound) or the lower (lower bound) border outside key range, then returns the empty list.

>>> list(db[:'aaa'])
[]
>>> list(db['z':])
[]

For extraction of keys it is upside-down rather simple to specify an upper key as the first parameter of a slice. If you retrieve an open slice, then it is possible to specify True as its step-parameter.

>>> 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')]

If you are interested in more detailed information on work of seek-methods, address documentation of LSM.fetch_range ().

Cursors


Though in most cases it is quite enough slices, thinner control of process of search and viewing of records is sometimes necessary.

>>> 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')]

Using cursors, do not leave them open at all. At first you can use the manager of a context of LSM.cursor () who will help to close cursors.

Transactions


The SQLite 4 LSM base supports nested transactions. It is the simplest to use them together with the LSM.transaction method (), the speaker also as the manager of a context or the decorator.

>>> 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

You can partially zakommitit or roll away transactions by means of the isolated blocking (wrapped block), and new transaction will begin with the old place:

>>> 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.

If you want, you can cause explicitly LSM.begin (), LSM.commit () and LSM.rollback ().

>>> db.begin()
>>> db['foo'] = 'baze'
>>> print db['foo']
baze
>>> db.rollback()
True
>>> print db['foo']
bar

Performance


Though I also cannot suffer all these benchmarks, it was very interesting to me what performance at LSM base. Therefore I by means of a small benchmark compared SQLite 4 LSM to LevelDB, Berkeley DB and Kyoto Cabinet. In an amicable way, they could not be compared as Kyoto Cabinet and Berkeley DB are the built-in V-trees, and Kyoto Cabinet and LevelDB do not support multiple access processes to base. Also I am not sure whether there is a support of transactions in LevelDB. In addition, the benchmark uses libraries of bases not directly, and via the available Python driver. So some restrictions and features of pitonovsky libraries could affect result.

Results of a benchmark (the it is less, the better):

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

I interpret these data so: performance of Berkeley DB and Kyoto Cabinet at receipt of key ranges was quite expected, that is approximately such, as well as at any reading. And LevelDB and LSM, on the contrary, appeared much quicker when reading ranges and record at them is made quickly enough.

LevelDB exceeded SQLite 4 LSM, but the last reads out ranges far more bright, than V-trees. It will be necessary to prodebazhit LSM'a benchmark because reading at it appeared four times more slowly, than record! At first I thought that just there are some problems with reading, but then thought that it is all about a cursor Python-wrapper for each fetch (). After replacement of the Python code by couple of direct calls of API language About reading speed strongly grew. If you want to try LSM Python binding, then make sure that you use version 0.1.4 or above as in the previous versions very slow implementation of fetch ().

Notes about SQLite 4


If you want to collect SQLite 4, then you can clone an outdated repository and compile it.

$ 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

At the end you will have a binary sqlite4, libsqlite4.a and sqlite4.h file.

Also for simplification of process of embedding it is possible to create own copies of the source integrated file:

make sqlite4.c

Has to note also that the current status of SQLite 4 … is unknown. Doctor Hipp mentioned that he is going to continue support of SQLite 3. Difficultly for it to blame him. But on site I would experiment ultimate users with the fourth version. Perhaps, behind it the future, but not the fact. And even if and yes, that, perhaps, not in the current type.

Additional materials


If you need dirty details, then here the list of useful links:


Other my posts which can be pleasant to you:


If you are interested in other built-in NoSQL-bases, then pay attention to unqlite-python and vedis-python. They are very similar to MongoDB and Redis respectively, use wrappers, lightweight expansions on With and can be built in projects on Python.

This article is a translation of the original post at habrahabr.ru/post/274733/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus