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.