armdb 0.15.0

sharded bitcask key-value storage optimized for NVMe
Documentation
//! Hash, order and routing shared by the segmented family.

use std::cmp::Ordering;

use xxhash_rust::xxh3::xxh3_64_with_seed;

/// A full scan walks the hash space in this many equal windows and takes a
/// fresh view of the collection for each.
pub(crate) const SCAN_WINDOWS: usize = 256;

const WINDOW_SHIFT: u32 = 56;

/// The 64-bit hash every structure of the family is keyed by.
#[inline]
pub(crate) fn key_hash(key: &[u8], seed: u64) -> u64 {
    xxh3_64_with_seed(key, seed)
}

/// Shard of a generation. Monotone in `h`, so shards are contiguous hash
/// ranges and concatenating them in order yields a sorted run.
#[inline]
pub(crate) fn shard_for_hash(h: u64, shard_count: usize) -> usize {
    ((h as u128 * shard_count as u128) >> 64) as usize
}

/// Real shards intersecting planner hash intervals, sorted and deduplicated.
/// Reject invalid topology before using the interval arithmetic.
pub(crate) fn overlapping_shards(
    planner: &[usize],
    planner_count: usize,
    real_count: usize,
) -> crate::error::DbResult<Vec<usize>> {
    if planner_count == 0 || real_count == 0 || planner.iter().any(|&p| p >= planner_count) {
        return Err(crate::error::DbError::Internal(
            "invalid segmented shard topology",
        ));
    }
    let mut real = Vec::new();
    for &p in planner {
        let (lo, hi) = shard_range(p, planner_count);
        real.extend(shard_for_hash(lo, real_count)..=shard_for_hash(hi, real_count));
    }
    real.sort_unstable();
    real.dedup();
    Ok(real)
}

/// Inclusive hash range routed to `shard`.
pub(crate) fn shard_range(shard: usize, shard_count: usize) -> (u64, u64) {
    debug_assert!(shard < shard_count);
    let n = shard_count as u128;
    let lo = ((shard as u128) << 64).div_ceil(n);
    let hi = ((shard as u128 + 1) << 64).div_ceil(n) - 1;
    (lo as u64, hi as u64)
}

#[inline]
#[cfg(test)]
pub(crate) fn window_of(h: u64) -> usize {
    (h >> WINDOW_SHIFT) as usize
}

/// Inclusive hash range of a scan window.
pub(crate) fn window_range(window: usize) -> (u64, u64) {
    debug_assert!(window < SCAN_WINDOWS);
    let lo = (window as u64) << WINDOW_SHIFT;
    (lo, lo | ((1u64 << WINDOW_SHIFT) - 1))
}

/// Partition of a filter split by the top `bits` bits of the hash.
#[inline]
pub(crate) fn filter_partition(h: u64, bits: u8) -> usize {
    if bits == 0 {
        0
    } else {
        (h >> (64 - u32::from(bits))) as usize
    }
}

/// Smallest split that brings the average partition to `target` keys or
/// fewer, capped at `max_bits`.
pub(crate) fn partition_bits_for(keys: u64, target: u64, max_bits: u8) -> u8 {
    let target = target.max(1);
    let mut bits = 0u8;
    while bits < max_bits && keys.div_ceil(1u64 << bits) > target {
        bits += 1;
    }
    bits
}

/// Order of entries in a Map-shape segment.
#[inline]
pub(crate) fn cmp_hk(ah: u64, ak: &[u8], bh: u64, bk: &[u8]) -> Ordering {
    ah.cmp(&bh).then_with(|| ak.cmp(bk))
}

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

    fn splitmix(state: &mut u64) -> u64 {
        *state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
        let mut z = *state;
        z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
        z ^ (z >> 31)
    }

    const SHARD_COUNTS: [usize; 7] = [1, 2, 3, 7, 16, 64, 255];

    #[test]
    fn overlapping_shards_cover_edges_and_nondivisible_topologies() {
        for planner_count in SHARD_COUNTS {
            for real_count in SHARD_COUNTS {
                for p in 0..planner_count {
                    let real = overlapping_shards(&[p, p], planner_count, real_count).unwrap();
                    assert!(real.windows(2).all(|w| w[0] < w[1]));
                    let (lo, hi) = shard_range(p, planner_count);
                    let mut hashes = vec![
                        0,
                        u64::MAX,
                        lo,
                        hi,
                        lo.saturating_sub(1),
                        hi.saturating_add(1),
                    ];
                    for r in 0..real_count {
                        let (a, b) = shard_range(r, real_count);
                        hashes.extend([a, b, a.saturating_sub(1), b.saturating_add(1)]);
                    }
                    for h in hashes {
                        if (lo..=hi).contains(&h) {
                            assert!(
                                real.contains(&shard_for_hash(h, real_count)),
                                "P={planner_count} R={real_count} p={p} h={h}"
                            );
                        }
                    }
                }
            }
        }
        assert_eq!(
            overlapping_shards(&[2, 0, 2], 3, 7).unwrap(),
            vec![0, 1, 2, 4, 5, 6]
        );
        for (shards, p, r) in [(&[0][..], 0, 3), (&[0][..], 3, 0), (&[3][..], 3, 7)] {
            assert!(overlapping_shards(shards, p, r).is_err());
        }
    }

    #[test]
    fn routing_is_monotone_in_the_hash() {
        let mut state = 7u64;
        for shard_count in SHARD_COUNTS {
            let mut hashes: Vec<u64> = (0..10_000).map(|_| splitmix(&mut state)).collect();
            hashes.extend([0, 1, u64::MAX - 1, u64::MAX]);
            hashes.sort_unstable();
            let mut previous = 0usize;
            for h in hashes {
                let shard = shard_for_hash(h, shard_count);
                assert!(shard < shard_count);
                assert!(shard >= previous, "routing went backwards at {h:#x}");
                previous = shard;
            }
        }
    }

    #[test]
    fn extreme_hashes_route_to_the_first_and_last_bucket() {
        for shard_count in SHARD_COUNTS {
            assert_eq!(shard_for_hash(0, shard_count), 0);
            assert_eq!(shard_for_hash(u64::MAX, shard_count), shard_count - 1);
        }
        assert_eq!(window_of(0), 0);
        assert_eq!(window_of(u64::MAX), SCAN_WINDOWS - 1);
        for bits in 0..=16u8 {
            assert_eq!(filter_partition(0, bits), 0);
            assert_eq!(filter_partition(u64::MAX, bits), (1usize << bits) - 1);
        }
    }

    #[test]
    fn shard_range_agrees_with_routing_at_both_edges() {
        for shard_count in SHARD_COUNTS {
            for shard in 0..shard_count {
                let (lo, hi) = shard_range(shard, shard_count);
                assert!(lo <= hi);
                assert_eq!(shard_for_hash(lo, shard_count), shard);
                assert_eq!(shard_for_hash(hi, shard_count), shard);
                if lo > 0 {
                    assert_eq!(shard_for_hash(lo - 1, shard_count), shard - 1);
                }
                if hi < u64::MAX {
                    assert_eq!(shard_for_hash(hi + 1, shard_count), shard + 1);
                }
            }
            assert_eq!(shard_range(0, shard_count).0, 0);
            assert_eq!(shard_range(shard_count - 1, shard_count).1, u64::MAX);
        }
    }

    #[test]
    fn windows_tile_the_hash_space() {
        let mut expected_lo = 0u64;
        for window in 0..SCAN_WINDOWS {
            let (lo, hi) = window_range(window);
            assert_eq!(lo, expected_lo);
            assert_eq!(window_of(lo), window);
            assert_eq!(window_of(hi), window);
            expected_lo = hi.wrapping_add(1);
        }
        assert_eq!(expected_lo, 0, "the last window must end at u64::MAX");
    }

    #[test]
    fn partition_bits_keep_the_average_under_the_target() {
        assert_eq!(partition_bits_for(0, 524_288, 16), 0);
        assert_eq!(partition_bits_for(524_288, 524_288, 16), 0);
        assert_eq!(partition_bits_for(524_289, 524_288, 16), 1);
        assert_eq!(partition_bits_for(25_920_000, 524_288, 16), 6);
        // The cap wins over the target.
        assert_eq!(partition_bits_for(u64::MAX, 1, 16), 16);
    }

    #[test]
    fn order_is_hash_first_then_key_bytes() {
        assert_eq!(cmp_hk(1, b"zz", 2, b"aa"), Ordering::Less);
        assert_eq!(cmp_hk(2, b"aa", 2, b"ab"), Ordering::Less);
        assert_eq!(cmp_hk(2, b"ab", 2, b"ab"), Ordering::Equal);
        // Bytes compare as unsigned.
        assert_eq!(cmp_hk(2, &[0x7f], 2, &[0x80]), Ordering::Less);
    }

    #[test]
    fn the_seed_changes_the_hash() {
        let key = [7u8; 32];
        assert_ne!(key_hash(&key, 1), key_hash(&key, 2));
        assert_eq!(key_hash(&key, 1), key_hash(&key, 1));
    }
}