Rethinking multi-grain timestamps

Surely, if the latency of a message passing between two computers is greater than the time between two events, one happening on one computer, and the other event on the other computer, it's exactly the same. Asking "which came first" is a stupid question, even if the speed of light does mean that an answer is possible (which is not guaranteed).

Cheers,
Wol

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.

"Relativity" is not some pixie dust you can sprinkle over your argument to handwave away the need to think, unfortunately.

To actually answer the question, yes at some point you need to take relativistic effect into account if you need really accurate time synchronization. Gravitational time dilation, meaning that your clock ticks faster or slower depending on the altitude (strength of the gravitational field), is a thing. Likewise, if two clocks are moving at significant velocity with respect to each other (say, GPS satellites) you start seeing relativistic effects.

But just signals propagating between fixed locations A and B at finite speed does not need any relativity. If you can measure the propagation delay between the two locations, you can agree on a common reference time. That's how e.g. TAI (https://en.wikipedia.org/wiki/International_Atomic_Time ) works, with super accurate atomic clocks spread out all over the world agreeing on a common reference time scale. (Just to clarify, the atomic clocks participating in TAI do account for gravitational time dilation; my point is that fixed clocks separated by some distance is not some unsolvable relativistic mystery.)

> Two events, happening separated by space, you just can NOT always tell which happened first. End of. Tough.

From your, no doubt, extensive studies of relativity you should know that is an ill posed statement. What relativity actually tells us is that there is no absolute time scale in the universe, it's all, drumroll, relative. However, for any particular observer, the order in which the observer sees events IS well defined. And thus two observers, knowing their distance and velocity with respect to each other can agree on a common time scale and they can calculate in which order, and when, the other sees events (which might not be the same in which it itself sees them).

> I think as soon as you have events happening to the same file system, from different computers, you just have to accept that knowing for sure which one happened first is a fool's errand. Some times you just have to accept that the Universe says NO!

Practically speaking, the problem is not so much that relativity is this mysterious force that prevents us from knowing, but rather that things like computers themselves as well as signal propagation in computer networks is subject to a lot of timing variation. Time synchronization protocols like NTP and PTP do a lot of clever filtering etc. to reduce that noise, but obviously can't reduce it to zero.

Another practical problem wrt ordering events is that if you have a bunch of timestamped events (which, as mentioned above, we can agree to a common timescale to a relatively high accuracy) coming in from a number of sources, one must wait for at least the propagation delay before one can be certain about the relative ordering of the events. Well, there are a numbers of approaches to dealing with agreeing upon a common event ordering in a distributed system, like the Google Spanner mentioned in a sibling comment, two-phase commit, and whatnot. They all tend to have drawbacks compared to a purely local system that doesn't need to care about such issues.