Using Dynamic Sets to Reduce the Aggregate Latency of Data Access

摘要

Many users of large distributed systems are plagued by high latency whenaccessing remote data. Latency is particularly problematic for the critical application of search and retrieval, which tends to access many objects and may suffer a long wait for each object accessed. Existing techniques like caching, inferential prefetching, and explicit prefetching are not suited to search, are ineffective at reducing latency for search applications, or greatly increase the complexity of the programming model. This dissertation shows that extending the file system interface to support a new abstraction called dynamic sets can address the problem of latency for search without incurring the penalties of the other techniques. A dynamic set is a lightweight and transitory collection of objects with well-defined semantics. An application creates a dynamic set on-demand to hold the objects it wishes to process. Adding dynamic sets to the system's interface results in two benefits. First, creation of a set discloses the application's interest in the set's members to the system. This allows the system to reduce the aggregate I/O latency of search through prefetching and reordering of requests. Second, dynamic sets provide direct support for accessing and manipulating sets of objects. Thus dynamic sets improve performance and functionality without unduly increasing the complexity of the programming model. This dissertation describes the design of the dynamic sets abstraction, an implementation which adds dynamic sets to the 4.3BSD file system interface, and an evaluation of the implement at ion. The implementation allows several applications, including Unix search tools and a WWW browser, to access sets of Coda, NFS, WWW, and local file system objects. With little effort one can modify other applications to use sets or extend the implementation to allow access to other systems.