Search

File system bugs that corrupt metadata on disk are insidious. Existing reliability methods, such as checksums, redundancy, or transactional updates, merely ensure that the corruption is reliably preserved. Typical workarounds, based on using backups or repairing the file system, are painfully slow. Worse, the recovery may result in further corruption. We present Recon, a system that protects file system metadata from buggy file system operations. Our approach leverages file systems that provide crash consistency using transactional updates. We define declarative statements called consistency invariants for a file system. These invariants must be satisfied by each transaction being committed to disk to preserve file system integrity. Recon checks these invariants at commit, thereby minimizing the damage caused by buggy file systems. The major challenges to this approach are specifying invariants and interpreting file system behavior correctly without relying on the file system code. Recon provides a framework for file-system specific metadata interpretation and invariant checking. We show the feasibility of interpreting metadata and writing consistency invariants for the Linux ext3 file system using this framework. Recon can detect random as well as targeted file-system corruption at runtime as effectively as the offline e2fsck file-system checker, with low overhead.

We collected file system content data from 857 desktop computers at Microsoft over a span of 4 weeks. We analyzed the data to determine the relative efficacy of data deduplication, particularly considering whole-file versus block-level elimination of redundancy. We found that whole-file deduplication achieves about three quarters of the space savings of the most aggressive block-level deduplication for storage of live file systems, and 87% of the savings for backup images. We also studied file fragmentation, finding that it is not prevalent, and updated prior file system metadata studies, finding that the distribution of file sizes continues to skew toward very large unstructured files.

This article presents a new Fast Hash-based File Existence Checking (FHFEC) method for archiving systems. During the archiving process, there are many submissions which are actually unchanged files that do not need to be re-archived. In this system, instead of comparing the entire files, only digests of the files are compared. Strong cryptographic hash functions with a low probability of collision can be used as digests. We propose a fast algorithm to check if a certain hash, that is, a corresponding file, is already stored in the system. The algorithm is based on dividing the whole domain of hashes into equally sized regions, and on the existence of a pointer array, which has exactly one pointer for each region. Each pointer points to the location of the first stored hash from the corresponding region and has a null value if no hash from that region exists. The entire structure can be stored in random access memory or, alternatively, on a dedicated hard disk. A statistical performance analysis has been performed that shows that in certain cases FHFEC performs nearly optimally. Extensive simulations have confirmed these analytical results. The performance of FHFEC has been compared to the performance of a binary search (BIS) and B+tree, which are commonly used in file systems and databases for table indices. The results show that FHFEC significantly outperforms both of them.

Storage management activities, such as reporting, file placement, migration and archiving, require the ability to discover files that belong to an application workflow by relying only on information from the file server. Some classes of application workflows, such as rendering an animated sequence from its graphics models or building an application from its source files, often exhibit a high degree of repeatability. We describe a system called Autograph that exploits this repeatability to discover files that belong to an application workflow. Our approach examines traces of file accesses, finds repeated and correlated accesses, and infers which files likely belong to the same workflow. Our solution targets server workflows and uses file server traces, which contain less process and file information than the local machine traces used in prior work. We show that Autograph successfully extracts workflow file signatures, even if the workflows are concurrent or share files.

Users tend to store huge amounts of files, of various formats, on their personal computers. As a result, finding a specific, desired file within the file system is a challenging task. This article addresses the desktop search problem by considering various techniques for ranking results of a search query over the file system. First, basic ranking techniques, which are based on various file features (e.g., file name, access date, file size, etc.), are considered and their effectiveness is empirically analyzed. Next, two learning-based ranking schemes are presented, and are shown to be significantly more effective than the basic ranking methods. Finally, a novel ranking technique, based on query selectiveness, is considered for use during the cold-start period of the system. This method is also shown to be empirically effective, even though it does not involve any learning.

Pangaea is a wide-area file system that supports data sharing among a community of widely distributed users. It is built on a symmetrically decentralized infrastructure that consists of commodity computers provided by the end users. Computers act autonomously to serve data to their local users. When possible, they exchange data with nearby peers to improve the system's overall performance, availability, and network economy. This approach is realized by aggressively creating a replica of a file whenever and wherever it is accessed.This paper presents the design, implementation, and evaluation of the Pangaea file system. Pangaea offers efficient, randomized algorithms to manage highly dynamic and potentially large groups of file replicas. It applies optimistic consistency semantics to replica contents, but it also offers stronger guarantees when required by the users. The evaluation demonstrates that Pangaea outperforms existing distributed file systems in large heterogeneous environments, typical of the Internet and of large corporate intranets.

Peer-to-Peer (P2P) file sharing software has brought a hot discussion on P2P file sharing among all businesses. Freenet, Gnutella, and Napster are the three most popular P2P file sharing applications. They use three distinct protocols and these protocols come with different characteristics. In this paper, we discuss the protocols of these P2P file sharing applications, in terms of the methodologies used for peer registry, query and content sharing. In order to maximize the benefit of P2P file sharing application that is to facilitate file sharing among various P2P file sharing applications, we propose a framework to integrate various P2P file sharing protocols using P2P gateway in this paper.

Distributed file systems are often used to replicate a Web site's content among its many servers. However, for content that needs to be dynamically updated and distributed to many servers, file system locking protocols exhibit high latency and heavy network usage. Poor performance arises because the Web-serving workload differs from the assumed workload. To address the shortcomings of file systems, we introduce the publish consistency model well suited to the Web-serving workload and implement it in the producer-consumer locking protocol. A comparison of this protocol against other file system protocols by simulation shows that producer-consumer locking removes almost all latency due to protocol overhead and significantly reduces network load.

We collect and analyze a snapshot of data from 10,568 file systems of 4801 Windows personal computers in a commercial environment. The file systems contain 140 million files totaling 10.5 TB of data. We develop analytical approximations for distributions of file size, file age, file functional lifetime, directory size, and directory depth, and we compare them to previously derived distributions. We find that file and directory sizes are fairly consistent across file systems, but file lifetimes vary widely and are significantly affected by the job function of the user. Larger files tend to be composed of blocks sized in powers of two, which noticeably affects their size distribution. File-name extensions are strongly correlated with file sizes, and extension popularity varies with user job function. On average, file systems are only half full.

We present a scalable distributed data structure called LH*. LH* generalizes Linear Hashing (LH) to distributed RAM and disk files. An LH* file can be created from records with primary keys, or objects with OIDs, provided by any number of distributed and autonomous clients. It does not require a central directory, and grows gracefully, through splits of one bucket at a time, to virtually any number of servers. The number of messages per random insertion is one in general, and three in the worst case, regardless of the file size. The number of messages per key search is two in general, and four in the worst case. The file supports parallel operations, e.g., hash joins and scans. Performing a parallel operation on a file of M buckets costs at most 2 M + 1 messages, and between 1 and O (log 2 M rounds of messages. We first describle the basic LH* scheme where a coordinator site manages abucket splits, and splits a bucket every time a collision occurs. We show that the average load factor of an LH* file is 65%–70% regardless of file size, and bucket capacity. We then enhance the scheme with load control, performed at no additional message cost. The average load factor then increases to 80–95%. These values are about that of LH, but the load factor for LH* varies more. We nest define LH* schemes without a coordinator. We show that insert and search costs are the same as for the basic scheme. The splitting cost decreases on the average, but becomes more variable, as cascading splits are needed to prevent file overload. Next, we briefly describe two variants of splitting policy, using parallel splits and presplitting that should enhance performance for high-performance applications. All together, we show that LH* files can efficiently scale to files that are orders of magnitude larger in size than single-site files. LH* files that reside in main memory may also be much faster than single-site disk files. Finally, LH* files can be more efficient than any distributed file with a centralized directory, or a static parallel or distributed hash file.

This paper presents ParFiSys, a parallel and distributed file system developed at the UPM. It provides several types of distributed file systems, which may be accessed using different mapping functions. Grouped management and parallelization are presented as new features of ParFiSys, not included in other existing parallel and distributed file systems. Moreover, the ParFiSys interface is briefly explained to show the facilities available to general purpose and supercomputing application programmers.

The increasing need for data sharing in large-scale distributed systems may place a heavy burden on critical resources such as file servers and networks. Our examination of the workload in one large commercial engineering environment shows that wide-spread sharing of unstable files among tens to hundreds of users is common. Traditional client-based file cacheing techniques are not scalable in such environments. We propose Frolic, a scheme for cluster-based file replication in large-scale distributed file systems. A cluster is a group of workstations and one or more file servers on a local area network. Large distributed systems may have tens or hundreds of clusters connected by a backbone network. By dynamically creating and maintaining replicas of shared files on the file servers in the clusters using those files, we effectively reduce reliance on central servers supporting such files, as well as reduce the distances between the accessing sites and data. We propose and study algorithms for the two main issues in Frolic, 1) locating a valid file replica, and 2) maintaining consistency among replicas. Our simulation experiments using a statistical workload model based upon measurement data and real workload characteristics show that cluster-based file replication can significantly reduce file access delays and server and backbone network utilizations in large-scale distributed systems over a wide range of workload conditions. The workload characteristics most critical to replication performance are: the size of shared files, the number of clusters that modify a file, and the number of consecutive accesses to files from a particular cluster.

This paper describes different methods and techniques used to model, analyze, evaluate and implement distributed file systems. Distributed file systems are characterized by the distributed system hardware and software architecture, in which they are implemented as well as by the file systems' functions. In addition, distributed file system performance depends on the load executed in the system. Modeling and analysis of distributed file systems requires new methods to approximate complexity of the system and to provide a useful solution. The complexity of the distributed file system is reflected in the possible placement of the files, file replication, and migration of files and processes. The synchronization mechanisms are needed to control file access. File sharing involves load sharing in distributed environment.

Recent measurement studies [8] have shown that peer-to-peer (P2P) file sharing applications are the major traffic source in the Internet. P2P applications, such as eDonkey, Kazaa, or BitTorrent, form overlay networks on the application layer and offer its peers to download and share their files with other peers in a highly distributed way. As a consequence, peers act simultaneously as both clients and servers. For a comprehensive survey of P2P technology, we refer to [7].

For five years, we collected annual snapshots of file-system metadata from over 60,000 Windows PC file systems in a large corporation. In this article, we use these snapshots to study temporal changes in file size, file age, file-type frequency, directory size, namespace structure, file-system population, storage capacity and consumption, and degree of file modification. We present a generative model that explains the namespace structure and the distribution of directory sizes. We find significant temporal trends relating to the popularity of certain file types, the origin of file content, the way the namespace is used, and the degree of variation among file systems, as well as more pedestrian changes in size and capacities. We give examples of consequent lessons for designers of file systems and related software.

RAID storage arrays often possess gigabytes of RAM forcaching disk blocks. Currently, most RAID systems use LRUor LRU-like policies to manage these caches. Since these arraycaches do not recognize the presence of file system buffer caches,they redundantly retain many of the same blocks as those cachedby the file system, thereby wasting precious cache space. In thispaper, we introduce X-RAY, an exclusive RAID array cachingmechanism. X-RAY achieves a high degree of (but not perfect) exclusivitythrough gray-box methods: by observing which files havebeen accessed through updates to file system meta-data, X-RAYconstructs an approximate image of the contents of the file systemcache and uses that information to determine the exclusive set ofblocks that should be cached by the array. We use microbenchmarksto demonstrate that X-RAY's prediction of the file systembuffer cache contents is highly accurate, and trace-based simulationto show that X-RAY considerably outperforms LRU andperforms as well as other more invasive approaches. The mainstrength of the X-RAY approach is that it is easy to deploy - allperformance gains are achieved without changes to the SCSI protocolor the file system above.

This paper describes an extension to the APL-S system that allows accessing directly from one host computer the files based on other computers tied to the same public network. APL-NET makes easy the development of distributed processing applications by handling internally all synchronization problems inherent to cooperating processes on different machines.

A new file organization method that guarantees retrieval of any record in one access is tested on two existing files, producing empirical results that compare favorably with theoretical predictions. The description of the method includes the algorithms used for implementing the required hashing and signature functions.

A simple algorithm is described for isolating the differences between two files. One application is the comparing of two versions of a source program or other file in order to display all differences. The algorithm isolates differences in a way that corresponds closely to our intuitive notion of difference, is easy to implement, and is computationally efficient, with time linear in the file length. For most applications the algorithm isolates differences similar to those isolated by the longest common subsequence. Another application of this algorithm merges files containing independently generated changes into a single file. The algorithm can also be used to generate efficient encodings of a file in the form of the differences between itself and a given “datum” file, permitting reconstruction of the original file from the diference and datum files.

Currently data files to be accessed remotely from dissimilar systems must be transformed to the local language processors' file format and data representation; a process that has changed little since punch cards were the main form of portable data files. A standard is proposed for languages to use the data type information available to the runtime library to make these data transformations before the data is transferred to the file or the user's variables. By specifying one binary format for each basic data type (integer, real, logical, etc) and a file organization that is portable between record-oriented and stream-oriented file systems, we can standardize file formats that will be usable on practically all current systems.

A file organization for cluster-based retrieval is presented and tested. This file organization is based on the bottom-up search which, in contrast to the more usual top-down search, starts at the lowest level of a cluster hierarchy (the documents) and looks at progressively larger clusters. This approach enables most of the efficiency problems previously associated with clustered file organizations to be avoided. There are two parts to this file organization - a compact cluster hierarchy representation which does not store cluster representatives and a compact inverted file which is used to provide a starting point for the bottom-up search. Retrieval experiments show that the bottom-up search using this file organization can be more effective than a serial search, especially if high precision results are required.

One of the main objectives in the design of a file system is the reduction of storage and data transfer costs. This paper presents a model in which several requests access the file system, and each request requires information from one or more variable length data-items. The probabilities of access and the distribution of each data-item's length are assumed to be known, and to be mutually independent. The file system uses one or more storage devices, and each record may be partitioned into subrecords that are stored on different devices. One of the subrecords is designated as the primary record; when a request for a record is made, the primary record is first accessed, and other sub-records are accessed only if the pertinent information is not stored in the primary record. The model that is presented in this paper, both as a nonlinear programming model and a mixed integer programming model, is a very general one; several types of file systems may be derived from it by an appropriate selection of its parameters. This model has already been used in the optimization of library routines' storage at a large scale operating system.

The steady increase in the power and complexity of modern computer systems has encouraged the implementation of automatic file migration systems which move files dynamically between mass storage devices and disk in response to user reference patterns. Using information describing 13 months of user disk data set file references, we develop and evaluate (replacement) algorithms for the selection of files to be moved from disk to mass storage. Our approach is general and demonstrates a general methodology for this type of problem. We find that algorithms based on both the file size and the time since the file was last used work well. The best realizable algorithms tested condition on the empirical distribution of the times between file references. Acceptable results are also obtained by selecting for replacement that file whose size times time to most recent reference is maximal. Comparisons are made with a number of standard algorithms developed for paging, such as Working Set, VMIN, and GOPT. Sufficient information (parameter values, fitted equations) is provided so that our algorithms may be easily implemented on other systems.

Binary search trees are an important technique for organizing large files, because they are efficient for both random and sequential access of records, and for modification of a file. Because of this, they have received a great deal of attention in recent years, and their properties are now better understood than those of most other file organization methods. This paper surveys the main results which have been obtained.

In distributed systems the efficiency of the network file system is a key performance issue. Replication of files and directories can enhance file system efficiency, but the choice of replication techniques is crucial. This paper studies a number of replication techniques, including remote access, prereplication, weighted voting, and two demand replication schemes: polling and staling. It develops a Markov chain model, which is capable of characterizing properties of file access sequences, including access locality and access bias. The paper compares the replication techniques under three different network file system architectures. The results show that, under reasonable assumptions, demand replication requires fewer file transfers than remote access, especially for files that have a high degree of access locality. Among the demand replication schemes, staling requires fewer auxiliary messages than polling.

There exist a number of file systems with different solutions to the problems of data access, concurrency control [1], serializing transactions [5], deadlock control and recoverability. There are pros and cons to every solution, and not all solutions are independent of each other. Also, depending on the applications, a file system can be designed in several different ways.

This work first discusses the factors that affect file (data base) organization performance, an elusive subject, and then presents a methodology, a model and a programmed system to estimate primarily total storage costs and average access time of several file organizations, given a specific data base, query characterization and device-related specifications. Based on these estimates, an appropriate file structure may be selected for the specific situation. The system is a convenient tool to study file structures and to facilitate as much as possible the process of data base structure design and evaluation.

A generalized file structure is provided by which the concepts of keyword, index, record, file, directory, file structure, directory decoding, and record retrieval are defined and from which some of the frequently used file structures such as inverted files, index-sequential files, and multilist files are derived. Two algorithms which retrieve records from the generalized file structure are presented.

When the data processed by a program span several files, the common practice of including file names as data in some of the files leads to difficulties in moving or sharing that data. In systems using tree structured directories, this problem can be solved by making a syntactic distinction between absolute and relative file names.

New challenges to file systems' metadata performance are imposed by the continuously growing number of files existing in file systems. The total amount of metadata can become too big to be cached, potentially leading to multiple storage device accesses for a single metadata lookup operation. This paper takes a look at the limitations of traditional file system designs and discusses an alternative metadata handling approach, using hash-based concepts already established for metadata and data placement in distributed storage systems. Furthermore, a POSIX compliant prototype implementation based on these concepts is introduced and benchmarked. A variety of file system metadata and data operations as well as the influence of different storage technologies are taken into account and performance is compared with traditional file systems.

This paper compares two working network-based file servers, the Xerox Distributed File System (XDFS) implemented at the Xerox Palo Alto Research Center, and the Cambridge File Server (CFS) implemented at the Cambridge University Computer Laboratory. Both servers support concurrent random access to files using atomic transactions, both are connected to local area networks, and both have been in service long enough to enable us to draw lessons from them for future file servers. We compare the servers in terms of design goals, implementation issues, performance, and their relative successes and failures, and discuss what we would do differently next time.