LSM tree for Postgres - Mailing list pgsql-hackers

Hi hackers,

I want to share results of my last research of implementing LSM index in Postgres.
Most of modern databases (RocksDB, MongoDB, Tarantool,...) are using LSM tree instead of classical B-Tree.

From one side, capacity of RAM at modern servers allows to keep the whole database in memory.
It leads to the anti-caching approach proposed by Michael Stonebraker
https://15721.courses.cs.cmu.edu/spring2016/papers/hstore-anticaching.pdf

From the other side: maintaining if indexes is one of the most important factor limiting database performance.
Postgres is able to insert records in table without indexes almost with linear disk write speed(hundred megabytes per second).
But if table contains indexes, inserted keys have random values and indexes don't fill in memory then we observer dramatic degradation of performance. Average HDD access time is about 10msec, which corresponds to 100 random reads per second. If table has several indexes
and is large enough not to fit in memory, then insert speed can be as low as tens TPS. Certainly SSD can provide much better random access time,
but still random reads are slow.

LSM approach tries to address this problem.
First of all I started my experiments with RocksDB (may be most popular LSM-based key-value storage, used in many databases).
There was FDW for RocksDB from VidarDB project: https://github.com/vidardb/pgrocks
As far as RocksDB is multuthreaded embedded database engine and Postgres is based on multiprocess architecture,
them used interesting approach "server inside server": there is bgworker process which works with RocksDB and
backends sendind requests to it through shared memory queue.

I have significantly rewriten their FDW implementation: original RocksDB server implementation was single threaded.
I have made it multitheaded making it possible to run multiple RocksDB requests in parallel.
My implementation can be found there:
https://github.com/postgrespro/lsm

Some results of benchmarking.
Benchmark is just insertion of 250 millions of records with random key in inclusive index containing one bigint key and 8 bigint fields.
SIze of index is about 20Gb and target system has 16GB of RAM:

Index	Clients	TPS
Inclusive B-Tree	1	9387
Inclusive B-Tree	10	18761
RocksDB FDW	1	138350
RocksDB FDW	10	122369
RocksDB	1	166333
RocksDB	10	141482

As you can see there is about 10 times difference.
May be somebody will find useful this idea of using IOT (index organized table) based on RocksDB  in Postgres.
But this approach violates all ACID properties of Postgres:
there is no atomicity and consistency (in principle RocksDB supports 2PC, but it is not used here),
isolation corresponds to something like "read uncommitted",
and  concerning durability - it is all up to RocksDB and I have serious doubts that it will survive failure especially with sync write mode disabled.
So I considered this project mostly as prototype for estimating efficiency of LSM approach.

Then I think about implementing ideas of LSM using standard Postgres nbtree.

We need two indexes: one small for fast inserts and another - big (main) index. This top index is small enough to fit in memory
so inserts in this index are very fast.
Periodically we will merge data from top index to base index and truncate the top index. To prevent blocking of inserts in the table
while we are merging indexes we can add ... on more index, which will be used during merge.

So final architecture of Lsm3 is the following:
two top indexes used in cyclic way and one main index. When top index reaches some threshold value
we initiate merge with main index, done by bgworker and switch to another top index.
As far as merging indexes is done in background, it doesn't  affect insert speed.
Unfortunately Postgres Index AM has not bulk insert operation, so we have to perform normal inserts.
But inserted data is already sorted by key which should improve access locality and partly solve random reads problem for base index.

Certainly to perform search in Lsm3 we have to make lookups in all three indexes and merge search results.
(in case of unique index we can avoid extra searches if searched value is found in top index).
It can happen that during merge of top and base indexes the same TID can be found in both of them.
But such duplicates can be easily eliminated during merge of search results.

As far as we are using standard nbtree indexes there is no need to worry about logging information in WAL.
There is no need to use inefficient "generic WAL records" or patch kernel by adding own WAL records.

Implementation of Lsm3 Index AM as standart Postgres extension  is available here:
https://github.com/postgrespro/lsm3

I have performed the same benchmark with random inserts (described above) for Lsm3:

Index	Clients	TPS
Inclusive B-Tree	1	9387
Inclusive B-Tree	10	18761
RocksDB FDW	1	138350
RocksDB FDW	10	122369
RocksDB	1	166333
RocksDB	10	141482
Lsm3	1	151699
Lsm3	10	65997

Size of nbtree is about 29Gb, single client performance is even higher than of RocksDB FDW, but parallel results are signficantly worser.
So Lsm3 can provide significant improve of performance for large indexes not fitting in main memory.
And the larger ratio between index size and RAM size is, the larger benefit in insertion speed you get.
Lsm3 is just standard postgres extension, fully integrated in Postgres infrastructure (MVCC, WAL, backups,...).
SO I hope it can be useful when standard indexes becomes bottleneck.


I will be glad to receive any feedback, may be some change requests or proposals.

Best regards,
Konstantin