armdb 0.15.3

sharded bitcask key-value storage optimized for NVMe
Documentation
//! Conservative hot-allocation estimates and newest-first residency assignment.
use super::{
    page_index::{PageIndex, pageable},
    sidecar::{
        OrderKind, SECTION_BLOCK_INDEX, SECTION_FILTER, SECTION_PREFIX_FILTER,
        SECTION_SEPARATOR_INDEX, SectionRecord,
    },
};
/// Length of the newest-first hot prefix within the configured budget.
pub(crate) fn assign(costs_newest_first: &[u64], budget: Option<u64>) -> usize {
    let Some(budget) = budget else {
        return costs_newest_first.len();
    };
    let mut sum = 0u64;
    costs_newest_first
        .iter()
        .take_while(|&&cost| {
            let Some(next) = sum.checked_add(cost) else {
                return false;
            };
            if next > budget {
                return false;
            }
            sum = next;
            true
        })
        .count()
}

/// Conservative bound of a segment's hot allocations.
pub(crate) fn cost(records: &[SectionRecord], order: OrderKind, pages: Option<&PageIndex>) -> u64 {
    const PER_STRUCTURE: u64 = 64;
    let mut cost = PER_STRUCTURE;
    for r in records.iter().filter(|r| pageable(r.kind, order)) {
        cost += match r.kind {
            SECTION_FILTER | SECTION_PREFIX_FILTER => r.len + PER_STRUCTURE,
            SECTION_BLOCK_INDEX => 16 * ((r.len - 8) / 24) + 8 + 2 * PER_STRUCTURE,
            SECTION_SEPARATOR_INDEX => match pages {
                Some(p) => r.len - 8 - 4 * p.index.blocks as u64 + 3 * PER_STRUCTURE,
                None => r.len + 3 * PER_STRUCTURE,
            },
            _ => 0,
        };
    }
    cost
}

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

    #[test]
    fn the_hot_set_is_a_prefix_within_the_budget() {
        assert_eq!(assign(&[80, 30, 10], None), 3);
        assert_eq!(assign(&[80, 30, 10], Some(0)), 0);
        assert_eq!(assign(&[80, 30, 10], Some(80)), 1);
        assert_eq!(assign(&[80, 30, 10], Some(100)), 1);
        assert_eq!(assign(&[80, 30, 10], Some(120)), 3);
        assert_eq!(assign(&[200, 1], Some(100)), 0);
        assert_eq!(assign(&[u64::MAX, 1], Some(u64::MAX)), 1);
    }

    proptest! {
        #[test]
        fn seals_and_oldest_drops_never_warm_a_survivor(
            ops in proptest::collection::vec(prop_oneof![(1u64..100).prop_map(Some), Just(None)], 1..200),
            budget in 0u64..400,
        ) {
            let mut costs = Vec::new();
            let mut hot = 0;
            for op in ops {
                match op {
                    Some(c) => {
                        costs.insert(0, c);
                        let n = assign(&costs, Some(budget));
                        prop_assert!(n <= hot + 1);
                        hot = n;
                    }
                    None => {
                        if costs.pop().is_some() {
                            let n = assign(&costs, Some(budget));
                            prop_assert!(n <= hot.min(costs.len()));
                            hot = n;
                        }
                    }
                }
            }
        }
    }
}