Massively scalable object storage for storing object replicas

• US 9,116,629 B2
• Filed: 09/13/2013
• Issued: 08/25/2015
• Est. Priority Date: 03/08/2011
• Status: Expired due to Fees

• 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:
  US14/026,207
• Publication Number:
  US 20140082301A1
• Time in Patent Office: 711 Days
• US Class Current: 1/1
• 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 storing data, comprising:

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

mapping a first partition of a plurality of partitions to a first set of the physical storage pools, wherein the mapping includes creating a plurality of replicas of a data object for the first partition, wherein each physical storage pool of the first set thereof is located in a different availability zone, and wherein the storage nodes within a particular availability zone are subject to a correlated loss of access to data objects stored therein;

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

modifying an attribute of the data object;

applying a hash function to the modified attribute;

identifying, based on a result of the hash function, the first partition of the plurality of partitions as corresponding to the received data management request;

manipulating the particular data object in the physical storage pools mapped to the first partition in accordance with the data management request;

modifying the result of the hash function to determine a plurality of different results;

for each data object replica of the plurality of data object replicas, storing the respective data object replica in a storage pool corresponding to a result of the plurality of different results;

determining that a first data object replica stored in a first storage pool is stored in the same availability zone as a second data object replica stored in a second storage pool; and

rebalancing the first and second data object replicas, wherein the rebalancing includes applying a constrained mapping function to bits of the results of the plurality of results, wherein a number of bits to which the constrained mapping function is applied is a partition power, and wherein after the rebalancing the first and second data object replicas are stored in different availability zones.

2. The method of claim 1, wherein the manipulating includes storing the data object.

3. The method of claim 1, wherein a quantity of the plurality of replicas is equal to a quantity of storage pools to which the first partition is mapped.

4. The method of claim 1, wherein based on storing the respective data object replica in the storage pool corresponding to the result of the plurality of different results, each data object replica is stored in a different storage pool.

5. The method of claim 1, wherein the hash function is a consistent hashing function.

6. The method of claim 1, wherein 2 to the partition power indicates a partition count.

7. The method of claim 6, wherein each partition is identified by a partition identifier, and wherein the constrained mapping function returns a storage pool location for each portion of the partition identification to which the constrained mapping function is applied.

8. The method of claim 7, wherein storage pool locations returned for a given partition identification correspond to storage pools in different availability zones.

9. A scalable online data storage system, comprising:

a distributed storage coupled to a network, the distributed storage including a first physical storage pool and a second physical storage pool from a plurality of physical storage pools, the first physical storage pool in a first availability zone and the second physical 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 partition of a plurality of partitions to a first set of the physical storage pools, wherein each physical storage pool of the first set thereof is located in a different availability zone, and wherein the storage nodes within a particular availability zone are subject to a correlated loss of access to data objects stored therein; and

a ring structure associated with the director, wherein the ring structure receives a particular data management request over the network, wherein the data management request is associated with a particular data object, and wherein the ring structure modifies an attribute of the data object, applies a hash function to the modified attribute, and identifies, based on a result of the hash function, the first partition of the plurality of partitions as corresponding to the received data management request;

wherein the ring structure based on the mapping creates a plurality of replicas of the data object for the first partition, and wherein the ring structure modifies the result to determine a plurality of different results;

wherein the director manipulates the particular data object in the physical storage pools mapped to the first partition in accordance with the data management request, wherein for each data object replica of the plurality of data object replicas, the director stores the respective data object replica in a storage pool corresponding to a result of the plurality of different results, wherein the ring structure determines that a first data object replica stored in a first storage pool is stored in the same availability zone as a second data object replica stored in a second storage pool, and applies a constrained mapping function to bits of the results of the plurality of results, and wherein the constrained mapping function returns a storage pool location for each portion of the partition identification to which the constrained mapping function is applied.

10. The scalable online data storage system of claim 9, wherein the director receives the data object.

11. The scalable online data storage system of claim 9, wherein a quantity of the plurality of replicas is equal to a quantity of storage pools to which the partition is mapped.

12. The scalable online data storage system of claim 9, wherein the hash function is a consistent hashing function.