Lockless algorithms for mere mortals

Posted Jul 29, 2020 17:58 UTC (Wed) by NYKevin (subscriber, #129325)
In reply to: Lockless algorithms for mere mortals by ras
Parent article: Lockless algorithms for mere mortals

> In contrast, if they independently observe A caused B they don't need to be in contact to know they agree on the ordering. They can be certain the other one saw A caused B without every meeting to agree on it.

There's also the Spanner approach (put atomic clocks in all of your datacenters, get them all nice and synchronized, and then everyone can agree that A happens-before B because A and B are both timestamped and you know the resolution of your clocks is finer than the difference between those timestamps). But that requires hardware support, because regular clocks are insufficiently precise for timestamping to be useful in most realistic applications. Also, this is clearly useless for something like multicore concurrency within a single machine (you're not sticking an atomic clock on each core, that would be ridiculous).

Lockless algorithms for mere mortals

Posted Jul 29, 2020 19:40 UTC (Wed) by Wol (subscriber, #4433) [Link] (2 responses)

Except that time depends on velocity, and velocity depends on gravity, and and and. So the only way to synchronize time in all your datacentres is to have only one large datacentre.

Except that then you know that the 1st floor has time moving at a different speed to the ground floor, and probably the front wall is moving at a different speed to the back ...

Cheers,
Wol

Lockless algorithms for mere mortals

Posted Jul 29, 2020 21:53 UTC (Wed) by NYKevin (subscriber, #129325) [Link]

Spanner is not hypothetical. Google is both using it internally, and selling it on GCP (at an extortionate rate, but it is there if you really want it). It actually works as I described. The simple reality is that relativistic effects are too small to matter when you're operating on the scale of milliseconds, on a single planet. If you want to set up datacenters on Mars, or synchronize things at the nanosecond level, then you might have a problem.

(Disclaimer: I work for Google. I do *not* get paid to promote Spanner or any other Google product.)

Lockless algorithms for mere mortals

Posted Aug 1, 2020 16:35 UTC (Sat) by anton (subscriber, #25547) [Link]

All the data centers are at rest wrt each other, and wrt to the events they observe (Earth rotation may be an issue, but not at the ms resolution they work with). Differences in the gravity field are miniscule, but even if they were significant, they would only change the time scale, not the order of events; and scale can be corrected by scaling the measured time to correct for this effect.

Lockless algorithms for mere mortals

Posted Jul 30, 2020 13:05 UTC (Thu) by sriram_srinivasan (guest, #140506) [Link] (1 responses)

Even Spanner's clocks have uncertainty in the millisecond range (7ms according to the paper), which is the reason for "commit wait". It has a considerable effect on throughput and latency. There are other options that rely on causal clocks and other ways of structuring transactions -- the Calvin database comes to mind -- that don't have to pay this penalty.

Lockless algorithms for mere mortals

Posted Jul 30, 2020 15:15 UTC (Thu) by NYKevin (subscriber, #129325) [Link]

Well sure, it's just software, not magical pixie dust. I was responding to the assertion that you need a causal relationship between A and B to order them, which is simply untrue.