Antiquity: exploiting a secure log for wide-area distributed storage

ABSTRACT

Antiquity is a wide-area distributed storage system designed to provide a simple storage service for applications like file systems and back-up. The design assumes that all servers eventually fail and attempts to maintain data despite those failures. Antiquity uses a secure log to maintain data integrity, replicates each log on multiple servers for durability, and uses dynamic Byzantine fault-tolerant quorum protocols to ensure consistency among replicas. We present Antiquity's design and an experimental evaluation with global and local testbeds. Antiquity has been running for over two months on 400+ PlanetLab servers storing nearly 20,000 logs totaling more than 84 GB of data. Despite constant server churn, all logs remain durable.

REFERENCES

• 1: Michael Abd-El-Malek , Gregory R. Ganger , Garth R. Goodson , Michael K. Reiter , Jay J. Wylie, Fault-scalable Byzantine fault-tolerant services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 2: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 3: N. S. Agency. Global information grid (gig). http://www.nsa.gov/ia/industry/gig.cfm. Last accessed September 2006.
• 4: T. E. Anderson , M. D. Dahlin , J. M. Neefe , D. A. Patterson , D. S. Roselli , R. Y. Wang, Serverless network file systems, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.109-126, December 03-06, 1995, Copper Mountain, Colorado, United States
• 5: Andy Bavier , Mic Bowman , Brent Chun , David Culler , Scott Karlin , Steve Muir , Larry Peterson , Timothy Roscoe , Tammo Spalink , Mike Wawrzoniak, Operating system support for planetary-scale network services, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.19-19, March 29-31, 2004, San Francisco, California
• 6: Ranjita Bhagwan , Kiran Tati , Yu-Chung Cheng , Stefan Savage , Geoffrey M. Voelker, Total recall: system support for automated availability management, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.25-25, March 29-31, 2004, San Francisco, California
• 7: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 8: Byung-Gon Chun , Frank Dabek , Andreas Haeberlen , Emil Sit , Hakim Weatherspoon , M. Frans Kaashoek , John Kubiatowicz , Robert Morris, Efficient replica maintenance for distributed storage systems, Proceedings of the 3rd conference on 3rd Symposium on Networked Systems Design & Implementation, p.4-4, May 08-10, 2006, San Jose, CA
• 9: E. Corp. Symmetrix remote data facility. http://www.emc.com/products/networking/srdf.jsp.Last accessed April 2006.
• 10: James Cowling , Daniel Myers , Barbara Liskov , Rodrigo Rodrigues , Liuba Shrira, HQ replication: a hybrid quorum protocol for byzantine fault tolerance, Proceedings of the 7th conference on USENIX Symposium on Operating Systems Design and Implementation, p.13-13, November 06-08, 2006, Seattle, WA
• 11: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 12: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 13: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 14: Patrick Eaton , Hakim Weatherspoon , John Kubiatowicz, Efficiently Binding Data to Owners in Distributed Content-Addressable Storage Systems, Proceedings of the Third IEEE International Security in Storage Workshop (SISW'05), p.40-51, December 13-13, 2005 [doi>10.1109/SISW.2005.4]
• 15: P. R. Eaton. Improving Access to Remote Storage for Weakly Connected Users. PhD thesis, EECS Department, University of California, Berkeley, January 11 2007.
• 16: Kevin Fu , M. Frans Kaashoek , David Mazières, Fast and secure distributed read-only file system, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.13-13, October 22-25, 2000, San Diego, California
• 17: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 18: G. R. Goodson, J. J. Wylie, G. R. Ganger, and M. K. Reiter. Byzantine-tolerant erasure-coded storage. Technical Report CMU-CS-03-187, Carnegie Mellon University School for Computer Science, Sept. 2003.
• 19: Andreas Haeberlen , Alan Mislove , Peter Druschel, Glacier: highly durable, decentralized storage despite massive correlated failures, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.143-158, May 02-04, 2005
• 20: John H. Hartman , John K. Ousterhout, The Zebra striped network file system, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.29-43, December 05-08, 1993, Asheville, North Carolina, United States
• 21: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 22: Edward K. Lee , Chandramohan A. Thekkath, Petal: distributed virtual disks, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.84-92, October 01-04, 1996, Cambridge, Massachusetts, United States
• 23: Fay W. Chang , Minwen Ji , Shun-Tak A. Leung , John MacCormick , Sharon E. Perl , Li Zhang, Myriad: Cost-Effective Disaster Tolerance, Proceedings of the Conference on File and Storage Technologies, p.103-116, January 28-30, 2002
• 24: Jinyuan Li , Maxwell Krohn , David Mazières , Dennis Shasha, Secure untrusted data repository (SUNDR), Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.9-9, December 06-08, 2004, San Francisco, CA
• 25: Barbara Liskov , Sanjay Ghemawat , Robert Gruber , Paul Johnson , Liuba Shrira, Replication in the harp file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.226-238, October 13-16, 1991, Pacific Grove, California, United States
• 26: Dahlia Malkhi , Michael Reiter, Byzantine quorum systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.569-578, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258650]
• 27: D. Malkhi, M. K. Reiter, D. Tulone, and E. Ziskind. Persistent objects in the fleet system. In DISCEX II, 2001.
• 28: Petros Maniatis , Mema Roussopoulos , T. J. Giuli , David S. H. Rosenthal , Mary Baker, The LOCKSS peer-to-peer digital preservation system, ACM Transactions on Computer Systems (TOCS), v.23 n.1, p.2-50, February 2005 [doi>10.1145/1047915.1047917]
• 29: Jean-Philippe Martin , Lorenzo Alvisi, A Framework for Dynamic Byzantine Storage, Proceedings of the 2004 International Conference on Dependable Systems and Networks (DSN'04), p.325, June 28-July 01, 2004
• 30: Jeanna Neefe Matthews , Drew Roselli , Adam M. Costello , Randolph Y. Wang , Thomas E. Anderson, Improving the performance of log-structured file systems with adaptive methods, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.238-251, October 05-08, 1997, Saint Malo, France
• 31: Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
• 32: Sape J. Mullender , Andrew S. Tanenbaum, A distributed file service based on optimistic concurrency control, Proceedings of the tenth ACM symposium on Operating systems principles, p.51-62, December 1985, Orcas Island, Washington, United States
• 33: A. Muthitacharoen, S. Gilbert, and R. Morris. Etna: A fault-tolerant algorithm for atomic mutable dht data. Technical Report MIT-LCS-TR-993, MIT Laboratory for Computer Science, June 2004.
• 34: Athicha Muthitacharoen , Robert Morris , Thomer M. Gil , Benjie Chen, Ivy: a read/write peer-to-peer file system, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060293]
• 35: Larry Peterson , Andy Bavier , Marc E. Fiuczynski , Steve Muir, Experiences building PlanetLab, Proceedings of the 7th conference on USENIX Symposium on Operating Systems Design and Implementation, p.25-25, November 06-08, 2006, Seattle, WA
• 36: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 37: Sean Rhea , Byung-Gon Chun , John Kubiatowicz , Scott Shenker, Fixing the embarrassing slowness of OpenDHT on PlanetLab, Proceedings of the 2nd conference on Real, Large Distributed Systems, p.5-5, December 13, 2005, San Francisco, CA
• 38: Sean Rhea , Patrick Eaton , Dennis Geels , Hakim Weatherspoon , Ben Zhao , John Kubiatowicz, Awarded Best Student Paper! - Pond: The OceanStore Prototype, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 39: Sean Rhea , Dennis Geels , Timothy Roscoe , John Kubiatowicz, Handling churn in a DHT, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.10-10, June 27-July 02, 2004, Boston, MA
• 40: R. Rodrigues and B. Liskov. Rosebud: A scalable byzantine-fault-tolerant storage architecture. Technical Report MIT-LCS-TR-932, MIT Laboratory for Computer Science, Dec. 2003.
• 41: Bruce Schneier , John Kelsey, Cryptographic support for secure logs on untrusted machines, Proceedings of the 7th conference on USENIX Security Symposium, 1998, p.4-4, January 26-29, 1998, San Antonio, Texas
• 42: Andrew S. Tanenbaum , Robbert van Renesse , Hans van Staveren , Gregory J. Sharp , Sape J. Mullender, Experiences with the Amoeba distributed operating system, Communications of the ACM, v.33 n.12, p.46-63, Dec. 1990 [doi>10.1145/96267.96281]
• 43: Chandramohan A. Thekkath , Timothy Mann , Edward K. Lee, Frangipani: a scalable distributed file system, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.224-237, October 05-08, 1997, Saint Malo, France
• 44: Robbert van Renesse , Fred B. Schneider, Chain replication for supporting high throughput and availability, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.7-7, December 06-08, 2004, San Francisco, CA
• 45: H. Weatherspoon. Design and Evaluation of Distributed Wide-Area On-line Archival Storage Systems. PhD thesis, EECS Department, University of California, Berkeley, October 13 2006.
• 46: Lidong Zhou , Fred B. Schneider , Robbert Van Renesse, COCA: A secure distributed online certification authority, ACM Transactions on Computer Systems (TOCS), v.20 n.4, p.329-368, November 2002 [doi>10.1145/571637.571638]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems
      D.4.5 Reliability
          Subjects: Fault-tolerance
  D.m MISCELLANEOUS

General Terms:
Design, Experimentation, Performance, Reliability, Security

Keywords:
archival storage systems, data durability, data integrity, distributed storage system, wide-area