Scalable cloud-based time series analysis

• US 10,331,490 B2
• Filed: 11/16/2018
• Issued: 06/25/2019
• Est. Priority Date: 11/16/2017
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Leonard, Michael James, Quirino, Thiago Santos, Blair, Edward Tilden, Beeman, Jennifer Leigh Sloan, Elsheimer, David Bruce
• Primary Examiner(s): Wu, Benjamin C
• Application Number:
  US16/193,661
• Publication Number:
  US 20190146849A1
• Time in Patent Office: 221 Days
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

Timestamped data can be read in parallel by multiple grid-computing devices. The timestamped data, which can be partitioned into groups based on time series criteria, can be deterministically distributed across the multiple grid-computing devices based on the time series criteria. Each grid-computing device can sort and accumulate the timestamped data into a time series for each group it receives and then process the resultant time series based on a previously distributed script, which can be compiled at each grid-computing device, to generate output data. The grid-computing devices can write their output data in parallel. As a result, vast amounts of timestamped data can be easily analyzed across an easily expandable number of grid-computing devices with reduced computational expense.

Claims

1. A system, comprising:

one or more data processors; and

a non-transitory computer-readable storage medium containing instructions which, when executed on the one or more data processors, cause the one or more data processors to perform operations including;

receiving a script at each of a plurality of grid-computing devices;

compiling the script on each of the plurality of grid-computing devices, wherein compiling a script on a grid-computing device comprises compiling the script for an operating system of the grid-computing device;

reading input data in parallel by the plurality of grid-computing devices, wherein the input data comprises timestamped data partitionable into groups according to time series criteria;

deterministically distributing the timestamped data across the plurality of grid-computing devices based on the groups, wherein, for each of the groups, the timestamped data associated with the group is associated with one of the plurality of grid-computing devices;

generating a time series for each of the groups at respective ones of the plurality of grid-computing devices, wherein generating a time series comprises accumulating the timestamped data associated with a group into the time series;

executing the compiled script, at each of the plurality of grid-computing devices, on the time series associated with the grid-computing device to generate output data; and

writing the output data in parallel by the plurality of grid-computing devices.

2. The system of claim 1, wherein the input data comprises the timestamped data in an unsorted format, and wherein generating the time series further comprises sorting the timestamped data associated with the group before accumulating the timestamped data associated with the group.

3. The system of claim 1, wherein the script contains analyzing instructions for analyzing timestamped data and the time series criteria.

4. The system of claim 1, wherein accumulating the timestamped data associated with the group into the time series comprises accumulating the timestamped data into a fixed-interval and fixed-length time series based on a time span of the input data.

5. The system of claim 1, wherein a first group and a second group are associated with a particular grid-computing device of the plurality of grid-computing devices, wherein a first time series and a second time series are associated with the particular grid-computing device, and wherein executing the compiled script at the particular grid-computing device comprises:

allocating memory to the particular grid-computing device for the execution of the compiled script;

executing the compiled script on the first time series using the allocated memory;

executing the compiled script on the second time series using the allocated memory, wherein executing the compiled script on the second time series occurs before releasing the allocated memory; and

releasing the allocated memory after executing the compiled script on the first time series and the second time series.

6. The system of claim 5, wherein executing the compiled script on the first time series comprises instantiating computational objects and data objects in the allocated memory, and wherein executing the compiled script on the second time series comprises reusing at least a portion of the computational objects.

7. The system of claim 1, wherein reading the input data by a given grid-computing device comprises reading a subset of the timestamped data by the given grid-computing device, wherein deterministically distributing the timestamped data occurs on each of the plurality of grid-computing devices, and wherein deterministically distributing the timestamped data on the given grid-computing device comprises:

generating, for each group present in the subset of the timestamped data, a hash value using the time series criteria associated with the group;

calculating a destination identifier for each group by performing a modulo operation using the hash value as a dividend and a number of grid-computing devices in the plurality of grid-computing devices as a divisor; and

distributing timestamped data associated with each group by transmitting the timestamped data associated with the group to a destination grid-computing device identified by the destination identifier.

8. The system of claim 1, wherein the input data is stored on a distributed file system across a plurality of data files, and wherein reading the input data in parallel by the plurality of grid-computing devices comprises contemporaneously reading multiple data files of the plurality of data files by the plurality of grid-computing devices.

9. The system of claim 1, wherein deterministically distributing the timestamped data comprises bundling a plurality of entries of the timestamped data associated with a group into a bundle;

and distributing the bundle to a destination node associated with the group.

10. The system of claim 9, wherein deterministically distributing the timestamped data further comprises sorting and accumulating the bundle prior to distributing the bundle.

11. A computer-implemented method, comprising:

receiving a script at each of a plurality of grid-computing devices;

compiling the script on each of the plurality of grid-computing devices, wherein compiling a script on a grid-computing device comprises compiling the script for an operating system of the grid-computing device;

reading input data in parallel by the plurality of grid-computing devices, wherein the input data comprises timestamped data partitionable into groups according to time series criteria;

deterministically distributing the timestamped data across the plurality of grid-computing devices based on the groups, wherein, for each of the groups, the timestamped data associated with the group is associated with one of the plurality of grid-computing devices;

generating a time series for each of the groups at respective ones of the plurality of grid-computing devices, wherein generating a time series comprises accumulating the timestamped data associated with a group into the time series;

executing the compiled script, at each of the plurality of grid-computing devices, on the time series associated with the grid-computing device to generate output data; and

writing the output data in parallel by the plurality of grid-computing devices.

12. The method of claim 11, wherein the input data comprises the timestamped data in an unsorted format, and wherein generating the time series further comprises sorting the timestamped data associated with the group before accumulating the timestamped data associated with the group.

13. The method of claim 11, wherein the script contains analyzing instructions for analyzing timestamped data and the time series criteria.

14. The method of claim 11, wherein accumulating the timestamped data associated with the group into the time series comprises accumulating the timestamped data into a fixed-interval and fixed-length time series based on a time span of the input data.

15. The method of claim 11, wherein a first group and a second group are associated with a particular grid-computing device of the plurality of grid-computing devices, wherein a first time series and a second time series are associated with the particular grid-computing device, and wherein executing the compiled script at the particular grid-computing device comprises:

allocating memory to the particular grid-computing device for the execution of the compiled script;

executing the compiled script on the first time series using the allocated memory;

executing the compiled script on the second time series using the allocated memory, wherein executing the compiled script on the second time series occurs before releasing the allocated memory; and

releasing the allocated memory after executing the compiled script on the first time series and the second time series.

16. The method of claim 15, wherein executing the compiled script on the first time series comprises instantiating computational objects and data objects in the allocated memory, and wherein executing the compiled script on the second time series comprises reusing at least a portion of the computational objects.

17. The method of claim 11, wherein reading the input data by a given grid-computing device comprises reading a subset of the timestamped data by the given grid-computing device, wherein deterministically distributing the timestamped data occurs on each of the plurality of grid-computing devices, and wherein deterministically distributing the timestamped data on the given grid-computing device comprises:

generating, for each group present in the subset of the timestamped data, a hash value using the time series criteria associated with the group;

calculating a destination identifier for each group by performing a modulo operation using the hash value as a dividend and a number of grid-computing devices in the plurality of grid-computing devices as a divisor; and

distributing timestamped data associated with each group by transmitting the timestamped data associated with the group to a destination grid-computing device identified by the destination identifier.

18. The method of claim 11, wherein the input data is stored on a distributed file system across a plurality of data files, and wherein reading the input data in parallel by the plurality of grid-computing devices comprises contemporaneously reading multiple data files of the plurality of data files by the plurality of grid-computing devices.

19. The method of claim 11, wherein deterministically distributing the timestamped data comprises bundling a plurality of entries of the timestamped data associated with a group into a bundle;

and distributing the bundle to a destination node associated with the group.

20. The method of claim 19, wherein deterministically distributing the timestamped data further comprises sorting and accumulating the bundle prior to distributing the bundle.

21. A computer-program product tangibly embodied in a non-transitory machine-readable storage medium, including instructions configured to cause a data processing apparatus to perform operations including:

receiving a script at each of a plurality of grid-computing devices;

compiling the script on each of the plurality of grid-computing devices, wherein compiling a script on a grid-computing device comprises compiling the script for an operating system of the grid-computing device;

reading input data in parallel by the plurality of grid-computing devices, wherein the input data comprises timestamped data partitionable into groups according to time series criteria;

deterministically distributing the timestamped data across the plurality of grid-computing devices based on the groups, wherein, for each of the groups, the timestamped data associated with the group is associated with one of the plurality of grid-computing devices;

generating a time series for each of the groups at respective ones of the plurality of grid-computing devices, wherein generating a time series comprises accumulating the timestamped data associated with a group into the time series;

executing the compiled script, at each of the plurality of grid-computing devices, on the time series associated with the grid-computing device to generate output data; and

writing the output data in parallel by the plurality of grid-computing devices.

22. The computer-program product of claim 21, wherein the input data comprises the timestamped data in an unsorted format, and wherein generating the time series further comprises sorting the timestamped data associated with the group before accumulating the timestamped data associated with the group.

23. The computer-program product of claim 21, wherein the script contains analyzing instructions for analyzing timestamped data and the time series criteria.

24. The computer-program product of claim 21, wherein accumulating the timestamped data associated with the group into the time series comprises accumulating the timestamped data into a fixed-interval and fixed-length time series based on a time span of the input data.

25. The computer-program product of claim 21, wherein a first group and a second group are associated with a particular grid-computing device of the plurality of grid-computing devices, wherein a first time series and a second time series are associated with the particular grid-computing device, and wherein executing the compiled script at the particular grid-computing device comprises:

allocating memory to the particular grid-computing device for the execution of the compiled script;

executing the compiled script on the first time series using the allocated memory;

executing the compiled script on the second time series using the allocated memory, wherein executing the compiled script on the second time series occurs before releasing the allocated memory; and

releasing the allocated memory after executing the compiled script on the first time series and the second time series.

26. The computer-program product of claim 25, wherein executing the compiled script on the first time series comprises instantiating computational objects and data objects in the allocated memory, and wherein executing the compiled script on the second time series comprises reusing at least a portion of the computational objects.

27. The computer-program product of claim 21, wherein reading the input data by a given grid-computing device comprises reading a subset of the timestamped data by the given grid-computing device, wherein deterministically distributing the timestamped data occurs on each of the plurality of grid-computing devices, and wherein deterministically distributing the timestamped data on the given grid-computing device comprises:

generating, for each group present in the subset of the timestamped data, a hash value using the time series criteria associated with the group;

calculating a destination identifier for each group by performing a modulo operation using the hash value as a dividend and a number of grid-computing devices in the plurality of grid-computing devices as a divisor; and

distributing timestamped data associated with each group by transmitting the timestamped data associated with the group to a destination grid-computing device identified by the destination identifier.

28. The computer-program product of claim 21, wherein the input data is stored on a distributed file system across a plurality of data files, and wherein reading the input data in parallel by the plurality of grid-computing devices comprises contemporaneously reading multiple data files of the plurality of data files by the plurality of grid-computing devices.

29. The computer-program product of claim 21, wherein deterministically distributing the timestamped data comprises bundling a plurality of entries of the timestamped data associated with a group into a bundle;

and distributing the bundle to a destination node associated with the group.

30. The computer-program product of claim 29, wherein deterministically distributing the timestamped data further comprises sorting and accumulating the bundle prior to distributing the bundle.