Balanced consistent hashing for distributed resource management
View Patent ↗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.
1. A method comprising:
determining locations of a plurality of resource identifiers in a resource identification space, wherein
the determining is performed by a computer;
dividing the resource identification space into a first plurality of disjoint areas of responsibility, wherein
the dividing is performed by the computer;
associating each area of responsibility with a distinct network node of a plurality of network nodes, wherein
the associating is performed by the computer,
each network node of the plurality of network nodes is a member of a cluster, and
a sum of all the areas of responsibility encompasses the entire resource identification space;
assigning management responsibility for a resource associated with a resource identifier located in a first area of responsibility to a network node associated with the first area of responsibility, wherein
the assigning is performed by the computer,
the resource is shared by the network nodes, and
the assigning comprises distributing lock mastering responsibilities associated with the resource identifier to the network node associated with the first area of responsibility;
detecting that a first network node is added to or removed from the network;
performing said dividing and said assigning using a current number of network nodes available to be associated with an area of responsibility into a second plurality of areas of responsibility, in response to said detecting; and
maximizing an overlap of areas of responsibility between the first plurality of areas of responsibility and the second plurality of areas of responsibility.
2. The method of claim 1 wherein the resource identification space is a name space.
3. The method of claim 2 further comprising:
calculating a resource identifier of the plurality of resource identifiers by hashing a name of the resource.
4. The method of claim 3 further comprising:
deriving the name of the resource using an inode identifier, wherein the resource is one of a file and a storage location in a file system.
5. The method of claim 3 further comprising:
deriving the name of the resource using an electronic mail address, wherein
the resource is one of a mailbox, state information associated with the mailbox, metadata associated with the mailbox, management information associated with the mailbox, and mail data in an electronic mail system.
6. The method of claim 1 wherein a resource identified by one of the plurality of resource identifiers is accessible to all members of the cluster.
7. The method of claim 1 further comprising:
determining the area of responsibility for the associated network node based on a capability of the associated network node.
8. The method of claim 7 further comprising:
relating the capability of the associated network node to one or more of processor capacity and memory capacity.
9. The method of claim 7 further comprising:
defining the capability of the associated network node by user input.
10. The method of claim 7 wherein the capability of the associated network node is defined relative to each other network node of the plurality of network nodes.
11. A non-transitory computer-readable storage medium comprising:
a first set of instructions, executable by a processor, configured to determine locations of a plurality of resource identifiers in a resource identification space;
a second set of instructions, executable by the processor, configured to divide the resource identification space into a first plurality of disjoint areas of responsibility, and associate each area of responsibility with a distinct network node of a plurality of network nodes, wherein
each network node of the plurality of network nodes is a member of a cluster, and
a sum of all the areas of responsibility encompasses the entire resource identification space;
a third set of instructions, executable by the processor, configured to assign management responsibility for a resource associated with a resource identifier located in a first area of responsibility to a network node associated with the first area of responsibility, wherein
the resource is shared by the network nodes, and
the assigning comprises distributing lock mastering responsibilities associated with the resource identifier to the network node associated with the first area of responsibility; and
a fourth set of instructions, executable by the processor, configured to detect that a first network node is added to or removed from the network;
divide the resource identification space and assign management responsibility using a current number of network nodes available to be associated with an area of responsibility into a second plurality of areas of responsibility, in response to detect that first network node is added or removed from the network, and
maximize an overlap of areas of responsibility between the first plurality of areas of responsibility and the second plurality of areas of responsibility.
12. The non-transitory computer-readable storage medium of claim 11 wherein the resource identification space is a name space.
13. The non-transitory computer-readable storage medium of claim 12 further comprising:
a fifth set of instructions, executable by the processor, configured to calculate a resource identifier of the plurality of resource identifiers by hashing a name of the resource.
14. The non-transitory computer-readable storage medium of claim 11 further comprising:
a fifth set of instructions, executable by the processor, configured to determine the area of responsibility for the associated network node based on a capability of the associated network node.
15. A system comprising:
a plurality of network nodes, wherein
each network node of the plurality of network nodes comprises a corresponding processor, a memory coupled to the processor, and a network interface coupled to the processor, and
the memory of each network node stores
a first set of instructions, executable by the processor of the network node, configured to determine locations of a plurality of resource identifiers in a resource identification space,
a second set of instructions, executable by the processor of the network node, configured to divide the resource identification space into a first plurality of disjoint areas of responsibility, and associate each area of responsibility with a distinct network node of the plurality of network nodes, wherein
each network node of the plurality of network nodes is a member of a cluster, and
a sum of all the areas of responsibility encompasses the entire resource identification space, and
a third set of instructions, executable by the processor of the network node, configured to assign management responsibility for a resource associated with a resource identifier located in a first area of responsibility to a network node associated with the first area of responsibility, wherein
the resource is shared by the network nodes, and
the assigning comprises distributing lock mastering responsibilities associated with the resource identifier to the network node associated with the first area of responsibility;
a fourth set of instructions, executable by the processor, configured to
detect that a first network node is added to or removed from the network;
divide the resource identification space and assign management responsibility using a current number of network nodes available to be associated with an area of responsibility into a second plurality of areas of responsibility, in response to detect that first network node is added or removed from the network, and
maximize an overlap of areas of responsibility between the first plurality of areas of responsibility and the second plurality of areas of responsibility; and
a network configured to couple the plurality of network nodes to one another wherein the network is coupled to the network interface of each network node.
16. The system of claim 15 wherein the memory of each network node further stores:
a fifth set of instructions, executable by the processor of the network node, configured to calculate a resource identifier of the plurality of resource identifiers by hashing a name of the resource, wherein the resource identification space is a name space.
17. The system of claim 15 wherein the memory of each network node further stores:
a fifth set of instructions, executable by the processor of the network node, configured to determine the area of responsibility for the associated network node based on a capability of the associated network node.
18. An apparatus comprising:
a network node of a plurality of network nodes, wherein
each network node of the plurality of network nodes is a member of a cluster;
means for determining locations of a plurality of resource identifiers in a resource identification space;
means for dividing the resource identification space into a first plurality of disjoint areas of responsibility, and associating each area of responsibility with a distinct network node, wherein
a sum of all the areas of responsibility encompasses the entire resource identification space;
means for assigning management responsibility for a resource associated with a resource identifier located in a first area of responsibility to a network node associated with the first area of responsibility, wherein
the resource is shared by the network nodes;
means for detecting that a first network node is added to or removed from the network;
means performing said dividing and said assigning using a current number of network nodes available to be associated with an area of responsibility into a second plurality of areas of responsibility, in response to said detecting; and
means for maximizing an overlap of areas of responsibility between the first plurality of areas of responsibility and the second plurality of areas of responsibility.
19. The method of claim 1 , further comprising:
the distinct network node sending a message to each other node in the cluster in response to a cluster restart, wherein
the cluster restart is performed in response to a cluster membership change.