Skip to main content

happenstance_sync_testkit/
kv_capped.rs

1//! A fixture peer with a cap on each value: Turnstile's peer D.
2//!
3//! SY-18's `[DEFERRED]` marker names the experiment: a KV-backed store with a
4//! 128 KiB value cap, against an origin that has already committed a 340 KB
5//! payload. This is that store, modelled rather than bound: the cap is checked
6//! on a value length computed from the event, and nothing is encoded.
7
8use alloc::format;
9use alloc::sync::Arc;
10use alloc::vec;
11use core::fmt;
12
13use happenstance_core::{
14    Event, EventId, EventType, MAX_EVENT_TYPE_LEN, MAX_TAG_LEN, MIN_SUPPORTED_EVENTS_PER_BATCH,
15    MIN_SUPPORTED_TAGS_PER_EVENT, RecordedAt, SequencePosition, StoreId,
16};
17use happenstance_sync::{
18    Ack, Classify, EventGroup, FailureClass, MemoryPeerError, MemoryResume, MemorySyncPeer,
19    PeerLimits, Pulled, PushBatch, ReplicatedEvent, SendSyncPeer,
20};
21use happenstance_testkit::Capability;
22
23use crate::fixture::compact_memory_peer;
24use crate::{Refusal, RefusalsOf, SyncFixture, Violation, oversized_push_refusal};
25
26/// The per-value cap of Turnstile peer D's KV store: 128 KiB.
27pub const KV_VALUE_CAP: usize = 128 * 1024;
28
29/// Bytes of a value that are not the event's type, tags or data: the origin
30/// `StoreId` (16), its position (8) and the recorded time (8).
31const KEY_OVERHEAD: usize = 32;
32
33/// What the envelope may occupy at the contract's floors: a type of
34/// `MAX_EVENT_TYPE_LEN` bytes and `MIN_SUPPORTED_TAGS_PER_EVENT` tags of
35/// `MAX_TAG_LEN` bytes each, and the key. 16,607 bytes.
36const ENVELOPE_ALLOWANCE: usize =
37    MAX_EVENT_TYPE_LEN + MIN_SUPPORTED_TAGS_PER_EVENT * MAX_TAG_LEN + KEY_OVERHEAD;
38
39/// The payload this peer declares: what a value holds once the envelope is
40/// reserved. 114,465 bytes.
41const DECLARED_EVENT_BYTES: usize = KV_VALUE_CAP - ENVELOPE_ALLOWANCE;
42
43/// 1 MiB, above the 340 KB seat map, so that what refuses the seat map is the
44/// value cap and not the batch limit.
45const DECLARED_BATCH_BYTES: usize = 1024 * 1024;
46
47/// The bytes Turnstile's committed seat map carries: 340,000.
48pub(crate) const TURNSTILE_SEAT_MAP_BYTES: usize = 340_000;
49
50const SEAT_MAP_PUBLISHED: EventType = EventType::from_static("SeatMapPublished");
51
52/// The origin of the seat map [`KvCappedFixture::refusals`] pushes.
53const REFUSAL_ORIGIN: StoreId = StoreId::from_bytes([0xD0; 16]);
54
55/// What a KV value holding `event` would occupy: its data and metadata, its
56/// type, its tags and [`KEY_OVERHEAD`].
57///
58/// Saturating, because a sum that wrapped would admit what it should refuse.
59fn value_len(event: &ReplicatedEvent) -> usize {
60    let tags = event
61        .event
62        .tags()
63        .iter()
64        .map(|tag| tag.as_str().len())
65        .fold(0, usize::saturating_add);
66    event
67        .payload_len()
68        .saturating_add(event.event.event_type().as_str().len())
69        .saturating_add(tags)
70        .saturating_add(KEY_OVERHEAD)
71}
72
73/// Turnstile's committed seat map: [`TURNSTILE_SEAT_MAP_BYTES`] of opaque zero
74/// bytes (SY-35), the first event in `origin`'s log.
75///
76/// # Errors
77///
78/// A [`Violation`] of `clause` if the event cannot be built. Unreachable: the
79/// type is a valid literal.
80pub(crate) fn turnstile_seat_map(
81    origin: StoreId,
82    clause: &'static str,
83) -> Result<ReplicatedEvent, Violation> {
84    let event = Event::new(SEAT_MAP_PUBLISHED, vec![0_u8; TURNSTILE_SEAT_MAP_BYTES])
85        .map_err(|error| Violation::new(clause, format!("the seat map is invalid: {error}")))?;
86    Ok(ReplicatedEvent::new(
87        EventId::new(origin, SequencePosition::FIRST),
88        RecordedAt::from_millis(1_800_000_000_000),
89        event,
90    ))
91}
92
93/// What a [`KvCappedPeer`] declares.
94fn declared() -> PeerLimits {
95    let mut limits = PeerLimits::minimum();
96    limits.max_event_bytes = DECLARED_EVENT_BYTES;
97    limits.max_batch_bytes = DECLARED_BATCH_BYTES;
98    limits.max_batch_events = MIN_SUPPORTED_EVENTS_PER_BATCH;
99    limits
100}
101
102/// A [`SyncFixture`] whose peer stores each event as one KV value of at most
103/// [`KV_VALUE_CAP`] bytes: Turnstile's peer D, the shape SY-18's marker names.
104///
105/// # What it declares, and why
106///
107/// A value holds the event's type, its tags and a 32-byte key as well as its
108/// payload, and [`PeerLimits`] has a field for the payload alone. So the peer
109/// reserves the envelope at the contract's floors and declares what is left:
110///
111/// | | bytes |
112/// |---|---:|
113/// | value cap | 131,072 |
114/// | type, at `MAX_EVENT_TYPE_LEN` | 255 |
115/// | 64 tags, at `MAX_TAG_LEN` each | 16,320 |
116/// | key: origin, position, recorded time | 32 |
117/// | **declared `max_event_bytes`** | **114,465** |
118///
119/// An event at every floor at once fills a value exactly, and is accepted. The
120/// declaration clears VT-21's 65,536-byte floor with 48,929 bytes to spare, and
121/// sits in the peer set's spread as: floor 65,536 = [`MemorySyncPeer`] < this
122/// peer 114,465 < the Neon store's 131,072 < 1 MiB for SQLite, Postgres and
123/// Cloudflare.
124///
125/// # What it refuses
126///
127/// A push holding any event whose value would exceed the cap is refused whole,
128/// before anything is stored, with [`KvPeerError::ValueTooLarge`], class
129/// [`FailureClass::Park`]. It never truncates. A push over `max_batch_bytes`
130/// is refused by the store behind the cap, class [`FailureClass::Split`].
131#[derive(Debug, Clone)]
132pub struct KvCappedFixture {
133    peer: Arc<MemorySyncPeer>,
134}
135
136impl KvCappedFixture {
137    /// A fixture over a fresh capped peer.
138    #[must_use]
139    pub fn new() -> Self {
140        Self {
141            peer: Arc::new(MemorySyncPeer::with_limits(
142                StoreId::from_bytes([0xC4; 16]),
143                declared(),
144            )),
145        }
146    }
147}
148
149impl Default for KvCappedFixture {
150    fn default() -> Self {
151        Self::new()
152    }
153}
154
155impl SyncFixture for KvCappedFixture {
156    type Peer = KvCappedPeer;
157
158    /// Declined, by incapacity, as the reference fixture's is.
159    const REOPEN: Capability = Capability::declined(
160        "the KV-capped reference peer keeps its log in process memory, behind the cap, and \
161         has no medium outside the process a reopen could read back",
162    );
163
164    async fn connect(&self) -> Self::Peer {
165        KvCappedPeer {
166            inner: Arc::clone(&self.peer),
167        }
168    }
169
170    /// The oversized push, declared `Split`, and the Turnstile seat map,
171    /// declared `Park`: 340,000 bytes is under the batch limit and over a
172    /// value, so it is the value cap that refuses it.
173    async fn refusals(&self, peer: &Self::Peer) -> RefusalsOf<Self::Peer> {
174        let mut refusals = oversized_push_refusal(peer).await?;
175        let seat_map = turnstile_seat_map(REFUSAL_ORIGIN, "SY-36")?;
176        let batch = PushBatch::new(vec![EventGroup::new(None, vec![seat_map])]);
177        refusals.push(Refusal {
178            provoked_by: "the Turnstile seat map, 340,000 bytes against a 131,072-byte value",
179            declared: FailureClass::Park,
180            outcome: peer.push(&batch).await.map(drop),
181        });
182        Ok(refusals)
183    }
184
185    /// The capped peer compacts as the reference peer behind it does: a cap
186    /// on values says nothing about retention.
187    const COMPACTION: Capability = Capability::SUPPORTED;
188
189    async fn compact_recorded_before(
190        &self,
191        peer: &Self::Peer,
192        cutoff: RecordedAt,
193    ) -> Result<(), Violation> {
194        compact_memory_peer(&peer.inner, cutoff)
195    }
196}
197
198/// One handle onto a [`KvCappedFixture`]'s peer.
199///
200/// `Arc` for the reason [`MemorySyncHandle`](crate::MemorySyncHandle) gives:
201/// many handles share one log, and the peer stays `Send + Sync`.
202#[derive(Debug, Clone)]
203pub struct KvCappedPeer {
204    inner: Arc<MemorySyncPeer>,
205}
206
207impl SendSyncPeer for KvCappedPeer {
208    type Error = KvPeerError;
209    type Resume = MemoryResume;
210
211    async fn pull(&self, from: Option<&Self::Resume>) -> Result<Pulled<Self::Resume>, Self::Error> {
212        SendSyncPeer::pull(&*self.inner, from)
213            .await
214            .map_err(KvPeerError::Store)
215    }
216
217    /// Checks every value before storing any, so a refused push stores nothing
218    /// and a group is never split by the cap.
219    async fn push(&self, batch: &PushBatch) -> Result<Ack, Self::Error> {
220        if let Some((event, len)) = batch
221            .events()
222            .map(|event| (event, value_len(event)))
223            .find(|(_, len)| *len > KV_VALUE_CAP)
224        {
225            return Err(KvPeerError::ValueTooLarge {
226                id: event.id,
227                value_len: len,
228                cap: KV_VALUE_CAP,
229            });
230        }
231        SendSyncPeer::push(&*self.inner, batch)
232            .await
233            .map_err(KvPeerError::Store)
234    }
235
236    fn limits(&self) -> PeerLimits {
237        SendSyncPeer::limits(&*self.inner)
238    }
239}
240
241/// How a [`KvCappedPeer`] fails.
242#[derive(Debug)]
243#[non_exhaustive]
244pub enum KvPeerError {
245    /// One event's value would exceed the cap. Nothing in the push was stored.
246    ValueTooLarge {
247        /// The event that cannot land here.
248        id: EventId,
249        /// What its value would occupy.
250        value_len: usize,
251        /// What a value may occupy.
252        cap: usize,
253    },
254    /// The in-memory store behind the cap refused: an oversized batch, or a
255    /// poisoned lock.
256    Store(MemoryPeerError),
257}
258
259impl fmt::Display for KvPeerError {
260    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
261        match self {
262            Self::ValueTooLarge { id, value_len, cap } => write!(
263                f,
264                "event {id} needs a value of {value_len} bytes, over this peer's cap of {cap}"
265            ),
266            Self::Store(_) => f.write_str("the store behind the value cap refused"),
267        }
268    }
269}
270
271impl core::error::Error for KvPeerError {
272    fn source(&self) -> Option<&(dyn core::error::Error + 'static)> {
273        match self {
274            Self::ValueTooLarge { .. } => None,
275            Self::Store(inner) => Some(inner),
276        }
277    }
278}
279
280impl Classify for KvPeerError {
281    fn class(&self) -> FailureClass {
282        match self {
283            // No retry or split makes this event fit a value (VT-25).
284            Self::ValueTooLarge { .. } => FailureClass::Park,
285            Self::Store(inner) => inner.class(),
286        }
287    }
288}
289
290#[cfg(test)]
291mod tests {
292    use alloc::format;
293    use alloc::vec;
294    use alloc::vec::Vec;
295
296    use happenstance_core::{
297        Event, EventId, EventType, MAX_EVENT_TYPE_LEN, MAX_TAG_LEN, MIN_SUPPORTED_EVENT_DATA_LEN,
298        MIN_SUPPORTED_TAGS_PER_EVENT, RecordedAt, SequencePosition, StoreId, Tag, Tags,
299    };
300    use happenstance_sync::{
301        Classify, EventGroup, FailureClass, MemoryPeerError, PushBatch, ReplicatedEvent,
302        SendSyncPeer,
303    };
304    use happenstance_testkit::block_on;
305
306    use super::{
307        KV_VALUE_CAP, KvCappedFixture, KvCappedPeer, KvPeerError, TURNSTILE_SEAT_MAP_BYTES,
308        turnstile_seat_map,
309    };
310    use crate::{SyncFixture, batch_over_the_limit};
311
312    const ORIGIN: StoreId = StoreId::from_bytes([0xE1; 16]);
313    const SMALL_ORIGIN: StoreId = StoreId::from_bytes([0xE2; 16]);
314
315    fn peer() -> KvCappedPeer {
316        block_on(KvCappedFixture::new().connect())
317    }
318
319    /// An event at every envelope floor the contract sets: a type of
320    /// `MAX_EVENT_TYPE_LEN` bytes and `MIN_SUPPORTED_TAGS_PER_EVENT` distinct
321    /// tags of `MAX_TAG_LEN` bytes, carrying `size` bytes of data.
322    fn at_the_floors(size: usize) -> ReplicatedEvent {
323        let event_type =
324            EventType::new("T".repeat(MAX_EVENT_TYPE_LEN)).expect("255 bytes is a valid type");
325        let tags: Tags = (0..MIN_SUPPORTED_TAGS_PER_EVENT)
326            .map(|i| Tag::new(format!("{i:0>255}")).expect("255 digits is a valid tag"))
327            .collect();
328        assert_eq!(tags.len(), MIN_SUPPORTED_TAGS_PER_EVENT);
329        let event = Event::new(event_type, vec![0_u8; size])
330            .expect("the type is valid")
331            .with_tags(tags);
332        ReplicatedEvent::new(
333            EventId::new(ORIGIN, SequencePosition::FIRST),
334            RecordedAt::from_millis(1_800_000_000_000),
335            event,
336        )
337    }
338
339    fn small() -> ReplicatedEvent {
340        ReplicatedEvent::new(
341            EventId::new(SMALL_ORIGIN, SequencePosition::FIRST),
342            RecordedAt::from_millis(1_800_000_000_000),
343            Event::new(EventType::from_static("Small"), vec![1_u8; 8]).expect("valid"),
344        )
345    }
346
347    fn held(peer: &KvCappedPeer) -> Vec<EventGroup> {
348        let pulled = block_on(peer.pull(None)).expect("an in-memory pull succeeds");
349        pulled.batch.groups
350    }
351
352    #[test]
353    fn the_declaration_reserves_the_envelope_at_the_contract_floors() {
354        let limits = peer().limits();
355        assert_eq!(limits.max_event_bytes, 114_465);
356        assert!(limits.max_event_bytes >= MIN_SUPPORTED_EVENT_DATA_LEN);
357        assert_eq!(
358            MAX_TAG_LEN, 255,
359            "the arithmetic below assumes the contract's tag bound"
360        );
361    }
362
363    #[test]
364    fn an_event_at_every_floor_fills_a_value_exactly() {
365        let peer = peer();
366        let event = at_the_floors(peer.limits().max_event_bytes);
367        assert_eq!(super::value_len(&event), KV_VALUE_CAP);
368
369        let batch = PushBatch::new(vec![EventGroup::new(None, vec![event.clone()])]);
370        let ack = block_on(peer.push(&batch)).expect("exactly the cap is accepted");
371        assert_eq!(ack.appended, 1);
372        assert_eq!(held(&peer), vec![EventGroup::new(None, vec![event])]);
373    }
374
375    #[test]
376    fn one_byte_more_is_refused_whole_and_parked() {
377        let peer = peer();
378        let event = at_the_floors(peer.limits().max_event_bytes + 1);
379        let id = event.id;
380        let batch = PushBatch::new(vec![EventGroup::new(None, vec![small(), event])]);
381
382        let error = block_on(peer.push(&batch)).expect_err("one byte over the cap is refused");
383        assert!(
384            matches!(
385                error,
386                KvPeerError::ValueTooLarge { id: refused, value_len: 131_073, cap: 131_072 }
387                    if refused == id
388            ),
389            "{error:?}"
390        );
391        assert_eq!(error.class(), FailureClass::Park);
392        assert_eq!(
393            held(&peer),
394            Vec::new(),
395            "nothing in a refused push is stored"
396        );
397    }
398
399    #[test]
400    fn the_seat_map_is_refused_for_its_value_not_the_batch() {
401        let peer = peer();
402        let seat_map = turnstile_seat_map(ORIGIN, "SY-18").expect("the seat map builds");
403        let batch = PushBatch::new(vec![EventGroup::new(None, vec![seat_map])]);
404        assert!(batch.payload_len() <= peer.limits().max_batch_bytes);
405
406        // 340,000 of data, a 16-byte type, no tags and the 32-byte key.
407        let expected = TURNSTILE_SEAT_MAP_BYTES + "SeatMapPublished".len() + 32;
408        assert_eq!(expected, 340_048);
409
410        let error = block_on(peer.push(&batch)).expect_err("340 KB is over a 128 KiB value");
411        assert!(
412            matches!(
413                error,
414                KvPeerError::ValueTooLarge { value_len, cap: KV_VALUE_CAP, .. }
415                    if value_len == expected
416            ),
417            "{error:?}"
418        );
419    }
420
421    #[test]
422    fn an_oversized_batch_is_split() {
423        let peer = peer();
424        let batch = batch_over_the_limit(&peer.limits()).expect("1 MiB is under the ceiling");
425
426        let error = block_on(peer.push(&batch)).expect_err("one byte over the batch limit");
427        assert!(
428            matches!(
429                error,
430                KvPeerError::Store(MemoryPeerError::BatchTooLarge { .. })
431            ),
432            "{error:?}"
433        );
434        assert_eq!(error.class(), FailureClass::Split);
435    }
436}