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