Massively scalable object storage system for storing object replicas

• US 8,538,926 B2
• Filed: 04/19/2011
• Issued: 09/17/2013
• 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:
  US13/089,442
• Publication Number:
  US 20120233418A1
• Time in Patent Office: 882 Days
• Field of Search: 707/999.01, 707/999.107, 707/999.202, 707/999.204, 707/652, 707/690, 707/694, 707/698, 707/825, 707/959, 709/251, 709/213, 709/220
• US Class Current: 707/652
• 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

Several different embodiments of a massively scalable object storage system are described. The object storage system is particularly useful for storage in a cloud computing installation whereby shared servers provide resources, software, and data to computers and other devices on demand. In several embodiments, the object storage system includes a ring implementation used to associate object storage commands with particular physical servers such that certain guarantees of consistency, availability, and performance can be met. In other embodiments, the object storage system includes a synchronization protocol used to order operations across a distributed system. In a third set of embodiments, the object storage system includes a metadata management system. In a fourth set of embodiments, the object storage system uses a structured information synchronization system. Features from each set of embodiments can be used to improve the performance and scalability of a cloud computing object storage system.

Claims

1. A method for storing data, comprising:

providing a plurality of physical storage pools, each storage pool including a plurality of storage nodes coupled to a network, each storage node further providing a non-transitory computer readable medium for data storage;

classifying a plurality of availability zones, wherein the storage nodes within an availability zone are subject to a correlated loss of access to stored data;

defining a plurality of abstract partitions, wherein each possible input data management request deterministically corresponds to one of the plurality of abstract partitions, and wherein the deterministic correspondence between each possible input data management request and an abstract partition of the plurality of abstract partitions is established using a function;

mapping the plurality of abstract partitions to the plurality of physical storage pools such that each mapped physical storage pool includes a replica of the data associated with the associated mapped abstract partition, and each replica for a particular abstract partition is mapped to a physical storage pool in a different availability zone, wherein the mapping the plurality of abstract partitions to the plurality of physical storage pools includes applying a constraint satisfaction algorithm;

receiving a data management request over the network, the data management request associated with a data object;

determining, using the data object and function, a partition identification;

identifying, using the partition identification and the constraint satisfaction algorithm, a first partition 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.

2. The method of claim 1, wherein the function is a consistent hashing function, the method further comprising:

receiving the data object to store in the physical storage pools,

wherein the determining a partition identification includes applying the consistent hashing function to the data object, and the partition identification includes a plurality of parts, and

wherein the mapping the plurality of abstract partitions includes applying the constraint Satisfaction algorithm to each of the plurality of parts.

3. The method of claim 1, further comprising:

storing in a constrained mapping database a plurality of results based on the applying the constraint satisfaction algorithm to each of the plurality of parts, wherein the identifying a first partition includes accessing the constrained mapping database.

4. The method of claim 1, further comprising:

determining that a storage pool has been removed from the plurality of storage pools; and

remapping the plurality of abstract partitions to the plurality of physical storage pools such that each mapped physical storage pool includes a replica of the data associated with the associated mapped abstract partition, each replica for a particular abstract partition is mapped to a physical storage pool in a different availability zone, and each remapped abstract partition has zero or one changes in physical storage pools used to replicate the partition.

5. The method of claim 1, further comprising:

determining that at least one overutilized physical storage pool has been mapped to a number of partition replicas that exceeds a threshold amount; and

remapping the plurality of abstract partitions to the plurality of physical storage pools such that each mapped physical storage pool includes a replica of the data associated with the mapped abstract partition, each replica for a particular abstract partition is mapped to a physical storage pool in a different availability zone, and the number of partition replicas in the overutlized physical storage pool does not exceed the threshold amount.

6. The method of claim 5, wherein the remapping results in each of the plurality of storage pools not exceeding the threshold number of partition replicas.

7. The method of claim 1, further comprising:

determining that at least one overutilized physical storage pool exceeds a threshold level of capacity use; and

remapping the plurality of abstract partitions to the plurality of physical storage pools such that each mapped physical storage pool includes a replica of the data associated with the mapped abstract partition, each replica for a particular abstract partition is mapped to a physical sotorage pool in a different availability zone, and the capacity of the overutilized physical storage pool does not exceed the threshold amount.

8. The method of claim 7, wherein the remapping results in each of the plurality of storage pools not exceeding the threshold level of capacity use.

9. The method of claim 1, wherein the data management request is one of a request to store a data object and a request to update a data object, and wherein the manipulation of the data object in accordance with the data management request includes storing a replica of the object in at least two of the physical storage pools mapped to the identified first partition.

10. The method of claim 1, wherein the data management request is a request to retrieve a data object, and wherein the manipulation of the data object in accordance with the data management request includes retrieving a replica of the object from one of the physical storage pools mapped to the identified first partition.

11. The method of claim 1, wherein the data management request is received over the Internet.

12. The method of claim 9, further comprising:

determining that a storage pool has been removed from the plurality of storage pools; and

remapping the partition replicas that were mapped to the storage pool that was removed from the plurality of storage pools such that each partition replica for the first partition remains mapped to a storage pool in a different zone.

13. The method of claim 9, further comprising:

determining that at least one storage pool has been mapped a number of partition replicas that exceeds a threshold amount; and

remapping the number of partition replicas from the at least one storage pool that has been mapped the number of partition replicas that exceeds the threshold amount such that each partition replica for the first partition remains mapped to a storage pool in a different zone while the at least one storage pool is mapped a number of partition replicas that does not exceed the threshold amount.

14. The method of claim 13, wherein the remapping results in each of the plurality of storage pools being mapped with a number of partition replicas that does not exceed the threshold amount.

15. The method of claim 9, further comprising:

determining that at least one storage pool exceeds a threshold storage capacity; and

remapping the number of partition replicas from the at least one storage pool that exceeds the threshold storage capacity such that each partition replica for the first partition remains mapped to a storage pool in a different zone while the at least one storage pool does not exceed the threshold storage capacity.

16. A massively scalable online data storage system, comprising:

a distributed storage coupled to a network, the distributed storage including a first storage pool and a second storage pool from a plurality of storage pools, the first storage pool in a first availability zone and the second storage pool in a second availability zone, each storage pool including at least one processor, a non-transitory computer readable medium, and a communications interface;

a director coupled to the network, the director including a processor, a computer readable medium, and a communications interface;

a constrained mapping database to store a mapping of a first abstract partition to the first and second storage pools, the mapping being based on a number of abstract partitions and a number of storage pools in the plurality of storage pools and based on applying a constraint satisfaction algorithm; and

a ring structure associated with the director, wherein the ring structure associates, using a hashing function, a storage request with the first abstract partition from a plurality of abstract partitions, and selectively associates a first abstract partition with a first fault-tolerant multi-master replication target, the first replication target including the first storage pool and the second storage pool;

wherein a partition identification of the first abstract partition includes a plurality of parts, and the ring structure maps the first abstract partition by applying the constraint satisfaction algorithm to each of the plurality of parts,

wherein the director routes inbound storage requests to the replication target and outbound storage responses from the replication target.

17. The massively scalable online data storage system of claim 16, wherein the distributed storage further comprises a third storage pool in a third availability zone.

18. The massively scalable online data storage system of claim 17, wherein the first replication target includes the third storage pool.

19. The massively scalable online data storage system of claim 17, wherein the ring structure rebalances the distributed storage, wherein rebalancing the distributed storage removes the second storage pool from the first replication target includes the third storage pool in the first replication target.

20. The massively scalable online data storage system of claim 19, wherein the ring structure rebalances the distributed storage due to a change in the number of storage pools.

21. The massively scalable online data storage system of claim 19, wherein rebalancing the distributed storage requires one or zero changes to the population of storage pools included in each replication target.

22. The massively scalable online data storage system of claim 19, wherein the ring structure reassociates the first abstract partition with a third storage node upon the failure of the second storage node, wherein the third storage node is in an availability zone different than the availability zone including the first storage node.

23. A non-transitory computer readable medium containing executable instructions, which when executed on a processor:

at a first time, initialize a ring by retrieving a set of ring parameters, the ring parameters including a number of abstract partitions, a number of physical storage pools, and a constraint satisfaction algorithm;

performing a consistent hashing function associating a first range of inputs with a first abstract partition and a second range of inputs with a second abstract partition;

determining a plurality of outputs by applying an algorithm to a result of the performing a consistent hashing function; and

allocating the available physical storage pools by mapping each abstract partition to one or more storage pools based on applying the constraint satisfaction algorithm to each output of the plurality of outputs;

at a second time, opaquely route an input request to a correct storage pool in accordance with the initialized ring;

at a third time, rebalance the ring by retrieving the set of ring parameters, performing a consistent hashing function associating the range of inputs with the first abstract partition and the second range of inputs with the second abstract partition; and

allocating the available storage pools mapping each abstract partition to one or more storage pools in accordance with the set of performance constraints such that each abstract partition has zero or one changes in the physical storage pools allocated thereto.