Computing Reviews

LH*RS--a highly-available scalable distributed data structure
Litwin W., Moussa R., Schwarz T. ACM Transactions on Database Systems30(3):769-811,2005.Type:Article
Date Reviewed: 01/19/06

This paper continues the authors’ research on scalable distributed data structures. In this work, the authors focus their attention on data availability, and extend their previous proposal, LH*, to provide high availability. An LH* server can be unavailable, in which case access to data becomes impossible; this may not be acceptable for an application.

The paper considers two issues: algorithm performance and high availability. On one side, the proposal applies Reed-Solomon codes with a Galois field (GF) (216) for parity calculus. It refines the parity matrix, and introduces the concept of a generic parity matrix. The authors also implement the GF multiplication using logarithms and antilogarithms. In addition, they pay special attention to the efficiency of the communication architecture. Such considerations support improving the performance of the algorithm. On the other side, the paper proposes the use of parity records, which are invisible to applications, and provide high availability for the application. The architecture considers a set of LH*RS servers that are contacted by the application only through the LH*RS clients. Such clients are localized in the application node. Clients are responsible for data search or storage over the network. Applications ask the clients for data.

There is another important component in the architecture: the coordinator. The paper describes the operation of such a coordinator to provide high-availability updating, insertion, and deletion of data in the system, and bucket split and merging. The paper also describes how the coordinator performs the above operations to derive recovery responsibilities for the LH*RS clients and servers; this avoids the coordinator being a hot spot in the system. According to paper, the coordinator is k-replicated. However, the resolution of coordinator failure is not clearly explained.

The paper provides some interesting evaluations of the proposal, which support the conclusion that the authors have proposed a new highly available scalable distributed data structure that can be applied in current systems (including peer-to-peer networks, replication systems, and databases).

Reviewer:  Jesus Villadangos-Alonso Review #: CR132323 (0608-0843)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy