Skip to main content

my_lsm_db/
lib.rs

1//! # my-lsm-db
2//!
3//! Eine kleine, eingebettete LSM-Key-Value-Datenbank mit typisierter
4//! Entitäts-Schicht, optimistischer Nebenläufigkeit (CAS), Transaktionen,
5//! Composite-Indexen, Queries/Aggregationen sowie dateibasiertem
6//! Backup/Restore.
7//!
8//! ## Welche API soll ich nutzen?
9//!
10//! - [`entity::EntityStore`] ist die **empfohlene High-Level-API**: typisierte
11//!   Entitäten, Collections, Indizes, Queries, CAS und Transaktionen. Einstieg
12//!   hier.
13//! - [`Database`] ist die **Low-Level-KV-Engine** (rohe Byte-Keys/Values,
14//!   Compaction, Manifest-Introspektion). Die meisten Anwendungen benötigen
15//!   sie nicht.
16//!
17//! ## Schnelleinstieg
18//!
19//! Siehe das `intro`-Beispiel (`cargo run --example intro`) und
20//! `CHANGELOG.md`.
21//!
22//! ## Format & Kompatibilität
23//!
24//! Die On-Disk-Format-Version ist `1`. Jeder `v1.x`-Release liest Datenbanken,
25//! die von einem beliebigen `v1.x`- (sowie Legacy-v1-)Binary geschrieben
26//! wurden. Ein künftiges Format `2` wird mit
27//! [`error::Error::UnsupportedFormatVersion`] abgewiesen und erfordert ein
28//! explizites Migrationswerkzeug. Details in `CHANGELOG.md`
29//! (Abschnitt *Compatibility Policy*).
30
31// Stil-Lints: bewusst crate-weit erlaubt, um im Release-Hardening keine
32// massenhaften, risikobehafteten Umschreibungen vorzunehmen. Betreffen rein
33// Kosmetik (collapsible_if, type_complexity, …), keine Korrektheit. Der CI-Gate
34// `cargo clippy -- -D warnings` bleibt für alle übrigen Lints aktiv.
35#![allow(
36    clippy::collapsible_if,
37    clippy::type_complexity,
38    clippy::needless_range_loop,
39    clippy::should_implement_trait,
40    clippy::manual_is_multiple_of,
41    clippy::let_and_return,
42    clippy::len_zero,
43    clippy::get_first,
44    clippy::unnecessary_lazy_evaluations,
45    clippy::unnecessary_map_or,
46    clippy::suspicious_open_options
47)]
48
49pub mod codec;
50pub mod compaction;
51pub mod entity;
52pub mod error;
53pub mod index;
54pub mod iterator;
55pub mod keycodec;
56pub mod lsmql;
57pub mod manifest;
58pub mod memtable;
59pub mod ordering;
60pub mod query;
61pub mod schema;
62pub mod sstable;
63pub mod version;
64pub mod wal;
65
66use std::collections::HashMap;
67use std::path::{Path, PathBuf};
68
69use error::Result;
70use iterator::{MergeIter, ScanIter, ScanSource, memtable_source, merge_vecs};
71use manifest::{Manifest, SegmentMeta};
72use memtable::{Entry, MemTable};
73use wal::Wal;
74
75/// Standard-Größe der MemTable, bei der geflusht wird.
76pub const DEFAULT_MEMTABLE_LIMIT: usize = 4 * 1024 * 1024;
77/// Ab wie vielen Tabellen in Level 0 kompaktiert wird.
78pub const DEFAULT_L0_COMPACT_THRESHOLD: usize = 4;
79/// Standard-Record-Obergrenze pro L1-Segment (Split-Regel §11.2 der
80/// Design-Spez: deterministisch, keine Größensteuerung). Größenordnung im
81/// Bereich des MemTable-Limits.
82pub const DEFAULT_SEGMENT_MAX_RECORDS: usize = 30_000;
83
84/// Konfiguration der Datenbank.
85#[derive(Clone)]
86pub struct Options {
87    pub memtable_limit: usize,
88    pub l0_compact_threshold: usize,
89    /// Deterministische Split-Regel für die L1-Segmente: ein Segment wird
90    /// geschlossen, sobald es diese Record-Anzahl erreicht.
91    pub segment_max_records: usize,
92}
93
94impl Default for Options {
95    fn default() -> Self {
96        Options {
97            memtable_limit: DEFAULT_MEMTABLE_LIMIT,
98            l0_compact_threshold: DEFAULT_L0_COMPACT_THRESHOLD,
99            segment_max_records: DEFAULT_SEGMENT_MAX_RECORDS,
100        }
101    }
102}
103
104/// **Low-Level-KV-Engine** (nicht die empfohlene Anwendungs-API).
105///
106/// Bietet rohe Byte-`put`/`get`/`delete`/`scan` über WAL + MemTable + SSTables
107/// sowie Compaction- und Manifest-Introspektion. Die meisten Anwendungen sollen
108/// stattdessen [`entity::EntityStore`] verwenden.
109pub struct Database {
110    dir: PathBuf,
111    wal_path: PathBuf,
112    manifest_path: PathBuf,
113    wal: Wal,
114    memtable: MemTable,
115    manifest: Manifest,
116    opts: Options,
117    closed: bool,
118    /// Geöffnete SSTable-Reader, nach Tabellen-ID. Wird bei Flush/Compaction invalidiert.
119    table_cache: HashMap<u64, sstable::TableReader>,
120    /// Nächste frei zu vergebende Transaktions-ID (nie wiederverwendet).
121    next_tx_id: u64,
122    /// Beim Öffnen ermittelte Format-Version der Datenbank
123    /// (`1` für Legacy-DBs ohne `VERSION`-Datei).
124    format_version: u32,
125}
126
127/// Eine Segment-Information aus dem Manifest (Snapshot, nicht mutierend).
128#[derive(Debug, Clone)]
129pub struct SegmentInfo {
130    pub file_id: u64,
131    pub min_key: Vec<u8>,
132    pub max_key: Vec<u8>,
133    pub records: u64,
134}
135
136/// Strukturelle Zusammenfassung des Manifests (Snapshot, nicht mutierend).
137#[derive(Debug, Clone)]
138pub struct ManifestSummary {
139    pub next_table_id: u64,
140    pub levels: Vec<Vec<u64>>,
141    pub segments: Vec<SegmentInfo>,
142    pub level_count: usize,
143}
144
145/// Detail-Informationen zu einer physischen Tabelle.
146#[derive(Debug, Clone)]
147pub struct TableInfo {
148    pub id: u64,
149    pub level: usize,
150    pub path: PathBuf,
151    pub num_records: u64,
152    pub key_bounds_hex: String,
153    pub size_bytes: u64,
154}
155
156/// Kopie der wirksamen Compaction-/Engine-Optionen.
157#[derive(Debug, Clone, Copy)]
158pub struct DbOptionsView {
159    pub memtable_limit: usize,
160    pub l0_compact_threshold: usize,
161    pub segment_max_records: usize,
162}
163
164impl Database {
165    /// Öffnet (oder erstellt) eine Datenbank in `dir`. Spielt beim Start den
166    /// WAL neu und rekonstruiert den SSTable-Bestand aus dem Manifest.
167    pub fn open(dir: impl AsRef<Path>) -> Result<Database> {
168        Self::open_with(dir, Options::default())
169    }
170
171    pub fn open_with(dir: impl AsRef<Path>, opts: Options) -> Result<Database> {
172        let dir = dir.as_ref().to_path_buf();
173        std::fs::create_dir_all(&dir)?;
174        let wal_path = dir.join("wal.log");
175        let manifest_path = dir.join("MANIFEST");
176
177        // v0.9: DB-weiter Format-Versionierungsvertrag. Die `VERSION`-Datei ist
178        // die alleinige autoritative Quelle für die Format-Familie.
179        let format_version = match version::read_version(&dir) {
180            Ok(Some(v)) => {
181                version::check_compatible(v)?;
182                v
183            }
184            Ok(None) => {
185                if !manifest_path.exists() {
186                    // Frisch erzeugte DB: aktuelle Version dauerhaft schreiben.
187                    version::write_version(&dir, version::FORMAT_VERSION)?;
188                    version::FORMAT_VERSION
189                } else {
190                    // Legacy-v1-DB ohne `VERSION`: als v1 behandeln, nicht
191                    // umschreiben (bestehende Datenbanken bleiben lesbar).
192                    1
193                }
194            }
195            Err(e) => return Err(e),
196        };
197
198        let manifest = Manifest::load(&manifest_path)?;
199        // Rekonstruiere eine frische Manifest-Struktur bis zur maximalen Levelhöhe.
200        let max_level = manifest.levels.len();
201        let mut manifest = manifest;
202        while manifest.levels.len() < max_level.max(1) {
203            manifest.levels.push(Vec::new());
204        }
205
206        let wal = Wal::create(&wal_path)?;
207        let mut db = Database {
208            dir,
209            wal_path,
210            manifest_path,
211            wal,
212            memtable: MemTable::new(),
213            manifest,
214            opts,
215            closed: false,
216            table_cache: HashMap::new(),
217            next_tx_id: 0,
218            format_version,
219        };
220
221        // Manifest-Reconstruction (§12.3): Legacy-L1-Konvertierung + harte
222        // Validierung von Datei-Existenz und Segment-Ranges.
223        db.convert_legacy_l1()?;
224        db.validate_open_state()?;
225
226        // Recovery: WAL in die MemTable einspielen. Die höchste gesehene
227        // Transaktions-ID (auch uncommitteter) übernehmen, damit nach einem
228        // Crash keine TX-ID in demselben WAL wiederverwendet wird.
229        let replay = wal::replay(&db.wal_path)?;
230        for rec in replay.records {
231            db.memtable.put(rec.key, rec.value);
232        }
233        db.next_tx_id = replay.max_tx_id + 1;
234
235        Ok(db)
236    }
237
238    /// Legacy-Konvertierung (§12.3): Alte `L 1`-Tabellen (v0.7-C/1d-Ära) ohne
239    /// Segment-Metadaten werden in Segmente überführt, Range aus dem
240    /// SSTable-Index abgeleitet. Danach gelten die Segment-Invarianten.
241    fn convert_legacy_l1(&mut self) -> Result<()> {
242        if !self.manifest.segments.is_empty() {
243            return Ok(());
244        }
245        let Some(legacy) = self.manifest.levels.get(1).cloned() else {
246            return Ok(());
247        };
248        if legacy.is_empty() {
249            return Ok(());
250        }
251        for id in legacy {
252            let path = self.table_path(id);
253            let reader = sstable::TableReader::open(&path)?;
254            let Some((first, last)) = reader.key_bounds() else {
255                return Err(crate::error::Error::Corrupt(
256                    "legacy L1 table without index keys",
257                ));
258            };
259            self.manifest.segments.push(SegmentMeta {
260                file_id: id,
261                min_key: first.to_vec(),
262                max_key: last.to_vec(),
263                records: reader.num_records(),
264            });
265        }
266        self.manifest
267            .segments
268            .sort_unstable_by(|a, b| a.min_key.cmp(&b.min_key));
269        while self.manifest.levels.len() <= 1 {
270            self.manifest.levels.push(Vec::new());
271        }
272        self.manifest.levels[1] = Vec::new();
273        self.manifest.validate()
274    }
275
276    /// Harte Validierung beim Öffnen (§12.3): keine Manifest-Referenz darf auf
277    /// eine fehlende Datei zeigen; die Segment-Range muss mit dem Index der
278    /// Datei übereinstimmen. Verstöße sind `Corrupt`, kein stilles Droppen.
279    fn validate_open_state(&self) -> Result<()> {
280        for level in &self.manifest.levels {
281            for id in level {
282                if !self.table_path(*id).exists() {
283                    return Err(crate::error::Error::Corrupt(
284                        "manifest references missing L0 table",
285                    ));
286                }
287            }
288        }
289        for seg in &self.manifest.segments {
290            let path = self.table_path(seg.file_id);
291            if !path.exists() {
292                return Err(crate::error::Error::Corrupt(
293                    "manifest references missing segment file",
294                ));
295            }
296            let reader = sstable::TableReader::open(&path)?;
297            let Some((first, last)) = reader.key_bounds() else {
298                return Err(crate::error::Error::Corrupt(
299                    "segment table without index keys",
300                ));
301            };
302            if first != seg.min_key.as_slice() || last != seg.max_key.as_slice() {
303                return Err(crate::error::Error::Corrupt(
304                    "segment range mismatch with table index",
305                ));
306            }
307        }
308        Ok(())
309    }
310
311    /// Löscht einen Schlüssel (Tombstone).
312    ///
313    /// Nicht durable, solange die Operation returniert — der Write wird erst
314    /// nach einem erfolgreichen `flush()`/`close()` dauerhaft (deferred
315    /// durability). Transaktionen sind nach `commit()` durable.
316    pub fn delete(&mut self, key: &[u8]) -> Result<()> {
317        self.put_internal(key, None)
318    }
319
320    /// Setzt einen Wert. Append-only in WAL + MemTable, Flush bei Größenlimit.
321    ///
322    /// Nicht durable, solange die Operation returniert: der Write wird erst
323    /// nach einem erfolgreichen `flush()`/`close()` dauerhaft (deferred
324    /// durability). Für Durability `flush()`/`close()` nutzen; Transaktionen
325    /// sind nach `commit()` durable.
326    pub fn put(&mut self, key: &[u8], value: &[u8]) -> Result<()> {
327        self.put_internal(key, Some(value))
328    }
329
330    fn put_internal(&mut self, key: &[u8], value: Option<&[u8]>) -> Result<()> {
331        self.wal.append(key, value)?;
332        // Beim Löschen über MemTable als Tombstone speichern; der WAL-Eintrag
333        // (value=None) wird beim Recovery identisch rekonstruiert.
334        self.memtable.put(key.to_vec(), value.map(|v| v.to_vec()));
335
336        if self.memtable.size_bytes() >= self.opts.memtable_limit {
337            self.flush()?;
338        }
339        Ok(())
340    }
341
342    /// Vergibt eine monotone, niemals wiederverwendete Transaktions-ID.
343    pub(crate) fn alloc_tx_id(&mut self) -> u64 {
344        let id = self.next_tx_id;
345        self.next_tx_id += 1;
346        id
347    }
348
349    /// Schreibt eine `Begin`-Markierung für `tx` in den WAL-Puffer.
350    pub(crate) fn wal_begin(&mut self, tx: u64) -> Result<()> {
351        self.wal.append_begin(tx)
352    }
353
354    /// Schreibt eine `TxPut`-Mutation für `tx` in den WAL-Puffer.
355    pub(crate) fn wal_tx_put(&mut self, tx: u64, key: &[u8], value: &[u8]) -> Result<()> {
356        self.wal.append_tx_put(tx, key, value)
357    }
358
359    /// Schreibt eine `TxDelete`-Mutation für `tx` in den WAL-Puffer.
360    pub(crate) fn wal_tx_delete(&mut self, tx: u64, key: &[u8]) -> Result<()> {
361        self.wal.append_tx_delete(tx, key)
362    }
363
364    /// Schreibt eine `Commit`-Markierung für `tx` in den WAL-Puffer.
365    pub(crate) fn wal_commit(&mut self, tx: u64) -> Result<()> {
366        self.wal.append_commit(tx)
367    }
368
369    /// Leert den WAL-Puffer und macht ihn dauerhaft (fsync) — der Commit-Point.
370    pub(crate) fn wal_sync(&mut self) -> Result<()> {
371        self.wal.sync()
372    }
373
374    /// Wendet eine committete Mutation NUR auf die MemTable an (kein WAL-Write).
375    /// Infallibel: Ein Committeter `Commit`-Record ist bereits durable, das
376    /// MemTable-Apply danach darf nicht mehr fehlschlagen.
377    pub(crate) fn mem_put(&mut self, key: &[u8], value: &[u8]) {
378        self.memtable.put(key.to_vec(), Some(value.to_vec()));
379    }
380
381    /// Wendet eine committete Löschung NUR auf die MemTable an. Infallibel.
382    pub(crate) fn mem_delete(&mut self, key: &[u8]) {
383        self.memtable.put(key.to_vec(), None);
384    }
385
386    /// Best-Effort-Flush, falls die MemTable das Limit überschritten hat.
387    /// Nach einem Commit ist die Durability über den WAL gesichert, ein
388    /// Flush-Fehler hier ist also nicht kritisch.
389    pub(crate) fn flush_if_over_limit(&mut self) -> Result<()> {
390        if self.memtable.size_bytes() >= self.opts.memtable_limit {
391            self.flush()?;
392        }
393        Ok(())
394    }
395    /// Holt einen Wert. `None` = nicht vorhanden oder gelöscht.
396    ///
397    /// Gezielter Punkt-Lookup statt voller Snapshot: prüft die MemTable (neueste
398    /// Quelle), dann die Level von neu (0) nach alt. Innerhalb eines Levels wird
399    /// die neueste Tabelle zuerst geprüft. Der erste Treffer gewinnt. Dadurch ist
400    /// `get` O(Anzahl Tabellen) statt O(gesamte Datenmenge).
401    pub fn get(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>> {
402        // MemTable ist die neueste Quelle → autoritativ.
403        if let Some(entry) = self.memtable.get(key) {
404            return Ok(entry.clone());
405        }
406        // L0: neueste Tabelle zuerst.
407        if let Some(ids) = self.manifest.levels.first() {
408            for id in ids.iter().rev() {
409                let hit = if let Some(reader) = self.table_cache.get_mut(id) {
410                    reader.lookup(key)?
411                } else {
412                    // Nicht gecacht → öffnen und IMMER cachen (auch ein negativer
413                    // Lookup profitiert vom geparsten Index und geöffneten File).
414                    let path = self.table_path(*id);
415                    let mut reader = sstable::TableReader::open(&path)?;
416                    let result = reader.lookup(key)?;
417                    self.table_cache.insert(*id, reader);
418                    result
419                };
420                // lookup unterscheidet "vorhanden (auch Tombstone)" von "fehlt".
421                if let Some(entry) = hit {
422                    return Ok(entry);
423                }
424            }
425        }
426        // L1: genau das eine Segment, dessen [min_key, max_key] den Key enthält.
427        if let Some(i) = self.find_segment(key) {
428            let id = self.manifest.segments[i].file_id;
429            let hit = if let Some(reader) = self.table_cache.get_mut(&id) {
430                reader.lookup(key)?
431            } else {
432                let path = self.table_path(id);
433                let mut reader = sstable::TableReader::open(&path)?;
434                let result = reader.lookup(key)?;
435                self.table_cache.insert(id, reader);
436                result
437            };
438            if let Some(entry) = hit {
439                return Ok(entry);
440            }
441        }
442        Ok(None)
443    }
444
445    /// Binary-Search: das eine L1-Segment, dessen `[min_key, max_key]` `key`
446    /// enthält (Disjunktheits-Invariante garantiert max. ein Treffer).
447    fn find_segment(&self, key: &[u8]) -> Option<usize> {
448        let segs = &self.manifest.segments;
449        if segs.is_empty() {
450            return None;
451        }
452        // Letztes Segment mit min_key <= key.
453        let mut lo = 0usize;
454        let mut hi = segs.len();
455        while lo < hi {
456            let mid = (lo + hi) / 2;
457            if segs[mid].min_key.as_slice() <= key {
458                lo = mid + 1;
459            } else {
460                hi = mid;
461            }
462        }
463        if lo == 0 {
464            return None;
465        }
466        let i = lo - 1;
467        if key <= segs[i].max_key.as_slice() {
468            Some(i)
469        } else {
470            None
471        }
472    }
473
474    /// Bereichs-Scan `[start, end)`. Lazy — materialisiert **nicht** die
475    /// Datenmenge, sondern liefert einen Stream über MemTable-Kopie + gecachten
476    /// SSTable-Cursorn.
477    pub fn scan_stream<'a>(
478        &'a mut self,
479        start: Option<&[u8]>,
480        end: Option<&[u8]>,
481    ) -> Result<ScanIter<'a>> {
482        let mut sources: Vec<Box<dyn ScanSource>> = Vec::new();
483        // MemTable ist die neueste Quelle (Index 0). Kopie ist beschränkt
484        // (≤ memtable_limit) und über den exklusiven Borrow konsistent.
485        sources.push(Box::new(memtable_source(&self.memtable, start, end)));
486        // L0: neueste zuerst.
487        if let Some(ids) = self.manifest.levels.first() {
488            for id in ids.iter().rev() {
489                // Gecachte Reader wiederverwenden (Index/Bloom/Handle teilen),
490                // statt pro Scan jede Datei neu zu öffnen — sonst O(Tabellen) pro
491                // Scan und quadratisch über viele Puts.
492                if !self.table_cache.contains_key(id) {
493                    self.table_cache
494                        .insert(*id, sstable::TableReader::open(&self.table_path(*id))?);
495                }
496                let reader = self.table_cache.get(id).expect("cached").fork()?;
497                sources.push(Box::new(sstable::TableIter::from_reader(
498                    reader, start, end,
499                )?));
500            }
501        }
502        // L1-Segmente (disjunkt, sortiert nach min_key; jede Reihenfolge als
503        // Quelle ist korrekt, da sich die Ranges nicht überlappen).
504        for seg in &self.manifest.segments {
505            let id = seg.file_id;
506            if !self.table_cache.contains_key(&id) {
507                self.table_cache
508                    .insert(id, sstable::TableReader::open(&self.table_path(id))?);
509            }
510            let reader = self.table_cache.get(&id).expect("cached").fork()?;
511            sources.push(Box::new(sstable::TableIter::from_reader(
512                reader, start, end,
513            )?));
514        }
515        let merge = MergeIter::new(sources);
516        Ok(ScanIter::new(self, merge))
517    }
518
519    /// Bereichs-Scan `[start, end)`. Liefert sortierte `(key, Option<value>)`.
520    /// Komfort-Wrapper: sammelt [`scan_stream`](Self::scan_stream) ein.
521    ///
522    /// Tombstones (`None`) werden **nicht** ausgegeben: gelöschte Keys tauchen in
523    /// Scans nicht auf, unabhängig davon, ob ihr Tombstone bereits bei einer
524    /// Compaction physisch entfernt wurde. So ist ein Scan vor/nach Compaction
525    /// identisch. (`scan_stream` ist die rohe, lazy Variante und liefert die
526    /// Tombstones weiterhin als `None`.)
527    pub fn scan(
528        &mut self,
529        start: Option<&[u8]>,
530        end: Option<&[u8]>,
531    ) -> Result<Vec<(Vec<u8>, Option<Vec<u8>>)>> {
532        Ok(self
533            .scan_stream(start, end)?
534            .collect::<std::result::Result<Vec<_>, _>>()?
535            .into_iter()
536            .filter(|(_, v)| v.is_some())
537            .collect())
538    }
539
540    /// Erzwingt das Flushen der aktuellen MemTable als SSTable (Level 0).
541    pub fn flush(&mut self) -> Result<()> {
542        if self.memtable.is_empty() {
543            return Ok(());
544        }
545        let records: Vec<(Vec<u8>, Entry)> = self
546            .memtable
547            .iter()
548            .map(|(k, v)| (k.to_vec(), v.clone()))
549            .collect();
550
551        let id = self.manifest.next_table_id;
552        self.manifest.next_table_id += 1;
553        let table_path = self.table_path(id);
554        compaction::build_table_from_sorted(&table_path, &records)?;
555
556        while self.manifest.levels.len() < 1 {
557            self.manifest.levels.push(Vec::new());
558        }
559        self.manifest.levels[0].push(id);
560        self.manifest.save(&self.manifest_path)?;
561        self.table_cache.clear(); // Struktur hat sich geändert
562
563        // WAL leeren: alle Daten sind jetzt persistiert. MUSS über den Wal-Handle
564        // laufen, damit der BufWriter-Puffer verworfen wird (sonst schreibt ein
565        // späteres sync() die alten Records zurück in den geleerten Log).
566        self.wal.truncate()?;
567        self.memtable = MemTable::new();
568
569        // Optional kompaktieren.
570        if self.manifest.levels[0].len() >= self.opts.l0_compact_threshold {
571            self.compact()?;
572        }
573        Ok(())
574    }
575
576    /// 3a-Compaction (Overlap-Merge): hält L0 klein und ordnet die L0-Tabellen
577    /// in die L1-Segmente ein, ohne die komplette L1-Basis neu zu schreiben.
578    ///
579    /// Nur die L1-Segmente, deren Key-Range den L0-Batch-Span schneidet, werden
580    /// gelesen und durch neue Segmente ersetzt; nicht-überlappende Segmente
581    /// bleiben unangetastet (gleiche Datei, gleiche Range). Tombstones dürfen
582    /// physisch entfallen: für jeden Key im Merge-Span liegt die komplette
583    /// Historie im Merge-Set (Disjunktheits-Invariante + alle L0-Tabellen im
584    /// Batch).
585    fn compact(&mut self) -> Result<()> {
586        let l0 = self.manifest.levels.get(0).cloned().unwrap_or_default();
587        if l0.len() < self.opts.l0_compact_threshold {
588            return Ok(());
589        }
590        let (batch_min, batch_max) = self
591            .table_bounds(&l0)?
592            .ok_or_else(|| crate::error::Error::Corrupt("empty L0 table in compact"))?;
593
594        // Überlappende Segmente mergen, Rest behalten.
595        let overlaps = |s: &SegmentMeta| {
596            s.min_key.as_slice() <= batch_max.as_slice()
597                && s.max_key.as_slice() >= batch_min.as_slice()
598        };
599        let overlap_ids: Vec<u64> = self
600            .manifest
601            .segments
602            .iter()
603            .filter(|s| overlaps(s))
604            .map(|s| s.file_id)
605            .collect();
606        let retained: Vec<SegmentMeta> = self
607            .manifest
608            .segments
609            .iter()
610            .filter(|s| !overlaps(s))
611            .cloned()
612            .collect();
613
614        // Merge: L0-Tabellen (neueste zuerst) + überlappende Segmente.
615        let mut input_ids: Vec<u64> = l0.iter().copied().rev().collect();
616        input_ids.extend(overlap_ids.iter().copied());
617        let merged = self.merge_ids(&input_ids, true)?;
618
619        // Deterministischer Split: Chunks von `segment_max_records` → Segmente.
620        let mut new_segments: Vec<SegmentMeta> = Vec::new();
621        for chunk in merged.chunks(self.opts.segment_max_records) {
622            if chunk.is_empty() {
623                continue;
624            }
625            let id = self.write_table(chunk)?;
626            new_segments.push(SegmentMeta {
627                file_id: id,
628                min_key: chunk[0].0.clone(),
629                max_key: chunk[chunk.len() - 1].0.clone(),
630                records: chunk.len() as u64,
631            });
632        }
633
634        // Neue L1 = beibehaltene + neue Segmente, sortiert nach min_key.
635        let mut all = retained;
636        all.extend(new_segments);
637        all.sort_unstable_by(|a, b| a.min_key.cmp(&b.min_key));
638        self.manifest.segments = all;
639
640        // Manifest-COMMIT (fsync + atomarer rename) MUSS vor dem Löschen der
641        // alten SSTables passieren (Crash-Fenster §13 der Design-Spez).
642        while self.manifest.levels.len() < 1 {
643            self.manifest.levels.push(Vec::new());
644        }
645        self.manifest.levels[0] = Vec::new();
646        self.manifest.save(&self.manifest_path)?;
647        self.table_cache.clear(); // alte gelöscht, neue Segmente entstanden
648        for id in &l0 {
649            let _ = std::fs::remove_file(self.table_path(*id));
650        }
651        for &id in &overlap_ids {
652            let _ = std::fs::remove_file(self.table_path(id));
653        }
654        Ok(())
655    }
656
657    /// Bereinigt verwaiste (Orphan-)SSTables. **Expliziter Maintenance-Schritt**,
658    /// keine automatische Bereinigung beim Oeffnen (siehe Design-Doc §30.10).
659    ///
660    /// Sicherheitsregeln:
661    /// - Nur `.sst`-Dateien, deren `file_id` **nicht** im committed Manifest
662    ///   (`self.manifest`, identisch mit `MANIFEST` auf Disk) steht, werden
663    ///   geloescht. Referenzierte Dateien werden niemals angetastet.
664    /// - `.manifest.tmp` (nie recovery-relevant) wird ebenfalls entfernt.
665    /// - Keine Aenderung am Manifest, keine Compaction.
666    ///
667    /// Erfordert exklusiven Zugriff: der `&mut self`-Borrow stellt sicher,
668    /// dass waehrend `gc()` kein gleichzeitiger Lese-/Schreibzugriff auf
669    /// dieselbe DB-Instanz besteht (In-Process). Cross-Process-Locking ist
670    /// bewusst nicht implementiert.
671    ///
672    /// Rueckgabe: Anzahl geloeschter `.sst`-Orphans.
673    pub fn gc(&mut self) -> Result<usize> {
674        use std::collections::HashSet;
675        let referenced: HashSet<u64> = self.manifest.all_ids().into_iter().collect();
676
677        let mut removed = 0usize;
678        for entry in std::fs::read_dir(&self.dir)? {
679            let path = entry?.path();
680            // Nur echte `.sst`-Dateien betrachten.
681            if path.extension().and_then(|e| e.to_str()) != Some("sst") {
682                continue;
683            }
684            let stem = match path.file_stem().and_then(|s| s.to_str()) {
685                Some(s) => s,
686                None => continue,
687            };
688            // Unsere Dateien folgen exakt dem Schema `{:06}.sst` (6 Ziffern,
689            // zero-padded). Fremde/anders benannte `.sst` werden uebersprungen
690            // (Opt-in-Maintenance-Risiko).
691            if stem.len() != 6 || !stem.bytes().all(|b| b.is_ascii_digit()) {
692                continue;
693            }
694            let id: u64 = match stem.parse() {
695                Ok(v) => v,
696                Err(_) => continue,
697            };
698            if referenced.contains(&id) {
699                continue; // referenziert -> niemals anfassen
700            }
701            std::fs::remove_file(&path)?;
702            removed += 1;
703        }
704
705        // Stray `.manifest.tmp` ist nie recovery-relevant -> immer gefahrlos
706        // entfernen (nicht in `removed` gezaehlt, da kein `.sst`).
707        let tmp = self.manifest_path.with_extension("manifest.tmp");
708        if tmp.exists() {
709            let _ = std::fs::remove_file(&tmp);
710        }
711
712        // Cache von entfernten (unreferenzierten) Eintraegen befreien.
713        self.table_cache.retain(|id, _| referenced.contains(id));
714
715        Ok(removed)
716    }
717
718    /// Mergt die gegebenen Tabellen-IDs in der uebergebenen Reihenfolge
719    /// **neueste zuerst** (erste Quelle gewinnt bei Key-Kollision = LWW).
720    /// Der Aufrufer garantiert die Ordnung: L0-Tabellen (desc nach ID) vor
721    /// L1-Segmenten (disjunkt, Reihenfolge egal).
722    /// `drop_tombstones` steuert, ob endgueltige Tombstones (resultierender Wert
723    /// `None`) physisch entfernt werden - nur zulaessig, wenn die komplette
724    /// Historie jedes betroffenen Keys im Merge-Set liegt (11.1 der Spez).
725    fn merge_ids(&self, ids: &[u64], drop_tombstones: bool) -> Result<Vec<(Vec<u8>, Entry)>> {
726        let mut sources = Vec::new();
727        for id in ids {
728            let path = self.table_path(*id);
729            // Manifestierte SSTable muss lesbar sein: Ein Lesefehler (fehlende
730            // oder korrupte Datei) bricht die Compaction ab, statt die Tabelle
731            // still zu ueberspringen und Daten zu verlieren (E.8).
732            let mut reader = sstable::TableReader::open(&path)?;
733            let records = reader.iter()?;
734            sources.push(records);
735        }
736        let mut merged = merge_vecs(sources)?;
737        if drop_tombstones {
738            merged.retain(|(_, v)| v.is_some());
739        }
740        Ok(merged)
741    }
742
743    /// `[min_key, max_key]`-Span ueber mehrere Tabellen (erste/letzte Index-Keys).
744    fn table_bounds(&self, ids: &[u64]) -> Result<Option<(Vec<u8>, Vec<u8>)>> {
745        let mut min: Option<Vec<u8>> = None;
746        let mut max: Option<Vec<u8>> = None;
747        for id in ids {
748            let path = self.table_path(*id);
749            // Wie `merge_ids`: Eine unlesbare Tabelle darf die Compaction nicht
750            // still fortschreiten lassen (E.8).
751            let reader = sstable::TableReader::open(&path)?;
752            let (first, last) = reader.key_bounds().ok_or_else(|| {
753                crate::error::Error::Corrupt("empty L0 table referenced in compact")
754            })?;
755            let f = first.to_vec();
756            let l = last.to_vec();
757            if min.as_ref().map_or(true, |m| f < *m) {
758                min = Some(f);
759            }
760            if max.as_ref().map_or(true, |m| l > *m) {
761                max = Some(l);
762            }
763        }
764        Ok(match (min, max) {
765            (Some(a), Some(b)) => Some((a, b)),
766            _ => None,
767        })
768    }
769
770    /// Schreibt eine neue SSTable mit frischer ID und gibt die ID zurück.
771    /// `build_table_from_sorted` fsynct die neue Datei bereits.
772    fn write_table(&mut self, records: &[(Vec<u8>, Entry)]) -> Result<u64> {
773        let new_id = self.manifest.next_table_id;
774        self.manifest.next_table_id += 1;
775        let path = self.table_path(new_id);
776        compaction::build_table_from_sorted(&path, records)?;
777        Ok(new_id)
778    }
779
780    fn table_path(&self, id: u64) -> PathBuf {
781        self.dir.join(format!("{:06}.sst", id))
782    }
783
784    /// Anzahl der aktuell bekannten SSTables (für Tests/Inspektion).
785    pub fn table_count(&self) -> usize {
786        self.manifest.all_ids().len()
787    }
788
789    pub fn level_count(&self) -> usize {
790        self.manifest.levels.len()
791    }
792
793    /// Die beim Öffnen ermittelte Format-Version der Datenbank.
794    ///
795    /// `1` für Legacy-Datenbanken ohne `VERSION`-Datei; die geschriebene
796    /// Version für alle ab v0.9 erzeugten Datenbanken.
797    pub fn format_version(&self) -> u32 {
798        self.format_version
799    }
800
801    /// Strukturelle Zusammenfassung des Manifests (Snapshot, keine Mutation).
802    pub fn manifest_summary(&self) -> ManifestSummary {
803        ManifestSummary {
804            next_table_id: self.manifest.next_table_id,
805            levels: self.manifest.levels.clone(),
806            segments: self
807                .manifest
808                .segments
809                .iter()
810                .map(|s| SegmentInfo {
811                    file_id: s.file_id,
812                    min_key: s.min_key.clone(),
813                    max_key: s.max_key.clone(),
814                    records: s.records,
815                })
816                .collect(),
817            level_count: self.manifest.levels.len(),
818        }
819    }
820
821    /// Detail-Informationen zu jeder physischen Tabelle (Record-Count,
822    /// Key-Range als Hex, Dateigröße). Zuverlässig via `TableReader`.
823    pub fn table_infos(&self) -> Result<Vec<TableInfo>> {
824        let mut out = Vec::new();
825        let l0: Vec<u64> = self.manifest.levels.get(0).cloned().unwrap_or_default();
826        for &id in &l0 {
827            out.push(self.table_info(id, 0)?);
828        }
829        for seg in &self.manifest.segments {
830            out.push(self.table_info(seg.file_id, 1)?);
831        }
832        Ok(out)
833    }
834
835    fn table_info(&self, id: u64, level: usize) -> Result<TableInfo> {
836        let path = self.table_path(id);
837        let size = std::fs::metadata(&path).map(|m| m.len()).unwrap_or(0);
838        let mut num_records = 0u64;
839        let mut key_bounds_hex = String::new();
840        if let Ok(reader) = sstable::TableReader::open(&path) {
841            num_records = reader.num_records();
842            if let Some((a, b)) = reader.key_bounds() {
843                key_bounds_hex = format!("{}..{}", hex_encode(a), hex_encode(b));
844            }
845        }
846        Ok(TableInfo {
847            id,
848            level,
849            path,
850            num_records,
851            key_bounds_hex,
852            size_bytes: size,
853        })
854    }
855
856    /// Größe der `wal.log`-Datei in Bytes (0 falls nicht vorhanden).
857    pub fn wal_size(&self) -> u64 {
858        std::fs::metadata(&self.wal_path)
859            .map(|m| m.len())
860            .unwrap_or(0)
861    }
862
863    /// Gesamtgröße aller Dateien im DB-Verzeichnis in Bytes.
864    pub fn db_size(&self) -> u64 {
865        let mut total = 0u64;
866        if let Ok(entries) = std::fs::read_dir(&self.dir) {
867            for e in entries.flatten() {
868                if let Ok(meta) = e.metadata() {
869                    if meta.is_file() {
870                        total += meta.len();
871                    }
872                }
873            }
874        }
875        total
876    }
877
878    /// Kopie der wirksamen Compaction-/Engine-Optionen.
879    pub fn options_view(&self) -> DbOptionsView {
880        DbOptionsView {
881            memtable_limit: self.opts.memtable_limit,
882            l0_compact_threshold: self.opts.l0_compact_threshold,
883            segment_max_records: self.opts.segment_max_records,
884        }
885    }
886
887    /// Erzwingt eine vollständige Compaction (alle L0-Tabellen + alle
888    /// L1-Segmente -> frische L1-Segmente, Tombstones physisch entfernt).
889    ///
890    /// Durability-/Recovery-Vertrag: identisch zur bestehenden `compact()`:
891    /// Manifest-Commit (fsync + atomarer rename) erfolgt **vor** dem Löschen
892    /// der alten SSTables. Ein Crash mitten in `compact_full` lässt die alten,
893    /// vom alten Manifest referenzierten SSTables intakt -> DB bleibt
894    /// konsistent/öffbar. Scheitert das Einlesen einer Tabelle, bricht der
895    /// Aufruf ab, es wird nichts gelöscht, das Manifest bleibt unverändert.
896    pub fn compact_full(&mut self) -> Result<usize> {
897        // 1. MemTable vollständig persistieren, damit alles in SSTables liegt.
898        self.flush()?;
899
900        // 2. Alle Quell-Tabellen: L0 (neueste zuerst) + alle L1-Segmente.
901        let l0: Vec<u64> = self.manifest.levels.get(0).cloned().unwrap_or_default();
902        let old_segment_ids: Vec<u64> = self.manifest.segments.iter().map(|s| s.file_id).collect();
903        let mut input_ids: Vec<u64> = l0.iter().copied().rev().collect();
904        input_ids.extend(old_segment_ids.iter().copied());
905
906        let merged = self.merge_ids(&input_ids, true)?;
907
908        // 3. Deterministic Split in neue L1-Segmente.
909        let mut new_segments: Vec<SegmentMeta> = Vec::new();
910        for chunk in merged.chunks(self.opts.segment_max_records) {
911            if chunk.is_empty() {
912                continue;
913            }
914            let id = self.write_table(chunk)?;
915            new_segments.push(SegmentMeta {
916                file_id: id,
917                min_key: chunk[0].0.clone(),
918                max_key: chunk[chunk.len() - 1].0.clone(),
919                records: chunk.len() as u64,
920            });
921        }
922        new_segments.sort_unstable_by(|a, b| a.min_key.cmp(&b.min_key));
923
924        // 4. Alte IDs merken, bevor das Manifest ersetzt wird.
925        let mut old_ids: Vec<u64> = l0;
926        old_ids.extend(old_segment_ids);
927
928        // 5. Manifest-COMMIT (fsync + rename) VOR dem Löschen der alten SSTables.
929        self.manifest.segments = new_segments;
930        while self.manifest.levels.len() < 1 {
931            self.manifest.levels.push(Vec::new());
932        }
933        self.manifest.levels[0] = Vec::new();
934        self.manifest.save(&self.manifest_path)?;
935        self.table_cache.clear();
936
937        // 6. Alte SSTables entfernen (nur nach erfolgreichem Commit).
938        for id in old_ids {
939            let _ = std::fs::remove_file(self.table_path(id));
940        }
941        Ok(self.manifest.segments.len())
942    }
943
944    /// Erstellt eine konsistente, eigenständige Kopie der Datenbank im
945    /// Verzeichnis `dest` (Backup/Restore-Vertrag, Phase H Zweig A).
946    ///
947    /// Vertrag:
948    /// - Startet exklusiv über `&mut self`; pending Direct-Writes werden zuerst
949    ///   durch `flush()` persistent gemacht.
950    /// - Es werden nur die zum committed Manifest gehörenden Dateien kopiert:
951    ///   `VERSION` (falls vorhanden), `MANIFEST`, `SCHEMA` (falls vorhanden)
952    ///   sowie genau die vom Manifest referenzierten `*.sst`. `wal.log`,
953    ///   `*.tmp` und Orphan-`.sst` sind bewusst KEIN Teil des Backup-Roots.
954    /// - Ein halbfertiger Zustand wird niemals als Erfolg gemeldet: schlägt das
955    ///   Kopieren fehl, werden bereits kopierte Dateien und das Zielverzeichnis
956    ///   best-effort entfernt und `Err` zurückgegeben.
957    /// - Keine Cross-Process-Synchronisation (bewusst außerhalb des Vertrags).
958    ///
959    /// Rückgabe: Anzahl kopierter Dateien.
960    pub fn backup(&mut self, dest: &Path) -> Result<usize> {
961        // 1. Pending Direct-Writes persistent machen (Vertragspunkt 2).
962        self.flush()?;
963
964        // 2. Ziel vorbereiten: nicht existent oder leer (kein stilles Überschreiben).
965        if dest.exists() {
966            if !dir_is_empty(dest)? {
967                return Err(error::Error::InvalidArgument(
968                    "backup destination exists and is not empty".into(),
969                ));
970            }
971            std::fs::remove_dir(dest)?;
972        }
973        std::fs::create_dir_all(dest)?;
974
975        // 3. Expliziter Backup-Root (Vertragspunkt 3 + §2).
976        let mut files: Vec<(PathBuf, PathBuf)> = Vec::new();
977        let add_if = |from: &Path, files: &mut Vec<(PathBuf, PathBuf)>| {
978            if from.exists() {
979                if let Some(name) = from.file_name() {
980                    files.push((from.to_path_buf(), dest.join(name)));
981                }
982            }
983        };
984        add_if(&self.dir.join("VERSION"), &mut files);
985        add_if(&self.manifest_path, &mut files);
986        add_if(&self.dir.join("SCHEMA"), &mut files);
987        for id in self.manifest.all_ids() {
988            let src = self.table_path(id);
989            if let Some(name) = src.file_name().map(|n| n.to_os_string()) {
990                files.push((src, dest.join(name)));
991            }
992        }
993
994        // 4. Kopieren mit Cleanup bei Fehler (Vertragspunkt 4).
995        let mut copied: Vec<PathBuf> = Vec::new();
996        let res = (|| -> Result<()> {
997            for (from, to) in &files {
998                std::fs::copy(from, to)?;
999                copied.push(to.clone());
1000            }
1001            Ok(())
1002        })();
1003        if let Err(e) = res {
1004            for p in &copied {
1005                let _ = std::fs::remove_file(p);
1006            }
1007            let _ = std::fs::remove_dir(dest);
1008            return Err(e);
1009        }
1010        Ok(copied.len())
1011    }
1012
1013    /// Stellt eine zuvor via [`Database::backup`] erzeugte Kopie in `dest` wieder
1014    /// her (Backup/Restore-Vertrag, Phase H Zweig A).
1015    ///
1016    /// Vertrag:
1017    /// - `src` muss ein gültiger Backup-Root sein (zumindest `MANIFEST`).
1018    /// - Versionsprüfung über den v0.9-Mechanismus: eine unvereinbare
1019    ///   `VERSION` führt zu [`error::Error::UnsupportedFormatVersion`].
1020    /// - `dest` muss leer oder nicht existent sein; eine bestehende Datenbank
1021    ///   wird nicht stillschweigend überschrieben (`InvalidArgument`).
1022    /// - Es werden nur die Backup-Root-Dateien kopiert (`VERSION`, `MANIFEST`,
1023    ///   `SCHEMA`, referenzierte `*.sst`), kein `wal.log`/`*.tmp`/Orphans.
1024    /// - Bei Copy-Fehler: best-effort Cleanup, dann `Err`.
1025    ///
1026    /// Rückgabe: Anzahl kopierter Dateien.
1027    pub fn restore(src: &Path, dest: &Path) -> Result<usize> {
1028        // 1. Versionsprüfung über den v0.9-Mechanismus (Vertragspunkt 8).
1029        match version::read_version(src) {
1030            Ok(Some(v)) => version::check_compatible(v)?,
1031            Ok(None) => {}
1032            Err(e) => return Err(e),
1033        }
1034
1035        // 2. Backup-Root validieren.
1036        let src_manifest = src.join("MANIFEST");
1037        if !src_manifest.exists() {
1038            return Err(error::Error::InvalidFormat(
1039                "backup missing MANIFEST".into(),
1040            ));
1041        }
1042
1043        // 3. Ziel vorbereiten: leer oder nicht existent (Vertragspunkt 7/9).
1044        if dest.exists() {
1045            if !dir_is_empty(dest)? {
1046                return Err(error::Error::InvalidArgument(
1047                    "restore target exists and is not empty".into(),
1048                ));
1049            }
1050            std::fs::remove_dir(dest)?;
1051        }
1052        std::fs::create_dir_all(dest)?;
1053
1054        // 4. Expliziten Backup-Root kopieren.
1055        let manifest = Manifest::load(&src_manifest)?;
1056        let mut files: Vec<(PathBuf, PathBuf)> = Vec::new();
1057        for name in ["VERSION", "MANIFEST", "SCHEMA"] {
1058            let from = src.join(name);
1059            if from.exists() {
1060                let file_name = from.file_name().map(|n| n.to_os_string());
1061                if let Some(n) = file_name {
1062                    files.push((from, dest.join(n)));
1063                }
1064            }
1065        }
1066        for id in manifest.all_ids() {
1067            let name = format!("{:06}.sst", id);
1068            let from = src.join(&name);
1069            if from.exists() {
1070                files.push((from, dest.join(&name)));
1071            }
1072        }
1073
1074        // 5. Kopieren mit Cleanup bei Fehler.
1075        let mut copied: Vec<PathBuf> = Vec::new();
1076        let res = (|| -> Result<()> {
1077            for (from, to) in &files {
1078                std::fs::copy(from, to)?;
1079                copied.push(to.clone());
1080            }
1081            Ok(())
1082        })();
1083        if let Err(e) = res {
1084            for p in &copied {
1085                let _ = std::fs::remove_file(p);
1086            }
1087            let _ = std::fs::remove_dir(dest);
1088            return Err(e);
1089        }
1090        Ok(copied.len())
1091    }
1092
1093    /// Schließt die Datenbank OHNE Flush (rein lesend). Verhindert, dass der
1094    /// `Drop` noch ein Flush/WAL-Sync auslöst. Für `inspect`/`stats`, die die
1095    /// DB nicht mutieren dürfen.
1096    pub fn close_without_flush(mut self) {
1097        self.closed = true;
1098    }
1099
1100    pub fn level_tables(&self, level: usize) -> usize {
1101        if level == 1 {
1102            return self.manifest.segments.len();
1103        }
1104        self.manifest.levels.get(level).map_or(0, Vec::len)
1105    }
1106
1107    /// Anzahl der L1-Segmente (für Tests/Inspektion).
1108    pub fn segment_count(&self) -> usize {
1109        self.manifest.segments.len()
1110    }
1111
1112    /// Segment-Metadaten (für Tests/Inspektion der Disjunktheits-Invariante).
1113    pub fn segments(&self) -> &[SegmentMeta] {
1114        &self.manifest.segments
1115    }
1116
1117    /// Alle Tabellen-IDs, die aktuell im Manifest referenziert werden (für
1118    /// Tests/Inspektion: prüft, dass keine Referenz auf fehlende Dateien besteht).
1119    pub fn table_ids(&self) -> Vec<u64> {
1120        self.manifest.all_ids()
1121    }
1122
1123    /// Sauber schließen: MemTable flushen, WAL + Manifest dauerhaft machen.
1124    ///
1125    /// Das ist der primäre Durability-Mechanismus für einen sauberen Shutdown.
1126    /// Rufe `close()` bewusst auf, statt dich auf `drop(db)` zu verlassen.
1127    pub fn close(&mut self) -> Result<()> {
1128        if self.closed {
1129            return Ok(());
1130        }
1131        self.flush()?;
1132        self.wal.sync()?;
1133        self.manifest.save(&self.manifest_path)?;
1134        self.closed = true;
1135        Ok(())
1136    }
1137}
1138
1139/// Best-Effort-Fallback: Flusht beim Verwerfen, wenn `close()` nicht explizit
1140/// gerufen wurde. Fehler werden ignoriert — `close()` ist die zuverlässige API.
1141/// Prüft, ob ein Verzeichnis existiert und keine Einträge enthält.
1142fn dir_is_empty(path: &Path) -> Result<bool> {
1143    let mut it = std::fs::read_dir(path)?;
1144    Ok(it.next().is_none())
1145}
1146
1147/// Hilfsfunktion: Bytes als Kleinbuchstaben Hex (für inspect-Ausgabe).
1148fn hex_encode(bytes: &[u8]) -> String {
1149    const HEX: &[u8; 16] = b"0123456789abcdef";
1150    let mut s = String::with_capacity(bytes.len() * 2);
1151    for &b in bytes {
1152        s.push(HEX[(b >> 4) as usize] as char);
1153        s.push(HEX[(b & 0x0f) as usize] as char);
1154    }
1155    s
1156}
1157
1158impl Drop for Database {
1159    fn drop(&mut self) {
1160        if !self.closed {
1161            // Best-Effort: nicht als Durability-Garantie betrachten.
1162            let _ = self.flush();
1163            let _ = self.wal.sync();
1164        }
1165    }
1166}
1167
1168/// Abstraktion über eine KV-Sicht für Reads + Writes. Einerseits die direkte
1169/// (committete) Engine (`DirectMutator`), andererseits eine Transaktions-Sicht
1170/// mit Pending-Overlay (`TxMutator`). So teilen sich nicht-transaktionale und
1171/// transaktionale Pfade dieselbe Entity-/Index-Logik.
1172pub trait Mutator {
1173    /// Punkt-Lookup. `None` = nicht vorhanden oder gelöscht.
1174    fn get(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>>;
1175    /// Bereichs-Scan `[start, end)`, sortiert, **lazy** (streamt die Quellen,
1176    /// materialisiert nicht die Datenmenge).
1177    fn scan<'s>(&'s mut self, start: Option<&[u8]>, end: Option<&[u8]>) -> Result<ScanStream<'s>>;
1178    /// Schreibt (bzw. überschreibt) einen Key.
1179    fn put(&mut self, key: &[u8], value: &[u8]) -> Result<()>;
1180    /// Löscht einen Key (Tombstone).
1181    fn delete(&mut self, key: &[u8]) -> Result<()>;
1182}
1183
1184/// Sortierter, lazy Scan-Stream über eine Mutator-Sicht.
1185pub type ScanStream<'s> = Box<dyn Iterator<Item = Result<(Vec<u8>, Option<Vec<u8>>)>> + 's>;
1186
1187/// Mutator direkt auf der committeten Engine (nicht-transaktionaler Pfad).
1188pub struct DirectMutator<'a> {
1189    pub db: &'a mut Database,
1190}
1191
1192impl<'a> Mutator for DirectMutator<'a> {
1193    fn get(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>> {
1194        let r = self.db.get(key);
1195        r
1196    }
1197    fn scan<'s>(&'s mut self, start: Option<&[u8]>, end: Option<&[u8]>) -> Result<ScanStream<'s>> {
1198        Ok(Box::new(self.db.scan_stream(start, end)?))
1199    }
1200    fn put(&mut self, key: &[u8], value: &[u8]) -> Result<()> {
1201        self.db.put(key, value)
1202    }
1203    fn delete(&mut self, key: &[u8]) -> Result<()> {
1204        self.db.delete(key)
1205    }
1206}
1207
1208#[cfg(test)]
1209mod tests {
1210    use super::*;
1211    use std::collections::BTreeMap;
1212
1213    /// Eager-Referenz: newest-wins-Merge über MemTable + alle Tabellen
1214    /// (gleiche Quellen-Reihenfolge wie `scan_stream`).
1215    fn model_scan(
1216        db: &Database,
1217        start: Option<&[u8]>,
1218        end: Option<&[u8]>,
1219    ) -> Vec<(Vec<u8>, Option<Vec<u8>>)> {
1220        let in_range = |k: &[u8]| start.is_none_or(|s| k >= s) && end.is_none_or(|e| k < e);
1221        let mut order: Vec<Vec<(Vec<u8>, Option<Vec<u8>>)>> = Vec::new();
1222        order.push(
1223            db.memtable
1224                .iter()
1225                .map(|(k, v)| (k.to_vec(), v.clone()))
1226                .collect(),
1227        );
1228        for level in &db.manifest.levels {
1229            for id in level.iter().rev() {
1230                if let Ok(mut r) = sstable::TableReader::open(&db.table_path(*id)) {
1231                    if let Ok(recs) = r.iter() {
1232                        order.push(recs);
1233                    }
1234                }
1235            }
1236        }
1237        for seg in &db.manifest.segments {
1238            if let Ok(mut r) = sstable::TableReader::open(&db.table_path(seg.file_id)) {
1239                if let Ok(recs) = r.iter() {
1240                    order.push(recs);
1241                }
1242            }
1243        }
1244        // order[0] ist die neueste Quelle → erster Insert pro Key gewinnt.
1245        let mut best: BTreeMap<Vec<u8>, Option<Vec<u8>>> = BTreeMap::new();
1246        for src in order {
1247            for (k, v) in src {
1248                if in_range(&k) {
1249                    best.entry(k).or_insert(v);
1250                }
1251            }
1252        }
1253        // `scan()` gibt keine Tombstones aus (gelöschte Keys erscheinen nicht).
1254        best.into_iter().filter(|(_, v)| v.is_some()).collect()
1255    }
1256
1257    fn setup(dir: &Path) -> Database {
1258        let mut db = Database::open(dir).unwrap();
1259        db.put(b"a", b"new").unwrap();
1260        db.put(b"b", b"tomb-mem").unwrap();
1261        db.put(b"c", b"1").unwrap();
1262        db.flush().unwrap(); // Tabelle 1
1263        db.delete(b"b").unwrap(); // Tombstone in MemTable schattiert altes b
1264        db.put(b"d", b"2").unwrap();
1265        db.put(b"z", b"znew").unwrap();
1266        db.flush().unwrap(); // Tabelle 2
1267        db.put(b"a", b"newer").unwrap();
1268        db.delete(b"c").unwrap();
1269        db.put(b"e", b"5").unwrap();
1270        db.put(b"\x00", b"low").unwrap();
1271        db
1272    }
1273
1274    #[test]
1275    fn lazy_equals_eager() {
1276        let dir = tempfile::tempdir().unwrap();
1277        let mut db = setup(dir.path());
1278        let ranges: Vec<(Option<&[u8]>, Option<&[u8]>)> = vec![
1279            (None, None),
1280            (Some(b"b"), None),
1281            (None, Some(b"d")),
1282            (Some(b"a"), Some(b"z")),
1283            (Some(b"cc"), Some(b"dd")), // mitten im Block / leere Mitte
1284            (Some(b"\xff"), None),      // größer als alle vorhandenen
1285            (Some(b""), Some(b"\x00")), // end == start → leer
1286        ];
1287        for (s, e) in ranges {
1288            let expected = model_scan(&db, s, e);
1289            let actual = db.scan(s, e).unwrap();
1290            assert_eq!(actual, expected, "range {s:?}..{e:?}");
1291        }
1292    }
1293
1294    #[test]
1295    fn scan_reuses_cached_table_readers() {
1296        // Regression: scan_stream muss gecachte Reader wiederverwenden statt
1297        // pro Scan jede Datei neu zu öffnen. Nach dem ersten Scan ist der Cache
1298        // befüllt; weitere Scans dürfen die Cache-Größe nicht mehr wachsen lassen.
1299        let dir = tempfile::tempdir().unwrap();
1300        let mut db = setup(dir.path()); // erzeugt 2 SSTables via flush
1301        assert!(db.table_cache.is_empty(), "cache startet leer");
1302        let expected: Vec<(Vec<u8>, Option<Vec<u8>>)> = db.scan(None, None).unwrap();
1303        let n = db.table_cache.len();
1304        assert!(
1305            n > 0 && n == db.table_count(),
1306            "cache befüllt mit allen Tabellen ({n} vs {})",
1307            db.table_count()
1308        );
1309        for _ in 0..3 {
1310            let again = db.scan(None, None).unwrap();
1311            assert_eq!(again, expected, "Ergebnis stabil über Scans");
1312            assert_eq!(db.table_cache.len(), n, "keine neuen Reader nach 1. Scan");
1313        }
1314    }
1315
1316    #[test]
1317    fn lazy_streams_consistently_under_borrow() {
1318        let dir = tempfile::tempdir().unwrap();
1319        let mut db = setup(dir.path());
1320        let mut stream = db.scan_stream(None, None).unwrap();
1321        let first = stream.next().unwrap().unwrap();
1322        // Der exklusive Borrow ist aktiv: weitere &mut-Zugriffe sind unmöglich.
1323        assert_eq!(first.0, b"\x00".to_vec());
1324        let rest: std::result::Result<Vec<_>, _> = stream.collect();
1325        assert!(!rest.unwrap().is_empty());
1326    }
1327}