1#![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
75pub const DEFAULT_MEMTABLE_LIMIT: usize = 4 * 1024 * 1024;
77pub const DEFAULT_L0_COMPACT_THRESHOLD: usize = 4;
79pub const DEFAULT_SEGMENT_MAX_RECORDS: usize = 30_000;
83
84#[derive(Clone)]
86pub struct Options {
87 pub memtable_limit: usize,
88 pub l0_compact_threshold: usize,
89 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
104pub 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 table_cache: HashMap<u64, sstable::TableReader>,
120 next_tx_id: u64,
122 format_version: u32,
125}
126
127#[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#[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#[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#[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 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 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 version::write_version(&dir, version::FORMAT_VERSION)?;
188 version::FORMAT_VERSION
189 } else {
190 1
193 }
194 }
195 Err(e) => return Err(e),
196 };
197
198 let manifest = Manifest::load(&manifest_path)?;
199 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 db.convert_legacy_l1()?;
224 db.validate_open_state()?;
225
226 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 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 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 pub fn delete(&mut self, key: &[u8]) -> Result<()> {
317 self.put_internal(key, None)
318 }
319
320 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 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 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 pub(crate) fn wal_begin(&mut self, tx: u64) -> Result<()> {
351 self.wal.append_begin(tx)
352 }
353
354 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 pub(crate) fn wal_tx_delete(&mut self, tx: u64, key: &[u8]) -> Result<()> {
361 self.wal.append_tx_delete(tx, key)
362 }
363
364 pub(crate) fn wal_commit(&mut self, tx: u64) -> Result<()> {
366 self.wal.append_commit(tx)
367 }
368
369 pub(crate) fn wal_sync(&mut self) -> Result<()> {
371 self.wal.sync()
372 }
373
374 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 pub(crate) fn mem_delete(&mut self, key: &[u8]) {
383 self.memtable.put(key.to_vec(), None);
384 }
385
386 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 pub fn get(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>> {
402 if let Some(entry) = self.memtable.get(key) {
404 return Ok(entry.clone());
405 }
406 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 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 if let Some(entry) = hit {
422 return Ok(entry);
423 }
424 }
425 }
426 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 fn find_segment(&self, key: &[u8]) -> Option<usize> {
448 let segs = &self.manifest.segments;
449 if segs.is_empty() {
450 return None;
451 }
452 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 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 sources.push(Box::new(memtable_source(&self.memtable, start, end)));
486 if let Some(ids) = self.manifest.levels.first() {
488 for id in ids.iter().rev() {
489 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 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 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 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(); self.wal.truncate()?;
567 self.memtable = MemTable::new();
568
569 if self.manifest.levels[0].len() >= self.opts.l0_compact_threshold {
571 self.compact()?;
572 }
573 Ok(())
574 }
575
576 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 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 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 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 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 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(); 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 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 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 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; }
701 std::fs::remove_file(&path)?;
702 removed += 1;
703 }
704
705 let tmp = self.manifest_path.with_extension("manifest.tmp");
708 if tmp.exists() {
709 let _ = std::fs::remove_file(&tmp);
710 }
711
712 self.table_cache.retain(|id, _| referenced.contains(id));
714
715 Ok(removed)
716 }
717
718 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 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 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 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 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 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 pub fn format_version(&self) -> u32 {
798 self.format_version
799 }
800
801 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 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 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 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 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 pub fn compact_full(&mut self) -> Result<usize> {
897 self.flush()?;
899
900 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 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 let mut old_ids: Vec<u64> = l0;
926 old_ids.extend(old_segment_ids);
927
928 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 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 pub fn backup(&mut self, dest: &Path) -> Result<usize> {
961 self.flush()?;
963
964 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 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 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 pub fn restore(src: &Path, dest: &Path) -> Result<usize> {
1028 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 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 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 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 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 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 pub fn segment_count(&self) -> usize {
1109 self.manifest.segments.len()
1110 }
1111
1112 pub fn segments(&self) -> &[SegmentMeta] {
1114 &self.manifest.segments
1115 }
1116
1117 pub fn table_ids(&self) -> Vec<u64> {
1120 self.manifest.all_ids()
1121 }
1122
1123 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
1139fn dir_is_empty(path: &Path) -> Result<bool> {
1143 let mut it = std::fs::read_dir(path)?;
1144 Ok(it.next().is_none())
1145}
1146
1147fn 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 let _ = self.flush();
1163 let _ = self.wal.sync();
1164 }
1165 }
1166}
1167
1168pub trait Mutator {
1173 fn get(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>>;
1175 fn scan<'s>(&'s mut self, start: Option<&[u8]>, end: Option<&[u8]>) -> Result<ScanStream<'s>>;
1178 fn put(&mut self, key: &[u8], value: &[u8]) -> Result<()>;
1180 fn delete(&mut self, key: &[u8]) -> Result<()>;
1182}
1183
1184pub type ScanStream<'s> = Box<dyn Iterator<Item = Result<(Vec<u8>, Option<Vec<u8>>)>> + 's>;
1186
1187pub 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 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 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 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(); db.delete(b"b").unwrap(); db.put(b"d", b"2").unwrap();
1265 db.put(b"z", b"znew").unwrap();
1266 db.flush().unwrap(); 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")), (Some(b"\xff"), None), (Some(b""), Some(b"\x00")), ];
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 let dir = tempfile::tempdir().unwrap();
1300 let mut db = setup(dir.path()); 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 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}