Balanced Consistent Hashing for Distributed Resource Management
AssigneeSymantec Corporation
InventorsHarold B. Prince, JR., Balemurughan Kumaresan, Kai Chiu Wong
Life of this patent
Estimating the term…
Abstract
A method, system, computer-readable storage medium and apparatus for balanced and consistent placement of resource management responsibilities within a multi-computer environment, such as a cluster, that are both scalable and make efficient use of cluster resources are provided. Embodiments reduce the time that a cluster is unavailable due to redistribution of resource management responsibilities by reducing the amount of redistribution of those responsibilities among the surviving cluster members. Embodiments further provide redistribution of resource management responsibilities based upon relative capabilities of the remaining cluster nodes.
Claims20
A computer-implemented method for redistributing lock mastership, at least a portion of the method being performed by a computing system comprising at least one processor, the method comprising:
- identifying a set of discrete computing-resource portions;
- identifying a cluster of nodes, each node having lock mastership over a subset of the discrete computing-resource portions;
- identifying a cluster event, the cluster event requiring a redistribution of lock mastership;
- determining a new mastership load distribution to apply across the cluster of nodes;
- for each node in the cluster of nodes:
- deallocating, from the lock mastership of the node, a sufficient number of discrete computing-resource portions to arrive at a lock-mastership load for the node no higher than a target number for the node as indicated by the new mastership load distribution;
- identifying a set of deallocated discrete computing-resource portions;
- for each node in the cluster of nodes:
- allocating, to the lock mastership of the node, a sufficient number of discrete computing-resource portions from the set of deallocated discrete computing-resource portions to arrive at a lock-mastership load for the node no lower than the target number for the node as indicated by the new mastership load distribution.
A system for redistributing lock mastership comprising:
- a redistribution module programmed to:
- identify a set of discrete computing-resource portions;
- identify a cluster of nodes, each node having lock mastership over a subset of the discrete computing-resource portions;
- identify a cluster event, the cluster event requiring a redistribution of lock mastership;
- determine a new mastership load distribution to apply across the cluster of nodes;
- for each node in the cluster of nodes:
- deallocate, from the lock mastership of the node, a sufficient number of discrete computing-resource portions to arrive at a lock-mastership load for the node no higher than a target number for the node as indicated by the new mastership load distribution;
- identify a set of deallocated discrete computing-resource portions;
- for each node in the cluster of nodes:
- allocate, to the lock mastership of the node, a sufficient number of discrete computing-resource portions from the set of deallocated discrete computing-resource portions to arrive at a lock-mastership load for the node no lower than the target number for the node as indicated by the new mastership load distribution.
- one or more processors configured to execute the redistribution module.
The system of claim 19, wherein the group of discrete computing-resource parcels comprises all discrete computing-resource parcels that share a same hash value according to a hash function.
A computer-readable-storage medium comprising one or more computer-executable instructions that, when executed by a computing device, cause the computing device to:
- identify a set of discrete computing-resource portions;
- identify a cluster of nodes, each node having lock mastership over a subset of the discrete computing-resource portions;
- identify a cluster event, the cluster event requiring a redistribution of lock mastership;
- determine a new mastership load distribution to apply across the cluster of nodes;
- for each node in the cluster of nodes:
- deallocate, from the lock mastership of the node, a sufficient number of discrete computing-resource portions to arrive at a lock-mastership load for the node no higher than a target number for the node as indicated by the new mastership load distribution;
- identify a set of deallocated discrete computing-resource portions;
- for each node in the cluster of nodes:
- allocate, to the lock mastership of the node, a sufficient number of discrete computing-resource portions from the set of deallocated discrete computing-resource portions to arrive at a lock-mastership load for the node no lower than the target number for the node as indicated by the new mastership load distribution.
Dependencies are inferred from the claim text.