LH* <sub>RS</sub> ---a highly-available scalable distributed data structure
ACM Transactions on Database SystemsPublished 1 September 2005
Witold Litwin, Rim Moussa, Thomas Schwarz
Citations48
SJR quartileQ1
SJR score0.91
SNIP1.85
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The scheme and its performance analysis are presented, including experiments with a prototype implementation on Wintel PCs, and the parity encoding and decoding are faster than for any other candidate coding the authors are aware of.
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.
Keywords
Computer Science
North-Holland mathematical libraryThe Theory of Error-Correcting Codes
11,012 Citations1977
This book presents an introduction to BCH Codes and Finite Fields, and methods for Combining Codes, and discusses self-dual Codes and Invariant Theory, as well as nonlinear Codes, Hadamard Matrices, Designs and the Golay Code.
IEEE Transactions on Information TheoryLow-density parity-check codes
10,471 Citations1962Robert G. Gallager
A simple but nonoptimum decoding scheme operating directly from the channel a posteriori probabilities is described and the probability of error using this decoder on a binary symmetric channel is shown to decrease at least exponentially with a root of the block length.
IEEE Transactions on Information TheoryGood error-correcting codes based on very sparse matrices
3,690 Citations1999David Mackay
IEEE Transactions on CommunicationsNear optimum error correcting coding and decoding: turbo-codes
2,743 Citations1996Claude Berrou, Alain Glavieux
A new family of convolutional codes, nicknamed turbo-codes, built from a particular concatenation of two recursive systematic codes, linked together by nonuniform interleaving appears to be close to the theoretical limit predicted by Shannon.
Electronics LettersNear Shannon limit performance of low density paritycheck codes
2,673 Citations1997David Mackay, Radford M. Neal
The authors report the empirical performance of Gallager's low density parity check codes on Gaussian channels, showing that performance substantially better than that of standard convolutional and concatenated codes can be achieved.
Journal of the ACMEfficient dispersal of information for security, load balancing, and fault tolerance
1,364 Citations1989Michael O. Rabin
Information Dispersal Algorithm (IDA) has numerous applications to secure and reliable storage of information in computer networks and even on single disks, to fault-tolerant and efficient transmission ofInformation in networks, and to communications between processors in parallel computers.
Elsevier eBooksDatabase Management Systems
1,336 Citations2014
New to this edition are the early coverage of the ER model, new chapters on Internet databases, data mining, and spatial databases, and a new supplement on practical SQL assignments (with solutions for instructors' use).
A digital fountain approach to reliable distribution of bulk data
1,157 Citations1998John W. Byers, Michael Luby +2 more
A protocol is developed that closely approximates a digital fountain using a new class of erasure codes that for large block sizes are orders of magnitude faster than standard erasures codes.
IEEE Transactions on Information TheoryImproved decoding of Reed-Solomon and algebraic-geometry codes
1,013 Citations1999Venkatesan Guruswami, Madhu Sudan
An improved list decoding algorithm for decoding Reed-Solomon codes and algebraic-geometry codes is presented, which generalizes to solve the list decoding problem for other algebraic codes, specifically alternant codes and algebraic-geometry codes.
Lecture notes in computer scienceErasure Coding Vs. Replication: A Quantitative Comparison
860 Citations2002Hakim Weatherspoon, John Kubiatowicz
It is shown that systems employing erasure codes have mean time to failures many orders of magnitude higher than replicated systems with similar storage and bandwidth requirements and erasure-resilient systems use an order of magnitude less bandwidth and storage to provide similar system durability.
Journal of ComplexityDecoding of Reed Solomon Codes beyond the Error-Correction Bound
739 Citations1997Madhu Sudan
To the best of the knowledge, this is the first efficient (i.e., polynomial time bounded) algorithm which provides error recovery capability beyond the error-correction bound of a code for any efficient code.
IEEE Transactions on ComputersEVENODD: an efficient scheme for tolerating double disk failures in RAID architectures
690 Citations1995Mario Blaum, J. Brady +2 more
A novel method for tolerating up to two disk failures in RAID architectures based on Reed-Solomon error-correcting codes, which can be used in any system requiring large symbols and relatively short codes, for instance, in multitrack magnetic recording.
Row-diagonal parity for double disk failure correction
489 Citations2004Peter Corbett, Bob English +5 more
Software Practice and ExperienceA tutorial on Reed–Solomon coding for fault‐tolerance in RAID-like systems
460 Citations1997James S. Plank
Biomedica biochimica actaAn XOR-based erasure-resilient coding scheme
418 Citations1995Johannes Blömer, Malik Kalfane +4 more
A erasure-resilient coding scheme that is based on a version of Reed-Solomon codes and which has the property that r = m is described, customized to give the rst real-time implementations of Priority Encoding Transmission (PET) for medium quality video transmission on Sun SPARCstation 20 workstations.
IEEE Transactions on Information TheoryX-code: MDS array codes with optimal encoding
404 Citations1999Lihao Xu, Jehoshua Bruck
A new class of MDS (maximum distance separable) array codes of size n/spl times/n (n a prime number) called X-code, which has a simple geometrical construction which achieves encoding/update optimal complexity.
Linear hashing: a new tool for file and table addressing
384 Citations1980Witold Litwin
Lecture notes in computer scienceThe Free Haven Project: Distributed Anonymous Storage Service
334 Citations2001Roger Dingledine, Michael J. Freedman +1 more
A design for a system of anonymous storage which resists the attempts of powerful adversaries to find or destroy any stored data is presented, and a way to classify anonymous systems based on the kinds of anonymity provided is suggested.
Accessing multiple mirror sites in parallel: using Tornado codes to speed up downloads
284 Citations1999John W. Byers, Michael Luby +1 more
This work considers enabling a client to access a file from multiple mirror sites in parallel to speed up the download, and develops a feedback-free protocol based on erasure codes that can deliver dramatic speedups at the expense of transmitting a moderate number of additional packets into the network.
ACM Transactions on Database SystemsLH*—a scalable, distributed data structure
238 Citations1996Witold Litwin, M.-A. Neimat +1 more
It is shown that LH* files can efficiently scale to files that are orders of magnitude larger in size than single-site files, and can be more efficient than any distributed file with a centralized directory, or a static parallel or distributed hash file.
Scalable, distributed data structures for internet service construction
236 Citations2000Steven D. Gribble, Eric Brewer +2 more
The distributed hash table simplifies Internet service construction by decoupling service-specific logic from the complexities of persistent, consistent state management, and by allowing services to inherit the necessary service properties from the DDS rather than having to implement the properties themselves.
Reliability mechanisms for very large storage systems
192 Citations2003Qin Xin, Ethan L. Miller +4 more
It is shown that simple RAID cannot guarantee sufficient reliability; the tradeoffs among other schemes between system availability and storage efficiency are examined; and it is believed that two-way mirroring should be sufficient for most large storage systems.
AlgorithmicaCoding techniques for handling failures in large disk arrays
147 Citations1994Lisa Hellerstein, Garth A. Gibson +3 more
This paper addresses the problem of designing erasure-correcting binary linear codes that protect against the loss of data caused by disk failures in large disk arrays, and describes how such codes can be used to encode data in disks, and gives a simple method for data reconstruction.
International Symposium on Computer ArchitectureEVENODD: an optimal scheme for tolerating double disk failures in RAID architectures
138 Citations1994Mario Blaum, J. Brady +2 more
Database Management Systems
137 Citations1998Oliver Grillmeyer
A database is a collection of information, such as facts about countries, statistics on demographics, a store’s inventory, and phone lists, that allows one to access, insert, delete, and modify information stored within a computer system.
Indexing Techniques for Advanced Database Systems
129 Citations1997Elisa Bertino, Beng Chin Ooi +5 more
Indexing Techniques for Advanced Database Systems is suitable as a secondary text for a graduate level course on indexing techniques, and as a reference for researchers and practitioners in industry.
Disk array storage system reliability
126 Citations2002Walter A. Burkhard, J. Menon
The authors consider various alternatives - improved MTBF and MTTR times as well as smaller reliability groups and increased numbers of check disks per group - to obtain the necessary improved reliability.
Tolerating multiple failures in RAID architectures with optimal storage and uniform declustering
92 Citations1997Guillermo A. Alvarez, Walter A. Burkhard +1 more
DATUM is the first known method that can mask any given number of failures, requires an optimal amount of redundant storage space, and spreads reconstruction accesses uniformly over disks in the presence of failures without needing large layout tables in controller memory.
Linear time erasure codes with nearly optimal recovery
79 Citations2002Noga Alon, Jeff Edmonds +1 more
This work describes erasure codes where both the encoding and decoding algorithms run in linear time and where r is only slightly larger than n and the message is recovered from any set of packets whose total length is r.
High Performance Distributed ComputingEvaluation of distributed recovery in large-scale storage systems
76 Citations2004Qin Xin, Ethan L. Miller +1 more
This work presents fast recovery mechanism (FARM), a distributed recovery approach that exploits excess disk capacity and reduces data recovery time and examines essential factors that influence system reliability, performance, and costs by simulating system behavior under disk failures.
Communications of the ACMExtracting guarantees from chaos
59 Citations2003John Kubiatowicz
The P2P revolution promises freedom from boundaries, censorship, and centralized control and claims the vast untapped resource of personal computers owned by ordinary people can be combined together to build something greater than the sum of its parts.
The Tiger Shark file system
57 Citations2002Roger Haskin, Frank Schmuck
Interestingly, most of the features that make Tiger Shark a good video server are important for other large-scale applications such as technical computing, data mining, digital library, and scalable network file servers.
High-availability LH* schemes with mirroring
42 Citations2002Witold Litwin, M.-A. Neimat
Several schemes for mirroring LH* files are presented, and the authors incorporate this technique into the LH* algorithms for scalable distributed linear hash files.
IEEE Transactions on ComputersA Double Track Error-Correction Code for Magnetic Tape
34 Citations1976Prusinkiewicz, Budkowski
An error-correction code, presented here, uses two redundant tracks and one redundant character which are formed from the askew and the vertical redundancy check (AVRC) bits.
Discrete Applied MathematicsAsymptotically optimal erasure-resilient codes for large disk arrays
33 Citations2000Yeow Meng Chee, Charles J. Colbourn +1 more
This paper takes a set systems view of the problem of constructing erasure-resilient codes, which leads to interesting extremal problems in finite set theory.
Distributed and Parallel DatabasesSnowball: Scalable Storage on Networks of Workstations with Balanced Load
32 Citations1998Radek Vingralek, Yuri Breitbart +1 more
The paper addresses two problems of realistic workloads: skewed access frequencies to the records and evolving access patterns where previously cold records may become hot and vice versa and automatically chooses the appropriate granularity for dynamic data migrations.
IEEE Transactions on Information TheoryCross parity check convolutional codes
30 Citations1989Thomas E. Fuja, C. Heegard +1 more
A class of convolutional codes called cross parity check (CPC) codes, which are useful for the protection of data stored on magnetic tape, is described and analyzed and the technique of parity check matrix reduction, which is useful for reducing the inherent decoding delay of CPC codes is described.
Lecture notes in computer scienceLH*lh: A scalable high performance data structure for switched multicomputers
29 Citations1996Jonas Karlsson, Witold Litwin +1 more
The efficiency of the LH*lh method is proved, various algorithmic choices that were made are justified, and a new perspective for high-performance applications is opened, especially for the database management of new types of data and in real-time environments.
IEEE Transactions on MagneticsReliability and performance of RAIDs
26 Citations1995T.J.E. Schwarz, Walter A. Burkhard
The ACATS declustering scheme is defined and analyzed for use with the classic Level 5 as well as MDS RAIDs both with and without ACATS and trade-offs between performance and reliability within these RAID organizations are demonstrated.
IEEE Transactions on Knowledge and Data EngineeringLH*g: a high-availability scalable distributed data structure by record grouping
26 Citations2002Witold Litwin, Tore Risch
LH*g (Linear Hashing by grouping) is a high-availability extension of the LH* scalable distributed data structure that scales up with constant key search and insert performance, while surviving any single-site unavailability (failure).
LH*s: a high-availability and high-security scalable distributed data structure
24 Citations2002Witold Litwin, M.-A. Neimat +3 more
LH*s is high availability variant of LH*, a Scalable Distributed Data Structure, where an LH*s record is striped onto different server nodes, and a parity segment allows one to reconstruct the record if a segment fails.
Theoretical Computer ScienceOptimal and pessimal orderings of Steiner triple systems in disk arrays
23 Citations2003Myra B. Cohen, Charles J. Colbourn
Steiner triple systems are well studied combinatorial designs that have been shown to possess properties desirable for the construction of multiple erasure codes in RAID architectures, andbinatorial problems involved in the generation of good and bad column orderings are defined.
Software-based erasure codes for scalable distributed storage
20 Citations2003Joseph A. Cooley, Jeremy Mineweaser +2 more
Tests indicate Lincoln Erasure codes (LEC), applicable to large-scale distributed storage that includes thousands of disks attached to multiple networks, has a higher throughput for encoding and decoding and lower probability of failure across a range of test conditions.
Design Issues For Scalable Availability LH* Schemes with Record Grouping 1
17 Citations1999Witold Litwin, Jai Menon +2 more
This work presents three high-availability LH* schemes using new concept of record grouping, and discusses the common building blocks and the specific features of each schema.
Distributed and Parallel DatabasesLoad control in scalable distributed file structures
13 Citations1996Yuri Breitbart, Radek Vingralek +1 more
The paper presents a family of distributed file structures, coined DiFS, for record structured, disk resident files with key based exact or interval match access, which considers explicitly the cost/performance ratio of the system by aiming to minimize the number of servers used to provide the required performance.
Elsevier eBooks*RSLH
12 Citations2004Witold Litwin, Rim Moussa +1 more
This demo, presents a prototype implementation of LH*RS: a highly available scalable and distributed data structure that falls far from the ideal storage system.
Theory of Computing SystemsFlexible Usage of Redundancy in Disk Arrays
11 Citations1999Eric J. Schwabe
This paper demonstrates for the first time how to divide the benefits of extra space for redundant information arbitrarily between increased fault tolerance and accelerated reconstruction of failed disks.
Evaluating the effectiveness of fault tolerance in replicated database management systems
11 Citations2003M. Sabaratnam, Øystein Torbjørnsen +1 more
This study evaluates the effectiveness of DBMS fault tolerance in the presence of corruption in database buffer cache, and identifies the weak data structure components in the data buffer cache that give fatal consequences when corrupted.
Apress eBooksAdvanced Transact-SQL for SQL Server 2000
10 Citations2000Itzik Ben-Gan, Tom Moreau
The authors offer practical solutions to the everyday problems programmers face and provide significant content on the advanced areas in T-SQL such as joins, subqueries, stored procedures, triggers, user-defined functions, indexed views, cascading actions, federated views, hierarchical structures, cursors and more.
Depression and AnxietyA Java Implementation of a Highly Available, Scalable and Distributed Data Structure, LH*g
6 Citations1997Ronny Lindberg
Results indicated that paternal (but not maternal) AS was associated with offspring AS and psychopathology.
Transmission Control Protocol (TCP) Specification
4 Citations1998Wesley M. Eddy
Elsevier eBooksRSLHA Highly Available Distributed Data Storage
4 Citations2004Witold Litwin, Rim Moussa +1 more
UrologyPerformance of the SDDS LH* LH under SDDS-2000.
3 Citations2002Fethi Bennour Sahli
The incidence of isolated HGPIN on prostate needle core biopsies in Asian men, as well as the likelihood of subsequent cancer detection, are comparable to the rates reported for Western populations.