Skip to main content

tuwunel_database/map/
seek.rs

1use std::sync::Arc;
2
3use futures::{FutureExt, Stream, StreamExt, TryFutureExt, TryStreamExt};
4use rocksdb::{Direction, ReadOptions};
5use tokio::task::consume_budget;
6use tuwunel_core::Result;
7
8use super::{Map, cache_iter_options_default, iter_options_default, scan_options_default};
9use crate::{
10	pool::{Seek, into_send_seek},
11	stream::State,
12};
13
14/// Builds a forward or reverse map stream from an optional raw seek key.
15///
16/// A block-cache probe selects inline iteration when the initial seek is
17/// cached; otherwise the seek runs on the engine's blocking pool. The
18/// projection type determines whether each item contains a key alone or a
19/// key-value pair.
20pub(super) fn seek_stream<'a, C, T>(
21	map: &'a Arc<Map>,
22	dir: Direction,
23	from: Option<&[u8]>,
24) -> impl Stream<Item = Result<T>> + Send + use<'a, C, T>
25where
26	C: From<State<'a>> + Stream<Item = Result<T>> + Send,
27{
28	seek_stream_bounded::<C, T>(map, dir, from, None)
29}
30
31/// Builds a map stream with an optional exclusive upper bound.
32///
33/// Both the cache probe and the real iterator own their bound bytes. The
34/// direction and starting position retain the unbounded seek behavior.
35pub(super) fn seek_stream_bounded<'a, C, T>(
36	map: &'a Arc<Map>,
37	dir: Direction,
38	from: Option<&[u8]>,
39	to: Option<&[u8]>,
40) -> impl Stream<Item = Result<T>> + Send + use<'a, C, T>
41where
42	C: From<State<'a>> + Stream<Item = Result<T>> + Send,
43{
44	let opts = bounded_options(iter_options_default(&map.engine), to);
45	let state = State::new(map, opts);
46
47	if is_cached(map, dir, from, to) {
48		let state = init(state, dir, from);
49		return consume_budget()
50			.map(move |()| C::from(state))
51			.into_stream()
52			.flatten()
53			.left_stream();
54	}
55
56	pool_seek::<C, T>(map, state, dir, from).right_stream()
57}
58
59/// Builds a forward stream over a whole column for an integrity walk.
60///
61/// The walk reads storage rather than cache, so its seek always ships to the
62/// blocking pool.
63pub(super) fn scan_stream<'a, C, T>(map: &'a Arc<Map>) -> impl Stream<Item = Result<T>> + Send
64where
65	C: From<State<'a>> + Stream<Item = Result<T>> + Send,
66{
67	let state = State::new(map, scan_options_default(&map.engine));
68
69	pool_seek::<C, T>(map, state, Direction::Forward, None)
70}
71
72fn pool_seek<'a, C, T>(
73	map: &'a Arc<Map>,
74	state: State<'a>,
75	dir: Direction,
76	from: Option<&[u8]>,
77) -> impl Stream<Item = Result<T>> + Send + use<'a, C, T>
78where
79	C: From<State<'a>> + Stream<Item = Result<T>> + Send,
80{
81	let seek = Seek {
82		map: map.clone(),
83		state: into_send_seek(state),
84		dir,
85		key: from.map(Into::into),
86		res: None,
87	};
88
89	map.engine
90		.pool
91		.execute_iter(seek)
92		.ok_into::<C>()
93		.into_stream()
94		.try_flatten()
95}
96
97/// Tests whether an initial seek can complete from block cache.
98///
99/// The probe uses the same direction and starting key as the real iterator
100/// without filling cache.
101#[tracing::instrument(
102    name = "cached",
103    level = "trace",
104    skip_all,
105    fields(%map),
106)]
107fn is_cached(map: &Arc<Map>, dir: Direction, from: Option<&[u8]>, to: Option<&[u8]>) -> bool {
108	let opts = bounded_options(cache_iter_options_default(&map.engine), to);
109	let state = init(State::new(map, opts), dir, from);
110
111	!state.is_incomplete()
112}
113
114fn bounded_options(mut opts: ReadOptions, to: Option<&[u8]>) -> ReadOptions {
115	if let Some(to) = to {
116		opts.set_iterate_upper_bound(to);
117	}
118
119	opts
120}
121
122/// Initializes iterator state for the requested seek direction.
123///
124/// The optional raw key is interpreted as a lower bound when moving forward and
125/// an upper bound when moving backward.
126fn init<'a>(state: State<'a>, dir: Direction, from: Option<&[u8]>) -> State<'a> {
127	match dir {
128		| Direction::Forward => state.init_fwd(from),
129		| Direction::Reverse => state.init_rev(from),
130	}
131}