Data gravitation

• US 8,069,145 B2
• Filed: 08/30/2007
• Issued: 11/29/2011
• Est. Priority Date: 08/30/2007
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Stansberry, Brian Edward, Surtani, Manik Ram
• Primary Examiner(s): Chbouki; Tarek
• Application Number:
  US11/897,710
• Publication Number:
  US 20090063588A1
• Time in Patent Office: 1,552 Days
• Field of Search: None
• US Class Current: 707/637
• CPC Class Codes: G06F 11/1666 where the redundant component is memory or memory area
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2043 where the redundant components share a common memory address space
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• 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/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54

Abstract

A method and apparatus for obtaining data of a cache node in a tree-structured cluster is described. In one embodiment, a query for data in the cache node of the tree-structured cluster is received. A determination of whether the data is stored in the queried cache node is made. An inquiry of other cache nodes in the cluster for the data is performed. An instance of the data from a cache node storing the data is replicated to the cache node receiving the query.

Claims

1. A computer-implemented method comprising:

determining, by a first cache node in a tree-structured cluster of cache nodes, that a second cache node in the tree-structured cluster of cache nodes has failed, wherein the first cache node is a backup cache node for the second cache node and stores data of the second cache node as backup data;

taking ownership, by the first cache node, of the data of the second cache node by treating the second cache node data as primary data of the first cache node, wherein a backup cache node for the first cache node stores the second cache node data as backup data for the first cache node in addition to backup data already stored for the first cache node at the backup cache node for the first cache node;

receiving, by the first cache node, a query for the second cache node data from a third cache node in the tree-structured cluster of cache nodes;

replicating, by the first cache node, an instance of the queried second cache node data to the third cache node; and

removing, by the first cache node, the instance of the queried data from the primary data of the first cache node in response to an instruction to delete the instance of the queried data, wherein the third cache node acts as primary owner of the instance of the queried data once it is replicated to the third cache node;

wherein a memory usage for each node in the tree-structured cluster of cache nodes is (b+1)X, where X is the average data size for each node and b is the number of buddies per node.

2. The method of claim 1, further comprising instructing the backup cache node for the first cache node to delete the instance of the queried data when the instruction to delete the instance of the queried data is received at the first cache node.

3. The method of claim 1, wherein the third cache node automatically inquires one or more other cache node in the cluster until it locates the instance of the queried data on the second cache node, and wherein inquiring the one or more other cache nodes is based on a per-invocation basis.

4. The method of claim 1, wherein the cluster comprises a plurality of cache nodes, each cache node selecting one other cache node as a backup.

5. The method of claim 1, wherein the cache nodes are located on different physical hosts.

6. The method of claim 1, wherein the cache nodes are located on different physical racks.

7. The method of claim 1, wherein one or more pools of cache nodes are formed in the cluster, wherein an instance of a cache node from a pool is replicated to one cache node in the same pool.

8. The method of claim 7, wherein the cache nodes from a pool are located on different physical racks.

9. An apparatus comprising:

a memory configured to store primary data for a first cache node of a tree-structured cluster of cache nodes and backup data for a second cache node of the tree-structured cluster of cache nodes; and

a processing device coupled to the memory, the processing device configured to;

determine that the second cache node has failed;

take ownership of the data of the second cache node by treating the second cache node data as primary data of the first cache node, wherein a backup cache node for the first cache node stores the second cache node data as backup data for the first cache node in addition to backup data already stored for the first cache node at the backup cache node for the first cache node;

receive a query for the second cache node data from a third cache node in the tree-structured cluster of cache nodes;

replicate an instance of the queried second cache node data to the third cache node; and

remove the instance of the queried data from the primary data of the first cache node in response to an instruction to delete the instance of the queried data, wherein the third cache node acts as primary owner of the instance of the queried data once it is replicated to the third cache node;

wherein a memory usage for each node in the tree-structured cluster of cache nodes is (b+1)X, where X is the average data size for each node and b is the number of buddies per node.

10. The apparatus of claim 9, wherein the processing device is further configured to instruct the backup cache node for the first cache node to delete the instance of the queried data when the instruction to delete the instance of the queried data is received at the first cache node.

11. The apparatus of claim 9, wherein the third cache node automatically inquires one or more other cache node in the cluster until it locates the instance of the queried data on the second cache node, and wherein inquiring the one or more other cache nodes is based on a per-invocation basis.

12. The apparatus of claim 9, wherein the cluster comprises a plurality of cache nodes, each cache node selecting one other cache node as a backup.

13. The apparatus of claim 9, wherein the cache nodes are located on different physical hosts.

14. The apparatus of claim 9, wherein the cache nodes are located on different physical racks.

15. The apparatus of claim 9, wherein one or more pools of cache nodes are formed in the cluster, wherein an instance of a cache node from a pool is replicated to one cache node in the same pool.

16. The apparatus of claim 15, wherein the cache nodes from a pool are located on different physical racks.

17. A non-transitory computer-readable storage medium, having instructions stored therein, which when executed, cause a computer system to perform a method comprising:

determining, by a first cache node in a tree-structured cluster of cache nodes, that a second cache node in the tree-structured cluster of cache nodes has failed, wherein the first cache node is a backup cache node for the second cache node and stores data of the second cache node as backup data;

taking ownership, by the first cache node, of the data of the second cache node by treating the second cache node data as primary data of the first cache node, wherein a backup cache node for the first cache node stores the second cache node data as backup data for the first cache node in addition to backup data already stored for the first cache node at the backup cache node for the first cache node;

receiving, by the first cache node, a query for the second cache node data from a third cache node in the tree-structured cluster of cache nodes;

replicating, by the first cache node, an instance of the queried second cache node data to the third cache node; and

removing, by the first cache node, the instance of the queried data from the primary data of the first cache node in response to an instruction to delete the instance of the queried data, wherein the third cache node acts as primary owner of the instance of the queried data once it is replicated to the third cache node;

wherein a memory usage for each node in the tree-structured cluster of cache nodes is (b+1)X, where X is the average data size for each node and b is the number of buddies per node.

18. The non-transitory computer-readable storage medium of claim 17 wherein the method further comprises instructing the backup cache node for the first cache node to delete the instance of the queried data when the instruction to delete the instance of the queried data is received at the first cache node.

19. The non-transitory computer-readable storage medium of claim 17, wherein the third cache node automatically inquires one or more other cache node in the cluster until it locates the instance of the queried data on the second cache node, and wherein inquiring the one or more other cache nodes is based on a per-invocation basis.

20. The non-transitory computer-readable storage medium of claim 17, wherein the cluster comprises a plurality of cache nodes, each cache node selecting one other cache node as a backup.

21. The non-transitory computer-readable storage medium of claim 17, wherein the cache nodes are located on different physical hosts.

22. The non-transitory computer-readable storage medium of claim 17, wherein the cache nodes are located on different physical racks.

23. The non-transitory computer-readable storage medium of claim 17, wherein one or more pools of cache nodes are formed in the cluster, wherein an instance of a cache node from a pool is replicated to one cache node in the same pool.

24. The non-transitory computer-readable storage medium of claim 23, wherein the cache nodes from a pool are located on different physical racks.