US6363396B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Object hashing with incremental changes
Assignee: Oracle International Corp
•
Filing: 1998-12-21
•
Granted: 2002-03-26
•
Expires: 2018-12-21
Abstract
Abstract A method and system are provided for reconfiguring a multiple node system after an epoch change in a manner that reduces the overhead and system unavailability typically incurred during reconfiguration. A resource-to-master mapping is established using the combination of a resource-to-bucket hash function and a bucket-to-node hash function. The resource-to-bucket hash function is not changed in response to an epoch change. The bucket-to-node hash function does change in response to epoch changes. Techniques are disclosed for adjusting the dynamic bucket-to-node hash function after an epoch change in a manner that load balances among the new number of nodes in the system. Further, the changes to the bucket-to-node assignments are performed in a way that reduces the number of resources that have to be remastered. In one embodiment, only those resources that lose their masters during an epoch change are assigned new masters during an initial reconfiguration. Load balancing is then gradually achieved by migrating resources after the system has been made available. The old masters of resources forward access requests to new masters of resources once they have transferred the master resource objects for the requested resources. In addition, techniques are disclosed for migrating resources from a node in anticipation of a planned shutdown of the node.
Inventors
- 👤 Boris Klots
- 👤 Roger J. Bamford
- 👤 Jeffrey Fischer
- 👤 Ravi Mirchandaney
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 17:15
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52; G06F16/00; G06F16/90; G06F16/901; G06F16/9014; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
89 words
A method for mastering resources to nodes in a multiple node system, the method comprising the steps of: for each resource in a set of resources, selecting a node to master the resource by mapping the resource to a specific hash bucket using a first hash function; mapping the specific hash bucket to a specific node using a second hash function; selecting said specific node to be master of said resource; and responding to an epoch change by modifying said second hash function without modifying said first hash function.
Claim 2
Independent Claim
89 words
A method for mastering resources to nodes in a multiple node system, the method comprising the steps of: for each resource in a set of resources, selecting a node to master the resource by mapping the resource to a specific hash bucket using a first hash function; mapping the specific hash bucket to a specific node using a second hash function; selecting said specific node to be master of said resource; and responding to an epoch change by modifying said second hash function without modifying said first hash function.
Claim 3
Dependent Claim
82 words
The method of claim 1 wherein: prior to the epoch change, a first number of nodes are used to master resources from said set of resources; after the epoch change, a second number of nodes are used to master resources from said set of resources; the method includes the step of using said first hash function to hash resources to a certain number of buckets, wherein said certain number of buckets is greater than both said first number and said second number.
Claim 4
Dependent Claim
37 words
The method of claim 1 wherein: said second hash function is implemented using bucket-to-node mapping information; and the step of modifying said second hash function comprises modifying one or more bucket-to-node mappings within said bucket-to-node mapping information.
Claim 5
Dependent Claim
48 words
The method of claim 3 wherein: each node of a plurality of nodes maintains a local copy of the bucket-to-node mapping information; and the step of modifying one or more bucket-to-node mappings within said bucket-to-node mapping information is performed in parallel at each of said plurality of nodes.
Claim 6
Dependent Claim
52 words
The method of claim 4 wherein the step of modifying said one or more bucket-to-node mappings is performed by applying a set of rules that generate a deterministic result based on the bucket-to-node mapping prior to the epoch change and how many nodes are available to master resources after the epoch change.
Claim 7
Dependent Claim
163 words
The method of claim 3 wherein the step of modifying one or more bucket-to-node mappings includes the steps of: determining a target bucket count based on how many of hash buckets are associated with said first hash function and how many nodes are available to master resources after the epoch change; if a particular node is available for mastering resources after the epoch change, then after the epoch change performing the steps of if more than the target bucket count of buckets were mapped to the particular node before the epoch change, then revising the bucket-to-node information to map one or more buckets that were mapped to the particular node before the epoch change to a different node; if less than the target bucket count of buckets were mapped to the particular node before the epoch change, then revising the bucket-to-node information to map one or more buckets that were mapped to a different node before the epoch change to the particular node.
Claim 8
Dependent Claim
98 words
The method of claim 1 wherein the step of modifying said second hash function includes the steps of: performing an initial reconfiguration after said epoch change, said initial reconfiguration including the step of remapping to nodes that exist after the epoch change a set of buckets that were mapped to nodes that were removed during the epoch change; after performing said initial reconfiguration, performing the steps of making the multiple node system generally available; and while the multiple node system is generally available, migrating to a deficit node one or more buckets currently mapped to a surplus node.
Claim 9
Dependent Claim
70 words
The method of claim 7 wherein the step of migrating includes the steps of: the surplus node sending to the deficit node resource information required for mastering resources that map to said one or more buckets; and after sending said resource information, the surplus node forwarding to said deficit node requests received by said surplus node that are related to said resources that map to said one or more buckets.
Claim 10
Dependent Claim
68 words
The method of claim 8 further comprising the steps of: the deficit node broadcasting to a set of nodes a message indicating that said deficit node is master of said resources that map to said one or more buckets; and the nodes in said set of nodes responding to said message by modifying said second hash function to map said one or more buckets to said deficit node.
Claim 11
Independent Claim
70 words
A method for remastering resources that are currently mastered on a node that is going to be removed from a multiple node system during an epoch change, the method comprising the steps of: the node sending to another node resource information required for mastering said resources; and after sending said resource information, the node forwarding to said other node requests received by said node that are related to said resources.
Claim 12
Independent Claim
70 words
A method for remastering resources that are currently mastered on a node that is going to be removed from a multiple node system during an epoch change, the method comprising the steps of: the node sending to another node resource information required for mastering said resources; and after sending said resource information, the node forwarding to said other node requests received by said node that are related to said resources.
Claim 13
Dependent Claim
73 words
The method of claim 10 wherein: the resources map to a hash bucket associated with a first hash function; the hash bucket maps to said node based on a second hash function; after receiving said resource information, said other node sends a message that said other node is master of said resources; and in response to said message, the second hash function is modified to map said hash bucket to said other node.
Claim 14
Dependent Claim
43 words
The method of claim 11 wherein: the other node broadcasts said message to a plurality of nodes; and the second hash function is modified by causing each node of said plurality of nodes to modify bucket-to-node mapping information maintained at said each node.
Claim 15
Dependent Claim
99 words
A computer-readable medium carrying sequences of instructions for mastering resources to nodes in a multiple node system, the sequences of instructions including instructions for performing the steps of: for each resource in a set of resources, selecting a node to master the resource by mapping the resource to a specific hash bucket using a first hash function; mapping the specific hash bucket to a specific node using a second hash function; selecting said specific node to be master of said resource; and responding to an epoch change by modifying said second hash function without modifying said first hash function.
Claim 16
Dependent Claim
99 words
A computer-readable medium carrying sequences of instructions for mastering resources to nodes in a multiple node system, the sequences of instructions including instructions for performing the steps of: for each resource in a set of resources, selecting a node to master the resource by mapping the resource to a specific hash bucket using a first hash function; mapping the specific hash bucket to a specific node using a second hash function; selecting said specific node to be master of said resource; and responding to an epoch change by modifying said second hash function without modifying said first hash function.
Claim 17
Dependent Claim
87 words
The computer-readable medium of claim 13 wherein: prior to the epoch change, a first number of nodes are used to master resources from said set of resources; after the epoch change, a second number of nodes are used to master resources from said set of resources; the computer-readable medium includes instructions for performing the step of using said first hash function to hash resources to a certain number of buckets, wherein said certain number of buckets is greater than both said first number and said second number.
Claim 18
Dependent Claim
38 words
The computer-readable medium of claim 13 wherein: said second hash function is implemented using bucket-to-node mapping information; and the step of modifying said second hash function comprises modifying one or more bucket-to-node mappings within said bucket-to-node mapping information.
Claim 19
Dependent Claim
49 words
The computer-readable medium of claim 15 wherein: each node of a plurality of nodes maintains a local copy of the bucket-to-node mapping information; and the step of modifying one or more bucket-to-node mappings within said bucket-to-node mapping information is performed in parallel at each of said plurality of nodes.
Claim 20
Dependent Claim
53 words
The computer-readable medium of claim 16 wherein the step of modifying said one or more bucket-to-node mappings is performed by applying a set of rules that generate a deterministic result based on the bucket-to-node mapping prior to the epoch change and how many nodes are available to master resources after the epoch change.
Claim 21
Dependent Claim
164 words
The computer-readable medium of claim 15 wherein the step of modifying one or more bucket-to-node mappings includes the steps of: determining a target bucket count based on how many of hash buckets are associated with said first hash function and how many nodes are available to master resources after the epoch change; if a particular node is available for mastering resources after the epoch change, then after the epoch change performing the steps of if more than the target bucket count of buckets were mapped to the particular node before the epoch change, then revising the bucket-to-node information to map one or more buckets that were mapped to the particular node before the epoch change to a different node; if less than the target bucket count of buckets were mapped to the particular node before the epoch change, then revising the bucket-to-node information to map one or more buckets that were mapped to a different node before the epoch change to the particular node.
Claim 22
Dependent Claim
99 words
The computer-readable medium of claim 13 wherein the step of modifying said second hash function includes the steps of: performing an initial reconfiguration after said epoch change, said initial reconfiguration including the step of remapping to nodes that exist after the epoch change a set of buckets that were mapped to nodes that were removed during the epoch change; after performing said initial reconfiguration, performing the steps of making the multiple node system generally available; and while the multiple node system is generally available, migrating to a deficit node one or more buckets currently mapped to a surplus node.
Claim 23
Dependent Claim
71 words
The computer-readable medium of claim 19 wherein the step of migrating includes the steps of: the surplus node sending to the deficit node resource information required for mastering resources that map to said one or more buckets; and after sending said resource information, the surplus node forwarding to said deficit node requests received by said surplus node that are related to said resources that map to said one or more buckets.
Claim 24
Dependent Claim
72 words
The computer-readable medium of claim 20 further comprising instructions for performing the steps of: the deficit node broadcasting to a set of nodes a message indicating that said deficit node is master of said resources that map to said one or more buckets; and the nodes in said set of nodes responding to said message by modifying said second hash function to map said one or more buckets to said deficit node.
Claim 25
Dependent Claim
78 words
A computer-readable medium carrying sequences for remastering resources that are currently mastered on a node that is going to be removed from a multiple node system during an epoch change, the sequences of instructions comprising instructions for performing the steps of: the node sending to another node resource information required for mastering said resources; and after sending said resource information, the node forwarding to said other node requests received by said node that are related to said resources.
Claim 26
Dependent Claim
78 words
A computer-readable medium carrying sequences for remastering resources that are currently mastered on a node that is going to be removed from a multiple node system during an epoch change, the sequences of instructions comprising instructions for performing the steps of: the node sending to another node resource information required for mastering said resources; and after sending said resource information, the node forwarding to said other node requests received by said node that are related to said resources.
Claim 27
Dependent Claim
74 words
The computer-readable medium of claim 22 wherein: the resources map to a hash bucket associated with a first hash function; the hash bucket maps to said node based on a second hash function; after receiving said resource information, said other node sends a message that said other node is master of said resources; and in response to said message, the second hash function is modified to map said hash bucket to said other node.
Claim 28
Dependent Claim
44 words
The computer-readable medium of claim 23 wherein: the other node broadcasts said message to a plurality of nodes; and the second hash function is modified by causing each node of said plurality of nodes to modify bucket-to-node mapping information maintained at said each node.
References Cited (Backward Citations)
US5202971A
Cited
US5060144A
Cited
US5287521A
Cited
US5161227A
Cited
US5551046A
Cited
US5408653A
Cited
US5403639A
Cited
US5452447A
Cited
US5612865A
Cited
US5970495A
Cited
US5892945A
Cited
US6026293A
Cited
US5963960A
Cited
US5893086A
Cited
US6023706A
Cited
US6292795B1
Cited
US6144983A
Cited
US6173313B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-03-25 | 2005-09-24 | 2006-03-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-03-25 | 2009-09-24 | 2010-03-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-03-25 | 2013-09-24 | 2014-03-26 | $7700.00 | Window Closed / Lapsed |