-
Notifications
You must be signed in to change notification settings - Fork 0
Home
Sergi edited this page Sep 28, 2026
·
5 revisions
Welcome to the log-compaction-optimiziation-lsm wiki!
Optimizing Log Compaction Strategies in LSM-Tree Engines The Challenge.
This project avoids high-level APIs and focuses on custom scheduling, priority.
Repository: log Compaction Optimiziation LSM
To prove deep systems capability, the project shouldn't just wrap RocksDB; it should implement a custom, decoupled, pluggable scheduler via its worker thread pool, or serve as a standalone minimal LSM-Engine written in Rust or C++.
[ Client Write Path ] [ Active I/O Metrics Telemetry ]
│ │
▼ ▼
┌────────────────────┐ ┌───────────────────┐
│ MemTable / WAL │ │ io_uring / eBPF │
└──────────┬─────────┘ └─────────┬─────────┘
│ (Flush) │
▼ ▼
┌────────────────────┐ ┌───────────────────┐
│ Level 0 SSTs │ │ Feedback Loop │
└────────────────────┘ └─────────┬─────────┘
│ │ (Throttling / Budget)
▼ ▼
┌────────────────────────────────────────────────────────────┐
│ Dynamic Compaction Scheduler │
│ - Size-Tiered vs Leveled Evaluator │
│ - Thread Pool Control & IOPS Token Bucket │
│ - Overlap Matrix / Priority Queue │
└──────────────────────────┬─────────────────────────────────┘
│
▼
┌────────────────────────┐
│ Parallel Compaction │
│ - Chunked Iterators │
└────────────────────────┘
A naive throttle uses a static rate-limiter (e.g., limit compaction to 50MB/s). A world-class engine self-throttles based on real-time query interference.
- The Mechanism: Use a lock-free ring buffer to track client read/write tail latencies (
$P_{99}$ and$P_{99.9}$ ). Alternatively, pull OS metrics using io_uring completion events or a minimal eBPF hook measuring block I/O device queues. - The Math: Implement a PID Controller (Proportional-Integral-Derivative) or a windowed Token Bucket algorithm where the bucket refilling speed drops inversely with the spike in foreground read latency.
- Portfolio Impact: Showcases understanding of OS-level scheduling, kernel telemetry, and control loop feedback structures.
Fixed compaction strategies force a trade-off: Size-Tiered Compaction Strategy (STCS) favors write-heavy workloads but kills space amplification; Leveled Compaction Strategy (LCS) minimizes read amplification but incurs brutal write amplification.
- The Mechanism: Create a compile-time abstraction layer (CompactionStrategy trait or virtual interface) allowing runtime swapping.
- The Optimization: Build a Workload-Adaptive Hybrid Strategy. If the scheduler detects a sudden burst of point/range lookups (high read amplification), it dynamically prioritizes Leveled compaction for lower levels. If it detects high-frequency sequential ingestion, it shifts to Size-Tiered grouping to stop the write path from stalling.
Determining exactly which SSTables to merge next heavily impacts the efficiency of the merge round.
- The Mechanism: Maintain an Interval Overlap Matrix of all active SSTables across adjacent levels. Design a multi-keyed Priority Queue (std::collections::BinaryHeap or custom heap) that ranks compaction candidates based on:
- Overlap Score: Minimizing the number of files touched in the target level to keep write amplification down.
- Tombstone Density: Prioritizing runs containing old tombstones to reclaim dead disk space rapidly.
- Size Ratio: Grouping files of uniform sizes to prevent out-of-order merging anomalies.
Streaming gigabytes of SSTables into memory during a merge will thrash the OS page cache and trigger massive memory allocations.
- The Mechanism: Build an N-Way Merge Iterator using a tournament tree or min-heap over chunked blocks.
- The Optimization: Use posix_fadvise (POSIX_FADV_DONTNEED) or custom io_uring read-registers to ensure pages read by the compaction background threads do not displace hot user data blocks out of the OS page cache.
| Component | Standard/Naive Approach | Your High-Throughput Approach | System Justification |
|---|---|---|---|
| I/O Throttling | Static throughput cap (X MB/s config). | Adaptive Feedback Loop via PID controller tracking |
Prevents background merges from stalling critical foreground user queries under high load. |
| Strategy Execution | Hardcoded compilation choice (e.g., Leveled only). | Dynamic Pluggable Scheduler Layer switching based on access patterns. | Switches between STCS (write-optimized) and LCS (read-optimized) metrics dynamically. |
| File Selection | Oldest-file-first or round-robin selection. | Heuristic Priority Queue tracking key-space overlap matrices & tombstone ratios. | Lowers overall Write Amplification Factor (WAF) by choosing the tightest key bounds. |
| Disk/OS Engine | Standard synchronous POSIX read/write APIs. | Asynchronous Vectorized I/O utilizing an io_uring thread loop. | Eliminates syscall context-switch overhead and enables clean zero-copy streaming. |
- Phase 1 (The Core Engine): A simple in-memory MemTable (SkipList) flushing immutable SSTables containing a simple [Index Block + Bloom Filter + Data Blocks] layout.
- Phase 2 (The Metric Watchdog): A separate thread tracking atomic throughput variables and transaction times from the write/read routes to continuously update a cluster health score.
- Phase 3 (The Scheduler & Token Engine): The heart of the project. A custom thread pool executing compaction tasks, consuming byte tokens generated by the Watchdog's feedback loop.
- Phase 4 (The Benchmarking Suite): Scripts driving mixed workloads (e.g., 80% write/20% read shifting instantly to 20% write/80% read) to visually map out how the scheduler throttles itself and keeps latency profiles stable.
- Phase 5 (The data store): To write a standalone custom minimal LSM engine, or build this as a pluggable architecture framework/plugin interacting with an existing database engine like RocksDB.