armdb 0.15.3

sharded bitcask key-value storage optimized for NVMe
Documentation
//! Shared byte-budget cache of sealed-segment blocks and verified metadata pages.
//!
//! Keys never go stale: a `(segment_id, version)` pair is never reused for
//! different bytes (invariant I4), so nothing is ever invalidated.

use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};

use quick_cache::sync::Cache;
use quick_cache::{OptionsBuilder, Weighter};

/// Blocks assumed when sizing the hash table: one per 16 KiB of budget.
const ASSUMED_BLOCK_LEN: u64 = 16 * 1024;
const MIN_ESTIMATED_ITEMS: usize = 16;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) enum CacheItem {
    Block(u32),
    Meta {
        kind: u32,
        prefix_len: u16,
        chunk: u32,
    },
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) struct SegBlockKey {
    pub segment_id: u64,
    pub version: u32,
    pub item: CacheItem,
}

#[derive(Clone)]
struct PayloadWeighter;

impl Weighter<SegBlockKey, Arc<[u8]>> for PayloadWeighter {
    fn weight(&self, _key: &SegBlockKey, value: &Arc<[u8]>) -> u64 {
        value.len() as u64
    }
}

pub(crate) struct SegBlockCache {
    inner: Option<Cache<SegBlockKey, Arc<[u8]>, PayloadWeighter>>,
    hits: AtomicU64,
    misses: AtomicU64,
    meta_hits: AtomicU64,
    meta_misses: AtomicU64,
}

impl SegBlockCache {
    pub(crate) fn new(max_bytes: u64) -> Self {
        let inner = (max_bytes > 0).then(|| {
            let items = ((max_bytes / ASSUMED_BLOCK_LEN) as usize).max(MIN_ESTIMATED_ITEMS);
            // One shard: quick_cache splits the byte budget between its
            // shards and refuses an item heavier than its shard's main
            // queue, so with several shards a large block would be refused
            // even when the whole cache has room for it. With one, a block
            // up to the main queue's 97 % of the budget fits. The default
            // split leaves S3-FIFO its probation queue, so a block read
            // shortly after its first read is kept.
            let options = OptionsBuilder::new()
                .estimated_items_capacity(items)
                .weight_capacity(max_bytes)
                .shards(1)
                .build()
                .expect("valid block cache options");
            Cache::with_options(
                options,
                PayloadWeighter,
                Default::default(),
                Default::default(),
            )
        });
        Self {
            inner,
            hits: AtomicU64::new(0),
            misses: AtomicU64::new(0),
            meta_hits: AtomicU64::new(0),
            meta_misses: AtomicU64::new(0),
        }
    }

    pub(crate) fn get(&self, key: &SegBlockKey) -> Option<Arc<[u8]>> {
        let found = self.inner.as_ref()?.get(key);
        let counter = match (key.item, found.is_some()) {
            (CacheItem::Block(_), true) => &self.hits,
            (CacheItem::Block(_), false) => &self.misses,
            (CacheItem::Meta { .. }, true) => &self.meta_hits,
            (CacheItem::Meta { .. }, false) => &self.meta_misses,
        };
        counter.fetch_add(1, Ordering::Relaxed);
        found
    }

    pub(crate) fn insert(&self, key: SegBlockKey, payload: Arc<[u8]>) {
        if let Some(cache) = &self.inner {
            cache.insert(key, payload);
        }
    }

    /// Current resident payload weight; cache table/ghost/Arc allocations are
    /// deliberately outside the payload-only weighter and measured separately.
    pub(crate) fn weight(&self) -> u64 {
        self.inner.as_ref().map_or(0, Cache::weight)
    }

    pub(crate) fn meta_hits(&self) -> u64 {
        self.meta_hits.load(Ordering::Relaxed)
    }
    pub(crate) fn meta_misses(&self) -> u64 {
        self.meta_misses.load(Ordering::Relaxed)
    }

    pub(crate) fn hits(&self) -> u64 {
        self.hits.load(Ordering::Relaxed)
    }

    pub(crate) fn misses(&self) -> u64 {
        self.misses.load(Ordering::Relaxed)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn key(segment_id: u64, version: u32, block: u32) -> SegBlockKey {
        SegBlockKey {
            segment_id,
            version,
            item: CacheItem::Block(block),
        }
    }

    fn payload(tag: u8, len: usize) -> Arc<[u8]> {
        Arc::from(vec![tag; len])
    }

    #[test]
    fn metadata_key_space_and_counters_are_independent_under_one_budget() {
        let cache = SegBlockCache::new(1 << 20);
        let block = key(1, 1, 0);
        let mut meta = block;
        meta.item = CacheItem::Meta {
            kind: 2,
            prefix_len: 0,
            chunk: 0,
        };
        let mut prefix = meta;
        prefix.item = CacheItem::Meta {
            kind: 2,
            prefix_len: 4,
            chunk: 0,
        };
        let mut kind = meta;
        kind.item = CacheItem::Meta {
            kind: 3,
            prefix_len: 0,
            chunk: 0,
        };
        for k in [block, meta, prefix, kind] {
            assert!(cache.get(&k).is_none());
        }
        for (i, k) in [block, meta, prefix, kind].into_iter().enumerate() {
            cache.insert(k, payload(i as u8, 100));
        }
        for (i, k) in [block, meta, prefix, kind].into_iter().enumerate() {
            assert_eq!(cache.get(&k).unwrap()[0], i as u8);
        }
        assert_eq!(
            (
                cache.hits(),
                cache.misses(),
                cache.meta_hits(),
                cache.meta_misses()
            ),
            (1, 1, 3, 3)
        );
        assert_eq!(cache.weight(), 400);
        for n in 0..2_000 {
            let mut k = meta;
            k.item = CacheItem::Meta {
                kind: 2,
                prefix_len: 0,
                chunk: n,
            };
            cache.insert(k, payload(1, 4096));
            cache.insert(key(1, 1, n), payload(2, 4096));
        }
        assert!(cache.weight() <= 1 << 20);
    }

    #[test]
    fn a_block_round_trips_and_counts_a_hit() {
        let cache = SegBlockCache::new(1 << 20);
        assert!(cache.get(&key(1, 1, 0)).is_none());
        cache.insert(key(1, 1, 0), payload(7, 100));
        assert_eq!(&*cache.get(&key(1, 1, 0)).unwrap(), &[7u8; 100][..]);
        assert_eq!(cache.hits(), 1);
        assert_eq!(cache.misses(), 1);
    }

    #[test]
    fn every_part_of_the_key_matters() {
        let cache = SegBlockCache::new(1 << 20);
        cache.insert(key(1, 1, 0), payload(1, 10));
        cache.insert(key(2, 1, 0), payload(2, 10));
        cache.insert(key(1, 2, 0), payload(3, 10));
        cache.insert(key(1, 1, 1), payload(4, 10));
        assert_eq!(cache.get(&key(1, 1, 0)).unwrap()[0], 1);
        assert_eq!(cache.get(&key(2, 1, 0)).unwrap()[0], 2);
        assert_eq!(cache.get(&key(1, 2, 0)).unwrap()[0], 3);
        assert_eq!(cache.get(&key(1, 1, 1)).unwrap()[0], 4);
    }

    #[test]
    fn a_zero_budget_disables_the_cache() {
        let cache = SegBlockCache::new(0);
        cache.insert(key(1, 1, 0), payload(7, 100));
        assert!(cache.get(&key(1, 1, 0)).is_none());
    }

    #[test]
    fn the_budget_bounds_what_stays() {
        let budget = 4u64 << 20;
        let cache = SegBlockCache::new(budget);
        for block in 0..64u32 {
            cache.insert(key(1, 1, block), payload(block as u8, 1 << 20));
        }
        let kept: u64 = (0..64u32)
            .filter_map(|block| cache.get(&key(1, 1, block)))
            .map(|p| p.len() as u64)
            .sum();
        assert!(
            kept <= budget,
            "{kept} bytes kept under a budget of {budget}"
        );
        assert!(kept > 0, "the cache kept nothing");
    }

    /// quick_cache is S3-FIFO: once the cache is full, a new block enters the
    /// small probation queue, which holds whatever the main queue does not
    /// (at least 3 % of the budget), and moves to the main queue if it is
    /// read before it reaches the end of probation. The main queue only
    /// evicts when something is promoted into it, so a promoted block
    /// outlives any number of blocks that are never read again. One shard
    /// makes the whole sequence deterministic.
    #[test]
    fn a_block_read_soon_after_insertion_outlives_blocks_never_read() {
        const BLOCK: usize = 1024;
        let cache = SegBlockCache::new(100 * BLOCK as u64);
        // Fill the cache and churn through the probation queue.
        for block in 0..200 {
            cache.insert(key(1, 1, block), payload(0, BLOCK));
        }
        let x = key(2, 1, 0);
        let y = key(2, 1, 1);
        cache.insert(x, payload(1, BLOCK));
        cache.insert(y, payload(2, BLOCK));
        // A reuse distance of one insertion: the probation queue must not be
        // so small that the next insertion already pushes `x` out.
        assert!(
            cache.get(&x).is_some(),
            "x was evicted by the next insertion"
        );

        for block in 0..200 {
            cache.insert(key(3, 1, block), payload(3, BLOCK));
        }
        assert!(cache.get(&x).is_some(), "a block read again was evicted");
        assert!(cache.get(&y).is_none(), "a block never read again stayed");
    }
}