What time is it? Part 3

In Part 1, we implemented a DAYTIME server using TCP. In Part 2, we implemented a TIME server using UDP.

Today, we will implement a simple NTP client using UDP.

The NTP (Network Time Protocol) specification has been evolving since 1985. Most of the focus has been on algorithms for synchronizing the clocks of computers to varying precisions. Currently the IETF is drafting version 4, but has only formally documented up to version 3 in RFC 1305. For use cases where less precision is required, version 4 of a variant called SNTP is documented in RFC 4330.

We will begin by referencing a set of vocabularies we depend upon:

USING: accessors arrays calendar combinators destructors
formatting kernel io io.sockets math pack random sequences ;

To parse and manipulate the NTP responses, we need to refer to the specification. These are often helpfully documented in ascii diagrams. The latest specification includes this description of a NTP packet:

1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN  |Mode |    Stratum    |     Poll      |   Precision   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Root  Delay                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Root  Dispersion                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Reference Identifier                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                    Reference Timestamp (64)                   |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                    Originate Timestamp (64)                   |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                     Receive Timestamp (64)                    |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                     Transmit Timestamp (64)                   |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                 Key Identifier (optional) (32)                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                                                               |
|                 Message Digest (optional) (128)               |
|                                                               |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The specification contains detailed information about each of these fields and how they should be interpreted and used. For now, we will just create a tuple class to hold the values contained in a typical NTP packet:

TUPLE: ntp leap version mode stratum poll precision
root-delay root-dispersion ref-id ref-timestamp
orig-timestamp recv-timestamp tx-timestamp ;

Timestamps in the NTP protocol are stored in 64-bits. The first 32-bits are an integer number of seconds, and the last 32-bits are a fractional number of seconds. This gives the protocol a theoretical precision of 233 picoseconds. Most clocks in use by NTP servers are not that accurate, so some of the precision is wasted. Currently, this timestamp should be simply interpreted as a number of seconds since January 1, 1900 (this will change slightly when the 64-bit value overflows in the year 2036).

To parse each timestamp, we will want to convert it into a number of seconds and then use the calendar vocabulary to manipulate it into a timestamp object:

: (time) ( sequence -- timestamp )
    [ first ] [ second 32 2^ / ] bi + seconds
    1900 1 1 0 0 0 instant <timestamp> time+ ;

Now that we have that, parsing the NTP packet is fairly direct:

: (ntp) ( payload -- ntp )
    "CCCcIIIIIIIIIII" unpack-be {
        [ first -6 shift HEX: 3 bitand ]  ! leap
        [ first -3 shift HEX: 7 bitand ]  ! version
        [ first HEX: 7 bitand ]           ! mode
        [ second ]                        ! stratum
        [ third ]                         ! poll
        [ [ 3 ] dip nth ]                 ! precision
        [ [ 4 ] dip nth 16 2^ / ]         ! root-delay
        [ [ 5 ] dip nth 16 2^ / ]         ! root-dispersion
        [ [ 6 ] dip nth ]                 ! ref-id
        [ [ { 7 8 } ] dip nths (time) ]   ! ref-timestamp
        [ [ { 9 10 } ] dip nths (time) ]  ! orig-timestamp
        [ [ { 11 12 } ] dip nths (time) ] ! recv-timestamp
        [ [ { 13 14 } ] dip nths (time) ] ! tx-timestamp
    } cleave ntp boa ;

The simplest client request is a 48-byte packet encoded with no timestamp information, but only the mode of operation (e.g., 3 or "client"):

CONSTANT: REQUEST B{ HEX: 1b 0 0 0 0 0 0 0
                     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
                     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
                     0 0 0 0 0 0 0 0 }

We will use the <datagram> word from the io.sockets vocabulary to send and receive UDP packets. Note that the resolve-host word is used to lookup the IP addresses for domain names, and picks one to use at random.

: <ntp> ( host -- ntp )
    123 <inet> resolve-host [ inet4? ] filter random
    f 0 <inet4> <datagram> [
        [ REQUEST ] 2dip [ send ] [ receive drop ] bi (ntp)
    ] with-disposal ;

We can make some convenience words for well-known hosts:

: default-ntp ( -- ntp )
    "pool.ntp.org" <ntp> ;

: local-ntp ( -- ntp )
    "localhost" <ntp> ;

Putting this all together, a NTP request/response can look like this:

( scratchpad ) default-ntp .
T{ ntp
    { leap 0 }
    { version 3 }
    { mode 4 }
    { stratum 3 }
    { poll 0 }
    { precision -8 }
    { root-delay 6453/65536 }
    { root-dispersion 4379/65536 }
    { ref-id 2903084642 }
    { ref-timestamp
        T{ timestamp
            { year 2010 }
            { month 4 }
            { day 30 }
            { minute 25 }
            { second 55+819995115/2147483648 }
        }
    }
    { orig-timestamp
        T{ timestamp { year 1900 } { month 1 } { day 1 } }
    }
    { recv-timestamp
        T{ timestamp
            { year 2010 }
            { month 4 }
            { day 30 }
            { minute 36 }
            { second 19+729484793/4294967296 }
        }
    }
    { tx-timestamp
        T{ timestamp
            { year 2010 }
            { month 4 }
            { day 30 }
            { minute 36 }
            { second 19+732746657/4294967296 }
        }
    }
}

This could be improved by parsing some of the fields as "human-readable" (like the leap indicator, mode, stratum, and reference id) and adding support for handling unresponsive servers or dropped packets. From here, one could learn the clock synchronization algorithms, or even use this as the basis to begin implementing a NTP server.

What time is it? Part 2

In Part 1, we implemented a server using the human-readable DAYTIME protocol.

One of the drawbacks of human-readable time is the challenge of parsing the text into an object that can be manipulated by computers. This is made harder when there is no clear specification for the format of the text (some conventions like RFC 822 exist, but the DAYTIME protocol leaves this detail unspecified).

Also in 1983, the TIME protocol (specified in RFC 868) was developed. It was intended to be used by machines (rather than humans) to retrieve the current time. As with the DAYTIME protocol, it supports both TCP and UDP. Below, we will implement a TIME server using UDP in Factor.

These are the vocabularies that we will be using:

USING: arrays destructors io.sockets kernel math pack system ;

The timestamp representation used as a payload is a 32-bit binary number of seconds since January 1, 1900. Most computers now use a 64-bit number of milliseconds since January 1, 1970 (referred to as the "epoch") to store the current time. Factor allows access to the current time as a number of microseconds since the epoch using the system-micros word.

We need to first create a word that will return the number of seconds since 1900. There were 2,208,988,800 seconds between January 1, 1900 and January 1, 1970. We will use that to adjust the current time:

CONSTANT: TIME1970 2208988800

: seconds-since-1900 ( -- n )
    system-micros 1000000 / >fixnum TIME1970 + ;

Jumping ahead slightly, we will create a word that receives a packet from a client (usually empty) and then sends the current time as a 32-bit binary number of seconds since 1900 back to the client. The io.sockets vocabulary provides some words for creating datagram servers (for UDP).

: serve-time ( datagram -- )
    [ receive nip ] keep
    [ seconds-since-1900 1array "i" pack ] 2dip
    send ;

According to the specification, the TIME server should run on port 37, but that typically requires administrative privileges, so we will run it on port 3700 for ease of testing. It is also best practices to bind to a specific network interface but, for now, we will listen for packets from any interface.

By running this code in the listener, we can test a datagram port that handles a single packet:

( scratchpad ) f 3700 <inet4> <datagram> [
                   serve-time
               ] with-disposal

And then using netcat, we can send an empty UDP packet to the server, which should respond with the current time in binary (which is why it is hard to read):

$ nc -u 127.0.0.1 3700

?X?

Putting this all together, we can create a word that will loop forever, serving the current time in this manner:

: time-server ( -- )
    f 3700 <inet4> <datagram> [
        [ dup serve-time t ] loop drop
    ] with-disposal ;

The resolution of this protocol is low (since it is number of seconds), limiting the use-cases it is capable of supporting. Over the years, much better solutions have become standardized.

What time is it? Part 1

Time is a harder-than-it-looks concept in most computing systems.

Every machine has a clock, every clock has a time, and every time has a near infinite number of representations. The challenges include mastery of such topics as timezones, calendars, encodings, localizations, offsets, precision, drift, geographic latencies, atomic clocks, even GPS synchronization.

Back in the early 1980's, one of the tasks for building computer networks involved designing protocols by which applications could determine the current time. Over the years, these protocols have grown in features and complexity.

But back in 1983, in RFC 867, the IETF standardized a very simple human-readable time protocol called DAYTIME to solve the basic question: "what time is it?". The specification supports both TCP and UDP implementations, but we will implement just the TCP portion in Factor.

First, we need some vocabularies:

USING: accessors calendar formatting kernel io
io.encodings.ascii io.servers.connection ;

Using the formatting vocabulary that I wrote, printing the current time is easy with strftime:

( scratchpad ) now "%c" strftime .
"Wed Apr 14 18:13:51 2010"

The threaded-server type can then be used to accept connections from clients and output the current time before closing the connection:

: <daytime-server> ( port -- server )
    ascii <threaded-server>
        swap >>insecure
        "daytime.server" >>name
        [ now "%c" strftime print flush ] >>handler ;

According to the specification, the DAYTIME server should run on port 13, but that typically requires administrative privileges, so we will run it on port 1300 for this test.

( scratchpad ) 1300 <daytime-server> start-server

And to test it, using netcat:

$ nc localhost 1300
Wed Apr 14 17:17:53 2010
$ nc localhost 1300
Wed Apr 14 17:17:53 2010
$ nc localhost 1300
Wed Apr 14 17:17:54 2010
$ nc localhost 1300
Wed Apr 14 17:17:54 2010
$ nc localhost 1300
Wed Apr 14 17:17:55 2010

Characteristic of some of the early, and quite rapid, development on the internet, the specification is a little loose as to what format the time should be represented in. Other protocols developed later will be much more specific about the form and character of the time representations they contain.

Connecting to Memcached

The Memcached project provides a "distributed memory object caching system", allowing quick storage and lookup functionality for key-value pairs. It is both free and highly useful and a necessary component to scaling most high traffic websites.

Libraries are available in many languages, but not Factor. I thought it would be fun to fix that and document some of the steps.

The first step is to understand what protocols are supported (in this case both text and binary) and over what mediums (either UDP or TCP). An example of the text protocol looks like:

$ telnet localhost 11211
Trying ::1...
Connected to localhost.
Escape character is '^]'.
set foo 0 60 3
bar
STORED
get foo
VALUE foo 0 3
bar
quit
Connection closed by foreign host.

We will start by implementing the binary protocol (which is more efficient than the text one) over TCP.

First, we will list the needed vocabularies and begin a namespace for the client implementation.

USING: accessors arrays assocs byte-arrays combinators fry
io io.encodings.binary io.sockets kernel make math math.parser
namespaces pack random sequences strings ;

IN: memcached

The io.sockets vocabulary provides some nice words for doing simple networking. One of those words is with-client, which connects to a specified address and then runs a quotation with the input and output streams configured to read and write to the connected socket. We will use this to provide a structure for making Memcached requests:

SYMBOL: memcached-server
"127.0.0.1" 11211 <inet> memcached-server set-global

: with-memcached ( quot -- )
    memcached-server get-global
    binary [ call ] with-client ; inline

Requests are made to the Memcached server by specifying a command type, and occasionally providing other fields:

TUPLE: request cmd key val extra opaque cas ;

: <request> ( cmd -- request )
    "" "" "" random-32 0 \ request boa ;

The header to every request is 24 bytes, and includes a magic byte, the command, the key length, the extra header length, the total body length including the value, an opaque value, and a field used for CAS (compare and swap):

: send-header ( request -- )
    {
        [ cmd>> ]
        [ key>> length ]
        [ extra>> length ]
        [
            [ key>> length ]
            [ extra>> length ]
            [ val>> length ] tri + +
        ]
        [ opaque>> ]
        [ cas>> ]
    } cleave
    '[ HEX: 80 _ _ _ 0 0 _ _ _ ] "CCSCCSIIQ" pack-be write ;

Now that we have that, sending a request is straight-forward:

: (send) ( str -- )
    [ >byte-array write ] unless-empty ;

: send-request ( request -- )
    {
        [ send-header    ]
        [ extra>> (send) ]
        [ key>>   (send) ]
        [ val>>   (send) ]
    } cleave flush ;

The response packet from the server has a similar structure to the request, so we can start by parsing the header:

: read-header ( -- header )
    "CCSCCSIIQ" [ packed-length read ] [ unpack-be ] bi ;

We can check the header for some error conditions:

: check-magic ( header -- )
    first HEX: 81 = [ "bad magic" throw ] unless ;

: check-status ( header -- )
    [ 5 ] dip nth {
        { HEX: 01  [ "key not found" throw     ] }
        { HEX: 02  [ "key exists" throw        ] }
        { HEX: 03  [ "value too large" throw   ] }
        { HEX: 04  [ "invalid arguments" throw ] }
        { HEX: 05  [ "item not stored" throw   ] }
        { HEX: 06  [ "value not numeric" throw ] }
        { HEX: 81  [ "unknown command" throw   ] }
        { HEX: 82  [ "out of memory" throw     ] }
        [ drop ]
    } case ;

We need some words to optionally read the key and value if they are present:

: (read) ( n -- str )
    dup 0 > [ read >string ] [ drop "" ] if ;

: read-key ( header -- key )
    [ 2 ] dip nth (read) ;

: read-val ( header -- val )
    [ [ 6 ] dip nth ] [ [ 2 ] dip nth ] bi - (read) ;

And now we have everything we need to read the response:

: read-response ( -- val key )
    read-header {
        [ check-magic  ]
        [ check-status ]
        [ read-key     ]
        [ read-val     ]
    } cleave swap ;

Believe it or not, but this is all we really need to implement the various Memcached commands, including the two most basic: GET and SET:

: m/get ( key -- val )
    HEX: 00 <request> swap >>key
    send-request read-response drop 4 tail ;

: m/set ( val key -- )
    HEX: 01 <request> swap >>key swap >>val
    { 0 0 } "II" pack-be >>extra ! flags exp
    send-request read-response 2drop ;

Replicating the telnet session from the beginning of the article from the Factor listener:

( scratchpad ) [ "bar" "foo" m/set ] with-memcached
( scratchpad ) [ "foo" m/get ] with-memcached .
"bar"

This could be improved in several ways, for example: handling servers that stop responding, keeping the network connections open over several sets of requests (or use UDP), and allowing access to some of the more advanced parts of the Memcached protocol (including flags and expiration timers).

It is available on my Github, and hopefully will be pulled into the main repository soon.