Distributed technique for allocating long-lived jobs among worker processes

A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

• in a distributed computing system, using a set of worker processes to execute a set of jobs that are long-lived;
• wherein each worker process in the set of worker processes is associated with a unique identifier;
• wherein the unique identifiers associated with the set of worker processes are assigned to the set of worker processes in an increasing order of the unique identifiers;
• and
• wherein the using the set of worker processes to execute the set of jobs is based on each worker process in the set of worker processes performing the following operations:
• identifying the set of jobs,
• identifying the set of worker processes,
• sorting the set of worker processes based on the unique identifiers associated with the set of worker processes to produce a sorted order of the set of worker processes,
• assigning one or more jobs in the set of jobs to each worker process in the set of worker processes in the sorted order of the set of worker processes such that each job in the set of jobs is assigned to exactly one worker process in the set of worker processes and such that a same number of jobs or an approximately same number of jobs is assigned to each worker process in the set of worker processes, and wherein the assigning one or more jobs in the set of jobs to each worker process in the set of worker processes involves:
• using the unique identifier for the worker process to seed a deterministic pseudorandom number generator, and
• using one or more numbers obtained from the deterministic pseudorandom number generator seeded with the unique identifier for the worker process to select one or more jobs in the set of jobs to assign to the worker process for the worker process to execute, and
• commencing execution of the one or more jobs that are assigned to the worker process itself.

A distributed computing system, comprising:

• a plurality of processors;
• memory;
• instructions stored in the memory and configured for execution by the plurality of processors as a set of a plurality of processes, wherein each process in the set of processes is associated with a unique identifier, wherein the unique identifiers associated with the set of processes are assigned to the set of processes in an increasing order of the unique identifiers, and wherein each process of the plurality of processes is configured by the instructions to:
• identify a set of jobs to be executed,
• identify the set of processes,
• sort the set of processes based on the unique identifiers associated with the set of processes to produce a sorted order of the set of processes, and
• assign one or more jobs in the set of jobs to each process in the set of processes in the sorted order of the set of processes such that each job in the set of jobs is assigned to exactly one process in the set of processes and such that a same number of jobs or an approximately same number of jobs is assigned to each process in the set of processes, and wherein each process of the plurality of processes is configured by the instructions to assign one or more jobs in the set of jobs to each process in the set of processes by:
• using the unique identifier for the process to seed a deterministic pseudorandom number generator, and
• using one or more numbers obtained from the deterministic pseudorandom number generator seeded with the unique identifier for the process to select one or more jobs in the set of jobs to assign to the process for the process to execute, and
• commence execution of the one or more jobs that are assigned to the process itself.