Ask HN: How does waiting 7ms help GCP spanner in external consistency?
1 comments
No database in the world guarantees any deterministic ordering for two transactions where the invocation-to-acknowledgement timespans overlap. Such transactions are considered concurrent and even a fully linearizable database can order them however it wants without losing correctness.
In your second example, trxA and trxB are concurrent because at real-world time 9ms, trxA hasn't yet committed.
And therein lies the reason why Spanner waited 7ms. Spanner forced those transactions to become concurrent by making trxA wait, thereby making the anomaly of trxA having a greater commit time than trxB due to clock skew between nodeA and nodeB correct as per the semantic guarantees of linearizability (or what Spanner calls "external consistency").
Had it not waited, trxA's timestamp (7ms nodeA time) would've been greater than trxB's timestamp (2ms nodeB time) even though trxA was acked back to the client before trxB was invoked by the client. This would be incorrect behavior.
In your second example, trxA and trxB are concurrent because at real-world time 9ms, trxA hasn't yet committed.
And therein lies the reason why Spanner waited 7ms. Spanner forced those transactions to become concurrent by making trxA wait, thereby making the anomaly of trxA having a greater commit time than trxB due to clock skew between nodeA and nodeB correct as per the semantic guarantees of linearizability (or what Spanner calls "external consistency").
Had it not waited, trxA's timestamp (7ms nodeA time) would've been greater than trxB's timestamp (2ms nodeB time) even though trxA was acked back to the client before trxB was invoked by the client. This would be incorrect behavior.
please bear with me on this, running through the example even when the wait kicked in trxA's timestamp (14ms nodeA time) is still greater than trxB's timestamp (9ms nodeB time) which violate gcp's definition of external consistency?
> To be externally consistent, a transaction must see the effects of all the transactions that complete before it and none of the effects of transactions that complete after it, in the global serial order
Example when both node waited
No wait example
in both cases localtime(trxA) > localtime(trxB) , external consistency is not achieved?
and in the no wait example the transactions are not concurrent, only when it waited it became concurrent?
I must be missing something here?
> To be externally consistent, a transaction must see the effects of all the transactions that complete before it and none of the effects of transactions that complete after it, in the global serial order
Example when both node waited
real-world time = 7ms
node A local time = 7ms
node B local time = 0ms
trxA arrive nodeA at (real-world time 7ms, A time 7ms, B time 0ms)
wait 7ms before commit
trxA commit by nodeA at (real-world time 14ms, A time 14ms, B time 7ms)
trxB arrive nodeB at (real-world time 9ms, A time 9ms, B time 2ms)
wait 7ms before commit
trxB is commit by nodeB at (real-world time 16ms, A time 16ms, B time 9ms)
No wait example
real-world time = 7ms
node A local time = 7ms
node B local time = 0ms
trxA arrive nodeA at (real-world time 7ms, A time 7ms, B time 0ms)
trxA take 1ms to commit
trxA commit by nodeA at (real-world time 8ms, A time 8ms, B time 1ms)
trxB arrive nodeB at (real-world time 9ms, A time 9ms, B time 2ms)
trxB take 1ms to commit
trxB is commit by nodeB at (real-world time 10ms, A time 10ms, B time 3ms)
in both cases localtime(trxA) > localtime(trxB) , external consistency is not achieved?
and in the no wait example the transactions are not concurrent, only when it waited it became concurrent?
I must be missing something here?
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.
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.
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
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)
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
https://cloud.google.com/blog/products/databases/strict-serializability-and-external-consistency-in-spanner
> To be externally consistent, a transaction must see the effects of all the transactions that complete before it and none of the effects of transactions that complete after it, in the global serial order
My understanding why distributed transaction need synchronized clock to gain external consistency is the following
Assume NTP max drift is 250ms
the following transaction will run into conflicted sequence
now there is a conflict in transaction time between transactionA and transactionB
transaction A is processed before transaction B , but because node B lag node A by 100ms transactionB is now considered to be processed before transactionA
Spanner have atomic clock that guarantees max time drift to be 7ms, and it waits this max uncertainty time of 7ms before commit. But how does that fundamentally solve the issue?
For example https://www.cockroachlabs.com/blog/living-without-atomic-clocks/
> So how does Spanner use TrueTime to provide linearizability given that there are still inaccuracies between clocks? It’s actually surprisingly simple. It waits. Before a node is allowed to report that a transaction has committed, it must wait 7ms. Because all clocks in the system are within 7ms of each other, waiting 7ms means that no subsequent transaction may commit at an earlier timestamp, even if the earlier transaction was committed on a node with a clock which was fast by the maximum 7ms. Pretty clever.
My interpretation from the articles is the following
In this example 7ms wait doesn't solve the problem, trxB is still committed at 9ms (local nodeB time) trxA is committed at 14ms (local nodeA time)
The conflict of trxB committed before trxA still exist, time(trxB) < time(trxA) even though trxB occur after trxA in real-world time
What am i missing here?