nori-sstable

Immutable sorted string tables with blocks, index, bloom filters, and compression.

Get Started API Reference View on GitHub

---

---

What is nori-sstable?

nori-sstable provides a production-ready implementation of SSTables (Sorted String Tables) for building LSM-tree storage engines. SSTables are immutable, on-disk data structures that store sorted key-value pairs with efficient lookups and range scans.

This crate is a core building block of the NoriKV distributed key-value store, but can be used standalone in any Rust project that needs persistent sorted storage.

---

Key Features

Storage & Format

• Block-based storage: 4KB blocks with prefix compression for space efficiency
• Two-level index: Sparse block index for fast key lookups with minimal I/O
• Bloom filters: Probabilistic membership testing (~0.9% false positive rate) to avoid unnecessary disk reads
• CRC32C checksums: Data integrity validation at block level

Performance & Optimization

• Block compression: Optional LZ4 (fast, 3.9 GB/s decompress) or Zstd (higher ratio) compression 🆕
• LRU block cache: Configurable in-memory cache for hot data blocks (default 64MB) 🆕
• Async I/O: Built on Tokio for high-performance asynchronous operations
• ~67ns bloom filter checks: Ultra-fast negative lookups

Developer Experience

• Tombstones: Explicit delete markers preserved through the storage layer
• Observability: Vendor-neutral metrics via nori-observe::Meter trait
• Thread-safe: Concurrent reads supported via Arc<SSTableReader>
• 100% Safe Rust: No unsafe code in the public API
• 108 tests passing: Comprehensive test suite including compression and property tests

{: .new }

Recent Updates: nori-sstable now includes production-ready LZ4/Zstd compression and an LRU block cache that delivers 18x performance improvements for hot key workloads!

---

Quick Example

use nori_sstable::{Compression, Entry, SSTableBuilder, SSTableConfig, SSTableReader};
use std::path::PathBuf;
use std::sync::Arc;

#[tokio::main]
async fn main() -> nori_sstable::Result<()> {
    // Build an SSTable with LZ4 compression
    let config = SSTableConfig {
        path: PathBuf::from("data.sst"),
        estimated_entries: 1000,
        compression: Compression::Lz4,  // Enable compression
        block_cache_mb: 64,              // 64MB cache (default)
        ..Default::default()
    };

    let mut builder = SSTableBuilder::new(config).await?;

    // Add entries in sorted order
    builder.add(&Entry::put("key1", "value1")).await?;
    builder.add(&Entry::put("key2", "value2")).await?;
    builder.add(&Entry::delete("key3")).await?; // Tombstone

    let metadata = builder.finish().await?;
    println!("Created SSTable with {} entries", metadata.entry_count);

    // Read data back
    let reader = Arc::new(SSTableReader::open(PathBuf::from("data.sst")).await?);

    // Point lookup (uses bloom filter + index + cache)
    if let Some(entry) = reader.get(b"key1").await? {
        println!("Found: {:?}", String::from_utf8_lossy(&entry.value));
    }

    // Range scan
    let mut iter = reader.iter();
    while let Some(entry) = iter.try_next().await? {
        println!("{:?} = {:?}", entry.key, entry.value);
    }

    Ok(())
}

---

Performance Highlights

Benchmarked on Apple M1 (release build):

Operation	Performance	Notes
Bloom filter check	~67ns	In-memory, ultra-fast
Point lookup (hit)	~5µs	With cache enabled
Point lookup (miss)	<20µs	Bloom filter skip
Sequential scan	~1M entries/sec	Streaming iteration
Hot key workload	18x faster (14ms → 777µs)	With 64MB cache
Compression ratio (LZ4)	2-3x typical	14x on highly compressible data

See detailed benchmarks →

---

Architecture Overview

┌─────────────────────────────────────────────────────────────┐
│                        Write Path                            │
│  User → SSTableBuilder → BlockBuilder → Compress → Writer   │
│           │                  │              │          │     │
│           ├─ BloomFilter     ├─ Prefix      │          └─ File I/O
│           │  (add keys)      │   Compression│                │
│           │                  │   (shared len)                │
│           └─ Index           └─ Restart                      │
│              (track blocks)     Points                       │
└─────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────┐
│                         Read Path                            │
│  User → SSTableReader → [Cache?] → [Bloom?] → Index → Block │
│                             ↓          ↓         ↓        ↓  │
│                          Hit/Miss  Contains?  Find    Binary │
│                          (~18x)    (~67ns)    Block   Search │
│                                                (log B)  (log E)│
│         SSTableIterator → load blocks on demand              │
│                            ↓                                 │
│                         BlockIterator                        │
│                          (decompress + decode)               │
└─────────────────────────────────────────────────────────────┘

File Layout

┌────────────────┐
│ Data Block 0   │ ← 4KB blocks (compressed with LZ4/Zstd)
├────────────────┤
│ Data Block 1   │   Entry: shared_len | unshared_len |
├────────────────┤          value_len | key | value
│     ...        │
├────────────────┤   Restart points every 16 entries
│ Data Block N   │
├────────────────┤
│ Index          │ first_key | block_offset | block_size (per block)
├────────────────┤
│ Bloom Filter   │ xxhash64 with double hashing
├────────────────┤ 10 bits/key → ~0.9% FP rate
│ Footer (64B)   │ Magic | Index offset/size | Bloom offset/size |
└────────────────┘ Compression type | CRC32C checksum

Learn more about the architecture →

---

When to Use nori-sstable

Great Fit

• Building LSM-tree storage engines (like RocksDB, LevelDB)
• Time-series databases with immutable time-ordered data
• Log storage with sorted logs and range queries
• Snapshot storage for point-in-time database snapshots
• Need fast reads with bloom filter optimization
• Hot key workloads where caching provides 10x+ speedups
• Workloads where compression saves significant storage costs

Not the Right Tool

• Need mutable data structures (use in-memory B-trees instead)
• Random writes (SSTables are write-once, immutable)
• Ultra-low latency < 1µs (use in-memory stores)
• Very small datasets < 1MB (overhead not worth it)

---

Documentation Sections

Getting Started

Learn how to install and use nori-sstable in your project.

Getting Started →

Core Concepts

Understand the fundamental concepts behind SSTables: immutability, block-based storage, bloom filters, and when to use them.

Core Concepts →

Compression 🆕

Deep dive into LZ4 and Zstd compression: when to use each, performance tradeoffs, and configuration.

Compression Guide →

Caching 🆕

Learn how the LRU block cache works, how to tune it for hot workloads, and achieve 18x speedups.

Caching Guide →

How It Works

Detailed internals: file format, block format, bloom filters, index structure, compression, and cache implementation.

How It Works →

API Reference

Complete API documentation for builders, readers, configuration, and iterators.

API Reference →

Performance

Benchmarks, tuning guides, compression ratio analysis, and profiling.

Performance →

Design Decisions

Rationale behind key design choices: block-based organization, immutability, compression strategy, and more.

Design Decisions →

Recipes

Common patterns and use cases with code examples.

Recipes →

Internals

Deep implementation details for contributors and advanced users.

Internals →

---

Installation

Add to your Cargo.toml:

[dependencies]
nori-sstable = "0.1"
tokio = { version = "1", features = ["full"] }

Then import in your code:

use nori_sstable::{
    SSTableBuilder, SSTableReader, SSTableConfig,
    Entry, Compression,
};

---

Project Status

Aspect	Status
Core functionality	Production-ready
Tests	108 tests passing
Compression	LZ4 + Zstd supported
Caching	LRU cache implemented
Documentation	Complete
Benchmarks	Comprehensive
Published	🚧 Preparing for crates.io

---

Contributing

nori-sstable is part of the NoriKV project and welcomes contributions!

• Found a bug? Open an issue
• Have a question? Start a discussion
• Want to contribute? Check the Contributing Guide

---

License

MIT License - see LICENSE for details.

---

Next Steps

New to SSTables? Start with Getting Started to build your first SSTable in 5 minutes.

Want to optimize performance? Check out Compression and Caching to learn about our newest performance features.

Need the API? Jump to API Reference for complete method documentation.

Curious about internals? Dive into How It Works for implementation details.