Update Bandwidth For Distributed Storage

In this paper,our research object is the update process of an erasure-codes-based distributed storage system.Specifically,we consider that when a node is updated,the node needs to transmit some symbols to other nodes via the network,then other nodes update the internal symbols that need to be updated accordingly via some calculation on the received symbols.Furthermore,we pay more attention to the transmission effi-ciency of this process,that is,the size of the network bandwidth occupied by the up-date process.As such,we propose a brand new measurement called update bandwidth,which is defined as the average amount of data symbols transferred in the network when the data symbols stored in a node are updated.In addition,in order to ensure that better update bandwidth will not affect other important requirements of the distributed stor-age system,such as storage efficiency,repair efficiency,and I/O efficiency during the update process,we have studied the relationship among update bandwidth,and the ex-isting three important metrics including code redundancy,update complexity and repair bandwidth.To conclude,this paper has the following contributions.1.For the most general array codes referred to as irregular array codes,we establish a closed-form expression of the minimum update bandwidth that the irregular array code can achieve subject to a certain node repair ability.Also,We attain the sufficient and necessary condition of code parameters of irregular array codes to achieve the minimum update bandwidth.2.In order to characterize the relationship between update bandwidth and redun-dancy,we define a family of irregular array code with the minimum update band-width,called the Minimum Update Bandwidth(MUB)code,and derive the min-imum code redundancy required by any MUB codes,that is,the minimum redun-dancy required by the irregular array code subject to minimum update bandwidth.In order to distinguish from the minimum code redundancy required by the irregu-lar array codes,we call the minimum redundancy that the MUB code can achieve as smallest redundancy.3.By comparing the smallest redundancy of the MUB code with the minimum code redundancy of the irregular array code,we find that these two parameters are equal only in some special cases.Therefore,we further define a special family of MUB codes as irregular array codes with minimum update bandwidth and mini-mum code redundancy at the same time,called Minimum Redundancy Minimum Update Bandwidth(MR-MUB)codes.In addition,we establish the necessary condition of code parameters that an MR-MUB code should satisfy.4.We constructed MR-MUB codes and MUB codes with smallest code redundancy to show that such codes really exist,and to show that the lower bounds of update bandwidth and redundancy we have obtained are accurate and achievable.5.In order to characterize the relationship between update bandwidth and update complexity,we establish the lower bound of the update complexity that the MR-MUB code can achieve,and this lower bound is strictly greater than the definition-implied minimum update complexity of the irregular array codes.This shows that the minimum redundancy,minimum update bandwidth and minimum update complexity cannot be achieved at the same time.6.In order to characterize the relationship between update bandwidth and repair bandwidth,we construct a family of(n=k+2,k)vertical maximum distance separable(MDS)array code.First,it can be proved that this code is an MR-MUB code,and secondly,it can be proved that it has the optimal repair bandwidth.It shows that under the special condition of n-k=2,the minimum redundancy of the irregular array code,the minimum update bandwidth and the optimal repair bandwidth can be achieved at the same time.