Structure of a file system

**Figure 2:** An example of a directory ``/joe'' containing file ``/joe/foo''. Each replica of ``joe'' stores three pointers to the gold replicas of ``foo'' for path-name traversal. Each replica of ``foo'' keeps a backpointer to the parent directory. Bronze replicas are connected randomly to form strongly connected graphs. Bronze replicas also have uni-directional links to the gold replicas of the file, which are not shown here.
$\includegraphics[width=5in]{htmlfigures/file-structure.eps}$

Pangaea decentralizes both the replica-set and consistency management by maintaining a distributed graph of replicas for each file. Figure 2 shows an example of a system with two files. Pangaea distinguishes two types of replicas: gold and bronze. They can both be read and written by users at any time, and they both run an identical update-propagation protocol. Gold replicas, however, play an additional role in maintaining the hierarchical name space.

First, gold replicas act as starting points from which bronze replicas are found during path-name traversal. To this end, the directory entry of a file lists the file's gold replicas. Second, gold replicas perform several tasks that are hard to do in a completely distributed way. In particular, they are used as pivots to keep the graph connected after a permanent node failure, and to maintain a minimum replication factor for a file. They form a clique in the file's graph so that they can monitor each other for these tasks. These issues are discussed in more detail in Section 4. Currently, Pangaea designates replicas created during initial file creation as gold and fixes their locations unless some of them fail permanently.

Each replica stores a backpointer that indicates its location in the file-system name space. A backpointer includes the parent directory's ID and the file's name within the directory.¹It is used for two purposes: to resolve conflicting directory operations (Section 5.2), and to keep the directory entry up-to-date when the gold replica set of the file changes (Section 6.2).

**Figure 3:** Key attributes of a replica.
$\begin{figure}\begin{center} \begin{pseudocode} \pstruct \type{Replica} \makeb... ...et{NodeID} ts: \type{Timestamp} \pend \end{pseudocode} \end{center}\end{figure}$

Figure 3 shows the key attributes of a replica. The timestamp (ts) and the version vector (vv) [23] record the last time the file was modified. Their use is described in more detail in Section 5. GoldPeers are uni-directional links to the gold replicas of the file. Peers point to the neighboring (gold or bronze) replicas in the file's graph.