Ajay Mohindra
Murthy Devarakonda
In this paper, we present the design and implementation of a distributed token manager for a cluster-optimized, distributed Unix file system. Tokens are a well known synchronization mechanism in distributed and multiprocessor systems. Here, in the cluster file system, we use tokens to maintain cache consistency for file data, and to support other single-system Unix semantics such as the semantics of the file open operation. The design goals for the token manager are good performance, deadlock-free operation, avoiding a single point of failure, and recovery from failures.
During 1991 though 1995, we developed a cluster-optimized, distributed Unix file system called Calypso. Calypso is designed to provide single-image file system within an enclosed cluster of RS6000's running AIX. Calypso takes advantage of homogeneity, and specialized hardware such as multi-ported disks and high-speed switch for communication. Calypso provides strong cache consistency and POSIX semantics. Recovery from partial cluster failures and surviving a single failure within the cluster are important requirements for Calypso.
Architecturally, we separated the core file operations and distributed state maintenance into two different subsystems. The file operations consist of fetching, caching, and interpreting the contents and attributes of Unix files. The distributed state maintenance part, on the other hand, provides cache consistency management (e.g., flushing and invalidation of cache as needed) and support for POSIX semantics. The distributed state maintenance part is implemented using tokens, and hence it is called a token manager (TM). A token designates the authority to perform certain operations on a part of a file. So, while a cluster node is holding a read token for a file page, processes on that node may read the file page with the assurance that the contents of the page are valid. This paper describes the following important issues in design and implementation of the token manager:
In this paper we describe a token arbitration protocol that minimizes the load on the cluster node functioning as the `server' (or owner) for tokens. The protocol employs a client-centric (or requester based) approach for revoking or downgrading tokens at the other cluster nodes to accomplish this. This approach also simplifies the design of the server because it can be built as a passive entity that only responds to requests but does not originate any requests on its own.
The contribution of this paper goes beyond presenting the token arbitration protocol and token support for the Calypso file system. A distributed token manager is an involved subsystem and as such it is an excellent example of complexity in distributed programming. The complexity is not so much because of the protocol, but as we show in this paper, even when the protocol is fairly straightforward, its implementation aspects such as serialization, recovery, fault-tolerance, and resource management create enormous complexity which demands careful design, implementation, and testing.