Dynamic redistribution of a distributed memory index when individual nodes have different lookup indexes

• US 7,962,453 B2
• Filed: 11/30/2004
• Issued: 06/14/2011
• Est. Priority Date: 04/26/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chandrasekaran, Sashikanth
• Primary Examiner(s): Timblin; Robert
• Assistant Examiner(s): REYES, MARIELA D
• Application Number:
  US11/000,818
• Publication Number:
  US 20050240595A1
• Time in Patent Office: 2,387 Days
• Field of Search: 707/10, 707/640, 707/650, 707/653
• US Class Current: 707/650
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

Techniques for performing window-by-window remastering are described, in which the mechanism used by nodes to determine the resource-to-window mapping is separated from the mechanism used by the nodes to access resource information. For example, all nodes of a multiple-node system may use the same hash function to determine which resources are involved in a remastering window. However, the resource indexes employed by the nodes to access resource information need not use that same hash function. For example, in nodes where the resource indexes are hash indexes, different nodes may use different hash functions. Further, some or all of the nodes may use mechanisms other than hash indexes to access the resource information.

Claims

1. A method of redistributing responsibilities for resources in a multiple-node system, the method comprising the steps of:

each node of a plurality of nodes determining a window-resource mapping between resources mastered by said each node and a plurality of windows, each window of the plurality of windows corresponding to a separate set of resources for which responsibility is to be redistributed;

a first node using a first resource index to locate resource information related to the resources mastered by the first node;

wherein the first node is a particular node of the plurality of nodes;

a second node of the plurality of nodes using a second resource index to locate resource information related to resources mastered by the second node;

reassigning from the first node to the second node responsibility for only a first set of resources, wherein the first set of resources correspond to a first window of said plurality of windows and are the responsibility of said first node;

for each window of said plurality of windows that is not the first window, reassigning to a node of the multi-node system responsibility for only a set of resources corresponding to said each window, wherein the corresponding set of resources are the responsibility of said first node;

wherein the window-resource mapping is based on;

(a) a different type of index access structure than that used for the first resource index, or

(b) a window hash function, wherein;

the window hash function maps a resource to one of a number of windows of said plurality of windows;

the first resource index is a first hash index that uses a first hash function, and

the first hash function maps a resource to a first number of buckets,

wherein the number of windows is not a multiple or a factor of the first number of buckets.

2. The method of claim 1 wherein the first resource index is based on a b-tree index access structure.

3. The method of claim 1 wherein:

the first resource index is a first hash index that has a first hash table of a first size;

the window hash function is used by a window hash table of a second size;

the first size is different from the second size; and

the first size and the second size are selected independent of each other.

4. The method of claim 1 wherein:

the first resource index is a first hash index; and

the second resource index is not a hash index.

5. The method of claim 1 wherein:

the multiple-node system is a multiple-node database system;

the resources are resources managed by the database system; and

the particular node uses the resource index to access lock information associated with the resources for which the particular node is responsible.

6. The method of claim 5 wherein the resource index and the lock information are stored in volatile memory within the particular node.

7. The method of claim 1 wherein:

the multiple-node system is a multiple-node file system;

the resources include files managed by the file system; and

the particular node uses the resource index to access file information associated with the files for which the particular node is responsible.

8. The method of claim 1 wherein the first resource index is a name-value lookup directory.

9. The method of claim 1 wherein the step of redistributing responsibilities relating to resources between the plurality of nodes in the multiple-node system includes remastering the resources between the plurality of nodes.

10. The method of claim 1,

wherein the window hash function maps a resource to a window number given to a specific resource name;

and

wherein the first resource index determines the location of the resource information based on a specific resource name;

wherein the resource information includes information other than a window number or a master node identifier.

11. The method of claim 10, wherein the first resource index is a first hash index;

wherein the first hash index uses a location hash function determines the location of the resource information based on the specific resource name; and

wherein the location hash function is dependent on node-specific parameters.

12. The method of claim 11, further comprising:

wherein each of the plurality of nodes use different location hash functions.

13. The method of claim 10, further comprising:

wherein the location hash function locates and saves resource information for a given resource name in a look-up index.

14. The method of claim 1, wherein the window-resource mapping is based on a different type of index access structure than that used for the first resource index.

15. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform:

each node of a plurality of nodes determining a window-resource mapping between resources mastered by said each node and a plurality of windows, each window of the plurality of windows corresponding to a separate set of resources for which responsibility is to be redistributed;

a first node using a first resource index to locate resource information related to the resources mastered by the first node;

wherein the first node is a particular node of the plurality of nodes;

a second node of the plurality of nodes using a second resource index to locate resource information related to resources mastered by the second node;

reassigning from the first node to the second node responsibility for only a first set of resources, wherein the first set of resources correspond to a first window of said plurality of windows and are the responsibility of said first node;

for each window of said plurality of windows that is not the first window, reassigning to a node of the multi-node system responsibility for only a set of resources corresponding to said each window, wherein the corresponding set of resources are the responsibility of said first node;

wherein the window-resource mapping is based on;

(a) a different type of index access structure than that used for the first resource index, or

(b) a window hash function, wherein;

the window hash function maps a resource to one of a number of windows of said plurality of windows;

the first resource index is a first hash index that uses a first hash function, and

the first hash function maps a resource to a first number of buckets,

wherein the number of windows is not a multiple or a factor of the first number of buckets.

16. The non-transitory computer-readable storage medium of claim 15, wherein the first resource index is based on a b-tree index access structure.

17. The non-transitory computer-readable storage medium of claim 15, wherein:

the first resource index is a first hash index that has a first hash table of a first size;

the window hash function is used by a window hash table of a second size;

the first size is different from the second size; and

the first size and the second size are selected independent of each other.

18. The non-transitory computer-readable storage medium of claim 15, wherein:

the first resource index is a first hash index; and

the second resource index is not a hash index.

19. The non-transitory computer-readable storage medium of claim 15, wherein:

the multiple-node system is a multiple-node database system;

the resources are resources managed by the database system; and

the particular node uses the resource index to access lock information associated with the resources for which the particular node is responsible.

20. The non-transitory computer-readable storage medium of claim 19, wherein the resource index and the lock information are stored in volatile memory within the particular node.

21. The non-transitory computer-readable storage medium of claim 15, wherein:

the multiple-node system is a multiple-node file system;

the resources include files managed by the file system; and

the particular node uses the resource index to access file information associated with the files for which the particular node is responsible.

22. The non-transitory computer-readable storage medium of claim 15, wherein the first resource index is a name-value lookup directory.

23. The non-transitory computer-readable storage medium of claim 15, wherein the step of redistributing responsibilities relating to resources between the plurality of nodes in the multiple-node system includes remastering the resources between the plurality of nodes.

24. The non-transitory computer-readable storage medium of claim 15, wherein the window-resource mapping is based on a different type of index access structure than that used for the first resource index.