Hacker News Reader

Comment by romed | Hacker News Reader

I’ve seen comments on HN over the years in which someone Dunning-Kruegers their way into saying that TrueTime is easily replicated. I always wonder if they have sixteen senior SREs in their pocket, because that’s the level of production engineering Google applies to the problem. Time SRE has at various points had take measures up to and including calling the USAF and telling them their satellites are fucked up. If you don’t have the staff for this, the easiest way to get access to TrueTime is probably to just use Cloud Spanner.

View on HN

> Time SRE has at various points had take measures up to and including calling the USAF and telling them their satellites are fucked up

It's another cute anecdote, but Google culture is full of these, always scant on details and always intended to show how big/smart/important/complex/indispensable their engineering is.

"Had to" is a strong term here, it's made to sound like USAF could not possibly have noticed some deviation they were likely to correct of their own accord as a matter of routine as they had been doing for the 20 years of the GPS project prior to Google being founded.

The reality is drift and bad clocks are and always have been a feature of GPS, one explicitly designed for, one an entire staff exists to cope with, and designs depending on the absolute accuracy of a single clock have never been correct

So yes, Google can be very impressed with Google. But I'm not sure that's the issue here.

Is it really surprising that people who have extremely precise time needs and a whole team devoted to solving them would notice issues that other people wouldn't? I think it's a very common pattern that a product has some set of trailblazer users who find issues before the people who make the product.

Also, I think you're over-interpreting. "Had to" here only means that they noticed and reported the issue first because their system depended on GPS time being right. It doesn't preclude the possibility that the USAF would notice and fix the issue eventually, just with a higher latency that Google wanted.

If some condition existed that exceeded GPS intended design, you most certainly wouldn't learn of it first from some random anecdote on HN.. more likely the front page of the BBC as the transportation system instantly collapses

So the anecdote itself is noise, it's intended to show how seriously intractable a problem accurate time is, but it doesn't do that, instead it only demonstrates OP's lack of familiarity with GPS and willingness to regurgitate corporate old wives' tales

Sub-millisecond flaws in GPS would make the transportation system collapse? Why?

Triangulation of location is bounded by the accuracy of those clocks.

1 microsecond is 300 meters of error.

What if all the satellites are off by the same amount?

According to the link posted higher up in the thread, in early 2016 they were all off by 13 microseconds for 12 hours, with no apparent consequences for anything ordinary people use GPS for such as location finding.

To triangulate, I think you need to know (1) where the satellites are, and (2) how far you are from each satellite. I think either absolute distance or relative distance works.

Getting both of these depends on knowing the time. That time comes from the satellites. Let's say they are all off by 1 us. Your time is derived from satellite time. That would mean the time you use to look up/calculate their positions will be off by 1 us from the correct time so you would get the wrong position for the satellites.

A quick Googling says the satellites orbital speed is 14000 km/hr, so using a time off by 1 us to look up/calculate satellite position would give you a position that is about 4 mm off.

The procedure for deriving the time from the satellites would get some extra error from this, but that should be limited to about the time it takes like to travel 4 mm, so we can ignore that. As a result your distance measurements between you and satellites would be off by about 4 mm or less.

The key here is that when all the satellites have the same error, the time you derive has the same error, so your distance calculations should still work, and so you only get an error of about how far satellites move in an interval equal to the time error.

In summary, if all the satellites are off by 1 us, your triangulation seems like it would be about 4 mm more uncertain.

If only one satellite is off, it is going to depend on how the time algorithm works. If the algorithm is such that it ends up with a time much closer to the times of the correct satellites than to the off satellite, then if it calculates the distance from the triangulated position to the expected positions of the satellites, and compares that to the measured distance, it should find that one is off by something on the order of the distance light travels in 1 us, and the others are all pretty close to where they should be. It should then be able to figure out that it has one unreliable satellite it, drop it, and then get the right location.

I have no idea if they actually take those kinds of precautions, though.

The case that would really screw it up would be if several satellites are off, but by different amounts. With enough observation it should be possible in many cases to even straighten that out, but it might be too complicated or too time consuming to be practical. (This is assuming that the error is that the satellites are simply set to the wrong time, but that wrong time is ticking at the right rate).

Precise geolocation relies on extreme time accuracy (the story always being that relativistic time dilation effects with the difference in gravity on the surface vs LEO must be accounted for), so yeah, it wouldn't surprise me one bit that the accuracy required is on the order of much less than a millisecond.

Here's an interesting article[1] about how relativity affects GPS satellites. The clock ticks in a GPS satellite need to be accurate to within 20-30 nanoseconds for accuracy, and they tick 38 microseconds/day faster to account for relativity.

[1] http://www.astronomy.ohio-state.edu/~pogge/Ast162/Unit5/gps....

GPS is one of the few technologies that have to account for both Special Relativity and General Relativity. The level of engineering that went into the system is just amazing.

Fun fact, GPS satellites use rubidium clocks instead of cesium clocks, and only maintain their accuracy thanks to yet another incredible feat of engineering.

A single satellite mildly misbehaving on occasion won't necessarily cause catastrophe. You're normally connected to more than the requisite 3 satellites anyway, so you might notice less accuracy, but not anything terrible.

Most of these systems are designed to work if you lose GPS entirely, so they fail gracefully.

Planes won't actually fall out of the sky if GPS makes mistakes. That's y2k fearmongering.

Why is it hard to believe that a group using GPS for a unique purpose has unique needs and detect unique issues?

https://www.bbc.com/news/technology-35491962

Could this be it?

> Is it really surprising that people who have extremely precise time needs and a whole team devoted to solving them would notice issues that other people wouldn't

If GPS timing is bad, a lot of people will notice that their position on the map is incorrect, because that's the whole purpose of the GPS network.

A 1 microsecond error is 300 meters.

GPS is not typically used to confirm a position that is known accurately by other means, and that is not its purpose. Only in those cases where there is a manifest conflict with independent spatial information will the problem be evident.

People are going to notice a 300m deviation due to landmarks and their eyes.

Rarely, if you are navigating at sea or in the air or in the woods... and even on the road, it is not uncommon for my GPS device to be clearly off without justifying the conclusion that there is a fault in a satellite.

Here are some users that have a high chance of noticing visually and in aggregate would probably produce a lot of noise:

* Air and sea port operators and navigators

* Military personal running supply lines

* Military personal on foot in operations and training

* Space-X

* NASA

* River boats

* Fresh water fishermen

* Etc

Out of all the possible users who would notice a 300m deviation just based on visual reconciliation, I personally would not say it would be so rare that the USAF would not find out very quickly. Of course, this is ignoring the equipment that would likely detect the issue way before somebody in the Army started phoning the USAF.

Unless I'm woefully off base here, if the satellites were incorrect, you would basically be permanently 300m off, not just temporarily.

There's not so many GPS satellites out there that you're going to be bouncing around them all the time - even if only one is affected, it would be very noticeable for extended periods of time.

Come on, in urban traffic a 300m error will easily place one in a parallel street.

>GPS is not typically used to confirm a position that is known accurately by other means

I am not so sure about that. The most common use of GPS is in satnav in cars. Satnavs typically show a map, and typically it is very easy to confirm your position on a map. Any inaccuracy by more than the usual few meters would be quickly noticed by the majority of GPS users.

If I remember correctly, there was a bug a couple of years back which caused an incorrect time offset between GPS and UTC time to be uploaded to some of the satellites - off by a handful of microseconds. Didn't affect navigation but it did trip a bunch of alerts on systems that relied on precise time. I don't think Google was the one that alerted the USAF to that though, in fact they may not have had sufficiently accurate timekeeping back then.

> Despite the flawed data set, there were no impacts to GPS positioning and navigation. Furthermore, GPS time (tGPS) was unaffected. Only a subset of the functions that make use of the GPS-UTC offset were affected.

https://www.gps.gov/systems/gps/performance/2016-UTC-offset-...

> A 1 microsecond error is 300 meters.

While the speed-of-light propagation is about 300 meters in a microsecond, isn't the final position error possibly much greater? For calculating position on Earth, you can think about a sphere expanding at the speed of light from each satellite. The 1 microsecond error here corresponds to a radius 300m bigger or smaller, which only corresponds to 300m horizontal distance on the ground if the satellite is on the horizon (assuming that Earth is locally a flat plane for simplicity here). For a satellite directly overhead, the 300m error is a vertical distance. Calculating the difference in horizontal position from this error is then finding the length of a leg of a right triangle with other leg length D and hypotenuse length D+300m, where D is the orbital distance from the satellite (according to Wikipedia, 20180km). The final horizontal distance error is then sqrt((D+300)^2 - D^2), or about 110km.

Of course, this is just the effect of a 1us error in a single satellite, I'm sure there's ways to detect and compensate for these errors.

Intuitively this seems wrong to me. If the satellite is overhead, the error would put you 300m into the ground so to speak. I'm not sure why you project that horizontally, and especially why you take the distance to the satellite into account.

As another sanity check, if the error for 1 us is 110 km, the error for 1 ns would be 110 m, and I suspect 1 ns error is not unusual for consumer electronics:

> To reduce this error level to the order of meters would require an atomic clock. However, not only is this impracticable for consumer GPS devices, the GPS satellites are only accurate to about 10 nano seconds (in which time a signal would travel 3m)

https://wiki.openstreetmap.org/wiki/Accuracy_of_GPS_data

> If the satellite is overhead, the error would put you 300m into the ground so to speak.

Right, I was basically calculating where that signal would just be reaching the surface at the same time it was 300m under you. This is a circle around you with a radius of ~110km (again using the approximation of the ground as a flat plane). Thinking about it more, there's not much reason to do this (GPS isn't really tied to the surface of the Earth, it gives you 3-D coordinates). I guess my point was that the 300m of distance from 1us of light propagation should not be thought of as a horizontal distance.

That would be if it were straight overhead, intersecting tangentially with another sphere. Realistically they're not overhead, but if two satellites are 30 degrees apart, the line of intersection between their spheres will move twice the distance one of the spheres moves. The magnifying factor is 1/sin(angle between the satellites from the observer).

I specifically worded this to be about money not brains. Most readers here can probably imagine how to implement a bounded time service. Most readers here also cannot afford to operate one. That is the point. Operating software reliably at large scale happens to be very expensive. 24x7 coverage with a short time-to-repair costs at a minimum several million dollars per year.

  24x7 coverage with a short time-to-repair costs at
  a minimum several million dollars per year.

Interesting - what are the constituents of that cost?

What sort of challenges do you face? Do you use PTP grandmaster clocks, or something else? How many sites, and how many clocks per site? Are the support issues mostly hardware failures, configuration problems, or something else? Is 24/7 support needed because the equipment lacks failover support, or is the failover support unreliable or insufficient?

You generally need at least 4-5 SREs for a high availability large (big 5) scale subsystem in a multinational corp just to cover all of the timezones and make sure you're not frantically calling everyone when someone goes on vacation or has to pick up their kid from the nurse. The salary plus benefits and overhead on that is easily in the millions.

I think it was meant that Google has such high costs. I read somewhere that Google operates two atomic clocks in each of its data centers, but I can't find a source for it right now, just this: https://www.wired.com/2012/11/google-spanner-time/

Atomic clocks aren't all that expensive. You can get a decent rubidium one for US $5K.

I'm guessing that was a reference to the January 2016 event[1]?

Google wasn't the only company that noticed it, and I have no idea if they discovered it before the USAF, but I can believe that someone from Google would phone up Schriever and ask WTF is going on.

[1] http://ptfinc.com/gps-glitch-january-2016/

Google also reports software and hardware security vulnerabilities and infrastructure security issues to external companies, organizations, and stakeholders responsible for the the design, operation, and maintenance of external systems. Google isn't the only company that does this - other organizations do too - but at this level expertise is a scarce resource, and we're all in the same boat so it behooves everyone when those capable can and do cooperate and participate in keeping a vigilant watch. This ethos is one if the reason the West dominates.

> including calling the USAF and telling them their satellites are fucked up

Citation needed. There is a worldwide organization, led by the US Naval observatory, that keeps constant watch on GPS satellite time performance. If google noticed anything that USNO and the other participants didn't that would need a paper or three published.

I’m sure someone has talked about this and proven or disproven it, but I’ve always been a little uneasy with the truetime protocol. I mean it’s faster than Raft, but for the use case maybe we are trying to fix the wrong problem?

If two events are independent, it matters very little what order we record them in the system of record.

My whole career we have been building cause and effect at transaction time but when we debug we stare at log files and time stamps like we are reading tea leaves, trying to figure out what situation A led to corrupted data in row B.

Maybe there’s a way to record this stuff instead of time stamps? Something DVCS style. Or maybe it’s provably intractable.

I think if 2 events are independent then you can use an eventually consistent DB like Cassandra and move on with your day. The importance of something like TrueTime arises when you have an example like in the article. Step 1: remove your parents from seeing your photo albums. Step 2: post your spring break photo album

That doesn't sound like a system you need "true time" for. :(

Of course, I think I just like thinking about how true time will start to fail once we get beyond the earth. Consider, what is the true time for events we are seeing in the stars right now?

Granted, I fully cede that being able to rely on a fully sequenced notion of time that everyone is a part of makes some reasoning much easier.

TrueTime is not a timestamp, but a time with a spread which reflects the maximum difference in time between two data centers.

If i understand correctly, if the size of this increases too much, this brings down the number of transactions per second which can be done, so keeping the spread small is key. Hence the atomic clocks etc.

Or just use global consensus with batching and avoid the need for clock synchronization altogether!

the only solution to this is to launch your own satellites :)

If we seal the surface of, then boil the ocean we can launch our own time satellites with completely sustainable propulsion.

I've always had an issue with systems assuming a universal time, because physics (Special Relativity) tells us there is no such thing. Two events in different places will be viewed as having a different order depending on your frame of reference. All that really matters on a physical level is causal connections.

I believe vector clocks capture this semantic. But they have other trade-offs.

Can't you solve that by just picking a reference frame though?

You need a quite elaborate system of a grid of synchronized, stationary clocks and rods to correctly define a reference frame, which is worse than what's required to come up with a "good enough on earth to some time resolution" true time.

To be clear this is pretty much exactly what the system of GPS satellites does, but without physical rods, and it is very expensive to construct and maintain. This works fine to a certain accuracy as long as you restrict your application to staying on earth.

Yes, and we all pick the Earth’s gravity well as our reference frame. Differences due to elevation and latitude are too small to measure for purposes of transaction clocks.

yeah, I’m pretty sure TrueTime is only defined on Earth, and GPS satellites do take relativity into account in their design.

http://www.astronomy.ohio-state.edu/~pogge/Ast162/Unit5/gps....

HTTP has had a reference frame since 1.0. It’s still one of my favorite features of just about any protocol ever.

Cache headers can set expiration times or offsets, but the client and server both send their own time stamp in the message. So when the server says “expire this at noon” but your laptop’s clock is five minutes slow or three time zones away, you can still figure out what the server meant by noon because the server tells you what time it thinks it is now. The accuracy is limited by network delays but for the problem space getting the right answer to the nearest second is still pretty damned good.

Special relativity has no such problem. In SR you can easily define a “time” coordinate everywhere such that all events can be timestamped with that coordinate and will respect causality.

GR at least usually has this property as well. (It doesn’t in the presence of closed timelike curves. It does in weak gravity and in the FLRW metric in cosmology. I’m not sure about the general strong gravity case.

Of course every inertial frame in SR has a well defined time coordinate, but that is not a universal time - other frames will disagree on which of two not-causally-connected events happened first. This is normally explained through the lack of a well defined "simultaneity" across different inertial frames.

You are correct that there is no truly capital-U-Universal time, but it doesn't matter. You control the whole system, so just choose one and call it "true time" and make everything participating in the system match it. Simultaneity in all inertial frames can be translated between one another, so if you go to a new place that has, for example, more time dilation due to different gravity, just note the parameters and translate it into your chosen "true time" and adjust the spread.

My point is not that it isn't possible, but that it is arbitrary and has no physical meaning. Writes thrown away in one frame because another concurrent write was "later" would in fact be kept in another frame. This is why it feels like a 'bug' to me conceptually - it's not how the universe works so why should a database need it.

To summarize, you're saying 'The universe doesn't need linear serializeability, so why should we?'

We build abstractions because they're useful to us, not because they have some special meaning to the universe. Systems with simpler abstractions are easier to understand and therefore build on top of. Complex numbers, for example, have no direct physical meaning in the (non-quantum mechanical) universe but can still be extremely useful and are sometimes the only/best way to solve some classical problems.

If you want to use a database where a required step of querying it is specifying a reference frame that the ordering of events is relative to, feel free. "In fact, for any two spacelike separated events, it is possible to find a reference frame where you can reverse the order in which they happen."[1] Personally I'll take a hard pass on bug reports like 'Foreign key constraint fails in reference frame 0.992c at 37.2Mm vector towards Alpha Centauri' which reads like the climax of Dante's Inferno for Systems Programmers.

[1]: https://physics.stackexchange.com/a/75765/28368

No, I'm saying the less impedance mismatch we have with the real physical world the easier things will be to work and make scale beyond earth (we will need a network that can scale to mars, for example, soonish). Fundamentally, we are limited by the laws of physics, so it is beneficial to understand them.

We build abstractions because they are useful, but we also often build the wrong abstractions - this is the entire history of science - building better abstractions. Simpler abstractions are great, but they can limit you. We can build all kinds of wonderful machinery with just classical physics, but if you want the modern world with GPS etc. you need relativity to make it work. All the databases based on truetime are great and marvels of engineering, but they won't be able to scale to even a second planet (getting a GPS equivalent to work across two planets is orders of magnitude harder than the earth one, not to mention the latency).

I'm not condoning your idea of a database that explicitly uses frames, but rather something based on more physical foundations like cause-and-effect. As I mentioned, I think vector clocks satisfy this. But maybe there are other better alternatives.

I'm fully aware of the physics (I have a MPhys, and DPhil in Particle Physics from Oxford).

When infinite resources are available, organizations will somehow find a way to consume them. There are properly consistent not-SQL architectures that do not need clocks, Datomic is one, and it does not require coordination with any government agencies to operate. https://www.datomic.com/

Also, I believe all the major cloud providers provide a "TrueTime" API service. I forgot the name that AWS uses, but you can call it on your EC2 instances and make sure your hosts are all in sync. It's pretty cool.

AFAIK AWS is only offering NTP service with a GPS source (i.e. stratum 1). TrueTime appears to be a service offering that is a step above that in terms of the guarantees it provides.

Ah, I've never had a use case for anything more accurate than NTP

You may never have built a system that needed it, but LTE cell handoffs require higher precision than NTP can supply. Almost every cell phone in use today benefits from highly precise timing.

This is why PTP and high precision GPS devices are built to integrate with cell provider gear.

TrueTime is more of a client side library that utilizes a service like NTPd.

You can implement a toy version of TrueTime with about 60 lines of C which uses a single ntp_gettime call for each of the TrueTime api functions (now, before, after).

If AWS's NTPd service offers drift <= 200 us/s, you could use it for TrueTime.

Reply on news.ycombinator.com