Generating data streams from pre-existing data sets

• US 10,162,672 B2
• Filed: 03/30/2016
• Issued: 12/25/2018
• Est. Priority Date: 03/30/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Wagner, Timothy Allen, Brooker, Marc John, Nair, Ajay
• Primary Examiner(s): Puente, Emerson C
• Assistant Examiner(s): Mills, Paul V
• Application Number:
  US15/085,885
• Publication Number:
  US 20170286156A1
• Time in Patent Office: 1,000 Days
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

Systems and methods are described for transforming a data set within a data source into a series of task calls to an on-demand code execution environment or other distributed code execution environment. Such environments utilize pre-initialized virtual machine instances to enable execution of user-specified code in a rapid manner, without delays typically caused by initialization of the virtual machine instances, and are often used to process data in near-real time, as it is created. However, limitations in computing resources may inhibit a user from utilizing an on-demand code execution environment to simultaneously process a large, existing data set. The present application provides a task generation system that can iteratively retrieve data items from an existing data set and generate corresponding task calls to the on-demand computing environment, while ensuring that at least one task call for each data item within the existing data set is made.

Claims

1. A system for processing data items within a data source via an on-demand code execution environment, the system comprising:

a non-transitory data store configured to implement a backlog cache indicating data items, from the data source, that have been identified for processing at the on-demand code execution environment as backlog items;

one or more processors, in communication with the non-transitory data store, configured to;

retrieve, for a set of data items within the data source, time data indicating points in time at which individual data items from the set of data items were created or modified within the data source;

determine, from the time data, an estimated modification frequency for the data source, the estimated modification frequency indicating an estimated frequency at which data items within the data source are created or modified;

obtaining a threshold period of time;

utilize the estimated modification frequency for the data source, the time data, and an anticipated rate of processing of data items at the on-demand code execution system to establish a demarcation time for the data source that is expected to result in a completion, within the threshold period of time, of processing of data items created or modified in the data source after the demarcation time, wherein data items created or modified in the data source prior to the demarcation time are considered backlogged data items, and wherein the set of data items includes at least one data item created or modified in the data source after the demarcation time;

enqueue within the backlog cache a first set of data items, from the data store, that were created or modified in the data source prior to the demarcation time;

iteratively submit data stream calls to the on-demand code execution environment, the data stream calls requesting that the demand code execution environment process, by execution of a task, data items from the data source that were created or modified after the demarcation time;

while data stream calls are submitted the on-demand code execution environment, submit backlog calls to the on-demand code execution environment, the backlog calls requesting that the demand code execution environment process, by execution of the task, data items from the backlog cache.

2. The system of claim 1, wherein the one or more processers are further configured to vary a rate at which backlog calls are submitted to the on-demand code execution environment according to at least one of a rate at which data stream calls are submitted to the on-demand code execution environment or a rate at which tasks corresponding to the data stream calls are completed by the on-demand code execution environment.

3. The system of claim 2, wherein the one or more processers are further configured to vary a rate at which backlog calls are submitted to the on-demand code execution environment according to at least a rate at which calls occur at the on-demand code execution environment.

4. The system of claim 1, further comprising one or more processors configured to implement a user interface subsystem that obtains, from a user computing device, information identifying the data source and the task, on the on-demand code execution environment, to utilize in processing data items from the data source.

5. The system of claim 1, wherein the data source corresponds to a plurality of distinct data sources.

6. The system of claim 1, wherein the task corresponds to a plurality of tasks, and wherein the information obtained from the user computing device further comprises information for determining an individual task, from the plurality of tasks, to call for processing a given data item from the plurality of data items.

7. The system of claim 1, wherein the one or more processers are further configured to determine that the first set of data items have not been previously processed by the system based at least in part on identifiers for the set of data items.

8. A computer-implemented method to process data items within a data source via an on-demand code execution environment, the computer-implemented method comprising:

retrieving, for a set of data items within the data source, time data indicating points in time at which individual data items from the set of data items were created or modified within the data source;

determining, from the time data, an estimated modification frequency for the data source, the estimated modification frequency indicating an estimated frequency at which data items within the data source are created or modified;

obtaining a threshold period of time;

utilizing the time data, the estimated modification frequency for the data source, and an anticipated rate of processing of data items at the on-demand code execution system to establish a demarcation time for the data source that is expected to result in a completion, within the threshold period of time, of processing of data items created or modified in the data source after the demarcation time, wherein data items created or modified in the data source prior to the demarcation time are considered backlogged data items, and wherein the set of data items includes at least one data item created or modified in the data source after the demarcation time;

enqueuing within a backlog cache a first set of data items, from the data store, that were created or modified in the data source prior to the demarcation time;

iteratively submitting data stream calls to the on-demand code execution environment, the data stream calls requesting that the demand code execution environment process, by execution of a task, data items from the data source that were created or modified after the demarcation time;

while data stream calls are submitted the on-demand code execution environment, submitting backlog calls to the on-demand code execution environment, the backlog calls requesting that the demand code execution environment process, by execution of the task, data items from the backlog cache.

9. The computer-implemented method of claim 8 further comprising varying a rate at which backlog calls are submitted to the on-demand code execution environment according to at least one of a rate at which data stream calls are submitted to the on-demand code execution environment or a rate at which tasks corresponding to the data stream calls are completed by the on-demand code execution environment.

10. The computer-implemented method of claim 8 further comprising obtaining information identifying the data source and the task from a user computing device.

11. The computer-implemented method of claim 8, wherein the information obtained from the user computing device further includes a maximum rate for submission of at least one data stream calls or backlog calls.

12. The computer-implemented method of claim 8 further comprising determining a data stream call rate based at least in part on errors received from the on-demand code execution environment.

13. The computer-implemented method of claim 8 further comprising determining that the first set of data items have not been previously processed based at least in part on identifiers for the set of data items.

14. The computer-implemented method of claim 13, wherein the identifiers for the first set of data items are retrieved from the data source.

15. Non-transitory computer readable media including computer-executable instructions to process data items within a data source via an on-demand code execution environment, wherein the computer-executable instructions, when executed by a computing system, cause the computing system to:

obtain time data indicating points in time at which individual data items from the data items within the data source were created or modified;

determine, from the time data, an estimated modification frequency for the data source, the estimated modification frequency indicating an estimated frequency at which data items within the data source are created or modified;

obtain a threshold period of time;

utilize the time data, the estimated modification frequency for the data source, and an anticipated rate of processing of data items at the on-demand code execution system, to establish a demarcation time for the data source that is expected to result in a completion, within the threshold period of time, of processing of data items created or modified in the data source after the demarcation time, wherein data items created or modified in the data source prior to the demarcation time are considered backlogged data items, and wherein the set of data items includes at least one data item created or modified in the data source after the demarcation time;

enqueue within a backlog cache a first set of data items, from the data store, that were created or modified in the data source prior to the demarcation time;

submit data stream calls to the on-demand code execution environment, the data stream calls requesting that the demand code execution environment process, by execution of a task, data items from the data source that were created or modified after the demarcation time;

concurrently to submission of data stream calls to the on-demand code execution environment, submit backlog calls to the on-demand code execution environment, the backlog calls requesting that the demand code execution environment process, by execution of the task, data items from the backlog cache.

16. The non-transitory computer-readable media of claim 15, wherein the computer-executable instructions further cause the computing system to vary a rate at which backlog calls are submitted to the on-demand code execution environment according to at least one of a rate at which data stream calls are submitted to the on-demand code execution environment or a rate at which tasks corresponding to the data stream calls are completed by the on-demand code execution environment.

17. The non-transitory computer-readable media of claim 15, wherein the computer-executable instructions further cause the computing system to obtain information identifying the data source and the task from a user computing device.

18. The non-transitory computer-readable media of claim 15, wherein the information obtained from the user computing device further includes a maximum rate for submission of at least one data stream calls or backlog calls.

19. The non-transitory computer-readable media of claim 15, wherein the computer-executable instructions further cause the computing system to determine a data stream call rate based at least in part on errors received from the on-demand code execution environment.

20. The non-transitory computer-readable media of claim 15, wherein the computer-executable instructions further cause the computing system to establish a second demarcation time for the data source, wherein data items are considered backlogged data items only when created or modified on or after the second demarcation time, and wherein data items are created or modified before the second demarcation time are considered archived items.

21. The non-transitory computer-readable media of claim 15, wherein the computer-executable instructions further cause the computing system to modify the demarcation time based at least in part on at least one of a rate at which data stream calls are submitted to the on-demand code execution environment or a rate at which tasks corresponding to the data stream calls are completed by the on-demand code execution environment.