TY - JOUR
T1 - Evaluating load balancing performance in distributed storage with redundancy
AU - Aktas, Mehmet Fatih
AU - Far, Amir Behruzi
AU - Soljanin, Emina
AU - Whiting, Philip
PY - 2021/6
Y1 - 2021/6
N2 - To facilitate load balancing, distributed systems store data redundantly. We evaluate the load balancing performance of storage schemes in which each object is stored at d different nodes, and each node stores the same number of objects. In our model, the load offered for the objects is sampled uniformly at random from all the load vectors with a fixed cumulative value. We find that the load balance in a system of n nodes improves multiplicatively with d as long as d =o (log (n)) , and improves exponentially once d = Θ (log (n)). We show that the load balance improves in the same way with d when the service choices are created with XOR's of r objects rather than object replicas. In such redundancy schemes, storage overhead is reduced multiplicatively by r. However, recovery of an object requires downloading content from r nodes. At the same time, the load balance increases additively by r. We express the system's load balance in terms of the maximal spacing or maximum of d consecutive spacings between the ordered statistics of uniform random variables. Using this connection and the limit results on the maximal d -spacings, we derive our main results.
AB - To facilitate load balancing, distributed systems store data redundantly. We evaluate the load balancing performance of storage schemes in which each object is stored at d different nodes, and each node stores the same number of objects. In our model, the load offered for the objects is sampled uniformly at random from all the load vectors with a fixed cumulative value. We find that the load balance in a system of n nodes improves multiplicatively with d as long as d =o (log (n)) , and improves exponentially once d = Θ (log (n)). We show that the load balance improves in the same way with d when the service choices are created with XOR's of r objects rather than object replicas. In such redundancy schemes, storage overhead is reduced multiplicatively by r. However, recovery of an object requires downloading content from r nodes. At the same time, the load balance increases additively by r. We express the system's load balance in terms of the maximal spacing or maximum of d consecutive spacings between the ordered statistics of uniform random variables. Using this connection and the limit results on the maximal d -spacings, we derive our main results.
UR - http://www.scopus.com/inward/record.url?scp=85100505488&partnerID=8YFLogxK
U2 - 10.1109/TIT.2021.3054385
DO - 10.1109/TIT.2021.3054385
M3 - Article
AN - SCOPUS:85100505488
SN - 0018-9448
VL - 67
SP - 3623
EP - 3644
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 6
ER -