Efficient movement of virtual nodes during reconfiguration of computing cluster

Patent metadata

Field	Value
Publication number	US-10534652-B1
Application number	US-201715638015-A
Country	US
Kind code	B1
Filing date	Jun 29, 2017
Priority date	Jun 29, 2017
Publication date	Jan 14, 2020
Grant date	Jan 14, 2020

Abstract

Given a current configuration of virtual node groups in a computing cluster and a new configuration indicating one or more changes to the virtual node groups, a cluster manager generates a reconfiguration plan to arrange virtual nodes into the desired virtual node groups of the new configuration while minimizing a number of virtual nodes to be moved between physical nodes in the computing cluster.

First claim

What is claimed is:

1. A method comprising:
identifying one or more virtual node groups associated with a computing cluster comprising a plurality of physical nodes, wherein each of the one or more virtual node groups comprises one or more virtual nodes associated with a corresponding one of the plurality of physical nodes;
receiving a new configuration of the computing cluster, the new configuration comprising an indication of one or more changes to the one or more virtual node groups associated with the computing cluster; and
determining, by a processor, a reconfiguration plan to reassign one or more of the virtual nodes from at least one of the one or more virtual node groups to a different virtual node group to effect the one or more changes while minimizing a number of virtual nodes to be moved between physical nodes.

2. The method of claim 1 , wherein the new configuration is defined by at least one of a customer or a system administrator.

3. The method of claim 2 , wherein the new configuration comprises at least one of an additional of a new physical node to the computing cluster or a removal of an existing physical node from the computing cluster.

4. The method of claim 1 , wherein determining the reconfiguration plan comprises:
generating a data structure with a plurality of elements, wherein each element represents a number of virtual nodes that would be retained if a corresponding existing virtual node group was matched to a corresponding new virtual node group; and
converting the data structure to a square data structure.

5. The method of claim 4 , wherein determining the reconfiguration plan further comprises:
subtracting each of the plurality of elements in the data structure from the value of the largest element in the data structure; and
reducing the data structure by subtracting the value of the smallest element in each row and column of the data structure from each other element in the corresponding row and column.

6. The method of claim 5 , wherein determining the reconfiguration plan further comprises:
determining a minimum number of straight lines that can be used to cross-off all of the zero elements in the data structure; and
identifying any rows or columns in the data structure that have only a single zero element.

7. The method of claim 1 , further comprising:
reassigning the virtual nodes among the virtual node groups according to the reconfiguration plan.

8. A system comprising:
one or more processors; and
memory to store computer-executable instructions that, if executed, cause the one or more processors to:
identify one or more virtual node groups associated with a computing cluster comprising a plurality of physical nodes, wherein each of the one or more virtual node groups comprises one or more virtual nodes associated with a corresponding one of the plurality of physical nodes;
receive a new configuration of the computing cluster, the new configuration comprising an indication of one or more changes to the one or more virtual node groups associated with the computing cluster;
determine a reconfiguration plan to reassign one or more of the virtual nodes from at least one of the one or more virtual node groups to a different virtual node group to effect the one or more changes while minimizing a number of virtual nodes to be moved between physical nodes; and
reassign the virtual nodes among the virtual node groups according to the reconfiguration plan.

9. The system of claim 8 , wherein the new configuration is defined by at least one of a customer or a system administrator.

10. The system of claim 9 , wherein the new configuration comprises at least one of an additional of a new physical node to the computing cluster or a removal of an existing physical node from the computing cluster.

11. The system of claim 8 , wherein to determine the reconfiguration plan, the one or more processors are configured to:
generate a data structure with a plurality of elements, wherein each element represents a number of virtual nodes that would be retained if a corresponding existing virtual node group was matched to a corresponding new virtual node group; and
convert the data structure to a square data structure.

12. The system of claim 11 , wherein to determine the reconfiguration plan, the one or more processors are configured to:
subtract each of the plurality of elements in the data structure from the value of the largest element in the data structure; and
reduce the data structure by subtracting the value of the smallest element in each row and column of the data structure from each other element in the corresponding row and column.

13. The system of claim 12 , wherein to determine the reconfiguration plan, the one or more processors are configured to:
determine a minimum number of straight lines that can be used to cross-off all of the zero elements in the data structure; and
identify any rows or columns in the data structure that have only a single zero element.

14. One or more non-transitory machine-readable mediums having stored therein instructions which, if performed by one or more processors, cause the one or more processors to:
identify one or more virtual node groups associated with a computing cluster comprising a plurality of physical nodes, wherein each of the one or more virtual node groups comprises one or more virtual nodes associated with a corresponding one of the plurality of physical nodes;
receive a new configuration of the computing cluster, the new configuration comprising an indication of one or more changes to the one or more virtual node groups associated with the computing cluster; and
reconfigure the computing cluster to reassign one or more of the virtual nodes from at least one of the one or more virtual node groups to a different virtual node group according to the one or more changes while minimizing a number of virtual nodes to be moved between physical nodes.

15. The one or more non-transitory machine-readable mediums of claim 14 , wherein the new configuration is defined by at least one of a customer or a system administrator, and wherein the new configuration comprises at least one of an additional of a new physical node to the computing cluster or a removal of an existing physical node from the computing cluster.

16. The one or more non-transitory machine-readable mediums of claim 14 , wherein to reconfigure the computing cluster, the one or more processors are configured to:
generate a data structure with a plurality of elements, wherein each element represents a number of virtual nodes that would be retained if a corresponding existing virtual node group was matched to a corresponding new virtual node group;
convert the data structure to a square data structure;
subtract each of the plurality of elements in the data structure from the value of the largest element in the data structure;
reduce the data structure by subtracting the value of the smallest element in each row and column of the data structure from each other element in the corresponding row and column;
determine a minimum number of straight lines that can be used to cross-off all of the zero elements in the data structure; and
identify any rows or columns in the data structure that have only a single zero element.

17. The one or more non-transitory machine-readable mediums of claim 16 , wherein to reconfigure the computing cluster, the one or more processors are configured to:
reassign the virtual nodes among the virtual node groups according to the rows and columns in the data structure that have only a single zero

Assignees

• Amazon Tech Inc

Inventors

• Dugar Rajib
• Manral Ashish
• Narayanan Ganesh

Classifications

• G06F9/5077 Primary

  Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455) · CPC title

• G06F9/5061

  Partitioning or combining of resources · CPC title

• G06F9/5088

  involving task migration · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• G06F9/5083

  Techniques for rebalancing the load in a distributed system · CPC title