Chapter 4: Storage Fundamentals

Datalevin's query model is fact-centric, but its performance and reliability are grounded in its storage architecture. Unlike many databases that build custom buffer managers and page caches, Datalevin leverages the operating system's existing strengths by building on LMDB (Lightning Memory-Mapped Database). Implementation-wise, this storage foundation is a native layer exposed upward through the JVM; Datalevin's Clojure database layer builds schema, Datalog, and indexing semantics on top while leveraging LMDB's transaction machinery.

This chapter explores why Datalevin chose this foundation, how it extends LMDB into DLMDB, and how the physical layout of data supports efficient Datalog queries, secondary indexes, and high-throughput writes.

1. The Foundation: Why LMDB?

LMDB is a small embedded key-value store with a deliberately narrow design. Its philosophy is to do as little as possible in user space, offloading memory management to the operating system (OS) kernel. LMDB does not know Datalevin attributes, datoms, or schema. It stores and orders raw bytes. Datalevin encodes typed values into those bytes and decodes them back into typed values.

1.1 Why Memory-Mapping Fits Datalevin

LMDB uses memory-mapping (mmap). It treats the database file as if it were a large array in the process's virtual address space. This does not mean the whole database file is loaded into memory. When Datalevin reads data, the OS kernel handles fetching the required pages from disk into the file-system page cache. This is the operating system's cache of file-backed pages in main memory, not the CPU's L1/L2/L3 hardware caches. A page is a fixed-size block of virtual memory that the OS maps, caches, and evicts as a unit.¹ The memory map reserves a range of virtual address space; physical memory is used for pages that are actually touched, and clean pages can be evicted by the kernel when memory is needed elsewhere. LMDB deliberately made this architectural choice, because the OS already manages file-backed pages across all processes on the machine, and it can evict, prefetch, and share those pages with knowledge of the whole system's workload.

Traditional databases often manage their own "buffer pool," a chunk of memory where they keep data pages. That design makes sense when the database is the main program on the machine and wants tight control over every page of memory. But many modern databases do not own the whole computer. They run in cloud VMs and containers beside other services, on desktops beside user applications, or embedded inside application servers. In those environments, the OS has a broader view of memory pressure than any one database process can have.

A database-owned buffer pool sees only the database's allocation. It may keep a page in its own cache while the OS also keeps the same page in the file-system cache, causing "double buffering." It also competes with the rest of the machine through a fixed memory budget chosen ahead of time. With mmap, Datalevin lets the OS page cache be the buffer cache. If another process needs memory, clean file-backed pages can be reclaimed by the kernel and read again later from the database file.

This does not mean mmap is always the right design for every database. It shifts some control from the database engine to the OS kernel, so systems that need custom I/O scheduling, specialized eviction policies, or tight control over page-fault latency may choose a private buffer manager. Datalevin's use case is different: it favors an embedded, low-administration engine that cooperates well with the rest of the host. This design has several benefits:

• Zero-Copy Reads: On the read hot path, Datalevin avoids copying bytes from the mapped database file into a separate JVM heap byte array. Because LMDB memory-maps the file, the native layer hands the address of the LMDB value memory to Java as a DirectByteBuffer. Datalevin's Clojure runtime then reads from that buffer and decodes the bytes into typed Datalevin values. This bypasses allocation of an intermediate byte array in Datalevin's JVM heap and minimizes garbage-collection overhead.

• OS-Wide Cache Management: The page cache is shared with the rest of the machine. This is a strong fit for cloud deployments, desktop applications, and embedded applications, where Datalevin is one component among many. The kernel can make better global decisions about clean page eviction than a database process that only sees its own heap and buffer pool.

• Less Configuration: A private buffer pool needs a size. Set it too small, and the database misses cache opportunities. Set it too large, and it starves the application or the rest of the host. mmap lets Datalevin rely on the OS to grow and shrink the effective cache according to real memory pressure.

• Immediate Recovery for Direct Commits: In LMDB's direct commit mode, crash recovery for the LMDB file does not require a long log-replay process. Section 1.2 explains the copy-on-write root-switching mechanism this relies on; Datalevin's optional WAL mode is a separate layer discussed later in this chapter.

By default, this memory map is read-only. That detail is important because many objections to mmap focus on writable mappings: accidental memory corruption, dirty-page writeback surprises, or weaker control over when modified pages reach storage. In LMDB's default mode, write transactions still read existing pages through the read-only map, but modified pages are written and published through LMDB's commit machinery rather than by changing mapped pages in place. Writable-map mode is a non-default, non-durable option, not the mode discussed here.

1.2 Read-Heavy Concurrency

LMDB provides MVCC (Multi-Version Concurrency Control) [1]. Readers never block writers, and writers never block readers. An illustration of LMDB's MVCC is in Figure 4.1. The easiest way to understand this, especially for Clojure programmers, is to think of LMDB's B+Tree as a persistent immutable data structure [2].

When a read transaction starts, it sees one stable root of the tree. That root is a snapshot: the reader can keep using it while other transactions commit newer versions. A writer does not mutate the pages that existing readers may still be using. Instead, it copies and modifies only the path from the root to the changed leaf pages. The unchanged parts of the tree are shared between the old and new versions.

At commit time, LMDB publishes the new version by switching the database root to the newly written tree. Readers that started earlier keep following the old root; new readers see the new root. This is structural sharing at storage-engine scale: small updates copy a small part of the tree, large unchanged regions are shared, and readers do not need locks on the writer's working pages.

The root switch is the publication point, not the whole physical write. New pages may have been written before the switch, but they are not the database state until the metadata that points to the new root is committed. If a crash happens after some new pages reach disk but before that metadata update, recovery uses the previous valid root. The transaction's changes are lost from the application's point of view, exactly as if the transaction had not committed. The physical bytes for the unpublished pages may still be present in the file, but no committed root points to them, so they are unreachable pages and can be overwritten or reused by later writes. Chapter 19 separates this atomic visibility rule from the disk-sync rules that determine when a commit is durable.

This design gives Datalevin fast and safe read concurrency. Reads are zero-copy and lockless, while writes remain atomic because a committed transaction becomes visible only when the root switch succeeds. In read-heavy workloads, throughput is often limited by CPU, memory bandwidth, or storage latency rather than by reader/writer lock contention.

2. B+Trees vs. LSM-Trees

Database storage engines generally fall into two families: sorted tree designs and log-structured designs. LMDB stores data in a B+Tree. Systems such as PostgreSQL and Oracle also rely heavily on B-tree-family indexes, while systems such as Cassandra, RocksDB, and LevelDB use log-structured merge-trees (LSM-trees) as their main storage pattern.

A B+Tree stores sorted keys in fixed-size pages [3]. A lookup starts at the root, walks through internal pages, and ends at a leaf page that contains the target key or, if the key is missing, the place where it would be. Because leaf entries are ordered by key, range scans can move through adjacent entries in sorted order. An LSM-Tree takes a different path [4]: it buffers writes and flushes sorted runs to disk, then merges those runs in the background. This can make writes very fast, but reads may need to consult several levels, and background compaction can add latency and CPU variation. The table below summarizes the performance characteristics of these two approaches.

Datalevin chose B+Trees because the Datalog query engine relies heavily on range scans and index joins. A B+Tree keeps data in key order and provides predictable read latency. By using LMDB, Datalevin avoids the "write stalls" and CPU spikes associated with LSM background compaction, making it a better fit for predictable, real-time applications. In addition, the multi-paradigm nature of Datalevin demands secondary indexes (Section 5), which often require storing large values, a pattern less suitable for LSM storage because such values can be rewritten repeatedly during compaction.

3. From LMDB to DLMDB

Standard LMDB is a general-purpose tool, but Datalevin uses a specialized fork called DLMDB to support advanced Datalog features. DLMDB improves LMDB in two ways that matter directly to query execution.

3.1 Order Statistics

A standard B+Tree cannot count every range without walking that range. DLMDB adds counted B+Trees, where each node in the tree stores the count of items in its subtree. Datalevin uses this metadata for indexes where fast counts, samples, and rank-based access matter. The counted B+Tree gives Datalevin these advantages:

• Cheap Counts: Prefix and range counts can be answered from tree metadata instead of by materializing matching datoms, which would be an O(n) operation. Common attribute/value-bound counts are cheap. For example, (d/count-datoms db nil :person/age 30) can be answered in O(1) while (d/count-datoms db nil :person/age nil) can be answered in O(log n).
• Fast Pagination: You can skip the first 1,000,000 items in a sorted range and start reading the 1,000,001st item instantly using "rank-based" lookups.
• Quick Sampling: Given an ordered sequence of positions to sample, a counted DB allows a cursor to move up and down the tree to reach each position directly without going through all the keys in between. In those cases, sampling becomes O(log n) instead of O(n).

These advantages translate directly into efficient query planning: the Datalog engine uses these counts and samples to decide the most efficient join order, such as whether to filter by age first or by city first.

3.2 Prefix Compression

DLMDB also uses page-level prefix compression. Datalog indexes often contain neighboring keys that share an encoded prefix. In EAV, nearby keys may begin with nearby entity ids. In AVE, many neighboring keys may begin with the same encoded attribute id before the encoded value differs. Prefix compression avoids storing those shared leading bytes over and over.

The practical effects are smaller pages and better locality. More index entries fit in the same amount of storage, and more useful keys fit in memory pages and processor caches, which can make index walks and range scans cheaper. The benefit is workload-dependent. Long structured KV keys can see larger savings. Datalog indexes benefit too, but the shared prefix is often a compact encoded id, so the effect is usually more modest than the best KV cases. Chapter 19 returns to the tuning implications, and Chapter 15 explains how DUPSORT nesting avoids repeating larger EAV and AVE prefixes in the first place.

4. From Datoms to EAV and AVE

At the logical level, a Datalevin fact is a datom: [entity attribute value]. At the storage level, the same datoms are encoded into sorted key-value entries. Datalevin stores the primary Datalog indexes in two orders:

• EAV (Entity-Attribute-Value): optimized for finding the facts about one entity.
• AVE (Attribute-Value-Entity): optimized for finding entities that have a particular attribute/value pair, and for range scans over attribute values.

As shown in Figure 4.2, Datalevin puts the same set of datoms into both indexes simultaneously. The important point for this chapter is the access pattern: EAV keeps facts for one entity close together, while AVE keeps facts for one attribute/value lookup or range close together. Chapter 15 explains the physical DUPSORT nesting behind these indexes, how the key/value split saves space by avoiding repeated prefixes, and why Datalevin's core Datalog indexes are EAV and AVE.

Datalevin encodes triples into raw bytes, using a header byte to distinguish data types. Datalevin's binary encoding ensures that the binary sort order matches the logical data sort order. For example, encoded numbers sort as numbers, encoded strings sort as strings, and encoded instants sort by time. This property lets the storage engine use the same byte ordering for equality lookup, range lookup, and ordered iteration. This consistency between binary and logical ordering is the key design feature that leads to Datalevin's simplicity.

5. Secondary Indexes and Blob Storage

Beyond the primary triple indexes, Datalevin supports specialized secondary indexes such as full-text search (FTS), vector search, and indexed document (idoc) indexes. An idoc is Datalevin's indexed document value: a nested map-like document whose paths can be queried efficiently. These features are not external plugins; they are integrated directly into the same LMDB environment.

5.1 Leveraging the KV Substrate

Secondary indexes are implemented as additional named sub-databases (DBIs) within the same storage file. A DBI is a named logical key-value space inside one LMDB environment. It lets Datalevin keep the primary datom indexes, full-text postings, vector metadata, document path indexes, and internal bookkeeping in one transactional storage substrate.

By default, Datalevin updates these indexes synchronously in the same transaction as the source datoms, preserving read-your-writes behavior for query functions such as fulltext, vec-neighbors, embedding-neighbors, and idoc-match. The secondary indexes are available for query immediately after commit by default.

For high-throughput data ingestion, though, full-text, vector, and embedding indexes can also opt into :indexing-mode :async. In async mode, the source datoms and a durable secondary-index job are committed atomically, then an in-process worker applies the index update after the transaction returns. Queries over that index become eventually consistent until the worker catches up. This is useful when indexing is expensive, especially for embedding providers that may call a local model or remote API.

5.2 Blob Storage Capabilities

While a Datalog triple is often a small piece of data, Datalevin also needs to handle large values. There are two common cases.

• Large secondary-index structures: Full-text, vector, embedding, and idoc indexes may need to store postings lists, vector metadata, serialized document structures, or other large internal values. Datalevin can store these as blobs in specialized DBIs instead of scattering them through the main triple indexes. For example, a search index might store a large compressed postings bitmap as a single KV value, then retrieve and process it with the same zero-copy efficiency as a simple triple.
• Large datom values: A user datom can also have a large value, such as a document, binary payload, or long text value. Datalevin does not put the whole payload inline in EAV and AVE. Instead, it stores the large value in a dedicated datalevin/giants DBI, keyed by an auto-incrementing integer giant id. The EAV and AVE indexes store that giant id, not the full value. When the datom is read, Datalevin follows the giant id to retrieve the original value from datalevin/giants. This is automatic internal storage behavior during transaction processing for values that exceed Datalevin's inline encoding threshold. Application code chooses the attribute value and, when needed, its schema type; it does not opt into datalevin/giants with a separate schema property or API call.

This indirection keeps the primary indexes compact and ordered even when some values are large. It also lets Datalevin leverage LMDB's ability to store values up to 2 GB in size while preserving efficient equality lookup, range scans, and secondary-index maintenance.

6. The Key-Value API: Direct Access

While Datalog is the primary interface, Datalevin exposes the underlying KV store as a first-class API. This is a deliberate design choice: the Datalog engine is built on top of this KV layer, rather than as a separate opaque engine.

Datalog and custom KV data can live in the same LMDB file. The Datalog engine uses named DBIs for indexes such as EAV and AVE, and application code can use other named DBIs in the same store for direct key-value data. Those DBIs share the same LMDB environment, durability settings, backup/copy behavior, and transaction boundary.

Exposing the KV layer lets application code bypass the triple model when it is not the best fit, for example when building custom indexes, high-frequency counters, or large binary blob stores. This multi-paradigm approach means you are not forced to fit every data shape into a Datalog triple if a simple key-value pair is more efficient.

The details of the KV API and its practical usage are covered in Chapter 10.

7. Persistence and Durability: WAL Mode

By default, local embedded Datalevin stores use LMDB's direct commit path. This is safe and fast for many workloads, and, as described above, LMDB's copy-on-write root switching gives the LMDB file immediate recovery after a crash.

For write-intensive workloads, Datalevin can add Write-Ahead Log (WAL) mode above LMDB. A WAL is an append-only transaction log. Datalevin first records the transaction in that log, then applies the change to LMDB in a faster, non-durable mode. Depending on the WAL durability profile, Datalevin may sync WAL records immediately or batch them before syncing. Once a WAL record is durable, it is the recovery source, while LMDB remains the indexed B+Tree state used for reads. When local WAL mode is enabled and no profile is specified, the default profile is :relaxed, which batches syncs and trades a short crash-loss window for higher throughput.

Application code reads the same committed state in WAL mode. If transact! returns success, the datoms have been applied to LMDB's indexes and the next query on the connection can see them, just as in non-WAL mode. What WAL mode changes is when the log and LMDB file are synced to durable storage; it does not require a different read-after-write pattern. In the relaxed profile, a crash before the next WAL sync, or before a snapshot/checkpoint that forces one, can lose the most recent acknowledged transactions, but while the process is running those transactions are part of the current LMDB-backed database state.

WAL mode also supports multi-threaded write concurrency and lays the foundation for data replication and high availability (HA) server behavior. In this chapter, the important point is the storage shape of WAL. The operational details are covered in Part V.

7.1 How WAL Mode Works

At a high level, a WAL transaction follows this sequence:

1. Application Request: The application requests a transaction.
2. WAL Append: The change is encoded and appended to a sequential log segment file.
3. Position Tracking: Every transaction receives a strictly increasing log position. Later chapters call this position a log sequence number (LSN).
4. Fast LMDB Update: The change is applied to the LMDB B+Tree, so ordinary reads can see the committed data. In WAL mode this LMDB update may be non-durable until a checkpoint or sync; durability comes from the WAL record rather than from forcing the LMDB file itself to storage.
5. Durability Scheduling: Depending on the chosen durability profile, Datalevin either syncs the WAL record immediately or batches it for a later sync.
6. Acknowledgment: Under :strict and :extra, acknowledgment waits for the WAL record to reach durable storage. Under :relaxed, acknowledgment can occur before the next group sync, leaving a small gap between acknowledged commit and durable sync.

On restart after a crash, Datalevin scans the WAL segments and replays any committed transactions that were not yet fully persisted in the LMDB file.

WAL mode is enabled according to the Datalevin surface or deployment mode you are using. For local stores, WAL is an explicit opt-in:

• Datalog databases: Local embedded databases disable WAL by default; enable it with {:wal? true} in create-conn or get-conn options.
• Key-value stores: Disabled by default; enable with {:wal? true} in open-kv options.

For server deployments, WAL is part of the operational design:

• Async read replicas: A non-HA replica requires WAL on the primary so it can bootstrap from a copy and then tail durable records.
• Consensus-lease HA: HA forces WAL on.

7.2 Replication and Operations

WAL mode has operational APIs such as create-snapshot!, gc-txlog-segments!, txlog-watermarks, and open-tx-log. Those operations matter for long-running services, replication, low-level change capture, and production tuning. They are covered in detail in Chapters 19, 20, and 22.

Summary

Datalevin's storage layer focuses on pragmatic engineering:

• It uses LMDB for stable embedded storage and zero-copy reads.
• It uses B+Trees to ensure predictable read performance for complex Datalog queries.
• It adds DLMDB extensions like order statistics to power the query planner.
• It stores datoms in EAV and AVE orders, covering entity-local reads and attribute/value lookups with compact sorted indexes.
• It integrates full-text, vector, embedding, and idoc indexes into the same LMDB environment, with synchronous updates by default and async indexing as an explicit ingestion option.
• It keeps large values out of the primary datom indexes by storing them through giant-value indirection.
• It exposes the underlying KV API for application-owned DBIs that need direct key-value access in the same store.
• It provides a WAL mode to scale write performance without sacrificing the B+Tree model.

By understanding these fundamentals, you can better tune your schema and queries for maximum performance.

References

[1] Howard Chu, "LMDB," The Databaseology Lectures, Carnegie Mellon University, Fall 2015, YouTube video. URL: https://www.youtube.com/watch?v=tEa5sAh-kVk.

[2] Chris Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998. DOI: https://doi.org/10.1017/CBO9780511530104.

[3] Rudolf Bayer and Edward M. McCreight, "Organization and Maintenance of Large Ordered Indexes," Acta Informatica 1:173-189, 1972. DOI: https://doi.org/10.1007/BF00288683.

[4] Patrick E. O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth J. O'Neil, "The Log-Structured Merge-Tree (LSM-Tree)," Acta Informatica 33:351-385, 1996. DOI: https://doi.org/10.1007/s002360050048.