3 ms·

If the two transactions don't have any overlapping splits then their relative timestamps can be anything, as long as there is no causality created between them

If the two transactions don't have any overlapping splits then their relative timestamps can be anything, as long as there is no causality created between them outside the system. Only if there is causality between them do their timestamps have to be in a certain order. Causality outside the system can only be created if the commit time of one transaction is strictly before the arrive time of the other transaction. As stated in my earlier post, there are no ordering guarantees for transactions that are sent one after the other to the database, if the first one wasn't commit-acked before the second one was sent. To my knowledge, no database in the world (single-node or distributed) offers such a guarantee, at least for transactions sent by different client processes. This is where a lot of people trip up. So if you have a for-loop from 1 to 10 that async sends 10 transactions (and you're not waiting for ack before sending the next one), those 10 transactions can be ordered/timestamped/applied in any order by the database and this would be correct behavior by even the strictest database models. In Spanner if two transactions have overlapping splits then there will be locking and they will be correctly serialized since Spanner is not multi-leader. The same row cannot be written to by different Spanner machines at the same real-world time. Your observation is actually correct - the timestamp order in Spanner will not perfectly reflect the order in which the transactions were written to the underlying data structure. But my point is that it doesn't need to because the way Spanner does it is still maximally correct.

olafA 3y ago
Thank you for taking the time to explains this. I am still a bit confused, if external consistency is not trying to solve global serial order, but only solving read from client point of view, such that all committed transaction before read timestamp will be returned and none of the transaction after read timestamp will be returned. I am confused on why each data node have to wait 7ms to commit, isn't it easier to ask whichever client is reading to read from the maximum uncertainty timestamp? Assume the following example nodeA is on time trxA arrive nodeA at (true time 7ms, A time 7ms, B time 0ms) trxA commit by nodeA at (true time 8ms, A time 8ms, B time 1ms) nodeB lag by 7ms trxB arrive nodeB at (true time 9ms, A time 9ms, B time 2ms) trxB is commit by nodeB at (true time 10ms, A time 10ms, B time 3ms) nodeD ahead by 7ms trxD arrive nodeD at (true time 9ms, D time 16ms, B time 2ms, A time 9ms) trxD commit by nodeD at (true time 10ms, D time 17ms, B time 3ms, A time 10ms) For example if client C is reading and client C lags real world time by 7ms ClientC ask to read node A and B for transaction on real-world time 11ms local time 4ms instead to ask all transaction before 4ms, ClientC will ask all transaction before 4ms + 2x_uncertainty(14ms) = 18ms trxA(8ms) < 18ms -> trxA will be read trxB(3ms) < 18ms -> trxB will be read trxD(17ms) < 18ms -> trxD will be read Instead of asking each node to wait to commit timestamp, this guarantees any commit happened before read in real-world time is read, and none of the commit happend after read in real-world is read (since we are requesting read at the time read happens)

olafA 3y ago

Thank you for taking the time to explains this. I am still a bit confused, if external consistency is not trying to solve global serial order, but only solving read from client point of view, such that all committed transaction before read timestamp will be returned and none of the transaction after read timestamp will be returned. I am confused on why each data node have to wait 7ms to commit, isn't it easier to ask whichever client is reading to read from the maximum uncertainty timestamp? Assume the following example nodeA is on time trxA arrive nodeA at (true time 7ms, A time 7ms, B time 0ms) trxA commit by nodeA at (true time 8ms, A time 8ms, B time 1ms) nodeB lag by 7ms trxB arrive nodeB at (true time 9ms, A time 9ms, B time 2ms) trxB is commit by nodeB at (true time 10ms, A time 10ms, B time 3ms) nodeD ahead by 7ms trxD arrive nodeD at (true time 9ms, D time 16ms, B time 2ms, A time 9ms) trxD commit by nodeD at (true time 10ms, D time 17ms, B time 3ms, A time 10ms) For example if client C is reading and client C lags real world time by 7ms ClientC ask to read node A and B for transaction on real-world time 11ms local time 4ms instead to ask all transaction before 4ms, ClientC will ask all transaction before 4ms + 2x_uncertainty(14ms) = 18ms trxA(8ms) < 18ms -> trxA will be read trxB(3ms) < 18ms -> trxB will be read trxD(17ms) < 18ms -> trxD will be read Instead of asking each node to wait to commit timestamp, this guarantees any commit happened before read in real-world time is read, and none of the commit happend after read in real-world is read (since we are requesting read at the time read happens)