Token Client Protocol

 6-jun-2000 / gmt
25-jul-2000 / gmt
19-aug-2001 / gmt



Configuration

The server configuration is a list of "hostname:portnum" strings read
from a file.  It is vital that all clients and servers agree on the
configuration;  accordingly, each message carries the signature of the
server list as a consistency check.  Servers are numbered beginning at 0.  

All messages are sent via UDP.  Server port numbers come from the
configuration file.  The client opens any available port and passes
its address when first connecting.

Clients always send messages to the proper destination based on the latest
available configuration information they have.  Token server and leader
assignments may change as servers crash or restart.

UDP transmissions are unreliable: they may occasionally be lost without
notice.  Clients must be prepared to reissue requests that go unanswered.



Administrative Messages

11 LOGIN	from client	request session ID to begin work
12 CONFIG	from server	reports session ID and server states
13 CATALOG	from client	reports relevant token holdings
14 ALIVE	from client	confirms that client is still functioning
15 LOGOUT	from client	voluntarily ends a client session

A client begins by sending a LOGIN message to any server.  If the server
is up, it responds with a CONFIG message.  This contains the current
server states and the index of the leading server.

A CONFIG message from the leading server assigns the client a session ID.
A CONFIG message from any other server returns a zero value for the ID,
but the client now knows which server is the leader, and repeats the
query (sending it to the leader) to get an ID assigned.

A client may later receive other unsolicited CONFIG messages indicating
a change in server states.  The client responds to each such message by
sending a CATALOG message listing all the tokens held by the client that
are now the responsibility of the sending server.

Each client sends an ALIVE message to the leading server every few
seconds as a heartbeat message confirming that the client still functions.
If the server does not receive any heartbeats for a long enough interval,
it declares the client to be down.  All the client's tokens are released,
the session ID is invalidated, and all subsequent messages are discarded.
The client must LOGIN anew to perform any further work.



Token Messages

21 REQUEST	from client	requests assignment of a token
22 GRANT	from server	assigns a token
23 REVOKE	from server	requests that a client return a token
24 RETURN	from client	updates and/or deassigns a token
25 CONFIRM	from server	acks a RETURN message

A client requests a token by sending a REQUEST message.  The server
responds, eventually, with a GRANT message.  In case of message loss,
the client periodically reissues an unanswered REQUEST message, and
must be prepared to deal with a duplicate GRANT message.

The client sends a RETURN message to update a token's data value, to
deassign the token, or to do both atomically.  The action is not complete
until acknowledged by a CONFIRM message from the server.  If no ack is
received the client should reissue the RETURN.  After deassigning a token,
the client must not request it again until the deassignment has been
confirmed.

The server may send an unsolicited REVOKE message for a token, in which
case the client is expected to deassign the token as soon as possible.
The client must respond to a REVOKE message for a token it no longer
holds by deassigning it again.



Message Contents

A message is a sequence of values.
Every message begins with this common header:
    int type	message type: the code number classifying the message
    int from	message sender: server or session ID
    int to	message recipient: server or session ID
    int ssig	server list signature, as a consistency check

Additional fields are as follows, by message type.

11 LOGIN
    string p		client's incoming datagram port, as ":portnum"
    			(previous version used "hostname:portnum")

12 CONFIG	the "to" field, if nonzero, reports the client's assigned ID
    int leader		index of the leading server
    int[] sstates	array of server states

13 CATALOG
    token[] holdings	tokens held by this client and served by recipient

14 ALIVE
    no additional fields

15 LOGOUT
    no additional fields

21 REQUEST
    long msgnum		arbitrary client message number
    token t		token name and (ignored) data value
    int access		1 for shared, -1 for exclusive access

22 GRANT
    long msgnum		identifies request being granted
    token t		token name and data value

23 REVOKE
    string name		token name only

24 RETURN
    long msgnum		arbitrary client message number
    token t		token name and data value
    int flags		1 = UPDATE data; 2 = DEASSIGN token; 3 = both

25 CONFIRM
    long msgnum		identifies RETURN message being confirmed



Message Field Encodings

Messages use a variable-length encoding for each field.  Decoding requires
knowing the order and types of the fields.  The very first field, the message
type, implicitly specifies the remaining sequence.

An integer value is encoded as one of:
    0snn nnnn			7-bit signed value (in one byte)
    1bbb snnn  nnnn nnnn  ...	12 + 8 * bbb bits (in bbb+2 bytes)

A string is encoded as an integer (giving the string length) followed by
the characters of the string.  No trailing NUL character is transmitted.

A token is encoded as two strings, the name and the data value.

An array of values is encoded as an integer (giving the length) followed
by the encodings of that many values.



Hashing Algorithms

The general function for hashing a string s of length n is:
    h = 0
    for (i = 0; i < n; i++)
        h = 37 * h + s[i]
    h = h & 0x7FFFFFFF		# result is 31-bit positive integer

Rehashing is used to produce a pseudorandom sequence.
The constants here are per Knuth vol 2 [1969], pp. 155-157.
    h = (314159261 * h + 453816707) & 0x7FFFFFFF

The server list signature, for n "hostname:portnum" strings, is:
    h = 0
    for (i = 0; i < n; i++)
        h = 39 * h + hash(server[i])
    h = h & 0x1FFF		# result is 13-bit positive integer



Computing the Server for a Particular Token

Each client receives occasional CONFIG messages containing an array of
server states:  0=DOWN, 1=BOOTING, 2=READY.  For purposes of assigning
token serving responsibilities, BOOTING and READY are equivalent.

For each token, there is a sequence that defines priorities for serving
that token.  The first server in the sequence that is not DOWN is the one
with current responsibility for the token.

Given a token named s, and an array a of servers {0, 1, ... , n-1}, the
array is reordered to produce that token's sever sequence by this code:
    h = hash(s)
    for (i = 0; i < n-1; i++)
        swap(a[i], a[i + h % (n - i)])
	h = rehash(h)

Note that the first server in the sequence is always simply
    hash(s) % n
and that if it is not DOWN then the rest of the sequence is immaterial.
