Distributed soft-state index management in BitVault — protocols and its correctness

In this paper, we report the design and implementation of the storage layer of BitVault: a content-addressable retention platform for large volume of reference data – seldom-changing information that needs to be retained for a long period of time. BitVault uses “smart brick” as the building block to lower the hardware cost. However, the challenges are to maintain low management cost in a system that needs to scale all the way from one brick to tens of thousands of bricks, to ensure reliability and to deliver with a simple enough design. Our design incorporates P2P technologies for its self-managing and self-healing capabilities and uses massively parallel repair to reduce vulnerability window of data loss. The simplicity of the architecture relies on an eventually reliable membership service provided by a perfect one-hop DHT (distributed hash table), and its object-driven repair model yields last-copy recall guarantee: independent of how many other failures that may occur and their sequences, as long as the last copy of a data object still remains in the system, the data can be retrieved and its replication degree fully restored. A prototype has been implemented. Theoretical analysis, simulations and experiments are conducted to validate the design of BitVault.