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.