Data gravitation in a distributed-tree structure

• US 20090132614A1
• Filed: 11/19/2007
• Published: 05/21/2009
• Est. Priority Date: 11/19/2007
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Surtani, Manik Ram, Greene, Jason Thomas
• Granted Patent: US 7,774,309 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

A method and apparatus for obtaining data from a cluster of cache nodes in a tree-based structure is disclosed. A querying cache node outside a partition group queries data of a cache node of the partition group. The partition group is made of one or more cache nodes of the cluster, where an instance of a cache node in the partition group is copied to each cache node in the partition group. The instance of the data of the cache nodes of the partition group is copied to the querying cache node. The partition group is adjusted to include the querying cache node as a member of the partition group.

Claims

1. A computer-implemented method for obtaining data from a cluster of cache nodes in a tree-based structure, the method comprising:

receiving a query for data of a cache node of a partition group from a querying cache node outside the partition group, the partition group comprising one or more cache nodes of the cluster, wherein an instance of a cache node in the partition group is copied to each cache node in the partition group;

copying the instance of the data of the cache nodes of the partition group to the querying cache node; and

adjusting the partition group to include the querying cache node as a member of the partition group.

2. The computer-implemented method of claim 1 further comprising:

querying a data backup of each node in the partition group; and

retaining the instance of the data from the cache node storing the data after the instance of the data has been copied to the querying cache node.

3. The computer-implemented method of claim 2 further comprising:

performing a cluster-wide flush block to prevent changes to the cache node;

selecting a single member of the partition group as a state provider, the state provider generating a state for the partition group;

transferring the state of the partition group to the querying cache node, wherein the state is applied directly to the querying cache node; and

releasing the cluster-wide flush block.

4. The computer-implemented method of claim 1 further comprising:

adjusting the membership size of the partition group based on a partition maintenance thread of the one or more node caches of the partition group,

wherein the partition maintenance thread comprises a hard upper membership size limit, a soft upper membership size limit, a hard lower membership size limit, a soft lower membership size limit, the limits defining how many copies of each data element can exist in the partition group.

5. The computer-implemented method of claim 4 further comprising:

removing a cache node from the partition group in response to the membership size of the partition group exceeding the hard upper membership size limit.

6. The computer-implemented method of claim 4 further comprising:

removing a cache node from the partition group in response to a distributed eviction initiated by an initiating cache node from the partition group.

7. The computer-implemented method of claim 1 wherein a metadata is associated with the partition group, the metadata comprising an identification of a region represented by the partition group and an identification of peer cache nodes in the partition group.

8. An apparatus for obtaining data from a cluster of cache nodes in a tree-based structure comprising:

a server configured to receive a query for data of a cache node of a partition group from a querying cache node outside the partition group, the partition group comprising one or more cache nodes of the cluster, wherein an instance of a cache node in the partition group is copied to each cache node in the partition group, to copy the instance of the data of the cache nodes of the partition group to the querying cache node, and to adjust the partition group to include the querying cache node as a member of the partition group.

9. The apparatus of claim 8 wherein the server is configured to query a data backup of each node in the partition group, and retain the instance of the data from the cache node storing the data after the instance of the data has been copied to the querying cache node.

10. The apparatus of claim 9 wherein the server is configured to further perform a cluster-wide flush block to prevent changes to the cache node, to select a single member of the partition group as a state provider, the state provider generating a state for the partition group, to transfer the state of the partition group to the querying cache node, wherein the state is applied directly to the querying cache node, to release the cluster-wide flush block.

11. The apparatus of claim 8 wherein the server is configured to adjust the membership size of the partition group based on a partition maintenance thread of the one or more node caches of the partition group,

wherein the partition maintenance thread comprises a hard upper membership size limit, a soft upper membership size limit, a hard lower membership size limit, a soft lower membership size limit, the limits defining how many copies of each data element can exist in the partition group.

12. The apparatus of claim 11 wherein the server is configured to remove a cache node from the partition group in response to the membership size of the partition group exceeding the hard upper membership size limit.

13. The apparatus of claim 11 wherein the server is configured to remove a cache node from the partition group in response to a distributed eviction initiated by an initiating cache node from the partition group.

14. The apparatus of claim 8 wherein a metadata is associated with the partition group, the metadata comprising an identification of a region represented by the partition group and an identification of peer cache nodes in the partition group.

15. An article of manufacture comprising:

a machine-accessible storage medium including data that, when accessed by a machine, cause the machine to perform a method for obtaining data from a cluster of cache nodes in a tree-based structure, the method comprising;

receiving a query for data of a cache node of a partition group from a querying cache node outside the partition group, the partition group comprising one or more cache nodes of the cluster, wherein an instance of the cache node in the partition group is copied to each cache node in the partition group;

copying the instance of the data of the cache nodes of the partition group to the querying cache node; and

adjusting the partition group to include the querying cache node as a member of the partition group.

16. The article of manufacture of claim 15 wherein the method further comprises:

querying a data backup of each node in the partition group; and

retaining the instance of the data from the cache node storing the data after the instance of the data has been copied to the querying cache node.

17. The article of manufacture of claim 16 wherein the method further comprises:

performing a cluster-wide flush block to prevent changes to the cache node;

selecting a single member of the partition group as a state provider, the state provider generating a state for the partition group;

transferring the state of the partition group to the querying cache node, wherein the state is applied directly to the querying cache node; and

releasing the cluster-wide flush block.

18. The article of manufacture of claim 15 wherein the method further comprises:

adjusting the membership size of the partition group based on a partition maintenance thread of the one or more node caches of the partition group,

wherein the partition maintenance thread comprises a hard upper membership size limit, a soft upper membership size limit, a hard lower membership size limit, a soft lower membership size limit, the limits defining how many copies of each data element can exist in the partition group.

19. The article of manufacture of claim 18 wherein the method further comprises:

removing a cache node from the partition group in response to the membership size of the partition group exceeding the hard upper membership size limit.

20. The article of manufacture of claim 18 wherein the method further comprises:

removing a cache node from the partition group in response to a distributed eviction initiated by an initiating cache node from the partition group.

21. The article of manufacture of claim 15 wherein a metadata is associated with the partition group, the metadata comprising an identification of a region represented by the partition group and an identification of peer cache nodes in the partition group.