Improving the input/output performance and correctness of network file systems
Randolph Yuantao Wang, David K. Patterson, Thomas E. Anderson · 1999
Traditional components, interfaces, tools, and engineering methodology for building distributed systems are inadequate for the new peer-to-peer system architecture. In order to meet the challenges presented by the new technology and manage the increasing complexity, I argue in this dissertation that we need a new approach to the construction of a network file system, in terms of both performance and correctness. I examine three key components of a network file system: the communication subsystem, the disk subsystem, and the cache coherence subsystem. First, I present a series of pipeline theories that systematically employ dynamic fragmentation to lower the cost of communication of file block sized messages. I describe a methodology for discovering pipeline characteristics and constructing customized pipeline algorithms. Experiments show that the pipeline theories can accurately predict system behavior and significantly improve its performance. Next, I present the design of a virtual log, a transactional log whose entries are not necessarily physically contiguous. This design leverages the embedded processor inside the disk to take advantage of the combination of knowledge of disk mechanisms and file system semantics. The virtual log can deliver an order of magnitude better transaction latency compared to traditional update-in-place policies. Finally, I show how to employ formal methods to manage the complexity of the cache coherence protocol construction. This approach allows us to build systems that are correct by design, not by brute force testing. These three components simultaneously enable and necessitate each other. Together, they allow the peer-to-peer systems to truly realize their performance potential.