US 11,537,431 B1Granted

Task contention reduction via policy-based selection

AssigneeAmazon Technologies, Inc.

InventorsSandeep Kumar, Anirudha Singh Bhadoriya

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system implements task contention reduction via policy-based selection. Tasks waiting to be performed are indexed in a task data structure that groups the tasks based on the resources to which the tasks pertain. Workers request batches of tasks for the workers to perform. A scan cycle includes building multiple batches of tasks by scanning the task data structure for a requesting worker. A policy (e.g., random or some other form of optimization) determines where the scan cycle starts in the data structure. Each batch of tasks is delivered to a worker along with a token that keeps the state of the scan cycle (e.g., where the scan cycle started, and where the next scan to build the next batch within the scan cycle begins). The worker returns the token with the next request for the next batch and the next batch is built based on the token's state information.

Claims20

Dependent claims

A system, comprising:

a task service implemented via one or more hardware processors and memory, wherein the task service indexes tasks for a distributed system in a task data structure, wherein tasks are identified within the task data structure according to a task key value of a task key space;
a plurality of resources of the distributed system, wherein tasks are grouped within the task data structure based at least in part on one or more of the resources to which the tasks pertain;
a plurality of workers implemented via one or more hardware processors and memory, wherein a respective worker of the plurality of workers:
sends a request to the task service that begins a scan cycle through the task key space;
receives, from the task service, a batch of one or more tasks and a corresponding token, wherein the token includes:
a start location within the task key space that indicates where the scan cycle started, and
a next location in the task key space;
performs the one or more tasks;
and
includes the token in a subsequent request to the task service for one or more additional tasks determined from the next location in the task key space;
wherein the task service, responsive to the request to begin the scan through the task key space, applies a policy to determine the start location within the task key space, wherein the task service returns to the worker the batch of one or more tasks and the corresponding token that includes the start location and the next location in the task key space.

8 more elements

A method, comprising:

performing, by a task service implemented via one or more computers:
indexing tasks in a task data structure, wherein tasks are indexed within the task data structure according to a task key value of a task key space, and wherein indexing tasks comprises locating the tasks within the task data structure based at least in part on resources to which the tasks pertain;
receiving a request from a worker to begin a scan cycle for tasks to perform;
applying a policy to determine a start location within the task key space for scanning for tasks;
scanning the task data structure starting from the start location for one or more tasks;
encoding the start location and a next location in the task key space into a token;
and
returning the one or more tasks and token to the worker.

5 more elements

Dependencies are inferred from the claim text.