Computing node job assignment using multiple schedulers

Patent metadata

Field	Value
Publication number	US-11068307-B2
Application number	US-201916580459-A
Country	US
Kind code	B2
Filing date	Sep 24, 2019
Priority date	Nov 14, 2018
Publication date	Jul 20, 2021
Grant date	Jul 20, 2021

Abstract

A set of computing nodes may receive a corresponding set of heartbeat messages that originated at the set of computing nodes. The set of heartbeat messages may relate to selecting, among the set of computing nodes, a leader computing node to process a set of jobs. State information included in the heartbeat messages may be provided to a leader election algorithm that outputs information indicating one or more computing nodes that are most qualified to process the set of jobs based on processing capabilities of the computing nodes and processing constraints associated with the set of jobs. The computing node may select itself as the leader computing node to process the set of jobs based on determining, from the information output by the leader election algorithm, that the computing node is most qualified to process the set of jobs and no other computing nodes are processing the set of jobs.

First claim

What is claimed is:

1. A method, comprising:
receiving, by a computing node included in a set of computing nodes, a set of heartbeat messages that originated from the set of computing nodes,
wherein the set of heartbeat messages is related to selecting, among the set of computing nodes, a leader computing node to process one or more jobs associated with the set of computing nodes,

determining, by the computing node and based on the set of heartbeat messages, a set of scores representing how qualified each computing node is to process the one or more jobs based on processing capabilities of corresponding computing nodes, of the set of computing nodes, and one or more processing constraints associated with the one or more jobs;
determining, by the computing node and based on the set of scores, whether the computing node is to be selected as the leader computing node based on whether a unique identifier associated with the computing node corresponds to a unique identifier in one of the set of heartbeat messages, of the set of heartbeat messages, associated with a highest score in the set of scores; and
selectively processing, by the computing node, the one or more jobs based on determining whether the computing node is to be selected as the leader computing node.

2. The method of claim 1 , wherein determining whether the computing node is to be selected as the leader computing node comprises:
determining that the computing node and one or more other computing nodes, included in the set of computing nodes, are tied for having the highest score in the set of scores; and
computing, for each heartbeat message in the set of heartbeat messages, a corresponding hash to break the tie between the computing node and the one or more other computing nodes,
wherein the corresponding hash for each respective heartbeat message is computed based on the unique identifier included in the respective heartbeat message and a time at which the respective heartbeat message was transmitted, and
wherein the computing node is selected as the leader computing node based on the corresponding hash associated with the heartbeat message transmitted by the computing node satisfying a condition.

3. The method of claim 2 , wherein the condition is satisfied when the corresponding hash for each respective heartbeat message transmitted by the computing node has a smallest value or a largest value as compared to hashes associated with heartbeat messages transmitted by the one or more other computing nodes that are tied with the computing node.

4. The method of claim 1 , wherein the one or more jobs include multiple jobs that are grouped together based on the one or more processing constraints.

5. The method of claim 1 , further comprising:
determining, by a scheduler instance executing on the computing node, the one or more jobs to be processed based on information contained in one or more data structures shared among the set of computing nodes.

6. The method of claim 1 , further comprising:
storing the set of heartbeat messages after receiving the set of heartbeat messages; and
expiring the set of heartbeat messages after determining whether the computing node is to be selected as the leader computing node.

7. The method of claim 1 , wherein transmissions of the set of heartbeat messages occur according to a periodicity, and wherein the determination of whether the computing node is to be selected as the leader computing node is performed according to the periodicity.

8. A computing node, comprising:
one or more memories; and
one or more processors communicatively coupled to the one or more memories, configured to:
receive a set of heartbeat messages that originated from a set of computing nodes,
wherein the set of heartbeat messages is related to selecting, among the set of computing nodes, a leader computing node to process one or more jobs associated with the set of computing nodes,

determine, based on the set of heartbeat messages, a set of scores representing how qualified each computing node is to process the one or more jobs based on processing capabilities of corresponding computing nodes, of the set of computing nodes, and one or more processing constraints associated with the one or more jobs;
determine, based on the set of scores, whether the computing node is to be selected as the leader computing node based on:
whether the computing node is most qualified to process the one or more jobs as compared to other computing nodes included in the set of computing nodes, and

whether the one or more jobs are being processed by any other computing node included in the set of computing nodes; and

selectively process the one or more jobs based on determining whether the computing node is to be selected as the leader computing node.

9. The computing node of claim 8 , wherein a heartbeat message further indicates, for the computing node, one or more unique identifiers associated with the computing node.

10. The computing node of claim 9 , wherein the one or more processors, when determining whether the computing node is to be selected as the leader computing node, are configured to:
generate a list of unique identifiers corresponding to the set of computing nodes,
wherein the list is sorted based on:
the set of scores representing how qualified each computing node is to process the one or more jobs, and
a hash based on the unique identifiers corresponding to the set of computing nodes in combination with a time at which the set of heartbeat messages were transmitted by the set of computing nodes; and

determine whether the computing node is to be selected as the leader computing node based on the list.

11. The computing node of claim 9 , wherein transmissions of the set of heartbeat messages occur according to a periodicity, and
wherein the one or more processors, when determining whether the computing node is to be selected as the leader computing node, are to:
determine whether the computing node is to be selected as the leader computing node based on the periodicity.

12. The computing node of claim 8 , wherein the one or more processors, when selectively processing the one or more jobs, are configured to:
process the one or more jobs based on determining that the computing node is most qualified to process the one or more jobs as compared to the other computing nodes and that the one or more jobs are not being processed by any other computing node included in the set of computing nodes, or
refrain from processing the one or more jobs based on determining that:
one or more of the other computing nodes are more qualified to process the one or more jobs as compared to the computing node, or
the one or more jobs are being processed by another computing node included in the set of computing nodes.

13. The computing node of claim 8 , wherein the one or more processors are further configured to:
store the set of heartbeat messages after receiving the set of heartbeat messages; and
expire the set of heartbeat messages after determining whether the computing node is to be selected as the leader computing node.

14. The computing node of claim 8 , wherein the set of computing nodes are subscribed to a message stream of a message broker; and
wherein the one or more processors, when receiving the set of heartbeat messages, are to:
receive the set of heartbeat messages based on being subscribed to the message stream.

15. A non-transitory computer-readable medium storing instructions, the instructions comprising:
one or more instructions that, when executed by one or more processors of a computing node, cause

Assignees

• Capital One Services Llc

Inventors

• Kancharla Gopi
• Yajnik Sanjiv
• Bajaj Raman
• Land James
• Gangarapu Susmitha
• Tandra Praveen
• Kumar Parvesh
• Prabhakara Janardhan

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/546

  Message passing systems or structures, e.g. queues · CPC title

• G06F2209/502

  Proximity · CPC title

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/542

  Event management; Broadcasting; Multicasting; Notifications · CPC title