Techniques for decentralized load balancing

• US 10,146,593 B2
• Filed: 12/22/2017
• Issued: 12/04/2018
• Est. Priority Date: 02/17/2017
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Gong, Qing, Chen, Shianchin "Sam", Li, Zhiyong
• Primary Examiner(s): Zhao, Bing
• Application Number:
  US15/852,591
• Publication Number:
  US 20180239651A1
• Time in Patent Office: 347 Days
• Field of Search: None
• CPC Class Codes: G06F 11/2023 Failover techniques
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3423 where the assessed time is active or idle time
• CPC Class Codes: G06F 11/3433 for load management allocation of a server based on load conditions G06F9/505; load rebalancing G06F9/5083; redistributing the load in a network by a load balancer H04L67/1029
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/163 Server or database system
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Various embodiments are generally directed to decentralized load balancing in a host cluster utilized to coordinate performance of processing tasks in a workload, such as via service agents and/or host instances included in the host cluster, for instance. Some embodiments are particularly directed to a set of service agents on one or more host instances that utilize a shared cache to coordinate among themselves to automatically balance a workload without a centralized controller or a centralized load balancer. In one or more embodiments, a set of service agents may automatically and cooperatively balance a workload among themselves using the shared cache.

Claims

1. A system comprising:

a cluster having a plurality of host instances, each host instance in the cluster, includes a processor and memory, to implement one or more service agents, the one or more service agents to perform tasks included in a workload;

a shared cache utilized by the one or more service agents of the plurality of hosts instances to automatically balance processing of the tasks in the workload among the host instances in the cluster without a centralized controller or a load balancer;

a first service agent of the one or more service agents implemented by a first host instance in the cluster of host instances to perform a task in the workload based on a data structure in the shared cache that indicates the first service agent is an active agent for the task;

a second service agent of the one or more service agents implemented by a second host instance in the cluster of host instances to;

transition from a sleep state to an active state in response to expiration of a timer;

identify a number of active service agents associated with the first host instance based on the data structure in the shared cache;

compute a difference between the number of active service agents associated with the first host instance and a number of active service agents associated with the second host instance;

compare the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance to a load difference threshold, wherein the load difference threshold is a numerical value determined based on a comparison of processing capabilities of hardware resources available to the first host instance to processing capabilities of hardware resources available to the second host instance; and

update the data structure in the shared cache to indicate that the second service agent is the active agent for the task when the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance exceeds the load difference threshold, the update to the data structure in the shared cache to reduce a portion of the workload performed by the first service agent of the one or more service agents implemented by the first host instance in the cluster of host instances.

2. The system of claim 1, wherein the first host instance and the second host instance have local access to a synchronized copy of the shared cached.

3. The system of claim 1, wherein the second service agent initializes a timer and transitions into the sleep state when the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance does not exceed the load difference threshold.

4. The system of claim 1, wherein the second service agent performs a second task in the workload and updates a timestamp in the shared cached to a current time based on performance of the second task.

5. The system of claim 4, wherein the data structure includes an association between the timestamp and a type of the task.

6. The system of claim 1, the first service agent comprising a metric collecting agent and wherein the task includes a portion of a resource metric collection service that monitors dynamic metrics associated with health of a software system.

7. The system of claim 1, wherein the first service agent updates a timestamp in the shared cached to indicate completion of the task.

8. The system of claim 1, wherein the first service agent identifies the task for performance based on a task queue in the shared cache.

9. The system of claim 1, wherein the load difference is set to zero based on the comparison indicating the processing capabilities of the hardware resources available to the first host instance are equal to the processing capabilities of the hardware resources available to the second host instance.

10. A computer-implemented method, comprising:

implementing one or more service agents with each host instance in a cluster having a plurality of host instances, the one or more service agents to perform tasks included in a workload;

utilizing a shared cache with the one or more service agents of the plurality of hosts instances to automatically balance processing of the tasks in the workload among the host instances in the cluster without a centralized controller or a load balancer;

performing a task in the workload with a first service agent based on a data structure in the shared cache that indicates the first service agent is an active agent for the task, the first service agent of the one or more service agents implemented by a first host instance in the cluster of host instances;

implementing a second service agent of the one or more service agents with a second host instance in the cluster of host instances, the second service agent for;

transitioning from a sleep state to an active state in response to expiration of a timer;

identifying a number of active service agents associated with the first host instance based on the data structure in the shared cache;

computing a difference between the number of active service agents associated with the first host instance and a number of active service agents associated with the second host instance;

comparing the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance to a load difference threshold, wherein the load difference threshold is a numerical value determined based on a comparison of processing capabilities of hardware resources available to the first host instance to processing capabilities of hardware resources available to the second host instance; and

updating the data structure in the shared cache to indicate that the second service agent is the active agent for the task when the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance exceeds the load difference threshold, the update to the data structure in the shared cache to reduce a portion of the workload performed by the first service agent of the one or more service agents implemented by the first host instance in the cluster of host instances.

11. The computer-implemented method of claim 10, wherein the first host instance and the second host instance have local access to a synchronized copy of the shared cached.

12. The computer-implemented method of claim 10, wherein the second service agent initializes a timer and transitions into the sleep state when the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance does not exceed the load difference threshold.

13. The computer-implemented method of claim 10, wherein the second service agent performs a second task in the workload and updates a timestamp in the shared cached to a current time based on performance of the second task.

14. The computer-implemented method of claim 13, wherein the data structure includes an association between the timestamp and a type of the task.

15. The computer-implemented method of claim 10, the first service agent comprising a metric collecting agent and wherein the task includes a portion of a resource metric collection service that monitors dynamic metrics associated with health of a software system.

16. The computer-implemented method of claim 10, wherein the first service agent updates a timestamp in the shared cached to indicate completion of the task.

17. The computer-implemented method of claim 10, wherein the first service agent identifies the task for performance based on a task queue in the shared cache.

18. The computer-implemented method of claim 10, wherein the load difference is set to zero based on the comparison indicating the processing capabilities of the hardware resources available to the first host instance are equal to the processing capabilities of the hardware resources available to the second host instance.

19. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, the computer-program product including instructions operable to cause a processor to perform operations comprising:

implement one or more service agents with each host instance in a cluster having a plurality of host instances, the one or more service agents to perform tasks included in a workload;

utilize a shared cache with the one or more service agents of the plurality of hosts instances to automatically balance processing of the tasks in the workload among the host instances in the cluster without a centralized controller or a load balancer;

perform a task in the workload with a first service agent based on a data structure in the shared cache that indicates the first service agent is an active agent for the task, the first service agent of the one or more service agents implemented by a first host instance in the cluster of host instances;

implement a second service agent of the one or more service agents with a second host instance in the cluster of host instances, the second service agent to;

transition from a sleep state to an active state in response to expiration of a timer;

identify a number of active service agents associated with the first host instance based on the data structure in the shared cache;

compute a difference between the number of active service agents associated with the first host instance and a number of active service agents associated with the second host instance;

compare the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance to a load difference threshold, wherein the load difference threshold is a numerical value determined based on a comparison of processing capabilities of hardware resources available to the first host instance to processing capabilities of hardware resources available to the second host instance; and

update the data structure in the shared cache to indicate that the second service agent is the active agent for the task when the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance exceeds the load difference threshold, the update to the data structure in the shared cache to reduce a portion of the workload performed by the first service agent of the one or more service agents implemented by the first host instance in the cluster of host instances.

20. The computer-program product of claim 19, wherein the first host instance and the second host instance have local access to a synchronized copy of the shared cached.

21. The computer-program product of claim 19, wherein the second service agent initializes a timer and transitions into the sleep state when the difference between the number of active service agents associated with the first host instance and the number of active service agents associated with the second host instance does not exceed the load difference threshold.

22. The computer-program product of claim 19, wherein the second service agent performs a second task in the workload and updates a timestamp in the shared cached to a current time based on performance of the second task.

23. The computer-program product of claim 22, wherein the data structure includes an association between the timestamp and a type of the task.

24. The computer-program product of claim 19, the first service agent comprising a metric collecting agent and wherein the task includes a portion of a resource metric collection service that monitors dynamic metrics associated with health of a software system.

25. The computer-program product of claim 19, wherein the first service agent updates a timestamp in the shared cached to indicate completion of the task.

26. The computer-program product of claim 19, wherein the first service agent identifies the task for performance based on a task queue in the shared cache.

27. The computer-program product of claim 19, wherein the load difference is set to zero based on the comparison indicating the processing capabilities of the hardware resources available to the first host instance are equal to the processing capabilities of the hardware resources available to the second host instance.