How fengbeihong/leveldb works
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