Introduction

Pastwatch is a cooperative and version controlled read/write file sharing system. The goal of the system is to allow users on a wide-area network to collaboratively create and edit information. The main challenge is to provide an available, reliable, and consistent system despite potentially unreliable and untrustworthy computers, networks, and users.

The rapid expansion of the Internet facilitates collaboration among geographically distributed and loosely affiliated users. An example of this kind of collaboration is when programmers from different institutions collaborate on an open-source software. Typically, members of an open-source project share a writable repository of the software's source code. Each member may choose to work on a piece of the source code, but members expect to see each other's committed changes. Many projects also grant read-only access to the repository to non-project members, so they can actively participate in testing different versions of the software. This technique also enables related projects to share source code.

The number of open-source software projects is rapidly growing; SourceForge, a free open-source software development portal, currently hosts repositories for over 98,000 projects and 1,000,000 users, with an observed increase of 10 projects per day. The popularity of SourceForge demonstrates that supporting global read/write file sharing is an emerging application.

Wide-area collaboration differs from the more conventional, LAN-based intra-organization collaboration in several important ways. First, many users from different organizations may participate in a project. Some of these users make changes to the project's data, while others only read. Second, users may be geographically distributed; their computers may reside on different networks. It would be desirable if shared files remain available even if some network connections fail. Third, because users do not come from the same organization, they may not all have the privilege to access a server from any one organization. Finally, if a collaborative project is not well funded by a single organization, there may not be enough reliable resources dedicated to the project.

None of the existing read/write file sharing techniques adequately addresses all these challenges. For example, SourceForge maintains a set of reliable servers that host repositories for open-source projects. SourceForge grants accounts to all registered users and has demonstrated enough good-will to earn the trust of most of its users. Unfortunately, the popularity of SourceForge also highlights a problem of using a centralized service. Despite SourceForge's continuing efforts to upgrade its network and computing facilities to keep up with the increasing number of users, its service frequently suffers from server overload, network congestion, and software and hardware failures. For example, in January of 2004, SourceForge repositories were unavailable for at least 40 hours.

Goals

Pastwatch has the following goals.

• It should provide read/write file sharing so project members can cooperatively edit shared files.
• It should provide up-to-date access to the repository to read-only users, even if no project members are on-line.
• It should avoid single points of failure, so shared files remain available even if some members' computers or network connections fail.
• It should support partitioned operations, so project members can make changes to the shared files even if the network partitions or if a member disconnects from the network.

A Cooperative Approach

Pastwatch replicates a project's repository onto each user's computer, so even if a user becomes disconnected, the repository remains available. The question, then, becomes how and when to synchronize the repository replicas to achieve consistency.

Pastwatch takes a cooperative approach to propagating changes between repository replicas. Instead of storing a master copy of a repository on a server and asking users to contact the server to synchronize their replicas, Pastwatch replicates data that represents a project's repository and different users changes onto multiple computers from different organizations. For example, a cooperative arrangement that uses Pastwatch to provide file sharing for open-source projects could involve computers that belong to different projects and the thousands of Internet servers that already contribute resources to help distribute open-source software.

There are three main benefits of this cooperative approach. First, replicating a repository's data across many computers avoids single points of failure. Second, cooperative storage can harness idle network and storage resources from people who are willing to donate them. Finally, cooperative storage can easily absorb new resources, and thus has the potential to scale naturally with the number of project members and read-only users. Pastwatch fulfills its cooperative vision by using a peer-to-peer distributed hash table (DHT) [1] to store the data that make up a project's repository.

Overview

Pastwatch achieves its goals using the following architecture. At a high level, a Pastwatch project consists of a directory hierarchy of version controlled files shared by a set of users. Pastwatch stores its repository of current and historical versions of the files in the form of a set of repository replicas, one on each user's computer. A user never directly modifies a repository replica. Instead, the user checks-out a copy of the directory hierarchy from a replica into a working directory on the user's local file system, makes changes to these local files, then commits the changes back into the repository. Any user can build a repository replica and check-out a working directory, but only project members can commit changes. This user interface is similar to that of CVS.

A user commits changes to a repository by creating a new leaf node in a virtual version tree. At a high level, each node in the tree represents the state of the shared files at a point in time. Operationally, each node contains a user's changes that, when applied to the state in the parent node, produces the new state. A node also contains a pointer to the parent node.

When users commit changes serially within a single partition, all the changes appear sequentially in the tree. If two users commit changes in separate network partitions, a fork appears in the tree. A repository branch consists of the set of changes between the root of the tree and a leaf node. Pastwatch preserves sequential consistency within each branch. Before most repository operations, Pastwatch scans the tree to bring the local replica up-to-date.

Future

We plan to deploy Pastwatch on the Internet this year and encourage users to adopt it.

Research Support

This research is part of the IRIS project which is supported by the National Science Foundation under Cooperative Agreement No. ANI-0225660. It is also partly funded by an NSF Career Grant.

References:

[1] F. Dabek, M. Frans Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In Proceedings of the 18th Symposium on Operating System Principles, October 2001.