Rethinking multi-grain timestamps [LWN.net]

Rethinking multi-grain timestamps

Posted Oct 10, 2023 2:45 UTC (Tue) by NYKevin (subscriber, #129325)
In reply to: Rethinking multi-grain timestamps by Wol
Parent article: Rethinking multi-grain timestamps

> At which point, don't you now get caught by relativity? :-)

Not yet. The next logical step down from 1 ms resolution is 100 µs resolution, but as long as both machines are within thirty kilometers[1] of each other, the events in question are separated by a timelike interval, and so all observers will agree about the order in which they happen.

That's not to say this never becomes a problem (obviously there are pairs of computers that are separated by more than thirty kilometers), but there are several objections to the "relativity" argument:

* The average LAN is way too small for this to be a problem, so LAN users can disregard relativity altogether unless we want to go to hundreds-of-nanoseconds precision or better.
* Even when relativity is a problem, you always have the option of selecting an arbitrary reference frame (like, say, the ITRF[2]), and declaring that to be the "right" reference frame, applying local corrections as needed, so you can still have a total ordering on events. Some observers will disagree with that ordering, but...
* ...in practice, the observers who disagree with your chosen ordering are either moving relative to your chosen reference frame, or they are experiencing a different level of gravity (because they're in space and your reference frame is not, or something along those lines). Data centers on Earth are not really moving relative to each other at significant speed, and surface variations in the Earth's gravity are quite small as well, so data centers will generally agree on the order in which events happen, even if they are separated by large distances. The "local corrections" that we need to do are entirely trivial, and amount to backsolving for the light-speed delay. Admittedly, this is a much harder problem if you want to build a data center on the Moon, or Mars, but we're not doing that yet.
* If all else fails, you adopt the TrueTime[3] data model and report time intervals instead of time stamps (i.e. instead of saying "it is exactly 14:00:00.000," you report something like "it is no earlier than 14:00:00.000 and no later than 14:00:00.007"). You can then account for all relativity of simultaneity by including it as part of the uncertainty (and always reporting relative to some arbitrary fixed reference frame, regardless of what the local reference frame looks like). This probably does make performance somewhat worse in some deployment scenarios (e.g. on Mars), but it has already been widely deployed as part of Spanner, so we know that it correctly solves the general "I don't know exactly what time it is" problem, regardless of whether that problem comes from relativity, clock skew, or some combination of the two.

[1]: https://www.wolframalpha.com/input?i=distance+light+trave...
[2]: https://en.wikipedia.org/wiki/International_Terrestrial_R...
[3]: https://static.googleusercontent.com/media/research.googl...

Disclaimer: I work for Google, and the service I manage uses Spanner as a backend.

to post comments

Rethinking multi-grain timestamps

Posted Oct 10, 2023 7:24 UTC (Tue) by Wol (subscriber, #4433) [Link] (3 responses)

> > At which point, don't you now get caught by relativity? :-)

> Not yet. The next logical step down from 1 ms resolution is 100 µs resolution, but as long as both machines are within thirty kilometers[1] of each other, the events in question are separated by a timelike interval, and so all observers will agree about the order in which they happen.

Fascinating! Yes really. But I think maybe I should have used the word "causality" rather than "relativity". My bad ...

But what I was trying to get at, is that if that distance is greater than your thirty kilometers, either you don't actually need to know the order, or any attempt to assign an order is essentially throwing dice at random. (I think about that with regard to distributed databases, and I'd certainly try to localise the problem to avoid those network effects ...)

At the end of the day, humans don't like it when the people who know say "it's unknowable". And in the example we appear to be discussing here, "make" running across a distributed file system, I find it hard to grasp how you can make the required sequential determinism work over the randomness of parallel file saves. If the system is running fast enough, or the network is large enough, the results will by the laws of physics be random, and any attempt to solve the problem is doomed to failure.

From what you're saying, we're nowhere near that limit yet, but we might get better results if we planned for hitting it, rather than pretending it's not there.

Cheers,
Wol

Rethinking multi-grain timestamps

Posted Oct 10, 2023 7:43 UTC (Tue) by NYKevin (subscriber, #129325) [Link] (2 responses)

> But what I was trying to get at, is that if that distance is greater than your thirty kilometers, either you don't actually need to know the order, or any attempt to assign an order is essentially throwing dice at random.

No, that is not what relativity says. Relativity says that the order is *arbitrary*, not that it is random. There is no randomness introduced by events separated by spacelike intervals - you can and should just pick your favorite reference frame, and use Lorentz transformations to correct all observations in other frames to match it. This is an entirely deterministic mathematical process which will produce a total ordering of all events (unless your chosen reference frame says they are exactly simultaneous, which can be disregarded since your measurements are not perfectly precise anyway).

> At the end of the day, humans don't like it when the people who know say "it's unknowable". And in the example we appear to be discussing here, "make" running across a distributed file system, I find it hard to grasp how you can make the required sequential determinism work over the randomness of parallel file saves. If the system is running fast enough, or the network is large enough, the results will by the laws of physics be random, and any attempt to solve the problem is doomed to failure.

Yes, but this is not about relativity. This is about "I don't know how fast my network/SSD/whatever runs," or "I don't know how wrong my clock is." Those are much older problems, which have been well-understood in the world of distributed systems for decades. The most common approach is to use something like Paxos, Raft, or CRDTs, all of which explicitly establish "happens-before" relationships as a natural part of their consensus/convergence algorithms. Or, to put it in even simpler terms: The way you make sure X happens before Y is to have the computers responsible for X and Y talk to each other and arrange for that to be the case.[1]

[1]: It should be acknowledged that this is harder than it sounds. If you only have two computers, it may well be completely intractable, for some definitions of "talk to each other" - see the "two generals problem." But there are versions of this problem which are more tractable, and modern distributed systems are built around solving those versions of the problem.

Rethinking multi-grain timestamps

Posted Oct 10, 2023 12:33 UTC (Tue) by Wol (subscriber, #4433) [Link] (1 responses)

> you can and should just pick your favorite reference frame, and use Lorentz transformations to correct all observations in other frames to match it.

I'm thinking humans here. And stock markets. Where $billions could hang on the precise ordering of events. :-)

And yes, I know that in our macro world all reference frames are - to all intents and purposes - the same. But as soon as you say "pick your favourite frame", you're going to get people fighting for the one that is to their personal advantage.

Which is my point. As clocks get faster (the point of this article) and distances get greater (we're talking about a network), the greater the importance of the chosen reference frame, which is a matter of politics not maths. Which means we cannot appeal to logic for a solution.

Cheers,
Wol

Rethinking multi-grain timestamps

Posted Oct 10, 2023 16:11 UTC (Tue) by wittenberg (guest, #4473) [Link]

At this point, you need some old guy to point out the definitive discussion of this: Time, Clocks, and the Ordering of Events in a Distributed System
https://lamport.azurewebsites.net/pubs/time-clocks.pdf (1978) by Leslie Lamport. As you would expect from him, it's beautifully written. Everybody concerned with this issue should read it.

--David