Reads at timestamps higher than the current MaxAssigned (MA) must block to ensure the writes up until the read timestamp are applied. Txn 2 receives start ts 3, and a read at ts 3 must acknowledge any writes up to ts 2.
My questions are:
Does this mean all reads (across all alphas) with a higher start timestamp are blocked until a write from a lower start timestamp is applied—even if those reads are unrelated to the data being written in the transaction?
If the answer to the previous question is yes, doesn’t this negatively affect database performance? Even if we go out of our way to keep transactions as short as possible, it seems like it would be easy to get in trouble with blocking reads.
After reviewing the white paper again, and looking a little more closely at the diagram in my first post, I think I may have answered my own question.
Reads with a higher start timestamp will not block for the entire duration of a write transaction, just from the time that the commit is requested and applied—which should be a tiny fraction of the entire write transaction.
For example, suppose a write transaction called Txn A is started (s in the diagram below) with a timestamp of 1. Now suppose a read transaction called Txn B arrives with a timestamp of 2 before the request to commit Txn A (c in the diagram below).
Since the commit has not started for Txn A yet, the read for Txn B is not blocked.
Now suppose a commit (c) is issued for Txn A, and a new read transaction named Txn C arrives with a timestamp of 4 right at the moment between the commit (c) starting and being applied (a) for Txn A.
In this case, the read for Txn C will be blocked between (c) and (a).
1 3 3
Txn A----●---------------◯-●-----
s c a
2
Txn B------------●---------------
4
Txn C---------------------●------
A simpler way to understand this is – an Alpha would block any read with start ts > max assigned as seen by the Alpha.
Zero maintains a MaxAssigned timestamp, which it streams to Alphas, along with all the records of start → Commit ts, guaranteeing that if MA = 100, then Zero has streamed all txns with Tcommit <= 100 as well (of course having guaranteed their persistence and high availability).
In your example, txn A has start ts = 1, so MA becomes 1. Then Txn B gets start ts = 2, then MA becomes 2. Typically Alpha would receive both of these MAs really quickly (micro-seconds), so reads with start ts = 1 and 2 can proceed.
When Txn A wants to commit, it would a new commit ts = 3, with MA now becoming 3. At the same time, a new start ts is given to Txn C, with MA becoming 4. That MA=4 can’t be streamed out immediately. That’s because Zero has to achieve quorum on the commit, so if Zero dies, we don’t lose that info. It would run quorum on 1-> 3 (start → commit), which might take milliseconds, and thus delay the stream of MA = 4. That’s when Txn C could get delayed in starting its read.
Other ways, reads could be delayed is of course, if Alpha falls behind wrt MA.
