# fengbeihong/leveldb architecture

> Architecture diagram of the GitHub repository fengbeihong/leveldb, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-04-22). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/fengbeihong/leveldb
- Repository: https://github.com/fengbeihong/leveldb

## Overview

##### Project type and purpose
- LevelDB is a C++ library implementing a high‑performance, ordered key‑value store.
- It is not a client‑server database but an embeddable library (LSM‑tree based) that applications link into.
- The README calls out core features (Put/Get/Delete, snapshots, atomic batches, custom comparators, pluggable compression and environment abstractions).

##### File structure
Top‑level directories:
- /leveldb – public C API and C++ headers (the “frontend” / client interface)
- db/ – core engine implementation (MemTable, WAL, VersionSet, compactions)
- table/ – SSTable (on‑disk sorted table) format, block builders, iterators
- util/ – helper data structures and utilities (arena allocator, bloom filters, caching, logging, CRC)
- port/ – OS/environment‑abstraction interfaces (Env) and platform glue (POSIX, Windows)
- helpers/ – in‑process “memenv” to simulate file system in memory for testing
- third_party/ – bundled dependencies (Google Benchmark, GoogleTest)
- benchmarks/, tests under db/, table/, util/, issues/ – performance and correctness test code
- CMakeLists.txt, cmake/ – build and configuration

##### Extract insights from README
- Public interface lives under include/leveldb/*.h – callers only include those headers.
- Core engine modules invoked by DB::Open(): builder, MemTable+WAL, table_cache, version_set, compaction.
- Virtual Env interface allows pluggable file I/O and thread scheduling.
- Compression (Snappy/Zstd) and Bloom filter policy are optional plugins.

a. Client API Layer
– include/leveldb/db.h (DB interface), options, comparator, filter_policy, iterator, write_batch
b. DB Engine
– DBImpl (receives API calls)
– Write‑Ahead Log (WAL)
– MemTable (in‑memory skiplist) + Immutable MemTable
– VersionSet (metadata about SSTables and levels)
– Compaction Manager (background thread merging tables)
c. Table (SSTable) Storage
– TableBuilder (writes .sst files), BlockBuilder, FilterBlockBuilder
– TableReader, BlockReader, two‑level iterator
– TableCache for open file handles and block caching
d. Utility Services
– Cache (LRU cache for blocks), Arena allocator, BloomFilter code, CRC32C, Env abstraction (filesystem, logs, mutexes)
e. Environment / Platform Abstraction
– port::Env interface, with POSIX and Windows implementations in util/env_*.cc
– memenv for in‑memory tests
f. External Plugins & Dependencies
– Snappy / Zstd compression libraries
– Google Benchmark (benchmarks/db_bench_*.cc), GoogleTest

##### Relationships and dataflow
- Client → DBImpl: calls Put/Get/Delete/Snapshot/WriteBatch
- DBImpl → WAL + MemTable: writes go first to WAL, then into in‑memory MemTable
- MemTable flush → TableBuilder → SSTable file on disk → VersionSet updated
- Background Compaction → reads existing SSTables from disk via TableCache, merges, writes new SSTables, updates VersionSet
- Get/Iterator → consult MemTable → Immutable MemTable → SSTables via VersionSet + TableCache → use Bloom filters → decompress blocks → return values
- Snapshot → VersionSet creates a point‑in‑time view

##### Architectural patterns and design principles
- Log‑Structured Merge Tree (LSM‑tree) for write performance and compaction
- Layered architecture: public API → engine core → storage layer → environment
- Plug‑in interfaces: Comparator, FilterPolicy, Env, Compression
- Separation of concerns: db/, table/, util/, port/
- Threading: single writer, background compaction thread(s) via Env

## Diagram (Mermaid)

```mermaid
graph TB
    %% Client API Layer
    subgraph "Client API Layer"
        direction TB
        DBAPI["DB Interface"]:::frontend
        Options["Options"]:::frontend
        Comparator["Comparator"]:::frontend
        FilterPolicy["FilterPolicy"]:::frontend
        IteratorAPI["Iterator"]:::frontend
        WriteBatchAPI["WriteBatch"]:::frontend
        TableAPI["Table API"]:::frontend
        TableBuilderAPI["TableBuilder API"]:::frontend
    end

    %% Engine Core
    subgraph "Engine Core"
        direction TB
        DBImpl["DBImpl (API Dispatch)"]:::core
        WALWriter["WAL Writer"]:::core
        WALReader["WAL Reader"]:::core
        MemTable["MemTable & Immutable"]:::core
        VersionSet["VersionSet"]:::core
        Builder["TableBuilder (Flush)"]:::core
        TableCacheCore["TableCache"]:::core
        WriteBatchInt["WriteBatch (Internal)"]:::core
        Compaction["Compaction Manager"]:::core
    end

    %% Storage Layer
    subgraph "Storage Layer"
        direction TB
        TableReader["TableReader"]:::storage
        BlockBuilder["BlockBuilder"]:::storage
        FilterBlock["FilterBlockBuilder"]:::storage
        TwoLevelIter["Two-Level Iterator"]:::storage
        Format["Table Format"]:::storage
        SSTable[(SSTable Files)]:::disk
    end

    %% Utility Services
    subgraph "Utility Services"
        direction TB
        Cache["LRU Cache"]:::util
        Arena["Arena Allocator"]:::util
        Bloom["Bloom Filter"]:::util
        CRC["CRC32C"]:::util
        EnvDefault["Env Delegator"]:::util
        EnvPosix["Env POSIX/Windows"]:::util
        Logging["Logging"]:::util
        Mutex["MutexLock"]:::util
        Status["Status Handling"]:::util
    end

    %% Environment / Platform Abstraction
    subgraph "Environment Abstraction"
        direction TB
        Port["port::Env Interface"]:::env
        PortPlat["Platform Glue"]:::env
        MemEnv["memenv (In-Memory)"]:::env
    end

    %% Plugins & Dependencies
    subgraph "Plugins & Dependencies"
        direction TB
        Snappy["Snappy/Zstd Compression"]:::plugin
        Benchmark["Google Benchmark"]:::plugin
        GTest["GoogleTest"]:::plugin
    end

    %% Data Flows
    DBAPI -->|Put/Get/Delete/Snapshot| DBImpl
    DBImpl -->|write| WALWriter
    DBImpl -->|read/write| MemTable
    WALWriter --> WALReader
    MemTable -->|flush| Builder
    Builder --> SSTable
    SSTable --> VersionSet
    Compaction --> TableCacheCore
    TableCacheCore --> TableReader
    TableReader --> BlockBuilder
    BlockBuilder -->|filter| FilterBlock
    TableReader --> TwoLevelIter
    DBImpl -->|snapshot| VersionSet
    DBImpl -->|batch| WriteBatchInt
    DBImpl -->|compaction trigger| Compaction
    DBImpl -->|uses| Comparator
    DBImpl -->|uses| FilterPolicy
    TableReader -->|uses| Bloom
    BlockBuilder -->|uses| CRC
    SSTable -->|disk I/O| EnvDefault
    EnvDefault --> Port
    Port --> PortPlat
    MemEnv --> Port

    %% Click events for mappings
    click DBAPI "https://github.com/fengbeihong/leveldb/blob/main/include/leveldb/db.h"
    click Options "https://github.com/fengbeihong/leveldb/blob/main/include/leveldb/options.h"
    click Comparator "https://github.com/fengbeihong/leveldb/blob/main/include/leveldb/comparator.h"
    click FilterPolicy "https://github.com/fengbeihong/leveldb/blob/main/include/leveldb/filter_policy.h"
    click IteratorAPI "https://github.com/fengbeihong/leveldb/blob/main/include/leveldb/iterator.h"
    click WriteBatchAPI "https://github.com/fengbeihong/leveldb/blob/main/include/leveldb/write_batch.h"
    click TableAPI "https://github.com/fengbeihong/leveldb/blob/main/include/leveldb/table.h"
    click TableBuilderAPI "https://github.com/fengbeihong/leveldb/blob/main/include/leveldb/table_builder.h"

    click DBImpl "https://github.com/fengbeihong/leveldb/blob/main/db/db_impl.cc"
    click WALWriter "https://github.com/fengbeihong/leveldb/blob/main/db/log_writer.cc"
    click WALReader "https://github.com/fengbeihong/leveldb/blob/main/db/log_reader.cc"
    click MemTable "https://github.com/fengbeihong/leveldb/blob/main/db/memtable.cc"
    click VersionSet "https://github.com/fengbeihong/leveldb/blob/main/db/version_set.cc"
    click Builder "https://github.com/fengbeihong/leveldb/blob/main/db/builder.cc"
    click TableCacheCore "https://github.com/fengbeihong/leveldb/blob/main/db/table_cache.cc"
    click WriteBatchInt "https://github.com/fengbeihong/leveldb/blob/main/db/write_batch.cc"

    click TableReader "https://github.com/fengbeihong/leveldb/blob/main/table/table.cc"
    click BlockBuilder "https://github.com/fengbeihong/leveldb/blob/main/table/block_builder.cc"
    click FilterBlock "https://github.com/fengbeihong/leveldb/blob/main/table/filter_block.cc"
    click TwoLevelIter "https://github.com/fengbeihong/leveldb/blob/main/table/two_level_iterator.cc"
    click Format "https://github.com/fengbeihong/leveldb/blob/main/table/format.cc"

    click Cache "https://github.com/fengbeihong/leveldb/blob/main/util/cache.cc"
    click Arena "https://github.com/fengbeihong/leveldb/blob/main/util/arena.cc"
    click Bloom "https://github.com/fengbeihong/leveldb/blob/main/util/bloom.cc"
    click CRC "https://github.com/fengbeihong/leveldb/blob/main/util/crc32c.cc"
    click EnvDefault "https://github.com/fengbeihong/leveldb/blob/main/util/env.cc"
    click EnvPosix "https://github.com/fengbeihong/leveldb/blob/main/util/env_posix.cc"
    click Logging "https://github.com/fengbeihong/leveldb/blob/main/util/logging.cc"
    click Mutex "https://github.com/fengbeihong/leveldb/blob/main/util/mutexlock.h"
    click Status "https://github.com/fengbeihong/leveldb/blob/main/util/status.cc"

    click Port "https://github.com/fengbeihong/leveldb/blob/main/port/port.h"
    click PortPlat "https://github.com/fengbeihong/leveldb/blob/main/port/port_posix.h"
    click MemEnv "https://github.com/fengbeihong/leveldb/blob/main/helpers/memenv/memenv.cc"

    click Benchmark "https://github.com/fengbeihong/leveldb/tree/main/third_party/benchmark"
    click GTest "https://github.com/fengbeihong/leveldb/tree/main/third_party/googletest"

    %% Styles
    classDef frontend fill:#D0E6FF,stroke:#0366D6,color:#0366D6;
    classDef core fill:#FFEFD5,stroke:#FF8C00,color:#FF8C00;
    classDef storage fill:#E6FFE6,stroke:#2E8B57,color:#2E8B57;
    classDef util fill:#F5E6FF,stroke:#8A2BE2,color:#8A2BE2;
    classDef env fill:#FFF5E6,stroke:#DAA520,color:#DAA520;
    classDef plugin fill:#FFE6E6,stroke:#DC143C,color:#DC143C;
    classDef disk fill:#FFFACD,stroke:#B8860B,color:#B8860B,shape:cylinder;
```
