LH*RS---a highly-available scalable distributed data structure
Litwin, Witold; Moussa, Rim; Schwarz, Thomas (2005), LH*RS---a highly-available scalable distributed data structure, ACM Transactions on Database Systems, 30, 3, p. 769-811. http://dx.doi.org/10.1145/1093382.1093386
TypeArticle accepté pour publication ou publié
Journal nameACM Transactions on Database Systems
MetadataShow full item record
Abstract (EN)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.
Subjects / KeywordsScalable Distributed Data Structure; Linear Hashing; High-Availability; Physical Database Design; P2P; Grid Computing
Showing items related by title and author.