LH*g: a high-availability scalable distributed data structure by record grouping

LH*g (Linear Hashing by grouping) is a high-availability extension of the LH* scalable distributed data structure. An LH*g file scales up with constant key search and insert performance, while surviving any single-site unavailability (failure). We achieve high availability through a new principle of record grouping. A group is a logical structure of up to k records, where k is a file parameter. Every group contains a parity record allowing for the reconstruction of an unavailable member. The basic scheme may be generalized to support the unavailability of any number of sites, at the expense of storage and messaging. Other known high-availability schemes are static, or require more storage, or provide worse search performance