Method and system for collecting and analyzing time-series data

• US 8,601,112 B1
• Filed: 03/14/2006
• Issued: 12/03/2013
• Est. Priority Date: 03/14/2006
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Nordstrom, Paul G., Thompson, Aaron C.
• Primary Examiner(s): CHOUDHURY, AZIZUL Q
• Application Number:
  US11/374,875
• Time in Patent Office: 2,821 Days
• Field of Search: 709/219, 709/224, 709/201, 709/238, 707/600, 707/741
• US Class Current: 709/224
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/0633 Workflow analysis

Abstract

A system for collecting and processing time-series data from a plurality of data source computers comprises a plurality of computer-implemented partitions and a plurality of computer implemented nodes which own respective ones of the partitions. The plurality of computer-implemented partitions comprise a plurality of processes configured to produce the desired outputs. The plurality of partitions are configured (i) to permit each of the data messages to be received at an arbitrary one of the plurality of nodes, and (ii) to forward the received data message to one or more of the plurality of nodes which own respective ones of the plurality of partitions responsible for participating in producing one of the desired outputs.

Claims

1. A system for collecting and processing time-series data from a plurality of data source computers external to the system, wherein the data is received at an arbitrary node within the system from the data source computers in the form of data messages that will be converted into datapoints at the node, the system comprising:

a calculation table comprising a list of calculation descriptors inserted based at least in part on information provided by a plurality of user computers, the calculation descriptors describing at least one of desired data analysis datapoints and desired data index datapoints of the system to perform analysis of the data, wherein a datapoint comprises;

a datakey which provides information to allow the datapoint to be properly routed to at least one computer-implemented partition in accordance with a type of analysis to be performed on the data,

a data value which provides data to be processed,

a data interval which provides a time interval associated with the datapoint,

wherein the type of analysis to be performed on the data is based at least in part on at least one of a product identifier, a session identifier, and a visitor identifier, wherein the analysis corresponds to at least one of a detection in shifts in purchasing patterns, a detection of purchasing sales levels, an evaluation of the effectiveness of promotions, real-time performance statistics for analysis of website traffic, real-time website performance statistics for analysis of purchasing trends, or historical website performance statistics for evaluation of customer experiences,

wherein the at least one computer-implemented partition is configured to process the at least one of desired data analysis datapoints and desired data index datapoints in accordance with the calculation table, a plurality of computer-implemented nodes configured to receive data messages from the plurality of data source computers, wherein each computer-implemented node corresponds to a plurality of computer-implemented partitions, the plurality of computer-implemented partitions comprising a plurality of processes created based at least in part on contents of the calculation table

wherein the calculation table is configured to be updated by the plurality of user computers during operation of the system to cause the production of at least one of desired data analysis datapoints and desired data index datapoints or to stop the production of at least one of desired data analysis datapoints and desired data index datapoints that are no longer needed; and

wherein the plurality of partitions are configured (i) to permit each of the data messages to be received at an arbitrary one of the plurality of nodes, and (ii) to forward the received data messages to one or more of the plurality of nodes which own respective ones of the-plurality of partitions responsible for participating in producing one of the desired processing of the data.

2. A system as defined in claim 1, wherein the plurality of partitions comprise an exogenous partition and a plurality of endogenous partitions, wherein an exogenous partition receives messages from data source computers, and an endogenous partition receives messages from data collection and analysis computers, wherein the data source computers provide data which is desired to be collected and analyzed, and the data collection and analysis computers collect and analyze such data.

3. A system as defined in claim 2, wherein individual ones of the plurality of endogenous partitions correspond to individual ones of the plurality of nodes.

4. A system as defined in claim 3, wherein the node to which the data message is forwarded is a destination node, wherein the data message is configured to be received at the exogenous partition and is configured to be forwarded from the exogenous partition to a destination partition corresponding to the destination node, the destination partition being one of the plurality of endogenous partitions and participating in the production of at least one of desired data analysis datapoints and desired data index datapoints.

5. A system as defined in claim 1, wherein each of the plurality of partitions comprises datapipes which are paired with the plurality of processes, the datapipes being configured to collect the time-series data in the data messages, and the plurality of processes being time-series processors configured to process the time-series data.

6. A system as defined in claim 1, wherein the plurality of processes comprise indexing processes configured to generate indices of the time-series data.

7. A system as defined in claim 6, wherein the indices each comprise a plurality of layers of indices, wherein the first layer comprises an index organized along a first dimension, wherein the second layer comprises a plurality of indices constructed based at least in part on the index datapoints, and wherein the plurality of indices are organized along additional dimensions that are different from each other and are user-specified using the calculation descriptors in the calculation table.

8. A system as defined in claim 7, wherein the first dimension is time.

9. A data processing method comprising:

collecting time-series data in the form of data messages from a data source computer at a first node implemented at a first computer;

routing the time-series data to a second node implemented at a second computer;

processing the time-series data in the form of data messages at the second node in order to convert the data into datapoints;

storing the time-series data in a data repository;

indexing the time-series data to produce an index of the time-series data stored in the data repository;

wherein the data source computer is one of a plurality of data source computers, the plurality of data source computers each publishing web pages to visitors of a web site, and the time-series data relating to the contents of the web pages;

wherein the collecting, sorting, processing, storing and indexing steps are performed repeatedly by a plurality of computers for time-series data received from each of the plurality of data source computers, the plurality of computers including the first and second computers; and

wherein the time-series data is collected, sorted, processed, stored and indexed in substantially real-time, as new time-series data is received from the plurality of data source computers, according to a calculation table comprising calculation descriptors corresponding to at least one of data analysis datapoints and data index datapoints, wherein the desired data analysis datapoints and desired data index datapoints provide;

routing information to allow the datapoint to be properly routed,

a data value which provides data to be processed,

a data interval which provides a time interval associated with the datapoint,

wherein the desired data analysis datapoints and desired data index datapoints are utilized to dynamically generate routing in accordance with a type of analysis to be performed on the data, wherein the type of analysis to be performed on the data is based at least in part on at least one of a product identifier, a session identifier, and a visitor identifier,

wherein the analysis corresponds to at least one of a detection in shifts in purchasing patterns, a detection of purchasing sales levels, an evaluation of the effectiveness of promotions, real-time performance statistics for analysis of website traffic, real-time website performance statistics for analysis of purchasing trends, or historical website performance statistics for evaluation of customer experiences,

wherein the routing information identifies at least one computer-implemented partition in a manner that will allow the datapoint to be properly routed to the at least one computer-implemented partition, and

wherein the at least one identified computer-implemented partition will process the at least one of desired data analysis datapoints and desired data index datapoints in accordance with the calculation table.

10. A method as defined in claim 9, wherein the number of data source computers is in excess of one thousand and wherein the number of computers is in excess of one hundred.

11. A method as defined in claim 9, wherein the number of data source computers is in excess of five thousand.

12. A method as defined in claim 9, wherein the first and second nodes comprise a plurality of processes created as instances of object classes in an object-oriented programming environment.

13. A method as defined in claim 9, wherein the collecting, sorting, processing and indexing steps are performed substantially in real-time as the time-series data is collected from the data source computers.

14. A method as defined in claim 9, wherein the processing is performed at least in part by time-series processors created responsive to the insertion of calculation descriptors in the calculation table, the calculation table describing at least one of desired data analysis datapoints and desired data index datapoints of the plurality of computers, and the time-series processors being configured to generate at least one of desired data analysis datapoints and desired data index datapoints.