1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// SPDX-License-Identifier: Apache-2.0
// Copyright (c) 2026-present, Dmitry Prudnikov
//! Caller-defined key domains that table outputs never span.
use crate::UserKey;
/// Splits the key space into domains that no new table spans.
///
/// A domain is a contiguous interval in the tree's comparator order. Flush,
/// ingest and compaction end an output before the first key of the next
/// domain, even below its target size.
///
/// A domain is an application's unit of lifetime, such as one retention
/// epoch of time-bucketed keys. With the keys of each domain in tables of
/// their own, expiring a domain removes whole tables instead of rewriting the
/// survivors that would otherwise share them.
///
/// Whether a table holds one domain follows from its key range alone, since
/// a domain is an interval: no marker is written, and a table written before
/// the policy, or under another one, is judged by the same test.
///
/// # Example
///
/// ```
/// use lsm_tree::{KeyDomains, UserKey};
///
/// /// One domain per value of the first byte.
/// struct FirstByte;
///
/// impl KeyDomains for FirstByte {
/// fn domain_end(&self, key: &[u8]) -> Option<UserKey> {
/// match key.first() {
/// Some(&b) if b < u8::MAX => Some(UserKey::from([b + 1].as_slice())),
/// _ => None,
/// }
/// }
/// }
///
/// assert_eq!(FirstByte.domain_end(b"a1").as_deref(), Some(b"b".as_slice()));
/// assert_eq!(FirstByte.domain_end(b"\xff"), None);
/// ```
pub trait KeyDomains: Send + Sync + core::panic::UnwindSafe + core::panic::RefUnwindSafe {
/// The first key past the domain that holds `key`, or `None` when that
/// domain runs to the end of the key space.
///
/// Every key from `key` up to the returned one (exclusive), in the tree's
/// comparator order, lies in `key`'s domain, and no key at or past it
/// does. The answer for any key of one domain is the same.
fn domain_end(&self, key: &[u8]) -> Option<UserKey>;
}
/// Where the domain of the output a writer is filling ends.
enum DomainEnd {
/// The output has no key yet.
Unknown,
/// The domain runs to the end of the key space.
Open,
/// The first key of the next domain.
At(UserKey),
}
/// The domain of the output a writer is filling, so it ends that output
/// before a key of the next one.
pub struct DomainCursor {
domains: alloc::sync::Arc<dyn KeyDomains>,
end: DomainEnd,
}
impl DomainCursor {
pub fn new(domains: alloc::sync::Arc<dyn KeyDomains>) -> Self {
Self {
domains,
end: DomainEnd::Unknown,
}
}
/// The end of the current output's domain when `key`, the next new key,
/// lies at or past it, without moving into `key`'s domain.
pub fn crosses(
&self,
key: &[u8],
comparator: &dyn crate::comparator::UserComparator,
) -> Option<&UserKey> {
match &self.end {
DomainEnd::At(end) if comparator.compare(key, end) != core::cmp::Ordering::Less => {
Some(end)
}
_ => None,
}
}
/// Whether `last`, a key past `first` taken in the same output, still lies
/// in `first`'s domain.
#[cfg(feature = "columnar")]
pub fn holds(
&self,
first: &[u8],
last: &[u8],
comparator: &dyn crate::comparator::UserComparator,
) -> bool {
self.domains
.domain_end(first)
.is_none_or(|end| comparator.compare(last, &end) == core::cmp::Ordering::Less)
}
/// The first key past the domain that holds `key` (see
/// [`KeyDomains::domain_end`]).
#[cfg(feature = "columnar")]
pub fn domain_end(&self, key: &[u8]) -> Option<UserKey> {
self.domains.domain_end(key)
}
/// The first key past the current output's domain, `None` while the
/// output has no key or when its domain runs to the end of the key space.
pub fn end(&self) -> Option<&UserKey> {
match &self.end {
DomainEnd::At(end) => Some(end),
DomainEnd::Unknown | DomainEnd::Open => None,
}
}
/// Takes `key` into the current output: its domain becomes the output's
/// when the output starts there or `key` crossed into another one.
pub fn enter(&mut self, key: &[u8], crossed: bool) {
if crossed || matches!(self.end, DomainEnd::Unknown) {
self.end = self
.domains
.domain_end(key)
.map_or(DomainEnd::Open, DomainEnd::At);
}
}
}
#[cfg(test)]
mod tests;