Systems and techniques for data recovery in a keymapless data storage system

• US 10,558,581 B1
• Filed: 02/19/2013
• Issued: 02/11/2020
• Est. Priority Date: 02/19/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin Laird
• Primary Examiner(s): Birkhimer, Christopher D
• Application Number:
  US13/770,892
• Time in Patent Office: 2,548 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Components of a data object are distributed throughout a data storage system. Manifests are used to store the locations of the components of data objects in a data storage system to allow for subsequent reconstruction of the data objects. The manifests may be stored in another data storage system when cost projections indicate it being economical to do so. If a manifest for a data object becomes lost or otherwise inaccessible, clues are used to regenerate the manifest, thereby providing a continued ability to access the components of the data object to reconstruct the data object.

Claims

1. A computer-implemented method, comprising:

storing, by one or more computing systems, a plurality of components corresponding to a data object in different locations of a data storage system, the plurality of components being generated by applying a redundancy encoding to the data object;

generating, by the one or more computing systems and based at least in part on a configuration of the data storage system, a manifest for the data object that includes at least;

locations, in the data storage system, of the plurality of components; and

information that identifies at least one construction of the data object from a subset of the plurality of components, the at least one construction based at least in part on the configuration;

storing the manifest in a different data storage system;

detecting, by the one or more computing systems, inaccessibility of the manifest from the different data storage system; and

as a result of detecting the inaccessibility of the manifest;

determining, by the one or more computing systems, without access to the manifest and based at least in part on a search parameter obtained from a data object identifier corresponding to the data object, the locations of the plurality of components, wherein the data object identifier includes information indicative of a location of the generated manifest;

determining, by the one or more computing systems, without access to the manifest, and based at least in part on the determined locations and based at least in part on the configuration, a construction of the data object from the plurality of components; and

regenerating, by the one or more computing systems, the manifest based at least in part on the determined construction.

2. The computer-implemented method of claim 1, wherein the data storage system is configured to respond to requests to retrieve data objects stored by the data storage system without using a keymap associating data object identifiers with locations of corresponding data objects stored by the data storage system.

3. The computer-implemented method of claim 1, wherein locating the plurality of components includes distinguishing, based at least in part on one or more characteristics of the data object obtained from outside of the manifest and the configuration of the data storage system, the plurality of components from other data objects stored by the data storage system.

4. The computer-implemented method of claim 1, wherein the method further comprises:

obtaining, without accessing the manifest, a hash associated with the data object, wherein determining the construction includes determining an ordering of the plurality of components of the data object that results in a tree hash that matches the obtained hash.

5. The computer-implemented method of claim 4, wherein obtaining the hash includes decoding the hash from a data object identifier corresponding to the data object.

6. The computer-implemented method of claim 1, wherein storing the manifest in the different data storage system is a result of determining to store the manifest in the different data storage system based at least in part on a projected cost of storing the manifest in the different data storage system being less than a projected cost of storing the manifest in the data storage system.

7. The computer-implemented method of claim 1, further comprising, as a result of detecting the inaccessibility of the manifest:

retrieving, by the one or more computing systems, the search parameter from the data object identifier corresponding to the data object, the data object identifier being formatted to comprise one or more search parameters, wherein the locating of the plurality of components of the data object is based at least in part on the one or more search parameters, the one or more search parameters comprising one or more of a component size for the data object, time information identifying when the data object was stored in the data storage system, or a number of components for the plurality of components of the data object.

8. The computer-implemented method of claim 7, wherein the one or more search parameters further comprises at least one of a first size of the data object or a second size corresponding to a component.

9. The computer-implemented method of claim 1, wherein determining the constructions of the data object comprises:

generating a hashed identifier based at least in part on a hash tree and the plurality of components; and

determining that the hashed identifier matches a previously-determined hashed identifier associated with the data object.

10. A computer-implemented method, comprising:

generating a manifest for a data object, the manifest including at least;

locations, in a data storage system, of a plurality of components corresponding to the data object, the plurality of components generated by applying a redundancy encoding to the data object; and

construction information for the data object identifying a subset of the plurality of components; and

regenerating the manifest by at least;

determining, based at least in part on a search parameter obtained based at least in part on an identifier of the data object, the locations of the plurality of components, wherein the identifier of the data object includes information indicative of a location of the generated manifest;

determining, without access to the manifest, a construction of the data object using a subset of the plurality of components; and

processing at least the determined construction to create the manifest.

11. The computer-implemented method of claim 10, wherein locating the plurality of components includes selecting the components based at least in part on one or more characteristics of the data object obtained without accessing the manifest.

12. The computer-implemented method of claim 11, wherein the one or more characteristics include a time of upload of the data object to the data storage system.

13. The computer-implemented method of claim 10, wherein locating the plurality of components includes selecting a set of components that are each a same size.

14. The computer-implemented method of claim 10, wherein the method further comprises:

detecting inaccessibility of the manifest from a different data storage system; and

regenerating the manifest in response to detecting the inaccessibility of the manifest.

15. The computer-implemented method of claim 10, wherein the search parameter is encoded in the identifier of the data object.

16. A system, comprising:

one or more processors; and

memory, including instructions that, if executed by the one or more processors, cause the system to;

identify, based at least in part on characteristics of a data object, a subset of a set of data objects persistently stored among a plurality of data storage devices, the subset comprising components of the data object;

determine, based at least in part on comparing a hash generated based on a potential ordering of the subset to a hash derived from an identifier of the data object, a construction of the data object using the identified subset; and

generate, based at least in part on the construction of the data object and the configuration, a manifest for the data object, the manifest comprising a specification of the subset informing construction of the data object from the subset.

17. The system of claim 16, wherein the instructions further cause the system to retrieve data objects without using a keymap that associates the data objects with respective locations in the system.

18. The system of claim 16, wherein the subset includes a plurality of data objects that were uploaded to the system within a predetermined time period and that are a same size.

19. The system of claim 16, wherein the instructions further cause the system to persist the generated manifest in a data storage system that is different from the system.

20. The system of claim 16, wherein:

the system is hosted by a computing resource provider as a service to customers of the computing resource provider;

the instructions further cause the system to provide an application programming interface for enabling the customers to utilize the service; and

the subset of data objects is stored on behalf of a particular customer of the customers.

21. One or more non-transitory computer-readable storage media having stored thereon instructions that, if executed by one or more processors of a computer system, cause the computer system to generate a manifest for a data object by at least:

locating, in a data storage system, a plurality of components of the data object that are combinable to construct the data object, the locating based at least in part on information indicative of a composition of the data object obtained from an identifier of the data object;

determining, without access to the manifest, and based at least in part on comparing a hash generated based on a potential ordering of a subset of plurality of components to a hash derived from an identifier of the data object, a construction of the data object using the subset of the plurality of components; and

generating, based at least in part on the determined construction, the manifest to include the construction and locations of the subset of the plurality of components.

22. The one or more non-transitory computer-readable storage media of claim 21, wherein:

the instructions further cause the computer system to store the generated manifest such that a data object identifier existing prior to generation of the generated manifest is usable, without a keymap, to locate the generated manifest.

23. The one or more non-transitory computer-readable storage media of claim 22, wherein storing the generated manifest includes causing a data storage system, different from the computer system, to persist the generated manifest.

24. The one or more non-transitory computer-readable storage media of claim 21, wherein the instructions cause the computer system to locate the plurality of components, determine the construction, and generate the manifest as a result of detecting an inaccessibility of a previously generated manifest for the data object.

25. The one or more non-transitory computer-readable storage media of claim 21, wherein determining the construction includes determining the ordering of the plurality of components that is usable to obtain a tree hash of the data object.

26. The one or more non-transitory computer-readable storage media of claim 21, wherein locating the plurality of components includes identifying data objects that were uploaded during a time period determined to be near a time at which the data object was uploaded.