Lock acquisition among node of divided cluster

Abstract

The acquisition of a lock among nodes of a divided cluster is disclosed. A method is performable by each of at least one node of the cluster. A node waits for a delay corresponding to its identifier. The node asserts intent to acquire the lock by writing its identifier to X and Y variables where another node has failed to acquire the lock. The node waits for another node to acquire the lock where the other node has written to X, and proceeds where Y remains equal to its own identifier. The node waits for another node to acquire the lock where the other node has written to a Z variable, and writes its own identifier to Z and proceeds where the other node has failed. The node writes a value to Y indicating that it is acquiring the lock, and maintains acquisition by periodically writing to Z.

1 . A method performable by each node of at least one node of a plurality of nodes of a divided cluster comprising, repeating a loop of:
 determining a value of a Z variable;   where the value of the Z variable is equal to a node identifier of another node,
 where the other node has acquired a lock, exiting the loop and failing to acquire the lock; 
 where the other node has failed to acquire the lock,
 writing a node identifier of the node to the Z variable; 
 waiting a predetermined time; 
 
   where the value of the Z variable is equal to the node identifier of the node and the other node has failed to acquire the lock, exiting the loop and beginning to acquire the lock.   
     
     
         2 . The method of  claim 1 , further comprising, after acquiring the lock, maintaining acquisition of the lock by periodically writing to the Z variable. 
     
     
         3 . The method of  claim 1 , wherein waiting for the delay comprises:
 where the other node has acquired the lock or the other node is itself waiting for the delay, setting the delay as an exponential delay corresponding to the node identifier of the node and multiplied by a constant; and,   where the other node has failed to acquire the lock and the other node is itself not waiting for the delay, setting the delay as a multiple of the constant.   
     
     
         4 . The method of  claim 3 , wherein determining the value of the Z variable comprises incrementing a loop counter, and wherein setting the delay as the exponential delay corresponding to the node identifier of the node and multiplied by the constant comprises setting the delay as the exponential delay corresponding to the node identifier of the node, multiplied by the constant, and multiplied by a value of the counter. 
     
     
         5 . A system comprising:
 a cluster of nodes divided into a plurality of groups, each group including at least one of the nodes; and,   a storage to which each node has communicative access and storing a plurality of variables written to by at least some of the nodes in accordance with a storage-based protocol for leadership of the cluster, comprising:
 an X variable to which node identifiers are stored by the nodes asserting intent to acquire leadership of the cluster and which is examined to determine whether the nodes should wait to allow another of the nodes to have a better chance of acquiring leadership of the cluster; 
 a Y variable to which node identifiers of the nodes are stored by the nodes asserting intent to acquire leadership of the cluster, and which is examined to determine whether the nodes should wait to allow another of the nodes to acquire leadership of the cluster; and, 
 a Z variable to which node identifiers are first stored by the nodes to begin acquiring leadership of the cluster and subsequently stored by one of the nodes that has acquired leadership of the cluster to maintain leadership of the cluster. 
   
     
     
         6 . The system of  claim 5 , wherein the cluster of nodes comprises a cluster of a first node and a second node, and the plurality of groups comprises a first group including the first node and a second group including the second node. 
     
     
         7 . The system of  claim 5 , wherein all of the nodes of the cluster participates in the storage-based protocol for leadership of the cluster. 
     
     
         8 . The system of  claim 5 , wherein one node from each group of the plurality of groups participates in the storage-based protocol for leadership of the cluster. 
     
     
         9 . The system of  claim 5 , wherein each node of the cluster of nodes is a server computing device. 
     
     
         10 . A server computing device comprising:
 a network communication mechanism to permit the server computing device to communicate with a first plurality of other server computing devices of a cluster, the server computing device being unable to communicate with a second plurality of other server computing devices of the cluster;   a processor; and,   a computer-readable medium having a computer program stored thereon executable by the processor to perform a storage-based protocol to determine leadership of the cluster by writing to a plurality of variables accessible throughout the cluster, and without sending node-to-node network messages throughout the cluster, and to maintain the leadership of the cluster if obtained by periodically writing to one of the plurality of variables.   
     
     
         11 . The server computing device of  claim 10 , wherein the cluster is divided into a plurality of groups of nodes, each group having an equal number of nodes. 
     
     
         12 . The server computing device of  claim 10 , wherein the plurality of variables comprises:
 an X variable to which node identifiers are stored by the nodes asserting intent to acquire leadership of the cluster and which is examined to determine whether the nodes should wait to allow another of the nodes to have a better chance of acquiring leadership of the cluster;   a Y variable to which node identifiers are stored by nodes asserting intent to acquire leadership of the cluster, to which a value is stored to indicating that one of the nodes is acquiring leadership of the cluster, and which is examined to determine whether the nodes should wait to allow another of the nodes to acquire leadership of the cluster; and,   a Z variable to which node identifiers are first stored by the nodes to begin acquiring leadership of the cluster and subsequently stored by one of the nodes that has acquired leadership of the cluster to maintain leadership of the cluster.   
     
     
         13 . An article of manufacture comprising:
 a computer-readable medium; and,   means in the medium for performing a storage-based protocol to determine node leadership of a cluster of nodes fragmented into a number of identically populated groups of nodes, and for maintaining leadership of the cluster if obtained by periodically writing to a variable.   
     
     
         14 . The article of manufacture of  claim 13 , wherein the storage-based protocol employs a plurality of variables comprising:
 a X variable to which node identifiers are stored by the nodes asserting intent to acquire leadership of the cluster and which is examined to determine whether the nodes should wait to allow another of the nodes to have a better chance of acquiring leadership of the cluster;   a Y variable to which node identifiers are stored by nodes asserting intent to acquire leadership of the cluster, to which a value is stored to indicating that one of the nodes is acquiring leadership of the cluster, and which is examined to determine whether the nodes should wait to allow another of the nodes to acquire leadership of the cluster; and,   a Z variable to which node identifiers are first stored by the nodes to begin acquiring leadership of the cluster and subsequently stored by one of the nodes that has acquired leadership of the cluster to maintain leadership of the cluster.   
     
     
         15 . The article of manufacture of  claim 13 , wherein each node of the cluster of nodes is a server.