Erebor

Erebor is a learning-focused, embedded LSM-tree key-value store written in Odin and inspired by SlateDB. Persistent data will eventually live in S3-compatible object storage; today the project is building and measuring the in-memory MemTable first.

Erebor is experimental and is not ready for production use.

The write path we are working toward is:

put -> WAL -> mutable MemTable -> immutable MemTable -> SSTable -> S3-compatible object storage ("disk")

See PRD.md for the requirements, learning roadmap, and decision log.

Current status

Phase 0 has an arena-backed sorted-slice MemTable in memtables/. It provides ordered writes, point lookups, replacement, lower-bound seek, forward iteration, clear ownership, and approximate size tracking. Iterators report when a mutation invalidates them. The next implementation is an arena-backed skip list with the same behavior so both representations can be tested against the same contract and workloads.

Phase	Focus	State
0	MemTable ownership, ordering, API, and implementation comparison	In progress
1	WAL, SSTable, and local manifest	Not started
2	S3-compatible object storage	Not started
3	Database range scans, compaction, caching, and bloom filters	Not started

Target architecture

Architecture status: This diagram shows the target end state. Today, Erebor implements only the arena-backed sorted-slice MemTable, including its ordered iterator and seek contract. The local filesystem backend will exercise the storage contract during development; S3-compatible object storage is the target persistent tier ("disk").

The design borrows RocksDB's active/immutable MemTable pipeline, read order, block-oriented reads, and leveled compaction, then adapts them to SlateDB-style immutable object storage and versioned manifests.

The Erebor instance groups the embedded stack with its persistent S3 namespace. Within it, the Erebor embedded stack contains library-owned memory, background procedures, and the object-store abstraction. Only the host application sits outside the instance boundary.

The editable source is design/architecture.d2. Regenerate the PNG with task architecture after changing it.

The procedure names in the diagram are design vocabulary rather than a frozen public API. They establish the ownership and publication boundaries the Odin implementation must preserve:

Boundary	Odin rule
Database mutation	Procedures that mutate state take explicit pointers such as db: ^DB; errors cross package boundaries as return values.
Active → immutable switch	Queue a ^Memtable, not a copied Memtable. A virtual.Arena is an owner and must not be shallow-copied or destroyed while a reader or flush still aliases it.
MemTable payloads	Copy caller slices into the table's long-lived arena. Seal the arena with the table, and bulk-destroy it only after the SST is published in a durable manifest.
Flush and compaction scratch	Give each job its own arena or explicit mem.Allocator; destroy or free_all it when the procedure completes. Never allocate persisted state from scratch memory.
Read results	The current memtables.get returns a borrowed arena slice. The eventual database API must copy into caller-owned memory or carry an explicit lifetime/pin; it must not disguise an internal alias as owned data.
Atomic visibility	Upload immutable data first, then conditionally publish the next complete manifest. Only after that publication may old arenas, WAL segments, or SSTables become reclaimable.

This keeps three lifetimes separate: request/job scratch, MemTable-generation memory, and database/cache state. It also keeps storage mutation simple: data objects are immutable; the manifest is the sole published view of which objects form the database.

Quick start

Requirements:

Dependency	Required	Notes
Odin compiler	Yes	Tested with dev-2026-07-nightly:819fdc7
Task 3.x	Optional	Cross-platform command wrapper
D2 0.7+	Optional	Regenerates design/architecture.png from its editable source
Third-party packages	No	Phase 0 uses only Odin's core collection

From the repository root:

odin version
task verify

task verify performs the release-aligned strict package check, runs the tests with bad-memory detection, builds build/liberebor_memtables.a, and validates generated package documentation. The individual commands are also available:

task check
task test
task build
task docs
task architecture

# Or invoke Odin directly
odin check memtables -no-entry-point \
  -vet -vet-tabs -vet-style -strict-style -warnings-as-errors -disallow-do
odin test memtables \
  -vet -vet-tabs -vet-style -strict-style -warnings-as-errors -disallow-do \
  -define:ODIN_TEST_FANCY=false \
  -define:ODIN_TEST_FAIL_ON_BAD_MEMORY=true
odin build memtables -build-mode:lib -out:build/liberebor_memtables.a
odin doc memtables

Normal Odin consumers import Erebor as source. The static library build is a compiler smoke test and is not the package distribution format.

The package-level API, ownership rules, and complexity notes live in memtables/README.md.

Package direction

Odin packages are directories, and every .odin file in a directory belongs to the same package. We will use packages as reusable library boundaries, not as a reason to split every implementation detail into another directory.

The repository should grow toward this shape only as each phase needs it:

.
├── PRD.md
├── README.md
├── design/                # Editable architecture source and rendered PNG
│   ├── architecture.d2
│   └── architecture.png
├── memtables/             # MemTable contract and concrete implementations
│   ├── doc.odin           # package-level `odin doc` overview
│   ├── types.odin         # entries, options, and shared result types
│   ├── sorted_slice.odin  # simple ordered reference implementation
│   ├── skip_list.odin     # arena-backed production candidate
│   └── *_test.odin
├── examples/
│   └── basic/             # small runnable `package main`
├── benchmarks/
│   └── memtables/         # explicit workloads, separate from correctness tests
├── wal/                   # Phase 1 append and replay package
├── sstable/               # Phase 1 immutable table format and iterator
├── manifest/              # Phase 1 database state snapshots
├── object_store/          # Phase 1 local backend; Phase 2 S3 backend
└── erebor/                # eventual high-level database API and lifecycle

This is a direction, not a request to create empty packages. In particular, the two MemTable representations should initially remain in one package as concrete types. We should introduce a factory or type-erased interface only after the shared operations are proven by the database read and flush paths.

MemTable plan

The sorted slice is the correctness and cache-locality baseline. The skip list is the primary general-purpose candidate because it keeps entries ordered while improving insertion cost and leaving a path toward concurrent writes.

The milestones are:

1. Freeze the shared semantics: byte ordering, copied ownership, missing versus empty values, size accounting, reset, and explicit iterator failure behavior.
2. Add forward iteration and lower-bound seek. A successful put or reset invalidates existing iterators instead of silently changing their view.
3. Implement a single-writer arena-backed skip list before attempting atomic pointer splicing or lock-free concurrency.
4. Run identical random-write, ordered-write, point-read, seek, and full-scan benchmarks for the sorted slice and skip list.
5. Choose the default from evidence while keeping concrete implementations reusable for experiments.
6. Add internal keys (user_key, sequence, kind) when Phase 1 introduces WAL recovery and snapshots. Tombstones and concurrent writers remain later work.

Reuse and publishing

Odin does not have an official package manager. Until the project earns a stable API, consumers should pin a Git commit or release tag and vendor the source. A consumer can map the vendored checkout as a library collection:

odin check path/to/your_app -collection:erebor=path/to/erebor

Packages beneath that checkout can then be imported with paths such as:

import "erebor:memtables"

Before the first public tag, the repository should have:

• a license and contribution guide;
• a documented supported Odin release or nightly revision;
• runnable examples that import the library instead of reaching into private representation details;
• package comments and declaration comments that produce useful odin doc output;
• CI for tests, strict checking, formatting, and at least the supported host platforms;
• semantic version tags and release notes that call out API or file-format compatibility.

There is no need to add third-party package metadata yet. The source tree, Git tag, documentation, and explicit dependency instructions are the distribution contract.

Reference patterns

• RocksDB MemTable design for the active-to-immutable switch, newest-first reads, and background flush.
• RocksDB overview and compaction notes for block cache, L0 output, and merging sorted runs into larger levels.
• SlateDB file layout and manifest design for immutable WAL and compacted SST objects, complete manifest snapshots, and conditional updates.
• Odin core:mem/virtual for growing virtual arenas and explicit bulk lifetime management.
• Official Odin package guidance for directory-based packages, imports, visibility, and library collections.
• Official package documentation guidance for doc.odin and declaration comments.
• Official test runner guidance for local and all-package test commands.
• odin-lang/Odin for multi-file library packages with nearby tests.
• odin-lang/examples for small, isolated runnable programs.
• laytan/odin-http for a substantial Odin library with subpackages, examples, compatibility notes, and generated documentation.