7 ms·

Living Without Atomic Clocks

143 points by tschottdorf 11y ago

tlarkworthy 11y ago
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 clocks, compared with reference clocks at the U.S. Naval Observatory, should have lost 40+/-23 nanoseconds during the eastward trip and should have gained 275+/-21 nanoseconds during the westward trip ... Relative to the atomic time scale of the U.S. Naval Observatory, the flying clocks lost 59+/-10 nanoseconds during the eastward trip and gained 273+/-7 nanosecond during the westward trip, where the errors are the corresponding standard deviations. These results provide an unambiguous empirical resolution of the famous clock "paradox" with macroscopic clocks." So if we are loosing nano seconds per day, couldn't we fly clocks around the datacenters and resync every month. 7ms seems beatable and not a terrible operational overhead for a fast globally consistent database.
- duskwuff 11y ago
  Maybe they've mixed up ms and µs? Their claim of "between 100ms and 250ms" for NTP also seems way too high.
  - jschwartzi 11y ago
    It likely has more to do with network latency than with any fundamental physical limitation of the system.
  - hnkimb3558 11y ago
    These are conservative upper bounds and are meant to encompass long tail offsets. You can usually get NTP down to < 10ms offsets, but if you rely on that, you'll likely run into problems which end up violating your database guarantees.
- bigdubs 11y ago
  Something I never understood. If velocity (?) affects time, wouldn't time operate a different speed at different parts of the universe / solar system?
  - fivesigma 11y ago
    Both velocity and gravity (distance from the nearest planet/star) affect time. It does, but the difference is negligible unless we're talking about the surface of a neutron star.
    - dingo_bat 11y ago
      The difference is not negligible if we are talking about applications like GPS etc.
  - yeureka 11y ago
    I am not a physicist but I believe the answer is yes as time is affected by acceleration.
  - fossuser 11y ago
    The movie Interstellar does a decent job demonstrating this (well the gravity piece anyway with the proximity to black holes). I also think satellite clocks have to take time relativity it into account (both due to distance from earth's gravity and their speed). Randall Munroe has a pretty entertaining write up that does a decent job giving a high level overview in pretty easy to understand terms: http://www.newyorker.com/tech/elements/the-space-doctors-big-idea-einstein-general-relativity http://www.newyorker.com/tech/elements/the-space-doctors-big...
  - theophrastus 11y ago
    I always thought it would be an interesting physics exam question to ask: "If a clock were landed on Halley's comet, and retrieved on its next orbit, what would be the expected difference in time relative to an earth bound clock?" It's tricky because all orbiting bodies experience a range of velocities as they orbit their star. But I gather Halley's comet has a particularly eccentric orbit (0.9) with a rapid perihelion of around 70km/sec, an aphelion of about 1km/sec, and about 75 years for a single orbit (ΔT' = ΔT / sqrt(1 - (v²/c²)))
- vinkelhake 11y ago
  The 7ms bound is on the machines that do the actual work, not the ones with access to special clock hardware.
  - lifty 11y ago
    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.
    - easytiger 11y ago
      7ms is even achievable with a well done local NTP setup
  - deleted 11y ago
    [deleted]
- jasonwatkinspdx 11y ago
  In this context, 7ms refers to the size of the TrueTime uncertainty interval, which is different from the typical instantaneous clock error. TrueTime returns an interval that is guaranteed to contain the absolute idealized physical "now." So this interval represents a worst case boundary, and if a system using TrueTime is able to separate events by the current interval, for example by forcing a committer to wait it out, then it can provide a temporal order that reflects the absolute real world physical order, despite any clock uncertainty. It's a bit different to think about than how we typically work with time, but it's a powerful primitive in a globally distributed system.
- easytiger 11y ago
  > 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
jasonwatkinspdx 11y ago
First, CockroachDB's time api is based on the Hybrid Logical Clocks paper: http://www.cse.buffalo.edu/tech-reports/2014-04.pdf 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 documents they're drawing from. Second, cloudera has a patent on this work: http://www.freepatentsonline.com/y2015/0156262.html http://www.freepatentsonline.com/y2015/0156262.html
- tlipcon 11y ago
  Kudu uses a similar algorithm which we call HybridTime. You can read the tech report here: http://pdsl.ece.utexas.edu/david/hybrid-time-tech-report-01.pdf http://pdsl.ece.utexas.edu/david/hybrid-time-tech-report-01.... and the source here: https://github.com/apache/incubator-kudu/blob/master/src/kudu/server/hybrid_clock.h https://github.com/apache/incubator-kudu/blob/master/src/kud... Both are probably more readable than patent-ese :)
  - jasonwatkinspdx 11y ago
    I know I'm diping my toe in some history here, but is there a sense of how the patent situation is going to shake out? I think this general family of algorithm is very important.
    - tlipcon 11y ago
      Agreed -- personally I'm against offensive use of patents like this as well, and it's my understanding that Cloudera doesn't intend to use this patent offensively. If it did, I would be upset and would consider leaving the company - I know many other employees feel the same way. The reason I agree to help write patent applications as an engineer is that I've seen the distraction and damages caused by patent trolls (or even other companies) and the importance of having a defensive portfolio. Disclaimer: Obviously I'm not speaking for the company or making any promises here :) -Todd
nickpsecurity 11y ago
Nice writeup. I disagree that we need chip-scale, atomic clocks. My idea was a dedicated, battery-backed piece of hardware that reliably stored time plus could sync other machines. Plugs into an interconnect with ultra-low latency. One for each datacenter. You can plug them into each machine in the cluster periodically to sync them. Or you can plug it into a master node that connects with low-latency management interface separate from main data line. Occasionally, time server gets exclusive access to that line, assesses latency, and then syncs its time. Time server might be custom built to avoid its own skew or keep one of the timekeeping devices attached. Those are periodically shipped to a central location to resync themselves against an atomic clock or each other. What yall think?
- NeutronBoy 11y ago
  > My idea was a dedicated, battery-backed piece of hardware that reliably stored time plus could sync other machines. Plugs into an interconnect with ultra-low latency. One for each datacenter. Google have a variant on this, where they use a GPS receiver in each data centre to provide an accurate time source for local machines.
  - dingo_bat 11y ago
    I've seen this being used extensively in sensor control centers (power grid/power plants), so it's definitely not limited to Google. Basically by accurate and precise timing, they are able to reconstruct and pinpoint the origin of a failure.
  - nickpsecurity 11y ago
    No, they use a GPS with 7ms time spread for servers as you said. What Im describing is a custom device set against an atomic clock to nano or microsecond accuracy which then does the same to the servers via low latency interconnects. Optionally with time server & dedicated networks for reduced admin overhead. Should do a lot better than 7ms with performance implications.
  - packetslave 11y ago
    It's actually a mix of GPS and atomic clocks for diversity. See the Spanner paper section on TrueTime for details
Animats 11y ago
Chip-scale atomic clocks are now about $1500.[1] This just gets you a 10.0000000000 MHz oscillator; something else has to count time and provide output. Passing around the max sequence number as a monotonic sequence indicator has a risk. A bogus sequence number near the max value can cause serious problems. [1] http://www.microsemi.com/salescontacts?ctype=3 http://www.microsemi.com/salescontacts?ctype=3
grogers 11y ago
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 that since they have accurately synchronized clocks, you'll never have to block long for that commitment to hold. Spanner also uses pessimistic locking, so for a R/W transaction, you can rely on locking reads to prevent the anomaly. With cockroachdb, wouldn't this commitment imply that poorly synchronized clocks would lead to poor performance?
- hnkimb3558 11y ago
  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.
  - grogers 11y ago
    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?

143 points by tschottdorf 11y ago

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 clocks, compared with reference clocks at the U.S. Naval Observatory, should have lost 40+/-23 nanoseconds during the eastward trip and should have gained 275+/-21 nanoseconds during the westward trip ... Relative to the atomic time scale of the U.S. Naval Observatory, the flying clocks lost 59+/-10 nanoseconds during the eastward trip and gained 273+/-7 nanosecond during the westward trip, where the errors are the corresponding standard deviations. These results provide an unambiguous empirical resolution of the famous clock "paradox" with macroscopic clocks." So if we are loosing nano seconds per day, couldn't we fly clocks around the datacenters and resync every month. 7ms seems beatable and not a terrible operational overhead for a fast globally consistent database.

duskwuff 11y ago
Maybe they've mixed up ms and µs? Their claim of "between 100ms and 250ms" for NTP also seems way too high.
- jschwartzi 11y ago
  It likely has more to do with network latency than with any fundamental physical limitation of the system.
- hnkimb3558 11y ago
  These are conservative upper bounds and are meant to encompass long tail offsets. You can usually get NTP down to < 10ms offsets, but if you rely on that, you'll likely run into problems which end up violating your database guarantees.
bigdubs 11y ago
Something I never understood. If velocity (?) affects time, wouldn't time operate a different speed at different parts of the universe / solar system?
- fivesigma 11y ago
  Both velocity and gravity (distance from the nearest planet/star) affect time. It does, but the difference is negligible unless we're talking about the surface of a neutron star.
  - dingo_bat 11y ago
    The difference is not negligible if we are talking about applications like GPS etc.
- yeureka 11y ago
  I am not a physicist but I believe the answer is yes as time is affected by acceleration.
- fossuser 11y ago
  The movie Interstellar does a decent job demonstrating this (well the gravity piece anyway with the proximity to black holes). I also think satellite clocks have to take time relativity it into account (both due to distance from earth's gravity and their speed). Randall Munroe has a pretty entertaining write up that does a decent job giving a high level overview in pretty easy to understand terms: http://www.newyorker.com/tech/elements/the-space-doctors-big-idea-einstein-general-relativity http://www.newyorker.com/tech/elements/the-space-doctors-big...
- theophrastus 11y ago
  I always thought it would be an interesting physics exam question to ask: "If a clock were landed on Halley's comet, and retrieved on its next orbit, what would be the expected difference in time relative to an earth bound clock?" It's tricky because all orbiting bodies experience a range of velocities as they orbit their star. But I gather Halley's comet has a particularly eccentric orbit (0.9) with a rapid perihelion of around 70km/sec, an aphelion of about 1km/sec, and about 75 years for a single orbit (ΔT' = ΔT / sqrt(1 - (v²/c²)))
vinkelhake 11y ago
The 7ms bound is on the machines that do the actual work, not the ones with access to special clock hardware.
- lifty 11y ago
  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.
  - easytiger 11y ago
    7ms is even achievable with a well done local NTP setup
- deleted 11y ago
  [deleted]
jasonwatkinspdx 11y ago
In this context, 7ms refers to the size of the TrueTime uncertainty interval, which is different from the typical instantaneous clock error. TrueTime returns an interval that is guaranteed to contain the absolute idealized physical "now." So this interval represents a worst case boundary, and if a system using TrueTime is able to separate events by the current interval, for example by forcing a committer to wait it out, then it can provide a temporal order that reflects the absolute real world physical order, despite any clock uncertainty. It's a bit different to think about than how we typically work with time, but it's a powerful primitive in a globally distributed system.
easytiger 11y ago
> 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

jasonwatkinspdx 11y ago

First, CockroachDB's time api is based on the Hybrid Logical Clocks paper: http://www.cse.buffalo.edu/tech-reports/2014-04.pdf 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 documents they're drawing from. Second, cloudera has a patent on this work: http://www.freepatentsonline.com/y2015/0156262.html http://www.freepatentsonline.com/y2015/0156262.html

tlipcon 11y ago
Kudu uses a similar algorithm which we call HybridTime. You can read the tech report here: http://pdsl.ece.utexas.edu/david/hybrid-time-tech-report-01.pdf http://pdsl.ece.utexas.edu/david/hybrid-time-tech-report-01.... and the source here: https://github.com/apache/incubator-kudu/blob/master/src/kudu/server/hybrid_clock.h https://github.com/apache/incubator-kudu/blob/master/src/kud... Both are probably more readable than patent-ese :)
- jasonwatkinspdx 11y ago
  I know I'm diping my toe in some history here, but is there a sense of how the patent situation is going to shake out? I think this general family of algorithm is very important.
  - tlipcon 11y ago
    Agreed -- personally I'm against offensive use of patents like this as well, and it's my understanding that Cloudera doesn't intend to use this patent offensively. If it did, I would be upset and would consider leaving the company - I know many other employees feel the same way. The reason I agree to help write patent applications as an engineer is that I've seen the distraction and damages caused by patent trolls (or even other companies) and the importance of having a defensive portfolio. Disclaimer: Obviously I'm not speaking for the company or making any promises here :) -Todd

nickpsecurity 11y ago

Nice writeup. I disagree that we need chip-scale, atomic clocks. My idea was a dedicated, battery-backed piece of hardware that reliably stored time plus could sync other machines. Plugs into an interconnect with ultra-low latency. One for each datacenter. You can plug them into each machine in the cluster periodically to sync them. Or you can plug it into a master node that connects with low-latency management interface separate from main data line. Occasionally, time server gets exclusive access to that line, assesses latency, and then syncs its time. Time server might be custom built to avoid its own skew or keep one of the timekeeping devices attached. Those are periodically shipped to a central location to resync themselves against an atomic clock or each other. What yall think?

NeutronBoy 11y ago
> My idea was a dedicated, battery-backed piece of hardware that reliably stored time plus could sync other machines. Plugs into an interconnect with ultra-low latency. One for each datacenter. Google have a variant on this, where they use a GPS receiver in each data centre to provide an accurate time source for local machines.
- dingo_bat 11y ago
  I've seen this being used extensively in sensor control centers (power grid/power plants), so it's definitely not limited to Google. Basically by accurate and precise timing, they are able to reconstruct and pinpoint the origin of a failure.
- nickpsecurity 11y ago
  No, they use a GPS with 7ms time spread for servers as you said. What Im describing is a custom device set against an atomic clock to nano or microsecond accuracy which then does the same to the servers via low latency interconnects. Optionally with time server & dedicated networks for reduced admin overhead. Should do a lot better than 7ms with performance implications.
- packetslave 11y ago
  It's actually a mix of GPS and atomic clocks for diversity. See the Spanner paper section on TrueTime for details

Animats 11y ago

Chip-scale atomic clocks are now about $1500.[1] This just gets you a 10.0000000000 MHz oscillator; something else has to count time and provide output. Passing around the max sequence number as a monotonic sequence indicator has a risk. A bogus sequence number near the max value can cause serious problems. [1] http://www.microsemi.com/salescontacts?ctype=3 http://www.microsemi.com/salescontacts?ctype=3

grogers 11y ago

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 that since they have accurately synchronized clocks, you'll never have to block long for that commitment to hold. Spanner also uses pessimistic locking, so for a R/W transaction, you can rely on locking reads to prevent the anomaly. With cockroachdb, wouldn't this commitment imply that poorly synchronized clocks would lead to poor performance?

hnkimb3558 11y ago
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.
- grogers 11y ago
  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?