# richardktran/lsm-tree-go-my-way architecture

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

- Interactive diagram: https://gitdiagram.com/richardktran/lsm-tree-go-my-way
- Repository: https://github.com/richardktran/lsm-tree-go-my-way

## Overview

This project is an implementation of a Log-Structured Merge Tree (LSM Tree) based key-value store in Golang. Its primary purpose is to provide a high-performance persistent key-value store by efficiently managing in-memory writes (via a MemTable) and periodically flushing them to disk (as immutable SSTables) while using a Write-Ahead Log (WAL) for durability.

##### Main Components
- Command Line Interface (CLI): Represented by the "cmd/cli" directory. This component acts as the entry point where users interact with the key-value store.
- Configuration Module: Found in "internal/config". This handles configurations and directory settings needed for running the application.
- Core Key-Value Store Layer: This is built upon several interconnected modules:
- MemTable (in "internal/memtable"): Acts as the in-memory component that temporarily aggregates write operations. Note that it supports multiple underlying algorithms (e.g., Sorted Array, Skip List) as seen in the "algorithm" subdirectory.
- Write-Ahead Log (WAL): Located under "internal/wal". This component logs incoming writes so that the system can recover in case of a failure.
- SSTable Module (in "internal/sstable"): Represents the on-disk immutable segment stores with sparse indexing. It explains how data is flushed from MemTable into sorted, block-based segments.
- Server Component: Present in "internal/server". Although not fully expanded in the README, this suggests that the application may support a server (or network interface) for remote clients.
- Supporting Constants & Utilities: The "internal/constant" and "internal/kv" directories contain key definitions and helper functions related to key-value records (including tests).

##### Relationships and Interactions
- Data Flow:
- The CLI (or possibly a server interface) receives user commands.
- Commands are parsed and passed to the core key-value store layer.
- Write operations first hit the MemTable and are simultaneously recorded in the WAL.
- On reaching a threshold or based on a flush trigger, the MemTable’s sorted data is flushed to an SSTable on disk, with a Sparse Index built from block offsets.
- Read operations may query the MemTable first and then search the set of immutable SSTables using their Sparse Indexes. The lookup process involves finding the correct block in an SSTable and scanning from the offset.
- Interaction:
- The WAL supports durability by allowing the MemTable to be rebuilt on recovery.
- The configuration module supplies runtime parameters to various components (e.g., file paths, block sizes).
- The Store module abstracts the strategies for data storage (memory vs. LSM-driven persistent storage).

##### Architectural Patterns and Design Principles
- Layered Architecture: Separation between CLI, configuration, core store logic, and low-level storage mechanisms.
- Write Optimization via Buffering: Use of MemTable and WAL to batch writes.
- Immutable Data Structures: Once data is flushed to disk as an SSTable, it remains unchanged (immutable) which simplifies concurrency and consistency.
- Pluggable Algorithms: The MemTable supports different underlying algorithms (Sorted Array, Skip List) providing flexibility and testability.

##### Relevant Technologies, Frameworks, or Libraries
- Golang as the programming language.
- Testing frameworks inherent to Golang (e.g., "go test" with race condition detection).
- The overall design is inspired by NoSQL systems like those found in LevelDB, RocksDB, etc.

##### Elements
- Clear labels for each component (e.g., CLI, Config, MemTable, WAL, SSTable, Store/LSM Tree, Server).
- Command input → CLI/Server → Store Layer.
- Write operations: Store → MemTable (and concurrently WAL).
- Flush process: MemTable → SSTable, with Sparse Index creation.
- Read operations: Query both MemTable and SSTable components.
- User-interface components (CLI and Server).
- In-memory components (MemTable, WAL).
- Persistent storage components (SSTable, Sparse Index).
- Utility/configuration components (Config, constants).
- Optionally, note internal testing mechanisms where relevant.

## Diagram (Mermaid)

```mermaid
graph TB
    %% User Interface Components
    subgraph "User Interface"
        CLI["\"CLI\""]:::ui
        SERVER["\"Server\""]:::ui
    end

    %% Core Key-Value Store with Store Implementations
    subgraph "Core Key-Value Store"
        subgraph "Store Implementations"
            LSM["\"LSM Tree Store\""]:::store
            MEMORY["\"Memory Store\""]:::store
        end
        %% LSM Tree internal components
        LSM -->|"\"writes_to\""| MT["\"MemTable\""]:::memory
        LSM -->|"\"writes_to\""| WAL["\"Write-Ahead Log\""]:::memory
        LSM -->|"\"flushes_to\""| SST["\"SSTable Module\""]:::disk
        LSM -->|"\"reads_from\""| MT
        LSM -->|"\"reads_from\""| SST
    end

    %% MemTable Algorithms as a support node for MemTable
    MT -->|"\"uses_algorithms\""| MTALGOS["\"MemTable Algorithms\""]:::memory

    %% Supporting Modules
    subgraph "Supporting Modules"
        CONFIG["\"Configuration Module\""]:::config
        CONSTANTS["\"Constants\""]:::utility
        KV["\"Key-Value Utilities\""]:::utility
    end

    %% Data Flow from UI to Core Store
    CLI -->|"\"sends_command\""| LSM
    SERVER -->|"\"sends_remote_command\""| LSM

    %% Configuration feeds into core modules
    CONFIG -->|"\"configures\""| LSM
    CONFIG -->|"\"configures\""| MT
    CONFIG -->|"\"configures\""| SST

    %% Supporting utilities used by the store
    CONSTANTS -->|"\"supports\""| LSM
    KV -->|"\"supports\""| LSM

    %% Class Definitions for colors
    classDef ui fill:#F9E79F,stroke:#F39C12,stroke-width:2px;
    classDef store fill:#AED6F1,stroke:#3498DB,stroke-width:2px;
    classDef memory fill:#A9DFBF,stroke:#27AE60,stroke-width:2px;
    classDef disk fill:#FADBD8,stroke:#E74C3C,stroke-width:2px;
    classDef config fill:#D2B4DE,stroke:#8E44AD,stroke-width:2px;
    classDef utility fill:#F0B27A,stroke:#D35400,stroke-width:2px;

    %% Click Events for Components
    click CLI "https://github.com/richardktran/lsm-tree-go-my-way/blob/main/cmd/cli/main.go"
    click CONFIG "https://github.com/richardktran/lsm-tree-go-my-way/tree/main/internal/config"
    click MT "https://github.com/richardktran/lsm-tree-go-my-way/blob/main/internal/memtable/memtable.go"
    click MTALGOS "https://github.com/richardktran/lsm-tree-go-my-way/tree/main/internal/memtable/algorithm"
    click WAL "https://github.com/richardktran/lsm-tree-go-my-way/blob/main/internal/wal/wal.go"
    click SST "https://github.com/richardktran/lsm-tree-go-my-way/tree/main/internal/sstable"
    click LSM "https://github.com/richardktran/lsm-tree-go-my-way/blob/main/internal/store/lsmtree/store.go"
    click MEMORY "https://github.com/richardktran/lsm-tree-go-my-way/blob/main/internal/store/memory/store.go"
    click SERVER "https://github.com/richardktran/lsm-tree-go-my-way/blob/main/internal/server/server.go"
    click CONSTANTS "https://github.com/richardktran/lsm-tree-go-my-way/blob/main/internal/constant/command.go"
    click KV "https://github.com/richardktran/lsm-tree-go-my-way/tree/main/internal/kv"
```
