Team for Research in
Ubiquitous Secure Technology

Citation
Byung-Gon Chun, Frank Dabek, Andreas Haeberlen, Emil Sit, Hakim Weatherspoon, M.Frans Kaashoek, John Kubiatowicz. ".Efficient Replica Maintenance for Distributed Storage Systems". 3rd USENIX Symposium on Networked Systems Design and Implementation, May, 2006.

Abstract
This paper considers replication strategies for storage systems that aggregate the disks of many nodes spread over the Internet. Maintaining replication in such systems can be prohibitively expensive, since every transient network or host failure could potentially lead to copying a server’s worth of data over the Internet to maintain replication levels. The following insights in designing an efficient replication algorithm emerge from the paper’s analysis. First, durability can be provided separately from availability; the former is less expensive to ensure and a more useful goal for many wide-area applications. Second, the focus of a durability algorithm must be to create new copies of data objects faster than permanent disk failures destroy the objects; careful choice of policies for what nodes should hold what data can decrease repair time. Third, increasing the number of replicas of each data object does not help a system tolerate a higher disk failure probability, but does help tolerate bursts of failures. Finally, ensuring that the system makes use of replicas that recover after temporary failure is critical to efficiency. Based on these insights, the paper proposes the Carbonite replication algorithm for keeping data durable at a low cost. A simulation of Carbonite storing 1 TB of data over a 365 day trace of PlanetLab activity shows that Carbonite is able to keep all data durable and uses 44% more network traffic than a hypothetical system that only responds to permanent failures. In comparison, Total Recall and DHash require almost a factor of two more network traffic than this hypothetical system.

Electronic downloads

• http://oceanstore.cs.berkeley.edu/publications/papers/pdf/carbonite06.pdf

• HTML

  Byung-Gon Chun, Frank Dabek, Andreas Haeberlen, Emil Sit,
  Hakim Weatherspoon, M.Frans Kaashoek, John Kubiatowicz.
  <a href="http://www.truststc.org/pubs/622.html"
  >.Efficient Replica Maintenance for Distributed Storage
  Systems</a>, 3rd USENIX Symposium on Networked Systems
  Design and Implementation, May, 2006.

• Plain text

  Byung-Gon Chun, Frank Dabek, Andreas Haeberlen, Emil Sit,
  Hakim Weatherspoon, M.Frans Kaashoek, John Kubiatowicz.
  ".Efficient Replica Maintenance for Distributed Storage
  Systems". 3rd USENIX Symposium on Networked Systems
  Design and Implementation, May, 2006.

• BibTeX

  @inproceedings{ChunDabekHaeberlenSitWeatherspoonKaashoekKubiatowicz06_EfficientReplicaMaintenanceForDistributedStorageSystems,
      author = {Byung-Gon Chun and Frank Dabek and Andreas
                Haeberlen and Emil Sit and Hakim Weatherspoon and
                M.Frans Kaashoek and John Kubiatowicz},
      title = {.Efficient Replica Maintenance for Distributed
                Storage Systems},
      booktitle = {3rd USENIX Symposium on Networked Systems Design
                and Implementation},
      month = {May},
      year = {2006},
      abstract = {This paper considers replication strategies for
                storage systems that aggregate the disks of many
                nodes spread over the Internet. Maintaining
                replication in such systems can be prohibitively
                expensive, since every transient network or host
                failure could potentially lead to copying a
                server’s worth of data over the Internet to
                maintain replication levels. The following
                insights in designing an efficient replication
                algorithm emerge from the paper’s analysis.
                First, durability can be provided separately from
                availability; the former is less expensive to
                ensure and a more useful goal for many wide-area
                applications. Second, the focus of a durability
                algorithm must be to create new copies of data
                objects faster than permanent disk failures
                destroy the objects; careful choice of policies
                for what nodes should hold what data can decrease
                repair time. Third, increasing the number of
                replicas of each data object does not help a
                system tolerate a higher disk failure probability,
                but does help tolerate bursts of failures.
                Finally, ensuring that the system makes use of
                replicas that recover after temporary failure is
                critical to efficiency. Based on these insights,
                the paper proposes the Carbonite replication
                algorithm for keeping data durable at a low cost.
                A simulation of Carbonite storing 1 TB of data
                over a 365 day trace of PlanetLab activity shows
                that Carbonite is able to keep all data durable
                and uses 44% more network traffic than a
                hypothetical system that only responds to
                permanent failures. In comparison, Total Recall
                and DHash require almost a factor of two more
                network traffic than this hypothetical system.},
      URL = {http://www.truststc.org/pubs/622.html}
  }
  

Posted by Jessica Gamble on 18 Mar 2009.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.