Distributed storage systems use erasure codes to reliably store data with a small storage overhead. To further improve system performance, some novel erasure codes introduce new features such as the regenerating property or symbol locality, enabling these codes to have optimal repair times and optimal degraded read performance. Unfortunately, the introduction of these new features often exacerbates the performance of other system metrics such as encoding throughput, data reliability, and storage overhead, among others. In this paper we describe the intricate relationships between erasure code properties and system-level performance metrics, showing the different tradeoffs distributed storage designers need to face. We also present Spider Codes, a new erasure code achieving a practical trade-off between the different system-level performance metrics.

Erasure codes are an integral part of many distributed storage systems aimed at Big Data, since they provide high fault-tolerance for low overheads. However, traditional erasure codes are inefficient on replenishing lost data (vital for long term resilience) and on reading stored data in degraded environments (when nodes might be unavailable). Consequently, novel codes optimized to cope with distributed storage system nuances are vigorously being researched. In this paper, we take an engineering alternative, exploring the use of simple and mature techniques - juxtaposing a standard erasure code with RAID-4 like parity to realize cross object redundancy (CORE), and integrate it with HDFS. We benchmark the implementation in a proprietary cluster and in EC2. Our experiments show that for an extra 20% storage overhead (compared to traditional erasure codes) CORE yields up to 58% saving in bandwidth and is up to 76% faster while recovering a single failed node. The gains are respectively 16% and 64% for double node failures.

To achieve reliability in distributed storage systems, data has usually been replicated across different nodes. However the increasing volume of data to be stored has motivated the introduction of erasure codes, a storage efficient alternative to replication, particularly suited for archival in data centers, where old datasets (rarely accessed) can be erasure encoded, while replicas are maintained only for the latest data. Many recent works consider the design of new storage-centric erasure codes for improved repairability. In contrast, this paper addresses the migration from replication to encoding: traditionally erasure coding is an atomic operation in that a single node with the whole object encodes and uploads all the encoded pieces. Although large datasets can be concurrently archived by distributing individual object encodings among different nodes, the network and computing capacity of individual nodes constrain the archival process due to such atomicity. We propose a new pipelined coding strategy that distributes the network and computing load of single-object encodings among different nodes, which also speeds up multiple object archival. We further present RapidRAID codes, an explicit family of pipelined erasure codes which provides fast archival without compromising either data reliability or storage overheads. Finally, we provide a real implementation of RapidRAID codes and benchmark its performance using both a cluster of 50 nodes and a set of Amazon EC2 instances. Experiments show that RapidRAID codes reduce a single object's coding time by up to 90%, while when multiple objects are encoded concurrently, the reduction is up to 20%.

Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives.

In P2P storage systems peers need to contribute some local storage resources in order to obtain a certain online and reliable storage capacity. To guarantee that the storage service works, P2P storage systems have to meet two main requirements. First, the storage system needs to maintain fairness among peers by ensuring that peers consuming more online storage capacity contribute more local storage resources. And second, to reduce redundancy costs and improve reliability, the storage system must incentivize low-available peers to improve their online availability. Traditionally, P2P storage systems achieved these two requirements by (i) using symmetric reciprocal exchanges between peers, and by (ii) allowing peers to selfishly select their set of storage partners. However, in this paper we show that these two mechanisms are suboptimal in terms of the overall storage resources contributed by all peers. To minimize this amount of contributed resources, we design a novel incentive mechanism based on asymmetric reciprocal exchanges between peers. Our mechanism incentivizes peers to select storage partners uniformly at random, and to establish asymmetric exchange relationships with them. These asymmetric exchange relationships allow low-available peers to compensate the increase of redundancy of high-available peers by giving them more storage capacity. We show that our solution reduces the overall amount of contributed resources as well as the resources contributed by each peer individually. Using real P2P availability traces, we show that our incentive mechanism can reduce the overall savings up to 60%, and individual savings from 2% up to 75%, depending on peers' availabilities.

Peer-to-peer (P2P) storage systems are strongly affected by churn - temporal and permanent peer failures. Because of this churn, the main requirement of such systems is to guarantee that stored objects can always be retrieved. This requirement is specially needed in two main situations: when users want to access the stored objects or when data maintenance processes have to repair lost information. To meet this requirement, exiting P2P storage systems introduce large amounts of redundancy that maintain data availability close to 100%. Unfortunately, these large amounts of redundancy increase the storage costs, either by reducing the overall net capacity or by increasing the communication required for data maintenance. In order to minimize storage costs, P2P storage systems can reduce data redundancy. However, less redundancy means lower data availability, which leads to increase object retrieval times. Unfortunately, longer retrieval times could compromise data maintenance processes and could penalize user's retrieval times. It is crucial then for P2P storage systems to predict the effects of a redundancy reduction. In order to provide this information, we present a novel analytical framework to measure object retrieval times under different redundancy and churn circumstances. Our framework can be directly used by backup applications aiming to maintain durability at the lower cost, or by data sharing applications that seek to reduce costs by penalizing user retrieval times. We validate our framework by simulation using real P2P traces (Skype and eMule's KAD).

Peer-to-peer (P2P) storage systems rely on data redundancy to obtain high levels of data availability. Among the existing data redundancy schemes, erasure coding is a widely adopted scheme in existing P2P storage systems. By properly tunning its parameters, erasure codes can minimize the required data redundancy, which reduces both the storage and the network overheads. However, to perform this optimization, storage systems need to measured the obtained data availability. Existing P2P storage systems assume homogeneous node availabilities in order to simplify this measurement. As we will prove, this assumption entails efficiency losses when real node availabilities are highly heterogeneous. In this work, we analyze how erasure codes can be optimized in an availability-aware fashion. We propose an analytical framework able to measure data availability more precisely than existing works. As a result, we can optimize the erasure code deployment while reducing its associated overheads. Our experiments show how by considering real node availabilities it is possible to reduce data redundancy about 50% and up to 80% in some specific scenarios.