Skip to main content

datum_persistence/query/
slice.rs

1//! Frozen persistence-id slice model.
2//!
3//! Datum PostgreSQL journal rows have stored this slice since v0.11.1. The
4//! count and hash are therefore durable data contracts, not tuning knobs.
5
6use crate::{PersistenceError, PersistenceResult};
7
8/// Number of persistence-id slices.
9///
10/// This value is fixed forever. Changing it would make newly computed slices
11/// disagree with the `slice` column already stored in PostgreSQL journals.
12pub const SLICE_COUNT: u16 = 1_024;
13
14const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325;
15const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
16
17/// Inclusive contiguous range of persistence-id slices.
18#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
19pub struct SliceRange {
20    min: u16,
21    max: u16,
22}
23
24impl SliceRange {
25    /// Creates and validates an inclusive range within `0..1024`.
26    pub fn new(min: u16, max: u16) -> PersistenceResult<Self> {
27        if min > max {
28            return Err(PersistenceError::Rejected(format!(
29                "minimum slice {min} exceeds maximum slice {max}"
30            )));
31        }
32        if max >= SLICE_COUNT {
33            return Err(PersistenceError::Rejected(format!(
34                "maximum slice {max} is outside the fixed 0..{} slice space",
35                SLICE_COUNT - 1
36            )));
37        }
38        Ok(Self { min, max })
39    }
40
41    /// Returns the inclusive lower slice.
42    #[must_use]
43    pub const fn min(self) -> u16 {
44        self.min
45    }
46
47    /// Returns the inclusive upper slice.
48    #[must_use]
49    pub const fn max(self) -> u16 {
50        self.max
51    }
52
53    /// Returns the number of slices in this range.
54    #[must_use]
55    pub const fn len(self) -> u16 {
56        self.max - self.min + 1
57    }
58
59    /// Returns `false`; validated inclusive ranges always contain a slice.
60    #[must_use]
61    pub const fn is_empty(self) -> bool {
62        false
63    }
64
65    /// Returns whether this range contains `slice`.
66    #[must_use]
67    pub const fn contains(self, slice: u16) -> bool {
68        self.min <= slice && slice <= self.max
69    }
70}
71
72/// Returns the frozen FNV-1a slice for a complete persistence id.
73///
74/// The hash consumes the UTF-8 bytes of the **full** persistence id, including
75/// the entity-type separator and entity id, then takes the result modulo
76/// [`SLICE_COUNT`]. PostgreSQL journal rows have persisted this exact result
77/// since Datum v0.11.1. Changing the offset basis, prime, byte encoding,
78/// input shape, or slice count is a storage compatibility break.
79#[must_use]
80pub fn slice_for(persistence_id: &str) -> u16 {
81    let mut hash = FNV_OFFSET_BASIS;
82    for byte in persistence_id.as_bytes() {
83        hash ^= u64::from(*byte);
84        hash = hash.wrapping_mul(FNV_PRIME);
85    }
86    u16::try_from(hash % u64::from(SLICE_COUNT)).expect("slice modulo fits u16")
87}
88
89/// Splits the fixed slice space into equal contiguous ranges.
90///
91/// Akka parity requires `number_of_ranges` to be a whole-number divisor of
92/// 1024. Consequently every returned range has equal size, and together they
93/// cover `0..=1023` without gaps or overlap. Zero, values above 1024, and
94/// non-divisors are rejected rather than receiving backend-specific remainder
95/// semantics.
96pub fn slice_ranges(number_of_ranges: usize) -> PersistenceResult<Vec<SliceRange>> {
97    let slice_count = usize::from(SLICE_COUNT);
98    if number_of_ranges == 0 || !slice_count.is_multiple_of(number_of_ranges) {
99        return Err(PersistenceError::Rejected(format!(
100            "number of slice ranges {number_of_ranges} must be a whole-number divisor of {SLICE_COUNT}"
101        )));
102    }
103
104    let range_size = slice_count / number_of_ranges;
105    (0..number_of_ranges)
106        .map(|index| {
107            let min = index * range_size;
108            let max = min + range_size - 1;
109            SliceRange::new(
110                u16::try_from(min).expect("slice range minimum fits u16"),
111                u16::try_from(max).expect("slice range maximum fits u16"),
112            )
113        })
114        .collect()
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120
121    #[test]
122    fn committed_golden_fixtures_freeze_the_production_hash() {
123        let fixtures = include_str!("../../tests/fixtures/persistence_slices.tsv");
124        let mut checked = 0;
125        for (line_number, line) in fixtures.lines().enumerate() {
126            if line.is_empty() || line.starts_with('#') {
127                continue;
128            }
129            let (persistence_id, expected) = line
130                .split_once('\t')
131                .unwrap_or_else(|| panic!("invalid slice fixture at line {}", line_number + 1));
132            let expected = expected.parse::<u16>().unwrap_or_else(|error| {
133                panic!(
134                    "invalid expected slice at fixture line {}: {error}",
135                    line_number + 1
136                )
137            });
138            assert_eq!(
139                slice_for(persistence_id),
140                expected,
141                "frozen slice changed for persistence id {persistence_id:?}"
142            );
143            checked += 1;
144        }
145        assert!(
146            checked >= 20,
147            "golden fixture must retain enough diverse ids to catch hash drift"
148        );
149    }
150
151    #[test]
152    fn ranges_are_contiguous_complete_non_overlapping_and_equal() {
153        for number_of_ranges in [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1_024] {
154            let ranges = slice_ranges(number_of_ranges).unwrap();
155            assert_eq!(ranges.len(), number_of_ranges);
156            assert_eq!(ranges.first().copied().map(SliceRange::min), Some(0));
157            assert_eq!(
158                ranges.last().copied().map(SliceRange::max),
159                Some(SLICE_COUNT - 1)
160            );
161
162            let expected_len = SLICE_COUNT / u16::try_from(number_of_ranges).unwrap();
163            let mut seen = vec![false; usize::from(SLICE_COUNT)];
164            for (index, range) in ranges.iter().copied().enumerate() {
165                assert_eq!(range.len(), expected_len);
166                if index > 0 {
167                    assert_eq!(ranges[index - 1].max() + 1, range.min());
168                }
169                for slice in range.min()..=range.max() {
170                    assert!(
171                        !std::mem::replace(&mut seen[usize::from(slice)], true),
172                        "slice {slice} appears in more than one range"
173                    );
174                }
175            }
176            assert!(seen.into_iter().all(std::convert::identity));
177        }
178    }
179
180    #[test]
181    fn range_boundaries_cover_one_and_one_range_per_slice() {
182        assert_eq!(
183            slice_ranges(1).unwrap(),
184            vec![SliceRange::new(0, 1_023).unwrap()]
185        );
186        let one_per_slice = slice_ranges(1_024).unwrap();
187        assert_eq!(one_per_slice.len(), 1_024);
188        assert_eq!(one_per_slice[0], SliceRange::new(0, 0).unwrap());
189        assert_eq!(one_per_slice[1_023], SliceRange::new(1_023, 1_023).unwrap());
190    }
191
192    #[test]
193    fn ranges_reject_zero_non_divisors_and_out_of_space_bounds() {
194        for invalid in [0, 3, 5, 1_023, 1_025] {
195            assert!(slice_ranges(invalid).is_err(), "{invalid} must be rejected");
196        }
197        assert!(SliceRange::new(2, 1).is_err());
198        assert!(SliceRange::new(0, SLICE_COUNT).is_err());
199    }
200}