# More on Pipelined Dynamic Scheduling of Big Data Streams
## 2 Related Work and Discussion  
Generally, the change of parallelization degree (number of nodes working in parallel) of a stream processing system is the main reason that causes the necessity for state migrations. In such cases, the usual practice is to use some type of system monitoring, where a system monitor observes the usage of the system's resources (links, CPU, memory) [5; 8; 9; 10; 11; 12]. After monitoring, some type of strategy determines where the tasks are going to migrate. In this paragraph, we discuss papers that mostly focus their attention on migration policies. In [13], the authors define five operator patterns based on which they generate rules for increasing scalability by load distribution and achieving elasticity: (1) _Simple Standby:_ For a critical query node \(N\) there is a standby node \(S\) on a separate unit. This standby node is activated in case of failure of node \(N\), so \(N\) needs to be continuously monitored. (2) _Checkpointing:_ Similar to 1, but supports stateful operators for storing and accessing information across multiple events (stateless operators store and access information based on the last event only). The state of \(N\) is periodically monitored and the standby node \(S\) restarts from this checkpoint. (3) _Hot Standby:_ The input stream is sent to redundant nodes \(S\), usually by multicasting, so they act as hot standby's whenever the time of failure incurred during checkpointing is unacceptable. This pattern works for stateful and stateless operators. (4) _Stream Partitioning:_ The input stream is partitioned and each tuple is directed to one of the nodes \(\mathrm{N}_{1},\ldots N_{n}\). This pattern is used to exploit data parallelization. and (5) _Stream Pipelining:_ Same as pattern 4, but the streams are placed to different computation units to be processed in a pipeline fashion. In [14], the authors manage and expose the operator state directly to the stream processing system. In this way, they create an integrated approach for dynamic scale out and recovery of the stateful operators. The operator state is periodically checkpointed by the stream processing engine and the state is backed-up. When possible bottlenecks are identified through monitoring of the CPU utilization, a scale-out operation is invoked and new virtual machines are allocated. The checkpointed state is re-partitioned and the overall processing is divided between the new processing elements. This scaling out increases parallelization when the system resource monitoring gives results which are above a predefined threshold. Recovery of failed operators is achieved by restoring the checkpointed state on a new virtual machine and replaying and unprocessed tuples. [PERSON] et al. [15] propose an approach named FUGU, which optimizes the scaling policy automatically. Thus the user avoids the need to set the configuration parameters for a selected scaling policy. The idea is to use an online parameter optimization approach. The approach employs three algorithms: a Scaling Algorithm, that takes decisions that characterize a host as overloaded or underloaded, based on a vector of measurements regarding the node utilization (CPU, memory, and network elements), an Operator Selection algorithm, which decides which operators to move, and an Operator Placement algorithm, which determines where to move these operators. Each scaling decision is translated into a set of moving operators. If the system is found to be underloaded, it selects all operators running on the least loaded hosts, in other words, it releases a host with minimum latencies (scale-in). When a host is found overloaded, the Operator Selection algorithm chooses a subset of operators to remain in the host, so that their summed load is smaller than the given threshold. The remaining operators will move to a new host (scale-out). The operator placement is modeled as a problem defined by nodes occupying a CPU capacity and by operators with a certain CPU load.