VOLUME COHORTS IN OBJECT-REDUNDANT STORAGE SYSTEMS

• US 20150169716A1
• Filed: 12/18/2013
• Published: 06/18/2015
• Est. Priority Date: 12/18/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: FRANKLIN, PAUL DAVID, DONLAN, BRYAN JAMES
• Granted Patent: US 10,685,037 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

Cohorts may be created on storage nodes in an object-redundant storage system that uses replication and/or a redundant encoding technique. In a cohort with N nodes, M data elements (replicas or shards) of an object are stored to M of the nodes that are randomly (or otherwise) selected from the N nodes. Metadata for locating other data elements for an object in the cohort may be stored with one or more of the data elements in the cohort. To retrieve an object from a cohort, a subset of the nodes may be queried; the subset may be randomly or otherwise selected. If enough data elements are retrieved for the object from the queried nodes, the object is provided to the requester. Otherwise, additional data elements may be retrieved according to the metadata returned with a data element or by querying additional nodes.

Claims

1. A system, comprising:

a plurality of storage nodes;

one or more processors; and

a memory that stores program instructions executable by at least one of the one or more processors to implement an object-redundant storage system configured to;

establish a cohort spanning N of the plurality of storage nodes;

receive data objects to be stored to the storage system;

for each data object;

generate M object-redundant data elements from the data object according to an object-redundant technique, where M is less than N;

select M storage nodes from among the N storage nodes in the cohort according to a selection technique; and

store the M data elements to the selected M storage nodes, wherein one of the M data elements is stored on each of the M storage nodes;

wherein said generating, said selecting, and said storing distributes the data elements generated for the received data objects across the N storage nodes in the cohort so that a given two of the N storage nodes contain different sets of data elements.

2. The system as recited in claim 1, wherein the object-redundant technique is a replication technique, and wherein the object-redundant data elements are replicas of the data objects.

3. The system as recited in claim 1, wherein the object-redundant technique is an erasure encoding technique, wherein the object-redundant data elements are shards generated from the data objects, and wherein a subset of at least R of the M shards generated for a given data object according to the redundant encoding technique are required to recreate the respective data object.

4. The system as recited in claim 1, wherein the object-redundant storage system is further configured to, for each data object:

generate, for at least one of the M data elements generated for the object, metadata indicating one or more locations in the cohort at which one or more others of the M data elements are stored; and

store the metadata with the respective at least one data element on the selected M storage nodes.

5. The system as recited in claim 1, wherein the object-redundant storage system is further configured to:

receive a request for a data object stored to the storage system;

select a subset of the N storage nodes in the cohort; and

query the selected subset of storage nodes for data elements corresponding to the requested data object.

6. The system as recited in claim 5, wherein the object-redundant storage system is further configured to:

select another subset of the N storage nodes in the cohort; and

query the other subset of storage nodes for data elements corresponding to the requested data object.

7. The system as recited in claim 5, wherein the object-redundant storage system is further configured to receive at least one data element corresponding to the requested data object from the queried subset of storage nodes.

8. The system as recited in claim 7, wherein the object-redundant storage system is further configured to:

determine that at least one more data element corresponding to the requested data object is needed; and

query at least one additional storage node in the cohort for at least one more data element.

9. The system as recited in claim 8, wherein the object-redundant storage system is further configured to:

receive, with the at least one data element received from the queried subset of storage nodes, metadata indicating one or more locations in the cohort at which one or more others of the M data elements for the requested data object are stored;

wherein, to query at least one additional storage node in the cohort for at least one more data element, the object-redundant storage system is further configured to determine the at least one additional storage node from the received metadata.

10. The system as recited in claim 1, wherein the selection technique randomly selects at least one of the M storage nodes from among the N storage nodes in the cohort.

11. The system as recited in claim 1, wherein the selection technique selects at least one the M storage nodes according to an identity of the respective data object.

12. A method, comprising:

receiving, by a storage service implemented on one or more computing devices, data objects to be stored to an object-redundant storage system, wherein the object-redundant storage system comprises a cohort spanning N storage nodes;

for each received data object;

generating M object-redundant data elements from the data object according to an object-redundant technique, where M is less than N;

selecting M storage nodes from among the N storage nodes in the cohort;

storing the M data elements to the selected M storage nodes, wherein one of the M data elements is stored on each of the M storage nodes; and

storing metadata indicating one or more locations in the cohort at which one or more of the M data elements are stored.

13. The method as recited in claim 12, wherein said storing metadata indicating one or more locations in the cohort at which one or more of the M data elements are stored comprises storing metadata with at least one of the M data elements indicating one or more locations in the cohort at which one or more others of the M data elements are stored.

14. The method as recited in claim 12, wherein the object-redundant technique is one of a replication technique or an erasure coding technique.

15. The method as recited in claim 12, wherein the selection technique is one of a technique that randomly selects at least one of the M storage nodes or a technique that selects at least one the M storage nodes according to an identity of the respective data object.

16. The method as recited in claim 12, further comprising:

receiving a request for a data object stored to the storage system;

selecting a subset of the N storage nodes in the cohort;

querying the selected subset of storage nodes for data elements corresponding to the requested data object; and

receiving at least one data element corresponding to the requested data object from the queried subset of storage nodes.

17. The method as recited in claim 16, further comprising:

determining that at least one more data element corresponding to the requested data object is needed;

determining at least one additional storage node that contains a data element corresponding to the requested data object from the metadata indicating one or more locations in the cohort at which one or more of the M data elements are stored; and

querying the at least one additional storage node in the cohort for at least one more data element.

18. A non-transitory computer-accessible storage medium storing program instructions executable on one or more computers to implement an object-redundant storage system configured to:

receive data objects to be redundantly stored to a set of N storage nodes;

for each received data object;

generate M object-redundant data elements from the data object according to an object-redundant technique, where M is less than N;

select M storage nodes from among the N storage nodes;

store the M data elements to the selected M storage nodes, wherein one of the M data elements is stored on each of the M storage nodes; and

store, with at least one of the M data elements, metadata indicating, for each of the M data elements, a location at which the respective data element is stored.

19. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the object-redundant technique is one of a replication technique or an erasure coding technique.

20. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the selection technique is one of a technique that randomly selects at least one of the M storage nodes or a technique that selects at least one the M storage nodes according to an identity of the respective data object.

21. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the object-redundant storage system is further configured to:

receive a request for a data object stored to the storage system;

select a subset of the N storage nodes;

query the selected subset of storage nodes for data elements corresponding to the requested data object; and

receive at least one data element corresponding to the requested data object from the queried subset of storage nodes.

22. The non-transitory computer-accessible storage medium as recited in claim 21, wherein the object-redundant storage system is further configured to:

determine that at least one more data element corresponding to the requested data object is needed;

determine at least one additional storage node that contains a data element corresponding to the requested data object from the metadata stored with the data elements; and

query the at least one additional storage node for at least one more data element.