Massively scalable object storage for storing object replicas

• US 10,209,893 B2
• Filed: 09/12/2017
• Issued: 02/19/2019
• Est. Priority Date: 03/08/2011
• Status: Active Grant

• Current Assignee: Rackspace US Incorporated (Apollo Global Management, Inc.)
• Original Assignee: Rackspace US Incorporated (Apollo Global Management, Inc.)
• Inventors: Barton, Michael, Reese, Will, Dickinson, John A., Payne, Jay B., Thier, Charles B., Holt, Gregory
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US15/702,726
• Publication Number:
  US 20180004426A1
• Time in Patent Office: 525 Days
• CPC Class Codes: G06F 16/1824 implemented using Network-attached Storage [NAS] architecture distributed or networked storage systems G06F3/067; protocols for distributed storage of data in a network H04L67/1097
• 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
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 47/80 Actions related to the user profile or the type of traffic
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1006 with static server selection, e.g. the same server being selected for a specific client
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• 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]
• CPC Class Codes: Y10S 707/9994 Distributed or remote access
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

An example method for storing data includes providing a plurality of physical storage pools, each storage pool including a plurality of storage nodes coupled to a network. The method also includes mapping a partition of a plurality of partitions to a set of physical storage pools, where each physical storage pool of the set of physical storage pools is located in a different availability zone, and the storage nodes within an availability zone are subject to a correlated loss of access to stored data. The method further includes receiving a data management request over the network, the data management request being associated with a data object. The method also includes identifying a first partition of the plurality of partitions corresponding to the received data management request and manipulating the data object in the physical storage pools mapped to the first partition in accordance with the data management request.

Claims

1. A method for locating objects on hosts in an online service with particular availability guarantees, the method comprising:

consulting by a director a multi-level ring structure including at least two levels, wherein a first level of the ring structure corresponds to hard constraints on the placement of objects, and a second level of the ring structure corresponds to soft constraints on the placement of objects, wherein the sum of the constraints controls the location of objects within the online service, wherein the satisfaction of at least one hard constraint is satisfied by identifying at least one diverse storage pool, and wherein at least one soft constraint is satisfied by identifying at least one durable storage location;

wherein each diverse storage pool includes a set of non-co-located storage elements, wherein no storage element of a diverse storage pool overlaps with any other storage element in any other diverse storage pool, the diverse storage pools communicably coupled with each other, and with the director, the set number of diverse storage pools being at least equal to a given replication number greater than one;

wherein each diverse storage pool includes a plurality of partitions, mapped onto the storage element of the diverse storage pool, each partition being associated with a distinct durable storage location managed by at least one local processor operably connected to a local communications port,

receiving from the director a selected set of distinct partitions, the cardinality of the set at least equal to the given replication number, wherein each distinct durable storage location is compliant with at least one hard constraint and one soft constraint, the contents of the selected set being deterministic relative to a selection key;

and effecting a change in an object located at a distinct durable storage location in the selected set by interacting with the local processor associated with the selected location;

the effected change selected from a set of operations including reading, writing, creating, deleting, and executing.

2. The method of claim 1, further comprising receiving a request from a location external to the online service to interact with a particular object, the request including a selection key.

3. The method of claim 2, further comprising providing a response to the request with information related to the object and the effected change.

4. The method of claim 3, wherein the response includes the contents of the object.

5. The method of claim 3, wherein the response includes the result of interpreting at least a portion of the object as executable instructions using the associated local processor and including the computed result.

6. The method of claim 2, wherein the request further includes data to be stored in the online service, and wherein effecting a change includes replicating copies of the data are in a number of distinct partitions at least equal to the replication number.

7. The method of claim 1, wherein no two diverse storage pools are subject to a correlated loss of access due to a single event.

8. A method for ensuring the availability of data, the method comprising:

partitioning, by a director, a plurality of storage pools into a set of diverse storage pools, the cardinality of the set of diverse storage pools being equal to a given replication number greater than one;

each storage pool including a plurality of storage elements, each with a local processor and a local communications port, and a plurality of partitions, each partition being associated with a distinct durable storage location managed by the least one local processor, the plurality of partitions being mapped onto the plurality of storage elements, and the storage elements within a storage pool being communicably coupled with each other and with the director, each diverse storage pool including a set of non-co-located storage elements, wherein no storage element of a first diverse storage pool overlaps with any other storage element in any other diverse storage pool;

creating a multi-level ring structure including at least two levels, wherein a first level of the ring maps a selection key to an ordered set of partitions, and a second level of the ring structure corresponding to a set of constraints on the partitions available for storage of an object, wherein the sum of the constraints controls the location of objects within the online service, wherein the satisfaction of at least one constraint is satisfied by identifying partitions mapped to storage elements within a number of diverse storage pools at least equal to the replication number, and wherein the mapping of the selection key to the corresponding ordered set of partitions being deterministic relative to the selection key;

replicating a provided object to a number of partitions within the corresponding ordered set of partitions mapped by the selection key, the number of partitions being at least equal to the replication number.

9. The method of claim 8, further comprising:

rebuilding the ring structure due to a change in the total number of available storage pools, storage elements, or partitions; and

replicating an object from a previous location to a new location based upon the rebuilt ring structure;

wherein the number of replicas of the object in diverse storage pools never drops below a set threshold.

10. The method of claim 9, wherein the set threshold is one less than the replication number.

11. The method of claim 9, wherein the set threshold is equal to the replication number.

12. The method of claim 8, wherein no two diverse storage pools are subject to a correlated loss of access due to a single event.

13. The method of claim 8, further comprising testing the availability and responsiveness of the storage elements corresponding to selected mapped partitions from the ordered set, and replicating the object to the next partition in the ordered set of partitions if any of the previously selected partitions are mapped to storage elements that fail the availability or responsiveness test.

14. A system for distributed evaluation, the system comprising:

a director, the director comprising an inbound communications port, an outbound communications port, a local storage, a director processor, and a set of executable instructions stored on a non-transitory medium;

a plurality of storage pools;

each storage pool including a plurality of storage elements, each with a local processor and a local communications port, and a plurality of partitions, each partition being associated with a distinct durable storage location managed by the least one local processor, the plurality of partitions being mapped onto the plurality of storage elements, and the storage elements within a storage pool being communicably coupled with each other and with the director, each diverse storage pool including a set of non-co-located storage elements;

a multi-level ring structure mapping a selection key to an ordered set of partitions, the ring operably connected to the director, the ring including at least two levels, wherein a first level of the ring maps a selection key to an ordered set of partitions, and a second level of the ring structure corresponding to a set of constraints on the partitions, wherein the mapping of the selection key to the corresponding ordered set of partitions being deterministic relative to the selection key;

the executable instructions associated with the director being operable to;

receive a request identifying a selection key and a set of arguments;

retrieve the set of matching partitions based upon the selection key; and

communicate at least a subset of the request to the storage element associated with each identified matching partition;

wherein the local processor evaluates a set of instructions and data located within the identified matching partition and returns a computed response.

15. The system of claim 14 wherein the selection key corresponds to an account identifier and the computed response corresponds to account information.

16. The system of claim 14 wherein the selection key corresponds to a container identifier and the computed response corresponds to information associated with the container.

17. The system of claim 14 wherein the request includes an executable function identifier, the selection key corresponds to a selection from a dataset stored in the plurality of storage pools, and the computed response corresponds to the output of the executable function when given the selection from the dataset as an input.

18. The system of claim 14, wherein the distinct durable storage location associated with each partition stores a structured data file, and wherein the computed response includes a selection from the structured data file.

19. The system of claim 14, wherein each partition is associated with an executable container, and the computed response is the result of executing the container.