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}