# US 10,503,611 B1 · Data protection management for distributed storage

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,503,611 B1
- Document ID: US10503611B1
- Status: Granted
- Kind: B1
- Application number: 15/390,415
- Filed: 2016-12-23
- Granted: 2019-12-10
- Earliest claimed: 2016-12-23
- Assignees: EMC IP Holding Company LLC
- Applicants: EMC IP Holding Company LLC
- Inventors: Shashwat Srivastav; Mikhail Danilov; Sriram Sankaran; Jun Luo; Subba R. Gaddamadugu; Peter M. Musial; Andrew D. Robertson; Chen Wang
- Web page: https://patentgrep.com/patent/US10503611B1

## CPC

- G06F 11/1469: {Backup restoration techniques}
- H03M 13/1515: {Reed-Solomon codes}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/065: {Replication mechanisms}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- G06F 11/1451: {by selection of backup contents}
- G06F 11/1464: {for networked environments}
- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes}
- G06F 2201/805: Real-time
- G06F 2201/82: Solving problems relating to consistency
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

An efficient and scalable method of managing data protection in a geographically distributed storage system is provided using erasure coding. Each zone in the geographically distributed storage system of multiple zones or clusters encodes primary backup chunks replicated from original data chunks in remote zones to create coding chunks. The zone retains one of the coding chunks and distributes the remaining coding chunks to remote zones for future recovery from dual and more complex failures. Upon completion, the primary backup chunks and peer backup chunks can safely be deleted to reduce overhead. Encoding k primary backup chunks to create m coding chunks, and distributing the m coding chunks to different remote zones assures recovery from 1 to m zone/cluster/chunk failures. After 1 to m zone failures the unaffected zones are each able to recover all of the unavailable chunks by retrieving from each other any of the unaffected zone's distributed coding chunks and still available original data chunks, and restoring the content of the unavailable chunks by decoding the combination of the retained coding chunk, distributed coding chunk, and any still available original data chunks.

## Claims

### Claim 1

A computer-executable method of managing data protection in a distributed storage system, the method comprising:
configuring a distributed storage system into a plurality of at least k+m zones in which each zone accumulates k equal-sized primary backup chunks and one or more peer backup chunks of original data chunks replicated from different remote zones; and
preparing the distributed storage system for recovery from a failure of 1 to m zones of the plurality of the at least k+m zones by performing the operations of:
encoding, at each zone of the plurality of at least k+m zones, the k equal-sized primary backup chunks to create m equalized-sized redundant coding chunks using an erasure coding such that the distributed storage system has at least k+m chunks of data,
retaining one of the m coding chunks in that zone of the plurality of at least k+m zones,
distributing each of the remaining m−1 coding chunks to a different one of the remaining m−1 zones, and
deleting each of k equal-sized primary backup chunks and the one or more peer backup chunks in that zone of plurality of at least k+m zones to reduce storage overhead.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
recovering unavailable chunks from a failure of 1 to m zones including performing, in each of the zones unaffected by the failure, any one or more of:
identifying any of still available coding chunks created and retained by the zone, and
retrieving any of the still available coding chunks distributed to the zone from another zone, and
creating local copies of any of the still available original data chunks from which the still available coding chunks were created; and
reconstructing as many unavailable chunks as possible from the still available coding chunks and the still available original data chunks.

### Claim 3 (depends on 1)

The method of claim 1, wherein the plurality of at least k+m zones into which the distributed storage system is configured is distributed across a geographical area.

### Claim 4 (depends on 1)

The method of claim 1, wherein the distributed storage system is a cloud-based storage system accessible over an inter-network.

### Claim 5 (depends on 1)

The method of claim 1, wherein each of the m coding chunks are equal-sized and belong to a set of blocks of data stored in a partitioned disk space.

### Claim 6 (depends on 1)

The method of claim 1, wherein an index layer maps one or more file-names to data stored within the distributed data storage system, and wherein the index layer is to manage secondary indices used to manage the data stored on the distributed data storage system.

### Claim 7

A distributed storage system comprising:
a cluster of nodes in communication with one or more data storage arrays and a storage engine, each node having a processor configured to execute an application, the storage engine enabling the application to process data I/O requests to and from the one or more data storage arrays, the processor further configured to:
configure the cluster of nodes into a plurality of k+m zones in which each zone manages data stored in the one or more data storage arrays, the data including k equal-sized primary backup chunks and one or more peer backup chunks of original data chunks replicated from different remote zones; and
prepare the cluster of nodes for recovery from a failure of any one or more zones in the plurality of zones, including causing each zone in the plurality of zones to:
encode the equal-sized primary backup chunks to create m coding chunks using erasure coding such that the distributed storage system has at least k+m chunks of data,
retain one of the m coding chunks in the zone,
distribute each of the other m−1 coding chunks not retained to different zones in the plurality of zones, and
delete any primary backup chunks and any peer backup chunks from the zone to reduce storage overhead.

### Claim 8 (depends on 7)

The distributed storage system of claim 7, the processor further configured to:
detect the failure of the any one or more zones in the plurality of zones;
recover from the failure, including causing an unaffected zone unaffected by the failure to:
retrieve from other unaffected zones any of the still available coding chunks;
create local copies of any of still available original data chunks from which the coding chunks were created; and
reconstruct any unavailable chunks from the still available coding chunks and the still available original data chunks.

### Claim 9 (depends on 7)

The distributed storage system of claim 7, wherein the plurality of zones into which the cluster of nodes is configured is distributed across a geographical area.

### Claim 10 (depends on 7)

The distributed storage system of claim 7, wherein the plurality of zones into which the cluster of nodes is configured is a cloud-based storage system accessible over an inter-network.

### Claim 11 (depends on 7)

The distributed storage system of claim 7, wherein the erasure coding used to encode the primary backup chunks into coding chunks is bit matrix erasure coding.

### Claim 12 (depends on 7)

The system of claim 7, wherein each of the m coding chunks are equal-sized and belong to a set of blocks of data stored in a partitioned disk space.

### Claim 13 (depends on 7)

The system of claim 7, wherein an index layer maps one or more file-names to data stored within the distributed data storage system, and wherein the index layer is to manage secondary indices used to manage the data stored on the distributed data storage system.

### Claim 14

A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for data protection management in a distributed storage system, the operations comprising:
configuring a cluster of nodes into a plurality of k+m zones in which each zone manages data stored in the one or more data storage arrays, the data including k equal-sized primary backup chunks and one or more peer backup chunks of original data chunks replicated from different remote zones; and
preparing the cluster of nodes for recovery from a failure of any one or more zones in the plurality of zones, including causing each zone in the plurality of zones to:
encode the k equal-sized primary backup chunks to create in coding chunks using erasure coding,
retain one of the m coding chunks in the zone,
distribute each of the other m−1 coding chunks not retained to different zones in the plurality of zones, and
delete any primary backup chunks from which coding chunks were created and any peer backup chunks from the zone to reduce storage overhead.

### Claim 15 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, the operations further comprising:
detecting the failure of the any one or more zones in the plurality of zones; and
recovering from the failure, including causing an unaffected zone unaffected by the failure to:
retrieve from other unaffected zones any of still available coding chunks,
create local copies of any of the still available original data chunks, from which the still available coding chunks were created and
reconstruct any unavailable chunks from the still available coding chunks and the still available original data chunks.

### Claim 16 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein the erasure coding used to encode the primary backup chunks to create coding chunks is bit matrix erasure coding.

### Claim 17 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein:
the plurality of zones into which the cluster is configured is at least k+m zones;
the any one or more zones in the plurality of the at least k+m zones from which the cluster of nodes can recover is from 1 to m zones of the plurality of the at least k+m zones; and
the erasure coding used to encode primary backup chunks to create coding chunks is a bit matrix encoding function having parameters k+m, in which k primary backup chunks are encoded to create m coding chunks.

### Claim 18 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, each of the m coding chunks are equal-sized and belong to a set of blocks of data stored in a partitioned disk space.

### Claim 19 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein an index layer maps one or more file-names to data stored within the distributed data storage system, and wherein the index layer is to manage secondary indices used to manage the data stored on the distributed data storage.