Struct BlockCache 

pub struct BlockCache { /* private fields */ }

Sharded LRU cache for decompressed snapshot blocks.

Architectural intent: Reduces repeated decompression and backend reads by caching hot blocks in memory, while sharding to minimize lock contention under concurrent access.

Constraints: For capacity > SHARD_COUNT, total capacity is divided evenly across shards. For 0 < capacity <= SHARD_COUNT, a single shard is used so global LRU semantics and exact capacity are preserved.

Side effects: Uses per-shard Mutexes, so high write or miss rates can introduce contention; memory usage grows with the number and size of cached blocks up to the configured capacity.

Implementations

impl BlockCache

pub fn with_capacity(capacity: usize) -> Self

Constructs a new block cache with a specified capacity in entries.

The capacity represents the total number of blocks (not bytes) that can be cached. Memory usage is approximately capacity × (block_size + 96 bytes).

Arguments

• capacity - Maximum number of blocks to cache. Must be ≥ 0.
  • 0: Disables caching (all operations become no-ops)
  • 1-256: Uses single shard (exact LRU, lower concurrency)
  • >256: Uses 16 shards (approximate LRU, higher concurrency)

Shard Allocation

• capacity = 0: No shards allocated, cache is effectively disabled
• capacity ≤ 256: Allocates 1 shard with exact capacity (global LRU)
• capacity > 256: Allocates 16 shards with ceil(capacity / 16) entries each (total capacity may be slightly higher than requested due to rounding)

Memory Allocation

This function performs upfront allocation of:

• Shard metadata: 16 × 128 bytes ≈ 2 KB (for multi-shard mode)
• LRU structures: ~8 bytes per entry for internal pointers
• Total upfront: ~2 KB + (capacity × 8 bytes)

Block data is allocated lazily as entries are inserted.

Performance

• Time complexity: O(num_shards) ≈ O(1) (at most 16 shards)
• Space complexity: O(num_shards + capacity)
• No I/O: Purely in-memory allocation

Examples

Default Configuration

use hexz_core::cache::lru::BlockCache;

// Typical server: 1000 blocks × 64 KiB = 64 MB cache
let cache = BlockCache::with_capacity(1000);

Memory-Constrained System

use hexz_core::cache::lru::BlockCache;

// Embedded device: 16 MiB budget, 64 KiB blocks → 256 entries
let budget_mb = 16;
let block_size_kb = 64;
let capacity = (budget_mb * 1024) / block_size_kb;
let cache = BlockCache::with_capacity(capacity);

// Uses single shard (capacity = 256 ≤ threshold)

High-Capacity System

use hexz_core::cache::lru::BlockCache;

// Server: 8 GB budget, 64 KiB blocks → 131072 entries
let budget_gb = 8;
let block_size_kb = 64;
let capacity = (budget_gb * 1024 * 1024) / block_size_kb;
let cache = BlockCache::with_capacity(capacity);

// Uses 16 shards (capacity = 131072 > 256)
// Each shard holds ceil(131072 / 16) = 8192 entries

Disabled Cache

use hexz_core::cache::lru::BlockCache;

// Disable caching (useful for testing or streaming workloads)
let cache = BlockCache::with_capacity(0);

// All get() calls return None, insert() calls are ignored

Tuning Notes

Choosing the right capacity involves balancing:

• Memory availability: Don’t exceed physical RAM or risk OOM
• Hit rate goals: Larger cache → higher hit rate (diminishing returns)
• Workload characteristics: Sequential vs. random, hot set size

Rule of thumb:

capacity = (available_memory × utilization_factor) / block_size

where utilization_factor:
  0.1-0.2 = Conservative (memory-constrained)
  0.3-0.5 = Moderate (balanced)
  0.5-0.8 = Aggressive (performance-critical)

pub fn get(&self, stream: SnapshotStream, block: u64) -> Option<Bytes>

Retrieves a decompressed block from the cache, if present.

This is the fast-path for read operations: if the requested block is cached, it is returned immediately without backend I/O or decompression. On a cache hit, the block is also marked as “most recently used” in the shard’s LRU list, reducing its likelihood of eviction.

Arguments

• stream - The snapshot stream (Disk or Memory) containing the block
• block - Zero-based block index within the stream

Returns

• Some(Bytes): The cached decompressed block data (cache hit)
• None: The block is not cached or cache is disabled (cache miss)

Cache Hit Behavior

On a cache hit:

1. Acquires the shard’s mutex (blocks if another thread holds it)
2. Looks up the key in the shard’s LRU map
3. Moves the entry to the head of the LRU list (marks as most recent)
4. Clones the Bytes handle (cheap: ref-counted, no data copy)
5. Releases the mutex

Cache Miss Behavior

On a cache miss, the caller is responsible for:

1. Fetching the block from the storage backend
2. Decompressing the block data
3. Inserting the decompressed data via insert()

Performance

Cache Hit

• Time complexity: O(1) (hash lookup + LRU update)
• Typical latency:
  • Uncontended: 50-150 ns (mutex + map lookup + Bytes clone)
  • Contended: 100-500 ns (mutex wait time)
• Allocation: None (Bytes is ref-counted, no data copy)

Cache Miss

• Time complexity: O(1) (hash lookup)
• Typical latency: 30-80 ns (mutex + map lookup)

Thread Safety

This method is thread-safe and can be called concurrently from multiple threads. Sharding reduces contention: up to SHARD_COUNT threads can access different shards in parallel without blocking each other.

Errors

This method returns None on:

• Cache miss: Key not found in the shard
• Cache disabled: capacity = 0 (no shards allocated)
• Mutex poisoning: If another thread panicked while holding the mutex (extremely rare; indicates a bug in cache implementation)

Examples

Typical Usage

use hexz_core::cache::lru::BlockCache;
use hexz_core::api::file::SnapshotStream;
use bytes::Bytes;

let cache = BlockCache::with_capacity(1000);

// Insert a block
let data = Bytes::from(vec![1, 2, 3, 4]);
cache.insert(SnapshotStream::Disk, 42, data.clone());

// Retrieve it (cache hit)
let cached = cache.get(SnapshotStream::Disk, 42);
assert_eq!(cached, Some(data));

// Different block (cache miss)
let missing = cache.get(SnapshotStream::Disk, 99);
assert_eq!(missing, None);

Stream Isolation

let cache = BlockCache::with_capacity(1000);

// Same block index, different streams
let disk_data = Bytes::from(vec![1, 2, 3]);
let mem_data = Bytes::from(vec![4, 5, 6]);

cache.insert(SnapshotStream::Disk, 10, disk_data.clone());
cache.insert(SnapshotStream::Memory, 10, mem_data.clone());

// Lookups are stream-specific (no collision)
assert_eq!(cache.get(SnapshotStream::Disk, 10), Some(disk_data));
assert_eq!(cache.get(SnapshotStream::Memory, 10), Some(mem_data));

Disabled Cache

let cache = BlockCache::with_capacity(0);

// All lookups return None (cache disabled)
assert_eq!(cache.get(SnapshotStream::Disk, 0), None);

pub fn insert(&self, stream: SnapshotStream, block: u64, data: Bytes)

Inserts or updates a decompressed block in the cache.

This method stores decompressed block data in the cache for future fast-path retrieval. If the block already exists, its data is updated and it is moved to the head of the LRU list (most recent). If the shard is full, the least-recently used entry in that shard is evicted to make room.

Arguments

• stream - The snapshot stream (Disk or Memory) containing the block
• block - Zero-based block index within the stream
• data - The decompressed block data as a Bytes buffer. Should match the snapshot’s block_size (typically 4-256 KiB), though this is not enforced.

Behavior

1. Constructs cache key (stream as u8, block)
2. Hashes key to determine target shard
3. Acquires shard mutex (blocks if contended)
4. If key exists: Updates value, moves to LRU head
5. If key is new:
   • If shard has space: Inserts at LRU head
   • If shard is full: Evicts LRU tail, inserts at head
6. Releases mutex

Eviction Policy

When a shard reaches capacity, the least-recently used entry in that shard is evicted. Eviction is per-shard, not global, meaning:

• An entry in a full shard may be evicted even if other shards have older entries
• Hit rate may degrade by ~2% compared to global LRU (acceptable for concurrency)

Performance

• Time complexity: O(1) (hash + map insertion + LRU reordering)
• Typical latency:
  • Uncontended: 80-200 ns (mutex + map update)
  • Contended: 200-1000 ns (mutex wait + update)
  • With eviction: +50-100 ns (drop old entry)
• Allocation: Bytes is ref-counted, so no data copy occurs

Thread Safety

This method is thread-safe and can be called concurrently. Sharding reduces contention: up to SHARD_COUNT threads can insert into different shards in parallel without blocking each other.

Correctness Requirements

CRITICAL: The caller must ensure:

1. Data integrity: data is the correct decompressed content for (stream, block)
2. Consistency: If a block is updated in the backend, the cache entry must be invalidated (this cache does not implement invalidation; snapshots are immutable)
3. Size matching: data.len() should match block_size (enforced by File, not by this cache)

Violating these requirements can cause data corruption or incorrect reads.

Errors

This method silently ignores errors:

• Cache disabled: capacity = 0 → no-op (does nothing)
• Mutex poisoning: If another thread panicked while holding the mutex → no-op (entry is not inserted, but no error is propagated)

These are defensive measures to prevent cache failures from breaking the read path.

Examples

Basic Insertion

use hexz_core::cache::lru::BlockCache;
use hexz_core::api::file::SnapshotStream;
use bytes::Bytes;

let cache = BlockCache::with_capacity(1000);

// Insert decompressed block
let data = Bytes::from(vec![0xDE, 0xAD, 0xBE, 0xEF]);
cache.insert(SnapshotStream::Disk, 42, data.clone());

// Verify insertion
assert_eq!(cache.get(SnapshotStream::Disk, 42), Some(data));

Update Existing Entry

let cache = BlockCache::with_capacity(1000);

// Insert original data
let old_data = Bytes::from(vec![1, 2, 3]);
cache.insert(SnapshotStream::Memory, 10, old_data);

// Update with new data (moves to LRU head)
let new_data = Bytes::from(vec![4, 5, 6]);
cache.insert(SnapshotStream::Memory, 10, new_data.clone());

// Retrieves updated data
assert_eq!(cache.get(SnapshotStream::Memory, 10), Some(new_data));

Eviction on Full Cache

let cache = BlockCache::with_capacity(2); // Tiny cache (single shard, 2 entries)

// Fill cache
cache.insert(SnapshotStream::Disk, 0, Bytes::from(vec![0]));
cache.insert(SnapshotStream::Disk, 1, Bytes::from(vec![1]));

// Access block 0 (makes block 1 the LRU)
let _ = cache.get(SnapshotStream::Disk, 0);

// Insert block 2 (evicts block 1, which is LRU)
cache.insert(SnapshotStream::Disk, 2, Bytes::from(vec![2]));

// Block 1 was evicted
assert_eq!(cache.get(SnapshotStream::Disk, 1), None);
// Blocks 0 and 2 remain
assert!(cache.get(SnapshotStream::Disk, 0).is_some());
assert!(cache.get(SnapshotStream::Disk, 2).is_some());

Disabled Cache (No-Op)

let cache = BlockCache::with_capacity(0); // Cache disabled

// Insert is silently ignored
cache.insert(SnapshotStream::Disk, 42, Bytes::from(vec![1, 2, 3]));

// Lookup returns None (nothing was cached)
assert_eq!(cache.get(SnapshotStream::Disk, 42), None);

Trait Implementations

impl Debug for BlockCache

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for BlockCache

fn default() -> Self

Constructs a block cache with the default L1 capacity (1000 entries).

This provides a sensible default for typical desktop/server workloads without requiring the caller to choose a capacity. For memory-constrained or high-performance systems, use BlockCache::with_capacity() to specify a custom value.

Memory Usage

With default capacity (1000 entries) and 64 KiB blocks:

• Data storage: 1000 × 64 KiB ≈ 64 MB
• Metadata overhead: ~100 KB
• Total: ~64.1 MB

Performance

Equivalent to BlockCache::with_capacity(DEFAULT_L1_CAPACITY), which:

• Allocates 16 shards (since 1000 > 256)
• Each shard holds 63 entries (ceil(1000 / 16))
• Total effective capacity: 1008 entries (16 × 63)

Examples

use hexz_core::cache::lru::BlockCache;

// Use default capacity (1000 entries ≈ 64 MB with 64 KiB blocks)
let cache = BlockCache::default();

// Equivalent to:
let cache2 = BlockCache::with_capacity(1000);