More Web Proxy on the site http://driver.im/

article

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

Authors:

Thomas SchwarzAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 30, Issue 3

Pages 769 - 811

https://doi.org/10.1145/1093382.1093386

Published: 01 September 2005 Publication History

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.

Supplementary Material

Litwin Appendix (p769-litwin-apndx.pdf)

Online appendix to designing mediation for context-aware applications. The appendix supports the information on page 769.

Download
245.61 KB

References

[1]

Alvarez, G., Burkhard, W., and Cristian, F. 1997. Tolerating multiple failures in RAID Architecture with Optimal Storage and Uniform Declustering. In International Symposium on Computer Architecture, ISCA-97, 62--72.]]

Digital Library

[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]

Bertino, E., Ooi, B. C., Sacks-Davis, R., Tan, K. L., Zobel, J., Shidlovsky, B., and Catania, B. 1999. Indexing Techniques for Advanced Database Systems. Kluver.]]

Digital Library

[6]

Bennour, F., Di&enegrave;, A., Ndiaye, Y., and Litwin, W. 2000. Scalable and distributed linear hashing LH&ast;LH under Windows NT. In SCI-2000 (Systemics, Cybernetics, and Informatics), Orlando, Florida.]]

[7]

Bennour, F. 2002. Performance of the SDDS LH&ast;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]

Ben-Gan, I., and Moreau, T. Advanced Transact-SQL For SQL Server 2000. 2003. Apress, ISBN 1-8931115-82-8.]]

Digital Library

[10]

Breitbart, Y., Vingralek, R., and Weikum, G. 1996. Load control in scalable distributed file structures. Distributed and Parallel Databases 4, 4, 319--354.]]

Digital Library

[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]

Dingledine, R., Freedman, M., and Molnar, D. 2000. The free haven project: Distributed anonymous storage service. Workshop on Design Issues in Anonymity and Unobservability (July).]]

Digital Library

[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).]]

Digital Library

[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]

Haskin, R. and Schmuck, F. 1996. The Tiger Shark File System. COMPCON-96, 1996.]]

Digital Library

[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.]]

Digital Library

[22]

Knuth, D. 1998. The art of computer programming. Vol. 3 Sorting and searching. 2nd Ed. Addison-Wesley, 780.]]

Digital Library

[23]

Kubiatowicz, J. 2003. Extracting guarantees from chaos. In Communications of the ACM, 46, 2, Feb.]]

Digital Library

[24]

Karlson, J., Litwin, W., and Risch, T. 1996. LH&ast;LH: A scalable high performance data structure for switched multicomputers. In Apers, P., Gardarin, G., Bouzeghoub, M., (eds.) Extending Database Technology, EDBT96, Lecture Notes in Computer Science, vol. 1057. Springer Verlag.]]

Digital Library

[25]

Lindberg, R. 1997. A Java Implementation of a Highly Available Scalable and Distributed Data Structure LH&ast;g. Master Th. LiTH-IDA-Ex-97/65. U. Linkoping, 1997/62.]]

[26]

Litwin, W. 1994. Linear hashing: A new tool for file and table addressing. Reprinted from VLDB80 in Readings in Databases, edited by M. Stonebraker, 2nd Edition, Morgan Kaufmann Publishers.]]

Digital Library

[27]

Litwin, W. 1980. Linear hashing: A new algorithm for files and tables addressing. International Conference on Databases. Aberdeen, Heyden, p. 260--275.]]

[28]

Litwin, W., Neimat, M.-A. Levy, G., Ndiaye, S., and Seck, T. 1997. LH&ast;S: A high-availability and high-security Scalable Distributed Data Structure. IEEE-Res. Issues in Data Eng. (RIDE-97).]]

Digital Library

[29]

Litwin, W., Menon J., and Risch, T. 1998. LH&ast; 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&ast; 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&ast;RS: A Highly Available Distributed Data Storage System. Research Prototype Demonstration. VLDB Toronto.]]

[32]

Litwin, W., Moussa, R., and Schwarz, T. 2004b. LH&ast;RS: A Highly Available Distributed Data Storage System. CERIA Tech. Rep. (Dec).]]

[33]

Litwin, W., Neimat, M.-A., and Schneider, D. 1993. Linear Hashing for Distributed Files. ACM-SIGMOD International Conference on Management of Data.]]

Digital Library

[34]

Litwin, W., Neimat, M.-A., and Schneider, D. 1996. A Scalable Distributed Data Structure. ACM Trans. Datab. Syst., Dec.]]

Digital Library

[35]

Litwin, W. and Neimat, M.-A. 1996. High-Availability LH&ast; Schemes with Mirroring, International Conference on Cooperating Information Systems, (COOPIS) IEEE Press.]]

Digital Library

[36]

Litwin, W. and Risch, T. 1997. LH&ast;g: A High-availability Scalable Distributed Data Structure through Record Grouping. Res. Rep. CERIA, U. Dauphine and U. Linkoping (May).]]

[37]

Litwin, W. and Risch, T. 2001. LH&ast;g: A high-availability scalable distributed data structure by record grouping. IEEE Trans. Knowl. Data Eng. 14, 4, 923--927.]]

Digital Library

[38]

Litwin, W. and Schwarz T. 2000. LH&ast;RS: A high-availability scalable distributed data structure using Reed Solomon codes. ACM-SIGMOD International conference on Management of Data.]]

Digital Library

[39]

Litwin, W. and Risch, T. 2002. LH&ast;g : A High-availability scalable distributed data structure by record grouping. IEEE Trans. Knowl. Data Eng. 14, 4, July/Aug.]]

Digital Library

[40]

Ljungstr&omuml;, M. 2000. Implementing LH&ast;RS: A scalable distributed highly-available data structure, Master Thesis, Feb., CS Dep. U. Linkoping, Sweden.]]

[41]

Luby, M., Mitzenmacher, M., Shokrollahi, M., Spielman, D., and Stemann, V. 1997. Practical Loss-Resilient Codes, STOC 97, Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing, El Paso, TX, 150--159.]]

Digital Library

[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&ast;RS. CERIA Res. Rep. {CERIA}.]]

[45]

Moussa, R. and Litwin, W. 2002. Experimental performance analysis of LH&ast;RS parity management. Distributed Data and Structures 4, Records of the 4th International Meeting (WDAS 2002), Paris, France.]]

[46]

Pâris, J. F. 1993. The management of replicated data. In Proceedings of the Workshop on Hardware and Software Architectures for Fault Tolerance. Mt. St. Michel, Fr. June.]]

Digital Library

[47]

Ramakrishnan, R. 1999. Database Management Systems. McGraw Hill.]]

Digital Library

[48]

RFC 793---Transmission Control Protocol http://www.faqs.org/rfcs/rfc793.html]]

[49]

Sabaratnam M., Torbjornsen, and Hvasshovd, S.-O. 1999. Evaluating the effectiveness of fault tolerance in replicated database management systems. 29th. Annual Interantional Symposium on Fault Tolerant Computing.]]

Digital Library

[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]

Vingralek, R., Breitbart, Y., Weikum, G. and Snowball. 1998. Scalable storage on networks of workstations. Distributed and Parallel Databases 6, 2, 117--156.]]

Digital Library

[53]

Weatherspoon, H. and Kubiatowicz, J. 2002. Erasure coding vs. replication: A quantitative comparison. 1st International Workshop on Peer-to-Peer systems, IPTPS-2002. March.]]

Digital Library

[54]

Xin, Q., Miller, E., Schwarz, T., Brandt, S., Long, D., Litwin, W. 2003. Reliability mechanisms for very large storage systems. 20th IEEE mass storage systems and technologies (MSST 2003), San Diego, CA. 146--156.]]

Digital Library

[55]

Xin, Q., Miller, E., and Schwarz, T. 2004. Evaluation of distributed recovery in large-scale storage systems. In 13th IEEE International Symposium on High Performance Distributed Computing (HPDC'04), Honolulu, HI.]]

Digital Library

Cited By

Ren YRen YLi XHu YLi JLee PMa XWon Y(2024)ELECTProceedings of the 22nd USENIX Conference on File and Storage Technologies10.5555/3650697.3650715(293-310)Online publication date: 27-Feb-2024
https://dl.acm.org/doi/10.5555/3650697.3650715
Shen ZCai YCheng KLee PLi XHu YShu J(2024)A Survey of the Past, Present, and Future of Erasure Coding for Storage SystemsACM Transactions on Storage10.1145/3708994Online publication date: 31-Dec-2024
https://doi.org/10.1145/3708994
Ning A(2024)A Highly Available Database System Based on Load Balancing Functionality2024 IEEE 2nd International Conference on Image Processing and Computer Applications (ICIPCA)10.1109/ICIPCA61593.2024.10709101(841-844)Online publication date: 28-Jun-2024
https://doi.org/10.1109/ICIPCA61593.2024.10709101
Show More Cited By

Recommendations

LH*—a scalable, distributed data structure

We present a scalable distributed data structure called LH*. LH* generalizes Linear Hashing (LH) to distributed RAM and disk files. An LH* file can be created from records with primary keys, or objects with OIDs, provided by any number of distributed and ...
LH * RSP 2 P : a fast and high churn resistant scalable distributed data structure for P2P systems

LH*<SUB align=right>RS<SUP align=right>P2P</SUP> is a new scalable distributed data structure (SDDS) for P2P applications. It deals with two major issues in P2P systems. One is efficient location of the peers with searched data ...
LH*RS: a high-availability scalable distributed data structure using Reed Solomon Codes

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 30, Issue 3

September 2005

226 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/1093382

Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2005

Published in TODS Volume 30, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
1,593
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ren YRen YLi XHu YLi JLee PMa XWon Y(2024)ELECTProceedings of the 22nd USENIX Conference on File and Storage Technologies10.5555/3650697.3650715(293-310)Online publication date: 27-Feb-2024
https://dl.acm.org/doi/10.5555/3650697.3650715
Shen ZCai YCheng KLee PLi XHu YShu J(2024)A Survey of the Past, Present, and Future of Erasure Coding for Storage SystemsACM Transactions on Storage10.1145/3708994Online publication date: 31-Dec-2024
https://doi.org/10.1145/3708994
Ning A(2024)A Highly Available Database System Based on Load Balancing Functionality2024 IEEE 2nd International Conference on Image Processing and Computer Applications (ICIPCA)10.1109/ICIPCA61593.2024.10709101(841-844)Online publication date: 28-Jun-2024
https://doi.org/10.1109/ICIPCA61593.2024.10709101
Slesarev AMikhailov MChernishev G(2023)Benchmarking Hashing Algorithms for Load Balancing in a Distributed Database EnvironmentAdvances in Model and Data Engineering in the Digitalization Era10.1007/978-3-031-23119-3_8(105-118)Online publication date: 10-Jan-2023
https://doi.org/10.1007/978-3-031-23119-3_8
Cheng LHu YKe ZXu JYao QFeng DWang WChen Wde Supinski BHall MGamblin T(2021)LogECMemProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3458817.3480852(1-15)Online publication date: 14-Nov-2021
https://dl.acm.org/doi/10.1145/3458817.3480852
Cheng LHu YLee P(2019)Coupling Decentralized Key-Value Stores with Erasure CodingProceedings of the ACM Symposium on Cloud Computing10.1145/3357223.3362713(377-389)Online publication date: 20-Nov-2019
https://dl.acm.org/doi/10.1145/3357223.3362713
Li SZhang QYang ZZhao HDai Y(2018)Building efficient and available distributed transaction with Paxos-based coding consensusIEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)10.1109/INFCOMW.2018.8406832(373-378)Online publication date: Apr-2018
https://doi.org/10.1109/INFCOMW.2018.8406832
Cheng LHu YWei WXiao R(2018)Enhanced Self-Coding for Available Memcached2018 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking, Sustainable Computing & Communications (ISPA/IUCC/BDCloud/SocialCom/SustainCom)10.1109/BDCloud.2018.00106(700-707)Online publication date: Dec-2018
https://doi.org/10.1109/BDCloud.2018.00106
Yiu MChan HLee PChen DDesnoyers Pde Lara E(2017)Erasure coding for small objects in in-memory KV storageProceedings of the 10th ACM International Systems and Storage Conference10.1145/3078468.3078470(1-12)Online publication date: 22-May-2017
https://dl.acm.org/doi/10.1145/3078468.3078470
Chabkinian JSchwarz Sj T(2016)Fast LH$$*$$źInternational Journal of Parallel Programming10.1007/s10766-015-0371-844:4(709-734)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s10766-015-0371-8
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents