Dynamic hashing method for optimal distribution of locks within a clustered system

• US 5,612,865 A
• Filed: 06/01/1995
• Issued: 03/18/1997
• Est. Priority Date: 06/01/1995
• Status: Expired due to Term

• Current Assignee: SIOS Technology Corp. (SIOS Corp.)
• Original Assignee: NCR Corporation
• Inventors: Dasgupta, Ranjan
• Primary Examiner(s): Gordon, Paul P.
• Assistant Examiner(s): PRESLEY, KAREN
• Application Number:
  US08/456,435
• Time in Patent Office: 656 Days
• Field of Search: 364/184, 395/800, 395/600, 395/650
• US Class Current: 700/79
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method for redistributing the mastership of system resources among the processing nodes within the clustered computer system following a change in the system configuration, such as the failure of a processing node or the return to service of a failed processing node. The method includes the steps of: maintaining a set of hash buckets within each processing node; assigning each one of the resources to one of the hash buckets; and assigning a hash vector, determined through utilization of an N-way recursive algorithm, to each one of the hash buckets, each one of the hash vectors identifying the processing nodes within the clustered computer system in a predetermined sequence unique to the one of the hash buckets. Mastership of any system resource resides with the first processing node identified by the hash vector assigned to the hash bucket to which the system resource is assigned. Following the failure of a processing node, the method reassigns mastership of the system resources assigned to the set of hash buckets associated with a failed processing node the next processing node having an active state identified by the hash vector assigned to the set of hash buckets associated with the failed processing node. Mastership of the resources initially assigned to the set of hash buckets associated with the failed node is reassigned to the failed node upon return of the failed node to an active state.

Claims

1. In a clustered computer system including a network of processing nodes, resources shared by said processing nodes, and a distributed lock manager for coordinating processing activities within the clustered computer system, the improvement comprising a method for evenly distributing the mastership of said resources within a clustered computer system amongst the processing nodes, said method comprising the steps of:

maintaining a set of hash buckets within each processing node;

assigning each one of said resources to one of said hash buckets;

assigning a hash vector to each one of said hash buckets, each one of said hash vectors identifying said processing nodes in a predetermined sequence unique to said one of said hash buckets, mastership of the resources assigned to any one of said hash buckets residing with the first processing node identified by the hash vector assigned to said one of said hash buckets; and

reassigning mastership of the resources assigned to said set of hash buckets associated with one of said processing nodes following a failure of said one of said processing nodes to the next processing node having an active state identified by the hash vector assigned to said set of hash buckets associated with said failed processing node.

2. The method according to claim 1, wherein:

each one of said hash vectors identifies each one of said processing nodes within said clustered computer system, the sequence in which said processing nodes are identified being unique to each one of said hash vectors.

3. The method according to claim 2, wherein said hash vectors are determined through an N-way recursive algorithm, wherein N is the number of processing nodes within said clustered computer system.

4. The method according to claim 1, further including the step of:

reassigning mastership of the resources initially assigned to said set of hash buckets associated with said failed node to said failed node upon return of said failed node to an active state.

5. The method according to claim 1, wherein said hash vectors for a set of hash buckets associated with each one of said processing nodes are selected to evenly distribute the mastership of the resources assigned to said set of hash buckets associated with each one of said processing nodes to the processing nodes within said clustered computer system having an active state.