The increasing demand for ssds coupled with scaling difficulties has left manufacturers scrambling for newer ssd interfaces which promise better performance and durability. While these interfaces reduce the rigidity of traditional abstractions, they require application or system-level changes that can impact the stability, security, and portability of systems. To make matters worse, such changes are rendered futile with the introduction of next-generation interfaces. It is therefore no surprise that such interfaces have seen limited adoption, leaving behind a graveyard of experimental interfaces ranging from open-channel ssds to stream ssds.

Existing metadata-private messaging systems are either non-scalable or vulnerable to long-term traffic analysis. Approaches that mitigate traffic analysis attacks often suffer from unrealistic and unimplementable assumptions or impose system-wide bandwidth restrictions, degrading usability, and performance. In this work, we present a new model for metadata-private communication systems-deferred retrieval-that guarantees traffic analysis resistance under realistic, implementable user assumptions. We introduce Sparta systems, practical and scalable instantiations of deferred retrieval that are distributable, achieve high throughput, and support multiple concurrent conversations without message loss. Specifically, we present three Sparta constructions optimized for different scenarios: (i) low-latency, (ii) high-throughput in shared-memory environments (multi-thread implementations), and (iii) high throughput in shared-nothing (distributed) environments. Our low latency Sparta supports latencies of less than one millisecond, while our high-throughput Sparta can scale to deliver over 700,000 100B messages per second on a single 48-core server.

It is essential to utilize a large number of I/O workloads to analyze commodity system performance or simulate scientific phenomena in high-performance scientific computing. I/O traces are often unavailable at scale due to trace storage overhead, privacy concerns, and the performance impact of trace instrumentation. We study how to generate sufficiently representative I/O workloads using Generative Adversarial Networks (GANs). The best GAN architecture can generate I/O workloads with maximum mean discrepancy (MMD) as low as 0.015-0.05, which implies the synthetic I/O workloads have successfully learned the potential distribution of real I/O traces. We demonstrate that the performance similarity between the original I/O trace and the generated I/O workload through trace replay can be 90.36%-97.32%.

Identifying intrusion from massive and multi-source logs accurately and in real-time presents challenges for today's users. This article presents Paradise, a real-time, generalized, and distributed provenance-based intrusion detection method. Paradise introduces a novel extract strategy to prune and extract process feature vectors from provenance dependencies at the system log level, and it stores them in high-efficiency memory databases. Using this strategy, Paradise does not depend on the specific operating system type or provenance collection framework. Provenance-based dependencies are calculated independently during the detection phase, thus, Paradise can negotiate all detection results from multiple detectors without extra communication overhead between detectors. Paradise also employs an efficient load-balanced distribution scheme that enhances the Kafka architecture to efficiently distribute provenance graph feature vectors to the detectors. The experimental results demonstrate that our method has a high detection accuracy with a low time overhead.

The emergence of containers dramatically simplifies and facilitates the development and deployment of applications. More and more enterprises deploy their applications on the container cloud platform. For cloud service providers, an effective container workload prediction method is a must to achieve efficient utilization of cloud resources. However, the existing methods are either rarely based on container load characteristics or cannot make accurate real-time predictions. In this paper, we propose a Docker container workload proactive prediction method using a hybrid model combining triple exponential smoothing and long short-term memory (LSTM), which not only can capture both short-term and long-term dependencies in container resource time series but also smooth the container resource utilization data. In order to improve the prediction accuracy of the hybrid model, those two single models are combined using the mean absolute percentage error (MAPE) method. Besides, we design a real-time Docker workload prediction system for the hybrid model. Our experiments show that the mean absolute percentage error of the hybrid model is decreased by an average of 3.24%, 12.18%, 13.42%, 43.45%, and 50.69% compared with the LSTM, the triple exponential smoothing, ES-ARIMA, Bayesian Ridge Regression and BiLSTM with an acceptable time and computational cost overhead.

More and more enterprises are beginning to use Docker containers to build cloud platforms. Predicting the resource usage of container workload has been an important and challenging problem to improve the performance of cloud computing platform. The existing prediction models either incur large time overhead or have insufficient accuracy. This article proposes a hybrid model of the ARIMA and triple exponential smoothing. It can accurately predict both linear and nonlinear relationships in the container resource load sequence. To deal with the dynamic Docker container resource load, the weighting values of the two single models in the hybrid model are chosen according to the sum of squares of their predicted errors for a period of time. We also design and implement a real-time prediction system that consists of the collection, storage, prediction of Docker container resource load data and scheduling optimization of CPU and memory resource usage based on predicted values. The experimental results show that the predicting accuracy of the hybrid model improves by 52.64, 20.15, and 203.72 percent on average compared to the ARIMA, the triple exponential smoothing model and ANN+SaDE model respectively with a small time overhead.

Container-based virtualization has gradually become a main solution in today‘s cloud computing environments. Detecting and analyzing anomaly in containers present a major challenge for cloud vendors and users. This paper proposes an online container anomaly detection system by monitoring and analyzing multidimensional resource metrics of the containers based on the optimized isolation forest algorithm. To improve the detection accuracy, it assigns each resource metric a weight and changes the random feature selection in the isolation forest algorithm to the weighted feature selection according to the resource bias of the container. In addition, it can identify abnormal resource metrics and automatically adjust the monitoring period to reduce the monitoring delay and system overhead. Moreover, it can locate the cause of the anomalies via analyzing and exploring the container log. The experimental results demonstrate the performance and efficiency of the system on detecting the typical anomalies in containers in both simulated and real cloud environments.

Online deep learning (ODL) has become an important methodology for modeling time-based performance of computer systems. An open problem is the intelligent selection of features from raw workload traces of computer systems. The best methods are overly sensitive to noisy data, causing frequent feature changes and re-training. Using all available features inflates training time and introduces model artifacts if some features should have been dropped. We present WinnowML, a method for automatically determining the most relevant feature subset for a predictive time-series model. WinnowML combines existing feature ranking algorithms and a history of each feature’s ranking to iteratively rank a feature set to lower prediction error and maximize long term relevance. From this ranked feature set, the most relevant and stable subset is selected to train a model. Experimentally, we show how WinnowML can lower a model’s mean absolute relative error up to 42% on average compared to the closest performing approach. Additionally, we lower the fluctuation in feature ranking and selection up to 65%. We also demonstrate how to combine WinnowML and a model search tool to provide improvements in performance of up to 14.5% when compared to using all the feature available.

While disk encryption is suitable for use in most situations where confidentiality of disks is required, stronger guarantees are required in situations where adversaries may employ coercive tactics to gain access to cryptographic keys. Deniable volumes are one such solution in which the security goal is to prevent an adversary from discovering that there is an encrypted volume. Multiple snapshot attacks, where an adversary is able to gain access to two or more images of a disk, have often been proposed in the deniable storage system literature; however, there have been no concrete attacks proposed or carried out. We present the first multiple snapshot attack, and we find that it is applicable to most, if not all, implemented deniable storage systems. Our attack leverages the pattern of consecutive block changes an adversary would have access to with two snapshots, and demonstrate that with high probability it detects moderately sized and large hidden volumes, while maintaining a low false positive rate.

It is increasingly important and a big challenge to detect intrusion behavior variants in today's world. Previous host-based intrusion detection methods typically explore the sequence of system calls or unix shell commands to detect the intrusion behavior. This article abstracts the detection of intrusion behavior variants as the comparison between different sequences when the sequence order or length transforms. To overcome the impact of sequence transformation on the detection accuracy, we propose P-Gaussian, a provenance-based Gaussian distribution detection scheme which comprises two key design features: (1) it utilizes provenance to describe and identify intrusion behavior variants, and eliminates the impact of sequence order transformation on the detection accuracy. (2) it adopts Gaussian distribution principle to accurately compute the similarity between intrusion behavior and its variant, and eliminates the impact of intrusion behavior sequence length increase on the detection accuracy. To improve the detection performance, P-Gaussian employs a Redis memory database with multiple Redis instances and multiple threads to enable the parallelism of provenance processing in multi-core environments. It also classifies hot and cold provenance to provide high-efficient long-term forensic analysis. Experimental results on widely-used real world applications demonstrate the performance and efficiency of our system.

Byte-addressable, non-volatile memory (NVM) presents an opportunity to rethink the entire system stack. We present Twizzler, an operating system redesign for this near-future. Twizzler removes the kernel from the I/O path, provides programs with memory-style access to persistent data using small (64 bit), object-relative cross-object pointers, and enables simple and efficient long-term sharing of data both between applications and between runs of an application. Twizzler provides a clean-slate programming model for persistent data, realizing the vision of Unix in a world of persistent RAM. We show that Twizzler is simpler, more extensible, and more secure than existing I/O models and implementations by building software for Twizzler and evaluating it on NVM DIMMs. Most persistent pointer operations in Twizzler impose less than 0.5 ns added latency. Twizzler operations are up to faster than Unix , and SQLite queries are up to faster than on PMDK. YCSB workloads ran 1.1– faster on Twizzler than on native and NVM-optimized SQLite backends.

The size and complexity of large storage systems, such as high-performance computing (HPC) systems, inhibit rapid effective restructuring of data layouts to maintain performance as workloads shift. To address this issue, we have developed Geomancy, a tool that models the placement of data within a distributed storage system and reacts to drops in performance. Our approach to optimizing throughput offers benefits for storage systems such as avoiding potential bottlenecks and increasing overall I/O throughput from 11% to 30%.

Provenance is a type of metadata that records the creation and transformation of data objects. It has been applied to a wide variety of areas such as security, search, and experimental documentation. However, provenance usually has a vast amount of data with its rapid growth rate which hinders the effective extraction and application of provenance. This paper proposes an efficient provenance management system via clustering and hybrid storage. Specifically, we propose a Provenance-Based Label Propagation Algorithm which is able to regularize and cluster a large number of irregular provenance. Then, we use separate physical storage mediums, such as SSD and HDD, to store hot and cold data separately, and implement a hot/cold scheduling scheme which can update and schedule data between them automatically. Besides, we implement a feedback mechanism which can locate and compress the rarely used cold data according to the query request. The experimental test shows that the system can significantly improve provenance query performance with a small run-time overhead.

Efficient intrusion detection and analysis of the security landscape in big data environments present challenge for today's users. Intrusion behavior can be described by provenance graphs that record the dependency relationships between intrusion processes and the infected files. Existing intrusion detection methods typically analyze and identify the anomaly either in a single provenance path or the whole provenance graph, neither of which can achieve the benefit on both detection accuracy and detection time. We propose Pagoda, a hybrid approach that takes into account the anomaly degree of both a single provenance path and the whole provenance graph. It can identify intrusion quickly if a serious compromise has been found on one path, and can further improve the detection rate by considering the behavior representation in the whole provenance graph. Pagoda uses a persistent memory database to store provenance and aggregates multiple similar items into one provenance record to maximumly reduce unnecessary I/O during the detection analysis. In addition, it encodes duplicate items in the rule database and filters noise that does not contain intrusion information. The experimental results on a wide variety of real-world applications demonstrate its performance and efficiency.

The need for reliable and cost-effective data storage grows as digital information becomes increasingly ubiquitous. Archival systems must store valuable data for years while adapting to changing user needs, capacity, and performance requirements. Storage devices differ in terms of performance, capacity, reliability, acquisition cost, power consumption, and the rates at which their features change over time. As a result, choosing the best storage technology to use for an archive has become increasingly challenging with the proliferation of new technologies alongside existing ones. We have designed a simulator that models the capacity, performance, acquisition cost, and power cost of an archival system using the characteristics of the drives and media that comprise it. We simulate and compare four storage technologies that exhibit different cost and performance characteristics: tape, optical disc, hard disk, and NAND flash SSD. We evaluate the total cost of ownership for each storage technology within an archival system, and we explore the effect that prospective technological advancements and growth rates over time may have on the relative cost and viability of each storage technology for archival systems. We show that the lifecycle and upgrade cost of drives are significant cost factors for removable media archives. We observe that increasing performance requires adding more drives to an archival system, and the cost of each drive dominates the cost to increase performance. We compare trends in storage technologies to suggest developments that could minimize the long-term total cost of ownership for archival systems. We show that hard disks and flash could become cost-competitive with tape-based archives by adopting new designs to minimize infrastructure and electricity costs.

Increasingly, archival systems are relying on authentication-based techniques that leverage secret-splitting rather than encryption to secure data for long-term storage. Secret-splitting data across multiple independent repositories reduces complexities in key management, eliminates the need for updates due to encryption algorithm deprecation over time, and reduces the risk of insider compromise. While reconstruction of stored data objects is straightforward if a user-maintained index is available, the system must also support disaster recovery incase the index is unavailable. Designing a mechanism for efficient index-free reconstruction, that does not increase the risk of attacker compromise, is a challenge. Reconstruction requires the association of chunks that make up an object, which is the kind of information attackers can use to identify chunks they must steal to illicitly obtain data. We propose two new techniques, the set-subset reconstruction and secret-split secure hash (S3H) reconstruction, which allow chunks of data to be correlated and quickly reconstructed without providing useful information to an attacker. Both techniques operate on the entire collections of secret-split chunks in the archive. While they can efficiently rebuild an entire archive, they are inefficient and impractical for rebuilding single objects, making them useless for attackers that do not have access to all of the data. These techniques can each be tuned to trade-off between reconstruction performance and security, reducing overall runtime from O(NK) (for N objects requiring K recombined chunks each to return the original object) to between O(N) and O(N2). These runtimes are practical for archives containing as many as 107objects for the secret-split secure hash method and 109objects for the set-subset method. Larger archives can run these techniques with manageable runtimes by grouping data into separate smaller collections and running the algorithms on each collection in parallel.

Removing hard drives from a data center may expose sensitive data, such as encryption keys or passwords. To prevent exposure, data centers have security policies in place to physically secure drives in the system, and securely delete data from drives that are removed. Despite advances in security technology and best practices, implementation of these security measures is often done incorrectly. We anticipate that physical security will fail, and fixing the issue after the failure is costly and ineffective.

Parameter tuning is an important task of storage performance optimization. Current practice usually involves numerous tweak-benchmark cycles that are slow and costly. To address this issue, we developed CAPES, a model-less deep reinforcement learning-based unsupervised parameter tuning system driven by a deep neural network (DNN). It is designed to find the optimal values of tunable parameters in computer systems, from a simple client-server system to a large data center, where human tuning can be costly and often cannot achieve optimal performance. CAPES takes periodic measurements of a target computer system's state, and trains a DNN which uses Q-learning to suggest changes to the system's current parameter values. CAPES is minimally intrusive, and can be deployed into a production system to collect training data and suggest tuning actions during the system's daily operation. Evaluation of a prototype on a Lustre file system demonstrates an increase in I/O throughput up to 45% at saturation point.

Magnetic disk capacities have grown over the last decades by a factor of at least ten thousand. While the minicomputer disk drives of the late eighties could only store 600 MB of data [5], 8TB or 10TB disk drives are common today. The same is not true for disk transfer rates: they are just one hundred times higher than those of the late eighties. As a result, copying the entire contents of a disk will take now considerably more time than thirty or forty years ago.

Carrying out even the simplest performance benchmark requires considerable knowledge of statistics and computer systems, and painstakingly following many error-prone steps, which are distinct skill sets yet essential for getting statistically valid results. As a result, many performance measurements in peer-reviewed publications are flawed. Among many problems, they fall short in one or more of the following requirements: accuracy, precision, comparability, repeatability, and control of overhead. This is a serious problem because poor performance measurements misguide system design and optimization. We propose a collection of algorithms and heuristics to automate these steps. They cover the collection, storing, analysis, and comparison of performance measurements. We implement these methods as a readily-usable open source software framework called Pilot, which can help to reduce human error and shorten benchmark time. Evaluation of Pilot on various benchmarks show that it can reduce the cost and complexity of running benchmarks, and can produce better measurement results.

Stored data needs to be protected against device failure and irrecoverable sector read errors, yet doing so at exabyte scale can be challenging given the large number of failures that must be handled. We have developed RESAR (Robust, Efficient, Scalable, Autonomous, Reliable) storage, an approach to storage system redundancy that only uses XOR-based parity and employs a graph to lay out data and parity. The RESAR layout offers greater robustness and higher flexibility for repair at the same overhead as a declustered version of RAID 6. For instance, a RESAR-based layout with 16 data disklets per stripe has about 50 times lower probability of suffering data loss in the presence of a fixed number of failures than a corresponding RAID 6 organization. RESAR uses a layer of virtual storage elements to achieve better manageability, a broader potential for energy savings, as well as easier adoption of heterogeneous storage devices.

In archival systems, storage media are often replaced much earlier than their expected service life in exchange for other benefits of new media, such as higher capacity, bandwidth, and I/O operations per second, or lower costs. In an era of decreasing media density growth rates, retiring media early by considering only short-term benefits while discarding potential long-term cost benefits could have a negative long-term impact on an archival system's economics. To extend an archival system's life, at low cost, while limiting performance degradation, we suggest extending media lifetime past manufacturer recommendations as well as increasing the horizon for planning and provisioning future media purchases. We present a cost-benefit analysis of the impact of prolonged media usage and long-term planning. Through Monte Carlo simulation, we simulate the behavior of an archival system using tapes, hard disk drives (HDDs), solid state devices (SSDs), and Blu-ray discs. We show that leaving older media in the archival system makes economic sense for SSDs without significantly affecting reliability; we show cost improvements of approximately 10% for SSDs for a low annual media density growth rate, such as 5%, which would have been a loss of 35%, for a high annual media density rate, such as 20%. We show that, for SSDs and hard disks, the optimal planning time of an archival system is at least as long as the media service life. Combining prolonged media usage with an extended planning horizon reduced costs by 15% for a system using SSDs.

Shingled magnetic recording (SMR) is a means of increasing the density of hard drives that brings a new set of challenges. Due to the nature of SMR disks, updating in place is not an option. Holes left by invalidated data can only be filled if the entire band is reclaimed, and a poor band compaction algorithm could result in spending a lot of time moving blocks over the lifetime of the device. We propose using write frequency to separate blocks to reduce data movement and develop a band compaction algorithm that implements this heuristic. We demonstrate how our algorithm results in improved data management, resulting in an up to 45% reduction in required data movements when compared to naive approaches to band management.

Raft is a new distributed consensus algorithm that is easier to understand than the older Paxos algorithm. Raft's major drawback is its high energy footprint: as it relies on static quorums for deciding when it can commit updates, it requires five participants to protect against two simultaneous failures. We propose to reduce this footprint by replacing the static quorums that Raft currently uses by quorums that vary according to the number of currently available participants. We present first a modified dynamic-linear voting protocol that disables single-server updates and show that a Raft cluster with four participants managed by this protocol would be almost as available as a conventional Raft cluster with five participants and always tolerate the irrecoverable failure of any single participant without any data loss. In addition, we show a Raft cluster with three participants and a witness managed by an unmodified dynamic-linear voting protocol would be more available than a conventional Raft cluster with five participants and could still tolerate most irrecoverable failures of any single participant while maintaining recoverability.

High-performance parallel storage systems, such as those used by supercomputers and data centers, can suffer from performance degradation when a large number of clients are contending for limited resources, like bandwidth. These contentions lower the efficiency of the system and cause unwanted speed variances. We present the Automatic Storage Contention Alleviation and Reduction system (ASCAR), a storage traffic management system for improving the bandwidth utilization and fairness of resource allocation. ASCAR regulates I/O traffic from the clients using a rule based algorithm that controls the congestion window and rate limit. The rule-based client controllers are fast responding to burst I/O because no runtime coordination between clients or with a central coordinator is needed; they are also autonomous so the system has no scale-out bottleneck. Finding optimal rules can be a challenging task that requires expertise and numerous experiments. ASCAR includes a SHAred-nothing Rule Producer (SHARP) that produces rules in an unsupervised manner by systematically exploring the solution space of possible rule designs and evaluating the target workload under the candidate rule sets. Evaluation shows that our ASCAR prototype can improve the throughput of all tested workloads - some by as much as 35%. ASCAR improves the throughput of a NASA NPB BTIO checkpoint workload by 33.5% and reduces its speed variance by 55.4% at the same time. The optimization time and controller overhead are unrelated to the scale of the system; thus, it has the potential to support future large-scale systems that can have millions of clients and thousands of servers. As a pure client-side solution, ASCAR needs no change to either the hardware or server software.

Maintaining information privacy is challenging when sharing data across a distributed long-term datastore. In such applications, secret splitting the data across independent sites has been shown to be a superior alternative to fixed-key encryption; it improves reliability, reduces the risk of insider threat, and removes the issues surrounding key management. However, the inherent security of such a datastore normally precludes it from being directly searched without reassembling the data; this, however, is neither computationally feasible nor without risk since reassembly introduces a single point of compromise. As a result, the secret-split data must be pre-indexed in some way in order to facilitate searching. Previously, fixed-key encryption has also been used to securely pre-index the data, but in addition to key management issues, it is not well suited for long term applications. To meet these needs, we have developed Percival: a novel system that enables searching a secret-split datastore while maintaining information privacy. We leverage salted hashing, performed within hardware security modules, to access prerecorded queries that have been secret split and stored in a distributed environment; this keeps the bulk of the work on each client, and the data custodians blinded to both the contents of a query as well as its results. Furthermore, Percival does not rely on the datastore's exact implementation. The result is a flexible design that can be applied to both new and existing secret-split datastores. When testing Percival on a corpus of approximately one million files, it was found that the average search operation completed in less than one second.

Shingled Magnetic Recording (SMR) is a means of increasing the density of hard drives that brings a new set of challenges. Due to the nature of SMR disks, updating in place is not an option. Holes left by invalidated data can only be filled if the entire band is reclaimed, and a poor band compaction algorithm could result in spending a lot of time moving blocks over the lifetime of the device. We propose using write frequency to separate blocks to reduce data movement and develop a band compaction algorithm that implements this heuristic. We demonstrate how our algorithm results in improved data management, resulting in an up to 47% reduction in required data movements when compared to naive approaches to band management.

We present a disk array organization that can survive three simultaneous disk failures while only using exclusive-or operations to calculate the parities that generate this failure tolerance. The reliability of storage systems using magnetic disks depends on how prone individual disks are to failure. Unfortunately, disk failure rates are impossible to predict and it is well known that individual batches might be subject to much higher failure rates at some point during their lifetime. It is also known that many disk drive families, but not all, suffer a substantially higher failure rate at the beginning and some at the end of their economic lifespan. Our proposed organization can be built on top of a dense two-failure tolerant layout using only exclusive-or operations and with a ratio of parity to data disks of 2/k. If the disk failure rates are higher than expected, the new organization can be super-imposed on the existing two-failure tolerant organization by introducing (k+1)/2 new parity disks and (k+1)/2 new reliability stripes to yield a three-failure tolerant layout without moving any data or calculating any other parity but the new one. We derive the organization using a graph visualization and a construction by Lawless of factoring a complete graph into paths.

The performance requirements and amount of work of an I/O workload affect the number of storage devices and the run time needed by the workload, and should be included in the calculation of the cost or energy consumption of storage devices. This paper introduces models to calculate the cost and energy consumption of storage devices for running a variety of workloads, categorized by their dominant requirements. Measurements of two latest hard disk and solid-state drive (SSD) are included to illustrate the models in practice. Contrary to common belief, SSD is not the energy efficient choice for many workloads.

Growth in disk capacity continues to outpace advances in read speed and device reliability. This has led to storage systems spending increasing amounts of time in a degraded state while failed disks reconstruct. Users and applications that do not use the data on the failed or degraded drives are negligibly impacted by the failure, increasing the perceived performance of the system. We leverage this observation with PERSES, a statistical data allocation scheme to reduce the performance impact of reconstruction after disk failure. PERSES reduces degradation from the perspective of the user by clustering data on disks such that data with high probability of co-access is placed on the same device as often as possible. Trace-driven simulations show that, by laying out data with PERSES, we can reduce the perceived time lost due to failure over three years by up to 80% compared to arbitrary allocation.

Disk failure rates vary so widely among different makes and models that designing storage solutions for the worst case scenario is a losing proposition. The approach we propose here is to design our storage solutions for the most probable case while incorporating in our design the option of adding extra redundancy when we find out that its disks are less reliable than expected. To illustrate our proposal, we show how to increase the reliability of existing two-dimensional disk arrays with n2data elements and 2n parity elements by adding n additional parity elements that will mirror the contents of half the existing parity elements. Our approach offers the three advantages of being easy to deploy, not affecting the complexity of parity calculations, and providing a five-year reliability of 99.999 percent in the face of catastrophic levels of data loss where the array would lose up to a quarter of its storage capacity in a year.

File names are one of the earliest computing abstractions, a string of characters to uniquely identify a file for the system, and to help users remember the contents when they look for it later. They are also a rich source of semantic metadata about files. However, this metadata is unstructured and opaque to the rest of the system. As a result, metadata in file names is often error-prone, and hard to search for. File names can and should be more meaningful and reliable, while simplifying application design and encouraging users and applications to provide more metadata for search.

Fault-tolerant disk arrays rely on replication or erasure-coding to reconstruct lost data after a disk failure. As disk capacity increases, so does the risk of encountering irrecoverable read errors that would prevent the full recovery of the lost data. We propose a three-dimensional erasure-coding technique that reduces that risk by guaranteeing full recovery in the presence of all triple and nearly all quadruple disk failures. Our solution performs better than existing solutions, such as sets of disk arrays using Reed-Solomon codes against triple failures in each individual array. Given its very high reliability, it is especially suited to the needs of very large data sets that must be preserved over long periods of time.

Proteus is an open-source simulation program that can predict the risk of data loss in many disk array configurations, among which, mirrored disks, all levels of RAID arrays and various two-dimensional RAID arrays. It characterizes each array by five numbers, namely, the size n of the array, the number nf of simultaneous disk failures the array will always tolerate without data loss, and the respective fractions f1, f2and f3of simultaneous failures of nf+ 1, nf+ 2 and nf+ 3 disks that will not result in a data loss. As with any simulation tool, Proteus imposes no restriction on the distributions of failure and repair events. Our measurements have shown a surprisingly good agreement with the results obtained through analytical techniques and no measurable difference between values obtained assuming deterministic repair times and those assuming exponential repair times.

We present a disk array architecture that does not require users to perform any maintenance tasks over the expected lifetime of the array. Preliminary results indicate that the key factor in the feasibility of our design is the failure rate of unused spare disks. As long as these rates remain negligible, zero maintenance disk arrays with at least 77 disks can provide a five-year reliability of five nines (99.999 percent) with a space overhead comparable to that of mirroring. If this is not the case, we would need between 64 and 70 percent extra spare disks to achieve the same five-year reliability, which would result in a higher space overhead.

We present a general method for estimating the risk of data loss in arbitrary two-dimensional RAID arrays where each data disk belongs to exactly two single-parity stripes. We start by representing each array organization by a graph where each parity stripe, and its associated parity disk, is represented by a node and each data disk by an edge. We then use this representation to identify and enumerate minimal sets of disk failures, say, triple failures, quadruple failures and so forth, that will cause a data loss. The overall probabilities that a given number n of disk failures will cause a data loss is then given by the ratio of the total number of fatal disk failures involving n disks over the total number of possible failures of n disks. To illustrate the power of our method, we apply it to two distinct, archival two-dimensional array organizations. The first, "square" organization is a traditional square layout where data disks are formed into a square and the parity stripes are formed by the rows and columns in the square. Hence a square layout organization with n^2 data disks will have 2n parity disks. The second, "complete" organization corresponds to a closer weave, where all parity stripes intersect and each intersection contains a parity disk. This organization with n parity disks will have n(n - 1)/2 data disks. Our results show that previous ad hoc estimates of the reliability of these arrays significantly underestimated their reliability by assuming that either all triple or all quadruple disk failures were fatal. We show that the two two-dimensional array organizations exhibit mean times to data loss and five-year survival rates that are very similar to those of a RAID Level 6 organization of much smaller capacity. Our complete organization is about 4.5 times and the square organization is about 8 times more reliable than a disk array with same storage capacity built from RAID level 6 stripes. We present a general method for estimating the risk of data loss in arbitrary two-dimensional RAID arrays where each data disk belongs to exactly two single-parity stripes. We start by representing each array organization by a graph where each parity stripe, and its associated parity disk, is represented by a node and each data disk by an edge. We then use this representation to identify and enumerate minimal sets of disk failures, say, triple failures, quadruple failures and so forth, that will cause a data loss. The overall probabilities that a given number n of disk failures will cause a data loss is then given by the ratio of the total number of fatal disk failures involving n disks over the total number of possible failures of n disks. To illustrate the power of our method, we apply it to two distinct, archival two-dimensional array organizations. The first, "square" organization is a traditional square layout where data disks are formed into a square and the parity stripes are formed by the rows and columns in the square. Hence a square layout organization with n^2 data disks will have 2n parity disks. The second, "complete" organization corresponds to a closer weave, where all parity stripes intersect and each intersection contains a parity disk. This organization with n parity disks will have n(n - 1)/2 data disks. Our results show that previous ad hoc estimates of the reliability of these arrays significantly underestimated their reliability by assuming that either all triple or all quadruple disk failures were fatal. We show that the two two-dimensional array organizations exhibit mean times to data loss and five-year survival rates that are very similar to those of a RAID Level 6 organization of much smaller capacity. Our complete organization is about 4.5 times and the square organization is about 8 times more reliable than a disk array with same storage capacity built from RAID level 6 stripes.

While file system metadata is well characterized by a variety of workload studies, scientific metadata is much less well understood. We characterize scientific metadata, in order to better understand the implications for index design. Based on our findings, existing solutions for either file system or scientific search will not suffice for indexing a large scientific file system. We describe the problems with existing solutions, and suggest column stores as an alternative approach.

Provenance is the metadata that describes the history of objects. Provenance provides new functionality in a variety of areas, including experimental documentation, debugging, search, and security. As a result, a number of groups have built systems to capture provenance. Most of these systems focus on provenance collection, a few systems focus on building applications that use the provenance, but all of these systems ignore an important aspect: efficient long-term storage of provenance. In this article, we first analyze the provenance collected from multiple workloads and characterize the properties of provenance with respect to long-term storage. We then propose a hybrid scheme that takes advantage of the graph structure of provenance data and the inherent duplication in provenance data. Our evaluation indicates that our hybrid scheme, a combination of Web graph compression (adapted for provenance) and dictionary encoding, provides the best trade-off in terms of compression ratio, compression time, and query performance when compared to other compression schemes.

Efficient provenance storage is an essential step towards the adoption of provenance. In this paper, we analyze the provenance collected from multiple workloads with a view towards efficient storage. Based on our analysis, we characterize the properties of provenance with respect to long term storage. We then propose a hybrid scheme that takes advantage of the graph structure of provenance data and the inherent duplication in provenance data. Our evaluation indicates that our hybrid scheme, a combination of web graph compression (adapted for provenance) and dictionary encoding, provides the best tradeoff in terms of compression ratio, compression time and query performance when compared to other compression schemes.

We present a two-dimensional RAID architecture that is specifically tailored to the needs of archival storage systems. Our proposal starts with a fairly conventional two-dimensional RAID architecture where each disk belongs to exactly one horizontal and one vertical RAID level 4 stripe. Once the array has been populated, we add a superparity device that contains the exclusive OR of all the contents of all horizontal-or vertical-parity disks. The new organization tolerates all triple disk failures and nearly all quadruple and quintuple disk failures. As a result, it provides mean times to data loss (MTTDLs) more than a hundred times better than those of sets of RAID level 6 stripes with equal capacity and similar parity overhead.

Many modern storage systems use deduplication in order to compress data by avoiding storing the same data twice. Deduplication needs to use data stored in the past, but accessing information about all data stored can cause a severe bottleneck. Similarity based deduplication only accesses information on past data that is likely to be similar and thus more likely to yield good deduplication. We present an adaptive deduplication strategy that extends Extreme Binning and investigate theoretically and experimentally the effects of the additional bin accesses.

Shingled Magnetic Recording technology is expected to play a major role in the next generation of hard disk drives. But it introduces some unique challenges to system software researchers and prototype hardware is not readily available for the broader research community. It is crucial to work on system software in parallel to hardware manufacturing, to ensure successful and effective adoption of this technology. In this work, we present a novel Shingled Write Disk (SWD) emulator that uses a hard disk utilizing traditional Perpendicular Magnetic Recording (PMR) and emulates a Shingled Write Disk on top of it. We implemented the emulator as a pseudo block device driver and evaluated the performance overhead incurred by employing the emulator. The emulator has a slight overhead which is only measurable during pure sequential reads and writes. The moment disk head movement comes into picture, due to any random access, the emulator overhead becomes so insignificant as to become immeasurable.

Preserving data for a long period of time in the face of faults, large and small, is crucial for designing reliable archival storage systems. However, the survivability of data is different from the reliability of storage because typically, data are stored in more than one storage at a given moment. Previous studies of reliability ignore the former. We present a framework for relating data survivability and storage reliability, and use the framework to gauge the impact of rare but large-scale events on data survivability. We also present a method to track all copies of data and the condition of all the online and offline media, devices and systems on which they are stored uninterruptedly over the whole lifetime of the data. With this method, the survivability of the data can be closely monitored, and potential dangers can be handled in a timely manner. A better understanding of data survivability can be used in reducing unnecessary data replicas, thus reducing the cost.

No abstract available.

In this paper, we present the design and performance evaluation of Oasis, an active storage framework for object-based storage systems that complies with the current T10 OSD standard. In contrast with previous work, Oasis has the following advantages. First, Oasis enables users to transparently process the OSD object and supports different processing granularity (from the single object to all the objects in the OSD) by extending the OSD object attribute page defined in the T10 OSD standard. Second, Oasis provides an easy and efficient way for users to manage the application functions in the OSD by using the existing OSD commands. Third, Oasis can authorize the execution of the application function in the OSD by enhancing the T10 OSD security protocol, allowing only authorized users to use the system. We evaluate the performance and scalability of our system implementation on Oasis by running three typical applications. The results indicate that active storage far outperforms the traditional object-based storage system in applications that filter data on the OSD. We also experiment with Java based applications and C based applications. Our experiments indicate that Java based applications may be bottlenecked for I/O-intensive applications, while for applications that do not heavily rely on the I/O operations, both Java based applications and C based applications achieve comparable performance. Our microbenchmarks indicate that Oasis implementation overhead is minimal compared to the Intel OSD reference implementation, between 1.2% to 5.9% for Read commands and 0.6% to 9.9% for Write commands.

The ever-increasing volume of archival data that needs to be reliably retained for long periods of time and the decreasing costs of disk storage, memory, and processing have motivated the design of low-cost, high-efficiency disk-based storage systems. However, managed disk storage is still expensive. To further lower the cost, redundancy can be eliminated with the use of interfile and intrafile data compression. However, it is not clear what the optimal strategy for compressing data is, given the diverse collections of data. To create a scalable archival storage system that efficiently stores diverse data, we present PRESIDIO, a framework that selects from different space-reduction efficent storage methods (ESMs) to detect similarity and reduce or eliminate redundancy when storing objects. In addition, the framework uses a virtualized content addressable store (VCAS) that hides from the user the complexity of knowing which space-efficient techniques are used, including chunk-based deduplication or delta compression. Storing and retrieving objects are polymorphic operations independent of their content-based address. A new technique, harmonic super-fingerprinting, is also used for obtaining successively more accurate (but also more costly) measures of similarity to identify the existing objects in a very large data set that are most similar to an incoming new object. The PRESIDIO design, when reported earlier, had comprehensively introduced for the first time the notion of deduplication, which is now being offered as a service in storage systems by major vendors. As an aid to the design of such systems, we evaluate and present various parameters that affect the efficiency of a storage system using empirical data.

We propose Clasas (from the Castilian “Claves seguras” for “secure keys”), a key-store for distributed storage such in the Cloud. The security of Clasas derives from breaking keys into K shares and storing the key shares at many different sites. This provides both a probabilistic and a deterministic guarantee against an adversary trying to obtain keys. The probabilistic guarantee is based on a combinatorial explosion, which forces an adversary to subvert a very large portion of the storage sites for even a minute chance of obtaining a key. The deterministic guarantee stems from the use of LH* distributed linear hashing. Our use of the LH* addressing rules insures that no two key shares (belonging to the same key) are ever, even in transit, stored at the same site. Consequentially, an adversary has to subvert at least K sites. In addition, even an insider with extensive administrative privileges over many of the sites used for key storage is prevented from obtaining access to any key. Our key-store uses LH* or its scalable availability derivate, LH*RS to distribute key shares among a varying number of storage sites in a manner transparent to its users. While an adversary faces very high obstacles in obtaining a key, clients or authorized entities acting on their behalf can access keys with a very small number of messages, even if they do not know all sites where key shares are stored. This allows easy sharing of keys, rekeying, and key revocation.

If the data density of magnetic disks is to continue its current 30-50% annual growth, new recording techniques are required. Among the actively considered options, shingled writing is currently the most attractive one because it is the easiest to implement at the device level. Shingled write recording trades the inconvenience of the inability to update in-place for a much higher data density by a using a different write technique that overlaps the currently written track with the previous track. Random reads are still possible on such devices, but writes must be done largely sequentially. In this paper, we discuss possible changes to disk-based data structures that the adoption of shingled writing will require. We first explore disk structures that are optimized for large sequential writes with little or no sequential writing, even of metadata structures, while providing acceptable read performance. We also examine the usefulness of non-volatile RAM and the benefits of object-based interfaces in the context of shingled disks. Finally, through the analysis of recent device traces, we demonstrate the surprising stability of written device blocks, with general purpose workloads showing that more than 93% of device blocks remain unchanged over a day, and that for more specialized workloads less than 0.5% of a shingled-write disk's capacity would be needed to hold randomly updated blocks.

Index partitioning techniques-where indexes are broken into multiple distinct sub-indexes-are a proven way to improve metadata search speeds and scalability for large file systems, permitting early triage of the file system. A partitioned metadata index can rule out irrelevant files and quickly focus on files that are more likely to match the search criteria. Also, in a large file system that contains many users, a user's search should not include confidential files the user doesn't have permission to view. To meet these two parallel goals, we propose a new partitioning algorithm, Security Aware Partitioning, that integrates security with the partitioning method to enable efficient and secure file system search. In order to evaluate our claim of improved efficiency, we compare the results of Security Aware Partitioning to six other partitioning methods, including implementations of the metadata partitioning algorithms of SmartStore and Spyglass, two recent systems doing partitioned search in similar environments. We propose a general set of criteria for comparing partitioning algorithms, and use them to evaluate the partitioning algorithms. Our results show that Security Aware Partitioning can provide excellent search performance at a low computational cost to build indexes, O(n). Based on metrics such as information gain, we also conclude that expensive clustering algorithms do not offer enough benefit to make them worth the additional cost in time and memory.

Disk scrubbing periodically scans the contents of a disk array to detect the presence of irrecoverable read errors and reconstitute the contents of the lost blocks using the built-in redundancy of the disk array. We address the issue of scheduling scrubbing runs in disk arrays that can tolerate two disk failures without incurring a data loss, and propose to start an urgent scrubbing run of the whole array whenever a disk failure is detected. Used alone or in combination with periodic scrubbing runs, these expedited runs can improve the mean time to data loss of disk arrays over a wide range of disk repair times. As a result, our technique eliminates the need for frequent scrubbing runs and the need to maintain spare disks and personnel on site to replace failed disks within a twenty-four hour interval.

Security functions such as access control, encryption and authentication are typically left up to applications on the modern Internet. There is no unified system to implement these critical features. The access control that does exist on the network doesn't integrate well with user authentication systems, so access control decisions are based on the network location of a computer rather than the privilege level of its user. Just about every layer of the Internet provides optional encryption, yet most data on the Internet continues to be sent in the clear. Application developers routinely make mistakes in security critical code leading to bugs that manifest in worms, malware or provide a doorway for actively malicious attackers. We propose a unified session layer that integrates trustworthiness features into the core of the network. This would reverse the fortunes of security on the Internet and lead us toward a safer, more secure global network.

Data deduplication is an essential and critical component of backup systems. Essential, because it reduces storage space requirements, and critical, because the performance of the entire backup operation depends on its throughput. Traditional backup workloads consist of large data streams with high locality, which existing deduplication techniques require to provide reasonable throughput. We present Extreme Binning, a scalable deduplication technique for non-traditional backup workloads that are made up of individual files with no locality among consecutive files in a given window of time. Due to lack of locality, existing techniques perform poorly on these workloads. Extreme Binning exploits file similarity instead of locality, and makes only one disk access for chunk lookup per file, which gives reasonable throughput. Multi-node backup systems built with Extreme Binning scale gracefully with the amount of input data; more backup nodes can be added to boost throughput. Each file is allocated using a stateless routing algorithm to only one node, allowing for maximum parallelization, and each backup node is autonomous with no dependency across nodes, making data management tasks robust with low overhead.

Two-dimensional RAID arrays maintain separate row and column parities for all their disks. Depending on their organization, they can tolerate between two and three concurrent disk failures without losing any data. We propose to enhance the robustness of these arrays by replacing a small fraction of these drives with storage class memory devices, and demonstrate how such a pairing is several times more reliable than relying on conventional disks alone, or simply augmenting popular redundant layouts. Depending on the ratio of the failure rates of these two devices, the substitution can double or even triple the mean time to data loss (MTTDL) of each array.

Digital archives are growing rapidly, necessitating stronger reliability measures than RAID to avoid data loss from device failure. Mirroring, a popular solution, is too expensive over time. We present a compromise solution that uses multi-level redundancy coding to reduce the probability of data loss from multiple simultaneous device failures. This approach handles small-scale failures of one or two devices efficiently while still allowing the system to survive rare-event, larger-scale failures of four or more devices. In our approach, each disk is split into a set of fixed size disklets which are used to construct reliability stripes. To protect against rare event failures, reliability stripes are grouped into larger super-groups, each of which has a corresponding super-parity; super-parity is only used to recover data when disk failures overwhelm the redundancy in a single reliability stripe. Super-parity can be stored on a variety of devices such as NV-RAM and always-on disks to offset write bottlenecks while still keeping the number of active devices low. Our calculations of failure probabilities show that adding super-parity allows our system to absorb many more disk failures without data loss. Through discrete event simulation, we found that adding super-groups has a significant impact on mean time to data loss and that rebuilds are slow but not unmanageable. Finally, we showed that robustness against rare events can be achieved for a fraction of total system cost.

We investigate the impact of irrecoverable read errors--also known as bad blocks--on the MTTDL of mirrored disks, RAID level 5 arrays and RAID level 6 arrays. Our study is based on the data collected by Bairavasundaram et al. from a population of 1.53 million disks over a period of 32 months. Our study indicates that irrecoverable read errors can reduce the mean time to data loss (MTTDL) of the three arrays by up to 99 percent, effectively canceling most of the benefits of fast disk repairs. It also shows the benefits of frequent scrubbing scans that map out bad blocks thus preventing future irrecoverable read errors. As an example, once-a-month scrubbing scans were found to improve the MTTDL of the three arrays by at least 300 percent compared to once-a-year scrubbing scans.

We propose the use of parity-based redundant data layouts of increasing reliability as a means to progressively harden data archives. We evaluate the reliability of two such layouts and demonstrate how moving to layouts of higher parity degree offers a mechanism to progressively and dramatically increase the reliability of a multi-device data store. Specifically we propose that a data archive can be migrated to progressively more reliable layouts as the data ages, trading limited (and likely unrealized) increases in update costs for increased reliability. Our parity-based schemes are drawn from SSPiRAL (Survivable Storage using Parity in Redundant Array Layouts) that offer capacity efficiency equivalent to a straightforward mirroring arrangement. Our analysis shows our proposed schemes would utilize no additional physical resources and result in improvements to mean time to data loss of four to seven orders of magnitude.

To offset the significant power demands of hard disk drives in computer systems, drives are typically powered down during idle periods. This saves power, but accelerates duty cycle consumption, leading to earlier drive failure. Hybrid disks with a small amount of non-volatile flash memory (NVCache) are coming on the market. We present four I/O subsystem enhancements that exploit the characteristics of hybrid disks to improve system performance: 1) artificial idle periods, 2) a read-miss cache, 3) anticipatory spin-up, and 4) NVCache write-throttling. These enhancements reduce power consumption, duty cycling, NVCache block-erase impact, and the observed spinup latency of a hybrid disk, resulting in lower power consumption, greater reliability, and faster I/O.

We propose increasing the survivability of data stored in two-dimensional RAID arrays by causing these arrays to reorganize themselves whenever they detect a disk failure. This reorganization will rebalance as much as possible the redundancy level of all stored data, thus reducing the potential impact of additional disk failures. It remains in effect until the failed disk gets repaired. We show how our technique can be applied to two-dimensional RAID arrays consisting of n2data disks and 2n parity disks and show how it can increase the mean time to data loss of the array by at least 200 percent as long as the reorganization process takes less than half the time it takes to replace a failed disk.

We present the first analytic study of stream tapping protocols, a family of protocols that provide the most efficient way to distribute videos on demand at low to medium request arrival rates, say, less than ten requests per hour for a two-hour video. The main results of this study are analytical solutions for the optimal operational points of stream tapping, stream tapping with small client buffers, stream tapping with partial preloading and stream tapping with proactive streams. In addition we introduce a new stream tapping protocol with batching that caps the bandwidth requirements of stream tapping at high to very high arrival rates.

Inter-file compression techniques store files as sets of references to data objects or chunks that can be shared among many files. While these techniques can achieve much better compression ratios than conventional intra-file compression methods such as Lempel-Ziv compression, they also reduce the reliability of the storage system because the loss of a few critical chunks can lead to the loss of many files. We show how to eliminate this problem by choosing for each chunk a replication level that is a function of the amount of data that would be lost if that chunk were lost. Experiments using actual archival data show that our technique can achieve significantly higher robustness than a conventional approach combining data mirroring and intra-file compression while requiring about half the storage space.

Being one of the few mechanical components in a typical computer system, hard drives consume a significant amount of the overall power used by a computer. Spinning down a hard drive reduces its power consumption, but only works when no disk accesses occur, limiting overall effectiveness. We have designed and implemented a technique to extend disk spin-down times using a small non-volatile storage cache called NVCache, which contains a combination of caching techniques to service reads and writes while the hard disk is in low-power mode. We show that combining NVCache with an adaptive disk spin-down algorithm, a hard disk’s power consumption can be reduced by up to 90%.

Power conservation in systems is critical for mobile, sensor network, and other power-constrained environments. While disk spin-down policies can contribute greatly to reducing the power consumption of the storage subsystem, the reshaping of the access workload can actively increase such energy savings. Traditionally reshaping of the access workload is a result of caches passively modifying the workload with the aim of increasing hit ratios and reducing access latency. In contrast, we present the a shifting predictive policy that actively reshapes the workload with the primary goal of conserving disk energy consumption. By reshaping the disk workload to explicitly lengthen idle periods, the disk can remain spun-down longer, saving more energy. We show that our approach can save up to 75% of disk energy compared to the common fixed-timeout spin-down policies. Our shifting algorithm dynamically shifts to the most energy efficient cache prefetching policy based on the current workload. This best shifting prefetching policy is shown to use 15% to 35% less energy than traditional disk spin-down strategies and 5% to 10% less energy than the use of a fixed (non-shifting) prefetching policy.

MEMS-based storage is an emerging nonvolatile secondary storage technology. It promises high performance, high storage density, and low power consumption. With fundamentally different architectural designs from magnetic disk, MEMS-based storage exhibits unique two-dimensional positioning behaviors and efficient power state transitions. We model these low-level, device-specific properties of MEMS-based storage and present request scheduling algorithms and power management strategies that exploit the full potential of these devices. Our simulations show that MEMS-specific device management policies can significantly improve system performance and reduce power consumption.

As an emerging nonvolatile secondary storage technology, MEMS-based storage exhibits several desirable properties including high performance, high storage volumic density, low power consumption, low entry cost, and small form factor. However, MEMS-based storage provides a limited amount of storage per device and is likely to be more expensive than magnetic disk. Systems designers will therefore need to make trade-offs to achieve well-balanced designs. We present an architecture in which MEMS devices are organized into MEMS storage enclosures with online spares. Such enclosures are proven to be highly reliable storage building bricks with no maintenance during their economic lifetimes. We also demonstrate the effectiveness of using MEMS as another layer in the storage hierarchy, bridging the cost and performance gap between MEMS storage and disk. We show that using MEMS as a disk cache can significantly improve system performance and cost-performance ratio.

We present the Deep Store archival storage architecture, a large-scale storage system that stores immutable data efficiently and reliably for long periods of time. Archived data is stored across a cluster of nodes and recorded to hard disk. The design differentiates itself from traditional file systems by eliminating redundancy within and across files, distributing content for scalability, associating rich metadata with content, and using variable levels of replication based on the importance or degree of dependency of each piece of stored data. We evaluate the foundations of our design, including PRESIDIO, a virtual content-addressable storage framework with multiple methods for interfile and intra-file compression that effectively addresses the data-dependent variability of data compression. We measure content and metadata storage efficiency, demonstrate the need for a variable-degree replication model, and provide preliminary results for storage performance.

Non-volatile storage technologies such as flash memory, magnetic RAM (MRAM), and MEMS-based storage are emerging as serious alternatives to disk drives. Among these, MEMS storage is predicted to be the least expensive and highest density, and at about 1 ms access times still considerably faster than hard disk drives. Like the other emerging non-volatile storage technologies, it is highly suitable for small mobile devices but it is expensive to replace hard drives entirely. Its non-volatility, dense storage, and high performance still make it an ideal candidate for the secondary storage subsystem. We examine the use of MEMS storage in the storage hierarchy and show that using a technique called MEMS caching disk, we can achieve 30-49% of the pure MEMS storage performance by using only a small amount (3% of the disk capacity) of MEMS storage in conjunction with a standard hard drive. The resulting system is ideally suited for commercial packaging with a small MEMS device included as part of a standard disk controller or paired with a disk.

Recent advances in large-capacity, low-cost storage devices have led to active research in design of large-scale storage systems built from commodity devices for supercomputing applications. Such storage systems, composed of thousands of storage devices, are required to provide high system bandwidth and petabyte-scale data storage. A robust network interconnection is essential to achieve high bandwidth, low latency, and reliable delivery during data transfers. However, failures, such as temporary link outages and node crashes, are inevitable. We discuss the impact of potential failures on network interconnections in very large-scale storage systems and analyze the trade-offs among several storage network topologies by simulations. Our results suggest that a good interconnect topology be essential to fault-tolerance of a petabyte-scale storage system.

Tabbycat is a video server prototype demonstrating the benefits of a proactive approach for distributing popular videos on demand to a large customer base. Rather than reacting to individual customer requests, Tabbycat broadcasts the contents of the most popular videos according to a fixed schedule. As a result, the number of customers watching a given video does not affect the cost of distributing it. We found that one workstation with a single ATA disk drive and a fast Ethernet interface could distribute three two-hour videos while achieving a maximum customer waiting time of less than four minutes.

We describe our experience graphically visualizing data access behavior, with a specific emphasis on visualizing the predictability of such accesses and the consistency of these observations at the block level. Such workloads are more frequently encountered after filtering through intervening cache levels and in this paper we demonstrate how such filtered workloads pose a problem for traditional caching schemes. We demonstrate how prior results are consistent across both file and disk access workloads. We also demonstrate how an aggregating cache based on predictive grouping can overcome such filtering effects. Our visualization tool provides an illustration of how file workloads remain predictable in the presence of intervening caches, explaining how the aggregating cache can remain effective under what would normally be considered adverse conditions. We further demonstrate how the same predictability remains true with physical block workloads.

Most broadcasting protocols for video-on-demand do not allow the customer to pause, move fast-forward or backward while watching a video. We propose a broadcasting protocol implementing these features in a purely proactive fashion. Our protocol implements rewind and pause interactions at the set-top box level by requiring the set-top box to keep in its buffer all video data it has received from the server until the customer has finished watching the video. It implements fast-forward by letting the video server transmit video data more frequently than needed by customers watching the video in sequence. As a result, any customer having watched the first x minutes of a video is able to fast-forward to any scene within the first 2x or 3x minutes of the video. We show that this expanding horizon feature can be provided at a reasonable cost. We also show how our protocol can accommodate customers connected to the service through a device lacking either the ability to receive data at more than two times the video consumption rate or the storage space required to store more than 20 to 25 percent of the video they are watching. While these customers cannot have access to any of the interactive features provided by our protocol, they can watch videos after the same wait time as all other customers.

In-place reconstruction of differenced data allows information on devices with limited storage capacity to be updated efficiently over low-bandwidth channels. Differencing encodes a version of data compactly as a set of changes from a previous version. Transmitting updates to data as a version difference saves both time and bandwidth. In-place reconstruction rebuilds the new version of the data in the storage or memory the current version occupies-no scratch space is needed for a second version. By combining these technologies, we support highly mobile applications on space-constrained hardware. We present an algorithm that modifies a differentially encoded version to be in-place reconstructible. The algorithm trades a small amount of compression to achieve this property. Our treatment includes experimental results that show our implementation to be efficient in space and time and verify that compression losses are small. Also, we give results on the computational complexity of performing this modification while minimizing lost compression.

We describe a way to manage distributed file system caches based upon groups of files that are accessed together. We use file access patterns to automatically construct dynamic groupings of files and then manage our cache by fetching groups, rather than single files. We present experimental results, based on trace-driven workloads, demonstrating that grouping improves cache performance. At the file system client, grouping can reduce LRU demand fetches by 50 to 60%. At the server cache hit rate improvements are much more pronounced, but vary widely (20 to over 1200%) depending upon the capacity of intervening caches. Our treatment includes information theoretic results that justify our approach to file grouping.

The subject of this article is differential compression , the algorithmic task of finding common strings between versions of data and using them to encode one version compactly by describing it as a set of changes from its companion. A main goal of this work is to present new differencing algorithms that (i) operate at a fine granularity (the atomic unit of change), (ii) make no assumptions about the format or alignment of input data, and (iii) in practice use linear time, use constant space, and give good compression. We present new algorithms, which do not always compress optimally but use considerably less time or space than existing algorithms. One new algorithm runs in O ( n ) time and O (1) space in the worst case (where each unit of space contains [log n ] bits), as compared to algorithms that run in O ( n ) time and O ( n ) space or in O ( n 2 ) time and O (1) space. We introduce two new techniques for differential compression and apply these to give additional algorithms that improve compression and time performance. We experimentally explore the properties of our algorithms by running them on actual versioned data. Finally, we present theoretical results that limit the compression power of differencing algorithms that are restricted to making only a single pass over the data.

Magnetic RAM (MRAM) is a new memory technology with access and cost characteristics comparable to those of conventional dynamic RAM (DRAM) and the non-volatility of magnetic media such as disk. Simply replacing DRAM with MRAM will make main memory non-volatile, but it will not improve file system performance. However, effective use of MRAM in a file system has the potential to significantly improve performance over existing file systems. The HeRMES file system will use MRAM to dramatically improve file system performance by using it as a permanent store for both file system data and metadata. In particular, metadata operations, which make up over 50% of all file system requests [14], are nearly free in HeRMES because they do not require any disk accesses. Data requests will also be faster, both because of increased metadata request speed and because using MRAM as a non-volatile cache will allow HeRMES to better optimize data placement on disk. Though MRAM capacity is too small to replace disk entirely, HeRMES will use MRAM to provide high-speed access to relatively small units of data and metadata, leaving most file data stored on disk.

We present opportunistic renewal, a lease management protocol designed to keep distributed file systems or distributed shared memories consistent in the presence of a network partition or other computer failures.Our treatment includes an analytical model of the protocol that compares performance with existing lease protocols and quantifies improvements.In addition, this analytical model provides the structure to understand message overhead and availability trade-offs when selecting lease parameters.We include results demonstrating that opportunistic renewal substantially reduces the network overhead associated with lease renewal.As a corollary, opportunistic renewal can reduce the lease length at any given network overhead; e.g., by a factor of 50 at 1% network overhead.Lower overhead makes leasing less intrusive and shorter lease periods allow a system to recover from failure more quickly.

Most existing distribution protocols for video-on-demand are tailored for a specific range of video access rates and perform poorly beyond that range. We present a dynamic heuristic broadcasting protocol that performs as well as stream tapping with unlimited extra tapping at low video access rates and has the same average bandwidth requirements as the best existing broadcasting protocols at high video access rates. We also show how our protocol can handle compressed video and adapt itself to the individual bandwidth requirements of each video.

Correct prediction of file accesses can improve system performance by mitigating the relative speed difference between CPU and disks. This paper discusses Program-based Last Successor (PLS) and presents Program- and Userbased Last Successor (PULS), file prediction algorithms that utilize information about the program and user that access the files. Our simulation results show that PLS makes 21% fewer incorrect predictions and PULS makes 24% fewer incorrect predictions than last-successor with roughly the same number of correct predictions that lastsuccessor makes. The cache space wasted on incorrect predictions can be reduced accordingly. We also show that a cache using the Least Recently Used (LRU) caching algorithm can perform better when the PULS is applied. In some cases, a cache using LRU and either PLS or PULS performs better than a cache up to 40 times larger using LRU alone.

In a distributed file system built on network attached storage, client computers access data directly from shared storage, rather than submitting I/O requests through a server. Without a server marshaling access to data, if a computer fails or becomes isolated in a network partition while holding locks on cached data objects, those objects become inaccessible to other computers until a locking authority can guarantee that the lock holder will not again directly access these data. We describe a server that acts as the locking authority and implements a lease-based protocol for revoking access to data objects locked by an isolated or failed computer. When a lease expires, the server can be assured that the client no longer acts on locked data, and can safely redistribute locks to other clients. During normal operation, this protocol invokes no message overhead, and uses no memory and performs no computation at the locking authority.

The key performance bottleneck for a video-on-demand (VOD) server is bandwidth, which controls the number of clients the server can simultaneously support. Previous work (Carter & Long, 1997, 1999) has shown that a strategy called "stream tapping" can make efficient use of bandwidth when clients are not allowed to interact (through VCR-like controls) with the video they are viewing. In this paper, we present an interactive version of stream tapping and analyze its performance through the use of discrete-event simulation. In particular, we show that stream tapping can use as little as 10% of the bandwidth required by dedicating a unique stream of data to each client request.

Many computer hardware and software architectures buffer data in memory to improve system performance. Volatile disk or file caches are sometimes used to delay the propagation of writes to disk (called delayed writes). While delayed writes improve system performance, volatile caches can cause the loss of vital data during sudden failure. In this study, we investigate managing non-volatile RAM (NVRAM) caches with different simple strategies to delay writes to disk. We evaluate the performance of NVRAM caches using three measures of merit: the number of stalled writes which wait while the cache is cleaned before being serviced the mean service time far I/O requests, and the number of writes generated by cleaning the cache. Our results show that even small non-volatile write caches using simple management policies can reduce the number of writes to disk by at least 70% and as much as 80% in some cases. Our results also show that the number of stalled writes is high: 30% at best and nearly 100% at worst. Adding pro-active purging effectively decreases both stalled writes and disk write activity.

Most efforts aimed at reducing the costs of video-on-demand services have focussed on reducing the cost of distributing the top ten to twenty videos by broadcasting them in a periodic fashion rather than waiting for individual requests. Unfortunately nearly all existing VoD broadcasting protocols require client set-top boxes (STB) to include enough local storage to store up to 55 percent of each video being viewed. Here we present a novel VoD broadcasting protocol that does not make that demand. Our dual broadcasting protocol can accommodate clients who do not have any storage device in their STB while providing a much lower maximum waiting time to customers whose STB includes a disk drive. We also discuss two possible extensions to this new protocol. One of them is aimed at reducing the bandwidth requirements of the protocol while the other extends the functionality of the VoD service by providing reverse and fast forward controls.

Broadcasting protocols for video-on-demand continuously retransmit videos that are watched simultaneously by many viewers. Nearly all broadcasting protocols assume that the client set-top box has enough storage to store between 48 and 60 minutes of video. We propose to use this storage to anticipate the customer requests and to preload, say, the first 3 minutes of the top 16 to 20 videos. This would provide instantaneous access to these videos and also eliminate the extra bandwidth required to handle compressed video signal.

Broadcasting protocols can improve the efficiency of video on demand services by reducing the bandwidth required to transmit videos that are simultaneously watched by many viewers. We present a polyharmonic broadcasting protocol that requires less bandwidth than the best extant protocols to achieve the same low maximum waiting time. We also show how to modify the protocol to accommodate very long videos without increasing the buffering capacity of the set-top box.

Broadcasting protocols can improve the efficiency of video on demand services by reducing the bandwidth required to transmit videos that are simultaneously watched by many viewers. We present two broadcasting protocols that achieve nearly the same low bandwidth as the best extant broadcasting protocol while guaranteeing a lower maximum access time. Our first protocol, cautious harmonic broadcasting, requires somewhat more bandwidth than our second protocol, quasi-harmonic broadcasting, but is also much simpler to implement.

Abstract results in high latency and low bandwidth to web-enabled clients and prevents the timely delivery of software. We present an algorithm for modifying delta compressed Differential or delta compression [5, 11, compactly enfiles so that the compressed versions may be reconstructed without scratch space. This allows network clients with limited resources to efficiently update software by retrieving delta compressed versions over a network. Delta compression for binary files, compactly encoding a version of data with only the changed bytes from a previous version, may be used to efficiently distribute software over low bandwidth channels, such as the Internet. Traditional methods for rebuilding these delta files require memory or storage space on the target machine for both the old and new version of the file to be reconstructed. With the advent of

Managing scientific data is a challenging task, and many of the problems it presents have yet to be adequately solved. The Real-time Environmental Information Network and Analysis System (REINAS) is an operational solution to the problem of collecting and distributing environmental data in a real-time context, as well as supporting data acquisition, retrieval, visualization and long-term data maintenance. The system is built around one or more databases and has been developed to support both real-time and retrospective regional scale environmental science. Continuous real-time data is acquired from dispersed sensors and input to a logically integrated but physically distributed system. The database engine provides a powerful structure to handle data management, but current database technology can have difficulty meeting the performance requirements that a large real-time environmental system demands. The REINAS architecture and current status is described in detail, including the challenges that were addressed in the construction of an operational system which includes a regional wireless instrumentation network comprised of over 200 instrument platforms and 1500 sensor streams producing real-time data of interest to thousands of users.

Efficiency is essential for video-on-demand (VOD) to be successful. Conventional VOD servers are inefficient, they dedicate a disk stream for each client, quickly using up all available streams. However, several systems have been proposed that allow clients to share streams. We present a new system called stream tapping that allows a client to greedily "tap" data from any stream on the VOD server containing video data the client can use. This is accomplished through the use of a small buffer on the client set-top box and requires less than 20% of the disk bandwidth used by conventional systems for popular videos. We present a description and analysis of the stream tapping system as well as comparisons between it and other efficiency-improving systems.

We address the problem of deciding when to spin down the disk of a mobile computer in order to extend battery life. Since one of the most critical resources in mobile computing environments is battery life, good energy conservation methods can dramatically increase the utility of mobile systems. We use a simple and efficient algorithm based on machine learning techniques that has excellent performance in practice. Our experimental results are based on traces collected from HP C2474s disks. Using this data, the algorithm outperforms several algorithms that are theoretically optimal in under various worst-case assumptions, as well as the best fixed time-out strategy. In particular, the algorithm reduces the power consumption of the disk to about half (depending on the disk's properties) of the energy consumed by a one minute fixed time-out. Since the algorithm adapts to usage patterns, it uses as little as 88% of the energy consumed by the best fixed time-out computed in retrospect. 1 In...

An accurate estimate of host reliability is important for correct analysis of many fault-tolerance and replication mechanisms. In a previous study, we estimated host system reliability by querying a large number of hosts to find how long they had been functioning, estimating the mean time-to-failure (MTTF) and availability from those measures, and in turn deriving an estimate of the mean time-to-repair (MTTR). However, this approach had a bias towards more reliable hosts that could result in overestimating MTTR and underestimating availability. To address this bias we have conducted a second experiment using a fault-tolerant replicated monitoring tool. This tool directly measures TTF, TTR, and availability by polling many sites frequently from several locations. We find that these more accurate results generally confirm and improve our earlier estimates, particularly for TTR. We also find that failure and repair are unlikely to follow Poisson processes.

A network subsystem supporting a continuous media file system must guarantee a minimum throughput, a maximum delay, and a maximum jitter. The authors present a transport protocol that provides these guarantees. To support different types of service, the protocol is built from modules selected to meet the requirements of each communication session. A buffering technique is used to provide jitter guarantees. To provide throughput and delay guarantees, network performance is optimized based on the required transfer rate. The effects of controlling transmission rate and packet size are presented. The resulting transport protocol is modeled on a simulated FDDI (fiber distributed data interface) network and the results are analyzed. It is shown that the protocol provides the required guarantees for the anticipated types of traffic.>

A family of communication protocols, called quorum multicasts, is presented that provides efficient communication services for widely replicated data. Quorum multicasts are similar to ordinary multicasts, which deliver a message to a set of destinations. The protocols extend this model by allowing delivery to a subset of the destinations, selected according to distance or expected data currency. These protocols provide well-defined failure semantics, and can distinguish between communication failure and replica failure with high probability. The authors have evaluated their performance, taking measurements of communication latency and failure in the Internet. A simulation study of quorum multicasts showed that they provide low latency and require few messages. A second study that measured a test application running at several sites confirmed these results.>

Voting protocols ensure the consistency of replicated objects by requiring all read and write requests to collect an appropriate quorum of replicas. It is proposed to replace some of these replicas with volatile witnesses that have no data and require no stable storage, and to regenerate them instead of waiting for recovery. The small size of volatile witnesses allows them to be regenerated much easier than full replicas. Regeneration attempts are also much more likely to succeed since volatile witnesses can be stored on diskless sites. It is shown that under standard Markovian assumptions two full replicas and one regenerable volatile witness managed by a two-tier dynamic voting protocol provide a higher data availability than three full replicas managed by majority consensus voting or optimistic dynamic voting provided site failures can be detected significantly faster than they can be repaired.>

Failure and repair rates of components are often assumed to be exponentially distributed. This hypothesis is testable for failure rates, though the process of gathering and reducing the data to a usable form can be difficult. By applying an appropriate test statistic, some samples were found to have a realistic change of being drawn from an exponential distribution, while others can be confidently classed as nonexponential. Data were collected from a large number of hosts via the Internet. Almost all of the visible Internet (over 350000 hosts) were considered, and more than 68000 of these that were judged likely to respond were queried. These hosts were sampled several times to obtain up-times, and finally to determine average host availability. Estimates of availability, mean-time-to-failure, and mean-time-to-repair were derived. The results reported correspond with those commonly seen in practice.>

Several strategies for replica maintenance are considered, and the benefits of each are analyzed. Formulas describing the reliability of the replicated data object are presented, and closed-form solutions are given for the tractable cases. Numerical solutions, validated by simulation results, are used to analyze the tradeoffs between reliability and storage cost. With estimates of the mean times to site failure and repair in a given system, the numerical techniques presented can be applied to predict the fewest number of replicas required to provide the desired level of reliability.>

The read and write availabilities of replicated data managed by the regeneration algorithm, a replica control protocol based on file regeneration, are evaluated, and two regeneration protocols are presented that overcome some of its limitations. The first protocol combines regeneration and the available copy approach to improve availability of replicated data. The second combines regeneration and the dynamic voting approach to guarantee data consistency in the presence of network partitions while maintaining a high availability. Expressions for the availabilities of replicated data managed by both protocols are derived and found to improve significantly on the availability achieved using extant consistency protocols.>

The accessibility of vital information can be enhanced by replicating the data on several sites and employing a consistency control protocol to manage the replicas. The reliability of a replicated data object depends on maintaining a viable set of current replicas. When storage is limited, it may not be feasible to simply replicate a data object at enough sites to achieve the desired level of reliability. Regeneration approximates the reliability provided by additional replicas for a modest increase in storage costs, and is applicable whenever a new replica of a data object can be created faster than a system failure can be repaired. Regeneration enhances reliability by creating new replicas on other sites in response to site failures. Several strategies for replica maintenance are considered, and the benefits of each are analyzed using simulation and both algebraic and numeric solutions to systems of differential equations.>

Two novel dynamic voting algorithms are proposed. One, called optimistic dynamic voting, operates on possibly out-of-date information, which greatly increases the efficiency of the algorithm and simplifies its implementation. The other, called topological dynamic voting, explicitly takes into account the topology of the network on which the copies reside to increase the availability of the replicated data. The authors compare availabilities of replicated data managed by both algorithms with those of data managed by existing voting protocols using a simulation model with realistic parameters. Optimistic dynamic voting is found to perform as well as the best existing voting algorithms while topological dynamic voting performs much better than all other voting algorithms when two or more copies reside in the same nonpartitionable group.>

When data are replicated an access protocol must be chosen to ensure the presentation of a consistent view of the data. Protocols based on quorum consensus provide good availability with the added benefit of mutual exclusion. Of the protocols based on quorum consensus, the dynamic voting protocols provide the highest known availability. A dynamic voting protocol that does not need the instantaneous state information required by the original dynamic voting proposal is described. It provides the same performance as the original dynamic voting in the asymptotic case and quickly converges to it for realistic access rates, at a cost in network traffic similar so that of static majority consensus voting. The availability afforded by dynamic voting protocols is analyzed, taking the access frequency into account. The analysis confirms the hypothesis that delaying state information does not appreciably affect availability. Discrete event simulation is used to confirm and to extend the analytical results.>