How richardktran/lsm-tree-go-my-way works
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.