Skip to main content

kevy_store/
small_set.rs

1//! `SmallSetData` — valkey-style inline-listpack encoding for tiny sets.
2//!
3//! Mirrors valkey's `OBJ_ENCODING_LISTPACK` for sets of size
4//! 1–N (`t_set.c::setTypeMaybeConvert`). valkey starts a fresh set as a
5//! 1-entry listpack inside one cache line; once cardinality grows past
6//! `set-max-listpack-entries` (128 default) OR a single member exceeds the
7//! per-entry size cap, it converts to `OBJ_ENCODING_HT`. kevy's analogue:
8//! [`SmallSetData`] for tiny sets, upgrade to [`crate::value::SetData`]
9//! (Swiss-table `KevySet<SmallBytes>`) on overflow.
10//!
11//! ## Layout
12//!
13//! Exactly 24 bytes, mirroring [`kevy_bytes::SmallBytes`] so the
14//! `Value::SmallSetInline(SmallSetData)` variant body matches the size
15//! of `Value::Str(SmallBytes)` and the
16//! `assert!(size_of::<Value>() <= 32)` in `value.rs:162` still holds:
17//!
18//! ```text
19//! offset: 0    1                                 23
20//!         +----+----+----+----+----+ ...     +-----+
21//!         | n  | u  |       buf[22]              |
22//!         +----+----+----+----+----+ ...     +-----+
23//! ```
24//!
25//! - `n` (u8): member count (`0..=22`, capped well below to leave room).
26//! - `u` (u8): bytes used in `buf` (sum of `1 + len_i` over all members).
27//! - `buf` ([u8; 22]): packed `[len_i: u8][member_i: u8; len_i]` entries.
28//!
29//! Per-entry length prefix is one byte → a single member is at most 21
30//! bytes (need 1 byte for the length itself). For 20-byte
31//! `element:__rand_int__` (the redis-benchmark default SADD member shape),
32//! one entry consumes 21 bytes — fits with 1 spare. For shorter members,
33//! 4-5 fit comfortably.
34//!
35//! ## Upgrade trigger
36//!
37//! Insert returns [`AddResult::NoRoom`] when either (a) the new member's
38//! `1 + len` would overflow the 22-byte budget, or (b) the per-member
39//! length exceeds the 21-byte per-entry cap. The caller upgrades to
40//! `Value::Set(Arc<SetData>)` and re-inserts the new member there.
41//!
42//! Linear-scan `contains` over ≤ N members is faster than the
43//! hash-then-SIMD-probe path on a 16-slot Swiss table when N is small
44//! AND the data is one cache line — the same structural reason valkey's
45//! listpack beats `OBJ_ENCODING_HT` for N≤128.
46//!
47//! ## Future extension
48//!
49//! Hash / List / ZSet families want the same encoding switch. The
50//! pattern factored here:
51//! 1. Inline 24-byte packed-entries variant on `Value`.
52//! 2. Per-op `try_*` helper returns `AddResult { Added, AlreadyPresent,
53//!    NoRoom }` so the caller knows when to upgrade.
54//! 3. `account_delta` accepts the per-member weight delta uniformly; the
55//!    inline variant returns its own `inline_weight()` (zero heap) so the
56//!    Store's `used_memory` accounting stays consistent across both
57//!    encodings.
58//!
59//! The `Hash` analogue will need `[len_field][field][len_val][val]`
60//! tuples; List can use the same `[len][bytes]` shape; ZSet needs
61//! `[score:8][len][member]`. All three fit the 24-byte budget for the
62//! 1–3 member cases that dominate `redis-benchmark` default shapes.
63
64use kevy_bytes::SmallBytes;
65
66/// Inline packed set storage. 24 bytes total — see module docs for layout.
67///
68/// ```
69/// use kevy_store::{Store, Value};
70/// let mut s = Store::new();
71/// s.sadd(b"s", &[b"x".as_slice()])?;
72/// s.snapshot_each(|_, v, _| {
73///     let Value::SmallSetInline(m) = v else { panic!("a one-member set stays inline") };
74///     assert!(m.contains(b"x"));
75///     assert!(!m.contains(b"y"));
76/// });
77/// # Ok::<(), kevy_store::StoreError>(())
78/// ```
79#[derive(Debug, Clone)]
80pub struct SmallSetData {
81    /// Number of inline members (0..=22 cap, real ceiling is byte-budget).
82    count: u8,
83    /// Bytes used in `buf` so far (sum of `1 + member_len` per entry).
84    used: u8,
85    /// Packed `[len_i: u8][member_i; len_i]` entries, contiguous from
86    /// offset 0 up to `used`.
87    buf: [u8; SMALL_SET_BUF_CAP],
88}
89
90/// Byte budget for the inline packed entries area. Chosen so that
91/// `count(1) + used(1) + buf(22) = 24` bytes total, matching the
92/// `SmallBytes` body size and preserving `size_of::<Value>() <= 32`.
93pub(crate) const SMALL_SET_BUF_CAP: usize = 22;
94
95/// Per-member length cap: one byte is spent on the length prefix, so the
96/// member payload can be at most `SMALL_SET_BUF_CAP - 1` bytes. Members
97/// larger than this trigger an [`AddResult::NoRoom`] regardless of how
98/// empty the inline buffer is — the caller must upgrade to
99/// `Value::Set` to store them.
100pub(crate) const SMALL_SET_MEMBER_MAX: usize = SMALL_SET_BUF_CAP - 1;
101
102/// Per-set member count cap. The byte budget tends to hit first (a single
103/// 20-byte member takes 21 of 22 bytes), but a hard `count` cap keeps the
104/// linear scan deterministic and bounds the `u8` count field.
105pub(crate) const SMALL_SET_COUNT_MAX: usize = 8;
106
107/// Outcome of [`SmallSetData::try_add`].
108pub(crate) enum AddResult {
109    /// Member was new; count + used updated.
110    Added,
111    /// Member already present; no change.
112    AlreadyPresent,
113    /// Member doesn't fit (either too long or buffer full / count cap).
114    /// Caller must upgrade to `Value::Set` and re-insert.
115    NoRoom,
116}
117
118impl SmallSetData {
119    /// Build an empty inline set.
120    pub(crate) fn new() -> Self {
121        Self { count: 0, used: 0, buf: [0; SMALL_SET_BUF_CAP] }
122    }
123
124    /// Build an inline set holding one member, if it fits. Returns `None`
125    /// when the member exceeds [`SMALL_SET_MEMBER_MAX`] — the caller
126    /// should create a `Value::Set(Arc::default())` and insert the
127    /// member there instead.
128    pub(crate) fn with_one(member: &[u8]) -> Option<Self> {
129        if member.len() > SMALL_SET_MEMBER_MAX {
130            return None;
131        }
132        let mut s = Self::new();
133        s.buf[0] = member.len() as u8;
134        s.buf[1..1 + member.len()].copy_from_slice(member);
135        s.count = 1;
136        s.used = 1 + member.len() as u8;
137        Some(s)
138    }
139
140    /// Number of inline members.
141    pub fn len(&self) -> usize {
142        self.count as usize
143    }
144
145    /// Whether the inline set has no members.
146    pub fn is_empty(&self) -> bool {
147        self.count == 0
148    }
149
150    /// Linear scan for `member`. ≤22 bytes of packed entries fit in one
151    /// cache line; loop is unrolled by the optimiser at small counts.
152    pub fn contains(&self, member: &[u8]) -> bool {
153        self.iter().any(|m| m == member)
154    }
155
156    /// Iterator over the packed entries as `&[u8]` slices. Owns nothing.
157    pub fn iter(&self) -> SmallSetIter<'_> {
158        SmallSetIter { buf: &self.buf[..self.used as usize], cursor: 0 }
159    }
160
161    /// Try to append `member`. See [`AddResult`].
162    pub(crate) fn try_add(&mut self, member: &[u8]) -> AddResult {
163        if self.contains(member) {
164            return AddResult::AlreadyPresent;
165        }
166        if member.len() > SMALL_SET_MEMBER_MAX {
167            return AddResult::NoRoom;
168        }
169        if self.count as usize >= SMALL_SET_COUNT_MAX {
170            return AddResult::NoRoom;
171        }
172        let need = 1 + member.len();
173        let new_used = self.used as usize + need;
174        if new_used > SMALL_SET_BUF_CAP {
175            return AddResult::NoRoom;
176        }
177        let off = self.used as usize;
178        self.buf[off] = member.len() as u8;
179        self.buf[off + 1..off + need].copy_from_slice(member);
180        self.used = new_used as u8;
181        self.count += 1;
182        AddResult::Added
183    }
184
185    /// Try to remove `member`. Returns whether it was present. On hit,
186    /// the trailing packed entries are shifted left by `1 + len` to
187    /// close the gap (deterministic O(used) memmove, fits in cache line).
188    pub(crate) fn try_remove(&mut self, member: &[u8]) -> bool {
189        let mut cursor = 0usize;
190        let used = self.used as usize;
191        while cursor < used {
192            let len = self.buf[cursor] as usize;
193            let start = cursor + 1;
194            let end = start + len;
195            if &self.buf[start..end] == member {
196                // Shift [end..used) → [cursor..)
197                self.buf.copy_within(end..used, cursor);
198                let shifted = used - end;
199                let new_used = cursor + shifted;
200                // Zero the freed tail (avoid leaking old member bytes
201                // into snapshots / accidental Debug prints).
202                self.buf[new_used..used].fill(0);
203                self.used = new_used as u8;
204                self.count -= 1;
205                return true;
206            }
207            cursor = end;
208        }
209        false
210    }
211}
212
213/// Iterator over [`SmallSetData`] members as `&[u8]` slices.
214///
215/// ```
216/// use kevy_store::{Store, Value};
217/// let mut s = Store::new();
218/// s.sadd(b"s", &[b"x".as_slice(), b"y"])?;
219/// let mut members = Vec::new();
220/// s.snapshot_each(|_, v, _| {
221///     if let Value::SmallSetInline(m) = v {
222///         members = m.iter().map(<[u8]>::to_vec).collect();
223///     }
224/// });
225/// members.sort();
226/// assert_eq!(members, [b"x".to_vec(), b"y".to_vec()]);
227/// # Ok::<(), kevy_store::StoreError>(())
228/// ```
229#[derive(Debug)]
230pub struct SmallSetIter<'a> {
231    buf: &'a [u8],
232    cursor: usize,
233}
234
235impl<'a> Iterator for SmallSetIter<'a> {
236    type Item = &'a [u8];
237
238    fn next(&mut self) -> Option<&'a [u8]> {
239        if self.cursor >= self.buf.len() {
240            return None;
241        }
242        let len = self.buf[self.cursor] as usize;
243        let start = self.cursor + 1;
244        let end = start + len;
245        self.cursor = end;
246        Some(&self.buf[start..end])
247    }
248}
249
250/// Materialise the inline set as a heap-backed [`crate::value::SetData`].
251/// Used when an upgrade is forced by an oversized member or full buffer.
252pub(crate) fn promote(inline: &SmallSetData) -> crate::value::SetData {
253    let mut s = crate::value::SetData::with_capacity(inline.len().max(1));
254    for m in inline.iter() {
255        s.insert(SmallBytes::from_slice(m));
256    }
257    s
258}
259
260#[cfg(test)]
261mod tests {
262    use super::*;
263
264    #[test]
265    fn size_is_24_bytes() {
266        // Mirrors SmallBytes' 24 B body so size_of::<Value>() <= 32 holds.
267        assert_eq!(core::mem::size_of::<SmallSetData>(), 24);
268    }
269
270    #[test]
271    fn empty_and_with_one() {
272        let s = SmallSetData::new();
273        assert_eq!(s.len(), 0);
274        assert!(!s.contains(b"foo"));
275
276        let s = SmallSetData::with_one(b"hi").unwrap();
277        assert_eq!(s.len(), 1);
278        assert!(s.contains(b"hi"));
279        assert!(!s.contains(b"hj"));
280    }
281
282    #[test]
283    fn member_too_long_for_with_one() {
284        let big = vec![b'x'; SMALL_SET_MEMBER_MAX + 1];
285        assert!(SmallSetData::with_one(&big).is_none());
286    }
287
288    #[test]
289    fn add_dedup_and_iter() {
290        let mut s = SmallSetData::new();
291        assert!(matches!(s.try_add(b"a"), AddResult::Added));
292        assert!(matches!(s.try_add(b"b"), AddResult::Added));
293        assert!(matches!(s.try_add(b"a"), AddResult::AlreadyPresent));
294        assert_eq!(s.len(), 2);
295        let v: Vec<&[u8]> = s.iter().collect();
296        assert_eq!(v, vec![b"a".as_slice(), b"b".as_slice()]);
297    }
298
299    #[test]
300    fn full_buffer_returns_no_room() {
301        let mut s = SmallSetData::new();
302        // single 20-byte member uses 21 of 22 bytes; second won't fit.
303        let m1 = b"element:__rand_int__";
304        assert_eq!(m1.len(), 20);
305        assert!(matches!(s.try_add(m1), AddResult::Added));
306        assert!(matches!(s.try_add(b"x"), AddResult::NoRoom));
307    }
308
309    #[test]
310    fn member_too_long_returns_no_room() {
311        let mut s = SmallSetData::new();
312        let big = vec![b'x'; SMALL_SET_MEMBER_MAX + 1];
313        assert!(matches!(s.try_add(&big), AddResult::NoRoom));
314        assert_eq!(s.len(), 0);
315    }
316
317    #[test]
318    fn remove_middle_shifts_tail() {
319        let mut s = SmallSetData::new();
320        assert!(matches!(s.try_add(b"aa"), AddResult::Added));
321        assert!(matches!(s.try_add(b"bbb"), AddResult::Added));
322        assert!(matches!(s.try_add(b"cc"), AddResult::Added));
323        assert!(s.try_remove(b"bbb"));
324        assert_eq!(s.len(), 2);
325        assert!(s.contains(b"aa"));
326        assert!(!s.contains(b"bbb"));
327        assert!(s.contains(b"cc"));
328        let v: Vec<&[u8]> = s.iter().collect();
329        assert_eq!(v, vec![b"aa".as_slice(), b"cc".as_slice()]);
330    }
331
332    #[test]
333    fn remove_absent_returns_false() {
334        let mut s = SmallSetData::new();
335        s.try_add(b"a");
336        assert!(!s.try_remove(b"zz"));
337        assert_eq!(s.len(), 1);
338    }
339
340    #[test]
341    fn count_cap_returns_no_room() {
342        let mut s = SmallSetData::new();
343        // 8 × 1-byte members fit in 16 bytes; 9th should hit the count cap
344        // before the byte cap.
345        for c in b"abcdefgh" {
346            assert!(matches!(s.try_add(&[*c]), AddResult::Added));
347        }
348        assert_eq!(s.len(), SMALL_SET_COUNT_MAX);
349        assert!(matches!(s.try_add(b"i"), AddResult::NoRoom));
350    }
351
352    #[test]
353    fn promote_preserves_members() {
354        let mut s = SmallSetData::new();
355        s.try_add(b"a");
356        s.try_add(b"bb");
357        s.try_add(b"ccc");
358        let promoted = promote(&s);
359        assert_eq!(promoted.len(), 3);
360        assert!(promoted.contains(b"a".as_slice()));
361        assert!(promoted.contains(b"bb".as_slice()));
362        assert!(promoted.contains(b"ccc".as_slice()));
363    }
364}