To date, two of my favorite topics are SQLite and database key-value. And this time I’m writing about both at once: this post is dedicated to Python wrapper for LSM- based storage used in SQLite 4 key-value.

I didn’t closely monitor the releases of SQLite, but version 3.8.11 caught my attention, because its description stated a serious performance increase compared to 3.8.0. In the accompanying information, I came across the mention of a new experimental expansion for full-text search ( which I once wrote about ), and therefore I wondered what the situation with SQLite 4 was .
')
Having studied the available information, I noticed that one of the tasks of the developers was to provide an interface for the connected database engines in new versions. At the time of writing this post in SQLite 4, there were already two built-in backends, one of which is a key-value LSM-based repository. In the past couple of months, I have been playing around with Cython while I was writing Python wrapper for embedded kv UnQLite and Vedis repositories . And I thought it would be nice to use Cython to create an interface to the database engine based on LSM used in SQLite 4.

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

What is LSM-tree?

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

• memory tree, working as a buffer,
• and one or more persistent trees located on the disk.

The letter M in the abbreviation LSM means merge: an operation to merge the buffered records with the tree (s) on the disk. This procedure allows you to greatly reduce the cost of seek by disk, which means one thing - fast writing. On the other hand, random reads may turn out to be slower, since the system will search through several trees. An LSM tree may be longer than a B-tree comparable to it. I suppose that another advantage of LSM trees is less fragmentation of the stored data, which speeds up the reading of key ranges.

Once again, this is my understanding of the theory. I could be mistaken or miss important points.

Properties

The implementation of LSM in SQLite 4 has a number of very interesting properties:

• Embedded database used by your application.
• Setting the order of viewing keys using cursors.
• Transactional (including nested transactions).
• Transactional parallelization model based on MVCC with support for the “one writes / several read” mode.
• Database stored on disk as a single file.
• Data stability in case of application or power failures.
• The possibility of flexible settings to fit your needs.

Creating a Python Library

So let's get started. First, let's create virtualenv and use pip to install Cython and lsm-db:

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

To verify the installation, you can run the line:

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

If everything is installed and working correctly, then the execution of this command will not entail anything. But keep in mind, I tested it only in Python 2.7 under Linux. So if you are using Python 3.4 under Windows, you may need to debug this code.

Small retreat

Next will be an example of an interactive console session that reflects the main features and capabilities of the lsm-db library. The API documentation contains a complete list of classes, methods and descriptions of parameters and return values.

First, start the Python interpreter in a virtual environment and create an instance of the LSM object, specifying the path to the database file:

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

In the LSM class, there are a number of parameters besides the filename that you can customize: block size, page size, etc.

Key-value features

The SQLMate 4 LSM engine is a key / value store, which makes it somewhat similar to the dict object in Python. We use the 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' 

Note: when we tried to access the just-deleted key, KeyError immediately popped up. By default, when we search for a key, the library first looks for a full match. In SQLite 4, LSM can also search for the closest key lexicographically if the value we are looking for does not exist. In addition to matching the search, there are two more search methods that return the next closest key: SEEK_LE and SEEK_GE. If no full match is found, then SEEK_LE returns the uppermost key (the highest key), the value of which is less than the desired one, and SEEK_GE - the lowermost key (the lowest key), whose value is greater than the desired one. Suppose 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 a number of other methods: keys (), values ​​() and update ().

Slices and iterations

In SQLite 4 LSM, you can iterate directly on the data or make a selection on a subset of keys. An interesting point is that when requesting a range of keys, its beginning and end may not exist. If there is no key, then the base will use one of the seek methods to find the next 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')] 

To return all keys in a given direction, you can use open (ended) slices:

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

If the upper (upper bound) or lower (lower bound) border is outside the range of keys, then an empty list is returned.

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

To retrieve the keys in the reverse order, it is enough just to specify the top key as the first slice parameter. If you retrieve an open slice, then you can set 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 about how the seek methods work, consult the LSM.fetch_range () documentation.

Cursors

Although in most cases there are enough slices, sometimes a more subtle control over the process of searching and viewing records is needed.

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

Do not leave them open when using cursors. At first, you can use the context manager LSM.cursor (), which will help close the cursors.

Transactions

LSM-base SQLite 4 supports nested transactions. The easiest way to use them is with the LSM.transaction () method, which also acts as a context manager or 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 commit or roll back transactions using wrapped block, and the new transaction will start from 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 explicitly call LSM.begin (), LSM.commit () and LSM.rollback ().

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

Performance

Although I can not tolerate all these benchmarks, I was very interested in what the performance of the LSM-base. Therefore, I compared SQLite 4 LSM with LevelDB, Berkeley DB and Kyoto Cabinet using a small benchmark . In a good way, they could not be compared, since Kyoto Cabinet and Berkeley DB are built-in B-trees, and Kyoto Cabinet and LevelDB do not support multiple process access to the database. Also, I'm not sure if there is transaction support in LevelDB. Among other things, the benchmark uses the database libraries not directly, but through the available Python driver. So some limitations and features of the Python libraries could affect the result.

Benchmark results (the smaller 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 this data as follows: the performance of Berkeley DB and Kyoto Cabinet when getting key ranges turned out to be quite expected, that is, about the same as with random reading. And LevelDB and LSM, on the contrary, turned out to be much faster when reading ranges, and they write quite quickly.

LevelDB exceeded SQLite 4 LSM, but the latter reads ranges much faster than B-trees. It will be necessary to punch out the LSM benchmark, because reading it turned out to be four times slower than writing! At first, I thought that there were just some problems with reading, but then I realized that the whole thing was in Python-wrapper for each fetch (). After replacing the Python code with a couple of direct C language API calls, the reading speed has increased dramatically. If you want to try LSM Python bindings, then make sure that you are using version 0.1.4 or higher, because in previous versions the fetch () implementation is very slow.

SQLite 4 Notes

If you want to build SQLite 4 yourself, 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 

Upon completion, you will have a binary file sqlite4, libsqlite4.a and sqlite4.h.

You can also create your own copies of the original merged file to simplify the embedding process:

 make sqlite4.c 

I should also note that the current status of SQLite 4 ... is unknown. Dr. Hipp mentioned that he plans to continue supporting SQLite 3. It’s hard to blame him. But in place of end users, I would experiment with the fourth version. Perhaps her future, but not a fact. And even if it does, it may not be in its current form.

Additional materials

If you need dirty details, here is a list of useful links:

• Python LSM-db documentation
• Introduction to SQLite4 LSM
• LSM C-API Description
• Quora: “How does the LSM tree work?”
• My benchmark script

My other posts that you might like:

• 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

If you are interested in other embedded NoSQL databases, then pay attention to unqlite-python and vedis-python . They are very similar to MongoDB and Redis, respectively, use wrappers, lightweight C extensions, and can be embedded in Python projects.