# devfiqi/lsm-engine architecture

> Architecture diagram of the GitHub repository devfiqi/lsm-engine, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-10-03). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/devfiqi/lsm-engine
- Repository: https://github.com/devfiqi/lsm-engine

## Overview

This Go repository implements an embedded LSM key-value engine. The principal workflow enters through the DB API: writes are WAL-backed before reaching the in-memory table, flushes create SSTables and feed compaction, while reads check memory before searching tables. The graph also shows recovery, skip-list storage, and the SSTable lookup accelerators. Relationships are based on source excerpts and README statements; no unsampled implementation was inspected.

Main entry points: [`db/db.go`](https://github.com/devfiqi/lsm-engine/blob/main/db/db.go) (DB Engine), [`sstable/reader.go`](https://github.com/devfiqi/lsm-engine/blob/main/sstable/reader.go) (SSTable Reader), [`compaction/compaction.go`](https://github.com/devfiqi/lsm-engine/blob/main/compaction/compaction.go) (K-way Merge), [`sstable/writer.go`](https://github.com/devfiqi/lsm-engine/blob/main/sstable/writer.go) (SSTable Writer)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_api["Engine API"]
  node_db["DB Engine<br/>[db.go]"]
  node_types["Storage API<br/>[types.go]"]
  node_errors["Engine Errors<br/>[errors.go]"]
end

subgraph group_write["Write Buffer"]
  node_memtable["MemTable<br/>[memtable.go]"]
  node_skiplist["Concurrent Skip-list<br/>[skiplist.go]"]
  node_wal["Write-Ahead Log<br/>[wal.go]"]
end

subgraph group_disk["SSTable Storage"]
  node_flush["SSTable Flush<br/>[writer.go]"]
  node_writer["SSTable Writer<br/>[writer.go]"]
  node_reader["SSTable Reader<br/>[reader.go]"]
  node_tables[("SSTable Files<br/>[writer.go]")]
  node_block["Data Blocks<br/>[reader.go]"]
end

subgraph group_maintenance["Recovery &amp; Compaction"]
  node_recovery["WAL Recovery<br/>[recover.go]"]
  node_compaction["Compaction Manager<br/>[compaction.go]"]
  node_merge["K-way Merge<br/>[compaction.go]"]
end

subgraph group_indexing["Lookup Structures"]
  node_bloom["Bloom Filter<br/>[bloom.go]"]
  node_sparse["Sparse Index<br/>[reader.go]"]
end

node_client(("Application"))

node_client -->|"calls"| node_db
node_types -->|"defines API"| node_db
node_db -->|"recovers WAL"| node_recovery
node_recovery -->|"replays records"| node_wal
node_db -->|"writes and reads"| node_memtable
node_memtable -->|"appends first"| node_wal
node_memtable -->|"stores entries"| node_skiplist
node_db -->|"flushes on full"| node_flush
node_flush -->|"encodes entries"| node_writer
node_writer -->|"writes files"| node_tables
node_db -->|"registers flush"| node_compaction
node_compaction -->|"runs compaction"| node_merge
node_merge -->|"scans inputs"| node_reader
node_merge -->|"writes merged output"| node_writer
node_merge -->|"builds filter"| node_bloom
node_writer -->|"embeds filter"| node_bloom
node_db -->|"searches tables"| node_reader
node_reader -->|"checks membership"| node_bloom
node_reader -->|"searches index"| node_sparse
node_reader -->|"scans selected block"| node_block
node_errors -.->|"reports failures"| node_db

click node_db "https://github.com/devfiqi/lsm-engine/blob/main/db/db.go"
click node_types "https://github.com/devfiqi/lsm-engine/blob/main/types.go"
click node_errors "https://github.com/devfiqi/lsm-engine/blob/main/errors.go"
click node_memtable "https://github.com/devfiqi/lsm-engine/blob/main/memtable/memtable.go"
click node_skiplist "https://github.com/devfiqi/lsm-engine/blob/main/skiplist/skiplist.go"
click node_wal "https://github.com/devfiqi/lsm-engine/blob/main/wal/wal.go"
click node_recovery "https://github.com/devfiqi/lsm-engine/blob/main/wal/recover.go"
click node_flush "https://github.com/devfiqi/lsm-engine/blob/main/sstable/writer.go"
click node_writer "https://github.com/devfiqi/lsm-engine/blob/main/sstable/writer.go"
click node_reader "https://github.com/devfiqi/lsm-engine/blob/main/sstable/reader.go"
click node_tables "https://github.com/devfiqi/lsm-engine/blob/main/sstable/writer.go"
click node_compaction "https://github.com/devfiqi/lsm-engine/blob/main/compaction/compaction.go"
click node_merge "https://github.com/devfiqi/lsm-engine/blob/main/compaction/compaction.go"
click node_bloom "https://github.com/devfiqi/lsm-engine/blob/main/bloom/bloom.go"
click node_sparse "https://github.com/devfiqi/lsm-engine/blob/main/sstable/reader.go"
click node_block "https://github.com/devfiqi/lsm-engine/blob/main/sstable/reader.go"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_db,node_types,node_errors toneBlue
class node_memtable,node_skiplist,node_wal toneAmber
class node_flush,node_writer,node_reader,node_tables,node_block toneMint
class node_recovery,node_compaction,node_merge toneRose
class node_bloom,node_sparse,node_client toneIndigo
```

## Components

### Engine API

- [DB Engine](https://github.com/devfiqi/lsm-engine/blob/main/db/db.go): `db/db.go`
- [Storage API](https://github.com/devfiqi/lsm-engine/blob/main/types.go): `types.go`
- [Engine Errors](https://github.com/devfiqi/lsm-engine/blob/main/errors.go): `errors.go`

### Write Buffer

- [MemTable](https://github.com/devfiqi/lsm-engine/blob/main/memtable/memtable.go): `memtable/memtable.go`
- [Concurrent Skip-list](https://github.com/devfiqi/lsm-engine/blob/main/skiplist/skiplist.go): `skiplist/skiplist.go`
- [Write-Ahead Log](https://github.com/devfiqi/lsm-engine/blob/main/wal/wal.go): `wal/wal.go`

### SSTable Storage

- [SSTable Flush](https://github.com/devfiqi/lsm-engine/blob/main/sstable/writer.go): `sstable/writer.go`
- [SSTable Writer](https://github.com/devfiqi/lsm-engine/blob/main/sstable/writer.go): `sstable/writer.go`
- [SSTable Reader](https://github.com/devfiqi/lsm-engine/blob/main/sstable/reader.go): `sstable/reader.go`
- [SSTable Files](https://github.com/devfiqi/lsm-engine/blob/main/sstable/writer.go): `sstable/writer.go`
- [Data Blocks](https://github.com/devfiqi/lsm-engine/blob/main/sstable/reader.go): `sstable/reader.go`

### Recovery & Compaction

- [WAL Recovery](https://github.com/devfiqi/lsm-engine/blob/main/wal/recover.go): `wal/recover.go`
- [Compaction Manager](https://github.com/devfiqi/lsm-engine/blob/main/compaction/compaction.go): `compaction/compaction.go`
- [K-way Merge](https://github.com/devfiqi/lsm-engine/blob/main/compaction/compaction.go): `compaction/compaction.go`

### Lookup Structures

- [Bloom Filter](https://github.com/devfiqi/lsm-engine/blob/main/bloom/bloom.go): `bloom/bloom.go`
- [Sparse Index](https://github.com/devfiqi/lsm-engine/blob/main/sstable/reader.go): `sstable/reader.go`

### Other components

- **Application**

## Connections

- Application → DB Engine: calls (evidence: `README.md`)
- Storage API → DB Engine: defines API (evidence: `types.go`)
- DB Engine → WAL Recovery: recovers WAL (evidence: `db/db.go`)
- WAL Recovery → Write-Ahead Log: replays records
- DB Engine → MemTable: writes and reads (evidence: `db/db.go`)
- MemTable → Write-Ahead Log: appends first (evidence: `memtable/memtable.go`)
- MemTable → Concurrent Skip-list: stores entries (evidence: `memtable/memtable.go`)
- DB Engine → SSTable Flush: flushes on full (evidence: `db/db.go`)
- SSTable Flush → SSTable Writer: encodes entries (evidence: `sstable/writer.go`)
- SSTable Writer → SSTable Files: writes files (evidence: `sstable/writer.go`)
- DB Engine → Compaction Manager: registers flush (evidence: `db/db.go`)
- Compaction Manager → K-way Merge: runs compaction (evidence: `compaction/compaction.go`)
- K-way Merge → SSTable Reader: scans inputs (evidence: `compaction/compaction.go`)
- K-way Merge → SSTable Writer: writes merged output (evidence: `compaction/compaction.go`)
- K-way Merge → Bloom Filter: builds filter (evidence: `compaction/compaction.go`)
- SSTable Writer → Bloom Filter: embeds filter (evidence: `sstable/writer.go`)
- DB Engine → SSTable Reader: searches tables (evidence: `db/db.go`)
- SSTable Reader → Bloom Filter: checks membership (evidence: `sstable/reader.go`)
- SSTable Reader → Sparse Index: searches index (evidence: `sstable/reader.go`)
- SSTable Reader → Data Blocks: scans selected block (evidence: `sstable/reader.go`)
- Engine Errors → DB Engine: reports failures
