Exploring heterogeneity of unreliable machines for P2P backup

Piotr Skowron, Krzysztof Rzadca

TL;DR

This paper demonstrates that reliable enterprise backup doesn't require expensive dedicated servers; instead, it can be built using the "wasted" disk space of existing, highly unreliable workstations. By moving away from rigid Distributed Hash Tables (DHTs) toward a flexible system of "pairwise replication contracts," the authors successfully built a prototype that provides efficient data protection even on networks where machines are only available 13% of the time.

What Problem Does This Paper Address?

Enterprise backup is a multi-billion dollar headache. Traditional solutions rely on expensive dedicated hardware (like DataDomain) or cloud providers (like Amazon or Dropbox), which can cost upwards of $1,000/TB annually. Meanwhile, most organizations have hundreds of workstations with massive amounts of unused disk space.

The challenge is that these workstations are "unreliable." Employees turn them off at night, reboot them for updates, or they simply crash. Standard peer-to-peer (P2P) storage systems often use Distributed Hash Tables (DHTs) to decide where data goes, but DHTs are rigid—they don't easily account for the fact that one machine might be much faster, more stable, or geographically further away than another. The authors set out to bridge the gap between theoretical P2P models and a practical, optimized backup system that thrives on heterogeneous, unreliable hardware.

Methods

The authors introduce NebuloStore, a prototype backup system with a "mixed architecture":

  • Control Layer: Uses a standard DHT just to store peer "descriptors" (IP addresses and public keys) so nodes can find each other.
  • Storage Layer: Abandons the DHT in favor of pairwise replication contracts. A contract is a bilateral agreement where Peer A agrees to store a chunk of Peer B’s data for a set time.
  • Utility-Based Placement: Instead of random placement, the system uses a utility function to score potential replicators. This function balances three goals:
  • Performance: Minimizing backup/restore time.
  • Resiliency: Ensuring a target number of replicas.
  • Geographic Dispersion: Keeping most replicas "near" for speed, but at least one "far" (measured by network TTL) to protect against local disasters like fires or floods.
  • Hill-Climbing Optimization: Peers periodically "gossip" about low-utility data chunks. If a peer finds a better storage partner than its current one, it renegotiates the contract to improve the system's overall health.
  • Asynchronous Messaging: To handle peers that are frequently offline, the system uses "synchro-peers"—small groups of nodes that cache control messages (like "I've updated this file") for their offline neighbors.

Datasets

The system was evaluated in two distinct environments to capture different types of heterogeneity:

  1. University Computer Labs: 150 workstations with real-world usage patterns. This was a "worst-case" scenario: machines were frequently rebooted or turned off at night, resulting in a median availability of just 13%.
  2. PlanetLab: 50 nodes scattered across Europe. These were highly stable (91% availability) but geographically distant, allowing the authors to test the system's ability to optimize for network latency and geographic spread.
  3. Student Data Traces: The authors used real data-size distributions from their faculty's students to simulate realistic backup loads.

Key Insights and Ideas

  • The "Cost of Unavailability": The most striking finding is how much peer downtime slows things down. In the stable PlanetLab environment, a backup took ~1.1 hours. In the 13%-available lab environment, that same backup took ~3.1 hours. This isn't just due to transfer speeds, but the "waiting time" for both the owner and the replicator to be online simultaneously.
  • Contracts > DHTs for Backup: Because backup isn't a "real-time" file system (like Farsite), you don't need the instant lookups of a DHT. Using contracts allows the system to be much more "opinionated" about where data lives, favoring stable or geographically diverse nodes.
  • Synchro-Peers are Essential: The authors found that without a caching mechanism for messages, more than half of the system's control messages would be lost due to churn. Using a small group of just 5 synchro-peers boosted message delivery success to 90%.
  • Linear Scalability: The total bandwidth of the system scales linearly with the number of machines, effectively removing the bottleneck of a single central backup server.

Key Results

  • Reliability on Junk Hardware: The system successfully maintained data redundancy even when the underlying machines were offline 87% of the time.
  • Optimized Placement: In PlanetLab tests, the system successfully moved "far" replicas to nodes with specific TTL ranges (averaging a distance of 8.1 hops) while keeping "near" replicas close, proving the utility function works.
  • Linear Load Balancing: The system automatically distributed the storage load proportionally to each machine's availability—more stable machines took on more replicas, while flaky machines were used less.
  • Throughput: On PlanetLab, the system achieved an estimated throughput of 4.49 Mb/s, which is competitive for background backup processes.

Limitations and Future Work

  • Deduplication: While the authors mention deduplication is possible in P2P systems, this prototype does not implement it. In a real enterprise setting, deduplication is critical for saving space.
  • Trust and Incentives: The current model assumes a single organization where everyone is "friendly." If expanded to a public P2P network, the system would need stronger mechanisms to prevent malicious peers from deleting data or lying about their storage capacity.
  • Global Optimality: The hill-climbing approach finds "local" improvements. While effective, it doesn't guarantee the mathematically perfect distribution of data across the entire network.
  • Version Control: The prototype only stores the latest version of a file. Future iterations would need to handle incremental backups and version history, similar to tools like git or rsync.

Summary updated

Abstract

P2P architecture is a viable option for enterprise backup. In contrast to dedicated backup servers, nowadays a standard solution, making backups directly on organization's workstations should be cheaper (as existing hardware is used), more efficient (as there is no single bottleneck server) and more reliable (as the machines are geographically dispersed). We present the architecture of a p2p backup system that uses pairwise replication contracts between a data owner and a replicator. In contrast to standard p2p storage systems using directly a DHT, the contracts allow our system to optimize replicas' placement depending on a specific optimization strategy, and so to take advantage of the heterogeneity of the machines and the network. Such optimization is particularly appealing in the context of backup: replicas can be geographically dispersed, the load sent over the network can be minimized, or the optimization goal can be to minimize the backup/restore time. However, managing the contracts, keeping them consistent and adjusting them in response to dynamically changing environment is challenging. We built a scientific prototype and ran the experiments on 150 workstations in the university's computer laboratories and, separately, on 50 PlanetLab nodes. We found out that the main factor affecting the quality of the system is the availability of the machines. Yet, our main conclusion is that it is possible to build an efficient and reliable backup system on highly unreliable machines (our computers had just 13% average availability).
BibTeX
@inproceedings{skowron2013exploring,
  author = {Piotr Skowron and Krzysztof Rzadca},
  title = {{Exploring heterogeneity of unreliable machines for P2P backup}},
  booktitle = {HPCS},
  year = {2013},
  url = {https://openreview.net/forum?id=I0ympd5V2d},
}

Loading related content...

Figure