Lockless algorithms for mere mortals

Posted Jul 29, 2020 0:30 UTC (Wed) by Cyberax (✭ supporter ✭, #52523)
In reply to: Lockless algorithms for mere mortals by ras
Parent article: Lockless algorithms for mere mortals

> I am no physicist, but causation looks to be the bare minimum that needs to be preserved to have an objective reality. By that I mean if it isn't possible to agree on A caused B, then it becomes impossible to have a shared truth. If we can not agree on what is true, there is no shared reality.
That's not quite true in distributed systems. There's a class of data structures that achieve a consensus without strict ordering: https://en.wikipedia.org/wiki/Conflict-free_replicated_da...

Lockless algorithms for mere mortals

Posted Jul 29, 2020 1:09 UTC (Wed) by ras (subscriber, #33059) [Link] (6 responses)

Yes, they can reach a consensus. But they can't do that unless they exchange information after the fact. Until that point they have two sets of observations that don't agree. It's only after they meet that they can decide what they will agree on.

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.

The example the wikipedia article you linked to is an excellent example. The database they must agree on is a single bit. The update performed is to set the bit to 1 if an event occurs, but since it is a distributed system that event may not be seen by some databases, so some "observe" 0, and some observe a 1. Clearly that is different. To agree they observers must meet and then follow the logic "since it is never reset to 0, and since one participant saw the event happen it must have happened, ergo after meeting we can all agree on 1".

Lockless algorithms for mere mortals

Posted Jul 29, 2020 17:58 UTC (Wed) by NYKevin (subscriber, #129325) [Link] (5 responses)

> 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.