Repair rate lower bounds for distributed storage
share
One of the primary objectives of a distributed storage system is to reliably store a large amount dsize of source data for a long duration using a large number N of unreliable storage nodes, each with capacity nsize. The storage overhead β is the fraction of system capacity available beyond dsize, i.e., β = 1- dsize/N · nsize. Storage nodes fail randomly over time and are replaced with initially empty nodes, and thus data is erased from the system at an average rate erate = λ· N · nsize, where 1/λ is the average lifetime of a node before failure. To maintain recoverability of the source data, a repairer continually reads data over a network from nodes at some average rate rrate, and generates and writes data to nodes based on the read data. The main result is that, for any repairer, if the source data is recoverable at each point in time then it must be the case that rrate >erate/2 ·β asymptotically as N goes to infinity and beta goes to zero. This inequality provides a fundamental lower bound on the average rate that any repairer needs to read data from the system in order to maintain recoverability of the source data.
READ FULL TEXT