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.

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.

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:

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.

Requirements:

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.

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.

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.

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.

• 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.