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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
//! Memtable hardening edge-case tests — Priority 3.
//!
//! These tests exercise unusual recovery paths and memtable state
//! combinations that are not covered by the standard basic / edge-case
//! suites: WAL replay with only range-deletes, replay of interleaved
//! point and range tombstones, and size accounting corner cases.
//!
//! ## See also
//! - [`tests_basic`] — standard put/get/delete/scan/recovery
//! - [`tests_edge_cases`] — empty-key rejects, overflow, concurrent
#[cfg(test)]
mod tests {
use crate::memtable::{Memtable, MemtableGetResult};
use tempfile::TempDir;
use tracing::Level;
use tracing_subscriber::fmt::Subscriber;
fn init_tracing() {
let _ = Subscriber::builder()
.with_max_level(Level::TRACE)
.try_init();
}
// Large write-buffer to avoid FlushRequired.
const WRITE_BUFFER: usize = 64 * 1024;
// ================================================================
// 1. WAL with only range-deletes recovers correctly
// ================================================================
/// # Scenario
/// A freshly opened memtable receives only `delete_range` calls
/// (no puts or point deletes). After closing and re-opening from the
/// same WAL, the range tombstones must be present and the point tree
/// must remain empty.
///
/// # Expected behavior
/// - `get()` for any key in the range returns `RangeDelete`.
/// - `get()` for a key outside the range returns `NotFound`.
#[test]
fn wal_only_range_deletes_recovered() {
init_tracing();
let tmp = TempDir::new().unwrap();
let wal_path = tmp.path().join("000000.log");
// Phase 1 — write range tombstones only.
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
mt.delete_range(b"a".to_vec(), b"d".to_vec()).unwrap();
mt.delete_range(b"m".to_vec(), b"p".to_vec()).unwrap();
}
// Phase 2 — reopen and verify.
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
// Inside first range.
assert_eq!(mt.get(b"b").unwrap(), MemtableGetResult::RangeDelete);
assert_eq!(mt.get(b"c").unwrap(), MemtableGetResult::RangeDelete);
// Inside second range.
assert_eq!(mt.get(b"n").unwrap(), MemtableGetResult::RangeDelete);
// Outside ranges.
assert_eq!(mt.get(b"e").unwrap(), MemtableGetResult::NotFound);
assert_eq!(mt.get(b"z").unwrap(), MemtableGetResult::NotFound);
}
}
// ================================================================
// 2. WAL replay preserves interleaved point-delete + range-delete
// ================================================================
/// # Scenario
/// A memtable receives interleaved puts, point-deletes, and range-
/// deletes. After re-opening from the same WAL, the final visibility
/// of each key must match the pre-close state.
///
/// # Expected behavior
/// WAL replay reproduces exact same get() results.
#[test]
fn wal_interleaved_point_and_range_deletes_recovered() {
init_tracing();
let tmp = TempDir::new().unwrap();
let wal_path = tmp.path().join("000000.log");
// Phase 1 — mixed writes.
let expected: Vec<(&[u8], MemtableGetResult)>;
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
mt.put(b"a".to_vec(), b"v_a".to_vec()).unwrap();
mt.put(b"b".to_vec(), b"v_b".to_vec()).unwrap();
mt.put(b"c".to_vec(), b"v_c".to_vec()).unwrap();
mt.put(b"d".to_vec(), b"v_d".to_vec()).unwrap();
// Point-delete "b".
mt.delete(b"b".to_vec()).unwrap();
// Range-delete [c, e) — covers "c" and "d".
mt.delete_range(b"c".to_vec(), b"e".to_vec()).unwrap();
expected = vec![
(b"a", mt.get(b"a").unwrap()),
(b"b", mt.get(b"b").unwrap()),
(b"c", mt.get(b"c").unwrap()),
(b"d", mt.get(b"d").unwrap()),
(b"e", mt.get(b"e").unwrap()),
];
}
// Phase 2 — reopen and verify.
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
for (key, exp) in &expected {
assert_eq!(
&mt.get(key).unwrap(),
exp,
"mismatch for key {:?}",
String::from_utf8_lossy(key)
);
}
}
}
// ================================================================
// 3. put → range-delete → put (resurrect) survives WAL replay
// ================================================================
/// # Scenario
/// A key is put, deleted by a range tombstone, then put again
/// (resurrected). After WAL replay, the final put should be visible
/// because its LSN is higher than the range tombstone.
///
/// # Expected behavior
/// `get("key")` returns the resurrected value after replay.
#[test]
fn wal_resurrect_after_range_delete_recovered() {
init_tracing();
let tmp = TempDir::new().unwrap();
let wal_path = tmp.path().join("000000.log");
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
mt.put(b"key".to_vec(), b"first".to_vec()).unwrap();
mt.delete_range(b"k".to_vec(), b"l".to_vec()).unwrap();
mt.put(b"key".to_vec(), b"resurrected".to_vec()).unwrap();
// Pre-close sanity check.
assert_eq!(
mt.get(b"key").unwrap(),
MemtableGetResult::Put(b"resurrected".to_vec())
);
}
// Reopen.
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
assert_eq!(
mt.get(b"key").unwrap(),
MemtableGetResult::Put(b"resurrected".to_vec())
);
}
}
// ================================================================
// 4. Multiple overlapping range tombstones via WAL replay
// ================================================================
/// # Scenario
/// Two overlapping range tombstones `[a, d)` and `[c, f)` are issued.
/// After replay, keys within the union `[a, f)` are deleted, while
/// keys outside remain visible (or NotFound if never written).
///
/// # Expected behavior
/// The union of both tombstones covers the full `[a, f)` range.
#[test]
fn wal_overlapping_range_tombstones_recovered() {
init_tracing();
let tmp = TempDir::new().unwrap();
let wal_path = tmp.path().join("000000.log");
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
// Put keys across the range.
for k in &[b"a", b"b", b"c", b"d", b"e", b"f", b"g"] {
mt.put(k.to_vec(), b"v".to_vec()).unwrap();
}
// Two overlapping range deletes.
mt.delete_range(b"a".to_vec(), b"d".to_vec()).unwrap();
mt.delete_range(b"c".to_vec(), b"f".to_vec()).unwrap();
}
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
// a, b, c, d, e — deleted (covered by union).
assert_eq!(mt.get(b"a").unwrap(), MemtableGetResult::RangeDelete);
assert_eq!(mt.get(b"b").unwrap(), MemtableGetResult::RangeDelete);
assert_eq!(mt.get(b"c").unwrap(), MemtableGetResult::RangeDelete);
assert_eq!(mt.get(b"d").unwrap(), MemtableGetResult::RangeDelete);
assert_eq!(mt.get(b"e").unwrap(), MemtableGetResult::RangeDelete);
// f, g — visible (outside both ranges).
assert_eq!(mt.get(b"f").unwrap(), MemtableGetResult::Put(b"v".to_vec()));
assert_eq!(mt.get(b"g").unwrap(), MemtableGetResult::Put(b"v".to_vec()));
}
}
// ================================================================
// 5. LSN counter is restored correctly after WAL replay
// ================================================================
/// # Scenario
/// After replaying a WAL with N operations, subsequent writes should
/// receive LSNs greater than any replayed LSN. This prevents stale
/// LSN assignment after crash recovery.
///
/// # Expected behavior
/// New writes after replay have LSNs > max replayed LSN.
#[test]
fn wal_lsn_counter_resumed_after_replay() {
init_tracing();
let tmp = TempDir::new().unwrap();
let wal_path = tmp.path().join("000000.log");
// Phase 1 — issue 5 operations (LSNs 0..4).
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
for i in 0..5u32 {
mt.put(format!("k{i}").into_bytes(), format!("v{i}").into_bytes())
.unwrap();
}
}
// Phase 2 — reopen and issue new write.
{
let mt = Memtable::new(&wal_path, None, WRITE_BUFFER).unwrap();
mt.put(b"new_key".to_vec(), b"new_val".to_vec()).unwrap();
// Read back and verify the new key is visible (implying its LSN
// is valid and higher than replayed entries, so it won't be
// shadowed by any old tombstone).
assert_eq!(
mt.get(b"new_key").unwrap(),
MemtableGetResult::Put(b"new_val".to_vec())
);
// Verify all old keys are still visible.
for i in 0..5u32 {
assert_eq!(
mt.get(format!("k{i}").as_bytes()).unwrap(),
MemtableGetResult::Put(format!("v{i}").into_bytes())
);
}
}
}
}