Cross-Rack Update Bandwidth for Rack-Aware Storage Systems

Rack-aware storage systems organize the storage nodes in racks such that the cross-rack communication cost is much more expensive than the intra-rack communication cost. In this paper, we primarily investigate the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks during an update process of one single node. It is critical to design erasure codes that minimize the cross-rack update bandwidth. Our main contributions are as follows. First, we establish the model of cross-rack update bandwidth of irregular array codes over rack-aware storage systems. Second, we derive the tight lower bound on cross-rack update bandwidth, and define minimum cross-rack update bandwidth (MCUB) codes as the irregular array codes that can achieve our tight lower bound. Third, we derive the tight lower bound on redundancy defined as the total number of parity symbols for MCUB codes, and define minimum redundancy MCUB (MR-MCUB) codes as the MCUB codes that can achieve the redundancy lower bound. Fourth, we present explicit constructions of MR-MCUB codes that achieve both the minimum cross-rack update bandwidth and the minimum redundancy, which means that the two lower bounds are tight. Last, we define intra-rack update bandwidth as the average amount of symbols incurred within one rack in an update process, and derive the lower bound of intra-rack update bandwidth of MCUB codes. Moreover, we show that our MCUB codes constructions can also achieve the lower bound of intra-rack update bandwidth.