LH*RS---a highly-available scalable distributed data structure

ABSTRACT

LH*RS is a high-availability scalable distributed data structure (SDDS). An LH*RS file is hash partitioned over the distributed RAM of a multicomputer, for example, a network of PCs, and supports the unavailability of any k ≥ 1 of its server nodes. The value of k transparently grows with the file to offset the reliability decline. Only the number of the storage nodes potentially limits the file growth. The high-availability management uses a novel parity calculus that we have developed, based on Reed-Salomon erasure correcting coding. The resulting parity storage overhead is about the lowest possible. The parity encoding and decoding are faster than for any other candidate coding we are aware of. We present our scheme and its performance analysis, including experiments with a prototype implementation on Wintel PCs. The capabilities of LH*RS offer new perspectives to data intensive applications, including the emerging ones of grids and of P2P computing.

REFERENCES

• 1: Guillermo A. Alvarez , Walter A. Burkhard , Flaviu Cristian, Tolerating multiple failures in RAID architectures with optimal storage and uniform declustering, Proceedings of the 24th annual international symposium on Computer architecture, p.62-72, June 01-04, 1997, Denver, Colorado, United States
• 2: Anderson, D. and Kubiatowicz, J. 2002. The Worldwide Computer. In Scientific American 286, 3, March.
• 3: The Boxwood Project. http://research.microsoft.com/research/sv/Boxwood/.
• 4: Bartalos, G. 1999. Internet: D-day at eBay. Yahoo INDIVIDUAL INVESTOR ONLINE, (July 19).
• 5: Elisa Bertino , C , Kian-Lee Tan , Beng Chin Ooi , Ron Sacks-Davis , Justin Zobel , Boris Shidlovsky, Indexing Techniques for Advanced Database Systems, Kluwer Academic Publishers, Norwell, MA, 1997
• 6: Bennour, F., Di&enegrave;, A., Ndiaye, Y., and Litwin, W. 2000. Scalable and distributed linear hashing LH*LH under Windows NT. In SCI-2000 (Systemics, Cybernetics, and Informatics), Orlando, Florida.
• 7: Bennour, F. 2002. Performance of the SDDS LH*LH under SDDS-2000. In Distributed Data and Structures 4 (Proceedings of WDAS 2002), Carleton Scientific, 1--12.
• 8: Burkhard, W. A. and Menon, J. 1993. Disk array storage system reliability. In Proceedings of the 22nd International Symposium on Fault Tolerant Computing, Toulouse, 432--441.
• 9: Itzik Ben-Gan , Thomas Moreau, Advanced Transact-SQL for SQL Server 2000, Apress, Berkely, CA, 2000
• 10: Yuri Breitbart , Radek Vingralek , Gerhard Weikum, Load control in scalable distributed file structures, Distributed and Parallel Databases, v.4 n.4, p.319-354, Oct. 1996 [doi>10.1007/BF00119338]
• 11: Breitbart, Y. and Vingralek, R. 1998. Addressing and balancing issues in distributed B+ trees. In 1st Workshop on Distributed Data and Structures (WDAS '98), Carleton-Scientific.
• 12: Com. ACM. 1997. Special Issue on High-Performance Computing (Oct).
• 13: CERIA Home page: http://ceria.dauphine.fr/
• 14: http://www.contingencyplanningresearch.com/cod.htm. 1996. Cost of a downtime Study.
• 15: Roger Dingledine , Michael J. Freedman , David Molnar, The free haven project: distributed anonymous storage service, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.67-95, January 2001, Berkeley, California, United States
• 16: Donoghue, A. Boldly 2003. Googling into the future. http://insight.zdnet.co.uk/internet/ecommerce/0,39020454,39116781,00.htm
• 17: Economist 2003. Moving up the stack. www.economist.com.May.
• 18: Gribble, S., Brewer, E., A., Hellerstein, J., and Culler, D. 2000. Scalable, Distributed Data Structures for Internet Service Construction. 4th Symposium on Operating Systems Design and Implementation (OSDI'00).
• 19: Gray, J., Szalay, A. S., Ihakar, A., Kunszt, P. S., Stoughton, C., Slutz, D. R., and van den Berg, J. 2002. Data Mining of SDDS SkyServer Database. International Workshop on Distributed Data Structures, (WDAS'02), Carleton Scientific.
• 20: R. L. Haskin , F. B. Schmuck, The Tiger Shark file system, Proceedings of the 41st IEEE International Computer Conference, p.226, February 25-28, 1996
• 21: Hellerstein, L., Gibson, G., Karp, R., Katz, R., and Patterson, R. 1994. Coding techniques for handling failures in large disk arrays. Algorithmica, vol. 12, p. 182--208.
• 22: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 23: John Kubiatowicz, Extracting guarantees from chaos, Communications of the ACM, v.46 n.2, February 2003 [doi>10.1145/606272.606297]
• 24: Jonas S. Karlsson , Witold Litwin , Tore Risch, LH*LH: A scalable High Performance Data Structure for Switched Multicomputers, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.573-591, March 25-29, 1996
• 25: Lindberg, R. 1997. A Java Implementation of a Highly Available Scalable and Distributed Data Structure LH*g. Master Th. LiTH-IDA-Ex-97/65. U. Linkoping, 1997/62.
• 26: Witold Litwin, Linear Hashing: a new tool for file and table addressing., Readings in database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 27: Litwin, W. 1980. Linear hashing: A new algorithm for files and tables addressing. International Conference on Databases. Aberdeen, Heyden, p. 260--275.
• 28: W. Litwin , M.-A. Neimat , G. Lev , S. Ndiaye , T. Seck, LH*s: a high-availability and high-security scalable distributed data structure, Proceedings of the 7th International Workshop on Research Issues in Data Engineering (RIDE '97) High Performance Database Management for Large-Scale Applications, p.141, April 07-08, 1997
• 29: Litwin, W., Menon J., and Risch, T. 1998. LH* with Scalable Availability. IBM Almaden Res. Rep. RJ 10121 (91937), (May).
• 30: Litwin, W., Menon, J., Risch, T., and Schwarz, T. 1999. Design Issues For Scalable Availability LH* Schemes with Record Grouping. DIMACS Workshop on Distributed Data and Structures, Princeton U. Carleton Scientific.
• 31: Litwin, W., Moussa, R., and Schwarz, T., 2004a. LH*RS: A Highly Available Distributed Data Storage System. Research Prototype Demonstration. VLDB Toronto.
• 32: Litwin, W., Moussa, R., and Schwarz, T. 2004b. LH*RS: A Highly Available Distributed Data Storage System. CERIA Tech. Rep. (Dec).
• 33: Witold Litwin , Marie-Anne Neimat , Donovan A. Schneider, LH: Linear Hashing for distributed files, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.327-336, May 25-28, 1993, Washington, D.C., United States
• 34: Witold Litwin , Marie-Anna Neimat , Donovan A. Schneider, LH*—a scalable, distributed data structure, ACM Transactions on Database Systems (TODS), v.21 n.4, p.480-525, Dec. 1996 [doi>10.1145/236711.236713]
• 35: W. Litwin , M.-A. Neimat, High-Availability LH* Schemes with Mirroring, Proceedings of the First IFCIS International Conference on Cooperative Information Systems, p.196, June 19-21, 1996
• 36: Litwin, W. and Risch, T. 1997. LH*g: A High-availability Scalable Distributed Data Structure through Record Grouping. Res. Rep. CERIA, U. Dauphine and U. Linkoping (May).
• 37: Witold Litwin , Tore Risch, LH*G: A High-Availability Scalable Distributed Data Structure By Record Grouping, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.923-927, July 2002 [doi>10.1109/TKDE.2002.1019223]
• 38: Witold Litwin , Thomas Schwarz, LH*RS: a high-availability scalable distributed data structure using Reed Solomon Codes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.237-248, May 15-18, 2000, Dallas, Texas, United States
• 39: Witold Litwin , Tore Risch, LH*G: A High-Availability Scalable Distributed Data Structure By Record Grouping, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.923-927, July 2002 [doi>10.1109/TKDE.2002.1019223]
• 40: Ljungstr&omuml;, M. 2000. Implementing LH*RS: A scalable distributed highly-available data structure, Master Thesis, Feb., CS Dep. U. Linkoping, Sweden.
• 41: Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi , Daniel A. Spielman , Volker Stemann, Practical loss-resilient codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.150-159, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258573]
• 42: MaCwilliams, F. J. and Sloane, N. J. A. 1997. The Theory of Error Correcting Codes. Elsevier/North Holland, Amsterdam.
• 43: Moussa, R. 2003. In Distributed Data and Structures 4, Carleton Scientific (Records of WDAS 2002, Paris).
• 44: Moussa, R. 2004. Experimental Performance Analysis of LH*RS. CERIA Res. Rep. {CERIA}.
• 45: Moussa, R. and Litwin, W. 2002. Experimental performance analysis of LH*RS parity management. Distributed Data and Structures 4, Records of the 4th International Meeting (WDAS 2002), Paris, France.
• 46: Jehan-François Pâris, The management of replicated data, Papers of the workshop on Hardware and software architectures for fault tolerance : experiences and perspectives: experiences and perspectives, p.305-311, June 1994, Le Mont Saint Michel, France
• 47: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill, Inc., New York, NY, 1999
• 48: RFC 793---Transmission Control Protocol http://www.faqs.org/rfcs/rfc793.html
• 49: Maitrayi Sabaratnam , Svein-Olaf Hvasshovd , Øystein Torbjørnsen, Evaluating the Effectiveness of Fault Tolerance in Replicated Database Management Systems, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.306, June 15-18, 1999
• 50: Schwarz, T. 2003. Generalized Reed Solomon Codes for Erasure Correction in SDDS. Workshop on Distributed Data and Structure 4, WDAS-4, Paris. Carleton Scientific.
• 51: SDDS-Bibliography. http://192.134.119.81/SDDS-bibliograhie.html, http://ceria.dauphine.fr/witold.html
• 52: Radek Vingralek , Yuri Breitbart , Gerhard Weikum, Snowball: Scalable Storage on Networks of Workstations with Balanced Load, Distributed and Parallel Databases, v.6 n.2, p.117-156, April 1998 [doi>10.1023/A:1008609030195]
• 53: Hakim Weatherspoon , John Kubiatowicz, Erasure Coding Vs. Replication: A Quantitative Comparison, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.328-338, March 07-08, 2002
• 54: Qin Xin , Ethan L. Miller , Thomas Schwarz , Darrell D. E. Long , Scott A. Brandt , Witold Litwin, Reliability Mechanisms for Very Large Storage Systems, Proceedings of the 20 th IEEE/11 th NASA Goddard Conference on Mass Storage Systems and Technologies (MSS'03), p.146, April 07-10, 2003
• 55: Qin Xin , Ethan L. Miller , Thomas J. E. Schwarz, Evaluation of Distributed Recovery in Large-Scale Storage Systems, Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing (HPDC'04), p.172-181, June 04-06, 2004 [doi>10.1109/HPDC.2004.12]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Distributed data structures

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Recovery and restart; Access methods

Keywords:
P2P, Scalable distributed data structure, grid computing, high-availability, linear hashing, physical database design