LSM Key/Value Storage in SQLite3
Several months ago I was delighted to see significant progress on a relatively new extension in the SQLite source tree. The lsm1 extension is based on the LSM key/value database developed as an experimental storage engine for the now-defunct SQLite4 project. Since development has stopped on SQLite4 for the forseeable future, I was happy to see this technology being folded into SQLite3 and was curious to see what the SQLite developers had in mind for this library.
The SQLite4 LSM captured my interest several years ago as it seemed like a viable alternative to some of the other embedded key/value databases floating around (LevelDB, BerkeleyDB, etc), and I went so far as to write a set of Python bindings for the library. As a storage engine, it seems to offer stable performance, with fast reads of key ranges and fast-ish writes, though random reads may be slower than the usual SQLite3 btree. Like SQLite3, the LSM database supports a single-writer/multiple-reader transactional concurrency model, as well as nested transaction support.
The LSM implementation in SQLite3 is essentially the same as that in SQLite4, plus some additional bugfixes and performance improvements. Crucially, the SQLite3 implementation comes with a standalone extension that exposes the storage engine as a virtual table. The rest of this post will deal with the virtual table, its implementation, and how to use it.
Just a heads-up: since this extension has not been officially announced or documented, I believe the developers may not consider it finished. The APIs and functionality described here may change with future releases of SQLite.
SQLite provides an API that allows one to programmatically define a complete
table, which can then be queried just like any ordinary database table. For
example, it's possible that you could expose a Redis database as a virtual
table and then operate on your Redis database completely from SQLite. More
commonly, perhaps you want to work with some CSV data but do not want to write
a script to parse it and load it into a database -- thanks to the CSV virtual
table extension, querying a CSV table can be as simple as running a
CREATE VIRTUAL TABLE query and then working directly with the auto-generated
To put it simply, a virtual table implements several methods, and ultimately returns rows of tabular data. The SQLite virtual machine then executes your queries against the data returned by your application. Hints are provided by SQLite so you can avoid returning the full data-set when only a small portion is needed, allowing for efficient implementations. SQLite may even propose several query plans, and based on the cost your application returns, will choose the most efficient.
LSM Virtual Table
The source code for
the LSM1 virtual table is concise, readable, and well-commented so I definitely
recommend checking it out. In a nutshell, the virtual table exposes a single
key/value database as a regular table. The keys are sorted lexicographically
and must be either
unsigned int (all keys in a given
database are required to be the same data-type). The value is a collection of
one or more ordinary SQLite columns, which the virtual table packs and encodes
into the value field associated with the given key.
Given this organization, queries on values are not going to be efficient, since there are no secondary indexes. But querying ranges of keys is going to be very fast! This makes the LSM a good fit for any ordered data-set where lookups will commonly be linear ranges -- things like time-series, event logs, analytics, etc. The LSM virtual table's cost estimator is smart enough that it can recognize when key ranges are being requested, and will return only as much data is needed.
Data is written to the LSM using the standard
INSERT or the SQLite-specific
INSERT OR REPLACE. Until recently,
DELETE were not supported,
but testing the latest version (and reading the code) it appears that both are
now working as expected! Due to the lack of secondary indexes, it probably is only wise to use
UPDATE queries restricted by individual keys or ranges of consecutive keys.
Compiling the Extension
At the time of writing, the SQLite build scripts do not include any macros for automatically compiling the LSM1 extension. I'll update this post if that changes, but in the meantime, it's pretty straightforward.
First you'll want to get a copy of the latest source code. You can grab the
source tarball or use
fossil to clone the repository:
fossil clone https://www.sqlite.org/src sqlite.fossil mkdir sqlite cd sqlite fossil open ../sqlite.fossil
To compile the extension, change directories into the
and run the following:
cd ext/lsm1 export CFLAGS="-fPIC -O2" TCCX="gcc -g -fPIC -O2" make lsm.so
You should now have a file named
lsm.so, which can be loaded at run-time as a
SQLite extension. To test that the extension is loadable, try running the
sqlite3 # start up the sqlite3 shell sqlite> .load ./lsm
Assuming no error is reported, you should be all set.
Working with LSM1
Let's kick the tires on the LSM virtual table. I'll assume you've got a SQLite shell opened and have loaded up the LSM extension.
-- create a simple table keyed by "name" (type TEXT) with address & phone -- as the associated value. CREATE VIRTUAL TABLE contacts USING lsm1 ('contacts.lsm', name, TEXT, address, phone); -- store 4 key/value pairs in the LSM database. INSERT INTO contacts (name, address, phone) VALUES ('charlie', '3000 Main St, Topeka KS', '785-555-1234'), ('huey', '1300 Walnut St, Topeka KS', '785-555-9999'), ('zaizee', '900 Maple Dr, Topeka KS', '913-555-1800'), ('mickey', '123 Chestnut Dr, Lawrence KS', '785-555-1000'); -- retrieve data back out of the LSM store. SELECT * FROM contacts; -- returns the following data (note that it is automatically sorted by key): charlie|3000 Main St, Topeka KS|785-555-1234 huey|1300 Walnut St, Topeka KS|785-555-9999 mickey|123 Chestnut Dr, Lawrence KS|785-555-1000 zaizee|900 Maple Dr, Topeka KS|913-555-1800 -- update the phone number for "mickey". Note that we have to include *all* -- column values when using "REPLACE". REPLACE INTO contacts (name, address, phone) VALUES ('mickey', '123 Chestnut Dr, Lawrence KS', '785-555-5000'); -- check the row was updated. SELECT phone FROM contacts WHERE name = 'mickey'; -- returns the following data: 785-555-5000 -- we can also use the UPDATE statement. UPDATE contacts SET phone = '785-555-8888' WHERE name = 'huey'; -- verify. SELECT phone FROM contacts WHERE name = 'huey'; 785-555-8888 -- delete "zaizee". DELETE FROM contacts WHERE name = 'zaizee'; -- verify row deleted. SELECT COUNT(*) FROM contacts; 3
Since the LSM database is stored in it's own file (
contacts.lsm per our
virtual table declaration), we can use LSM-specific tools to interact with the
database. python-lsm-db is one such tool.
Let's use it to introspect the database. We can see how SQLite is storing our
data, which is kind of neat:
>>> from lsm import LSM >>> db = LSM('./contacts.lsm') >>> list(db.keys()) ['charlie', 'huey', 'mickey'] >>> db['huey'] '\x991300 Walnut St, Topeka KSK785-555-8888' >>> db['mickey'] '\xab123 Chestnut Dr, Lawrence KSK785-555-5000'
Digging into the data, we can see the value is structured as a prefix plus
address data, plus another prefix and the phone number. The field length,
because the values we're dealing with are small, can be found by dividing the
6 (because the value modulo 6 is the data-type, which for our text
fields comes out to
3). So for
153 in decimal), we end up with
which happens to be the length of huey's address. For
75 in decimal) we
11, which is the length of huey's phone number (including the two hyphens).
171) we get
28, which is the length of mickey's address. Pretty
neat. If we were storing integers things are a bit more complicated, but
hopefully this gives an impression of what SQLite is doing under-the-hood.
- LSM1 code
- Sqlite4 LSM storage engine docs
- Python LSM database bindings and related blog post
- Experimental Peewee 3.0a support for LSM extension