Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Living Without Atomic Clocks

cockroachlabs.com

Post reply on HN
Print view View original

41–50 of 52 posts

Re: Living Without Atomic Clocks

#41

Post by nickpsecurity »

jasonwatkinspdx wrote: post #16

First, CockroachDB's time api is based on the Hybrid Logical Clocks paper: http://www.cse.buffalo.edu/tech-reports/2014-04.pdf This paper is one of the most interesting published in the last couple of years IMO. I remain surprised at how many people have overlooked it. I'm not sure why this blog post makes no mention of the work, in the past the Cockroach folks have been quite explicit about crediting the research do…

Far as the patent, why would one want to claim knowledge of a patent if willful infringement gives so much extra damages? ;)

Re: Living Without Atomic Clocks

#42

Post by easytiger »

tlarkworthy wrote: post #2

I don't understand why 7ms is considered a good bound for atomic clocks? Hafele and Keating Experiment: "During October, 1971, four cesium atomic beam clocks were flown on regularly scheduled commercial jet flights around the world twice, once eastward and once westward, to test Einstein's theory of relativity with macroscopic clocks. From the actual flight paths of each trip, the theory predicted that the flying clo…

> I don't understand why 7ms is considered a good bound for atomic clocks?

It isn't, GPS + ptp can give slaves on the same lan +/- 700ns very cheaply

Re: Living Without Atomic Clocks

#43

Post by easytiger »

lifty wrote: post #14
vinkelhake wrote: post #8

Earlier quoted context omitted.

The 7ms bound is on the machines that do the actual work, not the ones with access to special clock hardware.

Indeed. The machines that do the actual work will still use a an inaccurate clock and get periodic corrective updates. That being said, you should be able to get a much higher precision using PTP and some decent network cards. There are plenty of factors that come into play (network latency, congestion, etc) but 7 ms sets the bar low.

7ms is even achievable with a well done local NTP setup

Re: Living Without Atomic Clocks

#44

Post by rbanffy »

bigdubs wrote: post #4
tlarkworthy wrote: post #2

I don't understand why 7ms is considered a good bound for atomic clocks? Hafele and Keating Experiment: "During October, 1971, four cesium atomic beam clocks were flown on regularly scheduled commercial jet flights around the world twice, once eastward and once westward, to test Einstein's theory of relativity with macroscopic clocks. From the actual flight paths of each trip, the theory predicted that the flying clo…

Something I never understood. If velocity (?) affects time, wouldn't time operate a different speed at different parts of the universe / solar system?

It does. There is no such thing as "now" unless you also include a "here". Everyone experiences a different time. Even us, who live in different points on the surface of the planet experience time differently.

Re: Living Without Atomic Clocks

#45

Post by Retric »

andrepd wrote: post #23
Retric wrote: post #19

Earlier quoted context omitted.

That's not really correct, if you sit at the center of a large object you don't accelerate, but you experience time dilation. Further, as you dig deeper your acceleration decreases but time dilation continues to increase.

That's incorrect as well. You are mixing two relativistic effects: from the velocity of something relative to an observer, and from the gravity on that spot of the universe (which is what I assume you mean by acceleration). Also wrong, as you dig deeper into a planet you experience less gravity, not more.

Velocity and acceleration are different things and Talking about less or more gravity is a poor descriptor.

At the center of the moon you would 'float' aka no acceleration relative to the moon. You would still be orbiting the earth, sun, etc.

However by being at the bottom of a gravity well you get time dilation relative to someone in the same orbit on the other side of the earth.

However, it's important to note LEO means high orbital velocity which counters being higher in the gravity field. Similarly, standing on the surface of the earth you have time dilation from the earths rotation which you would not have at the center.

PS: On way to think about it is at the center space time is pulled by all the mass around you which is a stronger pull than standing beside a planet. However the pull is in balance, like a tug of war game nobody is winning.

Re: Living Without Atomic Clocks

#46

Post by hnkimb3558 »

jasonwatkinspdx wrote: post #16

First, CockroachDB's time api is based on the Hybrid Logical Clocks paper: http://www.cse.buffalo.edu/tech-reports/2014-04.pdf This paper is one of the most interesting published in the last couple of years IMO. I remain surprised at how many people have overlooked it. I'm not sure why this blog post makes no mention of the work, in the past the Cockroach folks have been quite explicit about crediting the research do…

CockroachDB's time api is based on the Hybrid Logical Clocks paper. We credit it on our design doc (https://github.com/cockroachdb/cockroach/blob/master/docs/de...) and in the source code.

This blog post doesn't mention HLC because the explanation didn't require it. HLC boils down to a mechanism for taking the maximum physical wall time across >= 2 nodes, while still being able to provide monotonically increasing time via incrementing the logical component of the hybrid logical timestamp. In the blog post, this is referred to as "taking the maximum timestamp across requests". A segue into HLC would have served only to further complicate the explanation.

The work done by Sandeep Kulkarni, Murat Demirbas, David Alves, Todd Lipcon, Vijay Garg, and others was instrumental to our early design efforts. I am dismayed to see there's a patent pending, though both our design and open source implementation predate the patent filing.

Re: Living Without Atomic Clocks

#47

Post by jhayward »

techdragon wrote: post #35
monochromatic wrote: post #32

Earlier quoted context omitted.

> For instance, if you look at a clock on a GPS satellite, moving fast relative to you, you can see it run slower than the one on your wrist. Actually, the general relativity effects of weaker gravitational field dominate the special relativity effects of velocity[1]. So the GPS satellite clock actually runs faster, not slower. [1] http://www.astronomy.ohio-state.edu/~pogge/Ast162/Unit5/gps....

There's a really neat thing about this, the relationship balances out at a certain orbital height, before it flips over so there's an orbit where your chronologically in synch with the ground.

That's only true with respect to a given locus of points on the ground, not the full surface. I.E., the relative velocity of the SV isn't the same for all points that may be measuring.

In practice the GR effect is compensated by the satellite at manufacturing, the SR effect is treated in the receiver - for just that reason.

Re: Living Without Atomic Clocks

#48

Post by hnkimb3558 »

grogers wrote: post #37

When executing a transaction with a given timestamp on some node, doesn't the node have to guarantee that it will no longer accept commits with a smaller timestamp? Without that commitment, you could read a piece of data that is later updated by a transaction that occurred logically before you, breaking serializablility and/or snapshot isolation. The spanner paper is unclear how they deal with this, but my guess is t…

Cockroach enforces this guarantee on a per-key basis as opposed to for the entire node. If a key has been read at time t, it may only be subsequently written at time > t. CockroachDB accomplishes this using a timestamp cache at the leader node for a range. But this doesn't cause writes to block. Instead, the write timestamp is pushed to the most recent read + 1 logical tick.

Re: Living Without Atomic Clocks

#49

Post by [deleted] »

hnkimb3558 wrote: post #46
jasonwatkinspdx wrote: post #16

First, CockroachDB's time api is based on the Hybrid Logical Clocks paper: http://www.cse.buffalo.edu/tech-reports/2014-04.pdf This paper is one of the most interesting published in the last couple of years IMO. I remain surprised at how many people have overlooked it. I'm not sure why this blog post makes no mention of the work, in the past the Cockroach folks have been quite explicit about crediting the research do…

CockroachDB's time api is based on the Hybrid Logical Clocks paper. We credit it on our design doc ( https://github.com/cockroachdb/cockroach/blob/master/docs/de... ) and in the source code. This blog post doesn't mention HLC because the explanation didn't require it. HLC boils down to a mechanism for taking the maximum physical wall time across >= 2 nodes, while still being able to provide monotonically increasing t…

[deleted]

Re: Living Without Atomic Clocks

#50

Post by grogers »

hnkimb3558 wrote: post #48
grogers wrote: post #37

When executing a transaction with a given timestamp on some node, doesn't the node have to guarantee that it will no longer accept commits with a smaller timestamp? Without that commitment, you could read a piece of data that is later updated by a transaction that occurred logically before you, breaking serializablility and/or snapshot isolation. The spanner paper is unclear how they deal with this, but my guess is t…

Cockroach enforces this guarantee on a per-key basis as opposed to for the entire node. If a key has been read at time t, it may only be subsequently written at time > t. CockroachDB accomplishes this using a timestamp cache at the leader node for a range. But this doesn't cause writes to block. Instead, the write timestamp is pushed to the most recent read + 1 logical tick.

Interesting, thanks for the info.

Do reads execute through raft? If not, how do you guarantee that behavior - relying on leader leases? If so, does the lease period guarantee disjointness in the timestamps a leader can process, or do you rely on the leader abdicating control via timeout?

Since it can push the write timestamp, does that mean the write transaction aborts if it was in serializable mode? Does that cause problems updating a value that is heavily read?

Post reply on HN