Line data Source code
1 : //!
2 : //! Simple on-disk B-tree implementation
3 : //!
4 : //! This is used as the index structure within image and delta layers
5 : //!
6 : //! Features:
7 : //! - Fixed-width keys
8 : //! - Fixed-width values (VALUE_SZ)
9 : //! - The tree is created in a bulk operation. Insert/deletion after creation
10 : //! is not supported
11 : //! - page-oriented
12 : //!
13 : //! TODO:
14 : //! - maybe something like an Adaptive Radix Tree would be more efficient?
15 : //! - the values stored by image and delta layers are offsets into the file,
16 : //! and they are in monotonically increasing order. Prefix compression would
17 : //! be very useful for them, too.
18 : //! - An Iterator interface would be more convenient for the callers than the
19 : //! 'visit' function
20 : //!
21 : use std::cmp::Ordering;
22 : use std::iter::Rev;
23 : use std::ops::{Range, RangeInclusive};
24 : use std::{io, result};
25 :
26 : use async_stream::try_stream;
27 : use byteorder::{BE, ReadBytesExt};
28 : use bytes::{BufMut, Bytes, BytesMut};
29 : use either::Either;
30 : use futures::{Stream, StreamExt};
31 : use hex;
32 : use thiserror::Error;
33 : use tracing::error;
34 :
35 : use crate::context::{DownloadBehavior, RequestContext};
36 : use crate::task_mgr::TaskKind;
37 : use crate::tenant::block_io::{BlockReader, BlockWriter};
38 :
39 : // The maximum size of a value stored in the B-tree. 5 bytes is enough currently.
40 : pub const VALUE_SZ: usize = 5;
41 : pub const MAX_VALUE: u64 = 0x007f_ffff_ffff;
42 :
43 : pub const PAGE_SZ: usize = 8192;
44 :
45 : #[derive(Clone, Copy, Debug)]
46 : struct Value([u8; VALUE_SZ]);
47 :
48 : impl Value {
49 14122159 : fn from_slice(slice: &[u8]) -> Value {
50 14122159 : let mut b = [0u8; VALUE_SZ];
51 14122159 : b.copy_from_slice(slice);
52 14122159 : Value(b)
53 14122159 : }
54 :
55 14438590 : fn from_u64(x: u64) -> Value {
56 14438590 : assert!(x <= 0x007f_ffff_ffff);
57 14438590 : Value([
58 14438590 : (x >> 32) as u8,
59 14438590 : (x >> 24) as u8,
60 14438590 : (x >> 16) as u8,
61 14438590 : (x >> 8) as u8,
62 14438590 : x as u8,
63 14438590 : ])
64 14438590 : }
65 :
66 25761 : fn from_blknum(x: u32) -> Value {
67 25761 : Value([
68 25761 : 0x80,
69 25761 : (x >> 24) as u8,
70 25761 : (x >> 16) as u8,
71 25761 : (x >> 8) as u8,
72 25761 : x as u8,
73 25761 : ])
74 25761 : }
75 :
76 : #[allow(dead_code)]
77 0 : fn is_offset(self) -> bool {
78 0 : self.0[0] & 0x80 != 0
79 0 : }
80 :
81 12860275 : fn to_u64(self) -> u64 {
82 12860275 : let b = &self.0;
83 12860275 : ((b[0] as u64) << 32)
84 12860275 : | ((b[1] as u64) << 24)
85 12860275 : | ((b[2] as u64) << 16)
86 12860275 : | ((b[3] as u64) << 8)
87 12860275 : | b[4] as u64
88 12860275 : }
89 :
90 1249836 : fn to_blknum(self) -> u32 {
91 1249836 : let b = &self.0;
92 1249836 : assert!(b[0] == 0x80);
93 1249836 : ((b[1] as u32) << 24) | ((b[2] as u32) << 16) | ((b[3] as u32) << 8) | b[4] as u32
94 1249836 : }
95 : }
96 :
97 : #[derive(Error, Debug)]
98 : pub enum DiskBtreeError {
99 : #[error("Attempt to append a value that is too large {0} > {}", MAX_VALUE)]
100 : AppendOverflow(u64),
101 :
102 : #[error("Unsorted input: key {key:?} is <= last_key {last_key:?}")]
103 : UnsortedInput { key: Box<[u8]>, last_key: Box<[u8]> },
104 :
105 : #[error("Could not push to new leaf node")]
106 : FailedToPushToNewLeafNode,
107 :
108 : #[error("IoError: {0}")]
109 : Io(#[from] io::Error),
110 : }
111 :
112 : pub type Result<T> = result::Result<T, DiskBtreeError>;
113 :
114 : /// This is the on-disk representation.
115 : struct OnDiskNode<'a, const L: usize> {
116 : // Fixed-width fields
117 : num_children: u16,
118 : level: u8,
119 : prefix_len: u8,
120 : suffix_len: u8,
121 :
122 : // Variable-length fields. These are stored on-disk after the fixed-width
123 : // fields, in this order. In the in-memory representation, these point to
124 : // the right parts in the page buffer.
125 : prefix: &'a [u8],
126 : keys: &'a [u8],
127 : values: &'a [u8],
128 : }
129 :
130 : impl<const L: usize> OnDiskNode<'_, L> {
131 : ///
132 : /// Interpret a PAGE_SZ page as a node.
133 : ///
134 3002178 : fn deparse(buf: &[u8]) -> Result<OnDiskNode<L>> {
135 3002178 : let mut cursor = std::io::Cursor::new(buf);
136 3002178 : let num_children = cursor.read_u16::<BE>()?;
137 3002178 : let level = cursor.read_u8()?;
138 3002178 : let prefix_len = cursor.read_u8()?;
139 3002178 : let suffix_len = cursor.read_u8()?;
140 :
141 3002178 : let mut off = cursor.position();
142 3002178 : let prefix_off = off as usize;
143 3002178 : off += prefix_len as u64;
144 3002178 :
145 3002178 : let keys_off = off as usize;
146 3002178 : let keys_len = num_children as usize * suffix_len as usize;
147 3002178 : off += keys_len as u64;
148 3002178 :
149 3002178 : let values_off = off as usize;
150 3002178 : let values_len = num_children as usize * VALUE_SZ;
151 3002178 : //off += values_len as u64;
152 3002178 :
153 3002178 : let prefix = &buf[prefix_off..prefix_off + prefix_len as usize];
154 3002178 : let keys = &buf[keys_off..keys_off + keys_len];
155 3002178 : let values = &buf[values_off..values_off + values_len];
156 3002178 :
157 3002178 : Ok(OnDiskNode {
158 3002178 : num_children,
159 3002178 : level,
160 3002178 : prefix_len,
161 3002178 : suffix_len,
162 3002178 : prefix,
163 3002178 : keys,
164 3002178 : values,
165 3002178 : })
166 3002178 : }
167 :
168 : ///
169 : /// Read a value at 'idx'
170 : ///
171 14122159 : fn value(&self, idx: usize) -> Value {
172 14122159 : let value_off = idx * VALUE_SZ;
173 14122159 : let value_slice = &self.values[value_off..value_off + VALUE_SZ];
174 14122159 : Value::from_slice(value_slice)
175 14122159 : }
176 :
177 2554382 : fn binary_search(
178 2554382 : &self,
179 2554382 : search_key: &[u8; L],
180 2554382 : keybuf: &mut [u8],
181 2554382 : ) -> result::Result<usize, usize> {
182 2554382 : let mut size = self.num_children as usize;
183 2554382 : let mut low = 0;
184 2554382 : let mut high = size;
185 19223080 : while low < high {
186 17125530 : let mid = low + size / 2;
187 17125530 :
188 17125530 : let key_off = mid * self.suffix_len as usize;
189 17125530 : let suffix = &self.keys[key_off..key_off + self.suffix_len as usize];
190 17125530 : // Does this match?
191 17125530 : keybuf[self.prefix_len as usize..].copy_from_slice(suffix);
192 17125530 :
193 17125530 : let cmp = keybuf[..].cmp(search_key);
194 17125530 :
195 17125530 : if cmp == Ordering::Less {
196 10846368 : low = mid + 1;
197 10846368 : } else if cmp == Ordering::Greater {
198 5822330 : high = mid;
199 5822330 : } else {
200 456832 : return Ok(mid);
201 : }
202 16668698 : size = high - low;
203 : }
204 2097550 : Err(low)
205 2554382 : }
206 : }
207 :
208 : ///
209 : /// Public reader object, to search the tree.
210 : ///
211 : #[derive(Clone)]
212 : pub struct DiskBtreeReader<R, const L: usize>
213 : where
214 : R: BlockReader,
215 : {
216 : start_blk: u32,
217 : root_blk: u32,
218 : reader: R,
219 : }
220 :
221 : #[derive(Clone, Copy, Debug, PartialEq, Eq)]
222 : pub enum VisitDirection {
223 : Forwards,
224 : Backwards,
225 : }
226 :
227 : impl<R, const L: usize> DiskBtreeReader<R, L>
228 : where
229 : R: BlockReader,
230 : {
231 481550 : pub fn new(start_blk: u32, root_blk: u32, reader: R) -> Self {
232 481550 : DiskBtreeReader {
233 481550 : start_blk,
234 481550 : root_blk,
235 481550 : reader,
236 481550 : }
237 481550 : }
238 :
239 : ///
240 : /// Read the value for given key. Returns the value, or None if it doesn't exist.
241 : ///
242 806436 : pub async fn get(&self, search_key: &[u8; L], ctx: &RequestContext) -> Result<Option<u64>> {
243 806436 : let mut result: Option<u64> = None;
244 806436 : self.visit(
245 806436 : search_key,
246 806436 : VisitDirection::Forwards,
247 806436 : |key, value| {
248 406388 : if key == search_key {
249 402376 : result = Some(value);
250 402376 : }
251 406388 : false
252 806436 : },
253 806436 : ctx,
254 806436 : )
255 806436 : .await?;
256 806436 : Ok(result)
257 806436 : }
258 :
259 1396 : pub fn iter<'a>(self, start_key: &'a [u8; L], ctx: &'a RequestContext) -> DiskBtreeIterator<'a>
260 1396 : where
261 1396 : R: 'a + Send,
262 1396 : {
263 1396 : DiskBtreeIterator {
264 1396 : stream: Box::pin(self.into_stream(start_key, ctx)),
265 1396 : }
266 1396 : }
267 :
268 : /// Return a stream which yields all key, value pairs from the index
269 : /// starting from the first key greater or equal to `start_key`.
270 : ///
271 : /// Note 1: that this is a copy of [`Self::visit`].
272 : /// TODO: Once the sequential read path is removed this will become
273 : /// the only index traversal method.
274 : ///
275 : /// Note 2: this function used to take `&self` but it now consumes `self`. This is due to
276 : /// the lifetime constraints of the reader and the stream / iterator it creates. Using `&self`
277 : /// requires the reader to be present when the stream is used, and this creates a lifetime
278 : /// dependency between the reader and the stream. Now if we want to create an iterator that
279 : /// holds the stream, someone will need to keep a reference to the reader, which is inconvenient
280 : /// to use from the image/delta layer APIs.
281 : ///
282 : /// Feel free to add the `&self` variant back if it's necessary.
283 481206 : pub fn into_stream<'a>(
284 481206 : self,
285 481206 : start_key: &'a [u8; L],
286 481206 : ctx: &'a RequestContext,
287 481206 : ) -> impl Stream<Item = std::result::Result<(Vec<u8>, u64), DiskBtreeError>> + 'a
288 481206 : where
289 481206 : R: 'a,
290 481206 : {
291 481206 : try_stream! {
292 481206 : let mut stack = Vec::new();
293 481206 : stack.push((self.root_blk, None));
294 481206 : let block_cursor = self.reader.block_cursor();
295 481206 : let mut node_buf = [0_u8; PAGE_SZ];
296 481206 : while let Some((node_blknum, opt_iter)) = stack.pop() {
297 481206 : // Read the node, through the PS PageCache, into local variable `node_buf`.
298 481206 : // We could keep the page cache read guard alive, but, at the time of writing,
299 481206 : // we run quite small PS PageCache s => can't risk running out of
300 481206 : // PageCache space because this stream isn't consumed fast enough.
301 481206 : let page_read_guard = block_cursor
302 481206 : .read_blk(self.start_blk + node_blknum, ctx)
303 481206 : .await?;
304 481206 : node_buf.copy_from_slice(page_read_guard.as_ref());
305 481206 : drop(page_read_guard); // drop page cache read guard early
306 481206 :
307 481206 : let node = OnDiskNode::deparse(&node_buf)?;
308 481206 : let prefix_len = node.prefix_len as usize;
309 481206 : let suffix_len = node.suffix_len as usize;
310 481206 :
311 481206 : assert!(node.num_children > 0);
312 481206 :
313 481206 : let mut keybuf = Vec::new();
314 481206 : keybuf.extend(node.prefix);
315 481206 : keybuf.resize(prefix_len + suffix_len, 0);
316 481206 :
317 481206 : let mut iter: Either<Range<usize>, Rev<RangeInclusive<usize>>> = if let Some(iter) = opt_iter {
318 481206 : iter
319 481206 : } else {
320 481206 : // Locate the first match
321 481206 : let idx = match node.binary_search(start_key, keybuf.as_mut_slice()) {
322 481206 : Ok(idx) => idx,
323 481206 : Err(idx) => {
324 481206 : if node.level == 0 {
325 481206 : // Imagine that the node contains the following keys:
326 481206 : //
327 481206 : // 1
328 481206 : // 3 <-- idx
329 481206 : // 5
330 481206 : //
331 481206 : // If the search key is '2' and there is exact match,
332 481206 : // the binary search would return the index of key
333 481206 : // '3'. That's cool, '3' is the first key to return.
334 481206 : idx
335 481206 : } else {
336 481206 : // This is an internal page, so each key represents a lower
337 481206 : // bound for what's in the child page. If there is no exact
338 481206 : // match, we have to return the *previous* entry.
339 481206 : //
340 481206 : // 1 <-- return this
341 481206 : // 3 <-- idx
342 481206 : // 5
343 481206 : idx.saturating_sub(1)
344 481206 : }
345 481206 : }
346 481206 : };
347 481206 : Either::Left(idx..node.num_children.into())
348 481206 : };
349 481206 :
350 481206 :
351 481206 : // idx points to the first match now. Keep going from there
352 481206 : while let Some(idx) = iter.next() {
353 481206 : let key_off = idx * suffix_len;
354 481206 : let suffix = &node.keys[key_off..key_off + suffix_len];
355 481206 : keybuf[prefix_len..].copy_from_slice(suffix);
356 481206 : let value = node.value(idx);
357 481206 : #[allow(clippy::collapsible_if)]
358 481206 : if node.level == 0 {
359 481206 : // leaf
360 481206 : yield (keybuf.clone(), value.to_u64());
361 481206 : } else {
362 481206 : stack.push((node_blknum, Some(iter)));
363 481206 : stack.push((value.to_blknum(), None));
364 481206 : break;
365 481206 : }
366 481206 : }
367 481206 : }
368 481206 : }
369 481206 : }
370 :
371 : ///
372 : /// Scan the tree, starting from 'search_key', in the given direction. 'visitor'
373 : /// will be called for every key >= 'search_key' (or <= 'search_key', if scanning
374 : /// backwards)
375 : ///
376 823356 : pub async fn visit<V>(
377 823356 : &self,
378 823356 : search_key: &[u8; L],
379 823356 : dir: VisitDirection,
380 823356 : mut visitor: V,
381 823356 : ctx: &RequestContext,
382 823356 : ) -> Result<bool>
383 823356 : where
384 823356 : V: FnMut(&[u8], u64) -> bool,
385 823356 : {
386 823356 : let mut stack = Vec::new();
387 823356 : stack.push((self.root_blk, None));
388 823356 : let block_cursor = self.reader.block_cursor();
389 2438364 : while let Some((node_blknum, opt_iter)) = stack.pop() {
390 : // Locate the node.
391 2037296 : let node_buf = block_cursor
392 2037296 : .read_blk(self.start_blk + node_blknum, ctx)
393 2037296 : .await?;
394 :
395 2037296 : let node = OnDiskNode::deparse(node_buf.as_ref())?;
396 2037296 : let prefix_len = node.prefix_len as usize;
397 2037296 : let suffix_len = node.suffix_len as usize;
398 2037296 :
399 2037296 : assert!(node.num_children > 0);
400 :
401 2037296 : let mut keybuf = Vec::new();
402 2037296 : keybuf.extend(node.prefix);
403 2037296 : keybuf.resize(prefix_len + suffix_len, 0);
404 :
405 2037296 : let mut iter = if let Some(iter) = opt_iter {
406 407796 : iter
407 1629500 : } else if dir == VisitDirection::Forwards {
408 : // Locate the first match
409 1621448 : let idx = match node.binary_search(search_key, keybuf.as_mut_slice()) {
410 406792 : Ok(idx) => idx,
411 1214656 : Err(idx) => {
412 1214656 : if node.level == 0 {
413 : // Imagine that the node contains the following keys:
414 : //
415 : // 1
416 : // 3 <-- idx
417 : // 5
418 : //
419 : // If the search key is '2' and there is exact match,
420 : // the binary search would return the index of key
421 : // '3'. That's cool, '3' is the first key to return.
422 416232 : idx
423 : } else {
424 : // This is an internal page, so each key represents a lower
425 : // bound for what's in the child page. If there is no exact
426 : // match, we have to return the *previous* entry.
427 : //
428 : // 1 <-- return this
429 : // 3 <-- idx
430 : // 5
431 798424 : idx.saturating_sub(1)
432 : }
433 : }
434 : };
435 1621448 : Either::Left(idx..node.num_children.into())
436 : } else {
437 8052 : let idx = match node.binary_search(search_key, keybuf.as_mut_slice()) {
438 4004 : Ok(idx) => {
439 4004 : // Exact match. That's the first entry to return, and walk
440 4004 : // backwards from there.
441 4004 : idx
442 : }
443 4048 : Err(idx) => {
444 : // No exact match. The binary search returned the index of the
445 : // first key that's > search_key. Back off by one, and walk
446 : // backwards from there.
447 4048 : if let Some(idx) = idx.checked_sub(1) {
448 4040 : idx
449 : } else {
450 8 : return Ok(false);
451 : }
452 : }
453 : };
454 8044 : Either::Right((0..=idx).rev())
455 : };
456 :
457 : // idx points to the first match now. Keep going from there
458 6325196 : while let Some(idx) = iter.next() {
459 5516332 : let key_off = idx * suffix_len;
460 5516332 : let suffix = &node.keys[key_off..key_off + suffix_len];
461 5516332 : keybuf[prefix_len..].copy_from_slice(suffix);
462 5516332 : let value = node.value(idx);
463 5516332 : #[allow(clippy::collapsible_if)]
464 5516332 : if node.level == 0 {
465 : // leaf
466 4710188 : if !visitor(&keybuf, value.to_u64()) {
467 422280 : return Ok(false);
468 4287908 : }
469 : } else {
470 806144 : stack.push((node_blknum, Some(iter)));
471 806144 : stack.push((value.to_blknum(), None));
472 806144 : break;
473 : }
474 : }
475 : }
476 401068 : Ok(true)
477 823356 : }
478 :
479 : #[allow(dead_code)]
480 20 : pub async fn dump(&self) -> Result<()> {
481 20 : let mut stack = Vec::new();
482 20 : let ctx = RequestContext::new(TaskKind::DebugTool, DownloadBehavior::Error);
483 20 :
484 20 : stack.push((self.root_blk, String::new(), 0, 0, 0));
485 20 :
486 20 : let block_cursor = self.reader.block_cursor();
487 :
488 12084 : while let Some((blknum, path, depth, child_idx, key_off)) = stack.pop() {
489 12064 : let blk = block_cursor.read_blk(self.start_blk + blknum, &ctx).await?;
490 12064 : let buf: &[u8] = blk.as_ref();
491 12064 : let node = OnDiskNode::<L>::deparse(buf)?;
492 :
493 12064 : if child_idx == 0 {
494 36 : print!("{:indent$}", "", indent = depth * 2);
495 36 : let path_prefix = stack
496 36 : .iter()
497 36 : .map(|(_blknum, path, ..)| path.as_str())
498 36 : .collect::<String>();
499 36 : println!(
500 36 : "blk #{blknum}: path {path_prefix}{path}: prefix {}, suffix_len {}",
501 36 : hex::encode(node.prefix),
502 36 : node.suffix_len
503 36 : );
504 12028 : }
505 :
506 12064 : if child_idx + 1 < node.num_children {
507 12028 : let key_off = key_off + node.suffix_len as usize;
508 12028 : stack.push((blknum, path.clone(), depth, child_idx + 1, key_off));
509 12028 : }
510 12064 : let key = &node.keys[key_off..key_off + node.suffix_len as usize];
511 12064 : let val = node.value(child_idx as usize);
512 12064 :
513 12064 : print!("{:indent$}", "", indent = depth * 2 + 2);
514 12064 : println!("{}: {}", hex::encode(key), hex::encode(val.0));
515 12064 :
516 12064 : if node.level > 0 {
517 16 : stack.push((val.to_blknum(), hex::encode(node.prefix), depth + 1, 0, 0));
518 12048 : }
519 : }
520 20 : Ok(())
521 20 : }
522 : }
523 :
524 : pub struct DiskBtreeIterator<'a> {
525 : #[allow(clippy::type_complexity)]
526 : stream: std::pin::Pin<
527 : Box<dyn Stream<Item = std::result::Result<(Vec<u8>, u64), DiskBtreeError>> + 'a + Send>,
528 : >,
529 : }
530 :
531 : impl DiskBtreeIterator<'_> {
532 4647664 : pub async fn next(&mut self) -> Option<std::result::Result<(Vec<u8>, u64), DiskBtreeError>> {
533 4647664 : self.stream.next().await
534 4647664 : }
535 : }
536 :
537 : ///
538 : /// Public builder object, for creating a new tree.
539 : ///
540 : /// Usage: Create a builder object by calling 'new', load all the data into the
541 : /// tree by calling 'append' for each key-value pair, and then call 'finish'
542 : ///
543 : /// 'L' is the key length in bytes
544 : pub struct DiskBtreeBuilder<W, const L: usize>
545 : where
546 : W: BlockWriter,
547 : {
548 : writer: W,
549 :
550 : ///
551 : /// `stack[0]` is the current root page, `stack.last()` is the leaf.
552 : ///
553 : /// We maintain the length of the stack to be always greater than zero.
554 : /// Two exceptions are:
555 : /// 1. `Self::flush_node`. The method will push the new node if it extracted the last one.
556 : /// So because other methods cannot see the intermediate state invariant still holds.
557 : /// 2. `Self::finish`. It consumes self and does not return it back,
558 : /// which means that this is where the structure is destroyed.
559 : /// Thus stack of zero length cannot be observed by other methods.
560 : stack: Vec<BuildNode<L>>,
561 :
562 : /// Last key that was appended to the tree. Used to sanity check that append
563 : /// is called in increasing key order.
564 : last_key: Option<[u8; L]>,
565 : }
566 :
567 : impl<W, const L: usize> DiskBtreeBuilder<W, L>
568 : where
569 : W: BlockWriter,
570 : {
571 4172 : pub fn new(writer: W) -> Self {
572 4172 : DiskBtreeBuilder {
573 4172 : writer,
574 4172 : last_key: None,
575 4172 : stack: vec![BuildNode::new(0)],
576 4172 : }
577 4172 : }
578 :
579 14438594 : pub fn append(&mut self, key: &[u8; L], value: u64) -> Result<()> {
580 14438594 : if value > MAX_VALUE {
581 0 : return Err(DiskBtreeError::AppendOverflow(value));
582 14438594 : }
583 14438594 : if let Some(last_key) = &self.last_key {
584 14434856 : if key <= last_key {
585 4 : return Err(DiskBtreeError::UnsortedInput {
586 4 : key: key.as_slice().into(),
587 4 : last_key: last_key.as_slice().into(),
588 4 : });
589 14434852 : }
590 3738 : }
591 14438590 : self.last_key = Some(*key);
592 14438590 :
593 14438590 : self.append_internal(key, Value::from_u64(value))
594 14438594 : }
595 :
596 14464351 : fn append_internal(&mut self, key: &[u8; L], value: Value) -> Result<()> {
597 14464351 : // Try to append to the current leaf buffer
598 14464351 : let last = self
599 14464351 : .stack
600 14464351 : .last_mut()
601 14464351 : .expect("should always have at least one item");
602 14464351 : let level = last.level;
603 14464351 : if last.push(key, value) {
604 14415328 : return Ok(());
605 49023 : }
606 49023 :
607 49023 : // It did not fit. Try to compress, and if it succeeds to make
608 49023 : // some room on the node, try appending to it again.
609 49023 : #[allow(clippy::collapsible_if)]
610 49023 : if last.compress() {
611 24874 : if last.push(key, value) {
612 24858 : return Ok(());
613 16 : }
614 24149 : }
615 :
616 : // Could not append to the current leaf. Flush it and create a new one.
617 24165 : self.flush_node()?;
618 :
619 : // Replace the node we flushed with an empty one and append the new
620 : // key to it.
621 24165 : let mut last = BuildNode::new(level);
622 24165 : if !last.push(key, value) {
623 0 : return Err(DiskBtreeError::FailedToPushToNewLeafNode);
624 24165 : }
625 24165 :
626 24165 : self.stack.push(last);
627 24165 :
628 24165 : Ok(())
629 14464351 : }
630 :
631 : /// Flush the bottommost node in the stack to disk. Appends a downlink to its parent,
632 : /// and recursively flushes the parent too, if it becomes full. If the root page becomes full,
633 : /// creates a new root page, increasing the height of the tree.
634 25761 : fn flush_node(&mut self) -> Result<()> {
635 25761 : // Get the current bottommost node in the stack and flush it to disk.
636 25761 : let last = self
637 25761 : .stack
638 25761 : .pop()
639 25761 : .expect("should always have at least one item");
640 25761 : let buf = last.pack();
641 25761 : let downlink_key = last.first_key();
642 25761 : let downlink_ptr = self.writer.write_blk(buf)?;
643 :
644 : // Append the downlink to the parent. If there is no parent, ie. this was the root page,
645 : // create a new root page, increasing the height of the tree.
646 25761 : if self.stack.is_empty() {
647 1596 : self.stack.push(BuildNode::new(last.level + 1));
648 24165 : }
649 25761 : self.append_internal(&downlink_key, Value::from_blknum(downlink_ptr))
650 25761 : }
651 :
652 : ///
653 : /// Flushes everything to disk, and returns the block number of the root page.
654 : /// The caller must store the root block number "out-of-band", and pass it
655 : /// to the DiskBtreeReader::new() when you want to read the tree again.
656 : /// (In the image and delta layers, it is stored in the beginning of the file,
657 : /// in the summary header)
658 : ///
659 3642 : pub fn finish(mut self) -> Result<(u32, W)> {
660 : // flush all levels, except the root.
661 5238 : while self.stack.len() > 1 {
662 1596 : self.flush_node()?;
663 : }
664 :
665 3642 : let root = self
666 3642 : .stack
667 3642 : .first()
668 3642 : .expect("by the check above we left one item there");
669 3642 : let buf = root.pack();
670 3642 : let root_blknum = self.writer.write_blk(buf)?;
671 :
672 3642 : Ok((root_blknum, self.writer))
673 3642 : }
674 :
675 4095304 : pub fn borrow_writer(&self) -> &W {
676 4095304 : &self.writer
677 4095304 : }
678 : }
679 :
680 : ///
681 : /// BuildNode represesnts an incomplete page that we are appending to.
682 : ///
683 : #[derive(Clone, Debug)]
684 : struct BuildNode<const L: usize> {
685 : num_children: u16,
686 : level: u8,
687 : prefix: Vec<u8>,
688 : suffix_len: usize,
689 :
690 : keys: Vec<u8>,
691 : values: Vec<u8>,
692 :
693 : size: usize, // physical size of this node, if it was written to disk like this
694 : }
695 :
696 : const NODE_SIZE: usize = PAGE_SZ;
697 :
698 : const NODE_HDR_SIZE: usize = 2 + 1 + 1 + 1;
699 :
700 : impl<const L: usize> BuildNode<L> {
701 29933 : fn new(level: u8) -> Self {
702 29933 : BuildNode {
703 29933 : num_children: 0,
704 29933 : level,
705 29933 : prefix: Vec::new(),
706 29933 : suffix_len: 0,
707 29933 : keys: Vec::new(),
708 29933 : values: Vec::new(),
709 29933 : size: NODE_HDR_SIZE,
710 29933 : }
711 29933 : }
712 :
713 : /// Try to append a key-value pair to this node. Returns 'true' on
714 : /// success, 'false' if the page was full or the key was
715 : /// incompatible with the prefix of the existing keys.
716 14513390 : fn push(&mut self, key: &[u8; L], value: Value) -> bool {
717 14513390 : // If we have already performed prefix-compression on the page,
718 14513390 : // check that the incoming key has the same prefix.
719 14513390 : if self.num_children > 0 {
720 : // does the prefix allow it?
721 14483891 : if !key.starts_with(&self.prefix) {
722 432 : return false;
723 14483459 : }
724 29499 : } else {
725 29499 : self.suffix_len = key.len();
726 29499 : }
727 :
728 : // Is the node too full?
729 14512958 : if self.size + self.suffix_len + VALUE_SZ >= NODE_SIZE {
730 48607 : return false;
731 14464351 : }
732 14464351 :
733 14464351 : // All clear
734 14464351 : self.num_children += 1;
735 14464351 : self.keys.extend(&key[self.prefix.len()..]);
736 14464351 : self.values.extend(value.0);
737 14464351 :
738 14464351 : assert!(self.keys.len() == self.num_children as usize * self.suffix_len);
739 14464351 : assert!(self.values.len() == self.num_children as usize * VALUE_SZ);
740 :
741 14464351 : self.size += self.suffix_len + VALUE_SZ;
742 14464351 :
743 14464351 : true
744 14513390 : }
745 :
746 : ///
747 : /// Perform prefix-compression.
748 : ///
749 : /// Returns 'true' on success, 'false' if no compression was possible.
750 : ///
751 49023 : fn compress(&mut self) -> bool {
752 49023 : let first_suffix = self.first_suffix();
753 49023 : let last_suffix = self.last_suffix();
754 49023 :
755 49023 : // Find the common prefix among all keys
756 49023 : let mut prefix_len = 0;
757 445745 : while prefix_len < self.suffix_len {
758 445745 : if first_suffix[prefix_len] != last_suffix[prefix_len] {
759 49023 : break;
760 396722 : }
761 396722 : prefix_len += 1;
762 : }
763 49023 : if prefix_len == 0 {
764 24149 : return false;
765 24874 : }
766 24874 :
767 24874 : // Can compress. Rewrite the keys without the common prefix.
768 24874 : self.prefix.extend(&self.keys[..prefix_len]);
769 24874 :
770 24874 : let mut new_keys = Vec::new();
771 24874 : let mut key_off = 0;
772 6729316 : while key_off < self.keys.len() {
773 6704442 : let next_key_off = key_off + self.suffix_len;
774 6704442 : new_keys.extend(&self.keys[key_off + prefix_len..next_key_off]);
775 6704442 : key_off = next_key_off;
776 6704442 : }
777 24874 : self.keys = new_keys;
778 24874 : self.suffix_len -= prefix_len;
779 24874 :
780 24874 : self.size -= prefix_len * self.num_children as usize;
781 24874 : self.size += prefix_len;
782 24874 :
783 24874 : assert!(self.keys.len() == self.num_children as usize * self.suffix_len);
784 24874 : assert!(self.values.len() == self.num_children as usize * VALUE_SZ);
785 :
786 24874 : true
787 49023 : }
788 :
789 : ///
790 : /// Serialize the node to on-disk format.
791 : ///
792 29403 : fn pack(&self) -> Bytes {
793 29403 : assert!(self.keys.len() == self.num_children as usize * self.suffix_len);
794 29403 : assert!(self.values.len() == self.num_children as usize * VALUE_SZ);
795 29403 : assert!(self.num_children > 0);
796 :
797 29403 : let mut buf = BytesMut::new();
798 29403 :
799 29403 : buf.put_u16(self.num_children);
800 29403 : buf.put_u8(self.level);
801 29403 : buf.put_u8(self.prefix.len() as u8);
802 29403 : buf.put_u8(self.suffix_len as u8);
803 29403 : buf.put(&self.prefix[..]);
804 29403 : buf.put(&self.keys[..]);
805 29403 : buf.put(&self.values[..]);
806 29403 :
807 29403 : assert!(buf.len() == self.size);
808 :
809 29403 : assert!(buf.len() <= PAGE_SZ);
810 29403 : buf.resize(PAGE_SZ, 0);
811 29403 : buf.freeze()
812 29403 : }
813 :
814 74784 : fn first_suffix(&self) -> &[u8] {
815 74784 : &self.keys[..self.suffix_len]
816 74784 : }
817 49023 : fn last_suffix(&self) -> &[u8] {
818 49023 : &self.keys[self.keys.len() - self.suffix_len..]
819 49023 : }
820 :
821 : /// Return the full first key of the page, including the prefix
822 25761 : fn first_key(&self) -> [u8; L] {
823 25761 : let mut key = [0u8; L];
824 25761 : key[..self.prefix.len()].copy_from_slice(&self.prefix);
825 25761 : key[self.prefix.len()..].copy_from_slice(self.first_suffix());
826 25761 : key
827 25761 : }
828 : }
829 :
830 : #[cfg(test)]
831 : pub(crate) mod tests {
832 : use std::collections::BTreeMap;
833 : use std::sync::atomic::{AtomicUsize, Ordering};
834 :
835 : use rand::Rng;
836 :
837 : use super::*;
838 : use crate::tenant::block_io::{BlockCursor, BlockLease, BlockReaderRef};
839 :
840 : #[derive(Clone, Default)]
841 : pub(crate) struct TestDisk {
842 : blocks: Vec<Bytes>,
843 : }
844 : impl TestDisk {
845 20 : fn new() -> Self {
846 20 : Self::default()
847 20 : }
848 2033784 : pub(crate) fn read_blk(&self, blknum: u32) -> io::Result<BlockLease> {
849 2033784 : let mut buf = [0u8; PAGE_SZ];
850 2033784 : buf.copy_from_slice(&self.blocks[blknum as usize]);
851 2033784 : Ok(std::sync::Arc::new(buf).into())
852 2033784 : }
853 : }
854 : impl BlockReader for TestDisk {
855 822568 : fn block_cursor(&self) -> BlockCursor<'_> {
856 822568 : BlockCursor::new(BlockReaderRef::TestDisk(self))
857 822568 : }
858 : }
859 : impl BlockWriter for &mut TestDisk {
860 432 : fn write_blk(&mut self, buf: Bytes) -> io::Result<u32> {
861 432 : let blknum = self.blocks.len();
862 432 : self.blocks.push(buf);
863 432 : Ok(blknum as u32)
864 432 : }
865 : }
866 :
867 : #[tokio::test]
868 4 : async fn basic() -> Result<()> {
869 4 : let mut disk = TestDisk::new();
870 4 : let mut writer = DiskBtreeBuilder::<_, 6>::new(&mut disk);
871 4 :
872 4 : let ctx = RequestContext::new(TaskKind::UnitTest, DownloadBehavior::Error);
873 4 :
874 4 : let all_keys: Vec<&[u8; 6]> = vec![
875 4 : b"xaaaaa", b"xaaaba", b"xaaaca", b"xabaaa", b"xababa", b"xabaca", b"xabada", b"xabadb",
876 4 : ];
877 4 : let all_data: Vec<(&[u8; 6], u64)> = all_keys
878 4 : .iter()
879 4 : .enumerate()
880 32 : .map(|(idx, key)| (*key, idx as u64))
881 4 : .collect();
882 32 : for (key, val) in all_data.iter() {
883 32 : writer.append(key, *val)?;
884 4 : }
885 4 :
886 4 : let (root_offset, _writer) = writer.finish()?;
887 4 :
888 4 : let reader = DiskBtreeReader::new(0, root_offset, disk);
889 4 :
890 4 : reader.dump().await?;
891 4 :
892 4 : // Test the `get` function on all the keys.
893 32 : for (key, val) in all_data.iter() {
894 32 : assert_eq!(reader.get(key, &ctx).await?, Some(*val));
895 4 : }
896 4 : // And on some keys that don't exist
897 4 : assert_eq!(reader.get(b"aaaaaa", &ctx).await?, None);
898 4 : assert_eq!(reader.get(b"zzzzzz", &ctx).await?, None);
899 4 : assert_eq!(reader.get(b"xaaabx", &ctx).await?, None);
900 4 :
901 4 : // Test search with `visit` function
902 4 : let search_key = b"xabaaa";
903 4 : let expected: Vec<(Vec<u8>, u64)> = all_data
904 4 : .iter()
905 32 : .filter(|(key, _value)| key[..] >= search_key[..])
906 20 : .map(|(key, value)| (key.to_vec(), *value))
907 4 : .collect();
908 4 :
909 4 : let mut data = Vec::new();
910 4 : reader
911 4 : .visit(
912 4 : search_key,
913 4 : VisitDirection::Forwards,
914 20 : |key, value| {
915 20 : data.push((key.to_vec(), value));
916 20 : true
917 20 : },
918 4 : &ctx,
919 4 : )
920 4 : .await?;
921 4 : assert_eq!(data, expected);
922 4 :
923 4 : // Test a backwards scan
924 4 : let mut expected: Vec<(Vec<u8>, u64)> = all_data
925 4 : .iter()
926 32 : .filter(|(key, _value)| key[..] <= search_key[..])
927 16 : .map(|(key, value)| (key.to_vec(), *value))
928 4 : .collect();
929 4 : expected.reverse();
930 4 : let mut data = Vec::new();
931 4 : reader
932 4 : .visit(
933 4 : search_key,
934 4 : VisitDirection::Backwards,
935 16 : |key, value| {
936 16 : data.push((key.to_vec(), value));
937 16 : true
938 16 : },
939 4 : &ctx,
940 4 : )
941 4 : .await?;
942 4 : assert_eq!(data, expected);
943 4 :
944 4 : // Backward scan where nothing matches
945 4 : reader
946 4 : .visit(
947 4 : b"aaaaaa",
948 4 : VisitDirection::Backwards,
949 4 : |key, value| {
950 0 : panic!("found unexpected key {}: {}", hex::encode(key), value);
951 4 : },
952 4 : &ctx,
953 4 : )
954 4 : .await?;
955 4 :
956 4 : // Full scan
957 4 : let expected: Vec<(Vec<u8>, u64)> = all_data
958 4 : .iter()
959 32 : .map(|(key, value)| (key.to_vec(), *value))
960 4 : .collect();
961 4 : let mut data = Vec::new();
962 4 : reader
963 4 : .visit(
964 4 : &[0u8; 6],
965 4 : VisitDirection::Forwards,
966 32 : |key, value| {
967 32 : data.push((key.to_vec(), value));
968 32 : true
969 32 : },
970 4 : &ctx,
971 4 : )
972 4 : .await?;
973 4 : assert_eq!(data, expected);
974 4 :
975 4 : Ok(())
976 4 : }
977 :
978 : #[tokio::test]
979 4 : async fn lots_of_keys() -> Result<()> {
980 4 : let mut disk = TestDisk::new();
981 4 : let mut writer = DiskBtreeBuilder::<_, 8>::new(&mut disk);
982 4 : let ctx = RequestContext::new(TaskKind::UnitTest, DownloadBehavior::Error);
983 4 :
984 4 : const NUM_KEYS: u64 = 1000;
985 4 :
986 4 : let mut all_data: BTreeMap<u64, u64> = BTreeMap::new();
987 4 :
988 4004 : for idx in 0..NUM_KEYS {
989 4000 : let key_int: u64 = 1 + idx * 2;
990 4000 : let key = u64::to_be_bytes(key_int);
991 4000 : writer.append(&key, idx)?;
992 4 :
993 4000 : all_data.insert(key_int, idx);
994 4 : }
995 4 :
996 4 : let (root_offset, _writer) = writer.finish()?;
997 4 :
998 4 : let reader = DiskBtreeReader::new(0, root_offset, disk);
999 4 :
1000 4 : reader.dump().await?;
1001 4 :
1002 4 : use std::sync::Mutex;
1003 4 :
1004 4 : let result = Mutex::new(Vec::new());
1005 4 : let limit: AtomicUsize = AtomicUsize::new(10);
1006 167640 : let take_ten = |key: &[u8], value: u64| {
1007 167640 : let mut keybuf = [0u8; 8];
1008 167640 : keybuf.copy_from_slice(key);
1009 167640 : let key_int = u64::from_be_bytes(keybuf);
1010 167640 :
1011 167640 : let mut result = result.lock().unwrap();
1012 167640 : result.push((key_int, value));
1013 167640 :
1014 167640 : // keep going until we have 10 matches
1015 167640 : result.len() < limit.load(Ordering::Relaxed)
1016 167640 : };
1017 4 :
1018 8040 : for search_key_int in 0..(NUM_KEYS * 2 + 10) {
1019 8040 : let search_key = u64::to_be_bytes(search_key_int);
1020 8040 : assert_eq!(
1021 8040 : reader.get(&search_key, &ctx).await?,
1022 8040 : all_data.get(&search_key_int).cloned()
1023 4 : );
1024 4 :
1025 4 : // Test a forward scan starting with this key
1026 8040 : result.lock().unwrap().clear();
1027 8040 : reader
1028 8040 : .visit(&search_key, VisitDirection::Forwards, take_ten, &ctx)
1029 8040 : .await?;
1030 8040 : let expected = all_data
1031 8040 : .range(search_key_int..)
1032 8040 : .take(10)
1033 79640 : .map(|(&key, &val)| (key, val))
1034 8040 : .collect::<Vec<(u64, u64)>>();
1035 8040 : assert_eq!(*result.lock().unwrap(), expected);
1036 4 :
1037 4 : // And a backwards scan
1038 8040 : result.lock().unwrap().clear();
1039 8040 : reader
1040 8040 : .visit(&search_key, VisitDirection::Backwards, take_ten, &ctx)
1041 8040 : .await?;
1042 8040 : let expected = all_data
1043 8040 : .range(..=search_key_int)
1044 8040 : .rev()
1045 8040 : .take(10)
1046 80000 : .map(|(&key, &val)| (key, val))
1047 8040 : .collect::<Vec<(u64, u64)>>();
1048 8040 : assert_eq!(*result.lock().unwrap(), expected);
1049 4 : }
1050 4 :
1051 4 : // full scan
1052 4 : let search_key = u64::to_be_bytes(0);
1053 4 : limit.store(usize::MAX, Ordering::Relaxed);
1054 4 : result.lock().unwrap().clear();
1055 4 : reader
1056 4 : .visit(&search_key, VisitDirection::Forwards, take_ten, &ctx)
1057 4 : .await?;
1058 4 : let expected = all_data
1059 4 : .iter()
1060 4000 : .map(|(&key, &val)| (key, val))
1061 4 : .collect::<Vec<(u64, u64)>>();
1062 4 : assert_eq!(*result.lock().unwrap(), expected);
1063 4 :
1064 4 : // full scan
1065 4 : let search_key = u64::to_be_bytes(u64::MAX);
1066 4 : limit.store(usize::MAX, Ordering::Relaxed);
1067 4 : result.lock().unwrap().clear();
1068 4 : reader
1069 4 : .visit(&search_key, VisitDirection::Backwards, take_ten, &ctx)
1070 4 : .await?;
1071 4 : let expected = all_data
1072 4 : .iter()
1073 4 : .rev()
1074 4000 : .map(|(&key, &val)| (key, val))
1075 4 : .collect::<Vec<(u64, u64)>>();
1076 4 : assert_eq!(*result.lock().unwrap(), expected);
1077 4 :
1078 4 : Ok(())
1079 4 : }
1080 :
1081 : #[tokio::test]
1082 4 : async fn random_data() -> Result<()> {
1083 4 : let ctx = RequestContext::new(TaskKind::UnitTest, DownloadBehavior::Error);
1084 4 :
1085 4 : // Generate random keys with exponential distribution, to
1086 4 : // exercise the prefix compression
1087 4 : const NUM_KEYS: usize = 100000;
1088 4 : let mut all_data: BTreeMap<u128, u64> = BTreeMap::new();
1089 400004 : for idx in 0..NUM_KEYS {
1090 400000 : let u: f64 = rand::thread_rng().gen_range(0.0..1.0);
1091 400000 : let t = -(f64::ln(u));
1092 400000 : let key_int = (t * 1000000.0) as u128;
1093 400000 :
1094 400000 : all_data.insert(key_int, idx as u64);
1095 400000 : }
1096 4 :
1097 4 : // Build a tree from it
1098 4 : let mut disk = TestDisk::new();
1099 4 : let mut writer = DiskBtreeBuilder::<_, 16>::new(&mut disk);
1100 4 :
1101 390344 : for (&key, &val) in all_data.iter() {
1102 390344 : writer.append(&u128::to_be_bytes(key), val)?;
1103 4 : }
1104 4 : let (root_offset, _writer) = writer.finish()?;
1105 4 :
1106 4 : let reader = DiskBtreeReader::new(0, root_offset, disk);
1107 4 :
1108 4 : // Test get() operation on all the keys
1109 390344 : for (&key, &val) in all_data.iter() {
1110 390344 : let search_key = u128::to_be_bytes(key);
1111 390344 : assert_eq!(reader.get(&search_key, &ctx).await?, Some(val));
1112 4 : }
1113 4 :
1114 4 : // Test get() operations on random keys, most of which will not exist
1115 400004 : for _ in 0..100000 {
1116 400000 : let key_int = rand::thread_rng().r#gen::<u128>();
1117 400000 : let search_key = u128::to_be_bytes(key_int);
1118 400000 : assert!(reader.get(&search_key, &ctx).await? == all_data.get(&key_int).cloned());
1119 4 : }
1120 4 :
1121 4 : // Test boundary cases
1122 4 : assert!(
1123 4 : reader.get(&u128::to_be_bytes(u128::MIN), &ctx).await?
1124 4 : == all_data.get(&u128::MIN).cloned()
1125 4 : );
1126 4 : assert!(
1127 4 : reader.get(&u128::to_be_bytes(u128::MAX), &ctx).await?
1128 4 : == all_data.get(&u128::MAX).cloned()
1129 4 : );
1130 4 :
1131 4 : // Test iterator and get_stream API
1132 4 : let mut iter = reader.iter(&[0; 16], &ctx);
1133 4 : let mut cnt = 0;
1134 390348 : while let Some(res) = iter.next().await {
1135 390344 : let (key, val) = res?;
1136 390344 : let key = u128::from_be_bytes(key.as_slice().try_into().unwrap());
1137 390344 : assert_eq!(val, *all_data.get(&key).unwrap());
1138 390344 : cnt += 1;
1139 4 : }
1140 4 : assert_eq!(cnt, all_data.len());
1141 4 :
1142 4 : Ok(())
1143 4 : }
1144 :
1145 : #[test]
1146 4 : fn unsorted_input() {
1147 4 : let mut disk = TestDisk::new();
1148 4 : let mut writer = DiskBtreeBuilder::<_, 2>::new(&mut disk);
1149 4 :
1150 4 : let _ = writer.append(b"ba", 1);
1151 4 : let _ = writer.append(b"bb", 2);
1152 4 : let err = writer.append(b"aa", 3).expect_err("should've failed");
1153 4 : match err {
1154 4 : DiskBtreeError::UnsortedInput { key, last_key } => {
1155 4 : assert_eq!(key.as_ref(), b"aa".as_slice());
1156 4 : assert_eq!(last_key.as_ref(), b"bb".as_slice());
1157 : }
1158 0 : _ => panic!("unexpected error variant, expected DiskBtreeError::UnsortedInput"),
1159 : }
1160 4 : }
1161 :
1162 : ///
1163 : /// This test contains a particular data set, see disk_btree_test_data.rs
1164 : ///
1165 : #[tokio::test]
1166 4 : async fn particular_data() -> Result<()> {
1167 4 : // Build a tree from it
1168 4 : let mut disk = TestDisk::new();
1169 4 : let mut writer = DiskBtreeBuilder::<_, 26>::new(&mut disk);
1170 4 : let ctx = RequestContext::new(TaskKind::UnitTest, DownloadBehavior::Error);
1171 4 :
1172 8004 : for (key, val) in disk_btree_test_data::TEST_DATA {
1173 8000 : writer.append(&key, val)?;
1174 4 : }
1175 4 : let (root_offset, writer) = writer.finish()?;
1176 4 :
1177 4 : println!("SIZE: {} blocks", writer.blocks.len());
1178 4 :
1179 4 : let reader = DiskBtreeReader::new(0, root_offset, disk);
1180 4 :
1181 4 : // Test get() operation on all the keys
1182 8004 : for (key, val) in disk_btree_test_data::TEST_DATA {
1183 8000 : assert_eq!(reader.get(&key, &ctx).await?, Some(val));
1184 4 : }
1185 4 :
1186 4 : // Test full scan
1187 4 : let mut count = 0;
1188 4 : reader
1189 4 : .visit(
1190 4 : &[0u8; 26],
1191 4 : VisitDirection::Forwards,
1192 8000 : |_key, _value| {
1193 8000 : count += 1;
1194 8000 : true
1195 8000 : },
1196 4 : &ctx,
1197 4 : )
1198 4 : .await?;
1199 4 : assert_eq!(count, disk_btree_test_data::TEST_DATA.len());
1200 4 :
1201 4 : reader.dump().await?;
1202 4 :
1203 4 : Ok(())
1204 4 : }
1205 : }
1206 :
1207 : #[cfg(test)]
1208 : #[path = "disk_btree_test_data.rs"]
1209 : mod disk_btree_test_data;
|
