# US 2019/0317860 A1 · Erasure coding for a single-image memory

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

- Number: US 2019/0317860 A1
- Document ID: US20190317860A1
- Status: Published application
- Kind: A1
- Application number: 16/013,718
- Filed: 2018-06-20
- Published: 2019-10-17
- Earliest claimed: 2018-04-16
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Edmund B. NIGHTINGALE
- Web page: https://patentgrep.com/patent/US20190317860A1

## CPC

- G06F 11/108: {Parity data distribution in semiconductor storages, e.g. in SSD}
- G06F 11/1088: {Reconstruction on already foreseen single or plurality of spare disks}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/0665: {at area level, e.g. provisioning of virtual or logical volumes}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- G06F 11/1004: {to protect a block of data words, e.g. CRC or checksum (G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00)}
- G06F 2211/1028: Distributed, i.e. distributed RAID systems with parity
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Erasure code for data is generated by: calculating the size and bytes of an erasure code block, calculating a number of stripes for the erasure code, and generating each stripe of each block for the erasure code, such that the stripes alternate in a pattern for each block, and saving hashes. A portion of the data is repaired by: for each block of the portion of the data, calculating the stripe of the block, identifying each hash for which the hash of the block of the portion of data does not match the saved hash of the block as a bad block, and for each identified bad block, generating a repair block for the bad block based on the stripe of the block and corresponding block of the data in the erasure coding for the data.

## Claims

### Claim 1

An apparatus, comprising:
a device including at least one memory adapted to store run-time data for the device, and at least one processor that is adapted to execute processor-executable code that, in response to execution, enables the device to perform actions, including:
generating erasure code for data by:
calculating the size and bytes of the erasure code;
calculating a number of stripes for the erasure code;
generating each stripe of each block for the erasure code, such that the stripes alternate in a pattern; and
saving a hash of each block of the data; and
repairing at least a portion of the data by:
for each block of the portion of the data, calculating the stripe of the block;
checking the hash of each block of the portion of data against the saved hash of the block;
identifying each hash for which the hash of the block of the portion of data does not match the saved hash of the block as a bad block; and
for each identified bad block, generating a repair block for the bad block based on the stripe of the block and corresponding block of the data in the erasure code for the data.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein data is within a region is divided into stripes, where each stripe is composed of blocks that are interlaced with blocks from other stripes.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein saving the hash of each block of the data is accomplished by saving the hash of each block of the data in a block hash partition that is separate from the data.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the stripes are of equal fixed size.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the stripes are of equal fixed size plus one partial stripe of less than the fixed size.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein generating the repair block for the bad block based on: the stripe of the block and corresponding block of the data in the erasure coding for the data includes stitching the stripe together based on calculated offsets, and applying an erasure coding algorithm to the stitched-together stripe.

### Claim 7 (depends on 1)

The apparatus of claim 1, the actions further including:
updating the erasure code responsive to a change in the data.

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein updating the erasure code includes:
receiving a range in the data that has changed;
determining which blocks in the range of data have changed; and
regenerating the erasure code for each block in the range of data determined to have changed.

### Claim 9 (depends on 8)

The apparatus of claim 8, wherein determining which blocks in the range have changed is accomplished by, for each block in the range of data, calculating a hash of the block, and comparing the calculated hash with the stored hash for the block.

### Claim 10

A method, comprising:
via at least one processor, generating erasure code for data, including generating each stripe of each block for the erasure code, such that the stripes alternate in a pattern; and
repairing at least a portion of the data.

### Claim 11 (depends on 10)

The method of claim 10, wherein generating the erasure code further includes:
calculating the size and bytes of the erasure code;
calculating a number of stripes for the erasure code; and
saving a hash of each block of the data.

### Claim 12 (depends on 10)

The method of claim 10, wherein repairing the portion of the data includes:
for each block of the portion of the data, calculating the stripe of the block;
checking the hash of each block of the portion of data against the saved hash of the block;
identifying each hash for which the hash of the block of the portion of data does not match the saved hash of the block as a bad block; and
for each identified bad block, generating a repair block for the bad block based on the stripe of the block and corresponding block of the data in the erasure coding for the data.

### Claim 13 (depends on 10)

The method of claim 10, the further comprising:
updating the erasure code responsive to a change in the data.

### Claim 14 (depends on 13)

The method of claim 13, wherein updating the erasure code includes:
receiving a range in the data that has changed;
determining which blocks in the range of data have changed; and
regenerating the erasure code for each block in the range of data determined to have changed.

### Claim 15

A processor-readable storage medium, having stored thereon process-executable code that, upon execution by at least one processor, enables actions, comprising:
generating erasure code for data by:
calculating the size and bytes of the erasure code;
calculating a number of stripes for the erasure code; and
calculating each stripe of each block for the erasure code, such that the stripes alternate in a pattern.

### Claim 16 (depends on 15)

The processor-readable storage medium of claim 15, wherein generating the erasure code data further includes saving a hash of each block of the data.

### Claim 17 (depends on 15)

The processor-readable storage medium of claim 15, the actions further comprising repairing a portion of the data.

### Claim 18 (depends on 17)

The processor-readable storage medium of claim 17, wherein repairing the portion of the data includes:
for each block of the portion of the data, calculating the stripe of the block;
checking the hash of each block of the portion of data against the saved hash of the block;
identifying each hash for which the hash of the block of the portion of data does not match the saved hash of the block as a bad block; and
for each identified bad block, generating a repair block for the bad block based on the stripe of the block and corresponding block of the data in the erasure code for the data.

### Claim 19 (depends on 15)

The processor-readable storage medium of claim 15, the actions further comprising:
updating the erasure code responsive to a change in the data.

### Claim 20 (depends on 19)

The processor-readable storage medium of claim 19, wherein updating the erasure code includes:
receiving a range in the data that has changed;
determining which blocks in the range of data have changed; and
regenerating the erasure code for each block in the range of data determined to have changed.