A Survey of Distributed Data Stream Processing Frameworks <s> 1) PROGRAMMING MODELS <s> Continuous queries in a Data Stream Management System (DSMS) rely on time as a basis for windows on streams and for defining a consistent semantics for multiple streams and updatable relations. The system clock in a centralized DSMS provides a convenient and well-behaved notion of time, but often it is more appropriate for a DSMS application to define its own notion of time---its own clock(s), sequence numbers, or other forms of ordering and times-tamping. Flexible application-defined time poses challenges to the DSMS, since streams may be out of order and uncoordinated with each other, they may incur latency reaching the DSMS, and they may pause or stop. We formalize these challenges and specify how to generate heartbeats so that queries can be evaluated correctly and continuously in an application-defined time domain. Our heartbeat generation algorithm is based on parameters capturing skew between streams, unordering within streams, and latency in streams reaching the DSMS. We also describe how to estimate these parameters at run-time, and we discuss how heartbeats can be used for processing continuous queries. <s> BIB001 </s> A Survey of Distributed Data Stream Processing Frameworks <s> 1) PROGRAMMING MODELS <s> A windowed query operator breaks a data stream into possibly overlapping subsets of data and computes a result over each. Many stream systems can evaluate window aggregate queries. However, current stream systems suffer from a lack of an explicit definition of window semantics. As a result, their implementations unnecessarily confuse window definition with physical stream properties. This confusion complicates the stream system, and even worse, can hurt performance both in terms of memory usage and execution time. To address this problem, we propose a framework for defining window semantics, which can be used to express almost all types of windows of which we are aware, and which is easily extensible to other types of windows that may occur in the future. Based on this definition, we explore a one-pass query evaluation strategy, the Window-ID (WID) approach, for various types of window aggregate queries. WID significantly reduces both required memory space and execution time for a large class of window definitions. In addition, WID can leverage punctuations to gracefully handle disorder. Our experimental study shows that WID has better execution-time performance than existing window aggregate query evaluation options that retain and reprocess tuples, and has better latency-accuracy tradeoffs for disordered input streams compared to using a fixed delay for handling disorder. <s> BIB002 </s> A Survey of Distributed Data Stream Processing Frameworks <s> 1) PROGRAMMING MODELS <s> What does a data stream mean? Much of the extensive work on query operators and query processing for data streams has proceeded without the benefit of an answer to this question. While such imprecision may be tolerable when dealing with simple cases, such as flat data, guaranteed physical order and element-wise operations, it can lead to ambiguities when dealing with nested data, disordered streams and windowed operators. We propose reconstitution functions to make the denotation and representation of data streams more precise, and use these functions to investigate the connection between monotonicity and non-blocking behavior of stream operators. We also touch on a reconstitution function for XML data. Other aspects of data stream semantics we consider are the use of punctuation to delineate finite subsets of a stream, adequacy of descriptions of stream disorder, and the formal specification of windowed operators. <s> BIB003 </s> A Survey of Distributed Data Stream Processing Frameworks <s> 1) PROGRAMMING MODELS <s> Many "big data" applications must act on data in real time. Running these applications at ever-larger scales requires parallel platforms that automatically handle faults and stragglers. Unfortunately, current distributed stream processing models provide fault recovery in an expensive manner, requiring hot replication or long recovery times, and do not handle stragglers. We propose a new processing model, discretized streams (D-Streams), that overcomes these challenges. D-Streams enable a parallel recovery mechanism that improves efficiency over traditional replication and backup schemes, and tolerates stragglers. We show that they support a rich set of operators while attaining high per-node throughput similar to single-node systems, linear scaling to 100 nodes, sub-second latency, and sub-second fault recovery. Finally, D-Streams can easily be composed with batch and interactive query models like MapReduce, enabling rich applications that combine these modes. We implement D-Streams in a system called Spark Streaming. <s> BIB004 </s> A Survey of Distributed Data Stream Processing Frameworks <s> 1) PROGRAMMING MODELS <s> As users of "big data" applications expect fresh results, we witness a new breed of stream processing systems (SPS) that are designed to scale to large numbers of cloud-hosted machines. Such systems face new challenges: (i) to benefit from the "pay-as-you-go" model of cloud computing, they must scale out on demand, acquiring additional virtual machines (VMs) and parallelising operators when the workload increases; (ii) failures are common with deployments on hundreds of VMs-systems must be fault-tolerant with fast recovery times, yet low per-machine overheads. An open question is how to achieve these two goals when stream queries include stateful operators, which must be scaled out and recovered without affecting query results. Our key idea is to expose internal operator state explicitly to the SPS through a set of state management primitives. Based on them, we describe an integrated approach for dynamic scale out and recovery of stateful operators. Externalised operator state is checkpointed periodically by the SPS and backed up to upstream VMs. The SPS identifies individual operator bottlenecks and automatically scales them out by allocating new VMs and partitioning the checkpointed state. At any point, failed operators are recovered by restoring checkpointed state on a new VM and replaying unprocessed tuples. We evaluate this approach with the Linear Road Benchmark on the Amazon EC2 cloud platform and show that it can scale automatically to a load factor of L=350 with 50 VMs, while recovering quickly from failures. <s> BIB005
The programming model of a DSPEs consist of a processing task which receives stream items from a source, performs some processing, and then emits some items to a sink  . Specifically, a programming model is an abstraction of the DSPE that allows for stream transformations and processing. Given the unbounded nature of streaming data, it is therefore, not feasible to have a global view of the incoming streaming data  . Hence, data is processed in chunks by defining finite, bounded time windows on top of an infinite data stream. A window in DSPEs is usually defined by either a time duration or a record count. The time-based window speci- fies a moving view that decomposes a stream into subsets and computes a result over each subset BIB002 , BIB003 while the count-based window is sized by the number of events included in the window. This enables transformations to be executed on the records contained in the window  . Time-based windows are common in stream applications BIB001 . Luu  described three commonly used timebased windowing patterns that most modern DSPEs support as shown in Fig. 2 . (i) Fixed or tumbling windows divide the incoming data stream into fixed-size segments, each with a window length, a start time, and an end time. Each incoming piece of data gets slotted into one and only one fixed window making it easy to perform aggregation transformations. (ii) Sliding windows divide the incoming stream of data into fixed-size segments, each with a window length and a sliding interval. If the sliding interval is the same size as the window length, then it is the same as the fixed window. If the sliding interval is smaller than the window length, then one or more pieces of data will be included in more than one sliding window; aggregation transformations in a sliding window will produce a smoother result than in the fixed window because of the overlapping of the windows. (iii) Session windows, unlike the fixed and sliding windows, do not have a predetermined window length. Instead, it is determined usually by a gap of inactivity that is greater than some threshold. A session is a burst of user activity followed by period of inactivity or timeout  . Many transformations on streams are carried out on each record independently and are often called stateless. Among the common types of stateless transformations are (i) Map, which transforms one record to another record, (ii) Filter, which filters out the records that do not satisfy a given predicate and (iii) FlatMap, which transforms each record to a stream and then flattens these streams into a single stream by combining the stream elements. Transformations that require the processor to maintain internal state across the records and are called stateful. Common types of stateful transformations are (i) Aggregation, which combines all the records to produce a single value, (ii) Group-and-aggregate, which extracts a grouping key from the record and computes a separate aggregated value for each key, (iv) Join, which joins same-keyed records from several streams, and (v) Sort, which sorts the records observed in the stream. In stateful transformations, all the ingested records within a specified time window are included in the compu-tation. The concept of windowing, meaningfully bounds the scope of the aggregation and can represent distinct or partially overlapped time frames  . In summary, DSPEs can do real time streaming data processing where tuples are processed as soon as they arrive or do batch data processing where time windows are used to split the tuples into batches or do both. A batch of stream elements for a given stream is a finite subset of the stream in a time interval. Distributed DSPEs usually process incoming data streams either natively (one tuple at a time) or in micro batches. A query or process is represented as a DAG consisting of a set of node operators, and the source and sink data stream operators. Operators can be either stateless or stateful. Most distributed DSPEs use the continuous operator model BIB004 where streaming computations are performed by a set of long-lived stateful operators. Each operator processes data stream records as they arrive by updating the internal state and sending new records in response BIB005 .