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