Incremental updates of grid encoded data storage systems

Patent metadata

Field	Value
Publication number	US-10089176-B1
Application number	US-201514789810-A
Country	US
Kind code	B1
Filing date	Jul 1, 2015
Priority date	Jul 1, 2015
Publication date	Oct 2, 2018
Grant date	Oct 2, 2018

Abstract

Techniques for incrementally updating grid encoding data storage systems are described herein. A grid of shards with a plurality of virtual shards is created where each virtual shard is a representation of a shard in the grid of shards that is not backed by a data storage device and where each shard of the grid of shards has an index value. Data is then stored in the grid of shards by updating a shard to store the data and by also updating a second shard based on a set of shards with the same index value as the shard updated to store the data.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
generating a grid of shards, the grid of shards forming a partitioned data set, the grid of shards being indexed by row and column, the grid of shards comprising a set of data shards, a set of derived shards, and a set of shards containing a predetermined data value, the set of derived shards comprising a set of horizontally-derived shards and a set of vertically-derived shards, wherein:
the partitioned data set includes one or more shards containing one or more portions of the data set and one or more shards generated by applying an erasure code to the one or more shards containing the one or more portions of the data set; and
each shard of the grid of shards has a corresponding row and corresponding column and is configured such that:
the shard is reproducible from other shards associated with the row and reproducible from other shards associated with the column;
if the shard is a horizontally-derived shard of the set of horizontally-derived shards, the shard is derived based at least in part on a set of data shards associated with the row; and
if the shard is a vertically-derived shard of the set of vertically-derived shards, the shard is derived based at least in part on a set of shards associated with the column; and

storing a data object using the grid of shards by at least:
storing a copy of the data object in a storage device corresponding to a first shard of the grid of shards to produce an updated first shard, the updated first shard having a first corresponding row and a first corresponding column;
updating a second shard of the grid of shards based at least in part on a first set of shards of the grid of shards, the first set of shards including the updated first shard and one or more shards of the set of shards containing the predetermined data value, each shard of the first set of shards having a same corresponding row as the second shard;
updating a third shard of the grid of shards based at least in part on a second set of shards of the grid of shards, the second set of shards including the updated first shard and one or more shards of the set of shards containing the predetermined data value, each shard of the second set of shards having a same corresponding column as the third shard; and
updating a fourth shard of the grid of shards based at least in part on a third set of shards of the grid of shards, the third set of shards including the updated second shard and one or more shards of the set of shards containing the predetermined data value, each shard of the third set of shards having the same corresponding column as the fourth shard.

2. The computer-implemented method of claim 1 , wherein each shard of the set of shards containing the predetermined data value is a virtual shard specifying the predetermined data value without storing the predetermined data value in a data storage device.

3. The computer-implemented method of claim 1 , wherein:
each data shard of the grid of shards is pre-initialized to the predetermined data value;
each horizontally-derived shard of the grid of shards is pre-initialized to a first derived value, the first derived value derived based at least in part on applying a first linear redundancy code to one or more shards of the grid of shards;
each horizontally-derived shard is a virtual shard specifying the first derived value without storing the first derived value in a data storage device;
each vertically-derived shard of the grid of shards is pre-initialized to a second derived value, the second derived value derived based at least in part on applying a second linear redundancy code to one or more shards of the grid of shards; and
each vertically-derived shard is a virtual shard specifying the first derived value without storing the first derived value in a data storage device.

4. The computer-implemented method of claim 1 , wherein the predetermined data value is zero.

5. The computer-implemented method of claim 1 , wherein each shard of the grid of shards has a corresponding set of grid metadata, the set of grid metadata at least specifying the predetermined data value.

6. A system, comprising at least one computing device that implements one or more services, wherein the one or more services:
generate a grid of shards, the grid of shards at least indexed by a first index, the grid of shards including a plurality of virtual shards, each virtual shard of the plurality of virtual shards having at least a corresponding first index, each virtual shard of the plurality of virtual shards configured to represent a shard of the grid of shards without storage of shard data in a data storage device; and
store a data object in the grid of shards by at least:
storing a copy of the data object in a storage device corresponding to a first shard of the grid of shards to produce an updated first shard, the updated first shard having at least a first corresponding first index; and
updating a second shard of the grid of shards based at least in part on a first set of shards of the grid of shards, the first set of shards including the updated first shard and one or more first virtual shards, each shard of the first set of shards having a same corresponding first index as the second shard.

7. The system of claim 6 , wherein the one or more services that update the first shard:
select the first shard from the plurality of virtual shards;
convert the first shard to a non-virtual shard; and
store at least a portion of the data object in the non-virtual shard.

8. The system of claim 6 , wherein the one or more services that update the second shard:
select the second shard from the plurality of virtual shards;
convert the second shard to a non-virtual shard; and
update the non-virtual shard based at least in part on applying a redundancy code to a subset of the first set of shards.

9. The system of claim 6 , wherein the grid of shards includes a second set of shards that is a bundle-encoded set of shards, the second set of shards including the first set of shards and the second shard, the bundle-encoded set of shards based at least in part on a first redundancy code.

10. The system of claim 6 , wherein:
the grid of shards is further indexed by a second index;
each shard of the plurality of virtual shards has a corresponding second index; and
the first shard of the grid of shards has a first corresponding second index.

11. The system of claim 10 , wherein the one or more services:
update a third shard of the grid of shards based at least in part on a second set of shards of the grid of shards, the second set of shards including the updated first shard and one or more second virtual shards, each shard of the second set of shards having a same corresponding second index as the third shard; and
update a fourth shard of the grid of shards based at least in part on a third set of shards of the grid of shards, the third set of shards including the second shard and one or more third virtual shards, each shard of the third set of shards having the same corresponding second index as the fourth shard.

12. The system of claim 11 , wherein the one or more services that update the third shard:
select the third shard from the plurality of virtual shards;
convert the third shard to a non-virtual shard; and
update the non-virtual shard based at least in part on applying a redundancy code to a subset of the second set of shards.

13. The system of claim 11 , wherein the one or more services that update the fourth shard:
select the fourth shard from the plurality of virtual shards;
convert the fourth shard to a non-virtual shard; and

Assignees

• Amazon Tech Inc

Inventors

• Donlan Bryan James
• Franklin Paul David
• Kirschner James Caleb

Classifications

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M13/09

  Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit · CPC title

• H04L67/1095 Primary

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title