# US 2021/0342225 A1 · Data Reconstruction in Distributed Storage Systems

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

- Number: US 2021/0342225 A1
- Document ID: US20210342225A1
- Status: Published application
- Kind: A1
- Application number: 17/305,610
- Filed: 2021-07-12
- Published: 2021-11-04
- Earliest claimed: 2014-02-25
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Lidor Carmi; Christian Eric Schrock; Steven Robert Schirripa
- Web page: https://patentgrep.com/patent/US20210342225A1

## CPC

- G06F 11/0763: {by bit configuration check, e.g. of formats or tags}
- G06F 11/1402: {Saving, restoring, recovering or retrying}
- G06F 11/1469: {Backup restoration techniques}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method of operating a distributed storage system, the method includes identifying missing chunks of a file. The file is divided into stripes that include data chunks and non-data chunks. The method also includes identifying non-missing chunks available for reconstructing the missing chunks and reconstructing missing data chunks before reconstructing missing non-data chunks using the available non-missing chunks.

## Claims

### Claim 1

A computer-implemented method when executed by data processing hardware causes the data processing hardware to perform operations comprising:
receiving a file for storage at a distributed storage system;
dividing the file into chunks comprising data chunks and non-data chunks;
distributing the chunks comprising the data chunks and the non-data chunks on multiple storage devices of the distributed storage system;
after distributing the chunks, scanning the distributed chunks to identify any damaged chunks; and
in response to identifying damaged chunks, automatically reconstructing the damaged chunks using non-damaged chunks.

### Claim 2 (depends on 1)

The method of claim 1, wherein automatically reconstructing the damaged chunks comprises:
identifying non-damaged chunks available for reconstructing the damaged chunks; and
reconstructing damaged data chunks before reconstructing damaged non-data chunks using the non-damaged chunks.

### Claim 3 (depends on 1)

The method of claim 1, wherein the operations further comprise:
determining a number of damaged chunks to reconstruct per recovery cycle of the distributed storage system as a minimum of the number of damaged chunks and a maximum number of chunks allowed for reconstruction per recovery cycle; and
selecting damaged data chunks preferentially over damaged non-data chunks for reconstruction during each recovery cycle.

### Claim 4 (depends on 1)

The method of claim 1, wherein the operations further comprise randomly selecting damaged data chunks for reconstruction from the damaged chunks.

### Claim 5 (depends on 1)

The method of claim 1, wherein the non-data chunks comprise code-check chunks, word-check chunks, and code-check-word-check chunks.

### Claim 6 (depends on 5)

The method of claim 5, wherein automatically reconstructing the damaged chunks using the other distributed chunks further comprises:
reconstructing damaged data chunks of the damaged chunks:
after reconstructing the damaged data chunks, reconstructing damaged code-check chunks of the damaged chunks; and
after reconstructing the damaged code-check chunks, reconstructing damaged word-check chunks and damaged code-check-word-check chunks.

### Claim 7 (depends on 5)

The method of claim 5, wherein automatically reconstructing the damaged chunks using the other distributed chunks further comprises:
reconstructing damaged data chunks and damaged word-check chunks;
after reconstructing damaged data chunks and the damaged word-check chunks, reconstructing damaged code-check chunks; and
after reconstructing damaged code-check chunks, reconstructing damaged code-check-word-check chunks.

### Claim 8 (depends on 5)

The method of claim 5, wherein automatically reconstructing the damaged chunks using the other distributed chunks further comprises:
reconstructing damaged data chunks capable of being reconstructed from other data chunks and/or code-check chunks only; and then
reconstructing damaged data chunks capable of being reconstructed from other non-missing chunks.

### Claim 9 (depends on 8)

The method of claim 8, wherein reconstructing missing data chunks capable of being reconstructed from other data chunks and/or code-check chunks only and reconstructing missing data chunks capable of being reconstructed from other non-missing chunks each comprises:
reconstructing multiple data chunks on a server during a recovery cycle; and
moving the reconstructed data chunks, except one data chunk, to other servers.

### Claim 10 (depends on 9)

The method of claim 9, wherein the operations further comprise identifying multiple chunks associated with the same code-check chunk for reconstruction during the recovery cycle.

### Claim 11

A system comprising:
data processing hardware; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
receiving a file for storage at a distributed storage system;
dividing the file into multiple chunks comprising data chunks and non-data chunks;
distributing the chunks comprising the data chunks and the non-data chunks on multiple storage devices of the distributed storage system;
after distributing the chunks, scanning the distributed chunks to identify any damaged chunks; and
in response to identifying damaged chunks, automatically reconstructing the damaged chunks using non-damaged chunks.

### Claim 12 (depends on 11)

The system of claim 11, wherein automatically reconstructing the damaged chunks comprises:
identifying non-damaged chunks available for reconstructing the damaged chunks; and
reconstructing damaged data chunks before reconstructing damaged non-data chunks using the non-damaged chunks.

### Claim 13 (depends on 11)

The system of claim 11, wherein the operations further comprise:
determining a number of damaged chunks to reconstruct per recovery cycle of the distributed storage system as a minimum of the number of damaged chunks and a maximum number of chunks allowed for reconstruction per recovery cycle; and
selecting damaged data chunks preferentially over damaged non-data chunks for reconstruction during each recovery cycle.

### Claim 14 (depends on 11)

The system of claim 11, wherein the operations further comprise randomly selecting damaged data chunks for reconstruction from the damaged chunks.

### Claim 15 (depends on 11)

The system of claim 11, wherein the non-data chunks comprise code-check chunks, word-check chunks, and code-check-word-check chunks.

### Claim 16 (depends on 15)

The system of claim 15, wherein automatically reconstructing the damaged chunks using the other distributed chunks further comprises:
reconstructing damaged data chunks of the damaged chunks:
after reconstructing the damaged data chunks, reconstructing damaged code-check chunks of the damaged chunks; and
after reconstructing the damaged code-check chunks, reconstructing damaged word-check chunks and damaged code-check-word-check chunks.

### Claim 17 (depends on 15)

The system of claim 15, wherein automatically reconstructing the damaged chunks using the other distributed chunks further comprises:
reconstructing damaged data chunks and damaged word-check chunks;
after reconstructing damaged data chunks and the damaged word-check chunks, reconstructing damaged code-check chunks; and
after reconstructing damaged code-check chunks, reconstructing damaged code-check-word-check chunks.

### Claim 18 (depends on 15)

The system of claim 15, wherein automatically reconstructing the damaged chunks using the other distributed chunks further comprises:
reconstructing damaged data chunks capable of being reconstructed from other data chunks and/or code-check chunks only; and then
reconstructing damaged data chunks capable of being reconstructed from other non-missing chunks.

### Claim 19 (depends on 18)

The system of claim 18, wherein reconstructing missing data chunks capable of being reconstructed from other data chunks and/or code-check chunks only and reconstructing missing data chunks capable of being reconstructed from other non-missing chunks each comprises:
reconstructing multiple data chunks on a server during a recovery cycle; and
moving the reconstructed data chunks, except one data chunk, to other servers.

### Claim 20 (depends on 19)

The system of claim 19, wherein the operations further comprise identifying multiple chunks associated with the same code-check chunk for reconstruction during the recovery cycle.
