kv: propagate synthetic timestamps through timestamp cache #57683
Assignees
Labels
A-kv-transactions
Relating to MVCC and the transactional model.
A-multiregion
Related to multi-region
C-enhancement
Solution expected to add code/behavior + preserve backward-compat (pg compat issues are exception)
Comments
nvanbenschoten
added
C-enhancement
nvanbenschoten
added a commit
to nvanbenschoten/cockroach
that referenced
this issue
Dec 11, 2020
Fixes cockroachdb#57683. Before this change, a read with a synthetic timestamp would not pass the synthetic flag through the timestamp cache to conflicting writes. This could cause issues where a write that was bumped by one of these future timestamps would not notice that its write timestamp was now synthetic. This change fixes this by propagating the synthetic flag through the timestamp cache. We have to play a few tricks to make this efficient around `sklPage.ratchetMaxTimestamp`, which attempts to keeping a running maximum of the timestamps in a given skiplist using atomics. The added complexity here is encapsulated in a new `ratchetingTime` type. The testing around here is actually pretty solid. `TestIntervalSklConcurrency` and `TestIntervalSklConcurrentVsSequential` both perform long series of randomized operations and assert against ratchet inversions. This change adds some randomization around synthetic timestamps to the tests and introduces synthetic timestamps to the ratcheting policy (which wasn't otherwise necessary) to get solid randomized test coverage. This made encoding and decoding timestamp cache values slightly slower, but on the order of nanoseconds. ``` name old time/op new time/op delta IntervalSklDecodeValue/logical=false,flags=false,txnID=false-16 11.7ns ± 2% 12.1ns ± 2% +3.52% (p=0.000 n=9+10) IntervalSklDecodeValue/logical=false,flags=false,txnID=true-16 11.7ns ± 1% 12.0ns ± 1% +2.66% (p=0.000 n=10+9) IntervalSklDecodeValue/logical=false,flags=true,txnID=false-16 11.8ns ± 1% 12.1ns ± 2% +3.27% (p=0.000 n=10+9) IntervalSklDecodeValue/logical=false,flags=true,txnID=true-16 11.7ns ± 0% 12.0ns ± 1% +2.82% (p=0.000 n=6+10) IntervalSklDecodeValue/logical=true,flags=false,txnID=false-16 11.7ns ± 2% 12.1ns ± 1% +3.08% (p=0.000 n=10+10) IntervalSklDecodeValue/logical=true,flags=false,txnID=true-16 11.7ns ± 1% 12.1ns ± 2% +3.59% (p=0.000 n=10+10) IntervalSklDecodeValue/logical=true,flags=true,txnID=false-16 11.7ns ± 1% 12.2ns ± 4% +4.11% (p=0.000 n=10+10) IntervalSklDecodeValue/logical=true,flags=true,txnID=true-16 11.7ns ± 2% 12.1ns ± 1% +3.42% (p=0.000 n=10+10) IntervalSklEncodeValue/logical=false,flags=false,txnID=false-16 6.25ns ± 1% 6.52ns ± 1% +4.38% (p=0.000 n=9+10) IntervalSklEncodeValue/logical=false,flags=false,txnID=true-16 6.25ns ± 1% 6.56ns ± 1% +5.00% (p=0.000 n=9+9) IntervalSklEncodeValue/logical=false,flags=true,txnID=false-16 6.23ns ± 2% 6.55ns ± 2% +5.07% (p=0.000 n=10+10) IntervalSklEncodeValue/logical=false,flags=true,txnID=true-16 6.23ns ± 2% 6.56ns ± 4% +5.28% (p=0.000 n=10+10) IntervalSklEncodeValue/logical=true,flags=false,txnID=false-16 6.26ns ± 3% 6.55ns ± 1% +4.66% (p=0.000 n=10+10) IntervalSklEncodeValue/logical=true,flags=false,txnID=true-16 6.24ns ± 1% 6.52ns ± 1% +4.53% (p=0.000 n=9+10) IntervalSklEncodeValue/logical=true,flags=true,txnID=false-16 6.29ns ± 3% 6.53ns ± 2% +3.71% (p=0.000 n=9+10) IntervalSklEncodeValue/logical=true,flags=true,txnID=true-16 6.23ns ± 2% 6.56ns ± 0% +5.26% (p=0.000 n=10+8) name old alloc/op new alloc/op delta IntervalSklDecodeValue/logical=false,flags=false,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=false,flags=false,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=false,flags=true,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=false,flags=true,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=true,flags=false,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=true,flags=false,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=true,flags=true,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=true,flags=true,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=false,flags=false,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=false,flags=false,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=false,flags=true,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=false,flags=true,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=true,flags=false,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=true,flags=false,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=true,flags=true,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=true,flags=true,txnID=true-16 0.00B 0.00B ~ (all equal) name old allocs/op new allocs/op delta IntervalSklDecodeValue/logical=false,flags=false,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=false,flags=false,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=false,flags=true,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=false,flags=true,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=true,flags=false,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=true,flags=false,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=true,flags=true,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=true,flags=true,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=false,flags=false,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=false,flags=false,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=false,flags=true,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=false,flags=true,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=true,flags=false,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=true,flags=false,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=true,flags=true,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=true,flags=true,txnID=true-16 0.00 0.00 ~ (all equal) ```
craig bot
pushed a commit
that referenced
this issue
Jan 6, 2021
57811: kv/tscache: propagate synthetic timestamps through timestamp cache r=nvanbenschoten a=nvanbenschoten Fixes #57683. Before this change, a read with a synthetic timestamp would not pass the synthetic flag through the timestamp cache to conflicting writes. This could cause issues where a write that was bumped by one of these future timestamps would not notice that its write timestamp was now synthetic. This change fixes this by propagating the synthetic flag through the timestamp cache. We have to play a few tricks to make this efficient around `sklPage.ratchetMaxTimestamp`, which attempts to keeping a running maximum of the timestamps in a given skiplist using atomics. The added complexity here is encapsulated in a new `ratchetingTime` type. The testing around here is actually pretty solid. `TestIntervalSklConcurrency` and `TestIntervalSklConcurrentVsSequential` both perform long series of randomized operations and assert against ratchet inversions. This change adds some randomization around synthetic timestamps to the tests and introduces synthetic timestamps to the ratcheting policy (which wasn't otherwise necessary) to get solid randomized test coverage. This made encoding and decoding timestamp cache values slightly slower, but on the order of nanoseconds. ``` name old time/op new time/op delta IntervalSklDecodeValue/logical=false,flags=false,txnID=false-16 11.7ns ± 2% 12.1ns ± 2% +3.52% (p=0.000 n=9+10) IntervalSklDecodeValue/logical=false,flags=false,txnID=true-16 11.7ns ± 1% 12.0ns ± 1% +2.66% (p=0.000 n=10+9) IntervalSklDecodeValue/logical=false,flags=true,txnID=false-16 11.8ns ± 1% 12.1ns ± 2% +3.27% (p=0.000 n=10+9) IntervalSklDecodeValue/logical=false,flags=true,txnID=true-16 11.7ns ± 0% 12.0ns ± 1% +2.82% (p=0.000 n=6+10) IntervalSklDecodeValue/logical=true,flags=false,txnID=false-16 11.7ns ± 2% 12.1ns ± 1% +3.08% (p=0.000 n=10+10) IntervalSklDecodeValue/logical=true,flags=false,txnID=true-16 11.7ns ± 1% 12.1ns ± 2% +3.59% (p=0.000 n=10+10) IntervalSklDecodeValue/logical=true,flags=true,txnID=false-16 11.7ns ± 1% 12.2ns ± 4% +4.11% (p=0.000 n=10+10) IntervalSklDecodeValue/logical=true,flags=true,txnID=true-16 11.7ns ± 2% 12.1ns ± 1% +3.42% (p=0.000 n=10+10) IntervalSklEncodeValue/logical=false,flags=false,txnID=false-16 6.25ns ± 1% 6.52ns ± 1% +4.38% (p=0.000 n=9+10) IntervalSklEncodeValue/logical=false,flags=false,txnID=true-16 6.25ns ± 1% 6.56ns ± 1% +5.00% (p=0.000 n=9+9) IntervalSklEncodeValue/logical=false,flags=true,txnID=false-16 6.23ns ± 2% 6.55ns ± 2% +5.07% (p=0.000 n=10+10) IntervalSklEncodeValue/logical=false,flags=true,txnID=true-16 6.23ns ± 2% 6.56ns ± 4% +5.28% (p=0.000 n=10+10) IntervalSklEncodeValue/logical=true,flags=false,txnID=false-16 6.26ns ± 3% 6.55ns ± 1% +4.66% (p=0.000 n=10+10) IntervalSklEncodeValue/logical=true,flags=false,txnID=true-16 6.24ns ± 1% 6.52ns ± 1% +4.53% (p=0.000 n=9+10) IntervalSklEncodeValue/logical=true,flags=true,txnID=false-16 6.29ns ± 3% 6.53ns ± 2% +3.71% (p=0.000 n=9+10) IntervalSklEncodeValue/logical=true,flags=true,txnID=true-16 6.23ns ± 2% 6.56ns ± 0% +5.26% (p=0.000 n=10+8) name old alloc/op new alloc/op delta IntervalSklDecodeValue/logical=false,flags=false,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=false,flags=false,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=false,flags=true,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=false,flags=true,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=true,flags=false,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=true,flags=false,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=true,flags=true,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklDecodeValue/logical=true,flags=true,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=false,flags=false,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=false,flags=false,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=false,flags=true,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=false,flags=true,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=true,flags=false,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=true,flags=false,txnID=true-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=true,flags=true,txnID=false-16 0.00B 0.00B ~ (all equal) IntervalSklEncodeValue/logical=true,flags=true,txnID=true-16 0.00B 0.00B ~ (all equal) name old allocs/op new allocs/op delta IntervalSklDecodeValue/logical=false,flags=false,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=false,flags=false,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=false,flags=true,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=false,flags=true,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=true,flags=false,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=true,flags=false,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=true,flags=true,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklDecodeValue/logical=true,flags=true,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=false,flags=false,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=false,flags=false,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=false,flags=true,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=false,flags=true,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=true,flags=false,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=true,flags=false,txnID=true-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=true,flags=true,txnID=false-16 0.00 0.00 ~ (all equal) IntervalSklEncodeValue/logical=true,flags=true,txnID=true-16 0.00 0.00 ~ (all equal) ``` Co-authored-by: Nathan VanBenschoten <nvanbenschoten@gmail.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Needed for non-blocking transactions: #52745.
Currently, a read with a synthetic timestamp does not pass the synthetic flag through the timestamp cache to conflicting writes. It should.
The text was updated successfully, but these errors were encountered: