Skip to main content

xs/store/
mod.rs

1//! The event stream store.
2//!
3//! A [`Store`] is an append-only log of [`Frame`]s persisted to a directory on
4//! disk. Append events with [`Store::append`], replay and follow them with
5//! [`Store::read`], and stash payload bytes in the content-addressed store with
6//! the `cas_*` methods.
7//!
8//! ## Topics
9//!
10//! Every frame has a dot-delimited `topic` (for example `clip.add`). Topics form
11//! a hierarchy: a reader can ask for an exact topic, a prefix wildcard like
12//! `clip.*`, `*` for everything, or a comma-separated list of such patterns
13//! (`game.move.*,game.create`). See [`validate_topic`](crate::store::validate_topic)
14//! for the allowed characters and [`ReadOptions::topic`] for querying.
15//!
16//! ## Retention
17//!
18//! Each frame carries a [`TTL`] that controls how long it is kept: forever, for
19//! a fixed duration, only the last N per topic, or ephemeral (broadcast to live
20//! readers but never stored). A `time:` frame is indexed by its expiry and a
21//! background sweeper removes it within one sweep interval (the default, one
22//! second, is set with [`StoreOptions::ttl_sweep`]). Reads never return an
23//! expired frame, even one the sweeper has not reached yet.
24//!
25//! A `last:n` topic keeps a live frame count, so an append carrying `last:n`
26//! knows how far over the topic is without scanning it, and trims in its own
27//! commit. Appends without one do not trim, so a topic can grow between them.
28//! The count is written in the same batch as the frames it counts. A store
29//! written before counts existed opens all the same: each `last:n` topic is
30//! counted from its index the first time a `last:n` frame lands on it.
31//!
32//! ## Durability
33//!
34//! Every append commits to the on-disk journal before it returns, so a process
35//! crash loses nothing. Only power loss or a kernel crash can lose the part of
36//! the journal not yet fsynced, and recovery then yields a stable prefix of the
37//! stream. An [`Fsync`] policy, set with [`Store::with_fsync`], decides when
38//! that fsync happens: after every append, on a timer (the default, one
39//! second), or never. [`Store::flush`] fsyncs on demand.
40
41mod fsync;
42pub use fsync::*;
43mod ttl;
44pub use ttl::*;
45
46#[cfg(test)]
47mod tests;
48
49use std::collections::{HashMap, HashSet};
50use std::ops::Bound;
51use std::path::PathBuf;
52use std::time::Duration;
53
54use tokio::sync::broadcast;
55use tokio::sync::mpsc::{self, UnboundedReceiver, UnboundedSender};
56
57use std::sync::atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering};
58use std::sync::{Arc, Mutex};
59
60use nu_protocol::engine::EngineState;
61use scru128::Scru128Id;
62
63use serde::{Deserialize, Deserializer, Serialize};
64
65use fjall::{
66    config::{BlockSizePolicy, HashRatioPolicy, RestartIntervalPolicy},
67    Database, Error as FjallError, Keyspace, KeyspaceCreateOptions, OwnedWriteBatch, PersistMode,
68};
69
70/// Error returned when opening a [`Store`].
71#[derive(Debug)]
72pub enum StoreError {
73    /// The store directory is already open in another process.
74    Locked,
75    /// The store on disk is stamped with a format version this build cannot
76    /// read: one written by a newer xs. A store from before versions existed
77    /// is not refused: it is stamped and opens.
78    Version {
79        /// The version found on disk.
80        found: u32,
81        /// The version this build writes and reads.
82        wanted: u32,
83    },
84    /// An error from the underlying `fjall` database.
85    Other(FjallError),
86}
87
88impl std::fmt::Display for StoreError {
89    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90        match self {
91            StoreError::Locked => write!(f, "Store is locked by another process"),
92            StoreError::Version { found, wanted } => write!(
93                f,
94                "Store format {found}, but this build reads format {wanted}: \
95                 the store was written by a newer xs"
96            ),
97            StoreError::Other(e) => write!(f, "{e}"),
98        }
99    }
100}
101
102impl std::error::Error for StoreError {}
103
104/// A single event in the stream.
105///
106/// A frame is metadata; the payload bytes (if any) live in the content-addressed
107/// store and are referenced by [`hash`](Frame::hash). Build one with the
108/// [`bon`](https://docs.rs/bon) builder, where the topic is the required
109/// starting argument:
110///
111/// ```
112/// use xs::{Frame, TTL};
113///
114/// let frame = Frame::builder("clip.add")
115///     .meta(serde_json::json!({ "source": "keyboard" }))
116///     .ttl(TTL::Last(100))
117///     .build();
118///
119/// assert_eq!(frame.topic, "clip.add");
120/// ```
121///
122/// The [`id`](Frame::id) is assigned by [`Store::append`] at write time, so the
123/// value you set on a builder is ignored when appending.
124#[derive(PartialEq, Eq, Serialize, Deserialize, Clone, Default, bon::Builder)]
125pub struct Frame {
126    /// Dot-delimited topic this frame belongs to (for example `clip.add`).
127    ///
128    /// Must satisfy [`validate_topic`]; [`Store::append`] rejects invalid topics.
129    #[builder(start_fn, into)]
130    pub topic: String,
131    /// Time-sortable identifier. Assigned by [`Store::append`]; any value set
132    /// before appending is overwritten.
133    #[builder(default)]
134    pub id: Scru128Id,
135    /// Integrity hash of the payload in the content-addressed store, if this
136    /// frame has one. Produce it with [`Store::cas_insert`].
137    pub hash: Option<ssri::Integrity>,
138    /// Arbitrary JSON metadata carried inline with the frame.
139    pub meta: Option<serde_json::Value>,
140    /// Retention policy for this frame. Defaults to [`TTL::Forever`] when unset.
141    pub ttl: Option<TTL>,
142}
143
144use std::fmt;
145
146impl fmt::Debug for Frame {
147    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
148        f.debug_struct("Frame")
149            .field("id", &format!("{id}", id = self.id))
150            .field("topic", &self.topic)
151            .field("hash", &self.hash.as_ref().map(|x| format!("{x}")))
152            .field("meta", &self.meta)
153            .field("ttl", &self.ttl)
154            .finish()
155    }
156}
157
158impl<'de> Deserialize<'de> for FollowOption {
159    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
160    where
161        D: Deserializer<'de>,
162    {
163        let s: String = Deserialize::deserialize(deserializer)?;
164        if s.is_empty() || s == "yes" {
165            Ok(FollowOption::On)
166        } else if let Ok(duration) = s.parse::<u64>() {
167            Ok(FollowOption::WithHeartbeat(Duration::from_millis(duration)))
168        } else {
169            match s.as_str() {
170                "true" => Ok(FollowOption::On),
171                "false" | "no" => Ok(FollowOption::Off),
172                _ => Err(serde::de::Error::custom("Invalid value for follow option")),
173            }
174        }
175    }
176}
177
178fn deserialize_bool<'de, D>(deserializer: D) -> Result<bool, D::Error>
179where
180    D: Deserializer<'de>,
181{
182    let s: String = Deserialize::deserialize(deserializer)?;
183    match s.as_str() {
184        "false" | "no" | "0" => Ok(false),
185        _ => Ok(true),
186    }
187}
188
189/// Options controlling a [`Store::read`] or [`Store::read_sync`] call.
190///
191/// Defaults replay every stored frame once, oldest first, then stop. Build a
192/// query with the [`bon`](https://docs.rs/bon) builder:
193///
194/// ```
195/// use xs::{ReadOptions, FollowOption};
196///
197/// // Replay history for one topic, then keep streaming new appends.
198/// let opts = ReadOptions::builder()
199///     .topic("clip.*".to_string())
200///     .follow(FollowOption::On)
201///     .build();
202/// ```
203#[derive(PartialEq, Deserialize, Clone, Debug, Default, bon::Builder)]
204pub struct ReadOptions {
205    /// Whether to keep streaming live appends after history is replayed.
206    /// Defaults to [`FollowOption::Off`].
207    #[serde(default)]
208    #[builder(default)]
209    pub follow: FollowOption,
210    /// Skip historical frames and emit only appends made after the read starts.
211    #[serde(default, deserialize_with = "deserialize_bool")]
212    #[builder(default)]
213    pub new: bool,
214    /// Start after this ID (exclusive).
215    #[serde(rename = "after")]
216    pub after: Option<Scru128Id>,
217    /// Start from this ID (inclusive).
218    pub from: Option<Scru128Id>,
219    /// Stop after emitting this many historical frames.
220    pub limit: Option<usize>,
221    /// Return the last N frames (most recent), in chronological order.
222    pub last: Option<usize>,
223    /// Restrict to one or more topic patterns, comma-separated. Each pattern
224    /// is an exact name, a `prefix.*` wildcard, or `*` for all, e.g.
225    /// `clip.add` or `game.move.*,game.create`. Commas are a safe separator
226    /// because [`validate_topic`] forbids them in topic names.
227    pub topic: Option<String>,
228}
229
230/// A single topic pattern: an exact topic name or a `prefix.*` wildcard.
231#[derive(Clone, Debug, PartialEq)]
232pub enum Pattern {
233    /// Matches the topic exactly.
234    Exact(String),
235    /// Matches any topic starting with this prefix. Stored with the trailing
236    /// dot, so `a.*` becomes `Prefix("a.")` and matches `a.b` but not `a`.
237    Prefix(String),
238}
239
240impl Pattern {
241    fn matches(&self, topic: &str) -> bool {
242        match self {
243            Pattern::Exact(t) => t == topic,
244            Pattern::Prefix(p) => topic.starts_with(p.as_str()),
245        }
246    }
247}
248
249/// A parsed topic filter: the value of [`ReadOptions::topic`] split on commas
250/// into individual [`Pattern`]s.
251///
252/// Note that synthetic control frames emitted by a following read --
253/// `xs.threshold` and heartbeat `xs.pulse` -- are delivered directly on the
254/// read channel and are never subject to this filter.
255#[derive(Clone, Debug, PartialEq)]
256pub enum TopicFilter {
257    /// Match every topic (no filter, or some element was `*`).
258    All,
259    /// Match topics satisfying at least one of these patterns.
260    Patterns(Vec<Pattern>),
261}
262
263impl TopicFilter {
264    /// Parse a comma-separated pattern list. Empty elements are ignored; an
265    /// empty or all-`*` spec yields [`TopicFilter::All`].
266    pub fn parse(spec: &str) -> TopicFilter {
267        let mut patterns = Vec::new();
268        for part in spec.split(',') {
269            let part = part.trim();
270            if part.is_empty() {
271                continue;
272            }
273            if part == "*" {
274                return TopicFilter::All;
275            }
276            if let Some(prefix) = part.strip_suffix(".*") {
277                patterns.push(Pattern::Prefix(format!("{prefix}.")));
278            } else {
279                patterns.push(Pattern::Exact(part.to_string()));
280            }
281        }
282        if patterns.is_empty() {
283            TopicFilter::All
284        } else {
285            TopicFilter::Patterns(patterns)
286        }
287    }
288
289    /// Parse an optional spec; `None` means no filter.
290    pub fn from_option(spec: Option<&str>) -> TopicFilter {
291        match spec {
292            Some(s) => TopicFilter::parse(s),
293            None => TopicFilter::All,
294        }
295    }
296
297    /// Does `topic` match this filter?
298    pub fn matches(&self, topic: &str) -> bool {
299        match self {
300            TopicFilter::All => true,
301            TopicFilter::Patterns(patterns) => patterns.iter().any(|p| p.matches(topic)),
302        }
303    }
304}
305
306/// K-way merge of per-pattern frame iterators, ordered by frame id, with
307/// dedupe when overlapping patterns yield the same frame from more than one
308/// iterator. Each input iterator must itself be sorted by id (ascending when
309/// `descending` is false, descending otherwise).
310struct MergeById<'a> {
311    iters: Vec<Box<dyn Iterator<Item = Frame> + 'a>>,
312    heap: std::collections::BinaryHeap<MergeEntry>,
313    descending: bool,
314    last_emitted: Option<Scru128Id>,
315}
316
317struct MergeEntry {
318    key: u128,
319    idx: usize,
320    frame: Frame,
321}
322
323impl PartialEq for MergeEntry {
324    fn eq(&self, other: &Self) -> bool {
325        self.key == other.key && self.idx == other.idx
326    }
327}
328impl Eq for MergeEntry {}
329impl PartialOrd for MergeEntry {
330    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
331        Some(self.cmp(other))
332    }
333}
334impl Ord for MergeEntry {
335    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
336        self.key.cmp(&other.key).then(self.idx.cmp(&other.idx))
337    }
338}
339
340/// BinaryHeap is a max-heap; for ascending merges flip the bits so the
341/// smallest id pops first.
342fn merge_key(id: &Scru128Id, descending: bool) -> u128 {
343    let raw = u128::from_be_bytes(id.to_bytes());
344    if descending {
345        raw
346    } else {
347        !raw
348    }
349}
350
351impl<'a> MergeById<'a> {
352    fn new(mut iters: Vec<Box<dyn Iterator<Item = Frame> + 'a>>, descending: bool) -> Self {
353        let mut heap = std::collections::BinaryHeap::with_capacity(iters.len());
354        for (idx, iter) in iters.iter_mut().enumerate() {
355            if let Some(frame) = iter.next() {
356                heap.push(MergeEntry {
357                    key: merge_key(&frame.id, descending),
358                    idx,
359                    frame,
360                });
361            }
362        }
363        MergeById {
364            iters,
365            heap,
366            descending,
367            last_emitted: None,
368        }
369    }
370}
371
372impl Iterator for MergeById<'_> {
373    type Item = Frame;
374
375    fn next(&mut self) -> Option<Frame> {
376        loop {
377            let entry = self.heap.pop()?;
378            if let Some(frame) = self.iters[entry.idx].next() {
379                self.heap.push(MergeEntry {
380                    key: merge_key(&frame.id, self.descending),
381                    idx: entry.idx,
382                    frame,
383                });
384            }
385            // Overlapping patterns can yield the same frame from more than
386            // one iterator; emit it once.
387            if self.last_emitted == Some(entry.frame.id) {
388                continue;
389            }
390            self.last_emitted = Some(entry.frame.id);
391            return Some(entry.frame);
392        }
393    }
394}
395
396impl ReadOptions {
397    /// Parse options from a URL query string (the form used by the HTTP API),
398    /// for example `follow=true&topic=clip.*&last=10`. `None` yields the
399    /// defaults.
400    pub fn from_query(query: Option<&str>) -> Result<Self, crate::error::Error> {
401        match query {
402            Some(q) => Ok(serde_urlencoded::from_str(q)?),
403            None => Ok(Self::default()),
404        }
405    }
406
407    /// Render these options back into a URL query string, the inverse of
408    /// [`from_query`](ReadOptions::from_query). Returns an empty string when no
409    /// options are set.
410    pub fn to_query_string(&self) -> String {
411        let mut params = Vec::new();
412
413        // Add follow parameter with heartbeat if specified
414        match self.follow {
415            FollowOption::Off => {}
416            FollowOption::On => params.push(("follow", "true".to_string())),
417            FollowOption::WithHeartbeat(duration) => {
418                params.push(("follow", duration.as_millis().to_string()));
419            }
420        }
421
422        // Add new if true
423        if self.new {
424            params.push(("new", "true".to_string()));
425        }
426
427        // Add after if present
428        if let Some(after) = self.after {
429            params.push(("after", after.to_string()));
430        }
431
432        // Add from if present
433        if let Some(from) = self.from {
434            params.push(("from", from.to_string()));
435        }
436
437        // Add limit if present
438        if let Some(limit) = self.limit {
439            params.push(("limit", limit.to_string()));
440        }
441
442        // Add last if present
443        if let Some(last) = self.last {
444            params.push(("last", last.to_string()));
445        }
446
447        if let Some(topic) = &self.topic {
448            params.push(("topic", topic.clone()));
449        }
450
451        // Return empty string if no params
452        if params.is_empty() {
453            String::new()
454        } else {
455            url::form_urlencoded::Serializer::new(String::new())
456                .extend_pairs(params)
457                .finish()
458        }
459    }
460}
461
462/// Whether a read keeps streaming after history is replayed.
463#[derive(Default, PartialEq, Clone, Debug)]
464pub enum FollowOption {
465    /// Stop once historical frames are exhausted.
466    #[default]
467    Off,
468    /// Replay history, then stream live appends indefinitely.
469    On,
470    /// Like [`On`](FollowOption::On), but also emit a periodic heartbeat frame
471    /// at the given interval so idle readers can detect a live connection.
472    WithHeartbeat(Duration),
473}
474
475#[derive(Debug)]
476enum GCTask {
477    CheckLastTTL {
478        topic: String,
479        keep: u32,
480    },
481    /// Remove every `time:` frame whose expiry has passed, up to
482    /// `MAX_SWEEP_PER_DRAIN`. Sent by the sweep tick.
483    Sweep,
484    Drain(tokio::sync::oneshot::Sender<()>),
485}
486
487/// A frame the gc worker is about to delete.
488enum Removal {
489    /// Only the id is known. The frame is fetched to learn its keys.
490    Id(Scru128Id),
491    /// An index hit that already carries every key the removal needs, so no
492    /// point read into `stream` is required. `expires_at` is `None` when the
493    /// frame has no `time:` ttl and so has no expiry index entry.
494    Indexed {
495        id: Scru128Id,
496        topic: String,
497        expires_at: Option<u64>,
498    },
499}
500
501impl Removal {
502    fn id(&self) -> Scru128Id {
503        match self {
504            Removal::Id(id) | Removal::Indexed { id, .. } => *id,
505        }
506    }
507}
508
509/// Where the next expiry sweep starts scanning. Everything below it has been
510/// swept, so the sweep steps over the tombstones earlier sweeps left instead
511/// of walking them again.
512///
513/// It only ever moves up to a key a sweep actually removed, and a sweep never
514/// looks past the frames that are due, so it can never come to rest above an
515/// entry that is still waiting for its expiry to pass. The one way an entry
516/// can appear below it is an index write, which
517/// [`note_indexed_expiry`](Store::note_indexed_expiry) moves it back for.
518#[derive(Clone, Copy, PartialEq, Eq, Debug)]
519struct SweepStart {
520    key: [u8; 24],
521    /// Whether `key` itself still has to be swept: false on the key a sweep
522    /// removed, true on one a later index write put back in play.
523    inclusive: bool,
524}
525
526impl SweepStart {
527    fn bound(&self) -> Bound<[u8; 24]> {
528        if self.inclusive {
529            Bound::Included(self.key)
530        } else {
531            Bound::Excluded(self.key)
532        }
533    }
534
535    /// Sort position, so two starts can be compared. An inclusive start sits
536    /// before an exclusive one on the same key: it covers one more entry.
537    fn rank(&self) -> ([u8; 24], u8) {
538        (self.key, u8::from(!self.inclusive))
539    }
540}
541
542/// Where a `last:n` trim scan of a topic starts. Below it the topic holds no
543/// live frame, only the tombstones of ones a trim or another removal path
544/// took, so a scan that starts here counts and trims exactly what a scan of
545/// the whole topic would.
546///
547/// A trim proves that of everything it removed. A scan that reaches the end of
548/// the topic without finding `keep` live frames proves it of everything under
549/// the oldest entry it saw, which is why the bound can be inclusive.
550///
551/// The one way a live frame can appear below it is an index write, which
552/// [`note_indexed_topic`](Store::note_indexed_topic) drops the floor for.
553#[derive(Clone, Copy, PartialEq, Eq, Debug)]
554struct TrimFloor {
555    id: Scru128Id,
556    /// Whether `id` itself is still on the topic and in scope for the scan.
557    inclusive: bool,
558}
559
560/// Options for opening a [`Store`]. Build one with the
561/// [`bon`](https://docs.rs/bon) builder; every field has a default.
562///
563/// ```
564/// use std::time::Duration;
565/// use xs::{Fsync, StoreOptions};
566///
567/// let options = StoreOptions::builder()
568///     .fsync(Fsync::Always)
569///     .ttl_sweep(Duration::from_millis(250))
570///     .build();
571/// assert_eq!(options.fsync, Fsync::Always);
572/// assert_eq!(StoreOptions::default().ttl_sweep, Duration::from_millis(1000));
573/// ```
574#[derive(Clone, Debug, PartialEq, Eq, bon::Builder)]
575pub struct StoreOptions {
576    /// When the journal is fsynced. See [`Fsync`].
577    #[builder(default)]
578    pub fsync: Fsync,
579    /// How often expired `time:` frames are swept from disk. Default 1000 ms.
580    /// Zero disables the sweeper; expired frames are then only hidden from
581    /// reads, never removed.
582    #[builder(default = Duration::from_millis(1000))]
583    pub ttl_sweep: Duration,
584}
585
586impl Default for StoreOptions {
587    fn default() -> Self {
588        StoreOptions::builder().build()
589    }
590}
591
592/// An append-only event stream backed by a directory on disk.
593///
594/// Open one with [`new`](Store::new). `Store` is cheaply [`Clone`]able: every
595/// clone shares the same underlying database, broadcast channel, and
596/// content-addressed store, so clone it freely across tasks and threads instead
597/// of wrapping it in an `Arc`.
598///
599/// See the [module docs](crate::store) for the topic and retention model.
600#[derive(Clone)]
601pub struct Store {
602    /// Directory backing this store (the path passed to [`new`](Store::new)).
603    pub path: PathBuf,
604    db: Database,
605    stream: Keyspace,
606    idx_topic: Keyspace,
607    /// `time:` frames keyed by expiry then id, valued by topic. The sweeper
608    /// range-scans it from [`sweep_start`](Store::sweep_start) up to now. See
609    /// [`idx_expiry_key`].
610    idx_expiry: Keyspace,
611    /// Where the next sweep resumes in `idx_expiry`; `None` is the start of
612    /// the index. In memory only: a reopened store sweeps from the start
613    /// again, which costs one walk of whatever tombstones outlived it and can
614    /// never skip a frame. See [`SweepStart`].
615    sweep_start: Arc<Mutex<Option<SweepStart>>>,
616    /// Per-topic `last:n` trim floor: every frame on the topic with an id at
617    /// or below it has been removed, so a trim scan stops there rather than
618    /// running on into the tombstones of the frames it trimmed last time. In
619    /// memory only, on the same reasoning as
620    /// [`sweep_start`](Store::sweep_start). See
621    /// [`last_overflow`](Store::last_overflow).
622    trim_floor: Arc<Mutex<HashMap<String, TrimFloor>>>,
623    broadcast_tx: broadcast::Sender<Frame>,
624    gc_tx: UnboundedSender<GCTask>,
625    /// Joins the background workers when the last caller-held clone drops.
626    /// Declared after `gc_tx` on purpose: fields drop in order, so the gc
627    /// channel closes before the join, and the gc worker can exit.
628    workers: Option<Arc<Workers>>,
629    /// Serialises every write that changes a topic's live frame population,
630    /// so a `last:n` count and the frames it counts can never disagree.
631    ///
632    /// Held by [`append`](Store::append), which also assigns ids under it so
633    /// subscribers see them in order, by
634    /// [`insert_frame`](Store::insert_frame), and by
635    /// [`remove_many`](Store::remove_many). Two trims reading one count at
636    /// once is how a trim deletes frames it was told to keep.
637    write_lock: Arc<Mutex<()>>,
638    /// Small keyspace holding the format version and one row per `last:n`
639    /// topic's live frame count. See [`FORMAT_VERSION`] and [`count_key`].
640    meta: Keyspace,
641    /// Every `last:n` topic's live frame count. The arithmetic happens here;
642    /// the `meta` row is a projection of it, written in whatever batch changed
643    /// it, and read back only at open.
644    ///
645    /// A count reading low is harmless: the topic trims late. A count reading
646    /// high deletes frames the topic was told to keep, with no error and no
647    /// trace, which is why every path that moves one holds
648    /// [`write_lock`](Store::write_lock).
649    last_counts: Arc<Mutex<HashMap<String, u64>>>,
650    /// Runtime handle captured at [`new`](Store::new), used to spawn the follow
651    /// and heartbeat tasks from the now-sync [`read`](Store::read). `Handle` is
652    /// cheaply `Clone`, so every `Store` clone shares the same runtime.
653    rt: Option<tokio::runtime::Handle>,
654    /// Optional base engine the processors clone, set via [`with_base_engine`].
655    /// `None` falls back to `Engine::new()`. See
656    /// [`prepared_base`](crate::nu::prepared_base) and ADR 0007.
657    base_engine: Option<Arc<EngineState>>,
658    /// Fsync policy and dirty flag, shared by every clone and the fsync worker.
659    fsync: Arc<FsyncState>,
660    /// Counters about this store's own work, shared by every clone and by
661    /// the gc worker. See [`StoreStats`].
662    stats: Arc<StoreStats>,
663}
664
665/// The store format this build writes and reads.
666///
667/// Bumped whenever an existing store stops being readable: [`Store::open`]
668/// refuses a store stamped with any other version. Version 1 is the first to
669/// keep a live frame count per `last:n` topic. A store from before it has no
670/// stamp, and opens: see [`Store::open`].
671const FORMAT_VERSION: u32 = 1;
672
673/// The `meta` key holding [`FORMAT_VERSION`].
674const META_VERSION: &[u8] = b"version";
675
676/// The `meta` key prefix under which each `last:n` topic's live frame count
677/// lives. A topic cannot contain a null byte, so nothing else can collide
678/// with these and `meta.prefix(COUNT_PREFIX)` finds exactly them.
679const COUNT_PREFIX: &[u8] = b"count\0";
680
681/// The `meta` key holding `topic`'s live frame count.
682fn count_key(topic: &str) -> Vec<u8> {
683    let mut key = Vec::with_capacity(COUNT_PREFIX.len() + topic.len());
684    key.extend_from_slice(COUNT_PREFIX);
685    key.extend_from_slice(topic.as_bytes());
686    key
687}
688
689/// Read every `last:n` topic's count out of `meta`. One pass over as many
690/// rows as there are such topics, which is the whole recovery story: the
691/// counts were written in the same batch as the frames they count, so they
692/// are correct as of the last commit and there is nothing to reconstruct.
693fn load_last_counts(meta: &Keyspace) -> Result<HashMap<String, u64>, FjallError> {
694    let mut counts = HashMap::new();
695    for guard in meta.prefix(COUNT_PREFIX) {
696        let (key, value) = guard.into_inner()?;
697        let Some(topic) = key.get(COUNT_PREFIX.len()..) else {
698            continue;
699        };
700        let (Ok(topic), Ok(count)) = (
701            std::str::from_utf8(topic),
702            <[u8; 8]>::try_from(value.as_ref()).map(u64::from_be_bytes),
703        ) else {
704            continue;
705        };
706        counts.insert(topic.to_owned(), count);
707    }
708    Ok(counts)
709}
710
711/// Counters the store keeps about its own work, always on.
712///
713/// Relaxed atomics on paths that already touch the database, so the cost is
714/// noise next to the work being counted. Cumulative for the life of the
715/// process, with no way to reset: a caller wanting a rate subtracts two
716/// reads.
717#[derive(Debug, Default)]
718pub struct StoreStats {
719    /// Frames accepted by [`append`](Store::append), including ephemeral ones
720    /// that were broadcast but never stored.
721    pub appends: AtomicUsize,
722    /// Frames pulled from a keyspace iterator by a read. Larger than the
723    /// number returned whenever a read filters: the gap is wasted work.
724    pub frames_scanned: AtomicUsize,
725    /// Point reads into `stream`. A topic read does one per frame it returns,
726    /// so this over `frames_scanned` says how well the index is filtering.
727    pub stream_reads: AtomicUsize,
728    /// Frames removed by [`remove_many`](Store::remove_many).
729    pub removed_frames: AtomicUsize,
730    /// Batches committed by [`remove_many`](Store::remove_many). One per gc
731    /// drain that had anything to do.
732    pub remove_commits: AtomicUsize,
733    /// `idx_topic` entries a `last:n` trim visited. The number this whole
734    /// design is about: it used to be `keep` on every append, and is now the
735    /// number of frames actually being removed.
736    pub trim_scanned: AtomicUsize,
737    /// Times the gc worker drained its queue.
738    pub gc_drains: AtomicUsize,
739    /// Nanoseconds the gc worker spent inside a drain. Against `gc_drains`
740    /// this is the cost of retention, which is otherwise invisible.
741    pub gc_nanos: AtomicU64,
742}
743
744/// A serializable read of [`StoreStats`]. See its fields for what each counts.
745#[derive(Debug, Clone, serde::Serialize)]
746pub struct StoreStatsSnapshot {
747    pub appends: u64,
748    pub frames_scanned: u64,
749    pub stream_reads: u64,
750    pub removed_frames: u64,
751    pub remove_commits: u64,
752    pub trim_scanned: u64,
753    pub gc_drains: u64,
754    pub gc_nanos: u64,
755}
756
757impl StoreStats {
758    fn snapshot(&self) -> StoreStatsSnapshot {
759        let n = |c: &AtomicUsize| c.load(Ordering::Relaxed) as u64;
760        StoreStatsSnapshot {
761            appends: n(&self.appends),
762            frames_scanned: n(&self.frames_scanned),
763            stream_reads: n(&self.stream_reads),
764            removed_frames: n(&self.removed_frames),
765            remove_commits: n(&self.remove_commits),
766            trim_scanned: n(&self.trim_scanned),
767            gc_drains: n(&self.gc_drains),
768            gc_nanos: self.gc_nanos.load(Ordering::Relaxed),
769        }
770    }
771}
772
773/// Cache hit rates for one keyspace, each `None` until that layer has been
774/// asked for something.
775#[derive(Debug, Clone, serde::Serialize)]
776pub struct KeyspaceRates {
777    pub block_cache_hit: Option<f64>,
778    pub data_block_cache_hit: Option<f64>,
779    pub index_block_cache_hit: Option<f64>,
780    pub filter_block_cache_hit: Option<f64>,
781    pub table_file_cache_hit: Option<f64>,
782    /// Share of filter lookups that saved a read. Only counted when the
783    /// filter reports a miss: a filter costs nothing on a hit, so this is
784    /// what it is worth, not how often it ran.
785    pub filter_efficiency: Option<f64>,
786}
787
788/// A rate is meaningless with no observations behind it.
789fn rate(observations: usize, value: f64) -> Option<f64> {
790    (observations > 0).then_some(value)
791}
792
793/// A point-in-time read of one keyspace's cache and filter counters.
794///
795/// Every rate is a fraction in `0.0..=1.0`, or `0.0` when nothing has been
796/// asked of that layer yet. The counters are cumulative since the process
797/// started; fjall has no way to reset them, so a caller comparing two reads
798/// should subtract.
799#[derive(Debug, Clone, serde::Serialize)]
800pub struct KeyspaceMetrics {
801    pub keyspace: &'static str,
802
803    /// Hit rates, or `null` where nothing has been asked of that layer yet.
804    /// fjall returns 1.0 for a rate with no observations, which reads as a
805    /// perfect cache on a store that has done no work.
806    pub rates: KeyspaceRates,
807
808    pub filter_queries: usize,
809    pub io_skipped_by_filter: usize,
810
811    /// Blocks asked for, and how many of those reached the filesystem.
812    pub block_loads: usize,
813    pub block_load_io: usize,
814    pub data_block_io: u64,
815    pub index_block_io: u64,
816    pub filter_block_io: u64,
817}
818
819impl KeyspaceMetrics {
820    fn read(keyspace: &'static str, ks: &Keyspace) -> Self {
821        // `Keyspace::metrics` hands back an `lsm_tree::Metrics`, a type fjall
822        // does not re-export, so the reference is never named.
823        let m = ks.metrics();
824        Self {
825            keyspace,
826            rates: KeyspaceRates {
827                block_cache_hit: rate(m.block_loads(), m.block_cache_hit_rate()),
828                data_block_cache_hit: rate(
829                    m.data_block_load_count(),
830                    m.data_block_cache_hit_rate(),
831                ),
832                index_block_cache_hit: rate(
833                    m.index_block_load_count(),
834                    m.index_block_cache_hit_rate(),
835                ),
836                filter_block_cache_hit: rate(
837                    m.filter_block_load_count(),
838                    m.filter_block_cache_hit_rate(),
839                ),
840                // No public count of table opens, so borrow the block loads:
841                // no block was loaded means no file was opened either.
842                table_file_cache_hit: rate(m.block_loads(), m.table_file_cache_hit_rate()),
843                filter_efficiency: rate(m.filter_queries(), m.filter_efficiency()),
844            },
845            filter_queries: m.filter_queries(),
846            io_skipped_by_filter: m.io_skipped_by_filter(),
847            block_loads: m.block_loads(),
848            block_load_io: m.block_load_io_count(),
849            data_block_io: m.data_block_io(),
850            index_block_io: m.index_block_io(),
851            filter_block_io: m.filter_block_io(),
852        }
853    }
854}
855
856/// Joins the background workers when the last caller-held `Store` drops.
857/// The gc worker's own clone carries `None`, so it never joins itself. The
858/// ticks stop first: the sweep tick holds a gc sender, and the gc worker
859/// only exits once every sender is gone. Once the joins return every worker
860/// has dropped its database handle, the database is closed, and the path
861/// can be reopened.
862struct Workers {
863    gc: Option<std::thread::JoinHandle<()>>,
864    fsync: Option<Tick>,
865    sweep: Option<Tick>,
866}
867
868impl Drop for Workers {
869    fn drop(&mut self) {
870        drop(self.fsync.take());
871        drop(self.sweep.take());
872        if let Some(handle) = self.gc.take() {
873            let _ = handle.join();
874        }
875    }
876}
877
878/// A thread that runs a closure every `interval` until dropped. Dropping it
879/// sets `stop`, unparks the thread, and joins it, so the join waits for at
880/// most one in-flight run of the closure.
881struct Tick {
882    stop: Arc<AtomicBool>,
883    handle: Option<std::thread::JoinHandle<()>>,
884}
885
886impl Tick {
887    fn spawn(interval: Duration, mut run: impl FnMut() + Send + 'static) -> Tick {
888        let stop = Arc::new(AtomicBool::new(false));
889        let handle = std::thread::spawn({
890            let stop = stop.clone();
891            move || loop {
892                // park_timeout may wake early; the flags checked by each
893                // closure make that harmless.
894                std::thread::park_timeout(interval);
895                if stop.load(Ordering::Acquire) {
896                    break;
897                }
898                run();
899            }
900        });
901        Tick {
902            stop,
903            handle: Some(handle),
904        }
905    }
906}
907
908impl Drop for Tick {
909    fn drop(&mut self) {
910        self.stop.store(true, Ordering::Release);
911        if let Some(handle) = self.handle.take() {
912            handle.thread().unpark();
913            let _ = handle.join();
914        }
915    }
916}
917
918/// Shared fsync bookkeeping.
919struct FsyncState {
920    mode: Fsync,
921    /// Set after every commit under `interval`; the tick clears it.
922    dirty: AtomicBool,
923}
924
925impl Store {
926    /// Open the store at `path`, creating the directory layout if it does not
927    /// exist. Spawns a background worker that garbage-collects expired frames.
928    /// Uses the default [`Fsync`] policy; see [`with_fsync`](Store::with_fsync)
929    /// to choose one.
930    ///
931    /// # Errors
932    ///
933    /// Returns [`StoreError::Locked`] if another process already holds the
934    /// store open, or [`StoreError::Other`] for any other database error.
935    ///
936    /// ```no_run
937    /// use xs::Store;
938    ///
939    /// let store = Store::new("./clipboard-store".into())?;
940    /// # Ok::<(), xs::StoreError>(())
941    /// ```
942    pub fn new(path: PathBuf) -> Result<Store, StoreError> {
943        Store::open(path, StoreOptions::default())
944    }
945
946    /// Open the store at `path` with an explicit [`Fsync`] policy. Otherwise
947    /// the same as [`new`](Store::new).
948    ///
949    /// ```no_run
950    /// use xs::{Store, Fsync};
951    ///
952    /// let store = Store::with_fsync("./clipboard-store".into(), Fsync::Always)?;
953    /// # Ok::<(), xs::StoreError>(())
954    /// ```
955    pub fn with_fsync(path: PathBuf, fsync: Fsync) -> Result<Store, StoreError> {
956        Store::open(path, StoreOptions::builder().fsync(fsync).build())
957    }
958
959    /// Open the store at `path` with explicit [`StoreOptions`]. Otherwise the
960    /// same as [`new`](Store::new).
961    ///
962    /// ```no_run
963    /// use std::time::Duration;
964    /// use xs::{Store, StoreOptions};
965    ///
966    /// let options = StoreOptions::builder()
967    ///     .ttl_sweep(Duration::from_millis(250))
968    ///     .build();
969    /// let store = Store::open("./clipboard-store".into(), options)?;
970    /// # Ok::<(), xs::StoreError>(())
971    /// ```
972    pub fn open(path: PathBuf, options: StoreOptions) -> Result<Store, StoreError> {
973        let fsync = options.fsync;
974        let db = match Database::builder(path.join("fjall"))
975            .cache_size(32 * 1024 * 1024) // 32 MiB
976            // One worker cannot keep up: every append writes three keyspaces, each
977            // calls check_memtable_rotate, and all of them queue into the single
978            // shared channel that worker also has to drain. At 1, flushes starve --
979            // 1M appends put only 10.7% of their bytes into segments, and 1.0% with
980            // the sweeper also committing. See BUGS-FOUND.md.
981            .worker_threads(2)
982            .open()
983        {
984            Ok(db) => db,
985            Err(FjallError::Locked) => return Err(StoreError::Locked),
986            Err(e) => return Err(StoreError::Other(e)),
987        };
988
989        // Options for stream keyspace: point reads by frame ID
990        let stream_opts = || {
991            KeyspaceCreateOptions::default()
992                .max_memtable_size(8 * 1024 * 1024) // 8 MiB
993                .data_block_size_policy(BlockSizePolicy::all(16 * 1024)) // 16 KiB
994                .data_block_hash_ratio_policy(HashRatioPolicy::all(8.0))
995                .expect_point_read_hits(true)
996        };
997
998        // Options for idx_topic keyspace: prefix scans only
999        let idx_opts = || {
1000            KeyspaceCreateOptions::default()
1001                .max_memtable_size(8 * 1024 * 1024) // 8 MiB
1002                .data_block_size_policy(BlockSizePolicy::all(16 * 1024)) // 16 KiB
1003                .data_block_hash_ratio_policy(HashRatioPolicy::all(0.0)) // no point reads
1004                .expect_point_read_hits(true)
1005        };
1006
1007        // An idx_topic key is `<topic>\0<id>`, so one topic repeats across
1008        // every entry it has. A restart point writes a key in full instead of
1009        // against the one before it, so fewer of them is a smaller index, and
1010        // nothing binary-searches inside these blocks to pay for it.
1011        let idx_topic_opts =
1012            || idx_opts().data_block_restart_interval_policy(RestartIntervalPolicy::all(32));
1013
1014        // An idx_expiry key is `<expiry><id>`: consecutive keys share a prefix
1015        // only when frames expire in the same millisecond, so the same change
1016        // buys much less. Left at the default.
1017        // Small, and read once at open. Defaults are right for it.
1018        let meta_opts = KeyspaceCreateOptions::default;
1019
1020        // A store written before `meta` existed has a stream and no meta, so
1021        // no `last:n` counts. That needs no conversion: a topic with no count
1022        // is counted from its index the first time a `last:n` frame lands on
1023        // it (see [`Store::derive_count`]), exactly as a topic in a new store
1024        // is. So such a store is stamped with the current version below and
1025        // opens. Only a store stamped with a different version is refused.
1026        if db.keyspace_exists("stream") && !db.keyspace_exists("meta") {
1027            tracing::info!(
1028                version = FORMAT_VERSION,
1029                "store predates last:n counts: counting each last:n topic on first use"
1030            );
1031        }
1032
1033        let meta = db.keyspace("meta", meta_opts).unwrap();
1034        match meta.get(META_VERSION).map_err(StoreError::Other)? {
1035            Some(value) => {
1036                let found = <[u8; 4]>::try_from(value.as_ref())
1037                    .map(u32::from_be_bytes)
1038                    .unwrap_or(0);
1039                if found != FORMAT_VERSION {
1040                    return Err(StoreError::Version {
1041                        found,
1042                        wanted: FORMAT_VERSION,
1043                    });
1044                }
1045            }
1046            // A store with a meta keyspace and no version in it is one this
1047            // build just created, or one from before counts existed (above),
1048            // so stamp it.
1049            None => meta
1050                .insert(META_VERSION, FORMAT_VERSION.to_be_bytes())
1051                .map_err(StoreError::Other)?,
1052        }
1053
1054        let stream = db.keyspace("stream", stream_opts).unwrap();
1055        let idx_topic = db.keyspace("idx_topic", idx_topic_opts).unwrap();
1056        let idx_expiry = db.keyspace("idx_expiry", idx_opts).unwrap();
1057
1058        // Every `last:n` topic's live frame count, read once here and kept in
1059        // memory after. See [`Store::last_counts`].
1060        let last_counts = load_last_counts(&meta).map_err(StoreError::Other)?;
1061
1062        let (broadcast_tx, _) = broadcast::channel(FOLLOW_BUFFER);
1063        let (gc_tx, gc_rx) = mpsc::unbounded_channel();
1064
1065        let fsync_state = Arc::new(FsyncState {
1066            mode: fsync,
1067            dirty: AtomicBool::new(false),
1068        });
1069
1070        let mut store = Store {
1071            path: path.clone(),
1072            db,
1073            stream,
1074            idx_topic,
1075            idx_expiry,
1076            sweep_start: Arc::new(Mutex::new(None)),
1077            trim_floor: Arc::new(Mutex::new(HashMap::new())),
1078            broadcast_tx,
1079            gc_tx,
1080            workers: None,
1081            write_lock: Arc::new(Mutex::new(())),
1082            meta,
1083            last_counts: Arc::new(Mutex::new(last_counts)),
1084            rt: tokio::runtime::Handle::try_current().ok(),
1085            base_engine: None,
1086            fsync: fsync_state,
1087            stats: Arc::new(StoreStats::default()),
1088        };
1089
1090        // Spawn the workers. The gc worker's clone is taken while `workers` is
1091        // still `None`, so only callers' clones join them.
1092        let gc = spawn_gc_worker(gc_rx, store.clone());
1093        let fsync_tick = match fsync {
1094            Fsync::Interval(interval) => Some(spawn_fsync_tick(
1095                store.db.clone(),
1096                store.fsync.clone(),
1097                interval,
1098            )),
1099            Fsync::Always | Fsync::Never => None,
1100        };
1101        let sweep_tick = if options.ttl_sweep.is_zero() {
1102            None
1103        } else {
1104            Some(spawn_sweep_tick(store.gc_tx.clone(), options.ttl_sweep))
1105        };
1106        store.workers = Some(Arc::new(Workers {
1107            gc: Some(gc),
1108            fsync: fsync_tick,
1109            sweep: sweep_tick,
1110        }));
1111
1112        Ok(store)
1113    }
1114
1115    /// Counters about this store's own work: appends, how much a read
1116    /// scanned against how much it returned, and what retention cost.
1117    pub fn stats(&self) -> StoreStatsSnapshot {
1118        self.stats.snapshot()
1119    }
1120
1121    /// Cache and filter counters for each keyspace, for tuning
1122    /// `cache_size`, `max_cached_files`, and the filter and pinning policies.
1123    ///
1124    /// Cumulative since the process started. See [`KeyspaceMetrics`].
1125    pub fn metrics(&self) -> Vec<KeyspaceMetrics> {
1126        vec![
1127            KeyspaceMetrics::read("stream", &self.stream),
1128            KeyspaceMetrics::read("idx_topic", &self.idx_topic),
1129            KeyspaceMetrics::read("idx_expiry", &self.idx_expiry),
1130        ]
1131    }
1132
1133    /// The runtime this store's tasks run on, if it was opened inside one.
1134    ///
1135    /// A following read needs it to wait on its receiver with a timeout, so
1136    /// it can notice an interrupt instead of parking until the next frame.
1137    pub fn runtime(&self) -> Option<tokio::runtime::Handle> {
1138        self.rt.clone()
1139    }
1140
1141    /// The [`Fsync`] policy this store was opened with.
1142    pub fn fsync(&self) -> Fsync {
1143        self.fsync.mode
1144    }
1145
1146    /// Fsync the journal now, whatever the [`Fsync`] policy. Every append
1147    /// that has returned is durable once this returns. Use it before a
1148    /// planned shutdown, or in tests that reopen a store.
1149    pub fn flush(&self) -> Result<(), crate::error::Error> {
1150        // Clear before persisting: a write that lands during the persist sets
1151        // the flag again, so the next tick still covers it.
1152        self.fsync.dirty.store(false, Ordering::Release);
1153        self.db.persist(PersistMode::SyncAll)?;
1154        Ok(())
1155    }
1156
1157    /// Apply the [`Fsync`] policy after a committed batch: sync inline under
1158    /// `always`, mark the journal dirty for the tick under `interval`, and do
1159    /// nothing under `never`.
1160    fn after_commit(&self) -> Result<(), crate::error::Error> {
1161        match self.fsync.mode {
1162            Fsync::Always => self.db.persist(PersistMode::SyncAll)?,
1163            Fsync::Interval(_) => self.fsync.dirty.store(true, Ordering::Release),
1164            Fsync::Never => {}
1165        }
1166        Ok(())
1167    }
1168
1169    /// Set a base engine the processor engines clone.
1170    ///
1171    /// A program that embeds xs prepares an [`EngineState`] with its own
1172    /// commands, env, and consts;
1173    /// [`prepared_base`](crate::nu::prepared_base) clones it per spawn and adds
1174    /// the store commands, so the actor, service, and action processors get
1175    /// those commands. Shared across `Store` clones, so set it once, before the
1176    /// processors spawn. No base set: `Engine::new()`.
1177    pub fn with_base_engine(mut self, base: EngineState) -> Self {
1178        self.base_engine = Some(Arc::new(base));
1179        self
1180    }
1181
1182    /// The base engine an embedder attached via [`with_base_engine`], if any.
1183    pub fn base_engine(&self) -> Option<&EngineState> {
1184        self.base_engine.as_deref()
1185    }
1186
1187    /// Wait until the background garbage-collection worker has processed every
1188    /// task queued so far. Useful in tests to observe TTL eviction
1189    /// deterministically.
1190    pub async fn wait_for_gc(&self) {
1191        let (tx, rx) = tokio::sync::oneshot::channel();
1192        let _ = self.gc_tx.send(GCTask::Drain(tx));
1193        let _ = rx.await;
1194    }
1195
1196    /// Queue a sweep now, as the sweep tick would. Follow it with
1197    /// [`wait_for_gc`](Store::wait_for_gc) to observe the removals.
1198    #[cfg(test)]
1199    fn sweep(&self) {
1200        let _ = self.gc_tx.send(GCTask::Sweep);
1201    }
1202
1203    /// Take [`write_lock`](Store::write_lock), even if a previous holder
1204    /// panicked.
1205    ///
1206    /// A panic while holding the lock -- a corrupt frame found mid-removal,
1207    /// say -- poisons it, and a plain `unwrap` would then fail every later
1208    /// write with an error that says nothing about what went wrong. Carrying
1209    /// on is safe because nothing the lock guards can be left half-changed:
1210    /// a batch commits all or nothing, and the in-memory counts move only
1211    /// after a commit succeeds. The worst a panic leaves behind is a count
1212    /// that reads low, which trims late and never deletes what it should
1213    /// keep.
1214    fn write_guard(&self) -> std::sync::MutexGuard<'_, ()> {
1215        self.write_lock
1216            .lock()
1217            .unwrap_or_else(std::sync::PoisonError::into_inner)
1218    }
1219
1220    /// Check a topic's count against what its index actually holds.
1221    ///
1222    /// Takes [`write_lock`](Store::write_lock), so no writer is part way
1223    /// between committing a batch and applying its count. Reading the two
1224    /// without it races: the gc worker can commit a removal between them and
1225    /// the numbers disagree for reasons that are nothing to do with the
1226    /// invariant.
1227    #[cfg(test)]
1228    fn assert_count_matches_index(&self, topic: &str) {
1229        let _guard = self.write_guard();
1230        let (low, high) = idx_topic_range(idx_topic_key_prefix(topic), None);
1231        let actual = self.idx_topic.range((low, high)).count() as u64;
1232        let claimed = self.last_counts.lock().unwrap().get(topic).copied();
1233        assert_eq!(
1234            claimed,
1235            Some(actual),
1236            "the count for {topic} disagrees with its index",
1237        );
1238    }
1239
1240    /// Number of entries in the expiry index.
1241    #[cfg(test)]
1242    fn idx_expiry_len(&self) -> usize {
1243        self.idx_expiry.len().unwrap()
1244    }
1245
1246    /// Read frames into an async channel according to `options`.
1247    ///
1248    /// By default this replays matching historical frames oldest-first and then
1249    /// closes the channel. With [`FollowOption::On`] it instead keeps the
1250    /// channel open and streams new appends as they arrive. When following, a
1251    /// single ephemeral `xs.threshold` frame is emitted to mark the boundary
1252    /// between replayed history and live events. Each item is a frame, or, as
1253    /// the last item before the channel closes, the [`ReadError`] that ended
1254    /// the read: a follower more than 4096 frames behind live gets
1255    /// [`ReadError::Lagged`].
1256    ///
1257    /// The returned [`Receiver`](tokio::sync::mpsc::Receiver) is bounded;
1258    /// dropping it stops the read. For a blocking, non-async caller use
1259    /// [`read_sync`](Store::read_sync).
1260    ///
1261    /// ```no_run
1262    /// use xs::{Store, ReadOptions, FollowOption};
1263    ///
1264    /// # async fn run(store: Store) {
1265    /// let mut rx = store.read(ReadOptions::builder().follow(FollowOption::On).build());
1266    /// while let Some(item) = rx.recv().await {
1267    ///     let Ok(frame) = item else { break }; // fell behind live
1268    ///     if frame.topic == "xs.threshold" {
1269    ///         // caught up to live; everything after this is new
1270    ///         continue;
1271    ///     }
1272    ///     println!("{} {}", frame.id, frame.topic);
1273    /// }
1274    /// # }
1275    /// ```
1276    #[tracing::instrument(skip(self))]
1277    pub fn read(&self, options: ReadOptions) -> tokio::sync::mpsc::Receiver<ReadItem> {
1278        let (tx, rx) = tokio::sync::mpsc::channel(100);
1279
1280        let should_follow = matches!(
1281            options.follow,
1282            FollowOption::On | FollowOption::WithHeartbeat(_)
1283        );
1284
1285        // A following read's scan of the stored frames hands the follow task
1286        // its live subscription once those frames are sent. With `new` there
1287        // is nothing stored to send, so it subscribes here and goes live at
1288        // once.
1289        let (follow_tx, follow_rx) = tokio::sync::oneshot::channel::<FollowFrom>();
1290        if options.new {
1291            if should_follow {
1292                let _ = follow_tx.send(FollowFrom {
1293                    broadcast_rx: self.broadcast_tx.subscribe(),
1294                    last_id: None,
1295                    count: 0,
1296                });
1297            }
1298        } else {
1299            let tx = tx.clone();
1300            let store = self.clone();
1301            let options = options.clone();
1302
1303            // The scan blocks on the store and on a reader slow to take
1304            // frames, so it runs on an OS thread.
1305            std::thread::spawn(move || {
1306                if let Some(from) = store.scan_stored(&options, should_follow, &tx) {
1307                    let _ = follow_tx.send(from);
1308                }
1309            });
1310        }
1311
1312        // Handle the live frames and heartbeat
1313        if should_follow {
1314            let handle = self
1315                .rt
1316                .clone()
1317                .expect("read() with follow needs a runtime handle");
1318
1319            {
1320                let tx = tx.clone();
1321                let limit = options.limit;
1322                let filter = TopicFilter::from_option(options.topic.as_deref());
1323
1324                handle.spawn(async move {
1325                    // Wait for the stored frames and the threshold to be sent.
1326                    // An error means the read ended during the scan.
1327                    let Ok(FollowFrom {
1328                        mut broadcast_rx,
1329                        last_id,
1330                        mut count,
1331                    }) = follow_rx.await
1332                    else {
1333                        return;
1334                    };
1335
1336                    loop {
1337                        tokio::select! {
1338                            _ = tx.closed() => break,
1339                            r = broadcast_rx.recv() => match r {
1340                                Ok(frame) => {
1341                                    // Filter by topic (any-match against the parsed patterns)
1342                                    if !filter.matches(&frame.topic) {
1343                                        continue;
1344                                    }
1345
1346                                    // Skip if the scan of stored frames already sent it
1347                                    if let Some(last_scanned_id) = last_id {
1348                                        if frame.id <= last_scanned_id {
1349                                            continue;
1350                                        }
1351                                    }
1352
1353                                    if tx.send(Ok(frame)).await.is_err() {
1354                                        break;
1355                                    }
1356
1357                                    if let Some(limit) = limit {
1358                                        count += 1;
1359                                        if count >= limit {
1360                                            break;
1361                                        }
1362                                    }
1363                                }
1364                                // The reader fell more than FOLLOW_BUFFER frames
1365                                // behind and the channel overwrote what it had not
1366                                // taken. The stored frames were read before
1367                                // subscribing, so this buffer covered only the
1368                                // catch-up and live frames: the reader is slower
1369                                // than the stream, and a retry would not help.
1370                                // Carrying on would hand it the frames after the
1371                                // gap as though nothing were missing. End the read
1372                                // with an error that says so (ADR 0008).
1373                                Err(broadcast::error::RecvError::Lagged(skipped)) => {
1374                                    tracing::warn!(
1375                                        skipped,
1376                                        "follow fell behind the live buffer, ending the read"
1377                                    );
1378                                    let _ = tx.send(Err(ReadError::Lagged { skipped })).await;
1379                                    break;
1380                                }
1381                                Err(broadcast::error::RecvError::Closed) => break,
1382                            }
1383                        }
1384                    }
1385                });
1386            }
1387
1388            // Handle heartbeat if requested
1389            if let FollowOption::WithHeartbeat(duration) = options.follow {
1390                let heartbeat_tx = tx;
1391                handle.spawn(async move {
1392                    loop {
1393                        tokio::select! {
1394                            _ = heartbeat_tx.closed() => break,
1395                            _ = tokio::time::sleep(duration) => {
1396                                let frame = Frame::builder("xs.pulse")
1397                                    .id(scru128::new())
1398                                    .ttl(TTL::Ephemeral)
1399                                    .build();
1400                                if heartbeat_tx.send(Ok(frame)).await.is_err() {
1401                                    break;
1402                                }
1403                            }
1404                        }
1405                    }
1406                });
1407            }
1408        }
1409
1410        rx
1411    }
1412
1413    /// Send the stored frames a read asks for, on the calling thread. For a
1414    /// following read, then subscribe to live frames, send what was stored
1415    /// since the first scan began, then `xs.threshold`, and return the
1416    /// subscription for the follow task. `None` when the read is over: it
1417    /// does not follow, `limit` was reached, or the reader went away.
1418    ///
1419    /// The subscription is taken after the first scan, not before (ADR 0008).
1420    /// A reader that appends while it works through the stored frames would
1421    /// otherwise pile its own frames up in the live buffer and overrun it.
1422    /// Frames appended during the first scan are read from the store by the
1423    /// catch-up scan instead; the live buffer only has to cover that.
1424    fn scan_stored(
1425        &self,
1426        options: &ReadOptions,
1427        follow: bool,
1428        tx: &mpsc::Sender<ReadItem>,
1429    ) -> Option<FollowFrom> {
1430        let filter = TopicFilter::from_option(options.topic.as_deref());
1431        let mut last_id = None;
1432        let mut count = 0;
1433
1434        // Where the catch-up scan starts when the first sent nothing.
1435        let catch_up_from;
1436
1437        if let Some(last_n) = options.last {
1438            // Handle --last N: get the N most recent frames. The newest frame
1439            // before the scan bounds the catch-up when none of them match.
1440            catch_up_from = self.iter_frames_rev().next().map(|frame| (frame.id, false));
1441
1442            // Collect last N frames (in reverse order), skipping expired
1443            let mut frames: Vec<Frame> = Vec::with_capacity(last_n);
1444            for frame in self.iter_for_filter_rev(filter.clone()) {
1445                if is_expired(&frame) {
1446                    continue;
1447                }
1448                frames.push(frame);
1449                if frames.len() >= last_n {
1450                    break;
1451                }
1452            }
1453
1454            // Reverse to chronological order and send
1455            for frame in frames.into_iter().rev() {
1456                last_id = Some(frame.id);
1457                count += 1;
1458                tx.blocking_send(Ok(frame)).ok()?;
1459            }
1460        } else {
1461            // Normal forward iteration
1462            // Determine start bound: from (inclusive) takes precedence over after (exclusive)
1463            catch_up_from = options
1464                .from
1465                .map(|id| (id, true))
1466                .or_else(|| options.after.map(|id| (id, false)));
1467            if !self.send_scan(
1468                filter.clone(),
1469                catch_up_from,
1470                options.limit,
1471                &mut last_id,
1472                &mut count,
1473                tx,
1474            ) {
1475                return None;
1476            }
1477        }
1478
1479        if !follow {
1480            return None;
1481        }
1482
1483        // Subscribe, then catch up from the store. A frame appended in between
1484        // is in both; the follow task skips it by `last_id`.
1485        let broadcast_rx = self.broadcast_tx.subscribe();
1486        let start = last_id.map(|id| (id, false)).or(catch_up_from);
1487        if !self.send_scan(filter, start, options.limit, &mut last_id, &mut count, tx) {
1488            return None;
1489        }
1490
1491        let threshold = Frame::builder("xs.threshold")
1492            .id(scru128::new())
1493            .ttl(TTL::Ephemeral)
1494            .build();
1495        tx.blocking_send(Ok(threshold)).ok()?;
1496
1497        Some(FollowFrom {
1498            broadcast_rx,
1499            last_id,
1500            count,
1501        })
1502    }
1503
1504    /// Send the stored frames matching `filter` from `start` on, skipping
1505    /// expired ones. `last_id` and `count` carry across scans. Returns false
1506    /// when the read is over: `limit` was reached or the reader went away.
1507    fn send_scan(
1508        &self,
1509        filter: TopicFilter,
1510        start: Option<(Scru128Id, bool)>,
1511        limit: Option<usize>,
1512        last_id: &mut Option<Scru128Id>,
1513        count: &mut usize,
1514        tx: &mpsc::Sender<ReadItem>,
1515    ) -> bool {
1516        for frame in self.iter_for_filter(filter, start) {
1517            if is_expired(&frame) {
1518                continue;
1519            }
1520            if limit.is_some_and(|limit| *count >= limit) {
1521                return false;
1522            }
1523            *last_id = Some(frame.id);
1524            if tx.blocking_send(Ok(frame)).is_err() {
1525                return false;
1526            }
1527            *count += 1;
1528        }
1529        true
1530    }
1531
1532    /// Replay matching historical frames as a blocking iterator.
1533    ///
1534    /// This honours the `topic`, `from`, `after`, `limit`, and `last` parts of
1535    /// [`ReadOptions`] but ignores [`follow`](ReadOptions::follow): it never
1536    /// streams live appends. Use [`read`](Store::read) when you need to follow.
1537    ///
1538    /// The iterator is lazy: it reads a frame per `next`, so a caller that
1539    /// stops early only pays for what it pulled. The exception is `last`,
1540    /// which reads in reverse and buffers its N frames to return them in
1541    /// chronological order.
1542    ///
1543    /// ```no_run
1544    /// use xs::{Store, ReadOptions};
1545    ///
1546    /// # fn run(store: Store) {
1547    /// let opts = ReadOptions::builder().topic("clip.*".to_string()).last(10).build();
1548    /// for frame in store.read_sync(opts) {
1549    ///     println!("{} {}", frame.id, frame.topic);
1550    /// }
1551    /// # }
1552    /// ```
1553    pub fn read_sync(&self, options: ReadOptions) -> impl Iterator<Item = Frame> + '_ {
1554        // Hide expired frames the sweeper has not reached yet
1555        let filter_expired = |frame: Frame| (!is_expired(&frame)).then_some(frame);
1556
1557        let filter = TopicFilter::from_option(options.topic.as_deref());
1558
1559        if let Some(last_n) = options.last {
1560            // Handle --last N: get the N most recent frames. This branch reads
1561            // in reverse and re-orders, so it has to collect, but it is bounded
1562            // by last_n.
1563            let iter = self.iter_for_filter_rev(filter);
1564
1565            // Collect last N frames (in reverse order), skipping expired
1566            let mut frames: Vec<Frame> = Vec::with_capacity(last_n);
1567            for frame in iter {
1568                if let Some(frame) = filter_expired(frame) {
1569                    frames.push(frame);
1570                    if frames.len() >= last_n {
1571                        break;
1572                    }
1573                }
1574            }
1575
1576            // Reverse to chronological order
1577            frames.reverse();
1578            Box::new(frames.into_iter()) as Box<dyn Iterator<Item = Frame> + '_>
1579        } else {
1580            // Normal forward iteration, streamed: the caller only pays for the
1581            // frames it pulls.
1582            let start_bound = options
1583                .from
1584                .map(|id| (id, true))
1585                .or_else(|| options.after.map(|id| (id, false)));
1586
1587            Box::new(
1588                self.iter_for_filter(filter, start_bound)
1589                    .filter_map(filter_expired)
1590                    .take(options.limit.unwrap_or(usize::MAX)),
1591            )
1592        }
1593    }
1594
1595    /// Returns the current module state as of a given point in the stream.
1596    ///
1597    /// Scans all frames up to (and including) `as_of` and returns a mapping of
1598    /// module name to CAS hash for the latest frame on each `xs.module.<name>`
1599    /// topic.
1600    /// Resolve the set of registered Nushell modules as of a given frame ID.
1601    ///
1602    /// Scans `xs.module.<name>` frames up to and including `as_of` and returns a
1603    /// map from module name to the content hash of its latest definition. Used
1604    /// by the scripting runtime; rarely needed when embedding the store
1605    /// directly.
1606    pub fn nu_modules_at(
1607        &self,
1608        as_of: &Scru128Id,
1609    ) -> std::collections::HashMap<String, ssri::Integrity> {
1610        let mut modules = std::collections::HashMap::new();
1611        let options = ReadOptions::builder().follow(FollowOption::Off).build();
1612        for frame in self.read_sync(options) {
1613            if frame.id > *as_of {
1614                break;
1615            }
1616            if let Some(hash) = frame.hash {
1617                if let Some(name) = frame.topic.strip_prefix("xs.module.") {
1618                    if !name.is_empty() {
1619                        modules.insert(name.to_string(), hash);
1620                    }
1621                }
1622            }
1623        }
1624        modules
1625    }
1626
1627    /// Fetch a single frame by ID, or `None` if no such frame exists.
1628    pub fn get(&self, id: &Scru128Id) -> Option<Frame> {
1629        self.stats.stream_reads.fetch_add(1, Ordering::Relaxed);
1630        self.stream
1631            .get(id.to_bytes())
1632            .unwrap()
1633            .map(|value| deserialize_frame((id.as_bytes(), value)))
1634    }
1635
1636    /// Delete a frame and its topic index entries. Removing a frame that does
1637    /// not exist is a no-op and returns `Ok(())`.
1638    ///
1639    /// This removes the stream entry only; any payload bytes in the
1640    /// content-addressed store are left in place.
1641    #[tracing::instrument(skip(self), fields(id = %id.to_string()))]
1642    pub fn remove(&self, id: &Scru128Id) -> Result<(), crate::error::Error> {
1643        self.remove_many([Removal::Id(*id)])
1644    }
1645
1646    /// Delete every frame in `removals`, with their index entries, in one
1647    /// batch with one commit. A [`Removal::Id`] whose frame is already gone
1648    /// is skipped, and nothing is committed when none remain.
1649    fn remove_many(
1650        &self,
1651        removals: impl IntoIterator<Item = Removal>,
1652    ) -> Result<(), crate::error::Error> {
1653        let _guard = self.write_guard();
1654        self.remove_many_locked(removals)
1655    }
1656
1657    /// [`remove_many`](Store::remove_many), for a caller already holding
1658    /// [`write_lock`](Store::write_lock).
1659    ///
1660    /// The gc worker decides how far over a topic is, reads the frames it is
1661    /// going to take, and removes them. All three have to happen under one
1662    /// hold: deciding from a count that an append then moves is how a trim
1663    /// takes frames it was told to keep.
1664    fn remove_many_locked(
1665        &self,
1666        removals: impl IntoIterator<Item = Removal>,
1667    ) -> Result<(), crate::error::Error> {
1668        let mut batch = self.db.batch();
1669        // How many frames this batch takes off each counted topic. Applied
1670        // once at the end, so the row is written once however many frames on
1671        // that topic the batch touches.
1672        let mut taken: HashMap<String, u64> = HashMap::new();
1673        for removal in removals {
1674            // `Some(topic)` when the removal took a frame off that topic, so
1675            // the topic's count should follow. Staging keys that are not
1676            // there is a no-op and is how stale entries get cleaned up, so
1677            // the removal runs either way; only the count is conditional.
1678            let counts_against = match removal {
1679                Removal::Id(id) => {
1680                    let Some(frame) = self.get(&id) else {
1681                        continue;
1682                    };
1683                    self.remove_frame_keys(&mut batch, &frame.id, &frame.topic, expires_at(&frame));
1684                    Some(frame.topic)
1685                }
1686                Removal::Indexed {
1687                    id,
1688                    topic,
1689                    expires_at,
1690                } => {
1691                    // The gc worker reads the frames it is going to remove
1692                    // before it takes the lock, so an append can trim one of
1693                    // them in between. Counting a frame that has already gone
1694                    // takes the topic below the truth, and a count that reads
1695                    // low never trims again.
1696                    //
1697                    // The check reads the index, not the frame: the value is
1698                    // eight bytes and the block is still warm from the scan
1699                    // that produced this id.
1700                    let mut key = idx_topic_key_prefix(&topic);
1701                    key.extend(id.as_bytes());
1702                    let present = self.idx_topic.contains_key(key)?;
1703                    self.remove_frame_keys(&mut batch, &id, &topic, expires_at);
1704                    present.then_some(topic)
1705                }
1706            };
1707            if let Some(topic) = counts_against {
1708                *taken.entry(topic).or_insert(0) += 1;
1709            }
1710        }
1711        let mut edits = Vec::new();
1712        for (topic, taken) in taken {
1713            if let Some(count) = self.count_of(&topic) {
1714                let now = count.saturating_sub(taken);
1715                edits.extend(self.stage_count(&mut batch, &topic, now));
1716            }
1717        }
1718        if batch.is_empty() {
1719            return Ok(());
1720        }
1721        batch.commit()?;
1722        self.apply_counts(edits);
1723        self.stats.remove_commits.fetch_add(1, Ordering::Relaxed);
1724        // No inline fsync in any mode. The tombstones reach disk with the next
1725        // append's sync or the next tick. If power loss brings a frame back,
1726        // its index entries come back with it, so it is trimmed or swept
1727        // again.
1728        if matches!(self.fsync.mode, Fsync::Interval(_)) {
1729            self.fsync.dirty.store(true, Ordering::Release);
1730        }
1731        Ok(())
1732    }
1733
1734    /// Queue the stream entry and index keys of a frame for removal on
1735    /// `batch`. `expires_at` is the frame's expiry index slot, `Some` only for
1736    /// a `time:` frame. The topic key is built without validation: the frame
1737    /// exists.
1738    fn remove_frame_keys(
1739        &self,
1740        batch: &mut OwnedWriteBatch,
1741        id: &Scru128Id,
1742        topic: &str,
1743        expires_at: Option<u64>,
1744    ) {
1745        self.stats.removed_frames.fetch_add(1, Ordering::Relaxed);
1746        let mut topic_key = idx_topic_key_prefix(topic);
1747        topic_key.extend(id.as_bytes());
1748        batch.remove(&self.stream, id.as_bytes());
1749        batch.remove(&self.idx_topic, topic_key);
1750        for prefix_key in idx_topic_prefix_keys(topic, id) {
1751            batch.remove(&self.idx_topic, prefix_key);
1752        }
1753        if let Some(expires_at) = expires_at {
1754            batch.remove(&self.idx_expiry, idx_expiry_key(expires_at, id));
1755        }
1756    }
1757
1758    /// The oldest `time:` frames whose expiry is at or before `now_ms`, at
1759    /// most `limit` of them, straight from the expiry index. A full `limit`
1760    /// means there may be more.
1761    ///
1762    /// The scan resumes at [`sweep_start`](Store::sweep_start) rather than at
1763    /// the start of the index. Everything below that point is the tombstones
1764    /// of frames earlier sweeps removed, and walking them again on every sweep
1765    /// is what made draining a backlog cost O(n^2/batch).
1766    fn expired_at(&self, now_ms: u64, limit: usize) -> Vec<Removal> {
1767        let last = idx_expiry_key(now_ms, &Scru128Id::from_bytes([0xff; 16]));
1768        let from = *self.sweep_start.lock().unwrap();
1769        // A clock that stepped backwards can leave the resume point above the
1770        // cut-off. Nothing below it is unswept, so there is nothing to do
1771        // until the clock catches up.
1772        if from.is_some_and(|start| start.key > last) {
1773            return Vec::new();
1774        }
1775        let start = from.map_or(Bound::Unbounded, |start| start.bound());
1776
1777        let mut removals = Vec::new();
1778        let mut swept = None;
1779        for guard in self
1780            .idx_expiry
1781            .range((start, Bound::Included(last)))
1782            .take(limit)
1783        {
1784            // Stop on a read error rather than skipping the entry: the resume
1785            // point may never pass an entry this sweep did not remove.
1786            let Ok((key, value)) = guard.into_inner() else {
1787                break;
1788            };
1789            let Ok(key) = <[u8; 24]>::try_from(key.as_ref()) else {
1790                break;
1791            };
1792            let (expires_at, id) = idx_expiry_parse_key(&key);
1793            removals.push(Removal::Indexed {
1794                id,
1795                topic: String::from_utf8_lossy(&value).into_owned(),
1796                expires_at: Some(expires_at),
1797            });
1798            swept = Some(key);
1799        }
1800
1801        if let Some(key) = swept {
1802            let mut start = self.sweep_start.lock().unwrap();
1803            // Only advance from the point this scan started at. An index write
1804            // that moved it back while the scan ran wins: the next sweep
1805            // covers this ground again, and covering it twice is cheap next to
1806            // leaving a frame behind.
1807            if *start == from {
1808                *start = Some(SweepStart {
1809                    key,
1810                    inclusive: false,
1811                });
1812            }
1813        }
1814        removals
1815    }
1816
1817    /// Count `topic`'s frames by walking its index.
1818    ///
1819    /// Called when the first `last:n` frame lands on a topic, to establish
1820    /// its count. It does not record the result: the caller stages it into
1821    /// the batch, and the in-memory map follows the commit.
1822    ///
1823    /// Caller must hold [`write_lock`](Store::write_lock), so nothing is
1824    /// writing to the topic while this counts it. That is what makes the
1825    /// count a plain scan rather than a moving target.
1826    ///
1827    /// The count is durable once written, so a topic is walked once in the
1828    /// store's life. It is the price of putting a `last:n` on a topic that
1829    /// already has frames, and it is paid by the append that does so.
1830    fn derive_count(&self, topic: &str) -> u64 {
1831        let (low, high) = idx_topic_range(idx_topic_key_prefix(topic), None);
1832        let count = self.idx_topic.range((low, high)).count();
1833        self.stats.trim_scanned.fetch_add(count, Ordering::Relaxed);
1834        count as u64
1835    }
1836
1837    /// `topic`'s count, or `None` if no `last:n` frame has ever touched it
1838    /// and so there is nothing to keep.
1839    fn count_of(&self, topic: &str) -> Option<u64> {
1840        self.last_counts.lock().unwrap().get(topic).copied()
1841    }
1842
1843    /// Stage `topic`'s new count on `batch`, and return what to do to the
1844    /// in-memory map once the batch commits.
1845    ///
1846    /// The map is deliberately not touched here. A count that moved for a
1847    /// write that then failed to commit reads high, and a count reading high
1848    /// deletes frames the topic was told to keep. So the map only ever
1849    /// follows a commit that succeeded: see [`apply_counts`](Store::apply_counts).
1850    ///
1851    /// Nothing is staged when the value has not changed, which is the steady
1852    /// state of a topic at its cap: one frame in, one frame out, the same
1853    /// number. A settled topic writes this row once and then never again.
1854    ///
1855    /// Caller must hold [`write_lock`](Store::write_lock).
1856    fn stage_count(
1857        &self,
1858        batch: &mut OwnedWriteBatch,
1859        topic: &str,
1860        now: u64,
1861    ) -> Option<(String, u64)> {
1862        if self.last_counts.lock().unwrap().get(topic) == Some(&now) {
1863            return None;
1864        }
1865        batch.insert(&self.meta, count_key(topic), now.to_be_bytes());
1866        Some((topic.to_owned(), now))
1867    }
1868
1869    /// Move the in-memory counts to what a committed batch just wrote.
1870    ///
1871    /// Caller must hold [`write_lock`](Store::write_lock).
1872    fn apply_counts(&self, edits: Vec<(String, u64)>) {
1873        if edits.is_empty() {
1874            return;
1875        }
1876        let mut counts = self.last_counts.lock().unwrap();
1877        for (topic, now) in edits {
1878            counts.insert(topic, now);
1879        }
1880    }
1881
1882    /// The oldest `want` frames on `topic`, forward from its trim floor.
1883    ///
1884    /// No reverse scan: the count already said how many are over, so this
1885    /// reads only as far as the entries it is going to remove.
1886    ///
1887    /// Frames in `pending` are walked past, not returned: the drain is
1888    /// already removing them. So this can return fewer than `want` when the
1889    /// topic runs out, including when it runs out of frames that are not
1890    /// pending. A short result is not an error: the gc drain takes it as the
1891    /// end of the topic, and an append that got less than it needed hands the
1892    /// rest to the gc worker.
1893    ///
1894    /// Caller must hold [`write_lock`](Store::write_lock).
1895    fn oldest_on_topic(
1896        &self,
1897        topic: &str,
1898        want: usize,
1899        pending: &HashSet<Scru128Id>,
1900    ) -> Vec<Overflow> {
1901        let floor = self.trim_floor.lock().unwrap().get(topic).copied();
1902        let (low, high) = idx_topic_range(
1903            idx_topic_key_prefix(topic),
1904            floor.map(|floor| (floor.id, floor.inclusive)),
1905        );
1906
1907        let mut overflow = Vec::with_capacity(want);
1908        let mut last = None;
1909        let mut scanned = 0;
1910        for guard in self.idx_topic.range((low, high)) {
1911            scanned += 1;
1912            let Ok((key, value)) = guard.into_inner() else {
1913                break;
1914            };
1915            let id = idx_topic_frame_id_from_key(&key);
1916            // Walk past what the drain is already removing. The count has
1917            // been told about these, so returning them would leave the trim
1918            // short by however many it handed back.
1919            if !pending.contains(&id) {
1920                overflow.push(Overflow {
1921                    id,
1922                    expires_at: idx_topic_expiry_of(&value),
1923                });
1924            }
1925            // A pending id still moves the floor: this drain removes it too.
1926            last = Some(id);
1927            if overflow.len() == want {
1928                break;
1929            }
1930        }
1931
1932        self.stats
1933            .trim_scanned
1934            .fetch_add(scanned, Ordering::Relaxed);
1935
1936        // Everything at or below what this pass takes is tombstone once the
1937        // batch commits, so the next pass opens above it instead of walking
1938        // it again.
1939        if let Some(id) = last {
1940            self.set_trim_floor(
1941                topic,
1942                floor,
1943                TrimFloor {
1944                    id,
1945                    inclusive: false,
1946                },
1947            );
1948        }
1949        overflow
1950    }
1951
1952    /// The frames on `topic` over its cap, oldest first, at most `limit` of
1953    /// them. A full `limit` means there are more.
1954    ///
1955    /// The count says how many are over, so this reads only the entries it is
1956    /// going to remove: no reverse scan to find where the cut goes. That is
1957    /// the whole point of keeping a count. Before it, a trim walked `keep`
1958    /// index entries on every append, which at a million-frame topic was
1959    /// 760 ms of gc worker time to delete one frame.
1960    ///
1961    /// `pending_here` is how many frames on this topic the drain is already
1962    /// removing. They still hold their slot in the count until the batch
1963    /// commits, so the trim has to take them off first or it removes them
1964    /// twice over.
1965    ///
1966    /// Returns nothing for a topic with no count, which is one no `last:n`
1967    /// frame has ever touched.
1968    fn last_overflow(
1969        &self,
1970        topic: &str,
1971        keep: u32,
1972        pending: &HashSet<Scru128Id>,
1973        pending_here: u64,
1974        limit: usize,
1975    ) -> Vec<Overflow> {
1976        let Some(count) = self.count_of(topic) else {
1977            return Vec::new();
1978        };
1979        // Both corrections are needed, and they are not alternatives. The
1980        // count says how many frames the topic holds, including the ones this
1981        // drain is already removing, so `pending_here` comes off it or the
1982        // trim asks for too many and takes frames the topic was told to keep.
1983        // Those same frames are the oldest, so they are the first the scan
1984        // reaches, and skipping them is what makes the ones it returns real.
1985        let live = count.saturating_sub(pending_here);
1986        let over = live.saturating_sub(u64::from(keep));
1987        if over == 0 {
1988            return Vec::new();
1989        }
1990        self.oldest_on_topic(topic, over.min(limit as u64) as usize, pending)
1991    }
1992
1993    /// Move a topic's trim floor to `to`, unless something moved it since the
1994    /// scan read `from`. An index write that dropped it while the scan ran
1995    /// wins: the next trim covers the topic from further back, and covering
1996    /// ground twice is cheap next to leaving a frame behind.
1997    fn set_trim_floor(&self, topic: &str, from: Option<TrimFloor>, to: TrimFloor) {
1998        let mut floors = self.trim_floor.lock().unwrap();
1999        if floors.get(topic).copied() == from {
2000            floors.insert(topic.to_string(), to);
2001        }
2002    }
2003
2004    /// Note that a `time:` frame's expiry entry has been committed at `key`.
2005    ///
2006    /// A frame restored with an id from the past, or appended in the instant a
2007    /// sweep passed its slot, lands below the resume point, where no later
2008    /// sweep would look. Move the resume point back onto it.
2009    ///
2010    /// Must be called after the commit: called before, a sweep could run,
2011    /// find nothing at the key yet, and leave the resume point above it again.
2012    fn note_indexed_expiry(&self, key: [u8; 24]) {
2013        let mut start = self.sweep_start.lock().unwrap();
2014        // Already at the start of the index: nothing can be below it.
2015        let Some(current) = *start else { return };
2016        let candidate = SweepStart {
2017            key,
2018            inclusive: true,
2019        };
2020        if candidate.rank() < current.rank() {
2021            *start = Some(candidate);
2022        }
2023    }
2024
2025    /// Note that a frame's topic index entry has been committed. An id at or
2026    /// below the topic's trim floor is in ground a trim scan no longer covers,
2027    /// so drop the floor and let the next trim scan the topic whole.
2028    ///
2029    /// Called after the commit, as
2030    /// [`note_indexed_expiry`](Store::note_indexed_expiry) is, and for every
2031    /// frame: `last:n` counts what is on the topic, whatever ttl put it there.
2032    fn note_indexed_topic(&self, topic: &str, id: &Scru128Id) {
2033        let mut floors = self.trim_floor.lock().unwrap();
2034        if floors.is_empty() {
2035            return;
2036        }
2037        if floors.get(topic).is_some_and(|floor| *id <= floor.id) {
2038            floors.remove(topic);
2039        }
2040    }
2041
2042    /// Forget where the sweep and the `last:n` trims had got to, so each next
2043    /// scan starts from the beginning of its index again. Called when a
2044    /// removal batch fails to commit: its frames are still there, but the
2045    /// resume points have already moved as though they were gone.
2046    fn reset_gc_resume(&self) {
2047        *self.sweep_start.lock().unwrap() = None;
2048        self.trim_floor.lock().unwrap().clear();
2049    }
2050
2051    // --- Content-addressed store (CAS) ---
2052    //
2053    // Frame payloads live here, keyed by an integrity hash. The typical flow is
2054    // `cas_insert` to store bytes, stash the returned hash on a `Frame`, then
2055    // `cas_read` to retrieve them later. Each method has a `_sync` twin for
2056    // blocking callers; the streaming `cas_reader`/`cas_writer` variants avoid
2057    // buffering the whole payload in memory.
2058
2059    /// Open a streaming reader for the payload identified by `hash`.
2060    pub async fn cas_reader(&self, hash: ssri::Integrity) -> cacache::Result<cacache::Reader> {
2061        cacache::Reader::open_hash(&self.path.join("cacache"), hash).await
2062    }
2063
2064    /// Blocking variant of [`cas_reader`](Store::cas_reader).
2065    pub fn cas_reader_sync(&self, hash: ssri::Integrity) -> cacache::Result<cacache::SyncReader> {
2066        cacache::SyncReader::open_hash(self.path.join("cacache"), hash)
2067    }
2068
2069    /// Open a streaming writer; finish it to obtain the payload's integrity hash.
2070    pub async fn cas_writer(&self) -> cacache::Result<cacache::Writer> {
2071        cacache::WriteOpts::new()
2072            .open_hash(&self.path.join("cacache"))
2073            .await
2074    }
2075
2076    /// Blocking variant of [`cas_writer`](Store::cas_writer).
2077    pub fn cas_writer_sync(&self) -> cacache::Result<cacache::SyncWriter> {
2078        cacache::WriteOpts::new().open_hash_sync(self.path.join("cacache"))
2079    }
2080
2081    /// Store `content` and return its integrity hash, ready to attach to a
2082    /// [`Frame::hash`].
2083    pub async fn cas_insert(&self, content: impl AsRef<[u8]>) -> cacache::Result<ssri::Integrity> {
2084        cacache::write_hash(&self.path.join("cacache"), content).await
2085    }
2086
2087    /// Blocking variant of [`cas_insert`](Store::cas_insert).
2088    pub fn cas_insert_sync(&self, content: impl AsRef<[u8]>) -> cacache::Result<ssri::Integrity> {
2089        cacache::write_hash_sync(self.path.join("cacache"), content)
2090    }
2091
2092    /// Convenience wrapper over [`cas_insert`](Store::cas_insert) for a byte slice.
2093    pub async fn cas_insert_bytes(&self, bytes: &[u8]) -> cacache::Result<ssri::Integrity> {
2094        self.cas_insert(bytes).await
2095    }
2096
2097    /// Blocking variant of [`cas_insert_bytes`](Store::cas_insert_bytes).
2098    pub fn cas_insert_bytes_sync(&self, bytes: &[u8]) -> cacache::Result<ssri::Integrity> {
2099        self.cas_insert_sync(bytes)
2100    }
2101
2102    /// Delete content no stored frame points at, once it is older than `grace`.
2103    ///
2104    /// Removing or trimming a frame leaves its content in place (see
2105    /// [`remove`](Store::remove)), and an ephemeral frame's content is never
2106    /// pointed at by a stored frame at all, so without this the content store
2107    /// only grows. This reads the hash of every stored frame, then walks the
2108    /// content files and deletes each one no frame uses and that was last
2109    /// written more than `grace` ago. The grace covers content that is about
2110    /// to be used: uploaded with `POST /cas` for a later append, or behind an
2111    /// ephemeral frame that live readers are still fetching.
2112    ///
2113    /// It holds [`write_lock`](Store::write_lock) throughout, so no frame can be appended
2114    /// between reading the hashes in use and deleting a file.
2115    pub fn cas_gc(&self, grace: Duration) -> Result<CasGcReport, crate::error::Error> {
2116        let _guard = self.write_guard();
2117        let in_use: HashSet<(String, String)> = self
2118            .iter_frames(None)
2119            .filter_map(|frame| frame.hash)
2120            .map(|hash| {
2121                let (algorithm, hex) = hash.to_hex();
2122                (algorithm.to_string(), hex)
2123            })
2124            .collect();
2125
2126        let cutoff = std::time::SystemTime::now()
2127            .checked_sub(grace)
2128            .unwrap_or(std::time::UNIX_EPOCH);
2129        let mut report = CasGcReport::default();
2130        let content = self.path.join("cacache").join("content-v2");
2131        let algorithms = match std::fs::read_dir(&content) {
2132            Ok(dir) => dir,
2133            Err(e) if e.kind() == std::io::ErrorKind::NotFound => return Ok(report),
2134            Err(e) => return Err(e.into()),
2135        };
2136        for algorithm in algorithms {
2137            let algorithm = algorithm?;
2138            let name = algorithm.file_name().to_string_lossy().into_owned();
2139            let mut files = Vec::new();
2140            content_files(&algorithm.path(), &mut files)?;
2141            for path in files {
2142                // cacache keeps a hash's hex digest split across directories:
2143                // content-v2/<algorithm>/ab/cd/ef01..., so its path below the
2144                // algorithm, joined, is the digest.
2145                let hex: String = path
2146                    .strip_prefix(algorithm.path())
2147                    .map(|rel| rel.iter().map(|part| part.to_string_lossy()).collect())
2148                    .unwrap_or_default();
2149                if in_use.contains(&(name.clone(), hex)) {
2150                    report.in_use += 1;
2151                    continue;
2152                }
2153                let meta = std::fs::metadata(&path)?;
2154                if meta.modified()? > cutoff {
2155                    report.recent += 1;
2156                    continue;
2157                }
2158                std::fs::remove_file(&path)?;
2159                report.deleted += 1;
2160                report.bytes_freed += meta.len();
2161            }
2162        }
2163        Ok(report)
2164    }
2165
2166    /// Read back the full payload for `hash` into a `Vec<u8>`.
2167    pub async fn cas_read(&self, hash: &ssri::Integrity) -> cacache::Result<Vec<u8>> {
2168        cacache::read_hash(&self.path.join("cacache"), hash).await
2169    }
2170
2171    /// Blocking variant of [`cas_read`](Store::cas_read).
2172    pub fn cas_read_sync(&self, hash: &ssri::Integrity) -> cacache::Result<Vec<u8>> {
2173        cacache::read_hash_sync(self.path.join("cacache"), hash)
2174    }
2175
2176    /// Persist a frame exactly as given, including its existing
2177    /// [`id`](Frame::id), without broadcasting it to live readers.
2178    ///
2179    /// Most callers want [`append`](Store::append) instead, which assigns a
2180    /// fresh ID and notifies subscribers. Use `insert_frame` only when you are
2181    /// reconstructing a stream with predetermined IDs (for example when
2182    /// restoring a backup).
2183    ///
2184    /// Re-importing an id the store already holds moves its index entries
2185    /// rather than leaving the old ones behind, and moves the `last:n` counts
2186    /// of both topics with them. A restored frame carrying `last:n` trims its
2187    /// topic like an append does; one without leaves the topic as it is.
2188    #[tracing::instrument(skip(self))]
2189    pub fn insert_frame(&self, frame: &Frame) -> Result<(), crate::error::Error> {
2190        let _guard = self.write_guard();
2191        // What this id is indexed under now, if anything. One seek, and it
2192        // answers both what to clean up and whether this write adds an entry.
2193        let superseded = self.get(&frame.id);
2194        let mut batch = self.db.batch();
2195        let mut stage = CountStage::default();
2196        let expiry_key = match self.stage_frame(&mut batch, frame, superseded, &mut stage) {
2197            Ok(key) => key,
2198            Err(e) => {
2199                self.unstage(&stage);
2200                return Err(e);
2201            }
2202        };
2203        self.commit_staged(batch, &[(frame, expiry_key)], stage)
2204    }
2205
2206    /// Queue `frame` on `batch`: its stream entry and index keys, the removal
2207    /// of whatever index entries its id already had, and the `last:n` count
2208    /// and trim of every topic involved. Counts and trims are tracked in
2209    /// `stage` across the whole batch, so several frames on one topic in one
2210    /// write count and trim as they would one at a time. Returns the frame's
2211    /// expiry index key, `Some` only for a `time:` frame.
2212    ///
2213    /// `superseded` is the frame this id is replacing, which only a restore
2214    /// can produce. An append mints a fresh id and passes `None`.
2215    ///
2216    /// Caller must hold [`write_lock`](Store::write_lock), and on an error
2217    /// must [`unstage`](Store::unstage) before dropping the batch.
2218    fn stage_frame(
2219        &self,
2220        batch: &mut OwnedWriteBatch,
2221        frame: &Frame,
2222        superseded: Option<Frame>,
2223        stage: &mut CountStage,
2224    ) -> Result<Option<[u8; 24]>, crate::error::Error> {
2225        let expiry_key = self.insert_frame_keys(batch, frame)?;
2226
2227        // The id may already have been indexed under another topic. Those
2228        // entries would otherwise survive their frame and answer for a topic
2229        // it no longer has. Only a restore gets here, so only it pays for the
2230        // keys.
2231        let moved_from = superseded.as_ref().filter(|old| old.topic != frame.topic);
2232        if let Some(old) = moved_from {
2233            let topic_key = idx_topic_key_from_frame(frame)?;
2234            let prefix_keys = idx_topic_prefix_keys(&frame.topic, &frame.id);
2235            let mut old_key = idx_topic_key_prefix(&old.topic);
2236            old_key.extend(frame.id.as_bytes());
2237            // "a.b" and "a.c" share the prefix key "a.", so drop only the keys
2238            // the write above is not putting straight back: removing and
2239            // inserting one key in one batch has no defined winner.
2240            for key in std::iter::once(old_key).chain(idx_topic_prefix_keys(&old.topic, &frame.id))
2241            {
2242                if key != topic_key && !prefix_keys.contains(&key) {
2243                    batch.remove(&self.idx_topic, key);
2244                }
2245            }
2246        }
2247        // A changed ttl moves the expiry entry, because the expiry is half of
2248        // its key. An unchanged one is the same key, already rewritten above
2249        // with whatever topic the frame now carries.
2250        if let Some(stale) = superseded
2251            .as_ref()
2252            .and_then(expires_at)
2253            .map(|at| idx_expiry_key(at, &frame.id))
2254            .filter(|stale| Some(*stale) != expiry_key)
2255        {
2256            batch.remove(&self.idx_expiry, stale);
2257        }
2258
2259        // Whether this write puts an entry on `frame.topic` that was not there
2260        // before. A brand new id does; so does an id arriving from another
2261        // topic. Only a replay onto the same topic does not, and counting one
2262        // of those puts the count above the truth, which deletes frames the
2263        // topic was told to keep.
2264        let fresh = superseded.is_none() || moved_from.is_some();
2265
2266        // The topic it left is now one shorter.
2267        if let Some(old) = moved_from {
2268            if let Some(count) = stage.count(self, &old.topic) {
2269                stage
2270                    .counts
2271                    .insert(old.topic.clone(), count.saturating_sub(1));
2272            }
2273        }
2274
2275        let keep = match frame.ttl {
2276            Some(TTL::Last(keep)) => Some(keep),
2277            _ => None,
2278        };
2279
2280        // A `last:n` frame makes its topic a counted one. If this is the first
2281        // the topic has seen, count what is already there, once, under the
2282        // lock: the entries on disk, plus any this batch already added to it.
2283        // Afterwards every frame moves that count whatever its own ttl: a
2284        // topic can mix ttls and every entry it holds takes a `keep` slot.
2285        let was = match (keep, stage.count(self, &frame.topic)) {
2286            (_, Some(count)) => Some(count),
2287            (Some(_), None) => Some(
2288                self.derive_count(&frame.topic)
2289                    + stage.uncounted.get(&frame.topic).copied().unwrap_or(0),
2290            ),
2291            (None, None) => None,
2292        };
2293
2294        let Some(was) = was else {
2295            // Not a counted topic, yet. Remember what this batch adds to it,
2296            // in case a later frame in the batch makes it one.
2297            if fresh && stage.watch_uncounted {
2298                *stage.uncounted.entry(frame.topic.clone()).or_default() += 1;
2299            }
2300            return Ok(expiry_key);
2301        };
2302        let now = if fresh { was + 1 } else { was };
2303
2304        // Over the cap, so take the oldest frame in this same batch. Exactly
2305        // one: a topic that is keeping up is over by one, and one that is
2306        // further behind -- grown by appends without a `last:n`, given a lower
2307        // `n`, or given more frames in one batch than it keeps -- is the gc
2308        // worker's to bring down. Only frames already on disk can be taken
2309        // here: one this batch added cannot be removed in the same batch,
2310        // because removing and inserting one key in one batch has no defined
2311        // winner.
2312        let over = keep.map_or(0, |keep| now.saturating_sub(u64::from(keep)));
2313        let taken = if over > 0 {
2314            let oldest = self.oldest_on_topic(&frame.topic, 1, &stage.taken);
2315            for old in &oldest {
2316                self.remove_frame_keys(batch, &old.id, &frame.topic, old.expires_at);
2317                stage.taken.insert(old.id);
2318            }
2319            stage.floors.insert(frame.topic.clone());
2320            oldest.len() as u64
2321        } else {
2322            0
2323        };
2324        if over > taken {
2325            if let Some(keep) = keep {
2326                let behind = stage.behind.entry(frame.topic.clone()).or_insert(keep);
2327                *behind = (*behind).min(keep);
2328            }
2329        }
2330        stage.counts.insert(frame.topic.clone(), now - taken);
2331        Ok(expiry_key)
2332    }
2333
2334    /// Undo what [`stage_frame`](Store::stage_frame) did outside the batch, for
2335    /// a batch that will not be committed. A trim moves its topic's floor
2336    /// past what it meant to remove, so put it back where a later trim will
2337    /// find them.
2338    fn unstage(&self, stage: &CountStage) {
2339        let mut floors = self.trim_floor.lock().unwrap();
2340        for topic in &stage.floors {
2341            floors.remove(topic);
2342        }
2343    }
2344
2345    /// Write the counts `stage` ended at, commit `batch`, and only then move
2346    /// the in-memory counts and tell the gc scans and readers about the
2347    /// frames in `stored`. A topic still over its cap goes to the gc worker,
2348    /// which takes the same lock and works in batches.
2349    ///
2350    /// Caller must hold [`write_lock`](Store::write_lock).
2351    fn commit_staged(
2352        &self,
2353        mut batch: OwnedWriteBatch,
2354        stored: &[(&Frame, Option<[u8; 24]>)],
2355        stage: CountStage,
2356    ) -> Result<(), crate::error::Error> {
2357        // One count row per topic, at what the whole batch left it.
2358        let mut edits = Vec::new();
2359        for (topic, now) in &stage.counts {
2360            edits.extend(self.stage_count(&mut batch, topic, *now));
2361        }
2362
2363        if let Err(e) = batch.commit() {
2364            // The frames did not land, and neither did the counts.
2365            self.unstage(&stage);
2366            return Err(e.into());
2367        }
2368        self.apply_counts(edits);
2369        for (frame, expiry_key) in stored {
2370            self.note_indexed(frame, *expiry_key);
2371        }
2372        for (topic, keep) in stage.behind {
2373            let _ = self.gc_tx.send(GCTask::CheckLastTTL { topic, keep });
2374        }
2375        self.after_commit()
2376    }
2377
2378    /// Queue the stream entry and index keys of a frame for insertion on
2379    /// `batch`, validating its topic first. Returns the frame's expiry index
2380    /// key, `Some` only for a `time:` frame. Nothing is done about an earlier
2381    /// frame under the same id, or about counts: that is
2382    /// [`stage_frame`](Store::stage_frame)'s job.
2383    fn insert_frame_keys(
2384        &self,
2385        batch: &mut OwnedWriteBatch,
2386        frame: &Frame,
2387    ) -> Result<Option<[u8; 24]>, crate::error::Error> {
2388        // Get the index topic key (also validates topic)
2389        let topic_key = idx_topic_key_from_frame(frame)?;
2390        let encoded: Vec<u8> = serde_json::to_vec(&frame).unwrap();
2391
2392        // Every idx_topic entry for this frame carries the same expiry, so a
2393        // topic scan can drop an expired id without reading the frame.
2394        let idx_value = idx_topic_expiry_value(frame);
2395
2396        batch.insert(&self.stream, frame.id.as_bytes(), encoded);
2397        batch.insert(&self.idx_topic, topic_key, idx_value);
2398        // Prefix index keys for hierarchical queries
2399        for prefix_key in idx_topic_prefix_keys(&frame.topic, &frame.id) {
2400            batch.insert(&self.idx_topic, prefix_key, idx_value);
2401        }
2402        // A time: frame is also indexed by its expiry, for the sweeper
2403        let expiry_key = expires_at(frame).map(|at| idx_expiry_key(at, &frame.id));
2404        if let Some(key) = expiry_key {
2405            batch.insert(&self.idx_expiry, key, frame.topic.as_bytes());
2406        }
2407        Ok(expiry_key)
2408    }
2409
2410    /// Note a committed frame's index entries. Both gc scans resume where
2411    /// they last stopped, and an id from the past, or a short `time:` ttl, can
2412    /// land behind them. Tell them, once the entries are there to be found.
2413    fn note_indexed(&self, frame: &Frame, expiry_key: Option<[u8; 24]>) {
2414        if let Some(key) = expiry_key {
2415            self.note_indexed_expiry(key);
2416        }
2417        self.note_indexed_topic(&frame.topic, &frame.id);
2418    }
2419
2420    /// Append a frame to the stream and return it with its freshly assigned
2421    /// [`id`](Frame::id).
2422    ///
2423    /// This is the primary write path. It:
2424    ///
2425    /// - assigns a new time-sortable ID (overwriting any ID on the input);
2426    /// - validates the topic (see [`validate_topic`]);
2427    /// - persists the frame, unless its [`TTL`] is [`TTL::Ephemeral`], in which
2428    ///   case it is only broadcast to live readers;
2429    /// - for a [`TTL::Last`] frame, trims the topic back to its limit in the
2430    ///   same commit;
2431    /// - broadcasts the frame to everyone currently in a following
2432    ///   [`read`](Store::read).
2433    ///
2434    /// Appends are serialized internally, so frames are assigned IDs and
2435    /// delivered to subscribers in a consistent order.
2436    ///
2437    /// # Errors
2438    ///
2439    /// Returns an error if the topic is invalid or the underlying write fails.
2440    ///
2441    /// ```no_run
2442    /// use xs::{Store, Frame, TTL};
2443    ///
2444    /// # async fn run(store: Store) -> Result<(), xs::Error> {
2445    /// let hash = store.cas_insert("hello clipboard").await?;
2446    /// let frame = store.append(
2447    ///     Frame::builder("clip.add").hash(hash).ttl(TTL::Last(100)).build(),
2448    /// )?;
2449    /// println!("appended {}", frame.id);
2450    /// # Ok(())
2451    /// # }
2452    /// ```
2453    pub fn append(&self, frame: Frame) -> Result<Frame, crate::error::Error> {
2454        let mut frames = self.append_many(vec![frame])?;
2455        Ok(frames
2456            .pop()
2457            .expect("append_many returns one frame per input"))
2458    }
2459
2460    /// Append several frames as one write and return them with their freshly
2461    /// assigned [`id`](Frame::id)s, in order.
2462    ///
2463    /// Each frame is handled as [`append`](Store::append) handles one, but
2464    /// together: the frames get consecutive ids with no other append between
2465    /// them, every topic is validated before anything is written, and the
2466    /// non-ephemeral frames are committed in a single batch. Only once that
2467    /// commit succeeds are the frames broadcast, in order, and `last:n`
2468    /// retention scheduled.
2469    ///
2470    /// # Errors
2471    ///
2472    /// Returns an error if any topic is invalid or the write fails. Either
2473    /// way nothing is stored and nothing is broadcast. Under
2474    /// [`Fsync::Always`], a failed sync after the commit also returns an
2475    /// error: the frames are written but not broadcast.
2476    pub fn append_many(&self, mut frames: Vec<Frame>) -> Result<Vec<Frame>, crate::error::Error> {
2477        // Serialize all writes to ensure ID generation, write, and broadcast
2478        // happen atomically. This guarantees subscribers receive frames in
2479        // scru128 ID order, and the `last:n` counts see one writer at a time.
2480        let _guard = self.write_guard();
2481
2482        for frame in frames.iter_mut() {
2483            frame.id = scru128::new();
2484        }
2485
2486        // Queue the frames that are not ephemeral, and check the topic of
2487        // every frame. An invalid one returns here, before the commit, so the
2488        // batch is dropped with nothing written.
2489        let mut batch = self.db.batch();
2490        let mut stage = CountStage {
2491            watch_uncounted: frames.len() > 1
2492                && frames.iter().any(|f| matches!(f.ttl, Some(TTL::Last(_)))),
2493            ..CountStage::default()
2494        };
2495        let mut stored = Vec::new();
2496        for frame in &frames {
2497            let staged = if frame.ttl == Some(TTL::Ephemeral) {
2498                idx_topic_key_from_frame(frame).map(|_| None)
2499            } else {
2500                // A fresh id, so it cannot already be in the stream.
2501                self.stage_frame(&mut batch, frame, None, &mut stage)
2502                    .map(Some)
2503            };
2504            match staged {
2505                Ok(Some(expiry_key)) => stored.push((frame, expiry_key)),
2506                Ok(None) => {}
2507                Err(e) => {
2508                    self.unstage(&stage);
2509                    return Err(e);
2510                }
2511            }
2512        }
2513        if !stored.is_empty() {
2514            self.commit_staged(batch, &stored, stage)?;
2515        }
2516
2517        self.stats
2518            .appends
2519            .fetch_add(frames.len(), Ordering::Relaxed);
2520        for frame in &frames {
2521            let _ = self.broadcast_tx.send(frame.clone());
2522        }
2523        Ok(frames)
2524    }
2525
2526    /// Iterate frames starting from a bound.
2527    /// `start` is `(id, inclusive)` where inclusive=true means >= and inclusive=false means >.
2528    fn iter_frames(
2529        &self,
2530        start: Option<(Scru128Id, bool)>,
2531    ) -> Box<dyn Iterator<Item = Frame> + '_> {
2532        let range = match start {
2533            Some((id, true)) => (Bound::Included(id.as_bytes().to_vec()), Bound::Unbounded),
2534            Some((id, false)) => (Bound::Excluded(id.as_bytes().to_vec()), Bound::Unbounded),
2535            None => (Bound::Unbounded, Bound::Unbounded),
2536        };
2537
2538        let scanned = self.stats.clone();
2539        Box::new(self.stream.range(range).filter_map(move |guard| {
2540            scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
2541            let (key, value) = guard.into_inner().ok()?;
2542            Some(deserialize_frame((key, value)))
2543        }))
2544    }
2545
2546    /// Iterate frames in reverse order (most recent first).
2547    fn iter_frames_rev(&self) -> Box<dyn Iterator<Item = Frame> + '_> {
2548        let scanned = self.stats.clone();
2549        Box::new(self.stream.iter().rev().filter_map(move |guard| {
2550            scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
2551            let (key, value) = guard.into_inner().ok()?;
2552            Some(deserialize_frame((key, value)))
2553        }))
2554    }
2555
2556    /// Iterate frames by topic in reverse order (most recent first).
2557    fn iter_frames_by_topic_rev(&self, topic: &str) -> Box<dyn Iterator<Item = Frame> + '_> {
2558        let prefix = idx_topic_key_prefix(topic);
2559        let now = now_ms();
2560        let scanned = self.stats.clone();
2561        Box::new(
2562            self.idx_topic
2563                .prefix(prefix)
2564                .rev()
2565                .filter_map(move |guard| {
2566                    scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
2567                    self.get(&idx_topic_hit_id(guard, now)?)
2568                }),
2569        )
2570    }
2571
2572    /// Iterate frames by topic prefix in reverse order (most recent first).
2573    fn iter_frames_by_topic_prefix_rev(
2574        &self,
2575        prefix: &str,
2576    ) -> Box<dyn Iterator<Item = Frame> + '_> {
2577        let mut index_prefix = Vec::with_capacity(prefix.len() + 1);
2578        index_prefix.extend(prefix.as_bytes());
2579        index_prefix.push(NULL_DELIMITER);
2580
2581        let now = now_ms();
2582        let scanned = self.stats.clone();
2583
2584        Box::new(
2585            self.idx_topic
2586                .prefix(index_prefix)
2587                .rev()
2588                .filter_map(move |guard| {
2589                    scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
2590                    self.get(&idx_topic_hit_id(guard, now)?)
2591                }),
2592        )
2593    }
2594
2595    /// Iterate frames on an exact topic, ascending by frame id, from `start`.
2596    fn iter_frames_by_topic(
2597        &self,
2598        topic: &str,
2599        start: Option<(Scru128Id, bool)>,
2600    ) -> Box<dyn Iterator<Item = Frame> + '_> {
2601        let range = idx_topic_range(idx_topic_key_prefix(topic), start);
2602        let now = now_ms();
2603        let scanned = self.stats.clone();
2604        Box::new(self.idx_topic.range(range).filter_map(move |guard| {
2605            scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
2606            self.get(&idx_topic_hit_id(guard, now)?)
2607        }))
2608    }
2609
2610    /// Iterate frames matching a topic prefix (for wildcard queries like "user.*").
2611    /// The prefix should include the trailing dot (e.g., "user." for "user.*").
2612    fn iter_frames_by_topic_prefix(
2613        &self,
2614        prefix: &str,
2615        start: Option<(Scru128Id, bool)>,
2616    ) -> Box<dyn Iterator<Item = Frame> + '_> {
2617        // Build index prefix: "user.\0" for scanning all "user.*" entries
2618        let mut index_prefix = Vec::with_capacity(prefix.len() + 1);
2619        index_prefix.extend(prefix.as_bytes());
2620        index_prefix.push(NULL_DELIMITER);
2621
2622        let range = idx_topic_range(index_prefix, start);
2623        let now = now_ms();
2624        let scanned = self.stats.clone();
2625
2626        Box::new(self.idx_topic.range(range).filter_map(move |guard| {
2627            scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
2628            self.get(&idx_topic_hit_id(guard, now)?)
2629        }))
2630    }
2631
2632    /// Forward iterator for a single pattern, using the topic index.
2633    fn iter_for_pattern(
2634        &self,
2635        pattern: Pattern,
2636        start: Option<(Scru128Id, bool)>,
2637    ) -> Box<dyn Iterator<Item = Frame> + '_> {
2638        match pattern {
2639            Pattern::Exact(topic) => self.iter_frames_by_topic(&topic, start),
2640            Pattern::Prefix(prefix) => self.iter_frames_by_topic_prefix(&prefix, start),
2641        }
2642    }
2643
2644    /// Reverse (most recent first) iterator for a single pattern.
2645    fn iter_for_pattern_rev(&self, pattern: Pattern) -> Box<dyn Iterator<Item = Frame> + '_> {
2646        match pattern {
2647            Pattern::Exact(topic) => self.iter_frames_by_topic_rev(&topic),
2648            Pattern::Prefix(prefix) => self.iter_frames_by_topic_prefix_rev(&prefix),
2649        }
2650    }
2651
2652    /// Forward iterator for a parsed topic filter, ascending by frame id.
2653    /// A single pattern uses the indexed path directly; multiple patterns
2654    /// are k-way merged with dedupe for overlapping patterns.
2655    fn iter_for_filter(
2656        &self,
2657        filter: TopicFilter,
2658        start: Option<(Scru128Id, bool)>,
2659    ) -> Box<dyn Iterator<Item = Frame> + '_> {
2660        match filter {
2661            TopicFilter::All => self.iter_frames(start),
2662            TopicFilter::Patterns(mut patterns) if patterns.len() == 1 => {
2663                self.iter_for_pattern(patterns.remove(0), start)
2664            }
2665            TopicFilter::Patterns(patterns) => {
2666                let iters = patterns
2667                    .into_iter()
2668                    .map(|p| self.iter_for_pattern(p, start))
2669                    .collect();
2670                Box::new(MergeById::new(iters, false))
2671            }
2672        }
2673    }
2674
2675    /// Reverse variant of [`iter_for_filter`](Store::iter_for_filter),
2676    /// descending by frame id (most recent first).
2677    fn iter_for_filter_rev(&self, filter: TopicFilter) -> Box<dyn Iterator<Item = Frame> + '_> {
2678        match filter {
2679            TopicFilter::All => self.iter_frames_rev(),
2680            TopicFilter::Patterns(mut patterns) if patterns.len() == 1 => {
2681                self.iter_for_pattern_rev(patterns.remove(0))
2682            }
2683            TopicFilter::Patterns(patterns) => {
2684                let iters = patterns
2685                    .into_iter()
2686                    .map(|p| self.iter_for_pattern_rev(p))
2687                    .collect();
2688                Box::new(MergeById::new(iters, true))
2689            }
2690        }
2691    }
2692}
2693
2694fn spawn_gc_worker(
2695    mut gc_rx: UnboundedReceiver<GCTask>,
2696    mut store: Store,
2697) -> std::thread::JoinHandle<()> {
2698    // The worker's own clone must not hold a live `gc_tx`, or the channel
2699    // never closes and the worker, the database, and the fsync worker outlive
2700    // every caller's handle. Give it a sender whose receiver is already gone.
2701    let (closed_tx, _) = mpsc::unbounded_channel();
2702    store.gc_tx = closed_tx;
2703
2704    // One drain per wake: take the task that woke us and whatever else is
2705    // queued, up to the cap, and apply every removal in one batch with one
2706    // commit. A Drain is answered after that commit, so every task queued
2707    // before it has been applied by the time its reply lands.
2708    const MAX_TASKS_PER_DRAIN: usize = 1024;
2709    // A sweep removes at most this many frames. When it fills the cap the
2710    // next drain starts with another sweep, without waiting for the tick.
2711    const MAX_SWEEP_PER_DRAIN: usize = 4096;
2712    // A last:n trim removes at most this many frames per topic per drain, and
2713    // is carried over the same way a full sweep is. Without a cap the first
2714    // trim of a topic with a backlog collects every id past `keep` at once.
2715    const MAX_TRIM_PER_DRAIN: usize = 4096;
2716
2717    std::thread::spawn(move || {
2718        // Tasks a full batch left unfinished, run first in the next drain.
2719        let mut carried: Vec<GCTask> = Vec::new();
2720        loop {
2721            if carried.is_empty() {
2722                match gc_rx.blocking_recv() {
2723                    Some(task) => carried.push(task),
2724                    None => break,
2725                }
2726            }
2727
2728            let drain_started = std::time::Instant::now();
2729
2730            // Ids in this drain, so a last:n scan and a sweep never count or
2731            // queue a frame twice.
2732            let mut pending = HashSet::new();
2733            // How many of those sit on each counted topic. A pending frame
2734            // still holds its slot in the count until the batch commits, so a
2735            // trim has to take them off before deciding how far over the
2736            // topic is.
2737            let mut pending_by_topic: HashMap<String, u64> = HashMap::new();
2738            let mut removals = Vec::new();
2739            let mut drains = Vec::new();
2740            let mut sweep_again = false;
2741            // Topics whose trim filled its cap, one entry each however many
2742            // tasks for them this drain took.
2743            let mut trim_again: HashMap<String, u32> = HashMap::new();
2744            // Topics this drain must trim, collapsed from however many tasks
2745            // asked. Scanned after the take loop so every Sweep has already
2746            // run: an expired frame is hidden from reads, so it must not hold
2747            // a keep slot.
2748            let mut trims: HashMap<String, u32> = HashMap::new();
2749            let mut taken = 0;
2750            while taken < MAX_TASKS_PER_DRAIN {
2751                let Some(task) = carried.pop().or_else(|| gc_rx.try_recv().ok()) else {
2752                    break;
2753                };
2754                match task {
2755                    GCTask::CheckLastTTL { topic, keep } => {
2756                        // One scan per topic per drain, at the smallest keep
2757                        // asked for. A second scan for the same topic filters
2758                        // out everything the first collected, skips keep, and
2759                        // walks the rest to return nothing.
2760                        trims
2761                            .entry(topic)
2762                            .and_modify(|k| *k = (*k).min(keep))
2763                            .or_insert(keep);
2764                    }
2765                    GCTask::Sweep => {
2766                        let expired = store.expired_at(now_ms(), MAX_SWEEP_PER_DRAIN);
2767                        sweep_again |= expired.len() == MAX_SWEEP_PER_DRAIN;
2768                        for removal in expired {
2769                            if pending.insert(removal.id()) {
2770                                if let Removal::Indexed { topic, .. } = &removal {
2771                                    *pending_by_topic.entry(topic.clone()).or_insert(0) += 1;
2772                                }
2773                                removals.push(removal);
2774                            }
2775                        }
2776                    }
2777                    GCTask::Drain(tx) => drains.push(tx),
2778                }
2779                taken += 1;
2780            }
2781
2782            // One hold for the whole of the rest of the drain: each trim reads
2783            // a count, reads the frames that count says are over, and removes
2784            // them, and an append landing between any two of those steps
2785            // makes the third one wrong.
2786            let write_guard = store.write_guard();
2787
2788            // Now that every Sweep in this drain has run, so `pending` holds
2789            // the expired frames it is removing, trim each topic once.
2790            for (topic, keep) in trims {
2791                let pending_here = pending_by_topic.get(&topic).copied().unwrap_or(0);
2792                let overflow =
2793                    store.last_overflow(&topic, keep, &pending, pending_here, MAX_TRIM_PER_DRAIN);
2794                let again = overflow.len() == MAX_TRIM_PER_DRAIN;
2795                for frame in overflow {
2796                    if pending.insert(frame.id) {
2797                        removals.push(Removal::Indexed {
2798                            id: frame.id,
2799                            topic: topic.clone(),
2800                            expires_at: frame.expires_at,
2801                        });
2802                    }
2803                }
2804                if again {
2805                    trim_again.insert(topic, keep);
2806                }
2807            }
2808
2809            let removed = store.remove_many_locked(removals);
2810            drop(write_guard);
2811            if let Err(e) = removed {
2812                tracing::error!("gc remove failed: {e}");
2813                // The batch did not land, so every frame this drain counted as
2814                // gone is still there, below resume points that have already
2815                // moved past it. Start both scans over.
2816                store.reset_gc_resume();
2817            }
2818            store.stats.gc_drains.fetch_add(1, Ordering::Relaxed);
2819            store
2820                .stats
2821                .gc_nanos
2822                .fetch_add(drain_started.elapsed().as_nanos() as u64, Ordering::Relaxed);
2823            for tx in drains {
2824                let _ = tx.send(());
2825            }
2826            carried.extend(
2827                trim_again
2828                    .into_iter()
2829                    .map(|(topic, keep)| GCTask::CheckLastTTL { topic, keep }),
2830            );
2831            if sweep_again {
2832                carried.push(GCTask::Sweep);
2833            }
2834        }
2835    })
2836}
2837
2838/// Fsync the journal every `interval` when something was written since the
2839/// last tick. No final persist is needed on stop: fjall syncs the journal
2840/// when the database closes.
2841fn spawn_fsync_tick(db: Database, state: Arc<FsyncState>, interval: Duration) -> Tick {
2842    Tick::spawn(interval, move || {
2843        if state.dirty.swap(false, Ordering::AcqRel) {
2844            if let Err(e) = db.persist(PersistMode::SyncAll) {
2845                tracing::error!("fsync failed: {e}");
2846            }
2847        }
2848    })
2849}
2850
2851/// Queue a [`GCTask::Sweep`] every `interval`. The gc worker does the scan
2852/// and the removals, so a slow sweep never blocks the tick.
2853fn spawn_sweep_tick(gc_tx: UnboundedSender<GCTask>, interval: Duration) -> Tick {
2854    Tick::spawn(interval, move || {
2855        let _ = gc_tx.send(GCTask::Sweep);
2856    })
2857}
2858
2859fn now_ms() -> u64 {
2860    std::time::SystemTime::now()
2861        .duration_since(std::time::UNIX_EPOCH)
2862        .unwrap()
2863        .as_millis() as u64
2864}
2865
2866/// When a `time:` frame expires, in ms since the epoch: its id's timestamp
2867/// plus its ttl. `None` for any other ttl.
2868fn expires_at(frame: &Frame) -> Option<u64> {
2869    match frame.ttl.as_ref() {
2870        Some(TTL::Time(ttl)) => Some(frame.id.timestamp().saturating_add(ttl.as_millis() as u64)),
2871        _ => None,
2872    }
2873}
2874
2875/// Has this frame's `time:` ttl passed? Matches the sweeper's cut-off, so a
2876/// frame is hidden from reads from the moment it becomes sweepable.
2877fn is_expired(frame: &Frame) -> bool {
2878    matches!(expires_at(frame), Some(at) if now_ms() >= at)
2879}
2880
2881/// Expiry index key: expiry in ms as big-endian u64, then the frame id. Sorts
2882/// by expiry, so a range scan up to now yields exactly the expired frames.
2883fn idx_expiry_key(expires_at: u64, id: &Scru128Id) -> [u8; 24] {
2884    let mut key = [0u8; 24];
2885    key[..8].copy_from_slice(&expires_at.to_be_bytes());
2886    key[8..].copy_from_slice(id.as_bytes());
2887    key
2888}
2889
2890fn idx_expiry_parse_key(key: &[u8]) -> (u64, Scru128Id) {
2891    let expires_at = u64::from_be_bytes(key[..8].try_into().unwrap());
2892    let id = Scru128Id::from_bytes(key[8..24].try_into().unwrap());
2893    (expires_at, id)
2894}
2895
2896/// Live frames held for a following read that has not taken them yet.
2897///
2898/// A following read subscribes only after it has sent the stored frames, so
2899/// this covers the catch-up and live frames, not the replay (ADR 0008). A
2900/// reader that falls further behind than this has its read ended with
2901/// [`ReadError::Lagged`] rather than silently skipped: see the `Lagged` arm in
2902/// [`read`](Store::read). Raising it buys a slow reader more room before that
2903/// happens, at a frame of memory per slot per follower.
2904pub(crate) const FOLLOW_BUFFER: usize = 4096;
2905
2906/// What [`Store::read`] yields: a frame, or the error that ended the read.
2907pub type ReadItem = Result<Frame, ReadError>;
2908
2909/// Why a following read ended before its reader dropped it (ADR 0008).
2910#[derive(Debug, Clone, PartialEq, Eq)]
2911pub enum ReadError {
2912    /// The reader fell more than [`FOLLOW_BUFFER`] frames behind the live
2913    /// stream; `skipped` frames went by unseen.
2914    Lagged { skipped: u64 },
2915}
2916
2917impl std::fmt::Display for ReadError {
2918    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
2919        match self {
2920            ReadError::Lagged { skipped } => {
2921                write!(f, "fell behind the live stream: {skipped} frames skipped")
2922            }
2923        }
2924    }
2925}
2926
2927impl std::error::Error for ReadError {}
2928
2929impl ReadError {
2930    /// The error as the last frame of a stream over the wire, where a Rust
2931    /// error cannot go: `xs.lagged`, with `{"skipped": n}` as its meta.
2932    pub fn to_frame(&self) -> Frame {
2933        match self {
2934            ReadError::Lagged { skipped } => Frame::builder("xs.lagged")
2935                .id(scru128::new())
2936                .ttl(TTL::Ephemeral)
2937                .meta(serde_json::json!({ "skipped": skipped }))
2938                .build(),
2939        }
2940    }
2941}
2942
2943/// What a following read's scan of the stored frames hands the follow task:
2944/// the live subscription, taken after the first scan, the last id sent, and
2945/// the count so far against `limit`.
2946struct FollowFrom {
2947    broadcast_rx: broadcast::Receiver<Frame>,
2948    last_id: Option<Scru128Id>,
2949    count: usize,
2950}
2951
2952const NULL_DELIMITER: u8 = 0;
2953const MAX_TOPIC_LENGTH: usize = 255;
2954
2955/// Validate a frame topic (per ADR 0001).
2956///
2957/// A topic must be non-empty and at most 255 bytes, start with an ASCII letter
2958/// or `_`, and contain only `a-z A-Z 0-9 _ - .`. It may not end with `.` or
2959/// contain consecutive dots. [`Store::append`] runs this automatically; call it
2960/// directly to validate user input before building a [`Frame`].
2961///
2962/// ```
2963/// use xs::store::validate_topic;
2964///
2965/// assert!(validate_topic("clip.add").is_ok());
2966/// assert!(validate_topic("clip.").is_err());
2967/// ```
2968pub fn validate_topic(topic: &str) -> Result<(), crate::error::Error> {
2969    if topic.is_empty() {
2970        return Err("Topic cannot be empty".to_string().into());
2971    }
2972    if topic.len() > MAX_TOPIC_LENGTH {
2973        return Err(format!("Topic exceeds max length of {MAX_TOPIC_LENGTH} bytes").into());
2974    }
2975    if topic.ends_with('.') {
2976        return Err("Topic cannot end with '.'".to_string().into());
2977    }
2978    if topic.contains("..") {
2979        return Err("Topic cannot contain consecutive dots".to_string().into());
2980    }
2981
2982    let bytes = topic.as_bytes();
2983    let first = bytes[0];
2984    if !first.is_ascii_alphabetic() && first != b'_' {
2985        return Err("Topic must start with a-z, A-Z, or _".to_string().into());
2986    }
2987
2988    for &b in bytes {
2989        if !b.is_ascii_alphanumeric() && b != b'_' && b != b'-' && b != b'.' {
2990            return Err(format!(
2991                "Topic contains invalid character: '{}'. Allowed: a-z A-Z 0-9 _ - .",
2992                b as char
2993            )
2994            .into());
2995        }
2996    }
2997
2998    Ok(())
2999}
3000
3001/// Validates a topic query (for --topic flag).
3002/// Accepts a comma-separated list of patterns; each element is an exact
3003/// topic, a `prefix.*` wildcard, or `*` (match all).
3004pub fn validate_topic_query(spec: &str) -> Result<(), crate::error::Error> {
3005    let mut seen = false;
3006    for part in spec.split(',') {
3007        let part = part.trim();
3008        if part.is_empty() {
3009            continue;
3010        }
3011        seen = true;
3012        validate_topic_pattern(part)?;
3013    }
3014    if !seen {
3015        return Err("Topic query cannot be empty".to_string().into());
3016    }
3017    Ok(())
3018}
3019
3020/// Validate a single topic pattern: "*", "prefix.*", or an exact topic.
3021fn validate_topic_pattern(topic: &str) -> Result<(), crate::error::Error> {
3022    if topic == "*" {
3023        return Ok(());
3024    }
3025    if let Some(prefix) = topic.strip_suffix(".*") {
3026        // Validate the prefix part (e.g., "user" in "user.*")
3027        // Prefix can be empty edge case: ".*" is not valid
3028        if prefix.is_empty() {
3029            return Err("Wildcard '.*' requires a prefix".to_string().into());
3030        }
3031        validate_topic(prefix)
3032    } else {
3033        validate_topic(topic)
3034    }
3035}
3036
3037/// Generate prefix index keys for hierarchical topic queries.
3038/// For topic "user.id1.messages", returns keys for prefixes "user." and "user.id1."
3039fn idx_topic_prefix_keys(topic: &str, frame_id: &scru128::Scru128Id) -> Vec<Vec<u8>> {
3040    let mut keys = Vec::new();
3041    let mut pos = 0;
3042    while let Some(dot_pos) = topic[pos..].find('.') {
3043        let prefix = &topic[..pos + dot_pos + 1]; // include the dot
3044        let mut key = Vec::with_capacity(prefix.len() + 1 + 16);
3045        key.extend(prefix.as_bytes());
3046        key.push(NULL_DELIMITER);
3047        key.extend(frame_id.as_bytes());
3048        keys.push(key);
3049        pos += dot_pos + 1;
3050    }
3051    keys
3052}
3053
3054/// An `idx_topic` value meaning "this frame has no `time:` ttl". Distinct from
3055/// the empty value an older store wrote, which means "unknown".
3056const IDX_TOPIC_NEVER: u64 = u64::MAX;
3057
3058/// What one write batch has done to the `last:n` counts so far, so several
3059/// frames on one topic in one batch count and trim as they would one at a
3060/// time. See [`Store::stage_frame`].
3061#[derive(Default)]
3062struct CountStage {
3063    /// Each counted topic's count, as the batch has left it so far.
3064    counts: HashMap<String, u64>,
3065    /// Frames this batch has added to a topic that is not counted (yet).
3066    uncounted: HashMap<String, u64>,
3067    /// Whether to keep `uncounted` at all: only a batch of several frames,
3068    /// one of them `last:n`, can start counting a topic part way through.
3069    watch_uncounted: bool,
3070    /// Frames this batch is already removing.
3071    taken: HashSet<Scru128Id>,
3072    /// Topics whose trim floor this batch moved.
3073    floors: HashSet<String>,
3074    /// Topics still over their cap once this batch commits, with the
3075    /// smallest `keep` asked for: the gc worker's to bring down.
3076    behind: HashMap<String, u32>,
3077}
3078
3079impl CountStage {
3080    /// `topic`'s count as this batch has left it, or the committed one.
3081    fn count(&self, store: &Store, topic: &str) -> Option<u64> {
3082        self.counts
3083            .get(topic)
3084            .copied()
3085            .or_else(|| store.count_of(topic))
3086    }
3087}
3088
3089/// One frame a `last:n` trim is going to remove, with everything
3090/// [`Store::remove_many`] needs to delete its keys. The topic is the one being
3091/// trimmed and the expiry came off the index entry, so no point read is needed.
3092#[derive(Debug, Clone, Copy)]
3093struct Overflow {
3094    id: Scru128Id,
3095    /// `Some` when the frame has a `time:` ttl and so an expiry index entry.
3096    /// `None` when it has none, or when the entry predates the index carrying
3097    /// one -- see [`idx_topic_expiry_of`].
3098    expires_at: Option<u64>,
3099}
3100
3101/// The expiry an `idx_topic` value carries, if it carries one.
3102///
3103/// `None` covers two cases the caller must treat alike: a frame with no `time:`
3104/// ttl, which has no expiry index entry to delete, and an entry written before
3105/// the index carried an expiry, whose frame may have one. Removing a key that
3106/// is not there is a no-op, so both are safe to treat as "nothing to delete" --
3107/// but the second leaves a stale expiry entry, which the sweeper drops on its
3108/// next pass when the point read finds no frame.
3109#[inline]
3110fn idx_topic_expiry_of(value: &[u8]) -> Option<u64> {
3111    match <[u8; 8]>::try_from(value) {
3112        Ok(bytes) => match u64::from_be_bytes(bytes) {
3113            IDX_TOPIC_NEVER => None,
3114            at => Some(at),
3115        },
3116        Err(_) => None,
3117    }
3118}
3119
3120/// The `idx_topic` value for a frame: its expiry in ms as a big-endian u64, or
3121/// [`IDX_TOPIC_NEVER`]. Every entry for the frame -- the exact topic key and
3122/// each prefix key -- gets the same eight bytes, so a topic scan can drop an
3123/// expired id without a point read into `stream`.
3124fn idx_topic_expiry_value(frame: &Frame) -> [u8; 8] {
3125    expires_at(frame).unwrap_or(IDX_TOPIC_NEVER).to_be_bytes()
3126}
3127
3128/// Has the frame behind this `idx_topic` value expired as of `now`? A value
3129/// that is not eight bytes -- an entry written before the index carried an
3130/// expiry -- reads as "unknown" and answers `false`, so the caller falls back
3131/// to reading the frame and letting [`is_expired`] decide. Both shapes can sit
3132/// in one index.
3133///
3134/// The arithmetic matches [`expires_at`] exactly, so this never hides a frame
3135/// [`is_expired`] would keep.
3136#[inline]
3137fn idx_topic_is_expired(value: &[u8], now: u64) -> bool {
3138    match <[u8; 8]>::try_from(value) {
3139        Ok(bytes) => {
3140            let expires_at = u64::from_be_bytes(bytes);
3141            expires_at != IDX_TOPIC_NEVER && now >= expires_at
3142        }
3143        Err(_) => false,
3144    }
3145}
3146
3147/// The frame id an `idx_topic` hit points at, or `None` to skip the hit
3148/// entirely.
3149///
3150/// The entry's value carries the frame's expiry, so an already expired id is
3151/// dropped here without the point read into `stream` that seeing its ttl would
3152/// otherwise take. `now` is sampled once when the iterator is built, which only
3153/// ever skips fewer frames than a fresh sample would: [`is_expired`] still runs
3154/// on everything that gets through, so the two never disagree about what is
3155/// visible.
3156#[inline]
3157fn idx_topic_hit_id(guard: fjall::Guard, now: u64) -> Option<Scru128Id> {
3158    let (key, value) = guard.into_inner().ok()?;
3159    if idx_topic_is_expired(&value, now) {
3160        return None;
3161    }
3162    Some(idx_topic_frame_id_from_key(&key))
3163}
3164
3165/// The `idx_topic` key range covering one index prefix, opening at `start`
3166/// when there is one.
3167///
3168/// Every key under a prefix is that prefix followed by the frame's 16 byte id,
3169/// and ids sort ascending, so a bound on the id is a bound on the key. Seeking
3170/// to it beats walking the topic from its first entry and discarding
3171/// everything below: on a topic holding 500k frames, reading `after` a recent
3172/// id touches a handful of index entries instead of all 500k.
3173///
3174/// The upper bound is the prefix plus all ones, the largest key the prefix can
3175/// hold. A topic never contains the NUL delimiter, so no other topic's keys
3176/// fall inside the range.
3177fn idx_topic_range(
3178    prefix: Vec<u8>,
3179    start: Option<(Scru128Id, bool)>,
3180) -> (Bound<Vec<u8>>, Bound<Vec<u8>>) {
3181    fn key_at(prefix: &[u8], id: &[u8; 16]) -> Vec<u8> {
3182        let mut key = Vec::with_capacity(prefix.len() + 16);
3183        key.extend_from_slice(prefix);
3184        key.extend_from_slice(id);
3185        key
3186    }
3187
3188    let hi = Bound::Included(key_at(&prefix, &[0xff; 16]));
3189    let lo = match start {
3190        Some((id, true)) => Bound::Included(key_at(&prefix, id.as_bytes())),
3191        Some((id, false)) => Bound::Excluded(key_at(&prefix, id.as_bytes())),
3192        // Shorter than every key it covers, so it sorts before all of them.
3193        None => Bound::Included(prefix),
3194    };
3195    (lo, hi)
3196}
3197
3198fn idx_topic_key_prefix(topic: &str) -> Vec<u8> {
3199    let mut v = Vec::with_capacity(topic.len() + 1); // topic bytes + delimiter
3200    v.extend(topic.as_bytes()); // topic string as UTF-8 bytes
3201    v.push(NULL_DELIMITER); // Delimiter for variable-sized keys
3202    v
3203}
3204
3205pub(crate) fn idx_topic_key_from_frame(frame: &Frame) -> Result<Vec<u8>, crate::error::Error> {
3206    validate_topic(&frame.topic)?;
3207    let mut v = idx_topic_key_prefix(&frame.topic);
3208    v.extend(frame.id.as_bytes());
3209    Ok(v)
3210}
3211
3212fn idx_topic_frame_id_from_key(key: &[u8]) -> Scru128Id {
3213    let frame_id_bytes = &key[key.len() - 16..];
3214    Scru128Id::from_bytes(frame_id_bytes.try_into().unwrap())
3215}
3216
3217/// What one [`Store::cas_gc`] pass found and did.
3218#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize)]
3219pub struct CasGcReport {
3220    /// Content files a stored frame points at: kept.
3221    pub in_use: u64,
3222    /// Content files nothing points at, but written within the grace: kept.
3223    pub recent: u64,
3224    /// Content files nothing points at, older than the grace: deleted.
3225    pub deleted: u64,
3226    /// The size of the deleted files, in bytes.
3227    pub bytes_freed: u64,
3228}
3229
3230/// Every file under `dir`, at any depth.
3231fn content_files(dir: &std::path::Path, out: &mut Vec<PathBuf>) -> std::io::Result<()> {
3232    for entry in std::fs::read_dir(dir)? {
3233        let entry = entry?;
3234        if entry.file_type()?.is_dir() {
3235            content_files(&entry.path(), out)?;
3236        } else {
3237            out.push(entry.path());
3238        }
3239    }
3240    Ok(())
3241}
3242
3243/// Decode a stored frame, or panic saying which one could not be decoded.
3244///
3245/// A value that will not decode means the store is damaged. Skipping it would
3246/// hand the caller a partial answer with nothing to say so; panicking fails
3247/// the operation that found it, loudly, and leaves the rest of the store
3248/// serving. See [`Store::write_guard`] for why that panic does not also take
3249/// down every later write.
3250fn deserialize_frame<B1: AsRef<[u8]> + std::fmt::Debug, B2: AsRef<[u8]>>(
3251    record: (B1, B2),
3252) -> Frame {
3253    serde_json::from_slice(record.1.as_ref()).unwrap_or_else(|e| {
3254        let key = record.0.as_ref();
3255        // A `stream` key is a raw 16-byte id, so print it as an id: that is
3256        // the form `xs remove` takes. Anything else is an index key, which is
3257        // a topic and an id, so show it as text.
3258        let key = match <[u8; 16]>::try_from(key) {
3259            Ok(bytes) => Scru128Id::from_bytes(bytes).to_string(),
3260            Err(_) => String::from_utf8_lossy(key).into_owned(),
3261        };
3262        // Lossy, and never unwrapped: the whole point of being here is that
3263        // these bytes are not what they claim to be.
3264        let value = String::from_utf8_lossy(record.1.as_ref());
3265        panic!("corrupt frame in the store\n  key:   {key}\n  error: {e}\n  value: {value}")
3266    })
3267}