Traditionally, there are two main forms of data replication to secondary locations: continuous and snapshot-based. Continuous replication mirrors every I/O to a remote server, which maintains the most up-to-date state, though at a large network bandwidth cost. Snapshot replication periodically transfers modified regions, so it has lower network bandwidth requirements since repeatedly overwritten regions are only transferred once. Snapshot replication, though, comes with larger I/O loads on primary storage since it must read modified regions to transfer. To achieve the benefits of both approaches, we present hybrid replication, which is a novel mix of continuous replication and snapshot-based replication. Hybrid replication selects data regions with high overwrite characteristics to be protected by snapshots, while data regions with fewer overwrites are protected by continuous replication. In experiments with real-world storage traces, hybrid replication reduces network bandwidth up to 40% relative to continuous replication and I/O requirements on primary storage up to 90% relative to snapshot replication.

Synchronous replication is critical for today's enterprise IT organization. It is mandatory by regulation in several countries for some types of organizations, including banks and insurance companies. The technology has been available for a long period of time, but due to speed of light and maximal latency limitations, it is usually limited to a distance of 50-100 miles. Flight data recorders, also known as black boxes, have long been used to record the last actions which happened in airplanes at times of disasters. We present an integration between an Enterprise Data Recorder and an asynchronous replication mechanism, which allows breaking the functional limits that light speed imposes on synchronous replication.

In this paper we consider the management of a tiered storage system consisting of disk and flash drive storage and a DRAM cache, with the challenge of taking into account heterogeneous quality of service (QoS) requirements. We integrate and adjust methods which control the use of fast resources such as flash drives and cache, according to the user access patterns of different data extents and the QoS requirements of the extents, which we developed in previous work. Using traces from real production systems, we show that the benefits of the integrated system are substantially larger than that provided by each method alone. Our method is able to substantially improve the performance of data with high QoS demands, with little or no damage to data with low QoS demands. Thus we are able to exploit the resources of the storage system to the advantage of all data types. we show improvements in the range of 9%-71% for datasets with the highest QoS requirements, and 0%-70% response time improvement overall, compared to a QoS optimized system which took only disk drive resource allocation into consideration. In workloads where cache is useful we obtain large gains, showing that it is important to integrate back-end (drives) and front-end (cache) optimization.

Continuous Data Protection or CDP is a method for capturing all changes occurring to a storage device, allowing fine granularity restore of objects from crash consistent images. In this paper we introduce a method for creating a virtual image of a block storage device, using a CDP journal log and an image of the device at one point in time. The creation of the disk image for any point in time is created on demand. The creation algorithm is very efficient and takes only a few minutes for multiple TeraBytes of changes. The algorithm for creating the image can be formalized as a map/reduce algorithm and can be parallelized easily over multiple machines to reduce the creation time. The creation on demand of the virtual image using journaling methods, minimizes the effect on the production volumes, allowing the use of CDPs for enterprise class applications.

Online, remote, data replication is critical for today’s enterprise IT organization. Availability of data is key to the success of the organization. A few hours of downtime can cost from thousands to millions of dollars With increasing frequency, companies are instituting disaster recovery plans to ensure appropriate data availability in the event of a catastrophic failure or disaster that destroys a site (e.g. flood, fire, or earthquake).

In the minimum fill-in problem, one wishes to find a set of edges of smallest size, whose addition to a given graph will make it chordal. The problem has important applications in numerical algebra and has been studied intensively since the 1970s. We give the first polynomial approximation algorithm for the problem. Our algorithm constructs a triangulation whose size is at most eight times the optimum size squared. The algorithm builds on the recent parameterized algorithm of Kaplan, Shamir, and Tarjan for the same problem. For bounded degree graphs we give a polynomial approximation algorithm with a polylogarithmic approximation ratio. We also improve the parameterized algorithm.

Abstract. In the minimum fill-in problem, one wishes to find a set of edges of smallest size, whose addition to a given graph will make it chordal. The problem has important applications in numerical algebra and has been studied intensively since the 1970s. We give the first polynomial approximation algorithm for the problem. Our algorithm constructs a triangulation whose size is at most eight times the optimum size squared. The algorithm builds on the recent parameterized algorithm of Kaplan, Shamir, and Tarjan for the same problem. For bounded degree graphs we give a polynomial approximation algorithm with a polylogarithmic approximation ratio. We also improve the parameterized algorithm.