Techniques and systems for data segregation in redundancy coded data storage systems

• US 10,180,912 B1
• Filed: 12/17/2015
• Issued: 01/15/2019
• Est. Priority Date: 12/17/2015
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Franklin, Paul David, Donlan, Bryan James, Theimer, Marvin Michael
• Primary Examiner(s): Do, Khang
• Application Number:
  US14/973,677
• Time in Patent Office: 1,125 Days
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 2212/1052 Security improvement
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

A computer system, such as a data storage system, implements techniques for segregating and controlling access to data stored in multiple regions. In some embodiments, redundancy coded shards generated from the data and stored in durable storage of a data storage system is allocated across multiple regions, but in a fashion that prevents actors with access to regions outside that of a “home” region from recovering a sufficient number of unique shards to regenerate the data represented thereby. In some embodiments, encryption is used to segregate the data by encrypting the generated shards, then storing the cryptographic information on or otherwise controlling access on hosts or other devices of only the home region.

Claims

1. A computer-implemented method, comprising:

in response to obtaining a data storage request whose fulfillment involves storing data in a plurality of volumes of durable storage of a data storage system, the data storage request specifying a home region of a plurality of regions, storing the data by at least;

using a redundancy code, redundancy coding the data into a bundle of bundle-encoded shards that includes a set of data shards and a set of derived shards, the set of data shards including an original form of the data, the set of derived shards including a redundancy-coded form of the data, a quorum quantity of the bundle of bundle-encoded shards being sufficient to recreate the data via the redundancy code, the quorum quantity being less than a quantity of shards in the bundle;

encrypting the set of data shards using an encryption key to produce an encrypted set of data shards;

processing the encryption key so as to generate a set of encryption key shards, the set of encryption key shards having a size equal to a size of the set of data shards, a quorum quantity of the set of encryption key shards being;

less than the quorum quantity of the bundle of bundle-encoded shards; and

sufficient to regenerate the encryption key;

distributing the encrypted set of data shards and the set of encryption key shards among a first set of volumes of the plurality of volumes, the first set of volumes being located in the home region;

storing the set of derived shards among a second set of volumes of the plurality of volumes, the second set of volumes located outside of the home region; and

tracking shard storage in the second set of volumes so as to prevent a total number of shards of the set of derived shards from being stored among the second set of volumes such that a number of shards that is stored outside of the home region is insufficient to recreate the data.

2. The computer-implemented method of claim 1, wherein:

the computer-implemented method further comprises encrypting the set of derived shards with the encryption key within the home region to produce an encrypted set of derived shards; and

storing the set of derived shards includes storing the encrypted set of derived shards on the second set of volumes.

3. The computer-implemented method of claim 1, further comprising generating the set of derived shards using the encrypted set of data shards.

4. The computer-implemented method of claim 1, wherein the set of derived shards has a quantity of shards insufficient for regeneration of any of the data without at least one member of the encrypted set of data shards.

5. A system, comprising:

at least one computing device configured to implement one or more services, wherein the one or more services;

in response to obtaining a data storage request whose fulfillment involves storing data in a plurality of volumes of durable storage of a data storage system, the data storage request specifying a home region of a plurality of regions, store the data by at least causing the one or more services to;

using a redundancy code, redundancy code the data into a bundle of bundle-encoded shards that includes a set of data shards and set of derived shards, the set of data shards including an original form of the data, the set of derived shards including a redundancy-coded form of the data, a quorum quantity of the bundle being sufficient to recreate the data via the redundancy code, the quorum quantity being less than a quantity of shards in the bundle;

encrypt the set of data shards using an encryption key to produce an encrypted set of data shards;

process the encryption key so as to generate a set of encryption key shards, the set of encryption key shards having a size equal to a size of the set of data shards, a quorum quantity of the set of encryption key shards being;

less than the quorum quantity of the bundle of bundle-encoded shards; and

sufficient to regenerate the encryption key;

distribute the encrypted set of data shards and some of the set of encryption key shards among a first set of volumes of the plurality of volumes, the first set of volumes being located in the home region;

store the set of derived shards among a second set of volumes, the second set of volumes located outside of the home region; and

track shard storage in the second set of volumes so as to prevent a total number of shards of the set of derived shards from being stored among the second set of volumes such that a number of shards that is stored outside of the home region is insufficient to recreate the data.

6. The system of claim 5, wherein the set of derived shards has a quantity of shards insufficient for regeneration of any of the data without at least one member of the encrypted set of data shards.

7. The system of claim 5, wherein the home region and a region outside the home region include a plurality of volumes to which the encrypted set of data shards and the set of derived shards are allocated.

8. The system of claim 5, wherein the encryption key is processed using a shared secret cryptographic algorithm.

9. The system of claim 8, wherein the shared secret cryptographic algorithm is Shamir'"'"'s Secret Sharing.

10. The system of claim 8, wherein the shared secret cryptographic algorithm is used to generate the set of encryption key shards, a subset of which is sufficient for reconstructing the encryption key.

11. The system of claim 10, wherein at least some of the set of encrypted key shards are stored within the home region.

12. The system of claim 5, wherein the redundancy code is a linear erasure code.

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

in response to obtaining a data storage request whose fulfillment involves storing data in a plurality of volumes of durable storage of a data storage system, the data storage request specifying a home region of a plurality of regions, store the data by at least causing the computer system to;

using a redundancy code, redundancy code the data into a bundle of bundle-encoded shards that includes a set of data shards and set of derived shards, the set of data shards including an original form of the data, the set of derived shards including a redundancy-coded form of the data, a quorum quantity of the bundle being sufficient to recreate the data via the redundancy code, the quorum quantity being less than a quantity of shards in the bundle;

encrypt the set of data shards using an encryption key to produce an encrypted set of data shards;

process the encryption key so as to generate a set of encryption key shards, the set of encryption key shards having a size equal to a size of the set of data shards, a quorum quantity of the set of encryption key shards being;

less than the quorum quantity of the bundle of bundle-encoded shards; and

sufficient to regenerate the encryption key;

distribute the encrypted set of data shards and some of the set of encryption key shards among a first set of volumes of the plurality of volumes, the first set of volumes being located in the home region;

store the set of derived shards among a second set of volumes of the plurality of volumes, the second set of volumes located outside of the home region; and

track shard storage in the second set of volumes so as to prevent a total number of shards of the set of derived shards from being stored among the second set of volumes such that a number of shards that is stored outside of the home region is insufficient to recreate the data.

14. The non-transitory computer-readable storage medium of claim 13, wherein the executable instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to generate the bundle of bundle-encoded shards as a subset of a grid of shards.

15. The non-transitory computer-readable storage medium of claim 14, wherein the set of derived shards are vertically derived.

16. The non-transitory computer-readable storage medium of claim 14, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to store at least some of the set of derived shards within the home region.

17. The non-transitory computer-readable storage medium of claim 13, wherein the encryption key is a plain-text encryption key provided by a key management service.

18. The non-transitory computer-readable storage medium of claim 13, wherein the redundancy code includes a linear erasure code.

19. The non-transitory computer-readable storage medium of claim 18, wherein the linear erasure code is Reed-Solomon.

20. The non-transitory computer-readable storage medium of claim 13, wherein the set of derived shards are generated using the encrypted set of data shards.