IP Library Granted Patent US 10,310,911
Granted Patent B2
US 10,310,911 · App. 14/657,592 · Granted Jun 4, 2019

Solver for cluster management system

Inventors: Albert Yen Shau (Sunnyvale, CA); Christopher Gianelloni (Santa Clara, CA); Derek Lewis Wood (Sunnyvale, CA); Jonathan Michael Gray (Hermosa Beach, CA); Nitin Motgi (Santa Clara, CA); Poorna Chandra Gowda Bannikkuppe Ramachandra (San Mateo, CA); Rohit Sarma Nistala (Torrance, CA)
Assignee: Google LLC
G06F9/5088G06F9/4881H04L67/10H04L67/1002H04L67/42H04L69/40
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 10,310,911
App. No.
14/657,592
Granted
Jun 4, 2019
Kind
B2
Abstract

A processing device receives a first cluster management operation request, wherein the first cluster management operation request is for a deployment operation of a first cluster and comprises a cluster template, a specified number of nodes to deploy and a configuration. The processing device determines a plurality of constraints from at least one of the cluster template or the configuration. The processing device deterministically solves for and outputs a first cluster layout comprising the specified number of nodes, each of the specified number of nodes comprising a hardware type, an image type and one or more services, wherein the first cluster layout satisfies the plurality of constraints.

Claims (77)

1. A method comprising:

receiving a first cluster management operation request, the first cluster management operation request being for a deployment operation of a first cluster and indicating a specified number of nodes and a cluster template, the cluster template being absent a cluster layout and comprising a plurality of constraints for determining a cluster layout;

deterministically solving, by a processing device, for a first cluster layout comprising the specified number of nodes, each of the specified number of nodes comprising a hardware type, an image type and one or more services, wherein the first cluster layout satisfies the plurality of constraints, and wherein the plurality of constraints specifies one or more hardware types for a node for each corresponding service of the one or more services that is installed on the node and one or more image types for the node for each corresponding service that is installed on the node;

outputting the first cluster layout; and

automatically deploying the first cluster in accordance with the first cluster layout.

2. The method of claim 1 , wherein:

a first constraint of the plurality of constraints defines, for a first service of the one or more services, one or more hardware types required for a node on which the first service is to be installed, one or more image types required for the node on which the first service is to be installed, and a quantity of instances of the first service to be deployed in the first cluster; and

a second constraint of the plurality of constraints defines, for the first service, at a third service that cannot coexist on the same node as the first service.

3. The method of claim 2 , wherein at least one of the one or more hardware types comprises a first hardware definition associated with a first provider and a second hardware definition associated with a second provider, and wherein the first hardware definition is used for a first node if the first provider is used to create the first node having the hardware type and the second hardware definition is used for the first node if the second provider is used to create the first node having the hardware type.

4. The method of claim 1 , further comprising:

receiving a second cluster management operation request to modify the first cluster, the second cluster management request comprising at least one of a modified cluster template or a different specified number of nodes;

determining whether the second cluster management operation will cause the first cluster layout to be modified; and

responsive to determining that the second cluster management operation will not cause the first cluster layout to be modified, performing the second cluster management operation without solving for a new cluster layout.

5. The method of claim 4 , further comprising performing the following responsive to determining that the second cluster management operation will cause the first cluster to deviate from the first cluster layout:

determining a new plurality of constraints from at least one of the cluster template or the modified cluster template;

defining a plurality of additional constraints from the first cluster layout;

deterministically solving for the new cluster layout, wherein the new cluster layout comprises the specified number of nodes or the different specified number of nodes, and wherein the new cluster layout satisfies the new plurality of constraints and the additional constraints; and

outputting the new cluster layout, wherein the first cluster is automatically updated in accordance with the new cluster layout.

6. The method of claim 1 , wherein deterministically solving for the first cluster layout comprises:

determining one or more valid service sets, each of the one or more valid service sets comprising one or more services that are permitted to be deployed together on a same node;

determining one or more valid node layouts using the one or more valid service sets, each of the one or more valid node layouts comprising a particular hardware type, a particular image type and a valid service set that is permitted to be deployed on a node having the particular hardware type and the particular image type; and

determining a combination of the one or more valid node layouts that satisfies the plurality of constraints and includes the specified number of nodes.

7. The method of claim 6 , wherein deterministically solving for the first cluster layout further comprises:

deterministically selecting the one or more valid node layouts to include in the combination based on at least one of a preferred image type or a preferred hardware type.

8. The method of claim 1 , wherein the first cluster is associated with a first tenant, the method further comprising:

receiving a second cluster management operation request to deploy or modify a second cluster associated with a second tenant, the second cluster management operation request comprising a second cluster template and a second specified number of nodes to deploy, wherein the first cluster template is not viewable by the second tenant and the second cluster template is not viewable by the first tenant; and

solving for a second cluster layout for the second cluster, wherein the first cluster and the first cluster layout are not viewable by the second tenant and the second cluster and the second cluster layout are not viewable by the first tenant.

9. A non-transitory computer readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to perform operations comprising:

receiving a first cluster management operation request, the first cluster management operation request being for a deployment operation of a first cluster and indicating a specified number of nodes and a cluster template, the cluster template being absent a cluster layout and comprising a plurality of constraints for determining a cluster layout;

deterministically solving, by the processing device, for a first cluster layout comprising the specified number of nodes, each of the specified number of nodes comprising a hardware type, an image type and one or more services, wherein the first cluster layout satisfies the plurality of constraints, and wherein the plurality of constraints specifies one or more hardware types for a node for each corresponding service of the one or more services that is installed on the node and one or more image types for the node for each corresponding service that is installed on the node;

outputting the first cluster layout; and

automatically deploying the first cluster in accordance with the first cluster layout.

10. The non-transitory computer readable storage medium of claim 9 , wherein:

a first constraint of the plurality of constraints defines, for a first service of the one or more services, one or more hardware types required for a node on which the first service is to be installed, one or more image types required for the node on which the first service is to be installed, and a quantity of instances of the first service to be deployed in the first cluster; and

a second constraint of the plurality of constraints defines, for the first service, at a third service that cannot coexist on the same node as the first service.

11. The non-transitory computer readable storage medium of claim 10 , wherein the first constraint further defines at least one of a first ratio indicating a minimum percentage of nodes in the cluster layout on which the first service must be installed or a second ratio indicating a maximum percentage of the nodes in the cluster layout on which the first service is allowed to be installed.

12. The non-transitory computer readable storage medium of claim 9 , the operations further comprising:

receiving a second cluster management operation request to modify the first cluster, the second cluster management request comprising at least one of a modified cluster template, a different specified number of nodes or a different configuration;

determining whether the second cluster management operation will cause the first cluster to deviate from the first cluster layout; and

responsive to determining that the second cluster management operation will not cause the first cluster to deviate from the first cluster layout, performing the second cluster management operation without solving for a new cluster layout.

13. The non-transitory computer readable storage medium of claim 12 , the operations further comprising performing the following responsive to determining that the second cluster management operation will cause the first cluster to deviate from the first cluster layout:

determining a new plurality of constraints from at least one of the cluster template, the modified cluster template or the different configuration;

defining a plurality of additional constraints from the first cluster layout;

deterministically solving for the new cluster layout, wherein the new cluster layout comprises the specified number of nodes or the different specified number of nodes, and wherein the new cluster layout satisfies the new plurality of constraints and the additional constraints; and

outputting the new cluster layout, wherein the first cluster is automatically updated in accordance with the new cluster layout.

14. The non-transitory computer readable storage medium of claim 9 , wherein deterministically solving for the first cluster layout comprises:

determining one or more valid service sets, each of the one or more valid service sets comprising one or more services that are permitted to be deployed together on a same node;

determining one or more valid node layouts using the one or more valid service sets, each of the one or more valid node layouts comprising a particular hardware type, a particular image type and a valid service set that is permitted to be deployed on a node having the particular hardware type and the particular image type; and

determining a combination of the one or more valid node layouts that satisfies the plurality of constraints and includes the specified number of nodes.

15. The non-transitory computer readable storage medium of claim 14 , wherein deterministically solving for the first cluster layout further comprises:

deterministically selecting the one or more valid node layouts to include in the combination based on at least one of a preferred image type or a preferred hardware type.

16. The non-transitory computer readable storage medium of claim 9 , wherein the first cluster is associated with a first tenant, the operations further comprising:

receiving a second cluster management operation request to deploy or modify a second cluster associated with a second tenant, the second cluster management operation request comprising a second cluster template, a second specified number of nodes to deploy and a configuration, wherein the first cluster template is not viewable by the second tenant and the second cluster template is not viewable by the first tenant; and solving for a second cluster layout for the second cluster, wherein the first cluster and the first cluster layout are not viewable by the second tenant and the second cluster and the second cluster layout are not viewable by the first tenant.

17. A computing device comprising:

a memory; and

a processing device coupled to the memory, the processing device to:

receive a first cluster management operation request, the first cluster management operation request being for a deployment operation of a first cluster and indicating a specified number of nodes and a cluster template, the cluster template being absent a cluster layout and comprising a plurality of constraints for determining a cluster layout;

deterministically solve for a first cluster layout comprising the specified number of nodes, each of the specified number of nodes comprising a hardware type, an image type and one or more services, wherein the first cluster layout satisfies the plurality of constraints, and wherein the plurality of constraints specifies one or more hardware types for a node for each corresponding service of the one or more services that is installed on the node and one or more image types for the node for each corresponding service that is installed on the node;

output the first cluster layout; and

automatically deploying the first cluster in accordance with the first cluster layout.

18. The computing device of claim 17 , wherein a first constraint of the plurality of constraints defines, for a first service of the one or more services:

one or more hardware types required for a node on which the first service is to be installed;

one or more image types required for the node on which the first service is to be installed;

a quantity of instances of the first service to be deployed in the first cluster; and at least one of a first ratio indicating a minimum percentage of nodes in the cluster layout on which the first service must be installed or a second ratio indicating a maximum percentage of the nodes in the cluster layout on which the first service is allowed to be installed.

19. The computing device of claim 17 , wherein the processing device is further to:

receive a second cluster management operation request to modify the first cluster, the second cluster management request comprising at least one of a modified cluster template, a different specified number of nodes or a particular configuration;

determine whether the second cluster management operation will cause the first cluster to deviate from the first cluster layout; and

responsive to determining that the second cluster management operation will not cause the first cluster to deviate from the first cluster layout, perform the second cluster management operation without solving for a new cluster layout.

20. The computing device of claim 19 , wherein the processing device is further to perform the following responsive to determining that the second cluster management operation will cause the first cluster to deviate from the first cluster layout:

determine a new plurality of constraints from at least one of the cluster template or the modified cluster template;

define a plurality of additional constraints from the first cluster layout;

deterministically solve for the new cluster layout, wherein the new cluster layout comprises the specified number of nodes or the different specified number of nodes, and wherein the new cluster layout satisfies the new plurality of constraints and the additional constraints; and

output the new cluster layout, wherein the first cluster is automatically updated in accordance with the new cluster layout.

21. The computing device of claim 17 , wherein deterministically solving for the first cluster layout comprises:

determining one or more valid service sets, each of the one or more valid service sets comprising one or more services that are permitted to be deployed together on a same node;

determining one or more valid node layouts using the one or more valid service sets, each of the one or more valid node layouts comprising a particular hardware type, a particular image type and a valid service set that is permitted to be deployed on a node having the particular hardware type and the particular image type; and

determining a combination of the one or more valid node layouts that satisfies the plurality of constraints and includes the specified number of nodes.

Assignments (3)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 28, 2018
From: CASK DATA, INC.
To: GOOGLE LLC
Reel/Frame 046729/0252 →
SECURITY INTEREST Recorded Jun 27, 2017
From: CASK DATA, INC.
To: SILICON VALLEY BANK
Reel/Frame 042830/0846 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 17, 2015
From: SHAU, ALBERT YEN; GIANELLONI, CHRISTOPHER; WOOD, DEREK LEWIS; GRAY, JONATHAN MICHAEL; MOTGI, NITIN; RAMACHANDRA, POORNA CHANDRA GOWDA BANNIKKUPPE; NISTALA, ROHIT SARMA
To: CASK DATA, INC.
Reel/Frame 035185/0617 →
Continuity (2)
Provisional Application 61953106 · Mar 14, 2014
Related Publication 20150264119A1 · Sep 17, 2015