History[08][07]

LMDB was developed and maintained by the Symas Corporation to replace Berkeley DB in the OpenLDAP project.

Checkpoints

In the event of a crash, the database starts of from where it was left, the OS takes care of writing data to disk and the database here doesn't need to take any snapshots. The on-disk representation is similar to the in-memory representation, there is no provision for compressing the data, due the memory map constraints.

Concurrency Control[03]

Locking overhead avoided by using MVCC, readers don't block at all and writers don't block readers. Deleted versions are reclaimed by the free space management module of LMDB (essentially stored into a B+ tree for later use).

Data Model

This embedded database is a key-value in the backend, which is stored in the memory-map. The keys are indexed in a B+ tree. LMDB provides transactional guarantees on top of this key-value store. It is not a relational database.

Indexes[09][03]

LMDB uses a modified design of B+ Tree with an append-only enhancement, and it uses 2 B+ trees : one for maintaining the regular user data pages and one for maintaining the free pages obtained after deletes. LMDB is optimized for read transactions. Due to use of Copy-on-Write, readers never block writers, therefore read transactions, by using older pages, may live indefinitely without affecting write performance.

Isolation Levels[03]

LMDB provides Serializable isolation with MVCC, this is possible because of the single-writer semantics. Only a single write transaction can can be alive at a single point of time, hence no races among multiple writers modifying the database.

Joins

Logging[10][11][12]

No logging procedures are implemented here, using copy-on-write semantics (with shadow paging) provides durability without any need for logging. Shadow paging allows new writes to a different location and not directly replace the existing pages, hence avoids data-corruption: the root page changing to the new data is only updated after the new tree is saved. Also the shadow root page reference update is atomic. Combined, this entirely avoids the need for logging. As a result, data loss on a power loss event is only up to the point where the last root page was saved, as long as fsync (or fdatasync on GNU/Linux OSes) is used. Reliability of the underlying storage hardware (SSD, HDD, NAS) is out of scope of LMDB's design.

Parallel Execution[13][14][15][16]

LMDB employs "Multi-version Concurrency Control". Multiple threads in multiple processes are permitted, whilst at the same time limiting write transactions to only one (via a mutex). There is however no limit on the number of readers, which scale linearly (resources permitting), including when a write transaction is in progress, and are "wait-free".

Query Compilation

Query Execution

There is no query planning or query execution options as this is an embedded database, since we operate at individual key level, the closest we can classify it is under tuple-at-a-time. The user can program custom querying models on top this embeddded database, which can support other query execution options.

Query Interface[17]

LMDB has no SQL layer but applications can directly access the database using API calls provided by LMDB. API support is not just in C but many wrappers for other languages have been developed by open-source contributors. All key-value store operations can be performed using these API calls.

Storage Architecture

LMDB uses mmap (shmem with copy-on-write enabled), hence it reliquishes most of the caching control to the OS. Memory map allows zero-copies for read/write and no additional buffers for the transaction control. Supports larger-than memory databases, it is bounded by the size of the virtual memory since they use a memory map.

Storage Model

They use a memory-map to store the database with copy-on-write semantics, hence no specific storage model but the semantics are left to the operating system. The on-disk representation is similar to the memory representation of the database.

Stored Procedures

System Architecture

LMDB uses the shared-everything model. It handles the memory as a single address space and all the threads access this in parallel. It uses copy-on-write semantics.

Views