Data gravitation in a distributed-tree structure

• US 7,774,309 B2
• Filed: 11/19/2007
• Issued: 08/10/2010
• 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: Surtanl, Manik Ram, Greene, Jason Thomas
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US11/986,243
• Publication Number:
  US 20090132614A1
• Time in Patent Office: 995 Days
• Field of Search: 707200-204, 711/118
• US Class Current: 707/635
• 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;

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

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.

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:

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.

5. The computer-implemented method of claim 1 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.

6. 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.

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

a storage device comprising the cluster of cache nodes in a tree-based structure; and

a processing device coupled to the storage device, the processing device 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, to adjust the partition group to include the querying cache node as a member of the partition group, and 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.

8. The apparatus of claim 7 wherein the processing device 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.

9. The apparatus of claim 8 wherein the processing device 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.

10. The apparatus of claim 7 wherein the processing device 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.

11. The apparatus of claim 7 wherein the processing device 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.

12. The apparatus of claim 7 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.

13. A non-transitory computer-readable storage medium, having instructions stored therein, which when executed, cause a computer system to perform a 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,

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.

14. The non-transitory computer-readable storage medium of claim 13 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.

15. The non-transitory computer-readable storage medium of claim 14 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.

16. The non-transitory computer-readable storage medium of claim 13 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.

17. The non-transitory computer-readable storage medium of claim 13 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.

18. The non-transitory computer-readable storage medium of claim 13 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.