Randomized subrequest selection using request-specific nonce

Patent metadata

Field	Value
Publication number	US-10445136-B1
Application number	US-201715611091-A
Country	US
Kind code	B1
Filing date	Jun 1, 2017
Priority date	Jun 1, 2017
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

Methods and related systems are provided for the generation and use of a request-specific nonce to coordinate the randomized selection of subrequests stemming from a top-level request to a system. The method includes receiving, but a subsystem of the system, a subrequest that is generated in response to the receipt of a top-level request to the system. The subsystem then determines a nonce that comprises a pseudorandom value that is consistent for all subrequests stemming from the top-level request. The subsystem may use the nonce to make a variety of processing decisions for the subrequests. In one embodiment, the nonce is used to determine which subrequests should be throttled. In another embodiment, the nonce is used to determine whether trace data should be collected for received subrequests. The nonce allows different subsystems to coordinate their processing decisions based on a randomized but consistent prioritization of the top-level request.

First claim

What is claimed is:

1. A system, comprising:
a top-level subsystem, implemented by one or more processors with associated memory, configured to receive a plurality of top-level requests;
a first subsystem, implemented by one or more processors with associated memory, configured to:
receive a first subrequest stemming from a top-level request of the plurality of top-level requests received by the service;
obtain a nonce value for the first subrequest using a nonce determination technique that provides a consistent pseudorandom nonce value for subrequests stemming from a same top-level request;
determine whether to perform an operation for the first subrequest using a shared request selection technique based at least in part on the nonce value;

a second subsystem implemented by one or more processors with associated memory, configured to:
receive a second subrequest stemming from the top-level request of the plurality of top-level requests;
obtain the nonce value using the nonce determination technique such that the nonce value has a same value for the first subrequest and the second subrequest;
determine whether to perform the operation for the second subrequest using the shared request selection technique.

2. The system of claim 1 , wherein:
the first subsystem is configured to perform the operation on a first plurality of subrequests based on its determinations of whether to perform the operation;
the second subsystem is configured to perform the operation on a second plurality of subrequests based on its determinations of whether to perform the operation;
wherein the operation performed on each of the subrequests impacts corresponding ones of the plurality of top-level requests, the operation on the first plurality of subrequests impacts a first proportion of top-level requests, and the operation on the second plurality of subrequests impacts a second proportion of top-level requests, and
wherein the determinations of whether to perform the operation by the first and second subsystems are coordinated based on the nonce determination technique and the request selection technique, such that an overall proportion of the plurality of top-level requests that are impacted by performance of the operation by either the first subsystem or the second subsystem is no greater than a larger of the first proportion and the second proportion.

3. The system of claim 1 , wherein to determine whether to perform an operation for the first subrequest, the first subsystem is configured to:
determine that the first subsystem is currently in an overloaded state;
compare the nonce value to a throttling threshold to determine that the first subrequest should be throttled; and
throttle the first subrequest.

4. The system of claim 1 , wherein to determine whether to perform an operation for the first subrequest, the trace data collection module is configured to:
compare the nonce value to a trace sampling threshold to determine that trace data should be collected for the first subrequest;
collect trace data for the first subrequest; and
store the collected trace data in a trace data store.

5. The system of claim 1 , wherein to perform the nonce determination technique, the first subsystem is configured to obtain the nonce value from a parameter of the first subrequest.

6. The system of claim 1 , wherein to perform the nonce determination technique, the first subsystem is configured to generate the nonce value using a consistent nonce generation function applied to one or more parameters associated with the first subrequest.

7. A method, comprising:
performing, by a subsystem of a plurality of subsystems:
receiving a subrequest stemming from a top-level request of a plurality of top-level requests received by a top-level subsystem of the plurality of subsystems;
obtaining a nonce value for the subrequest using a nonce determination technique that provides a consistent pseudorandom nonce value for subrequests stemming from a same top-level request; and
determining whether to perform an operation for the subrequest, wherein the determination is made using a request selection technique based at least in part on the nonce value, and the request selection technique is used by one or more other subsystems of the plurality of subsystems that receive subrequests stemming the same top-level request to determine whether to perform the operation on their subrequests.

8. The method of claim 7 , further comprising:
performing, by each of the plurality of subsystems, the operation on some of its received subrequests based on its determinations of whether to perform the operation;
wherein the operation, when performed on a particular subrequest, impacts a particular top-level request from which the particular subrequest stems, and the performance of the operation by each of the plurality of subsystems impacts a respective proportion of the plurality of top-level requests; and
wherein the determinations of whether to perform the operation by the plurality of subsystems are coordinated based on the nonce determination technique and the request selection technique, such that an overall proportion of the plurality of top-level requests that are impacted by the performance of the operation by the plurality of subsystems is no greater than a maximum one of the respective proportions of top-level requests impacted individual ones of the plurality of subsystems.

9. The method of claim 7 , wherein determining whether to perform an operation for the subrequest comprises comparing the nonce value to a throttling threshold to determine whether the subrequest should be throttled; and further comprising throttling the subrequest in response to a determination that the subrequest should be throttled.

10. The method of claim 7 , wherein determining whether to perform an operation for the subrequest comprises comparing the nonce value to a trace sampling threshold to determine whether the trace data should be collected for the subrequest; and further comprising collecting trace data for the subrequest in response to a determination that the trace data should be collected for the subrequest.

11. The method of claim 7 , wherein obtaining a nonce value for the subrequest comprises hashing the one or more parameters associated with the subrequest, the one or more parameters comprising one or more of: a client identifier, a session identifier, a source IP address, or a source TCP port number.

12. The method of claim 7 , wherein obtaining a nonce value for the subrequest is based at least in part on a request identifier generated for the top-level request.

13. The method of claim 7 , wherein obtaining a nonce value for the subrequest comprises generating the nonce value using a nonce generation function applied to a time quantization during which the top-level request is received, wherein the nonce generation function generates a different nonce value for a different time quantization.

14. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors cause the one or more processors to implement a subsystem of a plurality of subsystems, the subsystem configured to:
receive a subrequest stemming from a top-level request;
obtain a nonce value for the subrequest using a nonce determination technique that provides a consistent pseudorandom nonce value for subrequests stemming from a same top-level request; and
determine whether to perform an operation for the subrequest, wherein the determination is made using a request selection technique based at least in part on the nonce value, wherein the request select

Assignees

• Amazon Tech Inc

Inventors

• Roskind James

Classifications

• G06F2209/5022

  Workload threshold · CPC title

• G06F9/4881 Primary

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

• G06F9/505

  considering the load · CPC title