LevelDB: BitWeaving Range Scan Optimization

An architectural modification to Google's LevelDB storage engine, implementing intra-file BitWeaving (Order-Preserving Bit-Slicing) to drastically reduce disk I/O during value-based range scans.

---

🚀 Project Overview

The Problem: Inefficient Value Scans in LSM-Trees Standard LSM-trees natively sort data by key. This makes value-based range scans (e.g., SELECT * WHERE value > 800) highly inefficient, as it forces the engine into severe read amplification—requiring it to read, decompress, and deserialize every single block in the queried range just to evaluate the predicate.

The Solution: Embedded BitWeaving Filters This project modifies the LevelDB core engine to generate and store 32-bit dynamic bitmasks, combined with Hybrid ZoneMaps (Min/Max), for every 64-record cache-aligned data block.

During a range scan, the engine evaluates these bitmasks in memory. If the filter determines a block cannot satisfy the query predicate, the engine safely bypasses the disk I/O entirely for that block.

Key Achievements

• Up to 89.38% reduction in disk I/O for high-selectivity queries.
• Up to 10.19x latency speedup on read-heavy workloads.
• < 0.1% space overhead, maintaining a highly optimized storage footprint proven at a scale of 500 million records.

---

💡 Target Use Cases

While standard LevelDB excels at point-lookups (key-value retrieval), our BitWeaving integration transforms it into a highly efficient engine for analytical and time-series workloads. This unlocks massive performance gains in the following scenarios:

1. Financial Market Data & Algorithmic Backtesting

High-frequency trading platforms frequently utilize LevelDB as an ultra-fast local cache for order book events and price ticks (where the key is the timestamp and the value contains the trade metrics). When quantitative analysts run backtests, they often execute highly selective value-based queries—such as searching for liquidity spikes (WHERE trade_volume > 50000) within a specific historical window. Standard LevelDB forces the system to decompress and read every single market tick in that time frame. BitWeaving instantly filters out the "normal" trading blocks, drastically accelerating backtest execution and allowing quants to iterate on financial models much faster.

2. High-Throughput Infrastructure Monitoring (Anomaly Detection)

In cloud infrastructure environments, distributed systems generate massive volumes of diagnostic logs (network latency, CPU utilization, disk I/O throughput). When Site Reliability Engineers (SREs) query these logs to detect SLO violations (e.g., SELECT * WHERE latency > 500ms), the vast majority of the data is "normal" and irrelevant to the query. BitWeaving's highly selective O(1) filtering allows the storage engine to instantly skip the normal logs, reducing read amplification and speeding up root-cause analysis by an order of magnitude.

---

📍 Code Map: What We Added

Per the project requirements, our modifications successfully hijacked the read/write paths without altering LevelDB's public API. Our implementation is concentrated in the following files:

1. The Core Logic Engine

• util/bitweave.h: We built a header-only mathematical engine containing BitWeaveBuilder and BitWeaveReader. It utilizes a Hybrid ZoneMap approach, dynamically dividing the local range of a 64-record block into 32 equal bands to generate highly precise bitmasks.

• The 12-Byte Binary Signature: For every 64-record data block, we generate a highly compact metadata payload. This incurs an incredibly lightweight ~0.29% storage overhead.

struct BitWeaveTag {
    uint32_t block_min;  // 4 Bytes: Local ZoneMap Minimum
    uint32_t block_max;  // 4 Bytes: Local ZoneMap Maximum
    uint32_t bitmask;    // 4 Bytes: 32-Band Distribution Mask
}; 

• Dynamic Bitmasking Algorithm: Instead of global SSTable boundaries, we calculate boundaries dynamically for each physical block. A value v is assigned to one of 32 bands using the formula: band = floor(((v - min) * 32) / (max - min + 1))

2. The Write Path (Compaction)

• table/table_builder.cc: Intercepted the TableBuilder::Add() function to parse string slices into integers. When TableBuilder::Flush() completes a physical data block, our logic commits the corresponding 12-byte BitWeaveTag. During TableBuilder::Finish(), our logic bundles the generated bitmasks into a 12-byte payload and writes it to disk as a custom bitweave.leveldb.BWH Meta-Index block, resting alongside standard Bloom filters.

3. The Read Path (Query Filtering)

• table/table.cc:
  • Modified Table::Open to load the BitWeaving metadata into an in-memory std::unordered_map for O(1) index lookups. This translates physical disk offsets into our BitWeaving tags, enabling lightning-fast access during reads.
  • Intercepted Table::BlockReader (the final step before Disk/Cache I/O). If our BitWeaving filter returns false for a block, we immediately return NewEmptyIterator(), completely avoiding decompression and disk access.

4. The Evaluation Framework

• bitweave_*.cc: We initially considered evaluating our BitWeaving implementation using standard frameworks like YCSB Workload E or LevelDB's native db_bench. However, these industry-standard tools treat the storage engine as a black box, measuring only top-level latency and throughput. Because BitWeaving's primary contribution is avoiding disk I/O at the block level, we constructed a native C++ benchmarking suite that mirrors the read-heavy access patterns of YCSB Workload E, while instrumenting the internal engine to accurately report cache utilization, block-skipping rates, and metadata storage overhead."

---

🛠 Verification & Benchmarking

To verify the implementation, we have provided a comprehensive native benchmarking suite.

1. Build the Engine

mkdir -p build && cd build
cmake ..
make -j$(nproc)

2. Verify Mathematical Correctness

Runs unit tests to guarantee 0% false negatives in the bitmask logic, and a 10,000-record integration test to verify the TableReader hook.

./bitweave_test

3. Run the Evaluation Suite

We built three distinct benchmark binaries to stress-test different system limits:

• Micro-Benchmarks (Distributions): Tests the bitmask resolution against Uniform, Skewed, and Bimodal data distributions to measure worst-case vs. best-case selectivity.

  ./bitweave_benchmark

• Real-World Simulation: Runs the engine against simulated IoT temperature anomalies, network logs, and CPU spikes to measure latency speedups in production-like environments.

  ./bitweave_realworld

• Macro-Benchmarks (Scalability): Writes between 1 Million and 500 Million records to disk to verify that the 12-byte metadata payload does not bloat the storage engine footprint.

  ./bitweave_largescale

Note: Raw execution logs from our evaluation have been exported and saved in the benchmark_results/ directory at the root of this repository for immediate review.

---

📊 Performance & Key Achievements

Figure 1: Comprehensive evaluation across micro-benchmarks, real-world workloads, and scalability stress-tests.

• Up to 89.38% reduction in disk I/O: Verified during High Disk I/O anomaly detection queries where BitWeaving effectively skipped non-matching blocks, resulting in a significant decrease in disk reads.This was particularly evident in scenarios with high selectivity, where the majority of blocks were irrelevant to the query predicate. The reduction in disk I/O directly contributed to faster query execution times and improved overall system performance.
• Up to 10.19x latency speedup: Demonstrated in real-world scenarios, reducing scan times from 6.77 ms to 0.66 ms. This speedup is attributed to the elimination of unnecessary disk access and the efficient in-memory evaluation of bitmasks, allowing the engine to quickly determine which blocks to read and which to skip. The latency improvement was most pronounced in cases where a large portion of the data was irrelevant to the query, showcasing the effectiveness of BitWeaving in optimizing value-based range scans.
• Highly optimized storage footprint: Proven at a scale of 500 million records, where metadata overhead remained typically < 1% of total data. The compact metadata payload for each data block ensures that the additional storage requirements do not significantly impact the overall storage efficiency of the engine, even at large scales.

---

👥 Team Members

• Aryan Parab
• Vikas Mishra
• Nishant Miyani

---

🎓 Academic Context

• Instructor: Prof. Ibrahim Sabek
• Course: CSCI 543: Foundations of Modern Data Management and Processing, University of Southern California

---

💻 Technical Stack

• Language: C++17
• Base Engine: Google LevelDB (v1.23.0)
• Build System: CMake, Make
• Environment: Linux / Docker Containerization