clt_database/mvcc/
clock.rs

1use crate::sync::Mutex;
2
3/// No-op callback for use with [`LogicalClock::get_timestamp`] when no
4/// action needs to be taken atomically alongside timestamp generation
5/// (e.g. for begin timestamps).
6pub fn no_op(_: u64) {}
7
8/// Logical clock.
9pub trait LogicalClock: Send + Sync {
10    /// Generates the next timestamp, calls `f` with it, then returns it.
11    ///
12    /// Implementations that guard concurrent commit protocols (e.g.
13    /// [`MvccClock`]) hold their internal lock across the `f` call, so
14    /// that the timestamp is published (e.g. stored as `Preparing(ts)`)
15    /// before any other caller can observe a timestamp.
16    ///
17    /// Pass [`no_op`] when no atomic side-effect is needed (begin timestamps).
18    fn get_timestamp<F: FnOnce(u64)>(&self, f: F) -> u64;
19    fn reset(&self, ts: u64);
20}
21
22/// A mutex-guarded clock for concurrent MVCC use.
23///
24/// The lock is held across the `f` callback in [`get_timestamp`], ensuring
25/// that a commit timestamp is published (e.g. stored as `Preparing(ts)`)
26/// before any other transaction can generate a higher timestamp. This closes
27/// the TOCTOU window between timestamp generation and `Preparing` state
28/// publication in the commit protocol.
29///
30/// ## Speculative reads
31///
32/// We have speculative reads (and speculative ignores). That is, an active
33/// transaction can see changes of another transaction which is in the
34/// **preparing** phase. Assuming the other transaction successfully commits,
35/// the active transaction continues to make progress. If the other transaction
36/// gets aborted, then the active transaction needs to be aborted as well.
37///
38/// So, say `tx2` starts at `begin_ts(11)` and another transaction `tx1`,
39/// started earlier, is now in its preparing phase with `end_ts(10)`. Once the
40/// `end_ts` is assigned, that will be the final commit timestamp of that
41/// transaction. So `tx2` should see changes made by `tx1`, since `tx1` was
42/// committed (in logical time) before `tx2` started.
43///
44/// Whether `tx2` can see `tx1`'s changes depends on when `tx1` acquired the
45/// `end_ts` timestamp during the preparing phase.
46///
47/// > **Note:** We need speculative reads, otherwise it's difficult to make
48/// > the MVCC model work without blocking. I made an attempt in
49/// > [turso#5198](https://github.com/tursodatabase/turso/pull/5198) but this
50/// > introduced a subtle bug which violated snapshot isolation. So without speculative
51/// > reads in the previous example, `tx2` needs to wait till `tx1` is committed or
52/// > aborted.
53///
54/// ### Need for atomicity
55///
56/// We want to atomically generate `end_ts` and publish `Preparing(end_ts)`
57/// while the clock lock is held. This closes the TOCTOU window.
58///
59/// Consider the example:
60///
61/// ```text
62/// tx1 (Active):    generates end_ts = 10
63/// tx2 (Active):    gets begin_ts = 11
64/// tx2 (Active):    does queries but does not see changes by tx1 (tx1 is still Active)
65/// tx1 (Preparing): stores Preparing(end_ts=10)
66/// tx2 (Active):    queries again, now it can see changes by tx1 (tx1 is now Preparing)
67/// ```
68///
69/// **This is a snapshot isolation violation** — `tx2` observes different
70/// values for the same rows within the same transaction.
71///
72/// So we want the following two operations to be atomic:
73///
74/// ```text
75/// let ts = get_timestamp()
76/// store Preparing(ts)
77/// ```
78///
79/// `tx2` must get its begin timestamp either **before** or **after** these
80/// two operations. If it interleaves, the above bug happens.
81///
82/// ## Note on the Hekaton paper
83///
84/// The Hekaton paper doesn't mention this "gotcha". The paper says:
85///
86/// > "When the transaction has completed its normal processing and requests
87/// > to commit, it acquires an end timestamp and switches to the Preparing
88/// > state."
89///
90/// But it doesn't go into more detail about atomicity here.
91#[derive(Debug, Default)]
92pub struct MvccClock {
93    inner: Mutex<u64>,
94}
95
96impl MvccClock {
97    pub fn new() -> Self {
98        Self {
99            inner: Mutex::new(0),
100        }
101    }
102
103    /// Generate a begin timestamp. No side-effect needed alongside generation.
104    pub fn get_begin_timestamp(&self) -> u64 {
105        self.get_timestamp(no_op)
106    }
107
108    /// Generate a commit timestamp and call `f` with it while the lock is
109    /// held, atomically publishing the timestamp before releasing.
110    pub fn get_commit_timestamp<F: FnOnce(u64)>(&self, f: F) -> u64 {
111        self.get_timestamp(f)
112    }
113}
114
115impl LogicalClock for MvccClock {
116    fn get_timestamp<F: FnOnce(u64)>(&self, f: F) -> u64 {
117        let mut guard = self.inner.lock();
118        let ts = *guard;
119        *guard += 1;
120        f(ts);
121        ts
122    }
123
124    fn reset(&self, ts: u64) {
125        *self.inner.lock() = ts;
126    }
127}
clt_database/mvcc/clock.rs

clt_database/mvcc/
clock.rs
