Explain temporal reversal anomaly

[jseldess]

In the FAQ, we say that read-write transactions using SSI will never result in anomalies. But there is still timestamp reversal, which we need to explain somewhere, probably in the docs on transactions.

cc: @tschottdorf

[glycerine]

Curious what this is; is this a known anomoly in the database literature?

[spencerkimball]

It's something which can happen to a distributed database which supports serializable isolation by not linearizable. There's an explanation of it in this blog post: https://www.cockroachlabs.com/blog/living-without-atomic-clocks/

On Thu, Mar 17, 2016 at 12:58 PM, Jason E. Aten, Ph.D. < notifications@github.com> wrote:

Curious what this is; is this a known anomoly in the database literature?

— You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub https://github.com/cockroachdb/docs/issues/124#issuecomment-197973639

[glycerine]

Thanks @spencerkimball , that's a great writeup!

the token serves as a minimum timestamp for successive transactions and will guarantee that each has a properly ordered commit timestamp.

are timestamps nanosecond resolution (e.g. Go's time.Time?) If not, what resolution is used?

Crucially, the upper bound doesn’t change on restart, so the window of uncertainty shrinks. Transactions reading constantly updated data from many nodes might be forced to restart multiple times, though never for longer than the upper bound, nor more than one time per node.

Ideally I would like to see a proof of this liveness claim, under the assumption of byzantine node failure pattern. TLA+ specification perhaps?

[spencerkimball]

On Thu, Mar 17, 2016 at 2:31 PM, Jason E. Aten, Ph.D. < notifications@github.com> wrote:

Thanks @spencerkimball https://github.com/spencerkimball , that's a great writeup!

the token serves as a minimum timestamp for successive transactions and will guarantee that each has a properly ordered commit timestamp.

are timestamps nanosecond resolution (e.g. Go's time.Time?) If not, what resolution is used?

There are two parts to a timestamp: unix nanoseconds (Go's time.Time) as well as a logical component which is an additional 32 bits.

Crucially, the upper bound doesn’t change on restart, so the window of uncertainty shrinks. Transactions reading constantly updated data from many nodes might be forced to restart multiple times, though never for longer than the upper bound, nor more than one time per node.

Ideally I would like to see a proof of this liveness claim, under the assumption of byzantine node failure pattern. TLA+ specification perhaps?

Well the code simply refuses to restart beyond that originally established max timestamp, ergo you'll finally just run the transaction without anymore timestamp uncertainty and finish it. Not sure if this requires a proof, though one wouldn't hurt. There are other reasons transactions can restart though, and proving liveness under byzantine failures & concurrency there is far murkier water. I wouldn't make the claim of liveness with those piled on.

[jseldess]

You might cover this in your work on distributed transactions, @sploiselle.

[jseldess]

Since we haven't worked on this or gotten questions on this topic, I'll close this issue for now.