⚡ Kira KV Engine

KV-storage engine based on Minimal perfect hash functions with hybrid indexing (+PGM Index) for Rust.
Zero collisions. Pure O(1) performance.

🧠 Algorithm

Built on the BDZ algorithm using 3-hypergraph peeling:

• Maps exactly n keys to n unique indices
• Uses hypergraph construction with 3 vertices per key
• Peels vertices of degree 1 iteratively until fully resolved
• Falls back to rehashing with different salts if cycles occur

📖 Research: Simple and Space-Efficient Minimal Perfect Hash Functions (Botelho, Pagh, Ziviani, 2007)

For numeric data, we layer in PGM (Piecewise Geometric Model) indexing:

• Learns linear segments to approximate key distributions
• Provides O(log log n) worst-case with O(1) average lookups
• Excellent for sorted integer sequences with predictable patterns

📖 Research: The PGM-index: a fully-dynamic compressed learned index (Ferragina, Vinciguerra, 2020)

🚀 Quick Start

use kira_kv_engine::Builder;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Build perfect hash for string keys
    let keys = ["rust", "zig", "go", "swift", "kotlin"];
    let mph = Builder::new().build(keys.iter().map(|s| s.as_bytes()))?;
    
    // O(1) lookups, guaranteed unique indices
    for key in &keys {
        println!("{} → {}", key, mph.index(key.as_bytes()));
    }
    
    Ok(())
}

🎯 Hybrid Indexing

For mixed workloads, use the hybrid index that automatically partitions keys:

use kira_kv_engine::HybridBuilder;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mixed_keys = vec![
        1000u64.to_le_bytes().to_vec(),  // numeric key
        2000u64.to_le_bytes().to_vec(),  // numeric key  
        b"user:123".to_vec(),            // string key
        b"session:abc".to_vec(),         // string key
    ];
    
    let hybrid = HybridBuilder::new().build(mixed_keys)?;
    
    // Query by original key format
    println!("Numeric: {}", hybrid.index_u64(1000)?);
    println!("String: {}", hybrid.index_str("user:123")?);
    
    // Range queries for numeric keys
    let range_results = hybrid.range_u64(1000, 3000);
    println!("Range [1000,3000]: {:?}", range_results);
    
    Ok(())
}

📊 Performance Comparison *

Performance benchmarks on 1M keys (Intel Core i7-12700, Windows 11):

* our benchmarks

🏆 Performance Highlights *

Build Speed:

• Kira Hybrid: 5.3× faster than Redis, 8.6× faster than LevelDB
• Kira MPH: Competitive with HashMap, 2.1× faster than Redis

Lookup Speed:

• Kira Hybrid: 6.9× faster than Redis, 9.6× faster than LevelDB
• Kira MPH: 3.8× faster than Redis, 5.3× faster than LevelDB

Memory Efficiency:

• Kira: 18-50× smaller than traditional databases
• Kira: 19-24× smaller than HashMap/concurrent structures
• Zero fragmentation - exact memory requirements known

* our benchmarks

⚡ Speed Comparison Matrix *

* our benchmarks

🧪 Benchmarks

Run comprehensive benchmarks across algorithms:

cargo run --example million_build --release

Expected output on modern hardware:

=== kira_kv_engine :: Hybrid MPH+PGM Benchmark ===
🔥 TRADITIONAL MPH BENCHMARK
build:     0.977 s   (1.0 M keys/s)
lookup:    0.047 s   (21.4 M lookups/s)
Memory: 5.0 bytes/key, 24x compression vs HashMap

🚀 HYBRID MPH+PGM BENCHMARK  
build:     0.395 s   (2.5 M keys/s)
lookup:    0.026 s   (37.9 M lookups/s)

📊 PGM-ONLY BENCHMARK
build:     0.016 s   (62.7 M keys/s)
lookup:    0.022 s   (45.5 M lookups/s)
range:     0.781 s   (1,281 queries/s)

⚙️ Features

Enable optional optimizations:

[dependencies]

kira_kv_engine = { version = "0.1", features = ["serde", "parallel", "pgm", "simd"] }

• serde — Serialization support for persistence
• parallel — Multi-threaded construction via rayon
• pgm — Learned indexing for numeric keys
• simd — Vectorized operations where available

🎛️ Configuration

Fine-tune for your workload:

use kira_kv_engine::{Builder, BuildConfig};
/// MPH Only (for strings as a key)
let mph = Builder::new()
    .with_config(BuildConfig {
        gamma: 1.25,           // Lower = denser graph, more retries
        rehash_limit: 16,      // Max attempts before giving up
        salt: 0xDEADBEEF,     // Custom base salt
    })
    .build(keys)?;

📊 When to Use

Perfect for:

• Fixed datasets (config files, catalogs, dictionaries)
• Memory-constrained environments
• Predictable O(1) lookup requirements
• Cold start optimization (mmap friendly)
• High-performance lookups in hot paths

Not suitable for:

• Frequently changing key sets
• Unknown dataset sizes
• Write-heavy workloads

🚀 Performance Tips

• Use gamma ≈ 1.25 for datasets > 10M keys
• Enable parallel feature for build-time speedup
• Serialize indices to disk for instant cold starts
• Consider hybrid indexing for mixed numeric/string data

🎯 Real-World Use Cases *

Web Servers:

• Route matching: 6.9× faster than Redis lookups
• Session lookup: 37.9M operations/sec vs Redis 5.6M

Databases:

• Index structures: 29× less memory than LevelDB
• Cache lookups: Zero allocation after build

Gaming:

• Asset ID lookup: 21.4M lookups/sec
• Player data: Instant cold start from disk
  
  * provided with our performance benchmarks

📚 References

• BDZ Algorithm: Botelho, D., Pagh, R., Ziviani, N. (2007). Simple and Space-Efficient Minimal Perfect Hash Functions. WADS 2007
• PGM Index: Ferragina, P., Vinciguerra, G. (2020). The PGM-index: a fully-dynamic compressed learned index. VLDB 2020
• Learned Indexes: Kraska, T. et al. (2018). The Case for Learned Index Structures. SIGMOD 2018
• 3-Hypergraph Peeling: Peeling Random Planar Maps - Theoretical foundations