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}