Data centres that provide an easily accessible store of data are a necessary resource for many entities. The amount of data stored in a data centre may be in the order of multiple petabytes. It is normal for a data centre to be built from a plurality of separate data storage units to provide a data centre with expandable capacity and so that different parts of the data storage centre can be maintained independently. All, or part of, each of these data storage units may occasionally be offline due to a failure occurring or the data storage unit deliberately being taken offline for maintenance. The data is therefore preferably stored in such a way that it is still accessible when any of the data storage units for storing the data are offline. A known technique is to store the data in a replicated manner. That is to say, the same data stored in a data storage unit is also stored in one or more other, separate, data storage units. This approach allows fast retrieval of data from a back-up data storage unit if one of the primary data storage units is offline.
A problem with storing data in a replicated manner is that the demand on data storage capacity is greatly increased and this increases costs. To solve this problem, it is known to use erasure codes for data storage. Using erasure codes for data storage requires additional processing to reconstruct unavailable data. However, the data storage requirements are a lot lower than those of replication systems. Reed-Solomon codes are well known error correcting codes that can be used as erasure codes for data storage. For a systematic implementation of a Reed-Solomon code as an erasure code, data is coded into a plurality of source data nodes, k, and a plurality of redundant data nodes, r, the total number of data nodes, n, being k+r. The source and redundant data nodes may be stored in a plurality of different data storage units, the data storage units each storing one or more data nodes. Due to the reconstruction properties of Reed-Solomon codes, if any r of the n data nodes are unavailable due to their data storage unit being offline, then the r data nodes can still be obtained through processing performed on a plurality of the other data nodes.
A number of other coding techniques than Reed-Solomon are suitable for such data reconstructions. If the coding technique has the capability that any k nodes are able to reconstruct all of the source data nodes, the coding technique is Maximum Distance Separable, MDS. If the number of data nodes that are required to reconstruct a node is d, then for standard Reed-Solomon d=k.
It is highly preferable for the stored data to be coded systematically. This allows stored source data to be read directly from a data storage unit, without any processing being required to reconstruct the source data, if the data storage unit storing the source data is online.
There are known problems with using coded data for data storage as described above. For each data node that needs to be reconstructed, it is necessary to perform k read operations to obtain other data nodes and then processing operations to reconstruct the data nodes. The large number of read operations causes the data node reconstruction process to be slow and also results in a large increase in data traffic within the storage system.
An attempt to reduce the above-described problems of erasure codes is disclosed in the paper ‘A “Hitchhiker's” Guide to Fast and Efficient Data Reconstruction in Erasure-coded Data Centres’ by K. V. Rashimi et al, SIGCOMM 2014, Computer Communication Review, August 2014. In this paper a coding technique is disclosed that is motivated by a ‘piggy backing’ technique. The redundant data packets of two separate systematically coded sets of data packets are effectively combined with each other in a manner that reduces the necessary number of data reads. A first set of systematically coded data packets is generated using Reed-Solomon. A second set of systematically coded data packets is separately generated using Reed-Solomon. Each of the source data packets in the first set of data packets is respectively associated with source data packets in the second set of coded data packets and each of the redundant data packets in the first set of data packets is respectively associated with a redundant data packet in the second set of coded data packets. Each pair of associated data packets of the sets of coded data packets is stored together in the same data storage unit. The pairs of associated data packets are each stored in different data storage units. Accordingly, each data storage unit stores a pair of data packets, one from each set of coded data packets. The data packet form the first set of coded data packets is stored in a first sub-stripe of the data storage unit and the data packet form the second set of coded data packets is stored in a second sub-stripe of the same data storage unit, the first and second sub-stripes preferably not being contiguous. The paper provides results that demonstrate that the techniques for generating redundant data packets disclosed therein reduce the number of data read operations required from if the data had been coded using Reed-Solomon.
Other techniques for coding data for storage in a data centre exist that all aim to reduce the amount of read data from what is necessary with standard Reed-Solomon coding. The coding techniques differ in how effective they are at improving on Reed-Solomon coding, the properties of the code that can be used (including the relative number of source and redundant data packets), the amount of processing required to generate the coded data and the amount of processing required to reconstruct source data from the coded data. For example, some coding techniques reduce the amount of data that needs to be read from that of Reed-Solomon but incur the drawback of it being necessary to store more data than if Reed-Solomon coding had been used. Other coding techniques do not allow the use of systematic codes and therefore incur the drawback of increasing the processing requirements.
There remains a need to improve on all known MDS coding techniques that have the advantageous properties of being systematic and not requiring a higher data storage capacity as standard Reed-Solomon.