# US 10,310,904 B2 · Distributed technique for allocating long-lived jobs among worker processes

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,310,904 B2
- Document ID: US10310904B2
- Status: Granted
- Kind: B2
- Application number: 14/555,101
- Filed: 2014-11-26
- Published: 2016-05-26
- Granted: 2019-06-04
- Earliest claimed: 2014-11-26
- Assignees: Dropbox, Inc.
- Applicants: Dropbox, Inc.
- Inventors: James Cowling; James Turner
- Web page: https://patentgrep.com/patent/US10310904B2

## CPC

- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A distributed computing system that executes a set of long-lived jobs is described. During operation, each worker process performs the following operations. First, the worker process identifies a set of jobs to be executed and a set of worker processes that can execute the set of jobs. Next, the worker process sorts the set of worker processes based on unique identifiers for the worker processes. Then, the worker process assigns jobs to each worker process in the set of worker processes, wherein approximately the same number of jobs is assigned to each worker process, and jobs are assigned to the worker processes in sorted order. While assigning jobs, the worker process uses an identifier for each worker process to seed a pseudorandom number generator, and then uses the pseudorandom number generator to select jobs for each worker process to execute.

## Claims

### Claim 1

A computer-implemented 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.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein after a worker process assigns the one or more jobs to each worker process in the set of worker processes, the worker process stops executing jobs that are no longer assigned to the worker process.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein identifying the set of worker processes involves querying a distributed consensus service that operates by sending heartbeats to different machines in the distributed computing system to identify worker processes that are available to execute jobs.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein the method further comprises performing initialization operations for each worker process that commences execution, wherein the initialization operations include:
registering the worker process with a distributed consensus service to obtain an identifier for the worker process; and
subscribing to an online worker list to obtain notifications about changes to the set of worker processes that are available to execute jobs.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein using the seeded deterministic pseudorandom number generator to select the one or more jobs for each worker process to execute involves:
determining a desired number of jobs that the worker process will execute by dividing a number of jobs in the set of jobs by a number of worker processes in the set of worker processes and, if necessary, adding one to account for a remainder; and
repeating the following operations until the desired number of jobs is selected for the worker process to execute,
obtaining a random number from the deterministic pseudorandom number generator,
using the random number and a modulo operation to randomly select a job from the set of jobs, and
if the job has already been selected, repeating the process of obtaining a random number and using the random number to select a job until an unselected job is selected.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein each worker process repeats the operations involved in assigning jobs to worker processes whenever the set of worker processes changes.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the operations involved in executing a job are idempotent, thereby allowing multiple worker processes to repeat the operations without violating correctness when jobs are reassigned among worker processes.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, wherein the set of jobs that are long-lived includes jobs that process queues of updates and deletes directed to replicated copies of data items located in different zones, wherein each zone comprises a separate geographic storage location.

### Claim 9

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.

### Claim 10 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein after a worker process assigns the one or more jobs to each worker process in the set of worker processes, the worker process stops executing jobs that are no longer assigned to the worker process.

### Claim 11 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein identifying the set of worker processes involves querying a distributed consensus service that operates by sending heartbeats to different machines in the distributed computing system to identify worker processes that are available to execute jobs.

### Claim 12 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the method further comprises performing initialization operations for each worker process that commences execution, wherein the initialization operations include:
registering the worker process with a distributed consensus service to obtain an identifier for the worker process; and
subscribing to an online worker list to obtain notifications about changes to the set of worker processes that are available to execute jobs.

### Claim 13 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein using the seeded deterministic pseudorandom number generator to select the one or more jobs for each worker process to execute involves:
determining a desired number of jobs that the worker process will execute by dividing a number of jobs in the set of jobs by a number of worker processes in the set of worker processes and, if necessary, adding one to account for a remainder; and
repeating the following operations until the desired number of jobs is selected for the worker process to execute,
obtaining a random number from the deterministic pseudorandom number generator,
using the random number and a modulo operation to randomly select a job from the set of jobs, and
if the job has already been selected, repeating the process of obtaining a random number and using the random number to select a job until an unselected job is selected.

### Claim 14 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein each worker process repeats the operations involved in assigning jobs to worker processes whenever the set of worker processes changes.

### Claim 15 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the operations involved in executing a job are idempotent, thereby allowing multiple worker processes to repeat the operations without violating correctness when jobs are reassigned among worker processes.

### Claim 16 (depends on 9)

The non-transitory computer-readable storage medium of claim 9, wherein the set of jobs that are long-lived includes jobs that process queues of updates and deletes directed to replicated copies of data items located in different zones, wherein each zone comprises a separate geographic storage location.

### Claim 17

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.

### Claim 18 (depends on 17)

The distributed computing system of claim 17, wherein after a process assigns the one or more jobs to each process in the set of processes, the process stops executing jobs that are no longer assigned to the process.

### Claim 19 (depends on 17)

The distributed computing system of claim 17, wherein while identifying the set of processes each process is configured by the instructions to query a distributed consensus service that operates by sending heartbeats to different machines in the distributed computing system to identify processes that are available to execute jobs.

### Claim 20 (depends on 17)

The distributed computing system of claim 17, wherein each process is configured by the instructions to perform initialization operations when the process commences execution, wherein the initialization operations include:
registering the process with a distributed consensus service to obtain an identifier for the process; and
subscribing to an online list to obtain notifications about changes to the set of processes that are available to execute jobs.

### Claim 21 (depends on 17)

The distributed computing system of claim 17, wherein while using the seeded deterministic pseudorandom number generator to select the one or more jobs for each process, each process is configured by the instructions to:
determine a desired number of jobs that the process will execute by dividing a number of jobs in the set of jobs by a number of processes in the set of processes and, if necessary, adding one to account for a remainder; and
repeat the following operations until the desired number of jobs is selected for the process to execute,
obtain a random number from the deterministic pseudorandom number generator,
use the random number and a modulo operation to randomly select a job from the set of jobs, and
if the job has already been selected, repeat the process of obtaining a random number and using the random number to select a job until an unselected job is selected.

### Claim 22 (depends on 17)

The distributed computing system of claim 17, wherein each process is configured by the instructions to repeat the operations involved in assigning jobs to processes whenever the set of processes changes.

### Claim 23 (depends on 17)

The distributed computing system of claim 17, wherein the operations involved in executing a job are idempotent, thereby allowing multiple processes to repeat the operations without violating correctness when jobs are reassigned among processes.

### Claim 24 (depends on 17)

The distributed computing system of claim 17, wherein the set of jobs that are long-lived includes jobs that process queues of updates and deletes directed to replicated copies of data items located in different zones, wherein each zone comprises a separate geographic storage location.