Wayback file system

We describe the implementation of Wayback, and evaluate its performance using several benchmarks. Skip to main content. Conferences Students Sign in. Brian Cornell, Northwestern University. Peter A. Dinda, Northwestern University. As can be seen, the application uses a hibernate object-relational mapping layer to communicate with a relational database. The code has only been tested with DerbyDB and postgresql.

The NetarchiveSuite-specific settings are as follows:. Since indexing is a relatively intensive operation, it is useful to be able to specify which replica is used by the indexer. At present there is no way, other than manipulating the database, to retry indexing a file once it has reached this limit.

The value of this parameter is a compromise between updating the index as quickly as possible and overburdening the repository with heavy-duty FileListBatchJobs. This can be used when deploying the indexer to a legacy system to ensure that archive files already indexed are not reindexed at unnecessary computational expense.

To summarise, the indexer behaviour is that it reads all newly archived files based on their filesystem timestamp at some specified short interval, and then at some much longer interval reads a list of all the files in the archive to check for any unexplained holes in the index coverage. Tuning of these parameters is a matter for the individual repository, but one possibility would be to fetch a list of files updated in the last 24 hours every half-hour and a list of every file in the archive once a week.

The aggregator takes all files found in the indexer's output directory, sorts them, and merges them into an existing index file. The unix sort command is used so this application runs only in unix-like systems. The aggregator uses a rollover system to deal with the growth of index files.

At any given time, the active index files will consist of a list such as. Whenever the aggregator runs the interval between aggregator runs is determined by the parameter dk. If this file is now larger than dk. If this would cause wayback.

Note that at present the names of these index files are hard-coded. In addition to the settings described above, the aggregator also uses. When unlink is called on a regular file, the file is first truncated to zero length to preserve the contents of the file before deletion. Next, the directory catalog is updated with data consisting of the attributes of the file mode, owner, and times and the filename that is being deleted.

For links, the destination is also recorded. Calls to rmdir in Wayback actually translate to calls to rename. Directories are never deleted because their contents would be lost. Subsequently, and for user-initiated rename calls, the directory catalog is updated with data consisting of the old name of the file or directory, and the new name of the file or directory.

When chmod , chown , or utime is called, the directory catalog is updated with data c onsisting of the attributes of the file and the filename for which attributes are being changed. We encountered several issues while designing and implementing Wayback. The solutions we found and decisions we made have defined what Wayback is now.

The first major decision we had to make was whether this file system should be implemented in the kernel as its own file system, or using a user-level module. The trade-offs are in speed, ease of implementation, and features.

A kernel module would undoubtedly be much faster because the user-level overhead would be avoided. However, it could limit compatibility to certain kernel versions, and it would preclude adding versioning to existing file systems. It would also be much harder to implement a kernel module. The main factor in our decision to make a user-level file system had to do with the features we could easily implement.

We considered writing Wayback as a kernel-level extension to ext3. This would probably have been faster, but it would have been limited to ext3 file systems on normal block devices.

Implementing Wayback as a user-level file system would make it slower, but would let us remount any file system with versioning. Wayback logs changes as undo records. We recover previous versions by applying these records in reverse order until the appropriate version is reached.

This is straightforward, but it has a downside: while reverting to newer versions is very fast, reverting to very old versions can take some time. One alternative is a redo log, in which modifications themselves are written as log records.

Recovering an old version means applying the records in forward order until the appropriate version is reached. This has the advantage of allowing very old versions to be recovered very quickly, but newer versions are slow. Each logging technique can be combined with periodic checkpointing, providing snapshots of the whole file state from which to move forward or backward using the log.

We chose simple undo logging for Wayback because we felt that for our use cases — reverting mistakes made in editing programs and documents — we would typically have only to move backward by a small number of versions. In light of other applications we would like to support see Conclusion , we are reconsidering our logging model.

Once we had decided on a user-level approach, we next considered how to interact with the kernel. FUSE proved to be relatively stable and easy to use. Early versions of FUSE did not provide an upcall for the close system call. This lack would have made it impossible to create new versions on close, as in VMS. Fortunately, we had determined to do write-level versioning. However, it still indirectly affected Wayback's design. In particular, without close calls, managing file descriptors for log files is made unnecessarily difficult.

After deciding to use FUSE, we quickly came upon another issue. FUSE is designed only to provide a destination path for the file system, and not a source path to mount there. The examples for FUSE either remount an entire directory structure beginning in the root directory, or provide their own root from a different source such as memory. We decided that we wanted to have redirection from any path, not just the root directory, so we had to implement a work-around.

A variety of performance tests were run on Wayback FS to evaluate its performance. These tests include Bonnie [Bonnie], which performs various operations on a very large file; the Andrew Benchmark [Andrew], which simulates the operation of normal file systems; and a test that compares using Wayback FS to using manual checkins with RCS.

These tests were all run on three test systems:. Machine B: Intel Pentium 4 2. All of the tests were run under Linux kernel 2.

For comparison, another file system was built on top of FUSE before tests were run. This file system simply redirects requests from the mounted file system through to the underlying file system, acting as a pass-through. This file system is used to identify the performance hit taken solely by the FUSE system, and isolate the performance loss from versioning.

We consider the following file systems:. These configurations were used for our Bonnie and Andrew tests. We did not run any tests on the performance of reverting files, because it is not an everyday occurrence and shouldn't matter as much as reading and writing performance. Reverting or extracting a recent state from a file typically takes at the most seconds if not less than a second. Disk space usage does increase when reverting files depending on the size of the reversion, because Wayback does not remove the reverted entries from the log.

Rather it runs them backwards on the file, creating more entries in the log. Bonnie was originally created by Tim Bray to identify bottlenecks in file systems. Bonnie is implemented as a single C program.

The program takes arguments for the size of the file it will use and the path where it will be stored. Bonnie then creates the large file and performs many sequential operations on it, including writing character by character, writing block by block, rewriting, reading character by character, reading block by block, and seeking. For this test, Bonnie was run with a file size of 1 GB. Figures show the performance of the different Bonnie phases on the three machines.

For each phase and machine, we compare ext3, ext3 via our pass-through FUSE file system , and ext3 with Wayback versioning.

The point is to measure how much performance is lost by using Wayback and how it breaks down into FUSE overheads and the actual costs of Wayback. It is important to point out that in some cases layering ext3 below FUSE actually increases its performance. We expect that this is due to buffering effects as there is now an additional process which can buffer.

Additionally, the overheads shown in Figure 4 are slightly misleading. Bonnie is measuring the system and user time it uses, but does not count the time spent in the Wayback server on its behalf.

Figure 2. Bonnie Performance on Machine B. Figure 1. Bonnie Performance on Machine A. Figure 3. Bonnie Performance on Machine C. Figure 4. Bonnie Overheads. The largest impact on write speed is on machines with fast disks, particularly those that also have slow processors. The largest impact on rewrite speed is on machines with slow disks, which is to be expected as rewrites will include additional data to be written to the logs.

Read speed is maximally affected on slow machines with fast disks. In many cases, a large portion, often the majority of the performance impact is due to FUSE rather than versioning. The Andrew Benchmark, although quite old, is commonly used to measure the performance of file systems. It performs operations similar to those performed every day on file systems, including making directories, copying files, stating and reading files, and compiling a program. The original Andrew Benchmark was written on and designed for Sun computers.

It consists of a makefile that executes operations in five phases, ending in the compilation of a program. The program used in the benchmark will only compile on Sun systems however. The Andrew benchmark also only runs each phase once, and does not delete the files it creates. Because of these limitations, we rewrote the Andrew Benchmark in Perl. The program runs the same phases as the original Andrew Benchmark, except that it can run them with any set of files.

It can also run the test multiple times and print a summary. The phases of the Andrew Benchmark are designed to emulate everyday use of a file system. The phases are all done using the source directory of a program, and include:. Phase 1: Create five copies of the directory structure in the source tree.

Phase 2: Copy all of the files from the source tree into the first set of directories created.