C Library Specification
for the FTN token server

8-oct-1999 / gmt
6-jul-2000 / gmt



This document specifies a token service originally designed for use
with the Swarm storage system.  The token service is used for
synchronization and metadata maintenance but knows nothing about Swarm.



Tokens

A token is a named object holding opaque data of arbitrary size.
The token service provides a means for orderly sharing of tokens
among multiple clients.  If tokens represent permission to perform
actions by the client, they serve as both locks and data caches.

The token service is implemented as a distributed system running on
multiple servers.  The service survives the loss of any one server
imperfectly: no token *assignments* are lost, but data from unheld
tokens is lost.  Thus tokens combine reliable locks with unreliable
data storage.

Clients interface with the token service by calling a library of C
functions.  These functions hide the details of communication and
crash recovery from the clients.  Clients and servers communicate
using UDP.



Access

A token is named by a C string.  Token names are unique within a
particular token service.  It is possible to run multiple token
services simultaneously with disjoint token spaces.

Tokens are created, with empty data, on first reference.  There is
no fixed limit on the number of tokens and no predefined list of
known tokens.

Clients operate on tokens by requesting either shared or exclusive
access.  Any client holding a token can modify its data; when a
token is shared, data changes are recorded by the token service but
not redistributed to any other current token holders.

The access mode of a token cannot be upgraded or downgraded.
Instead, the token must be released and re-requested.



Contention

A client may hold a token indefinitely.  If the token service receives
a conflicting (non-sharable) request for the same token, it notifies the
client by invoking a callback function; but the token remains reserved
until freed voluntarily by the client.

When multiple requests await a newly released token, the oldest
request for exclusive access is granted.  [[ NOT IMPLEMENTED. ]]
If there are no requests for exclusive access, then all the remaining
requests are sharable, and they can be granted simultaneously.



Reliability

The token service survives the loss of up to half of the servers by
reassigning responsibilities among the remaining servers.  This process
is transparent to the clients.

While the assignment of tokens to clients is reliable, token data is
lost when a server crashes.  Token servers may also discard old unheld
tokens in the unlikely event of a memory shortage.  Consequently,
clients must be able to re-create token data as needed upon receiving
an empty token.

Any number of client failures are permitted without affecting the
token service.  Held tokens are automatically reclaimed when a client
crashes, with the token data retaining the last value seen by the
server.

The token service assumes a fail-stop failure model:  We assume that
systems crash "hard" and do not simply hang with connections open.
We also assume no network partitioning.



Expected Usage

The token service imposes no interpretation on the significance of a
token or the meaning of its data.  However, it is easier to understand
the motivation for the design by considering how Swarm is expected
to use tokens.

One token service is used for each distributed filesystem.  If multiple
filesystems are used, multiple token services are used.  Token servers
are be co-located with the filesystem servers so that the token service
fails only when the filesystem fails.  Note that the tokens held on a
server bear no special relation to the file data held on that server.

Most tokens correspond to Unix inodes.  The inode data in a token
eliminates the need to retrieve an actual inode from disk, yet the disk
version is available when needed for first-use initialization or for
crash recovery.

Tokens are used as locks to control access to the underlying disk
blocks.  Shared access allows simultaneous reading by multiple clients.
Exclusive access is required for writing.

Most changes to token data require exclusive access.  Clients with
shared access may register the inode data if it is initially empty;
multiple clients may potentially register consistent copies of the
same data.  (Or, to avoid duplicate effort, they could switch to an
exclusive request to perform the update.)  Shared clients may also
update file access times, with later values overwriting earlier ones.



Client Interface

The token service provides a library of thread-safe C functions,
below, for accessing tokens.  The key datatypes are
	Tok_Service	an opaque handle for a token service
	Tok_Token	an opaque handle for an individual token


Tok_Service Tok_Open(char *serverlist[])
    
    Initializes one client by contacting a token service running on
    the given set of servers.

    Tok_Open does not return until an adequate set of servers is
    available.  If the servers are down, Tok_Open periodically
    rechecks them until they are again functioning.

    A token service handle, for use with subsequent calls, is returned.


void Tok_Close(Tok_Service t)

    Disconnects a client from the token service.  This is the inverse
    of Tok_Open.


Tok_Token Tok_Request(Tok_Service t, char *name, int how,
	    void (*callback)(Tok_Token, ClientData), ClientData d)

    Acquires access to a token, blocking until the token is available.
    "how" is TOK_SHARED or TOK_EXCLUSIVE to select the access mode.
    An opaque token pointer is returned.

    If a conflicting request is received while the token is held,
	callback(Tok_Token t, ClientData d)
    is invoked to notify the client of this situation.  The client
    should generally release the token as soon as possible.

    The callback is invoked at most once and is run in a separate
    thread.  If a null callback address is supplied, the client cannot
    be notified.  This is reasonable if the client intends to hold the
    token only momentarily.

    It is an error to make a second request for a token already held
    by the calling client.


ClientData Tok_GetData(Tok_Token t)

    Returns a pointer to the data inside a token.  The pointer is
    guaranteed to be properly aligned for use with any datatype.
    The return value is valid only until the next Tok_SetData or
    Tok_Release call for this token.


int Tok_GetLength(Tok_Token t)

    Returns the length of the data held in a token and returned
    by Tok_GetData.


char *Tok_GetName(Tok_Token t)

    Returns the name of a token.  The returned pointer remains valid
    only until the token is released by a call to Tok_Release.


int Tok_GetAccess(Tok_Token t)

    Returns TOK_SHARED or TOK_EXCLUSIVE indicating the access mode
    of a token.


void (*Tok_GetCallback())(Tok_Token t)

    Returns the callback function, which may be null, associated with 
    a token.


ClientData Tok_GetArgument(Tok_Token t)
    
    Returns the client data associated with the callback function of
    a token.


void Tok_SetData(Tok_Token t, ClientData d, int length)
   
    Replaces the local copy of the data associated with a currently
    held token.  The data is copied, so the caller need not preserve
    it beyond the call.  Any previous value returned by Tok_GetData()
    is rendered invalid by this call.  The new data is not forwarded
    to the server.


void Tok_Update(Tok_Token t)

    Sends updated data to the token server without releasing the token.
    Requests granted subsequently for this token will see the new data,
    but the new data is not forwarded to any other current holders.

    Tok_Update has no effect:
    --  if Tok_SetData has not been called since the token was granted
    --  if Tok_Update has already been called since the last Tok_SetData
    --  if the server has requested revocation of this token
        (in which case the expected Tok_Release call will update it)


void Tok_Release(Tok_Token t)

    Returns a token to the token service.   This is the inverse of
    Tok_Request.

    After a token has been released, the pointer t becomes invalid,
    and no further actions are allowed on the token.  Additionally,
    pointers returned by Tok_GetName and Tok_GetData for this token
    are also rendered invalid.
