Yui-Wah (Clement) Lee

Abstract

This dissertation addresses a bottleneck problem in mobile file systems: the propagation of updated large files from a weakly-connected client to a server. It proposes a new and more efficient mechanism called operation-based update propagation,oroperation shipping. In the new mechanism, the client ships the user operation that updated the large files, rather than the files themselves, across the weak network. (In contrast, existing mechanisms use value shipping and ship the files.) The user operation is sent to a surrogate client that is strongly connected to the server. The surrogate replays the user operation, re-generates the files, and checks whether they are identical to the originals. If so, it will send the files to the server on behalf of the client. If not, it will report the failure to the client, which will then fall back to use value shipping to propagate the files. Note that the new mechanism neither compromises correctness nor hampers server scalability.

There are two types of operation shippings: application-transparent and application-aware. Their feasibilities and benefits have been demonstrated by the design, implementation, and evaluation of three realistic prototypes. These prototypes are extended from three existing systems: the Coda File System, the Bourne Again Shell (bash), and the GIMP (an image application). The bash shell is chosen as an example interactive shell that works with Coda in application-transparent operation shipping; the GIMP is chosen as an example interactive application that works with Coda in application-aware operation shipping. In the former case, many existing non-interactive applications do not need to be modified for being involved in operation shipping; in the latter case, the existing interactive applications do need some moderate modifications.

The prototypes have been evaluated using controlled experiments. The experiments have demonstrated the huge performance improvements of operation shipping, which ranged from 40 percents to nearly three orders of magnitude in terms of reduced network traffic and elapsed time. Besides, this work has made the following three main contributions: techniques for fixing non-repeating side effects (a novel use of forward error correction, and the technique of temporary-file renaming), a technique for re-enabling the use of cancellation optimization with operation shipping, and a study on the design alternatives for the support of application-aware operation shipping.