Optimizing computational data systems

• US 9,852,160 B1
• Filed: 05/30/2013
• Issued: 12/26/2017
• Est. Priority Date: 05/30/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Ramalingam, Harsha, Fernandes, Aaron
• Primary Examiner(s): Rostami, Mohammad S
• Assistant Examiner(s): Harmon, Courtney
• Application Number:
  US13/905,738
• Time in Patent Office: 1,671 Days
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2201/81 Threshold

Abstract

A data computation rate is calculated for use by components in a computational data system. The data computation rate defines the frequency at which a computation, or other types of processing, is performed on or using certain data, such as a data value in a database. The data computation rate might be calculated based upon a current or historical data consumption rate that defines the frequency at which a consumer requests or has requested data, a data update rate that defines the current or historical frequency at which the data that is utilized to generate the processed data is or has been modified, a consumer-specified tolerance, and/or other information. The computed data consumption rate might then be utilized to specify the frequency at which the data should be processed by components in the computational data system.

Claims

1. A computer-implemented method for optimizing a computational data system, the computer-implemented method comprising performing computer-implemented operations for:

determining at least one of a historical data consumption rate or a historical data update rate, the historical data consumption rate defining a rate at which the consumer has historically requested processed data, the historical data update rate defining a rate at which data has historically been updated;

determining an initial value for a data computation rate based at least in part on the at least one of the historical data consumption rate or the historical data update rate, the data computation rate comprising a frequency at which a computation is performed on the data to generate the processed data;

receiving a tolerance associated with a consumer of the processed data, the tolerance specifying a frequency at which processed data that is not current may be provided to the consumer in response to requests from the consumer for processed data;

computing a miss rate, the miss rate comprising a frequency at which misses occur over a period of time, a miss comprising sending stale data to the consumer in response to receiving a request from the consumer for processed data;

increasing the data computation rate if the miss rate is greater than the tolerance; and

decreasing the data computation rate if the miss rate is less than the tolerance.

2. The computer-implemented method of claim 1, wherein the initial value for the data computation rate is based at least in part on both the historical data consumption rate and the historical data update rate.

3. The computer-implemented method of claim 1, further comprising:

determining a current data consumption rate, the current consumption rate defining a rate at which the consumer is currently requesting the processed data;

determining a current data update rate, the current data update rate defining a rate at which the data is currently being updated; and

utilizing the current data consumption rate, the current data update rate, and the tolerance to compute the initial value for the data computation rate.

4. The computer-implemented method of claim 1, further comprising:

identifying a historical data consumption rate, the historical data consumption rate defining a rate at which the consumer has historically requested the processed data;

determining a current data consumption rate, the current data consumption rate defining a rate at which the consumer is currently requesting the data;

identifying a historical data update rate, the historical data update rate defining a rate at which the data has historically been updated;

determining a current data update rate, current data update rate defining a rate at which the data is currently being updated; and

utilizing the historical data consumption rate, the current data consumption rate, the historical data update rate, the current update rate, and the tolerance to compute the initial value for the data computation rate.

5. The computer-implemented method of claim 1, further comprising performing the computation on the data to generate the processed data at a frequency equivalent to the data computation rate.

6. The computer-implemented method of claim 1, further comprising repeating operations of computing the miss rate, increasing the data computation rate if the miss rate is greater than the tolerance, and decreasing the data computation rate if the miss rate is less than the tolerance.

7. A computer-implemented method for optimizing a computational data system, the computer-implemented method comprising performing computer-implemented operations for:

obtaining historical request data, the historical request data defining requests previously submitted by a consumer of processed data, the processed data generated by processing unprocessed data;

obtaining historical update event data, the historical update event data defining updates previously performed to the unprocessed data utilized to generate the processed data;

receiving, from the consumer of the processed data, a tolerance associated with the consumer of the processed data, the tolerance specifying a frequency at which processed data that is stale may be provided to the consumer in response to requests from the consumer; and

utilizing the historical request data, the historical update event data, and the tolerance to modify a data computation rate, the data computation rate comprising the rate at which a computation is performed on the unprocessed data to generate the processed data.

8. The computer-implemented method of claim 7, further comprising performing the computation on the unprocessed data to generate the processed data at a frequency equivalent to the computed data computation rate.

9. The computer-implemented method of claim 7, further comprising utilizing a plurality of data analysis models to compute an optimal rate for the data computation rate from the historical request data, the historical update event data, and the tolerance.

10. The computer-implemented method of claim 9, wherein at least one of the data analysis models utilizes asynchronous machine learning to compute the data computation rate.

11. The computer-implemented method of claim 9, wherein at least one of the data analysis models utilizes simulation to compute the data computation rate.

12. The computer-implemented method of claim 9, wherein at least one of the data analysis models utilizes a stochastic process to compute the data computation rate.

13. The computer-implemented method of claim 9, wherein at least one of the data analysis models utilizes forecasting data to compute the data computation rate, the forecasting data based on a predicted future data consumption rate.

14. The computer-implemented method of claim 9, wherein each of the plurality of data analysis models is configured to compute a data computation rate, and wherein the method further comprises selecting an optimal data computation rate from the data computation rates computed by the plurality of data analysis models.

15. The computer-implemented method of claim 9, wherein the optimal data computation rate comprises a data computation rate that can be utilized to provide the processed data to the consumer at a lowest operational cost while meeting the tolerance.

16. A system for optimizing a data computation rate, the system comprising one or more computer systems configured to:

determine a data update rate using historical update event data, the data update rate comprising a frequency at which unprocessed data is collected;

determine a data consumption rate using historical request data, the data consumption rate comprising a frequency at which a consumer is requesting processed data; and

utilize the data update rate, the data consumption rate, and a tolerance specified by the consumer to modify a data computation rate, the data computation rate comprising a frequency at which the unprocessed data is processed to generate the processed data, the data computation rate being less than the data update rate, the tolerance specifying a frequency at which processed data that is stale may be provided to the consumer in response to requests from the consumer for the processed data.

17. The system of claim 16, wherein the data computation rate is further computed using forecasting data, the forecasting data based on a predicted future data consumption rate.

18. The system of claim 16, wherein the one or more computer systems are further configured to:

compute a miss rate, the miss rate comprising a frequency at which processed data that is stale is provided to the consumer in response to requests from the consumer for the processed data; and

modify the computation rate based upon the miss rate and the tolerance.

19. The system of claim 16, wherein the one or more computer systems are further configured to compute an initial value for the data computation rate using a historical data consumption rate and a historical data update rate.

20. The system of claim 16, wherein the one or more computer systems are further configured to:

utilize a plurality of data analysis models to calculate a plurality of data computation rates; and

select an optimal data computation rate from the plurality of data computation rates computed by the plurality of data analysis models.

21. A computer-implemented method for optimizing a computational data system, the computer-implemented method comprising performing computer-implemented operations for:

receiving a pre-request signal from a data consumer, the pre-request signal identifying data desired by the data consumer, the pre-request signal also being an indication that the data consumer will transmit an actual request for the identified data at a later time;

generating the data identified in the pre-request signal from the data consumer;

subsequent to receiving the pre-request signal, receiving the actual request from the data consumer for the identified data; and

providing the identified data to the data consumer in response to receiving the actual request from the data consumer.

22. The computer-implemented method of claim 21, wherein the identified data is generated from data stored in a database.

23. The computer-implemented method of claim 22, wherein the identified data is also stored in the database.

24. The computer-implemented method of claim 23, wherein the data utilized to generate the identified data is periodically updated in the database.