Archival data organization and management

• US 9,092,441 B1
• Filed: 08/08/2012
• Issued: 07/28/2015
• Est. Priority Date: 08/08/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin L., Sorenson, James Christopher III, Seigle, Mark C., Claiborn, Christian L., Patiejunas, Kestutis
• Primary Examiner(s): Le, Uyen
• Application Number:
  US13/570,029
• Time in Patent Office: 1,084 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11

Abstract

Methods and systems are provided herein that facilitate cost-effective, scalable and reliable archival data organization and management. In an embodiment, data are redundantly encoded and stored to provide data reliability. Further, encoded data may be stored in self-describing storage entities that provide information describing data stored therein. Information provided by self-describing storage entities may be used to construct a limited map that is usable to facilitate data placement and data location services during data storage and retrieval. Data reliability and durability is provided because information about data stored in the system is mostly contained in the storage entities themselves. Cost efficiency is provided because only a limited map is provided for efficiency purposes instead of a potentially large global index data structure.

Claims

1. A system for providing archival data storage, comprising:

a plurality of data storage devices, each of the plurality of data storage devices storing a plurality of volume components, each of the plurality of volume components comprising a plurality of data components and corresponding to a volume, each volume corresponding to a volume identifier from a plurality of volume identifiers;

a plurality of data storage nodes, each of the plurality of data storage nodes being operably connected to one or more of the plurality of data storage devices and configured to provide information regarding the connected plurality of data storage devices and the plurality of data storage nodes;

a storage node registrar configured to receive information provided by the plurality of data storage nodes and to maintain a mapping that associates the plurality of volume identifiers with corresponding volume information, the mapping being based at least in part on the information received from the plurality of data storage nodes; and

a request processing sub-system configured to;

receive a request for a data object, the request specifying a volume identifier and an object identifier associated with the data object;

select, based at least in part on the volume identifier and the mapping maintained by the storage node registrar, one or more data storage nodes that store one or more volume components associated with the volume identifier;

for each of the selected one or more data storage nodes;

identify, based at least in part on the volume identifier, a volume component associated with the volume identifier that is stored by a data storage device operably connected to the data storage node;

retrieve, based at least in part on the object identifier, a data component stored in the identified volume component; and

provide the requested data object based at least in part on the retrieved data component from the selected one or more data storage nodes.

2. The system of claim 1, wherein the information provided by each of the plurality of data storage nodes comprises information about volume components stored in data storage devices operably connected to the data storage node and a network location of the data storage node.

3. The system of claim 1, wherein the mapping maintained by the storage node registrar associates each of a plurality of volume component identifiers with corresponding volume component information, the corresponding volume component information including a network location of a storage node that is connected to a storage device that stores the volume component.

4. The system of claim 1, wherein selecting the one or more data storage nodes comprises:

querying the storage node registrar using the volume identifier;

receiving, from the storage node registrar, one or more network locations corresponding to the one or more data storage nodes; and

determining a subset of the one or more data storage nodes based at least in part on a data encoding scheme.

5. The system of claim 1, wherein retrieving the data component stored in the identified volume component, for each of the selected one or more data storage nodes, comprises:

identifying a page within the volume component, based at least in part on the object identifier; and

determining a page offset within the page, based at least in part on the object identifier.

6. The system of claim 1, wherein providing the requested data object comprises applying one or more data decoding schemes to the retrieved data component.

7. The system of claim 6, wherein the one or more data decoding schemes include a redundancy-decoding scheme and a decryption scheme and wherein applying the one or more data decoding schemes to the retrieved data component comprises applying the redundancy-decoding scheme to the retrieved data component to obtain a resulting data object and applying the decryption scheme to the resulting data object.

8. The system of claim 1, wherein each volume component stores metadata information that identifies one or more data components stored therein.

9. A computer-implemented method comprising:

under the control of one or more computer systems comprising a storage node and configured with executable instructions,

receiving information, from a plurality of data storage nodes, each of the plurality of data storage nodes being operably connected to one or more of a plurality of data storage devices, regarding the connected plurality of data storage devices and the plurality of data storage nodes, wherein each of the plurality of data storage devices is configured to store a plurality of volume components, each of the plurality of volume components comprising plurality of data components and corresponding to a volume, each volume corresponding to a volume identifier from a plurality of volume identifiers;

providing information, from the plurality of data storage nodes, to a storage node registrar, the information regarding the connected plurality of data storage devices, the plurality of data storage nodes, at least a network location of the storage node, and storage information of one or more data storage devices operably connected to the storage node;

providing a mapping that associates the plurality of volume identifiers with corresponding volume information, the mapping being based at least in part on the information from the plurality of data storage nodes;

maintaining a request processing sub-system configured for;

receiving a request for a data object, the request specifying a volume identifier and an object identifier associated with the data component;

causing the request to be fulfilled using one of the one or more data storage devices operably connected to the storage node;

selecting, based at least in part on the volume identifier and the mapping, one or more data storage nodes that store one or more volume components associated with the volume identifier;

identifying, for each of the selected one or more data storage nodes, based at least in part on the volume identifier, a volume component associated with the volume identifier that is stored by a data storage device operably connected to the data storage node;

retrieving, based at least in part on the object identifier, a data component stored in the identified volume component, the data component being retrieved based at least in part on at least a portion of the provided information; and

providing the requested data object based at least in part on the retrieved data component from the selected one or more data storage nodes.

10. The computer-implemented method of claim 9, wherein providing information includes, for each of the one or more data storage devices:

identifying one or more volume components that are stored in the data storage device; and

obtaining information related to each of the one or more volume components.

11. The computer-implemented method of claim 10, wherein obtaining information related to each of the one or more volume components includes determining at least one of total space of the volume component, available space of the volume component, and a number of data components stored in the volume component.

12. The computer-implemented method of claim 9, wherein providing information occurs during a startup time of the storage node.

13. The computer-implemented method of claim 9, wherein the request includes at least one of storage, retrieval, and deletion of the data component.

14. The computer-implemented method of claim 9, further comprising providing updated information after one or more changes to data stored on the one or more data storage devices.

15. The computer-implemented method of claim 14, wherein the one or more changes to data stored on the one or more data storage devices includes at least one of data storage or data deletion.

16. The computer-implemented method of claim 9, further comprising providing updated information multiple times over a time period.

17. The computer-implemented method of claim 9, further comprising validating, based at least in part on information contained in the request, that the request can be fulfilled by at least one of the one or more data storage devices operably connected to the storage node.

18. The computer-implemented method of claim 9, further comprising validating, based at least in part on information contained in the request, integrity of payload data related to the request.

19. A computer-implemented method comprising:

under the control of one or more computer systems configured with executable instructions,

receiving information, from a plurality of data storage nodes, each of the plurality of data storage nodes being operably connected to one or more of a plurality of data storage devices, regarding the connected plurality of data storage devices and the plurality of data storage nodes, wherein each of the plurality of data storage devices is configured to store a plurality of volume components, each of the plurality of volume components comprising a plurality of data components and corresponding to a volume, each volume corresponding to a volume identifier from a plurality of volume identifiers;

providing information, from the plurality of data storage nodes, to a storage node registrar, the information regarding the connected plurality of data storage devices, the plurality of data storage nodes,

maintaining a mapping that associates the plurality of volume identifiers with corresponding volume information, the mapping being based at least in part on the information received from the plurality of data storage nodes;

maintaining a request processing sub-system configured for;

receiving a request to store a data object, the request specifying a volume identifier and an object identifier associated with the data object;

obtaining, in response to the received request to store the data object, one or more data components by causing an application of one or more data encoding schemes on the data object;

selecting, based at least in part on the volume identifier and the mapping maintained by the storage node registrar, one or more data storage nodes to store the one or more data components and one or more volume components associated with the volume identifier based at least in part on information that is dynamically provided by the one or more data storage nodes;

identify, for each of the selected one or more data storage nodes, based at least in part on the volume identifier, a volume component associated with the volume identifier that is stored by a data storage device operably connected to the data storage node;

retrieving, based at least in part on the object identifier, a data component stored in the identified volume component;

requesting the one or more data storage nodes to store the one or more data components; and

providing the requested data object based at least in part on the retrieved data component from the selected one or more data storage nodes.

20. The computer-implemented method of claim 19, wherein the request to store the data object specifies a volume identifier associated with the data object and wherein selecting the one or more data storage nodes is based at least in part on the volume identifier.

21. The computer-implemented method of claim 20, wherein the request to store the data object further specifies an object identifier used to identify the data object within a volume associated with the volume identifier and wherein requesting the one or more data storage nodes to store the one or more data components includes providing the volume identifier and the object identifier associated with the data object.

22. The computer-implemented method of claim 21, further comprising:

receiving a request to retrieve the data object, the request to retrieve the data object specifying the volume identifier and the object identifier;

identifying, based at least in part on the volume identifier and the information that is dynamically provided by the one or more data storage nodes, the one or more data storage nodes that host the one or more data components associated with the data object;

receiving, from a subset of the one or more data storage nodes, a subset of the one or more data components associated with the data object; and

providing the requested data object by causing an application of one or more decoding schemes corresponding to the one or more encoding schemes to the subset of the one or more data components.

23. The computer-implemented method of claim 19, wherein the one or more data encoding scheme includes a data redundancy encoding scheme and an encryption scheme.

24. The computer-implemented method of claim 23, wherein obtaining the one or more data components comprises at least encrypting the data object using the encryption scheme and redundantly-encoding the data object using the data redundancy encoding scheme.

25. One or more non-transitory computer-readable storage media having stored thereon instructions for causing at least one computer system to provide archival data storage, the instructions comprising instructions that cause said at least one computer to:

as a result of a received request to store a data object;

encode the data object into a first plurality of data components;

determine a plurality of data storage devices, each of the plurality of data storage devices storing a plurality of volume components, each of the plurality of volume components comprising a second plurality of data components and corresponding to a volume, each volume corresponding to a volume identifier from a plurality of volume identifiers;

store, on the determined plurality of data storage devices, the first plurality of data components based at least in part on aggregate information about a hierarchical data structure, portions of the aggregated information being received from the plurality of data storage devices, wherein the aggregated information comprises information about volume components stored in the plurality of data storage devices;

cause the first plurality of data components to be stored in the hierarchical data structure;

provide information, from a plurality of data storage nodes, to a storage node registrar, wherein each of the plurality of data storage nodes being operably connected to one or more of the plurality of data storage devices and configured to provide information regarding the connected plurality of data storage devices and the plurality of data storage nodes;

provide a mapping, to the storage node registrar, that associates the plurality of volume identifiers with corresponding volume information, the mapping being based at least in part on the information received from the plurality of data storage nodes;

maintain a request processing sub-system configured to;

receive a request for a data object, the request specifying a volume identifier and an object identifier associated with the data object;

select, based at least in part on the volume identifier and the mapping, one or more data storage nodes that store one or more volume components associated with the volume identifier;

identify, for each of the selected one or more data storage nodes, based at least in part on the volume identifier, a volume component associated with the volume identifier that is stored by a data storage device operably connected to the data storage node;

retrieve, based at least in part on the object identifier, a data component stored in the identified volume component; and

provide the requested data object based at least in part on the retrieved data component from the selected one or more data storage nodes.

26. The one or more non-transitory computer-readable storage media of claim 25, wherein the hierarchical data structure comprises a volume, the volume comprising a one or more volume components, each of the one or more volume components comprising one or more pages, and each of the one or more pages being configured to store one or more data components.

27. The one or more non-transitory computer-readable storage media of claim 25, wherein the instructions comprising instructions that further cause said at least one computer to update the aggregated information about the hierarchical data structure when a data component is added or deleted from the data structure.