datum-persistence 0.11.3

Event sourcing, durable state, and CQRS persistence for Datum
Documentation
//! Frozen persistence-id slice model.
//!
//! Datum PostgreSQL journal rows have stored this slice since v0.11.1. The
//! count and hash are therefore durable data contracts, not tuning knobs.

use crate::{PersistenceError, PersistenceResult};

/// Number of persistence-id slices.
///
/// This value is fixed forever. Changing it would make newly computed slices
/// disagree with the `slice` column already stored in PostgreSQL journals.
pub const SLICE_COUNT: u16 = 1_024;

const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325;
const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;

/// Inclusive contiguous range of persistence-id slices.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SliceRange {
    min: u16,
    max: u16,
}

impl SliceRange {
    /// Creates and validates an inclusive range within `0..1024`.
    pub fn new(min: u16, max: u16) -> PersistenceResult<Self> {
        if min > max {
            return Err(PersistenceError::Rejected(format!(
                "minimum slice {min} exceeds maximum slice {max}"
            )));
        }
        if max >= SLICE_COUNT {
            return Err(PersistenceError::Rejected(format!(
                "maximum slice {max} is outside the fixed 0..{} slice space",
                SLICE_COUNT - 1
            )));
        }
        Ok(Self { min, max })
    }

    /// Returns the inclusive lower slice.
    #[must_use]
    pub const fn min(self) -> u16 {
        self.min
    }

    /// Returns the inclusive upper slice.
    #[must_use]
    pub const fn max(self) -> u16 {
        self.max
    }

    /// Returns the number of slices in this range.
    #[must_use]
    pub const fn len(self) -> u16 {
        self.max - self.min + 1
    }

    /// Returns `false`; validated inclusive ranges always contain a slice.
    #[must_use]
    pub const fn is_empty(self) -> bool {
        false
    }

    /// Returns whether this range contains `slice`.
    #[must_use]
    pub const fn contains(self, slice: u16) -> bool {
        self.min <= slice && slice <= self.max
    }
}

/// Returns the frozen FNV-1a slice for a complete persistence id.
///
/// The hash consumes the UTF-8 bytes of the **full** persistence id, including
/// the entity-type separator and entity id, then takes the result modulo
/// [`SLICE_COUNT`]. PostgreSQL journal rows have persisted this exact result
/// since Datum v0.11.1. Changing the offset basis, prime, byte encoding,
/// input shape, or slice count is a storage compatibility break.
#[must_use]
pub fn slice_for(persistence_id: &str) -> u16 {
    let mut hash = FNV_OFFSET_BASIS;
    for byte in persistence_id.as_bytes() {
        hash ^= u64::from(*byte);
        hash = hash.wrapping_mul(FNV_PRIME);
    }
    u16::try_from(hash % u64::from(SLICE_COUNT)).expect("slice modulo fits u16")
}

/// Splits the fixed slice space into equal contiguous ranges.
///
/// Akka parity requires `number_of_ranges` to be a whole-number divisor of
/// 1024. Consequently every returned range has equal size, and together they
/// cover `0..=1023` without gaps or overlap. Zero, values above 1024, and
/// non-divisors are rejected rather than receiving backend-specific remainder
/// semantics.
pub fn slice_ranges(number_of_ranges: usize) -> PersistenceResult<Vec<SliceRange>> {
    let slice_count = usize::from(SLICE_COUNT);
    if number_of_ranges == 0 || !slice_count.is_multiple_of(number_of_ranges) {
        return Err(PersistenceError::Rejected(format!(
            "number of slice ranges {number_of_ranges} must be a whole-number divisor of {SLICE_COUNT}"
        )));
    }

    let range_size = slice_count / number_of_ranges;
    (0..number_of_ranges)
        .map(|index| {
            let min = index * range_size;
            let max = min + range_size - 1;
            SliceRange::new(
                u16::try_from(min).expect("slice range minimum fits u16"),
                u16::try_from(max).expect("slice range maximum fits u16"),
            )
        })
        .collect()
}

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

    #[test]
    fn committed_golden_fixtures_freeze_the_production_hash() {
        let fixtures = include_str!("../../tests/fixtures/persistence_slices.tsv");
        let mut checked = 0;
        for (line_number, line) in fixtures.lines().enumerate() {
            if line.is_empty() || line.starts_with('#') {
                continue;
            }
            let (persistence_id, expected) = line
                .split_once('\t')
                .unwrap_or_else(|| panic!("invalid slice fixture at line {}", line_number + 1));
            let expected = expected.parse::<u16>().unwrap_or_else(|error| {
                panic!(
                    "invalid expected slice at fixture line {}: {error}",
                    line_number + 1
                )
            });
            assert_eq!(
                slice_for(persistence_id),
                expected,
                "frozen slice changed for persistence id {persistence_id:?}"
            );
            checked += 1;
        }
        assert!(
            checked >= 20,
            "golden fixture must retain enough diverse ids to catch hash drift"
        );
    }

    #[test]
    fn ranges_are_contiguous_complete_non_overlapping_and_equal() {
        for number_of_ranges in [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1_024] {
            let ranges = slice_ranges(number_of_ranges).unwrap();
            assert_eq!(ranges.len(), number_of_ranges);
            assert_eq!(ranges.first().copied().map(SliceRange::min), Some(0));
            assert_eq!(
                ranges.last().copied().map(SliceRange::max),
                Some(SLICE_COUNT - 1)
            );

            let expected_len = SLICE_COUNT / u16::try_from(number_of_ranges).unwrap();
            let mut seen = vec![false; usize::from(SLICE_COUNT)];
            for (index, range) in ranges.iter().copied().enumerate() {
                assert_eq!(range.len(), expected_len);
                if index > 0 {
                    assert_eq!(ranges[index - 1].max() + 1, range.min());
                }
                for slice in range.min()..=range.max() {
                    assert!(
                        !std::mem::replace(&mut seen[usize::from(slice)], true),
                        "slice {slice} appears in more than one range"
                    );
                }
            }
            assert!(seen.into_iter().all(std::convert::identity));
        }
    }

    #[test]
    fn range_boundaries_cover_one_and_one_range_per_slice() {
        assert_eq!(
            slice_ranges(1).unwrap(),
            vec![SliceRange::new(0, 1_023).unwrap()]
        );
        let one_per_slice = slice_ranges(1_024).unwrap();
        assert_eq!(one_per_slice.len(), 1_024);
        assert_eq!(one_per_slice[0], SliceRange::new(0, 0).unwrap());
        assert_eq!(one_per_slice[1_023], SliceRange::new(1_023, 1_023).unwrap());
    }

    #[test]
    fn ranges_reject_zero_non_divisors_and_out_of_space_bounds() {
        for invalid in [0, 3, 5, 1_023, 1_025] {
            assert!(slice_ranges(invalid).is_err(), "{invalid} must be rejected");
        }
        assert!(SliceRange::new(2, 1).is_err());
        assert!(SliceRange::new(0, SLICE_COUNT).is_err());
    }
}