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.
1080 ///
1081 /// The returned [`Receiver`](tokio::sync::mpsc::Receiver) is bounded;
1082 /// dropping it stops the read. For a blocking, non-async caller use
1083 /// [`read_sync`](Store::read_sync).
1084 ///
1085 /// ```no_run
1086 /// use xs::{Store, ReadOptions, FollowOption};
1087 ///
1088 /// # async fn run(store: Store) {
1089 /// let mut rx = store.read(ReadOptions::builder().follow(FollowOption::On).build());
1090 /// while let Some(frame) = rx.recv().await {
1091 /// if frame.topic == "xs.threshold" {
1092 /// // caught up to live; everything after this is new
1093 /// continue;
1094 /// }
1095 /// println!("{} {}", frame.id, frame.topic);
1096 /// }
1097 /// # }
1098 /// ```
1099 #[tracing::instrument(skip(self))]
1100 pub fn read(&self, options: ReadOptions) -> tokio::sync::mpsc::Receiver<Frame> {
1101 let (tx, rx) = tokio::sync::mpsc::channel(100);
1102
1103 let should_follow = matches!(
1104 options.follow,
1105 FollowOption::On | FollowOption::WithHeartbeat(_)
1106 );
1107
1108 // Only take broadcast subscription if following. We initate the subscription here to
1109 // ensure we don't miss any messages between historical processing and starting the
1110 // broadcast subscription.
1111 let broadcast_rx = if should_follow {
1112 Some(self.broadcast_tx.subscribe())
1113 } else {
1114 None
1115 };
1116
1117 // Only create done channel if we're doing historical processing
1118 let done_rx = if !options.new {
1119 let (done_tx, done_rx) = tokio::sync::oneshot::channel();
1120 let tx_clone = tx.clone();
1121 let store = self.clone();
1122 let options = options.clone();
1123 let should_follow_clone = should_follow;
1124
1125 // Spawn OS thread to handle historical events
1126 std::thread::spawn(move || {
1127 let mut last_id = None;
1128 let mut count = 0;
1129
1130 // Handle --last N: get the N most recent frames
1131 let filter = TopicFilter::from_option(options.topic.as_deref());
1132
1133 if let Some(last_n) = options.last {
1134 let iter = store.iter_for_filter_rev(filter);
1135
1136 // Collect last N frames (in reverse order), skipping expired
1137 let mut frames: Vec<Frame> = Vec::with_capacity(last_n);
1138 for frame in iter {
1139 if is_expired(&frame) {
1140 continue;
1141 }
1142 frames.push(frame);
1143 if frames.len() >= last_n {
1144 break;
1145 }
1146 }
1147
1148 // Reverse to chronological order and send
1149 for frame in frames.into_iter().rev() {
1150 last_id = Some(frame.id);
1151 count += 1;
1152 if tx_clone.blocking_send(frame).is_err() {
1153 return;
1154 }
1155 }
1156 } else {
1157 // Normal forward iteration
1158 // Determine start bound: from (inclusive) takes precedence over after (exclusive)
1159 let start_bound = options
1160 .from
1161 .map(|id| (id, true))
1162 .or_else(|| options.after.map(|id| (id, false)));
1163
1164 let iter = store.iter_for_filter(filter, start_bound);
1165
1166 for frame in iter {
1167 if is_expired(&frame) {
1168 continue;
1169 }
1170
1171 last_id = Some(frame.id);
1172
1173 if let Some(limit) = options.limit {
1174 if count >= limit {
1175 return; // Exit early if limit reached
1176 }
1177 }
1178
1179 if tx_clone.blocking_send(frame).is_err() {
1180 return;
1181 }
1182 count += 1;
1183 }
1184 }
1185
1186 // Send threshold message if following
1187 if should_follow_clone {
1188 let threshold = Frame::builder("xs.threshold")
1189 .id(scru128::new())
1190 .ttl(TTL::Ephemeral)
1191 .build();
1192 if tx_clone.blocking_send(threshold).is_err() {
1193 return;
1194 }
1195 }
1196
1197 // Signal completion with the last seen ID and count
1198 let _ = done_tx.send((last_id, count));
1199 });
1200
1201 Some(done_rx)
1202 } else {
1203 None
1204 };
1205
1206 // Handle broadcast subscription and heartbeat
1207 if let Some(broadcast_rx) = broadcast_rx {
1208 let handle = self
1209 .rt
1210 .clone()
1211 .expect("read() with follow needs a runtime handle");
1212
1213 {
1214 let tx = tx.clone();
1215 let limit = options.limit;
1216
1217 handle.spawn(async move {
1218 // If we have a done_rx, wait for historical processing
1219 let (last_id, mut count) = match done_rx {
1220 Some(done_rx) => match done_rx.await {
1221 Ok((id, count)) => (id, count),
1222 Err(_) => return, // Historical processing failed/cancelled
1223 },
1224 None => (None, 0),
1225 };
1226
1227 let filter = TopicFilter::from_option(options.topic.as_deref());
1228
1229 let mut broadcast_rx = broadcast_rx;
1230 loop {
1231 tokio::select! {
1232 _ = tx.closed() => break,
1233 r = broadcast_rx.recv() => match r {
1234 Ok(frame) => {
1235 // Filter by topic (any-match against the parsed patterns)
1236 if !filter.matches(&frame.topic) {
1237 continue;
1238 }
1239
1240 // Skip if we've already seen this frame during historical scan
1241 if let Some(last_scanned_id) = last_id {
1242 if frame.id <= last_scanned_id {
1243 continue;
1244 }
1245 }
1246
1247 if tx.send(frame).await.is_err() {
1248 break;
1249 }
1250
1251 if let Some(limit) = limit {
1252 count += 1;
1253 if count >= limit {
1254 break;
1255 }
1256 }
1257 }
1258 // The reader fell more than FOLLOW_BUFFER frames
1259 // behind and the channel overwrote what it had not
1260 // taken. Carrying on would hand it the frames after
1261 // the gap as though nothing were missing, and the
1262 // read channel carries frames only, so there is no
1263 // way to say otherwise in band. End the read instead:
1264 // a closed stream is a signal the reader cannot
1265 // mistake for a complete one. It resumes with
1266 // `after` set to the last id it received.
1267 Err(broadcast::error::RecvError::Lagged(skipped)) => {
1268 tracing::warn!(
1269 skipped,
1270 "follow fell behind the live buffer, ending the read"
1271 );
1272 break;
1273 }
1274 Err(broadcast::error::RecvError::Closed) => break,
1275 }
1276 }
1277 }
1278 });
1279 }
1280
1281 // Handle heartbeat if requested
1282 if let FollowOption::WithHeartbeat(duration) = options.follow {
1283 let heartbeat_tx = tx;
1284 handle.spawn(async move {
1285 loop {
1286 tokio::select! {
1287 _ = heartbeat_tx.closed() => break,
1288 _ = tokio::time::sleep(duration) => {
1289 let frame = Frame::builder("xs.pulse")
1290 .id(scru128::new())
1291 .ttl(TTL::Ephemeral)
1292 .build();
1293 if heartbeat_tx.send(frame).await.is_err() {
1294 break;
1295 }
1296 }
1297 }
1298 }
1299 });
1300 }
1301 }
1302
1303 rx
1304 }
1305
1306 /// Replay matching historical frames as a blocking iterator.
1307 ///
1308 /// This honours the `topic`, `from`, `after`, `limit`, and `last` parts of
1309 /// [`ReadOptions`] but ignores [`follow`](ReadOptions::follow): it never
1310 /// streams live appends. Use [`read`](Store::read) when you need to follow.
1311 ///
1312 /// The iterator is lazy: it reads a frame per `next`, so a caller that
1313 /// stops early only pays for what it pulled. The exception is `last`,
1314 /// which reads in reverse and buffers its N frames to return them in
1315 /// chronological order.
1316 ///
1317 /// ```no_run
1318 /// use xs::{Store, ReadOptions};
1319 ///
1320 /// # fn run(store: Store) {
1321 /// let opts = ReadOptions::builder().topic("clip.*".to_string()).last(10).build();
1322 /// for frame in store.read_sync(opts) {
1323 /// println!("{} {}", frame.id, frame.topic);
1324 /// }
1325 /// # }
1326 /// ```
1327 pub fn read_sync(&self, options: ReadOptions) -> impl Iterator<Item = Frame> + '_ {
1328 // Hide expired frames the sweeper has not reached yet
1329 let filter_expired = |frame: Frame| (!is_expired(&frame)).then_some(frame);
1330
1331 let filter = TopicFilter::from_option(options.topic.as_deref());
1332
1333 if let Some(last_n) = options.last {
1334 // Handle --last N: get the N most recent frames. This branch reads
1335 // in reverse and re-orders, so it has to collect, but it is bounded
1336 // by last_n.
1337 let iter = self.iter_for_filter_rev(filter);
1338
1339 // Collect last N frames (in reverse order), skipping expired
1340 let mut frames: Vec<Frame> = Vec::with_capacity(last_n);
1341 for frame in iter {
1342 if let Some(frame) = filter_expired(frame) {
1343 frames.push(frame);
1344 if frames.len() >= last_n {
1345 break;
1346 }
1347 }
1348 }
1349
1350 // Reverse to chronological order
1351 frames.reverse();
1352 Box::new(frames.into_iter()) as Box<dyn Iterator<Item = Frame> + '_>
1353 } else {
1354 // Normal forward iteration, streamed: the caller only pays for the
1355 // frames it pulls.
1356 let start_bound = options
1357 .from
1358 .map(|id| (id, true))
1359 .or_else(|| options.after.map(|id| (id, false)));
1360
1361 Box::new(
1362 self.iter_for_filter(filter, start_bound)
1363 .filter_map(filter_expired)
1364 .take(options.limit.unwrap_or(usize::MAX)),
1365 )
1366 }
1367 }
1368
1369 /// Returns the current module state as of a given point in the stream.
1370 ///
1371 /// Scans all frames up to (and including) `as_of` and returns a mapping of
1372 /// module name to CAS hash for the latest frame on each `xs.module.<name>`
1373 /// topic.
1374 /// Resolve the set of registered Nushell modules as of a given frame ID.
1375 ///
1376 /// Scans `xs.module.<name>` frames up to and including `as_of` and returns a
1377 /// map from module name to the content hash of its latest definition. Used
1378 /// by the scripting runtime; rarely needed when embedding the store
1379 /// directly.
1380 pub fn nu_modules_at(
1381 &self,
1382 as_of: &Scru128Id,
1383 ) -> std::collections::HashMap<String, ssri::Integrity> {
1384 let mut modules = std::collections::HashMap::new();
1385 let options = ReadOptions::builder().follow(FollowOption::Off).build();
1386 for frame in self.read_sync(options) {
1387 if frame.id > *as_of {
1388 break;
1389 }
1390 if let Some(hash) = frame.hash {
1391 if let Some(name) = frame.topic.strip_prefix("xs.module.") {
1392 if !name.is_empty() {
1393 modules.insert(name.to_string(), hash);
1394 }
1395 }
1396 }
1397 }
1398 modules
1399 }
1400
1401 /// Fetch a single frame by ID, or `None` if no such frame exists.
1402 pub fn get(&self, id: &Scru128Id) -> Option<Frame> {
1403 self.stats.stream_reads.fetch_add(1, Ordering::Relaxed);
1404 self.stream
1405 .get(id.to_bytes())
1406 .unwrap()
1407 .map(|value| deserialize_frame((id.as_bytes(), value)))
1408 }
1409
1410 /// Delete a frame and its topic index entries. Removing a frame that does
1411 /// not exist is a no-op and returns `Ok(())`.
1412 ///
1413 /// This removes the stream entry only; any payload bytes in the
1414 /// content-addressed store are left in place.
1415 #[tracing::instrument(skip(self), fields(id = %id.to_string()))]
1416 pub fn remove(&self, id: &Scru128Id) -> Result<(), crate::error::Error> {
1417 self.remove_many([Removal::Id(*id)])
1418 }
1419
1420 /// Delete every frame in `removals`, with their index entries, in one
1421 /// batch with one commit. A [`Removal::Id`] whose frame is already gone
1422 /// is skipped, and nothing is committed when none remain.
1423 fn remove_many(
1424 &self,
1425 removals: impl IntoIterator<Item = Removal>,
1426 ) -> Result<(), crate::error::Error> {
1427 let mut batch = self.db.batch();
1428 for removal in removals {
1429 match removal {
1430 Removal::Id(id) => {
1431 if let Some(frame) = self.get(&id) {
1432 self.remove_frame_keys(
1433 &mut batch,
1434 &frame.id,
1435 &frame.topic,
1436 expires_at(&frame),
1437 );
1438 }
1439 }
1440 Removal::Indexed {
1441 id,
1442 topic,
1443 expires_at,
1444 } => self.remove_frame_keys(&mut batch, &id, &topic, expires_at),
1445 }
1446 }
1447 if batch.is_empty() {
1448 return Ok(());
1449 }
1450 batch.commit()?;
1451 self.stats.remove_commits.fetch_add(1, Ordering::Relaxed);
1452 // No inline fsync in any mode. The tombstones reach disk with the next
1453 // append's sync or the next tick. If power loss brings a frame back,
1454 // its index entries come back with it, so it is trimmed or swept
1455 // again.
1456 if matches!(self.fsync.mode, Fsync::Interval(_)) {
1457 self.fsync.dirty.store(true, Ordering::Release);
1458 }
1459 Ok(())
1460 }
1461
1462 /// Queue the stream entry and index keys of a frame for removal on
1463 /// `batch`. `expires_at` is the frame's expiry index slot, `Some` only for
1464 /// a `time:` frame. The topic key is built without validation: the frame
1465 /// exists.
1466 fn remove_frame_keys(
1467 &self,
1468 batch: &mut OwnedWriteBatch,
1469 id: &Scru128Id,
1470 topic: &str,
1471 expires_at: Option<u64>,
1472 ) {
1473 self.stats.removed_frames.fetch_add(1, Ordering::Relaxed);
1474 let mut topic_key = idx_topic_key_prefix(topic);
1475 topic_key.extend(id.as_bytes());
1476 batch.remove(&self.stream, id.as_bytes());
1477 batch.remove(&self.idx_topic, topic_key);
1478 for prefix_key in idx_topic_prefix_keys(topic, id) {
1479 batch.remove(&self.idx_topic, prefix_key);
1480 }
1481 if let Some(expires_at) = expires_at {
1482 batch.remove(&self.idx_expiry, idx_expiry_key(expires_at, id));
1483 }
1484 }
1485
1486 /// The oldest `time:` frames whose expiry is at or before `now_ms`, at
1487 /// most `limit` of them, straight from the expiry index. A full `limit`
1488 /// means there may be more.
1489 ///
1490 /// The scan resumes at [`sweep_start`](Store::sweep_start) rather than at
1491 /// the start of the index. Everything below that point is the tombstones
1492 /// of frames earlier sweeps removed, and walking them again on every sweep
1493 /// is what made draining a backlog cost O(n^2/batch).
1494 fn expired_at(&self, now_ms: u64, limit: usize) -> Vec<Removal> {
1495 let last = idx_expiry_key(now_ms, &Scru128Id::from_bytes([0xff; 16]));
1496 let from = *self.sweep_start.lock().unwrap();
1497 // A clock that stepped backwards can leave the resume point above the
1498 // cut-off. Nothing below it is unswept, so there is nothing to do
1499 // until the clock catches up.
1500 if from.is_some_and(|start| start.key > last) {
1501 return Vec::new();
1502 }
1503 let start = from.map_or(Bound::Unbounded, |start| start.bound());
1504
1505 let mut removals = Vec::new();
1506 let mut swept = None;
1507 for guard in self
1508 .idx_expiry
1509 .range((start, Bound::Included(last)))
1510 .take(limit)
1511 {
1512 // Stop on a read error rather than skipping the entry: the resume
1513 // point may never pass an entry this sweep did not remove.
1514 let Ok((key, value)) = guard.into_inner() else {
1515 break;
1516 };
1517 let Ok(key) = <[u8; 24]>::try_from(key.as_ref()) else {
1518 break;
1519 };
1520 let (expires_at, id) = idx_expiry_parse_key(&key);
1521 removals.push(Removal::Indexed {
1522 id,
1523 topic: String::from_utf8_lossy(&value).into_owned(),
1524 expires_at: Some(expires_at),
1525 });
1526 swept = Some(key);
1527 }
1528
1529 if let Some(key) = swept {
1530 let mut start = self.sweep_start.lock().unwrap();
1531 // Only advance from the point this scan started at. An index write
1532 // that moved it back while the scan ran wins: the next sweep
1533 // covers this ground again, and covering it twice is cheap next to
1534 // leaving a frame behind.
1535 if *start == from {
1536 *start = Some(SweepStart {
1537 key,
1538 inclusive: false,
1539 });
1540 }
1541 }
1542 removals
1543 }
1544
1545 /// Ids on `topic` past the newest `keep`, oldest first, at most `limit` of
1546 /// them, ignoring frames already in `pending` so a batch drops exactly
1547 /// what applying its tasks one by one would. A full `limit` means there
1548 /// may be more.
1549 ///
1550 /// Two bounded scans, both floored at the topic's
1551 /// [`trim_floor`](Store::trim_floor), below which the topic holds nothing
1552 /// but the tombstones of frames an earlier trim removed:
1553 ///
1554 /// 1. backwards from the newest entry for the `keep`-th newest live id,
1555 /// the high-water mark everything older than which is overflow;
1556 /// 2. forwards from the floor for the ids to remove.
1557 ///
1558 /// Taking the removals in forward order is what keeps trimming a backlog
1559 /// linear. A truncated pass leaves the floor on the newest id it removed,
1560 /// so the next pass starts above its own tombstones instead of walking
1561 /// them to reach what it left.
1562 ///
1563 /// Both scans read index keys only. The expiry an `idx_topic` value now
1564 /// carries is for the read path: a trim counts entries, so a `time:` frame
1565 /// the sweeper has not reached yet still holds one of the `keep` slots,
1566 /// exactly as it did when those values were empty.
1567 fn last_overflow(
1568 &self,
1569 topic: &str,
1570 keep: u32,
1571 pending: &HashSet<Scru128Id>,
1572 limit: usize,
1573 ) -> Vec<Overflow> {
1574 let floor = self.trim_floor.lock().unwrap().get(topic).copied();
1575 // The floor is a bound on the id, so it is a bound on the key: both
1576 // scans open at it and never reach the tombstones below it. See
1577 // [`idx_topic_range`].
1578 let (low, top) = idx_topic_range(
1579 idx_topic_key_prefix(topic),
1580 floor.map(|floor| (floor.id, floor.inclusive)),
1581 );
1582
1583 // The keep-th newest live id. Everything below it is overflow; fewer
1584 // than keep live entries means there is nothing to trim.
1585 let high = if keep == 0 {
1586 top
1587 } else {
1588 let mut seen = 0;
1589 let mut hwm = None;
1590 let mut oldest = None;
1591 for guard in self.idx_topic.range((low.clone(), top)).rev() {
1592 // A read error is not the end of the topic: give up on this
1593 // pass rather than record a floor the scan never reached.
1594 let Ok(key) = guard.key() else {
1595 return Vec::new();
1596 };
1597 let id = idx_topic_frame_id_from_key(&key);
1598 oldest = Some(id);
1599 if pending.contains(&id) {
1600 continue;
1601 }
1602 seen += 1;
1603 if seen == keep {
1604 hwm = Some(key.to_vec());
1605 break;
1606 }
1607 }
1608 match hwm {
1609 Some(key) => Bound::Excluded(key),
1610 None => {
1611 // The scan reached the end of the topic without finding
1612 // `keep` live frames. Nothing to trim, but everything
1613 // below the oldest entry it saw is tombstone, so the next
1614 // scan can start there instead of walking it again.
1615 if let Some(id) = oldest {
1616 self.set_trim_floor(
1617 topic,
1618 floor,
1619 TrimFloor {
1620 id,
1621 inclusive: true,
1622 },
1623 );
1624 }
1625 return Vec::new();
1626 }
1627 }
1628 };
1629
1630 let mut overflow = Vec::new();
1631 let mut trimmed = None;
1632 for guard in self.idx_topic.range((low, high)) {
1633 // Take the value too: it carries the frame's expiry, so the removal
1634 // needs no point read into `stream` to learn its keys.
1635 let Ok((key, value)) = guard.into_inner() else {
1636 break;
1637 };
1638 let id = idx_topic_frame_id_from_key(&key);
1639 if !pending.contains(&id) {
1640 overflow.push(Overflow {
1641 id,
1642 expires_at: idx_topic_expiry_of(&value),
1643 });
1644 }
1645 // A pending id counts: this drain removes it too, so the floor may
1646 // pass it.
1647 trimmed = Some(id);
1648 if overflow.len() == limit {
1649 break;
1650 }
1651 }
1652
1653 if let Some(id) = trimmed {
1654 self.set_trim_floor(
1655 topic,
1656 floor,
1657 TrimFloor {
1658 id,
1659 inclusive: false,
1660 },
1661 );
1662 }
1663 overflow
1664 }
1665
1666 /// Move a topic's trim floor to `to`, unless something moved it since the
1667 /// scan read `from`. An index write that dropped it while the scan ran
1668 /// wins: the next trim covers the topic from further back, and covering
1669 /// ground twice is cheap next to leaving a frame behind.
1670 fn set_trim_floor(&self, topic: &str, from: Option<TrimFloor>, to: TrimFloor) {
1671 let mut floors = self.trim_floor.lock().unwrap();
1672 if floors.get(topic).copied() == from {
1673 floors.insert(topic.to_string(), to);
1674 }
1675 }
1676
1677 /// Note that a `time:` frame's expiry entry has been committed at `key`.
1678 ///
1679 /// A frame restored with an id from the past, or appended in the instant a
1680 /// sweep passed its slot, lands below the resume point, where no later
1681 /// sweep would look. Move the resume point back onto it.
1682 ///
1683 /// Must be called after the commit: called before, a sweep could run,
1684 /// find nothing at the key yet, and leave the resume point above it again.
1685 fn note_indexed_expiry(&self, key: [u8; 24]) {
1686 let mut start = self.sweep_start.lock().unwrap();
1687 // Already at the start of the index: nothing can be below it.
1688 let Some(current) = *start else { return };
1689 let candidate = SweepStart {
1690 key,
1691 inclusive: true,
1692 };
1693 if candidate.rank() < current.rank() {
1694 *start = Some(candidate);
1695 }
1696 }
1697
1698 /// Note that a frame's topic index entry has been committed. An id at or
1699 /// below the topic's trim floor is in ground a trim scan no longer covers,
1700 /// so drop the floor and let the next trim scan the topic whole.
1701 ///
1702 /// Called after the commit, as
1703 /// [`note_indexed_expiry`](Store::note_indexed_expiry) is, and for every
1704 /// frame: `last:n` counts what is on the topic, whatever ttl put it there.
1705 fn note_indexed_topic(&self, topic: &str, id: &Scru128Id) {
1706 let mut floors = self.trim_floor.lock().unwrap();
1707 if floors.is_empty() {
1708 return;
1709 }
1710 if floors.get(topic).is_some_and(|floor| *id <= floor.id) {
1711 floors.remove(topic);
1712 }
1713 }
1714
1715 /// Forget where the sweep and the `last:n` trims had got to, so each next
1716 /// scan starts from the beginning of its index again. Called when a
1717 /// removal batch fails to commit: its frames are still there, but the
1718 /// resume points have already moved as though they were gone.
1719 fn reset_gc_resume(&self) {
1720 *self.sweep_start.lock().unwrap() = None;
1721 self.trim_floor.lock().unwrap().clear();
1722 }
1723
1724 // --- Content-addressed store (CAS) ---
1725 //
1726 // Frame payloads live here, keyed by an integrity hash. The typical flow is
1727 // `cas_insert` to store bytes, stash the returned hash on a `Frame`, then
1728 // `cas_read` to retrieve them later. Each method has a `_sync` twin for
1729 // blocking callers; the streaming `cas_reader`/`cas_writer` variants avoid
1730 // buffering the whole payload in memory.
1731
1732 /// Open a streaming reader for the payload identified by `hash`.
1733 pub async fn cas_reader(&self, hash: ssri::Integrity) -> cacache::Result<cacache::Reader> {
1734 cacache::Reader::open_hash(&self.path.join("cacache"), hash).await
1735 }
1736
1737 /// Blocking variant of [`cas_reader`](Store::cas_reader).
1738 pub fn cas_reader_sync(&self, hash: ssri::Integrity) -> cacache::Result<cacache::SyncReader> {
1739 cacache::SyncReader::open_hash(self.path.join("cacache"), hash)
1740 }
1741
1742 /// Open a streaming writer; finish it to obtain the payload's integrity hash.
1743 pub async fn cas_writer(&self) -> cacache::Result<cacache::Writer> {
1744 cacache::WriteOpts::new()
1745 .open_hash(&self.path.join("cacache"))
1746 .await
1747 }
1748
1749 /// Blocking variant of [`cas_writer`](Store::cas_writer).
1750 pub fn cas_writer_sync(&self) -> cacache::Result<cacache::SyncWriter> {
1751 cacache::WriteOpts::new().open_hash_sync(self.path.join("cacache"))
1752 }
1753
1754 /// Store `content` and return its integrity hash, ready to attach to a
1755 /// [`Frame::hash`].
1756 pub async fn cas_insert(&self, content: impl AsRef<[u8]>) -> cacache::Result<ssri::Integrity> {
1757 cacache::write_hash(&self.path.join("cacache"), content).await
1758 }
1759
1760 /// Blocking variant of [`cas_insert`](Store::cas_insert).
1761 pub fn cas_insert_sync(&self, content: impl AsRef<[u8]>) -> cacache::Result<ssri::Integrity> {
1762 cacache::write_hash_sync(self.path.join("cacache"), content)
1763 }
1764
1765 /// Convenience wrapper over [`cas_insert`](Store::cas_insert) for a byte slice.
1766 pub async fn cas_insert_bytes(&self, bytes: &[u8]) -> cacache::Result<ssri::Integrity> {
1767 self.cas_insert(bytes).await
1768 }
1769
1770 /// Blocking variant of [`cas_insert_bytes`](Store::cas_insert_bytes).
1771 pub fn cas_insert_bytes_sync(&self, bytes: &[u8]) -> cacache::Result<ssri::Integrity> {
1772 self.cas_insert_sync(bytes)
1773 }
1774
1775 /// Read back the full payload for `hash` into a `Vec<u8>`.
1776 pub async fn cas_read(&self, hash: &ssri::Integrity) -> cacache::Result<Vec<u8>> {
1777 cacache::read_hash(&self.path.join("cacache"), hash).await
1778 }
1779
1780 /// Blocking variant of [`cas_read`](Store::cas_read).
1781 pub fn cas_read_sync(&self, hash: &ssri::Integrity) -> cacache::Result<Vec<u8>> {
1782 cacache::read_hash_sync(self.path.join("cacache"), hash)
1783 }
1784
1785 /// Persist a frame exactly as given, including its existing
1786 /// [`id`](Frame::id), without broadcasting it to live readers or scheduling
1787 /// TTL garbage collection.
1788 ///
1789 /// Most callers want [`append`](Store::append) instead, which assigns a
1790 /// fresh ID, handles ephemeral and `Last` retention, and notifies
1791 /// subscribers. Use `insert_frame` only when you are reconstructing a stream
1792 /// with predetermined IDs (for example when restoring a backup).
1793 #[tracing::instrument(skip(self))]
1794 pub fn insert_frame(&self, frame: &Frame) -> Result<(), crate::error::Error> {
1795 let encoded: Vec<u8> = serde_json::to_vec(&frame).unwrap();
1796
1797 // Get the index topic key (also validates topic)
1798 let topic_key = idx_topic_key_from_frame(frame)?;
1799
1800 // Get prefix index keys for hierarchical queries
1801 let prefix_keys = idx_topic_prefix_keys(&frame.topic, &frame.id);
1802
1803 // Every idx_topic entry for this frame carries the same expiry, so a
1804 // topic scan can drop an expired id without reading the frame.
1805 let idx_value = idx_topic_expiry_value(frame);
1806
1807 // The id may already be here under a different topic or ttl. This is
1808 // an upsert, so the stream row is replaced, but the index keys carry
1809 // the topic and the expiry, so the old ones would survive their frame
1810 // and answer for a topic it no longer has.
1811 let superseded = self.get(&frame.id);
1812
1813 let mut batch = self.db.batch();
1814 batch.insert(&self.stream, frame.id.as_bytes(), encoded);
1815 batch.insert(&self.idx_topic, topic_key.clone(), idx_value);
1816 for prefix_key in &prefix_keys {
1817 batch.insert(&self.idx_topic, prefix_key, idx_value);
1818 }
1819 // A time: frame is also indexed by its expiry, for the sweeper
1820 let expiry_key = expires_at(frame).map(|at| idx_expiry_key(at, &frame.id));
1821 if let Some(key) = expiry_key {
1822 batch.insert(&self.idx_expiry, key, frame.topic.as_bytes());
1823 }
1824
1825 if let Some(old) = superseded.as_ref().filter(|old| old.topic != frame.topic) {
1826 let mut old_key = idx_topic_key_prefix(&old.topic);
1827 old_key.extend(frame.id.as_bytes());
1828 // "a.b" and "a.c" share the prefix key "a.", so drop only the keys
1829 // the write above is not putting straight back: removing and
1830 // inserting one key in one batch has no defined winner.
1831 for key in std::iter::once(old_key).chain(idx_topic_prefix_keys(&old.topic, &frame.id))
1832 {
1833 if key != topic_key && !prefix_keys.contains(&key) {
1834 batch.remove(&self.idx_topic, key);
1835 }
1836 }
1837 }
1838 // A changed ttl moves the expiry entry, because the expiry is half of
1839 // its key. An unchanged one is the same key, already rewritten above
1840 // with whatever topic the frame now carries.
1841 if let Some(stale) = superseded
1842 .as_ref()
1843 .and_then(expires_at)
1844 .map(|at| idx_expiry_key(at, &frame.id))
1845 .filter(|stale| Some(*stale) != expiry_key)
1846 {
1847 batch.remove(&self.idx_expiry, stale);
1848 }
1849
1850 batch.commit()?;
1851 // Both gc scans resume where they last stopped, and an id from the
1852 // past can land behind them. Tell them, once the entries are there to
1853 // be found.
1854 if let Some(key) = expiry_key {
1855 self.note_indexed_expiry(key);
1856 }
1857 self.note_indexed_topic(&frame.topic, &frame.id);
1858 self.after_commit()
1859 }
1860
1861 /// Append a frame to the stream and return it with its freshly assigned
1862 /// [`id`](Frame::id).
1863 ///
1864 /// This is the primary write path. It:
1865 ///
1866 /// - assigns a new time-sortable ID (overwriting any ID on the input);
1867 /// - validates the topic (see [`validate_topic`]);
1868 /// - persists the frame, unless its [`TTL`] is [`TTL::Ephemeral`], in which
1869 /// case it is only broadcast to live readers;
1870 /// - schedules garbage collection for [`TTL::Last`] retention;
1871 /// - broadcasts the frame to everyone currently in a following
1872 /// [`read`](Store::read).
1873 ///
1874 /// Appends are serialized internally, so frames are assigned IDs and
1875 /// delivered to subscribers in a consistent order.
1876 ///
1877 /// # Errors
1878 ///
1879 /// Returns an error if the topic is invalid or the underlying write fails.
1880 ///
1881 /// ```no_run
1882 /// use xs::{Store, Frame, TTL};
1883 ///
1884 /// # async fn run(store: Store) -> Result<(), Box<dyn std::error::Error + Send + Sync>> {
1885 /// let hash = store.cas_insert("hello clipboard").await?;
1886 /// let frame = store.append(
1887 /// Frame::builder("clip.add").hash(hash).ttl(TTL::Last(100)).build(),
1888 /// )?;
1889 /// println!("appended {}", frame.id);
1890 /// # Ok(())
1891 /// # }
1892 /// ```
1893 pub fn append(&self, mut frame: Frame) -> Result<Frame, crate::error::Error> {
1894 // Serialize all appends to ensure ID generation, write, and broadcast
1895 // happen atomically. This guarantees subscribers receive frames in
1896 // scru128 ID order.
1897 let _guard = self.append_lock.lock().unwrap();
1898
1899 frame.id = scru128::new();
1900
1901 // Check for null byte in topic (in case we're not storing the frame)
1902 idx_topic_key_from_frame(&frame)?;
1903
1904 // only store the frame if it's not ephemeral
1905 if frame.ttl != Some(TTL::Ephemeral) {
1906 self.insert_frame(&frame)?;
1907
1908 // If this is a Last TTL, schedule a gc task
1909 if let Some(TTL::Last(n)) = frame.ttl {
1910 let _ = self.gc_tx.send(GCTask::CheckLastTTL {
1911 topic: frame.topic.clone(),
1912 keep: n,
1913 });
1914 }
1915 }
1916
1917 self.stats.appends.fetch_add(1, Ordering::Relaxed);
1918 let _ = self.broadcast_tx.send(frame.clone());
1919 Ok(frame)
1920 }
1921
1922 /// Iterate frames starting from a bound.
1923 /// `start` is `(id, inclusive)` where inclusive=true means >= and inclusive=false means >.
1924 fn iter_frames(
1925 &self,
1926 start: Option<(Scru128Id, bool)>,
1927 ) -> Box<dyn Iterator<Item = Frame> + '_> {
1928 let range = match start {
1929 Some((id, true)) => (Bound::Included(id.as_bytes().to_vec()), Bound::Unbounded),
1930 Some((id, false)) => (Bound::Excluded(id.as_bytes().to_vec()), Bound::Unbounded),
1931 None => (Bound::Unbounded, Bound::Unbounded),
1932 };
1933
1934 let scanned = self.stats.clone();
1935 Box::new(self.stream.range(range).filter_map(move |guard| {
1936 scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
1937 let (key, value) = guard.into_inner().ok()?;
1938 Some(deserialize_frame((key, value)))
1939 }))
1940 }
1941
1942 /// Iterate frames in reverse order (most recent first).
1943 fn iter_frames_rev(&self) -> Box<dyn Iterator<Item = Frame> + '_> {
1944 let scanned = self.stats.clone();
1945 Box::new(self.stream.iter().rev().filter_map(move |guard| {
1946 scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
1947 let (key, value) = guard.into_inner().ok()?;
1948 Some(deserialize_frame((key, value)))
1949 }))
1950 }
1951
1952 /// Iterate frames by topic in reverse order (most recent first).
1953 fn iter_frames_by_topic_rev(&self, topic: &str) -> Box<dyn Iterator<Item = Frame> + '_> {
1954 let prefix = idx_topic_key_prefix(topic);
1955 let now = now_ms();
1956 let scanned = self.stats.clone();
1957 Box::new(
1958 self.idx_topic
1959 .prefix(prefix)
1960 .rev()
1961 .filter_map(move |guard| {
1962 scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
1963 self.get(&idx_topic_hit_id(guard, now)?)
1964 }),
1965 )
1966 }
1967
1968 /// Iterate frames by topic prefix in reverse order (most recent first).
1969 fn iter_frames_by_topic_prefix_rev(
1970 &self,
1971 prefix: &str,
1972 ) -> Box<dyn Iterator<Item = Frame> + '_> {
1973 let mut index_prefix = Vec::with_capacity(prefix.len() + 1);
1974 index_prefix.extend(prefix.as_bytes());
1975 index_prefix.push(NULL_DELIMITER);
1976
1977 let now = now_ms();
1978 let scanned = self.stats.clone();
1979
1980 Box::new(
1981 self.idx_topic
1982 .prefix(index_prefix)
1983 .rev()
1984 .filter_map(move |guard| {
1985 scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
1986 self.get(&idx_topic_hit_id(guard, now)?)
1987 }),
1988 )
1989 }
1990
1991 /// Iterate frames on an exact topic, ascending by frame id, from `start`.
1992 fn iter_frames_by_topic(
1993 &self,
1994 topic: &str,
1995 start: Option<(Scru128Id, bool)>,
1996 ) -> Box<dyn Iterator<Item = Frame> + '_> {
1997 let range = idx_topic_range(idx_topic_key_prefix(topic), start);
1998 let now = now_ms();
1999 let scanned = self.stats.clone();
2000 Box::new(self.idx_topic.range(range).filter_map(move |guard| {
2001 scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
2002 self.get(&idx_topic_hit_id(guard, now)?)
2003 }))
2004 }
2005
2006 /// Iterate frames matching a topic prefix (for wildcard queries like "user.*").
2007 /// The prefix should include the trailing dot (e.g., "user." for "user.*").
2008 fn iter_frames_by_topic_prefix(
2009 &self,
2010 prefix: &str,
2011 start: Option<(Scru128Id, bool)>,
2012 ) -> Box<dyn Iterator<Item = Frame> + '_> {
2013 // Build index prefix: "user.\0" for scanning all "user.*" entries
2014 let mut index_prefix = Vec::with_capacity(prefix.len() + 1);
2015 index_prefix.extend(prefix.as_bytes());
2016 index_prefix.push(NULL_DELIMITER);
2017
2018 let range = idx_topic_range(index_prefix, start);
2019 let now = now_ms();
2020 let scanned = self.stats.clone();
2021
2022 Box::new(self.idx_topic.range(range).filter_map(move |guard| {
2023 scanned.frames_scanned.fetch_add(1, Ordering::Relaxed);
2024 self.get(&idx_topic_hit_id(guard, now)?)
2025 }))
2026 }
2027
2028 /// Forward iterator for a single pattern, using the topic index.
2029 fn iter_for_pattern(
2030 &self,
2031 pattern: Pattern,
2032 start: Option<(Scru128Id, bool)>,
2033 ) -> Box<dyn Iterator<Item = Frame> + '_> {
2034 match pattern {
2035 Pattern::Exact(topic) => self.iter_frames_by_topic(&topic, start),
2036 Pattern::Prefix(prefix) => self.iter_frames_by_topic_prefix(&prefix, start),
2037 }
2038 }
2039
2040 /// Reverse (most recent first) iterator for a single pattern.
2041 fn iter_for_pattern_rev(&self, pattern: Pattern) -> Box<dyn Iterator<Item = Frame> + '_> {
2042 match pattern {
2043 Pattern::Exact(topic) => self.iter_frames_by_topic_rev(&topic),
2044 Pattern::Prefix(prefix) => self.iter_frames_by_topic_prefix_rev(&prefix),
2045 }
2046 }
2047
2048 /// Forward iterator for a parsed topic filter, ascending by frame id.
2049 /// A single pattern uses the indexed path directly; multiple patterns
2050 /// are k-way merged with dedupe for overlapping patterns.
2051 fn iter_for_filter(
2052 &self,
2053 filter: TopicFilter,
2054 start: Option<(Scru128Id, bool)>,
2055 ) -> Box<dyn Iterator<Item = Frame> + '_> {
2056 match filter {
2057 TopicFilter::All => self.iter_frames(start),
2058 TopicFilter::Patterns(mut patterns) if patterns.len() == 1 => {
2059 self.iter_for_pattern(patterns.remove(0), start)
2060 }
2061 TopicFilter::Patterns(patterns) => {
2062 let iters = patterns
2063 .into_iter()
2064 .map(|p| self.iter_for_pattern(p, start))
2065 .collect();
2066 Box::new(MergeById::new(iters, false))
2067 }
2068 }
2069 }
2070
2071 /// Reverse variant of [`iter_for_filter`](Store::iter_for_filter),
2072 /// descending by frame id (most recent first).
2073 fn iter_for_filter_rev(&self, filter: TopicFilter) -> Box<dyn Iterator<Item = Frame> + '_> {
2074 match filter {
2075 TopicFilter::All => self.iter_frames_rev(),
2076 TopicFilter::Patterns(mut patterns) if patterns.len() == 1 => {
2077 self.iter_for_pattern_rev(patterns.remove(0))
2078 }
2079 TopicFilter::Patterns(patterns) => {
2080 let iters = patterns
2081 .into_iter()
2082 .map(|p| self.iter_for_pattern_rev(p))
2083 .collect();
2084 Box::new(MergeById::new(iters, true))
2085 }
2086 }
2087 }
2088}
2089
2090fn spawn_gc_worker(
2091 mut gc_rx: UnboundedReceiver<GCTask>,
2092 mut store: Store,
2093) -> std::thread::JoinHandle<()> {
2094 // The worker's own clone must not hold a live `gc_tx`, or the channel
2095 // never closes and the worker, the database, and the fsync worker outlive
2096 // every caller's handle. Give it a sender whose receiver is already gone.
2097 let (closed_tx, _) = mpsc::unbounded_channel();
2098 store.gc_tx = closed_tx;
2099
2100 // One drain per wake: take the task that woke us and whatever else is
2101 // queued, up to the cap, and apply every removal in one batch with one
2102 // commit. A Drain is answered after that commit, so every task queued
2103 // before it has been applied by the time its reply lands.
2104 const MAX_TASKS_PER_DRAIN: usize = 1024;
2105 // A sweep removes at most this many frames. When it fills the cap the
2106 // next drain starts with another sweep, without waiting for the tick.
2107 const MAX_SWEEP_PER_DRAIN: usize = 4096;
2108 // A last:n trim removes at most this many frames per topic per drain, and
2109 // is carried over the same way a full sweep is. Without a cap the first
2110 // trim of a topic with a backlog collects every id past `keep` at once.
2111 const MAX_TRIM_PER_DRAIN: usize = 4096;
2112
2113 std::thread::spawn(move || {
2114 // Tasks a full batch left unfinished, run first in the next drain.
2115 let mut carried: Vec<GCTask> = Vec::new();
2116 loop {
2117 if carried.is_empty() {
2118 match gc_rx.blocking_recv() {
2119 Some(task) => carried.push(task),
2120 None => break,
2121 }
2122 }
2123
2124 let drain_started = std::time::Instant::now();
2125
2126 // Ids in this drain, so a last:n scan and a sweep never count or
2127 // queue a frame twice.
2128 let mut pending = HashSet::new();
2129 let mut removals = Vec::new();
2130 let mut drains = Vec::new();
2131 let mut sweep_again = false;
2132 // Topics whose trim filled its cap, one entry each however many
2133 // tasks for them this drain took.
2134 let mut trim_again: HashMap<String, u32> = HashMap::new();
2135 // Topics this drain must trim, collapsed from however many tasks
2136 // asked. Scanned after the take loop so every Sweep has already
2137 // run: an expired frame is hidden from reads, so it must not hold
2138 // a keep slot.
2139 let mut trims: HashMap<String, u32> = HashMap::new();
2140 let mut taken = 0;
2141 while taken < MAX_TASKS_PER_DRAIN {
2142 let Some(task) = carried.pop().or_else(|| gc_rx.try_recv().ok()) else {
2143 break;
2144 };
2145 match task {
2146 GCTask::CheckLastTTL { topic, keep } => {
2147 // One scan per topic per drain, at the smallest keep
2148 // asked for. A second scan for the same topic filters
2149 // out everything the first collected, skips keep, and
2150 // walks the rest to return nothing.
2151 trims
2152 .entry(topic)
2153 .and_modify(|k| *k = (*k).min(keep))
2154 .or_insert(keep);
2155 }
2156 GCTask::Sweep => {
2157 let expired = store.expired_at(now_ms(), MAX_SWEEP_PER_DRAIN);
2158 sweep_again |= expired.len() == MAX_SWEEP_PER_DRAIN;
2159 for removal in expired {
2160 if pending.insert(removal.id()) {
2161 removals.push(removal);
2162 }
2163 }
2164 }
2165 GCTask::Drain(tx) => drains.push(tx),
2166 }
2167 taken += 1;
2168 }
2169
2170 // Now that every Sweep in this drain has run, so `pending` holds
2171 // the expired frames it is removing, trim each topic once.
2172 for (topic, keep) in trims {
2173 let overflow = store.last_overflow(&topic, keep, &pending, MAX_TRIM_PER_DRAIN);
2174 let again = overflow.len() == MAX_TRIM_PER_DRAIN;
2175 for frame in overflow {
2176 if pending.insert(frame.id) {
2177 removals.push(Removal::Indexed {
2178 id: frame.id,
2179 topic: topic.clone(),
2180 expires_at: frame.expires_at,
2181 });
2182 }
2183 }
2184 if again {
2185 trim_again.insert(topic, keep);
2186 }
2187 }
2188
2189 if let Err(e) = store.remove_many(removals) {
2190 tracing::error!("gc remove failed: {e}");
2191 // The batch did not land, so every frame this drain counted as
2192 // gone is still there, below resume points that have already
2193 // moved past it. Start both scans over.
2194 store.reset_gc_resume();
2195 }
2196 store.stats.gc_drains.fetch_add(1, Ordering::Relaxed);
2197 store
2198 .stats
2199 .gc_nanos
2200 .fetch_add(drain_started.elapsed().as_nanos() as u64, Ordering::Relaxed);
2201 for tx in drains {
2202 let _ = tx.send(());
2203 }
2204 carried.extend(
2205 trim_again
2206 .into_iter()
2207 .map(|(topic, keep)| GCTask::CheckLastTTL { topic, keep }),
2208 );
2209 if sweep_again {
2210 carried.push(GCTask::Sweep);
2211 }
2212 }
2213 })
2214}
2215
2216/// Fsync the journal every `interval` when something was written since the
2217/// last tick. No final persist is needed on stop: fjall syncs the journal
2218/// when the database closes.
2219fn spawn_fsync_tick(db: Database, state: Arc<FsyncState>, interval: Duration) -> Tick {
2220 Tick::spawn(interval, move || {
2221 if state.dirty.swap(false, Ordering::AcqRel) {
2222 if let Err(e) = db.persist(PersistMode::SyncAll) {
2223 tracing::error!("fsync failed: {e}");
2224 }
2225 }
2226 })
2227}
2228
2229/// Queue a [`GCTask::Sweep`] every `interval`. The gc worker does the scan
2230/// and the removals, so a slow sweep never blocks the tick.
2231fn spawn_sweep_tick(gc_tx: UnboundedSender<GCTask>, interval: Duration) -> Tick {
2232 Tick::spawn(interval, move || {
2233 let _ = gc_tx.send(GCTask::Sweep);
2234 })
2235}
2236
2237fn now_ms() -> u64 {
2238 std::time::SystemTime::now()
2239 .duration_since(std::time::UNIX_EPOCH)
2240 .unwrap()
2241 .as_millis() as u64
2242}
2243
2244/// When a `time:` frame expires, in ms since the epoch: its id's timestamp
2245/// plus its ttl. `None` for any other ttl.
2246fn expires_at(frame: &Frame) -> Option<u64> {
2247 match frame.ttl.as_ref() {
2248 Some(TTL::Time(ttl)) => Some(frame.id.timestamp().saturating_add(ttl.as_millis() as u64)),
2249 _ => None,
2250 }
2251}
2252
2253/// Has this frame's `time:` ttl passed? Matches the sweeper's cut-off, so a
2254/// frame is hidden from reads from the moment it becomes sweepable.
2255fn is_expired(frame: &Frame) -> bool {
2256 matches!(expires_at(frame), Some(at) if now_ms() >= at)
2257}
2258
2259/// Expiry index key: expiry in ms as big-endian u64, then the frame id. Sorts
2260/// by expiry, so a range scan up to now yields exactly the expired frames.
2261fn idx_expiry_key(expires_at: u64, id: &Scru128Id) -> [u8; 24] {
2262 let mut key = [0u8; 24];
2263 key[..8].copy_from_slice(&expires_at.to_be_bytes());
2264 key[8..].copy_from_slice(id.as_bytes());
2265 key
2266}
2267
2268fn idx_expiry_parse_key(key: &[u8]) -> (u64, Scru128Id) {
2269 let expires_at = u64::from_be_bytes(key[..8].try_into().unwrap());
2270 let id = Scru128Id::from_bytes(key[8..24].try_into().unwrap());
2271 (expires_at, id)
2272}
2273
2274/// Live frames held for a following read that has not taken them yet.
2275///
2276/// A reader that falls further behind than this has its read ended rather
2277/// than silently skipped: see the `Lagged` arm in [`read`](Store::read).
2278/// Raising it buys a slow reader more room before that happens, at a frame
2279/// of memory per slot per follower.
2280const FOLLOW_BUFFER: usize = 4096;
2281
2282const NULL_DELIMITER: u8 = 0;
2283const MAX_TOPIC_LENGTH: usize = 255;
2284
2285/// Validate a frame topic (per ADR 0001).
2286///
2287/// A topic must be non-empty and at most 255 bytes, start with an ASCII letter
2288/// or `_`, and contain only `a-z A-Z 0-9 _ - .`. It may not end with `.` or
2289/// contain consecutive dots. [`Store::append`] runs this automatically; call it
2290/// directly to validate user input before building a [`Frame`].
2291///
2292/// ```
2293/// use xs::store::validate_topic;
2294///
2295/// assert!(validate_topic("clip.add").is_ok());
2296/// assert!(validate_topic("clip.").is_err());
2297/// ```
2298pub fn validate_topic(topic: &str) -> Result<(), crate::error::Error> {
2299 if topic.is_empty() {
2300 return Err("Topic cannot be empty".to_string().into());
2301 }
2302 if topic.len() > MAX_TOPIC_LENGTH {
2303 return Err(format!("Topic exceeds max length of {MAX_TOPIC_LENGTH} bytes").into());
2304 }
2305 if topic.ends_with('.') {
2306 return Err("Topic cannot end with '.'".to_string().into());
2307 }
2308 if topic.contains("..") {
2309 return Err("Topic cannot contain consecutive dots".to_string().into());
2310 }
2311
2312 let bytes = topic.as_bytes();
2313 let first = bytes[0];
2314 if !first.is_ascii_alphabetic() && first != b'_' {
2315 return Err("Topic must start with a-z, A-Z, or _".to_string().into());
2316 }
2317
2318 for &b in bytes {
2319 if !b.is_ascii_alphanumeric() && b != b'_' && b != b'-' && b != b'.' {
2320 return Err(format!(
2321 "Topic contains invalid character: '{}'. Allowed: a-z A-Z 0-9 _ - .",
2322 b as char
2323 )
2324 .into());
2325 }
2326 }
2327
2328 Ok(())
2329}
2330
2331/// Validates a topic query (for --topic flag).
2332/// Accepts a comma-separated list of patterns; each element is an exact
2333/// topic, a `prefix.*` wildcard, or `*` (match all).
2334pub fn validate_topic_query(spec: &str) -> Result<(), crate::error::Error> {
2335 let mut seen = false;
2336 for part in spec.split(',') {
2337 let part = part.trim();
2338 if part.is_empty() {
2339 continue;
2340 }
2341 seen = true;
2342 validate_topic_pattern(part)?;
2343 }
2344 if !seen {
2345 return Err("Topic query cannot be empty".to_string().into());
2346 }
2347 Ok(())
2348}
2349
2350/// Validate a single topic pattern: "*", "prefix.*", or an exact topic.
2351fn validate_topic_pattern(topic: &str) -> Result<(), crate::error::Error> {
2352 if topic == "*" {
2353 return Ok(());
2354 }
2355 if let Some(prefix) = topic.strip_suffix(".*") {
2356 // Validate the prefix part (e.g., "user" in "user.*")
2357 // Prefix can be empty edge case: ".*" is not valid
2358 if prefix.is_empty() {
2359 return Err("Wildcard '.*' requires a prefix".to_string().into());
2360 }
2361 validate_topic(prefix)
2362 } else {
2363 validate_topic(topic)
2364 }
2365}
2366
2367/// Generate prefix index keys for hierarchical topic queries.
2368/// For topic "user.id1.messages", returns keys for prefixes "user." and "user.id1."
2369fn idx_topic_prefix_keys(topic: &str, frame_id: &scru128::Scru128Id) -> Vec<Vec<u8>> {
2370 let mut keys = Vec::new();
2371 let mut pos = 0;
2372 while let Some(dot_pos) = topic[pos..].find('.') {
2373 let prefix = &topic[..pos + dot_pos + 1]; // include the dot
2374 let mut key = Vec::with_capacity(prefix.len() + 1 + 16);
2375 key.extend(prefix.as_bytes());
2376 key.push(NULL_DELIMITER);
2377 key.extend(frame_id.as_bytes());
2378 keys.push(key);
2379 pos += dot_pos + 1;
2380 }
2381 keys
2382}
2383
2384/// An `idx_topic` value meaning "this frame has no `time:` ttl". Distinct from
2385/// the empty value an older store wrote, which means "unknown".
2386const IDX_TOPIC_NEVER: u64 = u64::MAX;
2387
2388/// One frame a `last:n` trim is going to remove, with everything
2389/// [`Store::remove_many`] needs to delete its keys. The topic is the one being
2390/// trimmed and the expiry came off the index entry, so no point read is needed.
2391#[derive(Debug, Clone, Copy)]
2392struct Overflow {
2393 id: Scru128Id,
2394 /// `Some` when the frame has a `time:` ttl and so an expiry index entry.
2395 /// `None` when it has none, or when the entry predates the index carrying
2396 /// one -- see [`idx_topic_expiry_of`].
2397 expires_at: Option<u64>,
2398}
2399
2400/// The expiry an `idx_topic` value carries, if it carries one.
2401///
2402/// `None` covers two cases the caller must treat alike: a frame with no `time:`
2403/// ttl, which has no expiry index entry to delete, and an entry written before
2404/// the index carried an expiry, whose frame may have one. Removing a key that
2405/// is not there is a no-op, so both are safe to treat as "nothing to delete" --
2406/// but the second leaves a stale expiry entry, which the sweeper drops on its
2407/// next pass when the point read finds no frame.
2408#[inline]
2409fn idx_topic_expiry_of(value: &[u8]) -> Option<u64> {
2410 match <[u8; 8]>::try_from(value) {
2411 Ok(bytes) => match u64::from_be_bytes(bytes) {
2412 IDX_TOPIC_NEVER => None,
2413 at => Some(at),
2414 },
2415 Err(_) => None,
2416 }
2417}
2418
2419/// The `idx_topic` value for a frame: its expiry in ms as a big-endian u64, or
2420/// [`IDX_TOPIC_NEVER`]. Every entry for the frame -- the exact topic key and
2421/// each prefix key -- gets the same eight bytes, so a topic scan can drop an
2422/// expired id without a point read into `stream`.
2423fn idx_topic_expiry_value(frame: &Frame) -> [u8; 8] {
2424 expires_at(frame).unwrap_or(IDX_TOPIC_NEVER).to_be_bytes()
2425}
2426
2427/// Has the frame behind this `idx_topic` value expired as of `now`? A value
2428/// that is not eight bytes -- an entry written before the index carried an
2429/// expiry -- reads as "unknown" and answers `false`, so the caller falls back
2430/// to reading the frame and letting [`is_expired`] decide. Both shapes can sit
2431/// in one index.
2432///
2433/// The arithmetic matches [`expires_at`] exactly, so this never hides a frame
2434/// [`is_expired`] would keep.
2435#[inline]
2436fn idx_topic_is_expired(value: &[u8], now: u64) -> bool {
2437 match <[u8; 8]>::try_from(value) {
2438 Ok(bytes) => {
2439 let expires_at = u64::from_be_bytes(bytes);
2440 expires_at != IDX_TOPIC_NEVER && now >= expires_at
2441 }
2442 Err(_) => false,
2443 }
2444}
2445
2446/// The frame id an `idx_topic` hit points at, or `None` to skip the hit
2447/// entirely.
2448///
2449/// The entry's value carries the frame's expiry, so an already expired id is
2450/// dropped here without the point read into `stream` that seeing its ttl would
2451/// otherwise take. `now` is sampled once when the iterator is built, which only
2452/// ever skips fewer frames than a fresh sample would: [`is_expired`] still runs
2453/// on everything that gets through, so the two never disagree about what is
2454/// visible.
2455#[inline]
2456fn idx_topic_hit_id(guard: fjall::Guard, now: u64) -> Option<Scru128Id> {
2457 let (key, value) = guard.into_inner().ok()?;
2458 if idx_topic_is_expired(&value, now) {
2459 return None;
2460 }
2461 Some(idx_topic_frame_id_from_key(&key))
2462}
2463
2464/// The `idx_topic` key range covering one index prefix, opening at `start`
2465/// when there is one.
2466///
2467/// Every key under a prefix is that prefix followed by the frame's 16 byte id,
2468/// and ids sort ascending, so a bound on the id is a bound on the key. Seeking
2469/// to it beats walking the topic from its first entry and discarding
2470/// everything below: on a topic holding 500k frames, reading `after` a recent
2471/// id touches a handful of index entries instead of all 500k.
2472///
2473/// The upper bound is the prefix plus all ones, the largest key the prefix can
2474/// hold. A topic never contains the NUL delimiter, so no other topic's keys
2475/// fall inside the range.
2476fn idx_topic_range(
2477 prefix: Vec<u8>,
2478 start: Option<(Scru128Id, bool)>,
2479) -> (Bound<Vec<u8>>, Bound<Vec<u8>>) {
2480 fn key_at(prefix: &[u8], id: &[u8; 16]) -> Vec<u8> {
2481 let mut key = Vec::with_capacity(prefix.len() + 16);
2482 key.extend_from_slice(prefix);
2483 key.extend_from_slice(id);
2484 key
2485 }
2486
2487 let hi = Bound::Included(key_at(&prefix, &[0xff; 16]));
2488 let lo = match start {
2489 Some((id, true)) => Bound::Included(key_at(&prefix, id.as_bytes())),
2490 Some((id, false)) => Bound::Excluded(key_at(&prefix, id.as_bytes())),
2491 // Shorter than every key it covers, so it sorts before all of them.
2492 None => Bound::Included(prefix),
2493 };
2494 (lo, hi)
2495}
2496
2497fn idx_topic_key_prefix(topic: &str) -> Vec<u8> {
2498 let mut v = Vec::with_capacity(topic.len() + 1); // topic bytes + delimiter
2499 v.extend(topic.as_bytes()); // topic string as UTF-8 bytes
2500 v.push(NULL_DELIMITER); // Delimiter for variable-sized keys
2501 v
2502}
2503
2504pub(crate) fn idx_topic_key_from_frame(frame: &Frame) -> Result<Vec<u8>, crate::error::Error> {
2505 validate_topic(&frame.topic)?;
2506 let mut v = idx_topic_key_prefix(&frame.topic);
2507 v.extend(frame.id.as_bytes());
2508 Ok(v)
2509}
2510
2511fn idx_topic_frame_id_from_key(key: &[u8]) -> Scru128Id {
2512 let frame_id_bytes = &key[key.len() - 16..];
2513 Scru128Id::from_bytes(frame_id_bytes.try_into().unwrap())
2514}
2515
2516fn deserialize_frame<B1: AsRef<[u8]> + std::fmt::Debug, B2: AsRef<[u8]>>(
2517 record: (B1, B2),
2518) -> Frame {
2519 serde_json::from_slice(record.1.as_ref()).unwrap_or_else(|e| {
2520 // Try to convert the key to a Scru128Id and print in a format that can be copied for deletion
2521 let key_bytes = record.0.as_ref();
2522 if key_bytes.len() == 16 {
2523 if let Ok(bytes) = key_bytes.try_into() {
2524 let id = Scru128Id::from_bytes(bytes);
2525 eprintln!("CORRUPTED_RECORD_ID: {id}");
2526 }
2527 }
2528 let key = std::str::from_utf8(record.0.as_ref()).unwrap();
2529 let value = std::str::from_utf8(record.1.as_ref()).unwrap();
2530 panic!("Failed to deserialize frame: {e} {key} {value}")
2531 })
2532}