Method to create a partition-by time/tuple-based window in an event processing service
A method to create a partition by time/tuple based window in an event processing service is provided. When continuous data streams are received, tuples are stored in a data structure with partitions based upon partition keys. Only a specified amount of tuples may be stored in each partition. When a partition exceeds the specified number of tuples, the oldest tuples are removed from the data structure. Tuples stored beyond a specified time period are also removed from the data structure. Two data structures may also be used to implement a time/tuple based window. Tuples are stored in both a data structure with a partition by window and a data structure with a range window. Tuples are removed in the partition by window when tuples exceed the amount in the partition. Tuples are removed in the range window when tuples exceed a specified time period. The two data structures are synchronized.
1. A method comprising the steps of:
receiving one or more continuous data streams that comprise a plurality of tuples of data, wherein each tuple, within the plurality of tuples of data, is associated with a particular time, wherein the particular time is no earlier than the time of any previously generated tuple in the plurality of tuples received;
retaining in partitions of a data structure the plurality of tuples that fall within a sliding time-based window, wherein the sliding time-based window is bounded by (a) a specified relative range of time and (b) a maximum number of tuples to retain;
wherein retaining in partitions of a data structure the plurality of tuples that fall within a sliding time-based window comprises:
in response to receiving a tuple from the one or more continuous data streams, performing:
(a) removing, from each particular partition of said partitions of said data structure, tuples that exceed a specified amount of tuples to be stored in each particular partition, wherein the partitions in the data structure are based upon one or more partition keys;
(b) removing, from each particular partition of said partitions of said data structure, tuples that are associated with a particular time that is not within the specified relative range of time; and
(c) storing, in a particular partition among the partitions of the data structure, the tuple; and
wherein the method is performed by one or more computing devices.
2. The method of claim 1 , wherein the particular time for a tuple is based on the time that the tuple is received.
3. The method of claim 1 , wherein the particular time for a tuple is based on an order in which the tuple is received.
4. The method of claim 1 , wherein storing the tuple in the particular partition among partitions of the data structure is performed using a hash index.
5. The method of claim 1 , further comprising:
registering a query based upon CQL; and
in response to receiving a tuple from the one or more continuous data streams, evaluating the query with the tuple.
6. A method comprising the steps of:
receiving one or more continuous data streams that comprise a plurality of tuples of data, wherein each tuple, within the plurality of tuples of data, is associated with a particular time, wherein the particular time is no less than the time of any previously generated tuple in the plurality of tuples received;
retaining in a data structure the plurality of tuples that fall within a sliding time-based window, wherein the sliding time-based window is bounded by (a) a specified relative range of time and (b) a maximum number of tuples to retain, wherein the data structure comprises a first data structure and a second data structure;
wherein retaining in a data structure the plurality of tuples that fall within a sliding time-based window comprises:
in response to receiving a tuple from the one or more continuous data streams, performing the steps of:
(a) removing, from each particular partition of a first data structure, tuples that exceed a specified amount of tuples to be stored in each particular partition;
(b) removing, from a second data structure, tuples that are associated with a particular time that is not within a range of time;
(c) storing, the tuple, in the first data structure and the second data structure,
wherein tuples stored in the first data structure are stored in a particular partition among partitions based upon one or more partition keys, and
wherein tuples stored in the second data structure are sorted by the particular time of the tuples; and
(d) synchronizing tuples stored in the first data structure with tuples stored in the second data structure; and
wherein the method is performed by one or more computing devices.
7. The method of claim 6 , wherein the first data structure is a partition-by data structure.
8. The method of claim 6 , wherein the second data structure is a time-based data structure.
9. The method of claim 6 , wherein the particular time for a tuple is based on the time that the tuple is received.
10. The method of claim 6 , wherein the particular time for a tuple is based in an order in which the tuple is received.
11. The method of claim 6 , further comprising:
registering a query based upon CQL; and
upon receiving a tuple from the one or more continuous data streams, evaluating the query with the tuple.
12. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform:
receiving one or more continuous data streams that comprise a plurality of tuples of data, wherein each tuple, within the plurality of tuples of data, is associated with a particular time, wherein the particular time is no earlier than the time of any previously generated tuple in the plurality of tuples received;
retaining in partitions of a data structure the plurality of tuples that fall within a sliding time-based window, wherein the sliding time-based window is bounded by (a) a specified relative range of time and (b) a maximum number of tuples to retain; and
wherein retaining in partitions of a data structure the plurality of tuples that fall within a sliding time-based window comprises:
in response to receiving a tuple from the one or more continuous data streams, performing:
(a) removing, from each particular partition of said partitions of said data structure, tuples that exceed a specified amount of tuples to be stored in each particular partition, wherein the partitions in the data structure are based upon one or more partition keys;
(b) removing, from each particular partition of said partitions of said data structure, tuples that are associated with a particular time that is not within the specified relative range of time; and
(c) storing, in a particular partition among the partitions of the data structure, the tuple.
13. The computer-readable storage medium of claim 12 , wherein the particular time for a tuple is based on the time that the tuple is received.
14. The computer-readable storage medium of claim 12 , wherein the particular time for a tuple is based on an order in which the tuple is received.
15. The computer-readable storage medium of claim 12 , wherein storing the tuple in the particular partition among partitions of the data structure is performed using a hash index.
16. The computer-readable storage medium of claim 12 , further comprising:
registering a query based upon CQL; and
in response to receiving a tuple from the one or more continuous data streams, evaluating the query with the tuple.
17. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to:
receiving one or more continuous data streams that comprise a plurality of tuples of data, wherein each tuple, within the plurality of tuples of data, is associated with a particular time, wherein the particular time is no less than the time of any previously generated tuple in the plurality of tuples received;
retaining in a data structure the plurality of tuples that fall within a sliding time-based window, wherein the sliding time-based window is bounded by (a) a specified relative range of time and (b) a maximum number of tuples to retain, wherein the data structure comprises a first data structure and a second data structure; and
wherein retaining in a data structure the plurality of tuples that fall within a sliding time-based window comprises:
in response to receiving a tuple from the one or more continuous data streams, performing the steps of:
(a) removing, from each particular partition of a first data structure, tuples that exceed a specified amount of tuples to be stored in each particular partition;
(b) removing, from a second data structure, tuples that are associated with a particular time that is not within a range of time;
(c) storing, the tuple, in the first data structure and the second data structure,
wherein tuples stored in the first data structure are stored in a particular partition among partitions based upon one or more partition keys, and
wherein tuples stored in the second data structure are sorted by the particular time of the tuples; and
(d) synchronizing tuples stored in the first data structure with tuples stored in the second data structure.
18. The computer-readable storage medium of claim 17 , wherein the first data structure is a partition-by data structure.
19. The computer-readable storage medium of claim 17 , wherein the second data structure is a time-based data structure.
20. The computer-readable storage medium of claim 17 , wherein the particular time for a tuple is based on the time that the tuple is received.
21. The computer-readable storage medium of claim 17 , wherein the particular time for a tuple is based in an order in which the tuple is received.
22. The computer-readable storage medium of claim 17 , further comprising:
registering a query based upon CQL; and
upon receiving a tuple from the one or more continuous data streams, evaluating the query with the tuple.