Incremental updates of grid encoded data storage systems

• US 10,089,176 B1
• Filed: 07/01/2015
• Issued: 10/02/2018
• Est. Priority Date: 07/01/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Donlan, Bryan James, Franklin, Paul David, Kirschner, James Caleb
• Primary Examiner(s): Lamarre, Guy
• Application Number:
  US14/789,810
• Time in Patent Office: 1,189 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/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]

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.

Claims

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

update the non-virtual shard based at least in part on applying a redundancy code to a subset of the third set of shards.

14. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of execution by one or more processors of a computer system, cause the computer system to at least:

generate a grid of shards, each shard of the grid of shards indexed by a corresponding set of indices, each set of indices having a predetermined number of indices, the set of indices at least including a first index, the grid of shards including a plurality of virtual shards, each virtual shard of the plurality of virtual shards configured to represent a shard of the grid of shards without storage of shard data on a 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 virtual shards, each shard of the first set of shards having a same corresponding first index as the second shard.

15. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of execution by the one or more processors, cause the computer system to update a set of shards of the grid of shards, the set of shards selected based at least in part on the corresponding set of indices of the updated first shard and the corresponding set of indices of the second shard.

16. The non-transitory computer-readable storage medium of claim 14, wherein each shard of the grid of shards is reproducible from other shards associated with a selected index of the set of indices using a selected redundancy code of a set of redundancy codes.

17. The non-transitory computer-readable storage medium of claim 16, wherein each shard of the grid of shards has a corresponding set of grid metadata, the set of grid metadata at least including a set of constants associated with the set of redundancy codes and usable with the set of redundancy codes to reproduce the shard.

18. The non-transitory computer-readable storage medium of claim 17, wherein the set of grid metadata includes a second set of constants associated with a cyclic redundancy check usable to validate the grid of shards.

19. The non-transitory computer-readable storage medium of claim 14, wherein each virtual shard of the plurality of virtual shards is a null shard.

20. The non-transitory computer-readable storage medium of claim 14, wherein each virtual shard of the plurality of virtual shards is a virtual data shard specifying a predetermined data value that can be determined without storing the predetermined data value in a data storage device.