Skip to main content

driftdb/
db.rs

1//! Top-level `Db` handle: group-commit writer thread, background flush/compaction thread,
2//! MVCC snapshot reads, and crash recovery.
3//!
4//! Write path: `put/delete/write_batch` -> channel -> writer thread -> WAL append + one
5//! `fdatasync` per drained batch -> memtable insert -> `visible_seq` published -> ack.
6//! When the active memtable crosses `Options::memtable_size` the writer thread freezes it,
7//! opens a new WAL, and wakes the background thread, which flushes the oldest frozen memtable
8//! to an L0 SST and (independently) runs leveled compaction. All mutations to the manifest,
9//! the live `Version`, and the memtable list happen on exactly one of these two threads, so
10//! there is never a race to install a new `Version` or append a manifest edit.
11//!
12//! Read path: active memtable -> frozen memtables (newest first) -> L0 (newest first) -> L1+
13//! (binary search into the non-overlapping sorted run). See `Inner::get_at` for the locking
14//! order that keeps a concurrent flush from ever hiding data mid-flight.
15
16use crate::compaction::{self, CompactionPlan, Table, Version};
17use crate::error::{Error, Result};
18use crate::iter::{self, BoxIter};
19use crate::manifest::{Manifest, ManifestRecord, SstMeta};
20use crate::memtable::{Entry, Memtable, Value};
21use crate::sstable::{sst_path, SstReader, SstWriter};
22use crate::wal::{self, WalFile};
23use parking_lot::{Condvar, Mutex, RwLock};
24use std::collections::BTreeMap;
25use std::io::BufWriter;
26use std::ops::{Bound, RangeBounds};
27use std::os::unix::io::AsRawFd;
28use std::path::{Path, PathBuf};
29use std::sync::atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering};
30use std::sync::{mpsc, Arc};
31use std::time::Duration;
32
33/// Engine tuning knobs. See each field for the default (matches the phase-2 plan).
34///
35/// New fields may be added in a minor (0.x) release. Construct with
36/// `Options { memtable_size: ..., ..Default::default() }` (or start from
37/// [`Options::default()`] and mutate individual fields) rather than a full struct literal, so
38/// adding a field there isn't a breaking change for callers.
39#[derive(Clone, Debug)]
40pub struct Options {
41    /// Freeze the active memtable and roll to a new WAL once its approximate size reaches this.
42    ///
43    /// This also bounds recovery time: replay on reopen never reads more than roughly
44    /// `memtable_size * (1 + MAX_IMMUTABLE_MEMTABLES)` bytes of WAL (the active memtable plus
45    /// however many frozen-but-unflushed ones `rotate` allows to queue -- see
46    /// `MAX_IMMUTABLE_MEMTABLES` in `db.rs`), since anything older has already been flushed to
47    /// an SST and its WAL deleted. Each memtable can overshoot that budget by at most one
48    /// request's bytes (`write_batch`'s ops are never split across a group-commit boundary), since
49    /// the writer thread stops draining a group commit once it's already queued that many bytes
50    /// -- see `writer_thread`'s `budget` in `db.rs`.
51    ///
52    /// Range: `>= MIN_MEMTABLE_SIZE` (1 KiB). `Db::open`/`open_with` rejects anything smaller
53    /// with `Error::InvalidArgument`.
54    pub memtable_size: usize,
55    /// Compact all of L0 (+ overlapping L1) once L0 holds at least this many files.
56    ///
57    /// Range: `>= 1`.
58    pub l0_compaction_trigger: usize,
59    /// L1's byte budget; `L_n`'s budget is `l1_max_bytes * level_multiplier^(n-1)`.
60    ///
61    /// Range: `>= 1`.
62    pub l1_max_bytes: u64,
63    /// Per-level growth factor for the byte budget above.
64    ///
65    /// Range: `>= 1` (`1` disables growth: every level above L1 shares L1's budget).
66    pub level_multiplier: u32,
67    /// Roll to a new output SST once a compaction/flush output reaches this size (only at a
68    /// user-key boundary).
69    ///
70    /// Range: `>= 1`.
71    pub target_file_size: u64,
72    /// Number of levels, L0..L(max_levels-1). The bottom level is never a compaction source.
73    ///
74    /// Range: `2..=255` (at least L0 + one bottom level; compaction encodes a level number as
75    /// `u8`, so `max_levels - 1` must fit in a `u8`).
76    pub max_levels: usize,
77    /// How long the writer thread waits for more writes to batch after draining what's already
78    /// queued, once at least one request has arrived. `Duration::ZERO` disables the wait.
79    pub commit_window: Duration,
80}
81
82/// Floor for [`Options::memtable_size`]. Small enough not to break tests that deliberately use
83/// a tiny memtable to force frequent rotation, large enough that a `Db` isn't rotating memtables
84/// (and WAL files) on every single write.
85const MIN_MEMTABLE_SIZE: usize = 1024;
86
87impl Default for Options {
88    fn default() -> Self {
89        Options {
90            memtable_size: 4 * 1024 * 1024,
91            l0_compaction_trigger: 4,
92            l1_max_bytes: 10 * 1024 * 1024,
93            level_multiplier: 10,
94            target_file_size: 2 * 1024 * 1024,
95            max_levels: 7,
96            commit_window: Duration::ZERO,
97        }
98    }
99}
100
101impl Options {
102    /// Reject out-of-range fields with [`Error::InvalidArgument`]. Called by
103    /// `Db::open`/`open_with` before the target directory is touched.
104    fn validate(&self) -> Result<()> {
105        if self.memtable_size < MIN_MEMTABLE_SIZE {
106            return Err(Error::InvalidArgument(format!(
107                "memtable_size {} is below the minimum of {MIN_MEMTABLE_SIZE}",
108                self.memtable_size
109            )));
110        }
111        if self.l0_compaction_trigger < 1 {
112            return Err(Error::InvalidArgument(
113                "l0_compaction_trigger must be >= 1".into(),
114            ));
115        }
116        if self.l1_max_bytes < 1 {
117            return Err(Error::InvalidArgument("l1_max_bytes must be >= 1".into()));
118        }
119        if self.level_multiplier < 1 {
120            return Err(Error::InvalidArgument(
121                "level_multiplier must be >= 1".into(),
122            ));
123        }
124        if self.target_file_size < 1 {
125            return Err(Error::InvalidArgument(
126                "target_file_size must be >= 1".into(),
127            ));
128        }
129        if !(2..=255).contains(&self.max_levels) {
130            return Err(Error::InvalidArgument(format!(
131                "max_levels {} must be in 2..=255",
132                self.max_levels
133            )));
134        }
135        Ok(())
136    }
137}
138
139/// A batch of puts/deletes applied atomically: one writer-thread request, consecutive seqnos,
140/// one ack.
141#[derive(Debug, Default, Clone)]
142pub struct WriteBatch {
143    ops: Vec<(Vec<u8>, Value)>,
144}
145
146impl WriteBatch {
147    /// An empty batch.
148    pub fn new() -> Self {
149        Self::default()
150    }
151
152    /// Queue a put. Builder-style: chain further `put`/`delete` calls.
153    pub fn put(mut self, key: impl Into<Vec<u8>>, val: impl Into<Vec<u8>>) -> Self {
154        self.ops.push((key.into(), Value::Put(val.into())));
155        self
156    }
157
158    /// Queue a tombstone write. Builder-style: chain further `put`/`delete` calls.
159    pub fn delete(mut self, key: impl Into<Vec<u8>>) -> Self {
160        self.ops.push((key.into(), Value::Delete));
161        self
162    }
163
164    /// True if no `put`/`delete` has been queued yet.
165    pub fn is_empty(&self) -> bool {
166        self.ops.is_empty()
167    }
168
169    /// Number of queued ops.
170    pub fn len(&self) -> usize {
171        self.ops.len()
172    }
173}
174
175/// Per-level file counts + byte totals, plus write-amplification inputs.
176///
177/// `#[non_exhaustive]`: new fields may be added in a minor (0.x) release; construct via
178/// [`Db::stats`] rather than a struct literal.
179#[derive(Debug, Clone, Default)]
180#[non_exhaustive]
181pub struct Stats {
182    /// Number of live SST files per level, index 0 = L0.
183    pub level_files: Vec<usize>,
184    /// Total SST bytes per level, index 0 = L0 (parallel to [`Stats::level_files`]).
185    pub level_bytes: Vec<u64>,
186    /// Approximate bytes held by the active memtable plus any frozen ones waiting to flush.
187    pub memtable_bytes: u64,
188    /// Total user key+value bytes ever written (the numerator/denominator base for
189    /// [`Stats::write_amplification`]; not reduced by deletes or compaction).
190    pub user_bytes_written: u64,
191    /// Bytes written to SST files by flushes and compactions combined (not the WAL -- see
192    /// [`Stats::wal_bytes_written`]).
193    pub disk_bytes_written: u64,
194    /// Bytes written to the WAL (post-fsync, i.e. only what actually reached disk).
195    pub wal_bytes_written: u64,
196    /// `true` if the background thread has no frozen memtable to flush, isn't mid-flush or
197    /// mid-compaction right now, and `compaction::pick` finds nothing to do at the current
198    /// version -- i.e. the engine is quiescent as far as background work goes. A benchmark
199    /// polling for "steady state" should use this instead of watching `level_bytes` stop moving:
200    /// that heuristic can't tell "actually done" apart from "between two compactions that happen
201    /// to land on the same byte totals".
202    pub background_idle: bool,
203}
204
205impl Stats {
206    /// Write amplification, defined the way RocksDB defines it: `(WAL bytes + flush bytes +
207    /// compaction bytes) / user bytes`. `disk_bytes_written` already sums flush + compaction
208    /// bytes (see `Db::stats`), so this is `(wal_bytes_written + disk_bytes_written) /
209    /// user_bytes_written`, or `0.0` before anything has been written.
210    pub fn write_amplification(&self) -> f64 {
211        if self.user_bytes_written == 0 {
212            0.0
213        } else {
214            (self.wal_bytes_written + self.disk_bytes_written) as f64
215                / self.user_bytes_written as f64
216        }
217    }
218}
219
220/// A point-in-time read view. Registers its seqno in the snapshot table on creation and
221/// unregisters on drop; while at least one snapshot is registered at or below a given seqno,
222/// the compactor keeps every version a read at that seqno (or lower) might need.
223pub struct Snapshot {
224    inner: Arc<Inner>,
225    seq: u64,
226}
227
228impl std::fmt::Debug for Snapshot {
229    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
230        f.debug_struct("Snapshot").field("seq", &self.seq).finish()
231    }
232}
233
234impl Snapshot {
235    /// The seqno this snapshot reads at (every write acked at or before this seqno is visible;
236    /// nothing after it is).
237    pub fn seq(&self) -> u64 {
238        self.seq
239    }
240
241    /// Point lookup at this snapshot's seqno.
242    pub fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
243        self.inner.get_at(key, self.seq)
244    }
245
246    /// Range scan at this snapshot's seqno.
247    pub fn scan<R: RangeBounds<Vec<u8>>>(&self, range: R) -> Result<Vec<(Vec<u8>, Vec<u8>)>> {
248        self.inner.scan_at(range, self.seq)
249    }
250}
251
252impl Drop for Snapshot {
253    fn drop(&mut self) {
254        self.inner.unregister_snapshot(self.seq);
255    }
256}
257
258/// Active + frozen memtables. `immutables` is oldest-first; each is tagged with the number of
259/// the WAL file that holds exactly its records (see module docs).
260struct MemState {
261    active: Arc<Memtable>,
262    immutables: Vec<(u64, Arc<Memtable>)>,
263}
264
265#[derive(Default)]
266struct StatsInner {
267    user_bytes: AtomicU64,
268    wal_bytes: AtomicU64,
269    bytes_flushed: AtomicU64,
270    bytes_compacted: AtomicU64,
271}
272
273/// One request sent to the writer thread.
274enum Req {
275    Write {
276        batch: Vec<(Vec<u8>, Value)>,
277        ack: tokio::sync::oneshot::Sender<Result<u64>>,
278    },
279    /// Force-rotate the active memtable (used by `flush()`), even if it's under the size
280    /// threshold. `ack` carries the WAL number of the memtable that was frozen, or `None` if
281    /// the active memtable was empty (nothing to flush).
282    Rotate {
283        ack: tokio::sync::oneshot::Sender<Result<Option<u64>>>,
284    },
285}
286
287/// Shared engine state. Every mutation to `manifest`, `version`, or `mem.immutables` (removal)
288/// happens on the background thread; every mutation to `mem.active`/`mem.immutables` (push)
289/// happens on the writer thread. `fatal` is the one-way poison switch: once set, the writer
290/// thread fails every request and the background thread stops picking new work.
291struct Inner {
292    dir: PathBuf,
293    options: Options,
294    version: RwLock<Arc<Version>>,
295    mem: RwLock<MemState>,
296    manifest: Mutex<Manifest>,
297    visible_seq: AtomicU64,
298    next_file_number: AtomicU64,
299    /// seqno -> count of live `Snapshot`s registered at that seqno.
300    snapshots: Mutex<BTreeMap<u64, usize>>,
301    fatal: Mutex<Option<String>>,
302    shutdown: AtomicBool,
303    /// Count of `Db::compact()` calls currently in flight (fetch_add on entry, fetch_sub on
304    /// exit); the background thread's picker bypasses the normal trigger thresholds while this
305    /// is nonzero. A plain bool would livelock two concurrent `compact()` callers: whichever
306    /// finishes first would reset it to "off" while the other is still waiting for
307    /// `pick_forced` to run, and the picker would silently go back to the normal thresholds and
308    /// never satisfy the still-waiting caller.
309    force_compact: AtomicUsize,
310    /// Set by `bg_thread` while it's actually inside `do_flush`/`do_compact` (not just picking
311    /// work or sleeping). Read by `Stats::background_idle`.
312    bg_busy: AtomicBool,
313    /// Cleared (via an RAII guard) the moment `bg_thread` returns, including on panic. Belt and
314    /// braces for `wait_flushed`/`rotate`'s stall loop: with `Guard::shutdown_and_join`'s
315    /// join-writer-before-shutdown ordering, the background thread should never exit while a
316    /// memtable a caller is waiting on is still unflushed -- but if it ever does (e.g. a panic),
317    /// this lets those callers return an error instead of polling forever for a flush that will
318    /// never come.
319    bg_alive: AtomicBool,
320    work_mu: Mutex<()>,
321    work_cv: Condvar,
322    stall_mu: Mutex<()>,
323    stall_cv: Condvar,
324    flush_mu: Mutex<()>,
325    flush_cv: Condvar,
326    stats: StatsInner,
327}
328
329impl std::fmt::Debug for Inner {
330    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
331        f.debug_struct("Inner").field("dir", &self.dir).finish()
332    }
333}
334
335/// Error returned to a caller whose request can't reach the writer thread: normal shutdown (the
336/// sender was dropped by `Guard::shutdown_and_join`) or the writer thread having gone away
337/// unexpectedly (e.g. a panic, which drops its ack sender without replying). Both look the same
338/// from here -- the channel is just closed -- so the message says so plainly rather than
339/// guessing which one happened.
340fn closed_err() -> Error {
341    Error::Io(std::io::Error::other(
342        "driftdb: engine closed (writer thread is no longer running -- either close()/Drop \
343         already ran, or the writer thread exited unexpectedly)",
344    ))
345}
346
347impl Inner {
348    fn notify_bg(&self) {
349        self.work_cv.notify_all();
350    }
351
352    fn notify_all_waiters(&self) {
353        self.stall_cv.notify_all();
354        self.flush_cv.notify_all();
355    }
356
357    fn check_fatal(&self) -> Result<()> {
358        if let Some(msg) = self.fatal.lock().clone() {
359            return Err(Error::Io(std::io::Error::other(msg)));
360        }
361        Ok(())
362    }
363
364    /// Register a new read view at the current `visible_seq` and return it. Registration and the
365    /// `visible_seq` read happen under the same `snapshots` lock that [`Inner::oldest_snapshot`]
366    /// uses, so a concurrent compaction can never observe a `visible_seq` that's newer than what
367    /// this call is about to register (which would let it GC a version this read still needs).
368    ///
369    /// ponytail: one mutex lock/unlock pair per registration is the whole cost of correctness
370    /// here; a lock-free epoch scheme would remove the mutex from the read path entirely if this
371    /// ever shows up in a profile.
372    fn register_snapshot(&self) -> u64 {
373        let mut snapshots = self.snapshots.lock();
374        let seq = self.visible_seq.load(Ordering::Acquire);
375        *snapshots.entry(seq).or_insert(0) += 1;
376        seq
377    }
378
379    /// Unregister a read view previously returned by [`Inner::register_snapshot`].
380    ///
381    /// No `notify_all_waiters()` here: `stall_cv` is only waited on by `rotate` (for
382    /// `mem.immutables` shrinking, which only `do_flush` changes) and `flush_cv` only by
383    /// `wait_flushed`/`compact_blocking` (for a flush/compaction actually finishing, which
384    /// `do_flush`/`do_compact` already notify on). Nothing ever blocks on a condvar waiting for
385    /// the *snapshot table* to shrink -- `do_compact` just reads `oldest_snapshot()` once, it
386    /// doesn't wait for it to advance -- so broadcasting on every `get`/`scan` unregister (i.e.
387    /// on every read) was pure overhead.
388    fn unregister_snapshot(&self, seq: u64) {
389        let mut snapshots = self.snapshots.lock();
390        if let Some(count) = snapshots.get_mut(&seq) {
391            *count -= 1;
392            if *count == 0 {
393                snapshots.remove(&seq);
394            }
395        }
396    }
397
398    fn oldest_snapshot(&self) -> u64 {
399        let snapshots = self.snapshots.lock();
400        let floor = snapshots.keys().next().copied().unwrap_or(u64::MAX);
401        let visible = self.visible_seq.load(Ordering::Acquire);
402        drop(snapshots);
403        floor.min(visible)
404    }
405
406    fn alloc_file_number(&self) -> u64 {
407        self.next_file_number.fetch_add(1, Ordering::SeqCst)
408    }
409
410    /// Read at `seq`: active -> frozen (newest first) -> L0 (newest first) -> L1+ (binary
411    /// search). Memtables are snapshotted *before* the version so a flush that's mid-flight can
412    /// never hide data: the background thread installs the new version before it drops the
413    /// frozen memtable, so a reader either still sees the memtable or already sees the new SST.
414    fn get_at(&self, key: &[u8], seq: u64) -> Result<Option<Vec<u8>>> {
415        self.check_fatal()?;
416        let (active, immutables) = {
417            let mem = self.mem.read();
418            (
419                mem.active.clone(),
420                mem.immutables
421                    .iter()
422                    .rev()
423                    .map(|(_, m)| m.clone())
424                    .collect::<Vec<_>>(),
425            )
426        };
427        let version = self.version.read().clone();
428
429        if let Some(v) = active.get(key, seq) {
430            return Ok(as_option(v));
431        }
432        for imm in &immutables {
433            if let Some(v) = imm.get(key, seq) {
434                return Ok(as_option(v));
435            }
436        }
437        if let Some(l0) = version.levels.first() {
438            for table in l0 {
439                if key < table.meta.smallest.as_slice() || key > table.meta.largest.as_slice() {
440                    continue;
441                }
442                if let Some(v) = table.reader.get(key, seq)? {
443                    return Ok(as_option(v));
444                }
445            }
446        }
447        for level in version.levels.iter().skip(1) {
448            let idx = level.partition_point(|t| t.meta.largest.as_slice() < key);
449            if let Some(table) = level.get(idx) {
450                if key >= table.meta.smallest.as_slice() && key <= table.meta.largest.as_slice() {
451                    if let Some(v) = table.reader.get(key, seq)? {
452                        return Ok(as_option(v));
453                    }
454                }
455            }
456        }
457        Ok(None)
458    }
459
460    fn scan_at<R: RangeBounds<Vec<u8>>>(
461        &self,
462        range: R,
463        seq: u64,
464    ) -> Result<Vec<(Vec<u8>, Vec<u8>)>> {
465        self.check_fatal()?;
466        let start_bound = range.start_bound().cloned();
467        let start: Vec<u8> = match &start_bound {
468            Bound::Included(k) | Bound::Excluded(k) => k.clone(),
469            Bound::Unbounded => Vec::new(),
470        };
471        let end_bound = range.end_bound().cloned();
472
473        let (active, immutables) = {
474            let mem = self.mem.read();
475            (
476                mem.active.clone(),
477                mem.immutables
478                    .iter()
479                    .rev()
480                    .map(|(_, m)| m.clone())
481                    .collect::<Vec<_>>(),
482            )
483        };
484        let version = self.version.read().clone();
485
486        // ponytail: memtables are collected eagerly (rather than streamed via a borrowing
487        // iterator) to sidestep a `BoxIter<'a>: Send` lifetime fight with the skiplist's range
488        // iterator. Fine while memtables are capped at a few MiB by `Options::memtable_size`;
489        // revisit if scans ever need to run against a much larger active memtable.
490        let mut sources: Vec<BoxIter<'_>> = Vec::new();
491        let active_entries: Vec<Entry> = active.iter_from(&start).collect();
492        sources.push(Box::new(active_entries.into_iter().map(Ok)));
493        for imm in &immutables {
494            let entries: Vec<Entry> = imm.iter_from(&start).collect();
495            sources.push(Box::new(entries.into_iter().map(Ok)));
496        }
497        for level in &version.levels {
498            for t in level {
499                if t.meta.largest.as_slice() < start.as_slice() {
500                    continue;
501                }
502                sources.push(Box::new(t.reader.iter_from(&start)));
503            }
504        }
505
506        let merged = iter::merge(sources);
507        let visible = iter::visible(merged, seq);
508        let mut out = Vec::new();
509        for item in visible {
510            let (k, v) = item?;
511            // `iter_from`/the SST readers seek to `start` inclusively, so an `Excluded` start
512            // bound needs its own filter here to drop the boundary key itself.
513            if let Bound::Excluded(s) = &start_bound {
514                if k.as_slice() == s.as_slice() {
515                    continue;
516                }
517            }
518            let past_end = match &end_bound {
519                Bound::Included(e) => k.as_slice() > e.as_slice(),
520                Bound::Excluded(e) => k.as_slice() >= e.as_slice(),
521                Bound::Unbounded => false,
522            };
523            if past_end {
524                break;
525            }
526            out.push((k, v));
527        }
528        Ok(out)
529    }
530
531    /// Flush the oldest frozen memtable (tagged with `wal_number`) to an L0 SST, append the
532    /// manifest edit, install the new version, then drop the memtable and delete its WAL file.
533    /// Only ever called from the background thread.
534    fn do_flush(&self, wal_number: u64, memtable: &Arc<Memtable>) -> Result<()> {
535        let mut edit = Vec::new();
536        let mut new_table: Option<Arc<Table>> = None;
537        let last_seq = if memtable.is_empty() {
538            self.visible_seq.load(Ordering::Acquire)
539        } else {
540            let number = self.alloc_file_number();
541            let path = sst_path(&self.dir, number);
542            let file = std::fs::File::create(&path)?;
543            let mut w = SstWriter::new(BufWriter::new(file));
544            for (k, seq, v) in memtable.iter_from(&[]) {
545                w.add(&k, seq, &v)?;
546            }
547            let (bufw, summary) = w.finish()?;
548            bufw.into_inner().map_err(|e| e.into_error())?.sync_all()?;
549            wal::sync_dir(&self.dir)?;
550            let meta = SstMeta {
551                number,
552                smallest: summary.smallest,
553                largest: summary.largest,
554                size: summary.file_size,
555                max_seq: summary.max_seq,
556            };
557            let reader = Arc::new(SstReader::open(&path)?);
558            new_table = Some(Arc::new(Table {
559                meta: meta.clone(),
560                reader,
561            }));
562            edit.push(ManifestRecord::SstAdded { level: 0, meta });
563            self.stats
564                .bytes_flushed
565                .fetch_add(summary.file_size, Ordering::Relaxed);
566            summary.max_seq
567        };
568        edit.push(ManifestRecord::WalFlushed {
569            number: wal_number,
570            last_seq,
571        });
572        edit.push(ManifestRecord::NextFileNumber(
573            self.next_file_number.load(Ordering::SeqCst),
574        ));
575        self.manifest.lock().append(&edit)?;
576
577        if let Some(table) = new_table {
578            let mut v = self.version.write();
579            let mut nv = (**v).clone();
580            if nv.levels.is_empty() {
581                nv.levels.push(Vec::new());
582            }
583            nv.levels[0].insert(0, table);
584            *v = Arc::new(nv);
585        }
586
587        {
588            let mut mem = self.mem.write();
589            mem.immutables.retain(|(n, _)| *n != wal_number);
590        }
591        let _ = std::fs::remove_file(wal::wal_path(&self.dir, wal_number));
592        self.notify_all_waiters();
593        Ok(())
594    }
595
596    /// Run one compaction plan and install its result. Only ever called from the background
597    /// thread.
598    fn do_compact(&self, plan: &CompactionPlan) -> Result<()> {
599        let version = self.version.read().clone();
600        let result = compaction::run(
601            &self.dir,
602            &self.options,
603            plan,
604            &version,
605            self.oldest_snapshot(),
606            &self.next_file_number,
607        )?;
608
609        let mut edit = Vec::new();
610        for meta in &result.added {
611            edit.push(ManifestRecord::SstAdded {
612                level: result.output_level,
613                meta: meta.clone(),
614            });
615        }
616        for (level, number) in &result.deleted {
617            edit.push(ManifestRecord::SstDeleted {
618                level: *level,
619                number: *number,
620            });
621        }
622        edit.push(ManifestRecord::NextFileNumber(
623            self.next_file_number.load(Ordering::SeqCst),
624        ));
625        self.manifest.lock().append(&edit)?;
626
627        let bytes_out: u64 = result.added.iter().map(|m| m.size).sum();
628        self.stats
629            .bytes_compacted
630            .fetch_add(bytes_out, Ordering::Relaxed);
631
632        {
633            let mut v = self.version.write();
634            let mut nv = (**v).clone();
635            for (level, number) in &result.deleted {
636                if let Some(l) = nv.levels.get_mut(*level as usize) {
637                    l.retain(|t| t.meta.number != *number);
638                }
639            }
640            let out = result.output_level as usize;
641            if nv.levels.len() <= out {
642                nv.levels.resize(out + 1, Vec::new());
643            }
644            nv.levels[out].extend(result.new_tables.iter().cloned());
645            nv.levels[out].sort_by(|a, b| a.meta.smallest.cmp(&b.meta.smallest));
646            *v = Arc::new(nv);
647        }
648
649        for (_, number) in &result.deleted {
650            let _ = std::fs::remove_file(sst_path(&self.dir, *number));
651        }
652        self.notify_all_waiters();
653        Ok(())
654    }
655
656    /// Block (synchronously) until the frozen memtable tagged `wal_number` has been flushed
657    /// (or, if `fatal` gets set first, return that error). Called from a `spawn_blocking` task.
658    ///
659    /// Also bails out if the background thread -- the only thing that can ever flush
660    /// `wal_number` -- has exited while the target is still unflushed (see `bg_alive`'s doc):
661    /// belt and braces so this polls at most a little past that, rather than forever, if the
662    /// shutdown-ordering invariant `Guard::shutdown_and_join` relies on is ever violated.
663    fn wait_flushed(&self, wal_number: u64) -> Result<()> {
664        loop {
665            self.check_fatal()?;
666            if !self
667                .mem
668                .read()
669                .immutables
670                .iter()
671                .any(|(n, _)| *n == wal_number)
672            {
673                return Ok(());
674            }
675            if !self.bg_alive.load(Ordering::SeqCst) {
676                return Err(Error::Io(std::io::Error::other(format!(
677                    "driftdb: background thread exited before flushing wal {wal_number}"
678                ))));
679            }
680            let mut g = self.flush_mu.lock();
681            self.flush_cv.wait_for(&mut g, Duration::from_millis(50));
682        }
683    }
684
685    /// Force a full compaction: bump the in-flight counter, wake the background thread, then
686    /// block until `pick_forced` has nothing left. Called from a `spawn_blocking` task.
687    ///
688    /// Under sustained concurrent writes this can run for a long time: every flush installs a
689    /// new L0 file, which restarts the compaction cascade `pick_forced` is draining, so a
690    /// `compact()` racing a steady stream of writers may not see `pick_forced` return `None`
691    /// until the writes stop (or slow down enough for compaction to catch up).
692    fn compact_blocking(&self) -> Result<()> {
693        self.force_compact.fetch_add(1, Ordering::SeqCst);
694        self.notify_bg();
695        let result = loop {
696            if let Err(e) = self.check_fatal() {
697                break Err(e);
698            }
699            let metas = self.version.read().level_metas();
700            if compaction::pick_forced(&metas, &self.options).is_none() {
701                break Ok(());
702            }
703            if !self.bg_alive.load(Ordering::SeqCst) {
704                break Err(Error::Io(std::io::Error::other(
705                    "driftdb: background thread exited before forced compaction finished",
706                )));
707            }
708            let mut g = self.flush_mu.lock();
709            self.flush_cv.wait_for(&mut g, Duration::from_millis(50));
710        };
711        self.force_compact.fetch_sub(1, Ordering::SeqCst);
712        result
713    }
714}
715
716fn as_option(v: Value) -> Option<Vec<u8>> {
717    match v {
718        Value::Put(v) => Some(v),
719        Value::Delete => None,
720    }
721}
722
723/// How many frozen memtables `rotate` lets pile up (waiting on the background flush thread)
724/// before it stalls new writes. This is also the recovery-time bound: on crash, the WAL holds at
725/// most the active memtable plus this many frozen-but-unflushed ones, so replay on reopen never
726/// has more than roughly `Options::memtable_size * (1 + MAX_IMMUTABLE_MEMTABLES)` bytes of WAL to
727/// read, plus at most one request's bytes per memtable -- see `Options::memtable_size`'s doc
728/// comment.
729const MAX_IMMUTABLE_MEMTABLES: usize = 2;
730
731/// Freeze the active memtable and open a fresh WAL, stalling while `MAX_IMMUTABLE_MEMTABLES`
732/// frozen memtables are already waiting on the background thread. Returns the WAL number the
733/// just-frozen memtable is tagged with, or `None` if the active memtable was empty. Only ever
734/// called from the writer thread.
735///
736/// The stall loop only checks `fatal`, not `shutdown`: `rotate` runs exclusively on the writer
737/// thread, and `Guard::shutdown_and_join` only ever sets `shutdown` *after* the writer thread has
738/// already been joined (so that the background thread can't observe `shutdown` and exit while
739/// the writer is still about to freeze a memtable it needs to flush -- see that function's doc).
740/// By the time `shutdown` could possibly be true, this function isn't running anymore either, so
741/// there is nothing for it to respect here. It does check `bg_alive` (belt and braces, same
742/// rationale as `wait_flushed`): if the background thread -- the only thing that ever drains
743/// `immutables` -- has exited while the backlog is still full, nothing will ever unstall this
744/// loop, so it errors out instead of stalling forever.
745fn rotate(inner: &Inner, wal: &mut WalFile) -> Result<Option<u64>> {
746    {
747        let mem = inner.mem.read();
748        if mem.active.is_empty() {
749            // Nothing new to freeze, but a flush caller still needs to wait for whatever's
750            // already frozen. Flushes drain `immutables` oldest-first, so the newest entry's
751            // wal number is a valid wait target: once it's gone, every older one is too.
752            return Ok(mem.immutables.last().map(|(n, _)| *n));
753        }
754    }
755    loop {
756        if inner.mem.read().immutables.len() < MAX_IMMUTABLE_MEMTABLES {
757            break;
758        }
759        inner.check_fatal()?;
760        if !inner.bg_alive.load(Ordering::SeqCst) {
761            return Err(Error::Io(std::io::Error::other(
762                "driftdb: background thread exited while writes were stalled waiting for a flush",
763            )));
764        }
765        let mut g = inner.stall_mu.lock();
766        if inner.mem.read().immutables.len() >= MAX_IMMUTABLE_MEMTABLES {
767            inner.stall_cv.wait_for(&mut g, Duration::from_millis(50));
768        }
769    }
770    let old_wal_number = wal.number();
771    let new_number = inner.alloc_file_number();
772    let new_wal = WalFile::create(&inner.dir, new_number)?;
773    let old_wal = std::mem::replace(wal, new_wal);
774    drop(old_wal);
775
776    let mut mem = inner.mem.write();
777    let old_active = std::mem::replace(&mut mem.active, Arc::new(Memtable::new()));
778    mem.immutables.push((old_wal_number, old_active));
779    drop(mem);
780    Ok(Some(old_wal_number))
781}
782
783fn fail_write(ack: tokio::sync::oneshot::Sender<Result<u64>>, msg: &str) {
784    let _ = ack.send(Err(Error::Io(std::io::Error::other(msg.to_string()))));
785}
786
787fn fail_rotate(ack: tokio::sync::oneshot::Sender<Result<Option<u64>>>, msg: &str) {
788    let _ = ack.send(Err(Error::Io(std::io::Error::other(msg.to_string()))));
789}
790
791/// Total key+value bytes a request would add to the memtable (`0` for `Req::Rotate`, which adds
792/// nothing). Used by `writer_thread` to bound how many bytes one group commit drains.
793fn write_req_bytes(req: &Req) -> u64 {
794    match req {
795        Req::Write { batch, .. } => batch
796            .iter()
797            .map(|(k, v)| {
798                k.len() as u64
799                    + match v {
800                        Value::Put(v) => v.len() as u64,
801                        Value::Delete => 0,
802                    }
803            })
804            .sum(),
805        Req::Rotate { .. } => 0,
806    }
807}
808
809/// Cap on requests drained into one group-commit batch. Higher pays off under heavy concurrency
810/// (more puts amortized over one `fdatasync`); it costs nothing at low concurrency since
811/// `rx.try_recv()` simply returns empty once the queue is drained, so this is sized for the
812/// high end (hundreds to low thousands of concurrent callers) rather than split into a separate
813/// low-concurrency tier.
814const MAX_BATCH_REQUESTS: usize = 1024;
815
816/// The single writer thread: owns the current WAL file, batches requests via group commit, and
817/// is the only place that ever appends to `mem.active` or freezes it into `mem.immutables`.
818fn writer_thread(inner: Arc<Inner>, rx: mpsc::Receiver<Req>, mut wal: WalFile) {
819    loop {
820        let first = match rx.recv() {
821            Ok(r) => r,
822            Err(_) => break, // every Sender dropped -- shut down.
823        };
824        // Bound how many bytes this group commit can add to the active memtable: once the
825        // batch already holds at least `budget` bytes of ops, stop draining, even if
826        // `MAX_BATCH_REQUESTS` hasn't been reached yet. Without this, draining purely by request
827        // count let one group overshoot `memtable_size` by however much a burst of large
828        // requests added up to (up to `MAX_BATCH_REQUESTS` of them) before `rotate` ever got a
829        // chance to look at the size -- see `Options::memtable_size`'s doc comment. The first
830        // request is always taken regardless of `budget` so a single request larger than the
831        // whole budget still makes progress.
832        let budget = (inner.options.memtable_size as u64)
833            .saturating_sub(inner.mem.read().active.size() as u64);
834        let mut batch_bytes = write_req_bytes(&first);
835        let mut batch = vec![first];
836        while batch.len() < MAX_BATCH_REQUESTS && batch_bytes < budget {
837            match rx.try_recv() {
838                Ok(r) => {
839                    batch_bytes += write_req_bytes(&r);
840                    batch.push(r);
841                }
842                Err(_) => break,
843            }
844        }
845        if !inner.options.commit_window.is_zero() {
846            let deadline = std::time::Instant::now() + inner.options.commit_window;
847            while batch.len() < MAX_BATCH_REQUESTS && batch_bytes < budget {
848                let now = std::time::Instant::now();
849                if now >= deadline {
850                    break;
851                }
852                match rx.recv_timeout(deadline - now) {
853                    Ok(r) => {
854                        batch_bytes += write_req_bytes(&r);
855                        batch.push(r);
856                    }
857                    Err(_) => break,
858                }
859            }
860        }
861
862        if let Some(msg) = inner.fatal.lock().clone() {
863            for req in batch {
864                match req {
865                    Req::Write { ack, .. } => fail_write(ack, &msg),
866                    Req::Rotate { ack } => fail_rotate(ack, &msg),
867                }
868            }
869            continue;
870        }
871
872        let mut writes = Vec::new();
873        let mut rotates = Vec::new();
874        for req in batch {
875            match req {
876                Req::Write { batch, ack } => writes.push((batch, ack)),
877                Req::Rotate { ack } => rotates.push(ack),
878            }
879        }
880
881        let mut sync_failed = false;
882        if !writes.is_empty() {
883            let mut flat: Vec<(u64, Vec<u8>, Value)> = Vec::new();
884            let mut acks: Vec<(tokio::sync::oneshot::Sender<Result<u64>>, u64)> = Vec::new();
885            let mut seq = inner.visible_seq.load(Ordering::Relaxed);
886            let mut user_bytes = 0u64;
887            for (ops, ack) in writes {
888                for (k, v) in ops {
889                    seq += 1;
890                    wal.append(seq, &k, &v);
891                    user_bytes += k.len() as u64
892                        + match &v {
893                            Value::Put(v) => v.len() as u64,
894                            Value::Delete => 0,
895                        };
896                    flat.push((seq, k, v));
897                }
898                acks.push((ack, seq));
899            }
900
901            if flat.is_empty() {
902                for (ack, s) in acks {
903                    let _ = ack.send(Ok(s));
904                }
905            } else {
906                let wal_bytes = wal.pending_len();
907                match wal.sync() {
908                    Ok(()) => {
909                        let active = inner.mem.read().active.clone();
910                        for (s, k, v) in flat {
911                            active.insert(k, s, v);
912                        }
913                        inner.visible_seq.store(seq, Ordering::Release);
914                        inner
915                            .stats
916                            .user_bytes
917                            .fetch_add(user_bytes, Ordering::Relaxed);
918                        inner
919                            .stats
920                            .wal_bytes
921                            .fetch_add(wal_bytes, Ordering::Relaxed);
922                        for (ack, s) in acks {
923                            let _ = ack.send(Ok(s));
924                        }
925                    }
926                    Err(e) => {
927                        sync_failed = true;
928                        let msg = format!("engine poisoned after fsync failure: {e}");
929                        *inner.fatal.lock() = Some(msg.clone());
930                        inner.notify_all_waiters();
931                        inner.notify_bg();
932                        for (ack, _) in acks {
933                            fail_write(ack, &msg);
934                        }
935                    }
936                }
937            }
938        }
939
940        if sync_failed {
941            let msg = inner.fatal.lock().clone().unwrap_or_default();
942            for ack in rotates {
943                fail_rotate(ack, &msg);
944            }
945            continue;
946        }
947
948        let active_big = inner.mem.read().active.size() >= inner.options.memtable_size;
949        if active_big || !rotates.is_empty() {
950            match rotate(&inner, &mut wal) {
951                Ok(rotated) => {
952                    if rotated.is_some() {
953                        inner.notify_bg();
954                    }
955                    for ack in rotates {
956                        let _ = ack.send(Ok(rotated));
957                    }
958                }
959                Err(e) => {
960                    let msg = e.to_string();
961                    *inner.fatal.lock() = Some(msg.clone());
962                    inner.notify_all_waiters();
963                    inner.notify_bg();
964                    for ack in rotates {
965                        fail_rotate(ack, &msg);
966                    }
967                }
968            }
969        }
970    }
971    let _ = wal.sync();
972}
973
974/// RAII flip of `Inner::bg_alive` back to `false` when `bg_thread` returns -- including via an
975/// unwinding panic, so `wait_flushed`/`rotate`'s belt-and-braces checks can't be fooled by a
976/// stale `true` left behind by a background thread that died unexpectedly.
977struct BgAliveGuard<'a>(&'a AtomicBool);
978
979impl Drop for BgAliveGuard<'_> {
980    fn drop(&mut self) {
981        self.0.store(false, Ordering::SeqCst);
982    }
983}
984
985/// The single background thread: flushes frozen memtables (oldest first) then runs compaction,
986/// repeating until there's nothing left, then sleeps until woken. Exits once shutdown has been
987/// requested and every frozen memtable has been drained.
988fn bg_thread(inner: Arc<Inner>) {
989    let _bg_alive_guard = BgAliveGuard(&inner.bg_alive);
990    loop {
991        loop {
992            if inner.fatal.lock().is_some() {
993                break;
994            }
995            let oldest = inner.mem.read().immutables.first().cloned();
996            if let Some((wal_n, mt)) = oldest {
997                inner.bg_busy.store(true, Ordering::Relaxed);
998                let result = inner.do_flush(wal_n, &mt);
999                inner.bg_busy.store(false, Ordering::Relaxed);
1000                if let Err(e) = result {
1001                    tracing::error!("driftdb: flush of wal {wal_n} failed: {e}");
1002                    *inner.fatal.lock() = Some(format!("flush failed: {e}"));
1003                    inner.notify_all_waiters();
1004                }
1005                continue;
1006            }
1007            let version = inner.version.read().clone();
1008            let metas = version.level_metas();
1009            let plan = if inner.force_compact.load(Ordering::SeqCst) > 0 {
1010                compaction::pick_forced(&metas, &inner.options)
1011            } else {
1012                compaction::pick(&metas, &inner.options)
1013            };
1014            if let Some(plan) = plan {
1015                inner.bg_busy.store(true, Ordering::Relaxed);
1016                let result = inner.do_compact(&plan);
1017                inner.bg_busy.store(false, Ordering::Relaxed);
1018                if let Err(e) = result {
1019                    tracing::error!("driftdb: compaction failed: {e}");
1020                    *inner.fatal.lock() = Some(format!("compaction failed: {e}"));
1021                    inner.notify_all_waiters();
1022                }
1023                continue;
1024            }
1025            break;
1026        }
1027        // Keep running past `shutdown` while a forced `compact()` is still in flight -- it
1028        // polls `pick_forced` on its own and would otherwise spin forever once this thread,
1029        // the only thing that can actually run a plan, stops picking up work.
1030        //
1031        // Once `fatal` is set, though, nothing here will ever make progress again (every flush
1032        // and every compaction attempt bails out at the top of the inner loop), so `shutdown`
1033        // must be able to tear this thread down immediately regardless of leftover `immutables`
1034        // or an in-flight forced compaction -- otherwise a flush/fsync failure leaves a frozen
1035        // memtable stuck forever and `Guard::shutdown_and_join` (close()/Drop) never returns.
1036        //
1037        // `Guard::shutdown_and_join` only sets `shutdown` after the writer thread has already
1038        // been joined, so by the time this observes `shutdown == true`, the writer can no
1039        // longer be about to freeze a new immutable memtable behind this thread's back -- every
1040        // one it will ever produce is already in `mem.immutables` (or already flushed).
1041        let fatal = inner.fatal.lock().is_some();
1042        if inner.shutdown.load(Ordering::SeqCst)
1043            && (fatal
1044                || (inner.mem.read().immutables.is_empty()
1045                    && inner.force_compact.load(Ordering::SeqCst) == 0))
1046        {
1047            break;
1048        }
1049        let mut g = inner.work_mu.lock();
1050        inner.work_cv.wait_for(&mut g, Duration::from_millis(200));
1051    }
1052}
1053
1054/// Take an exclusive, non-blocking `flock` on `dir/LOCK` (creating it if needed) so at most one
1055/// `Db` -- in this process or another -- has `dir` open at a time. Two writers sharing a
1056/// WAL/manifest would corrupt each other's state, and mmap-based WAL replay racing a live writer
1057/// could SIGBUS, so this is checked before recovery touches anything else in `dir`.
1058///
1059/// The returned `File` must be kept open for as long as the lock should be held; the kernel
1060/// releases the lock when the fd is closed (including on process exit, e.g. `kill -9`, which is
1061/// exactly what lets `tests/crash_kill.rs`'s killed child not wedge the parent's reopen).
1062fn acquire_dir_lock(dir: &Path) -> Result<std::fs::File> {
1063    let path = dir.join("LOCK");
1064    let file = std::fs::OpenOptions::new()
1065        .read(true)
1066        .write(true)
1067        .create(true)
1068        .truncate(false)
1069        .open(&path)?;
1070    // Safety: `flock` on an fd this call owns exclusively until it returns; LOCK_NB makes the
1071    // call return immediately (EWOULDBLOCK) instead of blocking if another process holds it.
1072    let ret = unsafe { libc::flock(file.as_raw_fd(), libc::LOCK_EX | libc::LOCK_NB) };
1073    if ret != 0 {
1074        let err = std::io::Error::last_os_error();
1075        if err.raw_os_error() == Some(libc::EWOULDBLOCK) {
1076            return Err(Error::Locked(dir.to_path_buf()));
1077        }
1078        return Err(err.into());
1079    }
1080    Ok(file)
1081}
1082
1083/// Owns the writer-thread `Sender`, both thread `JoinHandle`s, and the directory lock. Reachable
1084/// only through `Db::guard` (an `Arc<Guard>`) -- never cloned into the threads themselves -- so
1085/// when the last `Db` handle drops, this drops too, which is what actually tells the threads to
1086/// stop.
1087struct Guard {
1088    inner: Arc<Inner>,
1089    sender: Mutex<Option<mpsc::Sender<Req>>>,
1090    handles: Mutex<Option<(std::thread::JoinHandle<()>, std::thread::JoinHandle<()>)>>,
1091    /// The `dir/LOCK` file from [`acquire_dir_lock`]. Cleared (closing the fd, releasing the
1092    /// flock) only *after* both threads have joined in `shutdown_and_join`, so a concurrent
1093    /// `Db::open` on the same directory can never race the writer/background threads while they
1094    /// still have the WAL or manifest open.
1095    lock: Mutex<Option<std::fs::File>>,
1096    /// Serializes `shutdown_and_join` across concurrent callers (e.g. two overlapping
1097    /// `Db::close()` calls, or one racing the final `Drop`). Without this, a losing caller could
1098    /// still set `shutdown = true` of its own accord before the winning caller's writer-thread
1099    /// join finishes, reopening the exact early-shutdown race `shutdown_and_join` exists to
1100    /// close. Held for the whole call so a second caller only proceeds (to what is then a no-op)
1101    /// once the first has fully finished.
1102    shutdown_mu: Mutex<()>,
1103}
1104
1105impl Guard {
1106    /// Idempotent. Order matters here: dropping the sender and joining the writer thread
1107    /// *before* setting `shutdown` is what makes this safe against the race that used to let
1108    /// the background thread exit early.
1109    ///
1110    /// Old bug: `shutdown` was set first. The background thread could then observe
1111    /// `shutdown == true` with `mem.immutables` empty and exit, while the writer thread was
1112    /// still draining its already-queued requests and about to `rotate` one last active
1113    /// memtable into `immutables` -- which would then sit there forever with nothing left to
1114    /// flush it. A concurrent `flush()`'s `wait_flushed` (or a concurrent `rotate`'s stall
1115    /// loop, if the backlog was full) would then poll forever for a flush that could never
1116    /// come.
1117    ///
1118    /// Fix: drop the sender (so `writer_thread`'s `rx.recv()` drains whatever's already queued
1119    /// and returns once empty) and join the writer thread FIRST, while the background thread is
1120    /// still very much alive and able to pick up anything the writer freezes. Only once the
1121    /// writer has fully stopped -- meaning every immutable memtable it will ever produce is
1122    /// already sitting in `mem.immutables` -- is it safe to set `shutdown` and let the
1123    /// background thread drain the rest and exit.
1124    fn shutdown_and_join(&self) {
1125        let _serialize = self.shutdown_mu.lock();
1126        *self.sender.lock() = None;
1127        if let Some((writer, bg)) = self.handles.lock().take() {
1128            let _ = writer.join();
1129            self.inner.shutdown.store(true, Ordering::SeqCst);
1130            self.inner.notify_bg();
1131            self.inner.notify_all_waiters();
1132            let _ = bg.join();
1133        } else {
1134            // Handles already taken by an earlier call (or another thread racing this one) --
1135            // still make sure `shutdown` is set and everyone still waiting gets woken.
1136            self.inner.shutdown.store(true, Ordering::SeqCst);
1137            self.inner.notify_bg();
1138            self.inner.notify_all_waiters();
1139        }
1140        *self.lock.lock() = None;
1141    }
1142}
1143
1144impl Drop for Guard {
1145    fn drop(&mut self) {
1146        self.shutdown_and_join();
1147    }
1148}
1149
1150/// The public handle. Cheap to clone (`Arc` under the hood). Every write blocks on the writer
1151/// thread's group commit; every read is lock-free past a couple of short `RwLock` reads.
1152///
1153/// Dropping the last clone joins the writer and background threads synchronously (see
1154/// `Guard::shutdown_and_join`) -- which may block on an in-progress flush or compaction -- so
1155/// data acked before the drop is never lost even if the caller never calls `close()`. Prefer
1156/// [`Db::close`] explicitly where possible, though: it's the same join, but `async` (via
1157/// `spawn_blocking`) instead of blocking whatever thread happens to run the final `Drop`.
1158#[derive(Clone)]
1159pub struct Db {
1160    guard: Arc<Guard>,
1161}
1162
1163impl std::fmt::Debug for Db {
1164    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1165        f.debug_struct("Db")
1166            .field("dir", &self.guard.inner.dir)
1167            .finish()
1168    }
1169}
1170
1171impl Db {
1172    /// Open (or create) a driftdb instance rooted at `path` with default [`Options`].
1173    pub async fn open(path: impl AsRef<Path>) -> Result<Self> {
1174        Self::open_with(path, Options::default()).await
1175    }
1176
1177    /// Open (or create) a driftdb instance rooted at `path` with custom [`Options`]. Runs
1178    /// recovery (manifest replay, orphan cleanup, WAL replay) synchronously on a blocking
1179    /// thread before returning.
1180    ///
1181    /// Validates `options` first (see each [`Options`] field's documented range) and fails with
1182    /// [`Error::InvalidArgument`] without touching `path` at all if any field is out of range.
1183    pub async fn open_with(path: impl AsRef<Path>, options: Options) -> Result<Self> {
1184        options.validate()?;
1185        let dir = path.as_ref().to_path_buf();
1186        tokio::task::spawn_blocking(move || open_sync(&dir, options))
1187            .await
1188            .map_err(|e| Error::Io(std::io::Error::other(e.to_string())))?
1189    }
1190
1191    fn send_req(&self, req: Req) -> Result<()> {
1192        let sender = self.guard.sender.lock();
1193        match sender.as_ref() {
1194            Some(s) => s.send(req).map_err(|_| closed_err()),
1195            None => Err(closed_err()),
1196        }
1197    }
1198
1199    /// Durable, atomic write of one or more ops. Returns the seqno of the batch's last op.
1200    ///
1201    /// Every key/value is checked against [`wal::MAX_KEY_LEN`]/[`wal::MAX_VALUE_LEN`] before the
1202    /// batch is sent to the writer thread; an oversized op fails the whole batch with
1203    /// [`Error::InvalidArgument`] and nothing is written. Empty keys and empty values are
1204    /// allowed.
1205    pub async fn write_batch(&self, batch: WriteBatch) -> Result<u64> {
1206        for (key, val) in &batch.ops {
1207            if key.len() > wal::MAX_KEY_LEN {
1208                return Err(Error::InvalidArgument(format!(
1209                    "key length {} exceeds MAX_KEY_LEN ({})",
1210                    key.len(),
1211                    wal::MAX_KEY_LEN
1212                )));
1213            }
1214            if let Value::Put(v) = val {
1215                if v.len() > wal::MAX_VALUE_LEN {
1216                    return Err(Error::InvalidArgument(format!(
1217                        "value length {} exceeds MAX_VALUE_LEN ({})",
1218                        v.len(),
1219                        wal::MAX_VALUE_LEN
1220                    )));
1221                }
1222            }
1223        }
1224        let (tx, rx) = tokio::sync::oneshot::channel();
1225        self.send_req(Req::Write {
1226            batch: batch.ops,
1227            ack: tx,
1228        })?;
1229        rx.await.map_err(|_| closed_err())?
1230    }
1231
1232    /// Durable put. Returns once the record is in the WAL + memtable.
1233    pub async fn put(&self, key: &[u8], val: &[u8]) -> Result<()> {
1234        self.write_batch(WriteBatch::new().put(key, val)).await?;
1235        Ok(())
1236    }
1237
1238    /// Tombstone write. Same durability contract as `put`.
1239    pub async fn delete(&self, key: &[u8]) -> Result<()> {
1240        self.write_batch(WriteBatch::new().delete(key)).await?;
1241        Ok(())
1242    }
1243
1244    /// Latest-version read. Registers a short-lived snapshot for the duration of the read so a
1245    /// concurrent compaction can't drop the version this call is in the middle of reading (see
1246    /// `Inner::register_snapshot`).
1247    ///
1248    /// The registration itself is kept (only the redundant condvar notify on unregister was
1249    /// removed -- see `Inner::unregister_snapshot`): once `get_at` has cloned the active/frozen
1250    /// memtable `Arc`s and the `Version` `Arc`, a *later* compaction genuinely can't take data
1251    /// away from this call (SSTs are immutable and `do_compact`/`do_flush` only ever install a
1252    /// new `Version`, never mutate an existing `Table` in place). But between this call
1253    /// registering `seq` and `get_at` actually taking those clones, an *already in-flight*
1254    /// compaction could otherwise install a version that already dropped a pre-`seq` entry this
1255    /// read needs (it computes `oldest_snapshot()` -- the floor below which it's safe to GC old
1256    /// versions/tombstones -- from the same `snapshots` map). Registering first closes that
1257    /// window: `oldest_snapshot()` can never be computed as newer than a `seq` that's already
1258    /// registered. Dropping registration entirely would reopen it, so it stays.
1259    ///
1260    /// Runs inline on the calling task, unlike [`Db::scan`]. `get` touches at most one block per
1261    /// SST level (bloom-filtered, mmap-backed) rather than a whole range, so its worst-case I/O
1262    /// and decompression cost is bounded and small enough to not need `spawn_blocking`'s
1263    /// overhead.
1264    pub async fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
1265        let inner = &self.guard.inner;
1266        let seq = inner.register_snapshot();
1267        let result = inner.get_at(key, seq);
1268        inner.unregister_snapshot(seq);
1269        result
1270    }
1271
1272    /// Full range scan at the current seqno (see [`Snapshot::scan`] for a fixed-seqno version).
1273    /// Same short-lived-snapshot protection as [`Db::get`].
1274    ///
1275    /// Unlike `get`, a scan's disk I/O and decompression cost scales with the range's size and
1276    /// isn't bounded, so it runs on a `spawn_blocking` thread rather than inline on the calling
1277    /// async task -- otherwise a large scan would stall every other task on the same tokio
1278    /// worker thread for as long as it took to walk the range.
1279    pub async fn scan<R: RangeBounds<Vec<u8>>>(&self, range: R) -> Result<Vec<(Vec<u8>, Vec<u8>)>> {
1280        let owned_range: (Bound<Vec<u8>>, Bound<Vec<u8>>) =
1281            (range.start_bound().cloned(), range.end_bound().cloned());
1282        let inner = self.guard.inner.clone();
1283        tokio::task::spawn_blocking(move || {
1284            let seq = inner.register_snapshot();
1285            let result = inner.scan_at(owned_range, seq);
1286            inner.unregister_snapshot(seq);
1287            result
1288        })
1289        .await
1290        .map_err(|e| Error::Io(std::io::Error::other(e.to_string())))?
1291    }
1292
1293    /// Open a read snapshot at the current seqno. Compaction won't drop any version a live
1294    /// snapshot could still observe.
1295    pub fn snapshot(&self) -> Snapshot {
1296        let inner = self.guard.inner.clone();
1297        let seq = inner.register_snapshot();
1298        Snapshot { inner, seq }
1299    }
1300
1301    /// Force-rotate the active memtable (even if under the size threshold) and wait until it's
1302    /// been flushed to L0.
1303    pub async fn flush(&self) -> Result<()> {
1304        let (tx, rx) = tokio::sync::oneshot::channel();
1305        self.send_req(Req::Rotate { ack: tx })?;
1306        let target: Option<u64> = rx.await.map_err(|_| closed_err())??;
1307        if let Some(wal_n) = target {
1308            let inner = self.guard.inner.clone();
1309            tokio::task::spawn_blocking(move || inner.wait_flushed(wal_n))
1310                .await
1311                .map_err(|e| Error::Io(std::io::Error::other(e.to_string())))??;
1312        }
1313        Ok(())
1314    }
1315
1316    /// Flush, then force compaction until every level is under budget (or, in the case of L0
1317    /// and any level over its byte budget, fully drained one file at a time down to the bottom).
1318    ///
1319    /// Safe to call concurrently from multiple tasks -- each waits for the levels to actually
1320    /// be drained rather than for some other caller's flag. Under sustained concurrent writes,
1321    /// though, this can run for a long time (or, in principle, indefinitely if writes never let
1322    /// up): every flush adds a new L0 file, which restarts the compaction cascade this is
1323    /// waiting to drain.
1324    pub async fn compact(&self) -> Result<()> {
1325        self.flush().await?;
1326        let inner = self.guard.inner.clone();
1327        tokio::task::spawn_blocking(move || inner.compact_blocking())
1328            .await
1329            .map_err(|e| Error::Io(std::io::Error::other(e.to_string())))?
1330    }
1331
1332    /// Snapshot of current file/byte counts and write-amplification inputs.
1333    pub fn stats(&self) -> Stats {
1334        let inner = &self.guard.inner;
1335        let version = inner.version.read().clone();
1336        let mut level_files = Vec::with_capacity(version.levels.len());
1337        let mut level_bytes = Vec::with_capacity(version.levels.len());
1338        for level in &version.levels {
1339            level_files.push(level.len());
1340            level_bytes.push(level.iter().map(|t| t.meta.size).sum());
1341        }
1342        let (memtable_bytes, immutables_empty) = {
1343            let mem = inner.mem.read();
1344            let bytes = mem.active.size() as u64
1345                + mem
1346                    .immutables
1347                    .iter()
1348                    .map(|(_, m)| m.size() as u64)
1349                    .sum::<u64>();
1350            (bytes, mem.immutables.is_empty())
1351        };
1352        // Best-effort: each of these three checks is a separate, unsynchronized read, so a
1353        // background flush/compaction could start or finish between them. That only risks a
1354        // stale `true`/`false` for one `stats()` call, never a hang -- callers polling this in a
1355        // loop (see `benches/report.rs`) converge on the next poll.
1356        let background_idle = immutables_empty
1357            && !inner.bg_busy.load(Ordering::Relaxed)
1358            && compaction::pick(&version.level_metas(), &inner.options).is_none();
1359        Stats {
1360            level_files,
1361            level_bytes,
1362            memtable_bytes,
1363            user_bytes_written: inner.stats.user_bytes.load(Ordering::Relaxed),
1364            disk_bytes_written: inner.stats.bytes_flushed.load(Ordering::Relaxed)
1365                + inner.stats.bytes_compacted.load(Ordering::Relaxed),
1366            wal_bytes_written: inner.stats.wal_bytes.load(Ordering::Relaxed),
1367            background_idle,
1368        }
1369    }
1370
1371    /// Drain the writer thread and join both background threads. Idempotent; also runs (with a
1372    /// blocking join) if the last `Db` handle is simply dropped, so WAL-acked data always
1373    /// survives even without calling this explicitly.
1374    pub async fn close(&self) -> Result<()> {
1375        let guard = self.guard.clone();
1376        tokio::task::spawn_blocking(move || guard.shutdown_and_join())
1377            .await
1378            .map_err(|e| Error::Io(std::io::Error::other(e.to_string())))
1379    }
1380}
1381
1382/// Recovery + startup, run synchronously on a blocking thread. See the module docs and
1383/// `docs/plans/2026-09-25-driftdb-phase-2.md`'s "Recovery" section for the sequence.
1384fn open_sync(dir: &Path, options: Options) -> Result<Db> {
1385    std::fs::create_dir_all(dir)?;
1386    let lock_file = acquire_dir_lock(dir)?;
1387    let (mut manifest, mstate) = Manifest::open(dir)?;
1388
1389    let live_ssts: std::collections::HashSet<u64> =
1390        mstate.levels.iter().flatten().map(|m| m.number).collect();
1391    for entry in std::fs::read_dir(dir)? {
1392        let path = entry?.path();
1393        if let Some(name) = path.file_name().and_then(|n| n.to_str()) {
1394            if let Some(num_str) = name.strip_suffix(".sst") {
1395                if let Ok(num) = num_str.parse::<u64>() {
1396                    if !live_ssts.contains(&num) {
1397                        let _ = std::fs::remove_file(&path);
1398                    }
1399                }
1400            }
1401        }
1402    }
1403
1404    let wal_files = wal::list_wal_files(dir)?;
1405    for (n, p) in &wal_files {
1406        if *n <= mstate.last_flushed_wal {
1407            let _ = std::fs::remove_file(p);
1408        }
1409    }
1410    let remaining: Vec<(u64, PathBuf)> = wal_files
1411        .into_iter()
1412        .filter(|(n, _)| *n > mstate.last_flushed_wal)
1413        .collect();
1414
1415    let replay_mem = Memtable::new();
1416    let mut max_replayed_seq = 0u64;
1417    for (_n, p) in &remaining {
1418        let seq = wal::replay(p, |seq, key, val| {
1419            replay_mem.insert(key, seq, val);
1420        })?;
1421        max_replayed_seq = max_replayed_seq.max(seq);
1422    }
1423
1424    let mut next_file_number = mstate.next_file_number.max(1);
1425    let mut levels: Vec<Vec<SstMeta>> = mstate.levels.clone();
1426    let mut last_flushed_wal = mstate.last_flushed_wal;
1427
1428    if !replay_mem.is_empty() {
1429        let number = next_file_number;
1430        next_file_number += 1;
1431        let path = sst_path(dir, number);
1432        let file = std::fs::File::create(&path)?;
1433        let mut w = SstWriter::new(BufWriter::new(file));
1434        for (k, seq, v) in replay_mem.iter_from(&[]) {
1435            w.add(&k, seq, &v)?;
1436        }
1437        let (bufw, summary) = w.finish()?;
1438        bufw.into_inner().map_err(|e| e.into_error())?.sync_all()?;
1439        wal::sync_dir(dir)?;
1440        let meta = SstMeta {
1441            number,
1442            smallest: summary.smallest,
1443            largest: summary.largest,
1444            size: summary.file_size,
1445            max_seq: summary.max_seq,
1446        };
1447        if levels.is_empty() {
1448            levels.push(Vec::new());
1449        }
1450        levels[0].push(meta.clone());
1451        let max_wal_number = remaining.iter().map(|(n, _)| *n).max().unwrap();
1452        last_flushed_wal = last_flushed_wal.max(max_wal_number);
1453        manifest.append(&[
1454            ManifestRecord::SstAdded { level: 0, meta },
1455            ManifestRecord::WalFlushed {
1456                number: max_wal_number,
1457                last_seq: summary.max_seq.max(max_replayed_seq),
1458            },
1459            ManifestRecord::NextFileNumber(next_file_number),
1460        ])?;
1461        for (_n, p) in &remaining {
1462            let _ = std::fs::remove_file(p);
1463        }
1464    } else if !remaining.is_empty() {
1465        // Every `remaining` WAL replayed to zero records -- either genuinely empty (no writes
1466        // landed before the last close) or entirely torn (already truncated to nothing by
1467        // `wal::replay`). There's nothing to flush, but leaving these files on disk means one
1468        // extra empty `wal-*.log` piles up per open/close cycle forever, so clean them up here
1469        // too instead of only in the "had data" branch above.
1470        for (_n, p) in &remaining {
1471            let _ = std::fs::remove_file(p);
1472        }
1473    }
1474
1475    let last_seq = mstate.last_seq.max(max_replayed_seq);
1476
1477    let mut version_levels: Vec<Vec<Arc<Table>>> = Vec::with_capacity(levels.len());
1478    for (li, metas) in levels.iter().enumerate() {
1479        let mut tabs = Vec::with_capacity(metas.len());
1480        for m in metas {
1481            let reader = Arc::new(SstReader::open(&sst_path(dir, m.number))?);
1482            tabs.push(Arc::new(Table {
1483                meta: m.clone(),
1484                reader,
1485            }));
1486        }
1487        if li == 0 {
1488            tabs.sort_by_key(|a| std::cmp::Reverse(a.meta.number));
1489        } else {
1490            tabs.sort_by(|a, b| a.meta.smallest.cmp(&b.meta.smallest));
1491        }
1492        version_levels.push(tabs);
1493    }
1494
1495    let new_wal_number = next_file_number
1496        .max(remaining.iter().map(|(n, _)| n + 1).max().unwrap_or(0))
1497        .max(1);
1498    next_file_number = next_file_number.max(new_wal_number + 1);
1499    let wal_file = WalFile::create(dir, new_wal_number)?;
1500    manifest.append(&[ManifestRecord::NextFileNumber(next_file_number)])?;
1501
1502    let inner = Arc::new(Inner {
1503        dir: dir.to_path_buf(),
1504        options,
1505        version: RwLock::new(Arc::new(Version {
1506            levels: version_levels,
1507        })),
1508        mem: RwLock::new(MemState {
1509            active: Arc::new(Memtable::new()),
1510            immutables: Vec::new(),
1511        }),
1512        manifest: Mutex::new(manifest),
1513        visible_seq: AtomicU64::new(last_seq),
1514        next_file_number: AtomicU64::new(next_file_number),
1515        snapshots: Mutex::new(BTreeMap::new()),
1516        fatal: Mutex::new(None),
1517        shutdown: AtomicBool::new(false),
1518        force_compact: AtomicUsize::new(0),
1519        bg_busy: AtomicBool::new(false),
1520        bg_alive: AtomicBool::new(true),
1521        work_mu: Mutex::new(()),
1522        work_cv: Condvar::new(),
1523        stall_mu: Mutex::new(()),
1524        stall_cv: Condvar::new(),
1525        flush_mu: Mutex::new(()),
1526        flush_cv: Condvar::new(),
1527        stats: StatsInner::default(),
1528    });
1529    let _ = last_flushed_wal; // only used to compute `remaining` above; kept for clarity.
1530
1531    let (tx, rx) = mpsc::channel::<Req>();
1532    let writer_inner = inner.clone();
1533    let writer_handle = std::thread::Builder::new()
1534        .name("driftdb-writer".into())
1535        .spawn(move || writer_thread(writer_inner, rx, wal_file))
1536        .expect("spawn driftdb writer thread");
1537    let bg_inner = inner.clone();
1538    let bg_handle = std::thread::Builder::new()
1539        .name("driftdb-bg".into())
1540        .spawn(move || bg_thread(bg_inner))
1541        .expect("spawn driftdb background thread");
1542
1543    let guard = Arc::new(Guard {
1544        inner,
1545        sender: Mutex::new(Some(tx)),
1546        handles: Mutex::new(Some((writer_handle, bg_handle))),
1547        lock: Mutex::new(Some(lock_file)),
1548        shutdown_mu: Mutex::new(()),
1549    });
1550    Ok(Db { guard })
1551}