I am a programmer and architect (the kind that writes code) with a focus on testing and open source; I maintain the PHPUnit_Selenium project. I believe programming is one of the hardest and most beautiful jobs in the world. Giorgio is a DZone MVB and is not an employee of DZone and has posted 638 posts at DZone. You can read more from them at their website. View Full User Profile

Distributed time

12.01.2013
| 1947 views |
  • submit to reddit

If you run the date command on your (Unix) machine, you would see something like:

$ date
Mon Nov 25 07:56:59 CET 2013

in your timezone of choice. This time comes from an hardware piece local to your machine, embedded somewhere on the motherboard, and usually powered by the BIOS battery. The larger your system becomes, the more complex determining the current time will be.

Clock drifts

The time read by date is called system time; it is separated from the actual time read from the hardware clock at boot time and advanced at each timer interrupt produced by a specialized circuit. These times can even be in different time zones: you can set the system time to your country's timezone while keeping the hardware clock in UTC.
hwclock will query the hardware clock for you:

$ hwclock
Wed 06 Nov 2013 02:12:28 PM CET  -0.287960 seconds

Running the same command with debug options explains a bit how the clock works:

$ hwclock --debug
hwclock from util-linux-ng 2.17.2
Using /dev interface to clock.
Assuming hardware clock is kept in local time.
Waiting for clock tick...
...got clock tick
Time read from Hardware Clock: 2013/11/06 14:13:24
Hw clock time : 2013/11/06 14:13:24 = 1383743604 seconds since 1969
Wed 06 Nov 2013 02:13:24 PM CET  -0.450946 seconds

I ran this command inside a virtual machine which was hibernated for a couple of weeks, so you can see time got stuck for all the intervals in which the machine was persisted to disk. Running the same in a physical machine gives:

$ hwclock --debug
hwclock from util-linux-ng 2.17.2
Using /dev interface to clock.
Assuming hardware clock is kept in local time.
Waiting for clock tick...
...got clock tick
Time read from Hardware Clock: 2013/11/06 14:13:24
Hw clock time : 2013/11/06 14:13:24 = 1383743604 seconds since 1969
Wed 06 Nov 2013 02:13:24 PM CET  -0.450946 seconds

The clock advances via ticks that happen at a fixed frequency, such as 4000 Hz. This tick is received by the kernel, which increments its time accordingly. However, the frequency of the interrupt is only fixed up to a tolerance.

In fact, different hardware with the same specifications show clock ticks happening at a very similar frequency, but not identical. Given a reference, very precise clock such as a time server, the amount at which another machine distances itself from the reference is called clock drift; it is usually proportional to the time from the last adjustment.

Enter NTP

NTP is a protocol that performs automated adjustments of a machine's time by keeping a daemon (ntpd on Unix machines) running on them and querying external time servers. Time servers are run by statistical institutes (IEN in my country) attaching machine to precise hardware such as atomic clocks like the ones running in GPS satellites.

A full description of the protocol could be a small book in its own right, but it works more or less like this:

  • a local system A knows its clock is drifting and sends an outgoing packet to a time server B, marking it with A1.
  • the time server B responds with another packet marked with the real time B1.
  • A receives this packet at local time A2.
  • A now knows the real time at A1+(A2-A1)/2, assuming symmetric latency, was B1. It can adjust its clock to match at B1+(A2-A1)/2.

(actually the markers are more complex: the server has marks the times B1 and B2 of reception of the packet and emission of a response. Moreover the process is repeated and its results are statistically analyzed. NTP also features the complexity in the forms of layers of servers, but we're not going there.)

We only want to focus on the last phase: the adjustment. A clock under the control of NTP may adjust itself, especially under high load, by seconds or tens of seconds.

This means that in your database you could register events such as:

  • message(1, in_response_to=NULL, text=..., created_at=14:13:24)
  • message(2, in_response_to=1, text=..., created_at=14:13:22)

which can make your life difficult when a customer asks how it is possible that an answer was created before the question. They told you programming was an easy job, right? This scenario may happen especially when the messages are not generated by humans but by automated processes instead.

Multiple servers

The reason NTP is so widely used is to keep a fleet of servers synchronized with a single time source. Even then, the system isn't perfect as each machine is drifting according to its own local hardware clock.

Even if all clock are slower than the reference and show a delay with respect to the source, the situation we described before is still possible due to the relative difference from the machines. Suppose real time is 14:13:25 when 1 and 2 are inserted in sequence, but by different servers:

  • message(1, in_response_to=NULL, text=..., created_at=14:13:24) // machine with a slower clock with respect to source
  • message(2, in_response_to=1, text=..., created_at=14:13:22) // machine with a slower clock with respect to the other

Making the database generate times only solves the problem until more than one machine is required for writes, and it trade-offs testability of code that relies on time which now depends on a database.

A drastic solution is to ask the time to a centralized server, which introduces delay and becomes a single point of failure (and is stil subjected to adjustments). A more pragmatic solution is specify that all times gathered by the application, if not sensitive, have a 10-second tolerance.

Conclusions

Time is a complex concept: no wonder several thousand years passed from the dawn of civilization to when we gained tools precise enough to measure seconds and milliseconds (think of hourglasses). Small errors accumulate until precise clocks become misaligned with each other, and constant updates are required; which is a problem with distributed systems and the need for partition tolerance...

Published at DZone with permission of Giorgio Sironi, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)