armdb 0.15.1

sharded bitcask key-value storage optimized for NVMe
Documentation
//! Charged batches of a segmented source's typed migration (spec, variant A).
pub(crate) const BATCH_MAX_ENTRIES: usize = 65_536;
pub(crate) const BATCH_MAX_BYTES: usize = 16 << 20;
const ENTRY_OVERHEAD: usize = 64;
const OP_OVERHEAD: usize = 48;

pub(crate) enum SourceAction {
    Put(Vec<u8>),
    Delete,
}
pub(crate) struct DerivedOp {
    pub(crate) target: &'static str,
    pub(crate) key: Vec<u8>,
    pub(crate) value: Option<Vec<u8>>,
}
pub(crate) struct BatchEntry {
    pub(crate) key: Vec<u8>,
    pub(crate) action: SourceAction,
    pub(crate) ops: Vec<DerivedOp>,
}

impl BatchEntry {
    fn charge(&self) -> usize {
        let action = match &self.action {
            SourceAction::Put(v) => v.capacity(),
            SourceAction::Delete => 0,
        };
        ENTRY_OVERHEAD
            + self.key.capacity()
            + action
            + self.ops.capacity() * OP_OVERHEAD.max(std::mem::size_of::<DerivedOp>())
            + self
                .ops
                .iter()
                .map(|o| o.key.capacity() + o.value.as_ref().map_or(0, Vec::capacity))
                .sum::<usize>()
    }
}

pub(crate) struct MigrationBatch {
    entries: Vec<BatchEntry>,
    charged: usize,
    max_entries: usize,
    max_bytes: usize,
}

impl MigrationBatch {
    pub(crate) fn new(max_entries: usize, max_bytes: usize) -> Self {
        Self {
            entries: Vec::new(),
            charged: 0,
            max_entries,
            max_bytes,
        }
    }
    fn next_capacity(&self) -> usize {
        if self.entries.len() == self.entries.capacity() {
            self.entries.capacity().saturating_mul(2).max(4)
        } else {
            self.entries.capacity()
        }
    }
    /// Preflight before retaining an entry; a caller drains this batch first.
    pub(crate) fn must_drain_before(&self, entry: &BatchEntry) -> bool {
        !self.is_empty()
            && (self.entries.len() >= self.max_entries
                || self.charged.saturating_add(entry.charge()).saturating_add(
                    self.next_capacity()
                        .saturating_mul(std::mem::size_of::<BatchEntry>()),
                ) > self.max_bytes)
    }
    /// Add a preflighted entry; true when it must be applied before the next push.
    pub(crate) fn push(&mut self, entry: BatchEntry) -> bool {
        assert!(
            !self.must_drain_before(&entry),
            "drain before retaining an over-budget entry"
        );
        let capacity = self.next_capacity();
        self.entries.reserve_exact(capacity - self.entries.len());
        self.charged += entry.charge();
        self.entries.push(entry);
        self.entries.len() >= self.max_entries || self.charged() >= self.max_bytes
    }
    pub(crate) fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }
    pub(crate) fn charged(&self) -> usize {
        self.charged + self.entries.capacity() * std::mem::size_of::<BatchEntry>()
    }
    pub(crate) fn drain(&mut self) -> Vec<BatchEntry> {
        self.charged = 0;
        std::mem::take(&mut self.entries)
    }
}

/// Test-faults-only entry limit for exercising multi-batch crash recovery.
/// Production always uses `BATCH_MAX_ENTRIES`; bytes never change.
pub(crate) fn batch_max_entries() -> usize {
    #[cfg(feature = "test-faults")]
    if let Some(limit) = std::env::var("ARMDB_SEG_INDEX_BATCH_ENTRIES")
        .ok()
        .and_then(|value| value.parse::<usize>().ok())
        .filter(|&n| n > 0)
    {
        return limit.min(BATCH_MAX_ENTRIES);
    }
    BATCH_MAX_ENTRIES
}

#[cfg(test)]
mod tests {
    use super::*;
    fn entry(key: u8, value: usize, ops: usize) -> BatchEntry {
        BatchEntry {
            key: vec![key; 8],
            action: SourceAction::Put(vec![0; value]),
            ops: (0..ops)
                .map(|i| DerivedOp {
                    target: "t",
                    key: vec![i as u8; 24],
                    value: Some(Vec::new()),
                })
                .collect(),
        }
    }
    #[test]
    fn the_budget_charges_keys_values_ops_and_capacity() {
        let mut b = MigrationBatch::new(10, 1 << 20);
        b.push(entry(1, 100, 3));
        assert!(b.charged() >= 8 + 100 + 3 * 24);
    }
    #[test]
    fn a_full_batch_asks_to_be_applied() {
        let mut b = MigrationBatch::new(2, 1 << 20);
        assert!(!b.push(entry(1, 1, 1)));
        assert!(b.push(entry(2, 1, 1)));
    }
    #[test]
    fn an_oversized_entry_forms_its_own_batch() {
        let mut b = MigrationBatch::new(10, 64);
        assert!(
            b.push(entry(1, 1000, 1)),
            "one entry over budget is accepted alone and flushes"
        );
        assert_eq!(b.drain().len(), 1);
        assert!(b.is_empty());
    }
    #[test]
    fn an_oversized_entry_cannot_join_a_nonempty_batch() {
        let mut b = MigrationBatch::new(100, 2048);
        assert!(!b.push(entry(1, 1, 1)));
        let oversized = entry(2, 4096, 1);
        assert!(b.must_drain_before(&oversized));
        assert_eq!(b.drain().len(), 1);
        assert!(b.push(oversized));
        assert_eq!(b.drain().len(), 1);
    }
    #[test]
    fn capacity_growth_is_preflighted_and_charged() {
        let first = entry(1, 1, 0);
        let row_charge = first.charge();
        let size = std::mem::size_of::<BatchEntry>();
        let mut b = MigrationBatch::new(100, row_charge * 5 + size * 4);
        for key in 0..4 {
            assert!(!b.push(entry(key, 1, 0)));
        }
        assert_eq!(b.charged(), row_charge * 4 + size * 4);
        assert!(
            b.must_drain_before(&entry(5, 1, 0)),
            "the fifth row grows capacity to eight"
        );
    }
    #[test]
    fn delete_fanout_covering_values_and_multiple_targets_are_charged() {
        let mut e = entry(1, 8192, 100);
        e.key.reserve_exact(128);
        e.ops.reserve_exact(50);
        for (i, op) in e.ops.iter_mut().enumerate() {
            op.target = if i % 2 == 0 { "a" } else { "b" };
            op.value = Some(Vec::with_capacity(256));
        }
        let expected = ENTRY_OVERHEAD
            + e.key.capacity()
            + 8192
            + e.ops.capacity() * std::mem::size_of::<DerivedOp>().max(OP_OVERHEAD)
            + 100 * (24 + 256);
        assert_eq!(e.charge(), expected);
        e.action = SourceAction::Delete;
        for op in &mut e.ops {
            op.value = None;
        }
        let expected = expected - 8192 - 100 * 256;
        assert_eq!(e.charge(), expected);
        let mut b = MigrationBatch::new(100, expected * 2);
        b.push(e);
        assert!(b.charged() >= expected);
    }
    #[test]
    fn an_index_targets_shared_migration_accepts_keep_and_refuses_update_and_delete() {
        use crate::seg::testkit::{TextCodec, key_of, meta};
        let dir = tempfile::tempdir().unwrap();
        let tree = crate::seg::SegTree::open_deferred(
            dir.path(),
            meta(),
            &[],
            true,
            crate::seg::SegConfig::test(),
            TextCodec,
            crate::NoHook,
        )
        .unwrap();
        let key = key_of(7);
        tree.core().put(&key, b"old").unwrap();
        assert_eq!(
            tree.migrate_rows(|_, _| crate::MigrateAction::Keep)
                .unwrap(),
            0
        );
        for update in [true, false] {
            let err = tree
                .migrate_rows(|_, _| {
                    if update {
                        crate::MigrateAction::Update(String::from("new"))
                    } else {
                        crate::MigrateAction::Delete
                    }
                })
                .unwrap_err();
            assert!(matches!(err, crate::DbError::Config(message) if message.contains("Keep")));
            assert_eq!(tree.try_get(&key).unwrap(), Some(String::from("old")));
        }
    }
}