LH*RS: a high-availability scalable distributed data structure using Reed Solomon Codes

ABSTRACT

LH*RS is a new high-availability Scalable Distributed Data Structure (SDDS). The data storage scheme and the search performance of LH*RS are basically these of LH*. LH*RS manages in addition the parity information to tolerate the unavailability of k ⪈ 1 server sites. The value of k scales with the file, to prevent the reliability decline. The parity calculus uses the Reed -Solomon Codes. The storage and access performance overheads to provide the high-availability are about the smallest possible. The scheme should prove attractive to data-intensive applications.

REFERENCES

• ABC97: 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
• B&al95: C. K. Baru , G. Fecteau , A. Goyal , H. Hsiao , A. Jhingran , S. Padmanabhan , G. P. Copeland , W. G. Wilson, DB2 parallel edition, IBM Systems Journal, v.34 n.2, p.292-322, 1995
• B99: Bartalos, G. Intemet: D-Day at eBay. Yahoo INDIVIDUAL INVESTOR ONLINE, (Jul 19, 1999).
• B99a: 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
• BBM93: Mario Blaum , Jim Brady , Jehoshua Bruck , Jai Menon, EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures, IEEE Transactions on Computers, v.44 n.2, p.192-202, February 1995 [doi>10.1109/12.364531]
• BFT98: B laum, M & al. Array Codes, Handbook of Coding Theory. V.S. Hess and W.C. Huffman, (ed.), Elsevier Science B.V., 1998.
• BV98: Breitbart, Y. Vingralek, R. Distributed and Scalable B+ tree Data Structures. Workshop on Distr. Data and Struct., 1998, Carleton Scientific (publ.)
• BM93: W. A. Burkhard, J. Menon: Disk Array Storage System Reliability. 22rd Intl. Syrup. on Fault Tolerant Computing, Toulouse, June 1993,432-441.
• CACM97: Special Issue on High-Performance Computing. Comm. Of ACM. (Oct. 1997).
• G99: Gribble, S. Cluster-Based Intemet Services with SDDS. Master Th. UC Berkeley, 1999.
• H96: 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
• H&a94: Hellerstein, L, Gibson, G., Karp, R., Katz, R. Patterson, D. Coding Techniques for Handling Failures in Large Disk Arrays. Algorithmica, 1994, 12, 182-208.
• I98: Inktomi Corporation. http://www.inktomi.com/.
• IBM99: Breaking the Scalability Barrier on Windows NT. http://w ww. s oftw are. ibm. c om/data/p ubs/p apers/nt- scale/
• K98: 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
• KLR96: 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
• L80: Witold Litwin, Linear hashing: a new tool for file and table addressing, Readings in database systems (2nd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• L97: Lindberg., R. 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.
• L&al97: 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
• L00: Ljungstr6m, M. Implementing LH*Rs " A Scalable Distributed High-Availability Data Structure. Master Th. (Feb. 2000), CS Dep., U. Linkoping, Suede.
• LMR98: Litwin, W., Menon J., Risch, T..LH* with Scalable Availability. IBM Almaden Res. Rep. RJ 10121 (91937), (May 1998), (subm.).
• LMRS99: Litwin, W., Menon, J.Risch, T., Schwarz, Th. Design Issues For Scalable Availability LH* Schemes with Record Grouping. DIMACS Workshop on Distributed Data and Structures. Carleton Scientific, 1999.
• LNS93: 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
• LNS96: 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]
• LN96: 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
• LR97: Litwin W., Risch, T. LH*g: a High-Availability Scalable Distributed Data Structure through Record Grouping. Res. Rep. CERIA, U. Dauphine & U. Linkoping (May. 1997).
• LS99: Litwin, W., Schwarz, Th. LH*Rs" A High- Availability Scalable Distributed Data Structure using Reed Solomon Codes. Res. Rep. CERIA, U. Dauphine (Sept. 1999).
• M97: Gates, B. The Microsoft Scalability Day http://204.203.124.10/backoffice/scalability/covera#e.htm
• MM92: Marcus, M., Minc, H. A Survey of Matrix Theory and Matrix Inequalities, Dover, New York, 1992.
• P98: President's Inf. Techn. Advisory Comm. Interim Rep. To the Pres. Of the United States. August 1998.
• MS97: MacWilliams, F. J., Sloane, N. J. A. The Theory of Error Correcting Codes, Elsevier / North Holland, Amsterdam, 1997.
• PTVF92: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• R98: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• S99: Smith, D. The Cost of Lost Data. Res. Rep. School of Business and Management, Pepperdine University, 1999.
• SDDS: SDDS-bibliography. http ://ceria.dauphine. fr/S D DS-bib liograhie.html
• SG90: Michael Stonebraker , Gerhard A. Schloss, Distributed RAID - A New Multiple Copy Algorithm, Proceedings of the Sixth International Conference on Data Engineering, p.430-437, February 05-09, 1990
• VBW94: Radek Vingralek , Yuri Breitbart , Gerhard Weikum, Distributed file organization with scalable cost/performance, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.253-264, May 24-27, 1994, Minneapolis, Minnesota, United States
• VBW98: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Management, Performance

Keywords:
Reed-Solomon Codes, SDDS, high-availability, scalable