foundationdb/env.rs
1// Copyright 2018 foundationdb-rs developers, https://github.com/Clikengo/foundationdb-rs/graphs/contributors
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8//! Pluggable sources for the effects that must stay deterministic under
9//! FoundationDB simulation: time and randomness.
10//!
11//! # Why control flow must not read ambient time or randomness
12//!
13//! The deterministic simulator virtualizes both: it decides what time it is and
14//! which pseudo-random choices are made, which is precisely what lets it replay
15//! a failing run from a seed. Code that calls `Instant::now()` or draws from a
16//! thread-local generator steps outside that control, so its behavior changes
17//! from run to run and a bug found in simulation cannot be reproduced.
18//!
19//! The way out is to take time and randomness as dependencies instead of
20//! reaching for them: [`Clock`] and [`Rng`], bundled in an [`Environment`].
21//! Production code uses [`WallClock`] and [`SeededRng`], which do the obvious
22//! thing. Simulation workloads pass implementations backed by the simulator,
23//! provided by the `foundationdb-simulation` crate.
24//!
25//! Ambient wall-clock time remains fine for purely observational output, metrics
26//! durations or log timestamps that nothing branches on.
27//!
28//! # Measure with monotonic, persist with wall
29//!
30//! [`Clock`] offers two readings and they are not interchangeable.
31//! [`Clock::monotonic`] never goes backwards but counts from an epoch private to
32//! that one instance, so it is the right and only choice for durations,
33//! deadlines, budgets and backoff. [`Clock::wall`] is a real timestamp, counted
34//! from the UNIX epoch, so it is the right choice for anything written to the
35//! database or compared across processes, at the cost of being able to jump when
36//! the machine clock is adjusted.
37//!
38//! Never persist a monotonic reading and never compare two of them coming from
39//! different [`Clock`] instances: the values are meaningless outside the
40//! instance that produced them.
41//!
42//! # Drawing a lot of randomness
43//!
44//! [`Rng`] is deliberately minimal, one `u64` per call through a shared
45//! reference. A component that needs a large volume of random data, or
46//! distributions this trait does not offer, should draw a single `u64` and use
47//! it to seed its own local generator (`rand_chacha::ChaCha8Rng::seed_from_u64`
48//! for instance). The run stays reproducible, since the seed came from the
49//! environment, and the heavy sampling stays local and fast.
50//!
51//! # Non-goals
52//!
53//! This module supplies *values*, never control over execution: there is no
54//! sleep and no spawn capability here. Under simulation the caller owns the
55//! schedule: it advances simulated time and re-invokes the deterministic unit of
56//! work. An asynchronous `Timer` capability is planned surface and is
57//! deliberately deferred, so do not work around its absence by sleeping on the
58//! ambient runtime inside code that must be simulable.
59//!
60//! # Known limitation
61//!
62//! Under simulation, wall time is derived from simulated time and therefore
63//! never jumps. Bugs that only appear when the machine clock is stepped by NTP,
64//! a leap second or an operator, cannot be exercised in simulation: exercise
65//! those with a purpose-built [`Clock`] in a unit test instead.
66
67use std::collections::hash_map::RandomState;
68use std::fmt;
69use std::hash::{BuildHasher, Hasher};
70use std::sync::Arc;
71use std::sync::atomic::{AtomicU64, Ordering};
72use std::time::{Duration, Instant, SystemTime, UNIX_EPOCH};
73
74/// Where time comes from.
75///
76/// See the [module documentation](self) for why time is a dependency rather
77/// than something to reach for, and for the rule that decides between the two
78/// readings: measure with [`monotonic`](Self::monotonic), persist with
79/// [`wall`](Self::wall).
80pub trait Clock: fmt::Debug + Send + Sync {
81 /// A monotonic reading, for measuring how much time has passed.
82 ///
83 /// Successive readings never decrease, which makes this the reading to use
84 /// for elapsed times, deadlines, budgets and backoff.
85 ///
86 /// <div class="warning">
87 ///
88 /// The epoch is arbitrary and **private to this instance**. Never persist a
89 /// monotonic reading, and never compare readings taken from two different
90 /// `Clock` instances: only the difference between two readings of the *same*
91 /// instance carries meaning.
92 ///
93 /// </div>
94 fn monotonic(&self) -> Duration;
95
96 /// A wall-clock reading, time elapsed since the UNIX epoch.
97 ///
98 /// This is a real timestamp, comparable across processes and machines, so it
99 /// is the reading to persist in the database or put in a message. In
100 /// production it can jump forwards or backwards when the machine clock is
101 /// adjusted (NTP, a leap second, an operator), so never measure a duration
102 /// with it. Under simulation it is deterministic.
103 fn wall(&self) -> Duration;
104}
105
106/// Where pseudo-random values come from.
107///
108/// See the [module documentation](self) for why randomness is a dependency
109/// rather than something to reach for, and for the pattern to follow when a lot
110/// of randomness is needed.
111///
112/// <div class="warning">
113///
114/// Implementations are **not** cryptographically secure and must not be used to
115/// derive secrets, tokens or keys.
116///
117/// </div>
118pub trait Rng: fmt::Debug + Send + Sync {
119 /// The next value of the sequence, uniform over the whole `u64` range.
120 ///
121 /// This takes `&self` so that a generator can be shared: an implementation
122 /// advances its state through interior mutability.
123 fn next_u64(&self) -> u64;
124
125 /// The next value of the sequence, uniform over the whole `u32` range.
126 ///
127 /// The default implementation truncates [`next_u64`](Self::next_u64).
128 fn next_u32(&self) -> u32 {
129 self.next_u64() as u32
130 }
131}
132
133/// The [`Clock`] of production code, reading the clocks of the machine.
134///
135/// [`monotonic`](Clock::monotonic) counts from the moment the instance was
136/// built, so the first reading of a fresh `WallClock` is close to zero.
137#[derive(Debug, Clone)]
138pub struct WallClock {
139 anchor: Instant,
140}
141
142impl WallClock {
143 /// Builds a clock whose monotonic epoch is now.
144 #[cfg_attr(feature = "trace", tracing::instrument(level = "debug"))]
145 pub fn new() -> Self {
146 Self {
147 anchor: Instant::now(),
148 }
149 }
150}
151
152impl Default for WallClock {
153 fn default() -> Self {
154 Self::new()
155 }
156}
157
158impl Clock for WallClock {
159 fn monotonic(&self) -> Duration {
160 self.anchor.elapsed()
161 }
162
163 fn wall(&self) -> Duration {
164 // A system clock set before 1970 is the only way this fails, and no
165 // caller can do anything useful with an error here.
166 SystemTime::now()
167 .duration_since(UNIX_EPOCH)
168 .unwrap_or(Duration::ZERO)
169 }
170}
171
172/// The [`Rng`] of production code: SplitMix64, seeded once.
173///
174/// [`new`](Self::new) takes the seed, which makes the whole sequence
175/// reproducible: the same seed always yields the same values in the same order.
176/// [`Default`] takes its seed from the entropy the standard library uses to seed
177/// `HashMap`, which is best effort, unpredictable in practice but neither
178/// reproducible nor guaranteed by anything.
179///
180/// <div class="warning">
181///
182/// SplitMix64 is a fast statistical generator, **not** a cryptographic one.
183///
184/// </div>
185#[derive(Debug)]
186pub struct SeededRng {
187 state: AtomicU64,
188}
189
190/// The golden-ratio increment of SplitMix64.
191const SPLITMIX_GAMMA: u64 = 0x9E37_79B9_7F4A_7C15;
192
193impl SeededRng {
194 /// Builds a generator producing the sequence of `seed`, reproducibly.
195 #[cfg_attr(feature = "trace", tracing::instrument(level = "debug"))]
196 pub fn new(seed: u64) -> Self {
197 Self {
198 state: AtomicU64::new(seed),
199 }
200 }
201}
202
203impl Default for SeededRng {
204 fn default() -> Self {
205 Self::new(RandomState::new().build_hasher().finish())
206 }
207}
208
209impl Rng for SeededRng {
210 fn next_u64(&self) -> u64 {
211 // fetch_add hands back the state this call consumed and leaves the next
212 // one in place, so concurrent callers each finalize a distinct value.
213 let z = self.state.fetch_add(SPLITMIX_GAMMA, Ordering::Relaxed);
214 let z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
215 let z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
216 z ^ (z >> 31)
217 }
218}
219
220/// The effects a layer needs but must not reach for: time and randomness.
221///
222/// Cloning is cheap, both sources sit behind an `Arc`, so an `Environment` is
223/// meant to be passed by value into the layers and recipes that need it and kept
224/// alongside the [`Database`](crate::Database).
225///
226/// # Example
227///
228/// ```
229/// # use foundationdb::env::Environment;
230/// // Production: machine clock, generator seeded from entropy.
231/// let env = Environment::default();
232///
233/// // A reproducible run: the same seed replays the same sequence.
234/// let env = Environment::with_seed(42);
235/// let first = env.rng().next_u64();
236/// assert_eq!(Environment::with_seed(42).rng().next_u64(), first);
237/// ```
238#[derive(Clone, Debug)]
239pub struct Environment {
240 clock: Arc<dyn Clock>,
241 rng: Arc<dyn Rng>,
242}
243
244impl Environment {
245 /// Bundles a clock and a generator.
246 #[cfg_attr(
247 feature = "trace",
248 tracing::instrument(level = "debug", skip(clock, rng))
249 )]
250 pub fn new(clock: Arc<dyn Clock>, rng: Arc<dyn Rng>) -> Self {
251 Self { clock, rng }
252 }
253
254 /// The machine clock, with a generator replaying the sequence of `seed`.
255 #[cfg_attr(feature = "trace", tracing::instrument(level = "debug"))]
256 pub fn with_seed(seed: u64) -> Self {
257 Self::new(Arc::new(WallClock::new()), Arc::new(SeededRng::new(seed)))
258 }
259
260 /// The clock of this environment.
261 pub fn clock(&self) -> &Arc<dyn Clock> {
262 &self.clock
263 }
264
265 /// The pseudo-random generator of this environment.
266 pub fn rng(&self) -> &Arc<dyn Rng> {
267 &self.rng
268 }
269}
270
271impl Default for Environment {
272 fn default() -> Self {
273 Self::new(Arc::new(WallClock::new()), Arc::new(SeededRng::default()))
274 }
275}
276
277#[cfg(test)]
278mod tests {
279 use super::*;
280
281 fn take(rng: &SeededRng, count: usize) -> Vec<u64> {
282 (0..count).map(|_| rng.next_u64()).collect()
283 }
284
285 #[test]
286 fn the_same_seed_produces_the_same_sequence() {
287 let expected = take(&SeededRng::new(42), 16);
288
289 assert_eq!(take(&SeededRng::new(42), 16), expected);
290 assert!(
291 expected.windows(2).any(|pair| pair[0] != pair[1]),
292 "the sequence is constant: {expected:?}"
293 );
294 }
295
296 #[test]
297 fn different_seeds_produce_different_sequences() {
298 assert_ne!(take(&SeededRng::new(42), 16), take(&SeededRng::new(43), 16));
299 }
300
301 #[test]
302 fn next_u32_truncates_next_u64() {
303 let wide = SeededRng::new(7);
304 let narrow = SeededRng::new(7);
305
306 for _ in 0..16 {
307 assert_eq!(narrow.next_u32(), wide.next_u64() as u32);
308 }
309 }
310
311 #[test]
312 fn wall_clock_monotonic_never_goes_backwards() {
313 let clock = WallClock::new();
314
315 let mut previous = clock.monotonic();
316 for _ in 0..1_000 {
317 let now = clock.monotonic();
318 assert!(now >= previous, "{now:?} is before {previous:?}");
319 previous = now;
320 }
321 }
322
323 #[test]
324 fn wall_clock_wall_is_a_real_timestamp() {
325 // Any machine running this test has a clock set past 2020.
326 const YEAR_2020: Duration = Duration::from_secs(1_577_836_800);
327
328 assert!(WallClock::new().wall() > YEAR_2020);
329 }
330
331 #[test]
332 fn the_default_environment_is_usable() {
333 let env = Environment::default();
334
335 assert!(env.clock().monotonic() < Duration::from_secs(1));
336 let drawn: Vec<u64> = (0..4).map(|_| env.rng().next_u64()).collect();
337 assert!(drawn.windows(2).any(|pair| pair[0] != pair[1]));
338
339 // Cloning shares the very same sources.
340 let clone = env.clone();
341 assert!(Arc::ptr_eq(clone.clock(), env.clock()));
342 assert!(Arc::ptr_eq(clone.rng(), env.rng()));
343 }
344
345 #[test]
346 fn a_seeded_environment_replays_its_sequence() {
347 let expected: Vec<u64> = (0..8)
348 .map(|_| Environment::with_seed(99).rng().next_u64())
349 .collect();
350
351 // Every fresh environment restarts the same sequence.
352 assert!(expected.iter().all(|value| *value == expected[0]));
353
354 let env = Environment::with_seed(99);
355 assert_eq!(env.rng().next_u64(), expected[0]);
356 assert_ne!(
357 env.rng().next_u64(),
358 expected[0],
359 "the sequence must advance"
360 );
361 }
362
363 #[test]
364 fn debug_output_names_the_implementations() {
365 assert!(format!("{:?}", WallClock::new()).contains("WallClock"));
366 assert!(format!("{:?}", SeededRng::new(1)).contains("SeededRng"));
367
368 let debug = format!("{:?}", Environment::with_seed(1));
369 assert!(debug.contains("Environment"), "{debug}");
370 assert!(debug.contains("WallClock"), "{debug}");
371 assert!(debug.contains("SeededRng"), "{debug}");
372 }
373}