Exact-repair regenerating codes for distributed storage system

Applications

• Distributed storage systems
• Data servers
• Peer-to-peer networks
• Cloud computing

Key Benefits & Differentiators

• Efficient node regeneration in large DSS
• Optimal storage and repair bandwidth; MBR and MSR are possible solutions
• Small field size
• Scalable

Problem

Distributed Storage System (DSS), a technology used by data-intensive technologies such as cloud computing, consists of a large number of inexpensive storage devices that are prone to failures. Modern DSSs are equipped with a repair procedure to ensure continued operation and reproduce the data lost due to such node failures. Regenerating codes are a class of codes used in this procedure to reduce the amount of download during repair, while maintaining maximum storage efficiency. Currently, regenerating codes require a tradeoff between the storage space and the amount of download needed for repair. Particularly, existing codes operate in one of two extreme points in this tradeoff: minimum storage regenerating (MSR) points and minimum bandwidth regenerating (MBR) points, and a universal optimal regenerating scheme is needed.

Solution

Researchers at the University of Minnesota have developed a novel regenerating coding scheme that can optimally trade between the required disk storage and the repair communication bandwidth for any (n, d, k)* DSS system. This coding scheme can be used to develop exact-repair regenerating codes for the entire trade-off, including the Minimum Storage Regeneration (MSR) and Minimum Bandwidth Regeneration (MBR) points. This regenerating cascade code has a linear structure; hence, the code can be obtained by multiplying the data message matrix by an encoder matrix. The signed determinant codes, are used as the main building blocks of these codes. In these codes parameters of the code are decoupled, meaning that the encoder matrix depends solely on n and d and the data message matrix depends solely on d and the storage size which remains the same for all nodes. All the data symbols can be recovered from the content of any k = d nodes. In addition, the trade-off achieved using this code is independent of n; therefore, despite the growing number of constraints with the number of codes, the storage capacity is not decreased. Moreover, this code requires a small field size, in order of the number of nodes n. Finally, this code is scalable - appending new nodes to an existing system, without changing neither the content nor the repair data of the existing nodes is possible, provided that the total number of nodes does not exceed the underlying field size.

*n = total number of storage nodes, k = number of nodes suffice for data recovery, d = number of helper nodes in a repair process.

Phase of Development

Theoretical construction and proof of concept is completed. Simulation and testing on encoding/decoding of the data is ongoing.

This technology is now available for license! The University is excited to partner with industry to see this innovation reach its potential. Please contact us to share your business’ needs and your licensing interests in this technology. The license is for the sale, manufacture or use of products claimed by the patents.