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:
- 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%.
- 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.
- 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
gitorrsync.
Summary updated