Lithos

Lithos

High-Performance Log-Structured Merge (LSM) Tree Key-Value Storage Engine

---

Overview

Lithos is a custom-built embeddable key-value database built around a Log-Structured Merge Tree (LSM Tree).

The storage engine is implemented in C++17, exposed safely through a Rust cxx FFI bridge, and monitored through a Next.js telemetry dashboard.

Highlights

• Skip List MemTable
• Write Ahead Log (WAL)
• Sorted String Tables (SSTables)
• Multi-Level Storage
• Background Compaction
• Bloom Filters
• Compression
• Rust ↔ C++ Zero-cost FFI
• Axum REST API
• Live Dashboard

---

Table of Contents

• Architecture
• Features
• Tech Stack
• Write Path
• Read Path
• LSM Layout
• Compaction
• Bloom Filters
• Storage Hierarchy
• Request Lifecycle
• Project Structure
• Dashboard
• API
• Getting Started
• Roadmap
• Project Status

---

Preview

System Architecture

graph LR
Client[Client]
API[Rust Axum API]
FFI[cxx FFI]
Engine[C++ Engine]
WAL[(WAL)]
Mem[(Skip List)]
L0[(L0)]
L1[(L1)]
L2[(L2)]
Bloom[Bloom Filter]
Dashboard[Next.js Dashboard]

Client-->API
API-->FFI
FFI-->Engine
Engine-->WAL
Engine-->Mem
Mem--Flush-->L0
L0--Compaction-->L1
L1--Compaction-->L2
API-->Bloom
Dashboard-->API

Loading

Features

Feature	Status
Skip List MemTable	✅
WAL	✅
SSTables	✅
Multi-Level SSTables	✅
Bloom Filter	✅
Background Compaction	✅
Compression	✅
Rust FFI	✅
REST API	✅
Live Dashboard	✅

Tech Stack

Layer	Technology
Storage Engine	C++17
FFI	Rust cxx
Backend	Rust + Axum
Frontend	Next.js
UI	Tailwind CSS

Zero-Cost FFI

Lithos communicates between Rust and C++ through the cxx crate with negligible overhead.

Write Path

flowchart LR
A[PUT]
B[Append WAL]
C[Insert MemTable]
D{Full?}
E[Return]
F[Flush]
G[Compaction]

A-->B-->C-->D
D--No-->E
D--Yes-->F-->G-->E

Loading

Read Path

flowchart TD
A[GET]
A-->B[MemTable]
B--Found-->C[Return]
B--Miss-->D[Bloom Filter]
D--Definitely No-->E[NULL]
D--Maybe-->F[SSTables]
F-->C

Loading

LSM Tree

Memory
┌─────────────┐
│ MemTable    │
└─────┬───────┘
      │ Flush
      ▼
┌─────────────┐
│ L0 SSTables │
└─────┬───────┘
      │ Compaction
      ▼
┌─────────────┐
│ L1 SSTables │
└─────┬───────┘
      ▼
┌─────────────┐
│ L2 SSTables │
└─────────────┘

Flush Lifecycle

stateDiagram-v2
[*]-->Writing
Writing-->Writing
Writing-->Flush: Threshold
Flush-->SSTable
SSTable-->Writing

Loading

Skip List (MemTable)

The MemTable uses a probabilistic Skip List for O(log n) insertion and lookup.

Compaction

flowchart LR
A[L0-1]
B[L0-2]
C[L0-3]
D[Merge]
E[L1]

A-->D
B-->D
C-->D
D-->E

Loading

Bloom Filter

flowchart LR
Query-->Bloom
Bloom--No-->Stop[Skip Disk]
Bloom--Maybe-->Disk[SSTables]

Loading

Request Lifecycle

sequenceDiagram
participant Client
participant Rust
participant CPP
participant WAL
participant Mem
participant Disk

Client->>Rust: PUT
Rust->>CPP: FFI
CPP->>WAL: Append
CPP->>Mem: Insert
CPP-->>Rust: OK
Rust-->>Client: 200
Mem->>Disk: Flush
Disk->>Disk: Compaction

Loading

Project Structure

Lithos/
├── engine/
├── backend/
├── frontend/
├── ffi/
├── docs/
└── data/

Deployment Topology

Dashboard

The dashboard visualizes:

• MemTable occupancy
• WAL activity
• SSTables
• Compaction
• Bloom filter efficiency
• Storage hierarchy
• Query metrics
• Disk usage

Add screenshots or GIFs:

• docs/assets/dashboard.png
• docs/assets/demo.gif

REST API

PUT

curl -X POST http://localhost:8080/set \
-H "Content-Type: application/json" \
-d '{"key":"hello","value":"world"}'

GET

curl http://localhost:8080/get?key=hello

Getting Started

Backend

cd backend
cargo run

Frontend

cd frontend
npm install
npm run dev

Open:

http://localhost:3000

Roadmap

• Distributed replication
• MVCC
• Transactions
• Range scans
• Parallel compaction
• Block cache
• SIMD optimizations

Project Status

• Core LSM Engine
• WAL
• Skip List
• Bloom Filters
• Multi-Level SSTables
• Background Compaction
• Compression
• Rust FFI
• Axum API
• Next.js Dashboard

---

Built as a systems engineering project focused on storage engines, database internals, and high-performance systems programming.