4 ms·

So the basic issue is touched on in the article in the Partial Order section. Lamport Clocks cannot order unrelated events. But for higher consistency levels i

So the basic issue is touched on in the article in the Partial Order section. Lamport Clocks cannot order unrelated events. But for higher consistency levels in databases, this is exactly what we need. The classic solution to this is to extend Lamport clocks into Vector Clocks. As the name implies, these are a vector, where each entry corresponds to a Lamport clock at that server. The obvious downside of this is you need vectors as long as the number of servers, making timestamps considerably more expensive, as well as the inflexibility this implies. One of Spanner's key properties is External Consistency. This is as strong as it gets. Spanner is capable of correctly ordering all events across the entire system in relation to idealized physical time. It does this through a combination of better than typical physical clock synchronization, and waiting out any ambiguity window as needed. The latter does have a performance cost, but the paper makes the argument such costs combined with consistency are preferable to the subtle bugs developers will inevitably introduce without such. Another thing in the mix here is Hybrid Logical Clocks, which are an extension of Lamport Clocks that keeps them within some constant of the idealized physical time. This is actually what CockroachDB uses (or at least a variation on it). To get this stuff to gel in your head I would suggest reading the primary papers: https://lamport.azurewebsites.net/pubs/time-clocks.pdf https://lamport.azurewebsites.net/pubs/time-clocks.pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.569.3601&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56... https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf https://static.googleusercontent.com/media/research.google.c... https://cse.buffalo.edu/tech-reports/2014-04.pdf https://cse.buffalo.edu/tech-reports/2014-04.pdf There are also a couple educators/experts that have great presentations on this topic material, namely Kyle Kingsbury aka Aphyr and Lindsey Kuper. I apologize for not chasing down the exact talks, but they should be up on youtube and such.

dTal 5y ago
>Spanner is capable of correctly ordering all events across the entire system in relation to idealized physical time As "idealized physical time" itself does not have consistent ordering, surely this is impossible in real life? The notion of a single universal instant is rough approximation which breaks down when separate nodes are moving relative to one another, or are at different gravitational potentials. We're putting gigahertz CPUs on spacecraft now so this isn't just a theoretical problem! How is this resolved? Perhaps an enforced maximum temporal resolution?
- potiuper 5y ago
  'As "idealized physical time" itself does not have consistent ordering' - No. A consistent "causality" ordering exists relative to the big bang. A simultaneous "now" does not exist, but that does not prevent relative orderings from being discerned. An enforced max [absolute] time resolution is not necessary, but a consistent universal ordering requires relative speeds, which require a reference frame or gauge, and a sequencing clock for each observer. With regards to satellites, the frame is motion relative to the [center of the] Earth.
  - omegalulw 5y ago
    Is this distinction even necessary to make here? For all practical database usages, I doubt you need enough precision to have to account for special and general relativity.
- jlokier 5y ago
  > As "idealized physical time" itself does not have consistent ordering, surely this is impossible in real life? It's possible when you have reliable clocks to provide time bounds, and knowledge of the physical system to provide space bounds to permit clock synchronisation to some accuracy. If two external agents make requests that conflict or interact (aka are non-commutative), if the requests are close enough in time and separate enough in space, the lack of true global time (ie. relativity) means there will be no physically unambiguous order to the requests. But you can delay the responses to non-commutative requests for long enough to impose an unambiguous global order on any external logic that depends on information in the response. In effect, the "global time" of external agents events isn't a function of the instant when they make a request, it is an ordering function of the both the request and response events, which makes each external request take a time range physically. The ranges are managed to ensure there is a global order to any possible information dependencies the external agents may be using. In a way, this is a neat optimisation of vector logical clocks while maintaining the logic, reducing the dimensionality of the vector. This can be generalised in large distributed systems to partial dimension reduction. When the system has clocks that are synchronised across the internal system to some accuracy, "close enough in time" can be resolved more accurately, and the required delays to disambiguate requests that are close together in time can be reduced. It is possible Spanner might develop an inconsistency near the event horizon of a black hole. Something to watch out for.

dTal 5y ago

>Spanner is capable of correctly ordering all events across the entire system in relation to idealized physical time As "idealized physical time" itself does not have consistent ordering, surely this is impossible in real life? The notion of a single universal instant is rough approximation which breaks down when separate nodes are moving relative to one another, or are at different gravitational potentials. We're putting gigahertz CPUs on spacecraft now so this isn't just a theoretical problem! How is this resolved? Perhaps an enforced maximum temporal resolution?

potiuper 5y ago
'As "idealized physical time" itself does not have consistent ordering' - No. A consistent "causality" ordering exists relative to the big bang. A simultaneous "now" does not exist, but that does not prevent relative orderings from being discerned. An enforced max [absolute] time resolution is not necessary, but a consistent universal ordering requires relative speeds, which require a reference frame or gauge, and a sequencing clock for each observer. With regards to satellites, the frame is motion relative to the [center of the] Earth.
- omegalulw 5y ago
  Is this distinction even necessary to make here? For all practical database usages, I doubt you need enough precision to have to account for special and general relativity.
jlokier 5y ago
> As "idealized physical time" itself does not have consistent ordering, surely this is impossible in real life? It's possible when you have reliable clocks to provide time bounds, and knowledge of the physical system to provide space bounds to permit clock synchronisation to some accuracy. If two external agents make requests that conflict or interact (aka are non-commutative), if the requests are close enough in time and separate enough in space, the lack of true global time (ie. relativity) means there will be no physically unambiguous order to the requests. But you can delay the responses to non-commutative requests for long enough to impose an unambiguous global order on any external logic that depends on information in the response. In effect, the "global time" of external agents events isn't a function of the instant when they make a request, it is an ordering function of the both the request and response events, which makes each external request take a time range physically. The ranges are managed to ensure there is a global order to any possible information dependencies the external agents may be using. In a way, this is a neat optimisation of vector logical clocks while maintaining the logic, reducing the dimensionality of the vector. This can be generalised in large distributed systems to partial dimension reduction. When the system has clocks that are synchronised across the internal system to some accuracy, "close enough in time" can be resolved more accurately, and the required delays to disambiguate requests that are close together in time can be reduced. It is possible Spanner might develop an inconsistency near the event horizon of a black hole. Something to watch out for.