{'fraction_non_alphanumeric': 0.024186471021869625, 'fraction_numerical': 0.008073858251132096, 'mean_word_length': 4.973579366743552, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Evaluation of Load Prediction Techniques for Distributed Stream Processing

Distributed Stream Processing (DSP) systems enable processing large streams of continuous data to produce results in near to real time. They are an essential part of many data-intensive applications and analytics platforms. The rate at which events arrive at DSP systems can vary considerably over time, which may be due to trends, cyclic, and seasonal patterns within the data streams. A priori knowledge of incoming workloads enables proactive approaches to resource management and optimization tasks such as dynamic scaling, live migration of resources, and the tuning of configuration parameters during run-times, thus leading to a potentially better Quality of Service. In this paper we conduct a comprehensive evaluation of different load prediction techniques for DSP jobs. We identify three use-cases and formulate requirements for making load predictions specific to DSP jobs. Automatically optimized classical and Deep Learning methods are being evaluated on nine different datasets from typical DSP domains, i.e. the IoT, Web 2.0, and cluster monitoring. We compare model performance with respect to overall accuracy and training duration. Our results show that the Deep Learning methods provide the most accurate load predictions for the majority of the evaluated datasets.


I. INTRODUCTION
Distributed Stream Processing (DSP) systems are responsible for extracting valuable insights from large streams of real-time data. Application areas include IoT data processing, click stream analysis, network monitoring, fraud detection, spam filtering, and news processing [1], [2]. These jobs require high throughput rates and low end-to-end processing latencies to support time-sensitive decisions. Input streams, however, are dynamic in nature and processing loads, therefore, have the potential to change significantly over time. Consequently, DSP systems like Heron [3], Spark [4] and Flink [5] are able to scale horizontally across a cluster of commodity nodes in order to accommodate different processing loads. With this potential for workloads to fluctuate over time and the ability of systems to dynamically adjust configurations at runtime, research into approaches for the adaptive management of resources has grown in popularity in recent times.
Prominent applications within this domain include: the automated dynamic scaling of resources which aims to reduce over-and under-provisioning, minimizing operating costs and preventing possible reductions in the service quality [6]- [9]; The live migration of functionality/state across the network where cluster metrics are collected, processed, and scanned for anomalies which might reveal performance degradations and/or signs of component failure [10]- [12]; and the automatic system tuning where dynamic runtime adjustment of system configurations are performed in order to improve overall system availability and reliability [13]- [15]. The majority of these approaches rely on coarse-grained metrics to reactively make remediation decisions. In some cases these metrics are also system specific and/or require a customized version of the system. Interestingly, an increasing number of approaches use Time Series Forecasting (TSF), a more generalizable and proactive basis for making good decisions.
Through forecasting what is to come we are better able to anticipate and plan for the future. While the use of TSF is not new in the context of DSP systems, in most cases it requires experts to pick the appropriate method and configure it to the situation at hand. Moreover, to the best of our knowledge, no comprehensive comparison has been conducted thus far where previous attempts at comparing these methods were inconclusive and present results obtained from a small number of datasets [16].
In this paper we evaluate seven methods which meet the requirements for performing TSF for DSP jobs across nine different streaming datasets. We select various classical TSF methods as well as two Deep Learning (DL) methods. The datasets were sampled across various application domains, including: IoT, Web 2.0, and cluster monitoring. Each consists of a single value representing the number of events arriving at the DSP system every second and thus represents the load upon the system. Based on the three main use cases: dynamic scaling, live migrations, and system tuning; we investigate three sampling rates: the first for more shorter term higher granularity predictions, the second for mid-range predictions; and the third for more longer term lower granularity predictions. Critically, we provide implementations for automatically optimizing the hyperparameters of the prediction models thus removing the necessity for configuring them by hand.
The remainder of the paper is structured as follows: Section II identifies the use cases and requirements for performing TSF for DSP systems. Section III presents the TSF methods, experimental design, evaluation metrics, time series datasets, and the experimental setup. Section IV presents and discusses our results. Section V describes the related work on TSF for load prediction, while Section VI concludes the paper.

II. PROBLEM ANALYSIS
In this section we first motivate the use of TSF for DSP systems by exploring different use cases and then explain the requirements for TSF for such tasks.

A. Use Cases
We identified three use cases where accurate load prediction would be quite useful for efficiently running DSP jobs despite varying input rates.
1) Dynamic Scaling: The scalability of DSP systems is achieved by partitioning the entire data streams among dataparallel task instances that are deployed across clusters of computers. Streaming jobs are by nature long-running and streaming workloads often change over time. Many DSP systems have the ability to scale dynamically, yet the difficult task of deciding by how much and when is typically still left up to the user with off-the-shelf DSP systems. Furthermore, the current research on this problem relies on coarse-grained metrics such as CPU utilization, throughput, and backpressure which tend to show incorrect provisioning, oscillations, and long convergence times [8]. There is, therefore, a promising opportunity to combine TSF with performance modeling in order to scale parallelism and resource usage proactively based on predicted loads. For this use case a shorter prediction time horizon is important, i.e. 5 minutes.
2) Timing of Live Migrations: As DSP systems approach even greater scales, the number of things that can go wrong increase as well. Live migrations allow administrators to transparently tune the performance of computing infrastructures when performance degradations in cluster nodes are detected, migrating system functionality and state over the network. Much of the research in this area is focused on the methods for detecting these anomalies, however, the question of when these preemptive actions should take place is likewise an important question to answer. Here TSF can provide a way to automate this process by predicting periods of low utilization where changes to the cluster will have potentially less of an impact on overall performance. For this use case a mid-range prediction time horizon, i.e. 15 minutes, is important.
3) Automatic System Tuning: Self-tuning systems are those which are capable of optimizing their own internal configuration parameters in order to maximize or minimize the fulfilment of one or more objective functions. If done correctly, this can yield systems which are more performant, cost effective, reliable, and power efficient. In order to achieve this, approaches within this domain commonly conduct profiling runs and/or use historical data in order to model performance behaviors. TSF, when combined with these models, not only allows the system to determine which configurations need tuning and by how much, but critically also the timings of these updates. As workloads change over time, delaying configuration updates can greatly improve the effectiveness of optimizations. For this use case, longer-term forecasts with hourly time horizons are most useful.

B. Requirements
DSP systems come with their own specific requirements which need to be taken into consideration while designing approaches to load prediction. In this section we define these requirements and present them as follows: 1) Minimal Configuration: Solutions should follow a plugand-play approach. User configuration requirements for tuning model hyperparameters should be kept to an absolute minimum. As input data streams and infrastructures deviate greatly, solutions should provide automatic optimization mechanisms to quickly adapt to a wide range of deployments.
2) Limited Model Inputs: Inputs consist of the ingress rate values, i.e. the sum of the events entering the source operators of the DSP job per second. As this is a scalar value, the focus should be on univariate time series prediction. Concerning the amount of data that is used for initial training, this depends on how long the DSP job has been running and availability of metrics data. The default retention periods of time series databases such as InfluxDB 1 and Prometheus 2 commonly used for storing such data is 7 and 15 days respectively. Thus, a limited amount of training data should be expected.
3) Frequent Model Updates: As new observations are continually being produced, models should consider these for their forecasts such that the quality of the predictions does not degrade. This can be achieved by periodically retraining the models or updating them before each new prediction with the latest observations produced since the last prediction was made. The parameters in classical methods need to be updated to the most recent observations to capture the changes in the time series. Opposed to that ML models inherently incorporate the most recent observations to perform inference, making updates to the model weights not as urgent.
4) Variable Forecasting Length: Models which support multi-step time series forecasting are required. Understanding how expected workloads change over time is an important aspect to consider when designing strategies for the use cases which we have previously defined. Solutions should have the ability to incorporate various sample rates to match desired time horizons.

III. METHODOLOGY
In this section we present our experiment methodology by introducing TSF methods we investigate, time series datasets upon which we base our comparison, the evaluation metrics by which we measure the performance of our models, and the setup of our experiments. The code and datasets for our experiments can be found in the associated github repository 3 .

A. TSF Methods
The following are methods commonly used in the domain of TSF. One of the targets of our investigation is to validate whether or not these methods are suitable considering the requirements defined and presented in the previous section. These methods are as follows: 1) Baselines -Last Observation and Last Day Observation: The two performance baseline models are established by taking either the last observation or the observation from before 24 hours, and projecting it forwards for the length of the forecast.
3) TES: Holt and Winters [17], [18] extended SES and developed Triple Exponential Smoothing (TES) which allows incorporating trend and seasonality. 4) ARIMA: Auto Regressive Integrated Moving Average (ARIMA) is a widely used approach for time series forecasting [19]. 5) SARIMA: Due to the seasonal nature of the datasets, we included Seasonal Auto Regressive Integrated Moving Average (SARIMA) models, which add seasonality to ARIMA models [19].
6) Prophet: Prophet [20] is a popular open source time series forecasting library developed by Facebook. It aims at making time-series data analysis available to non-expert users. 7) CNN: Convolutional Neural Network (CNN) architectures have been used successfully for time series prediction on multiple occasions [21], [22], as they allow for increased training speed and deep architectures due to shared filters. 8) GRU: Recurrent Neural Networks (RNNs) allow for the memorization of past observations which makes them suitable for applications on time series [23], [24]. We design a gated recurrent unit (GRU) [25].

B. Evaluation Metrics
Our main objective is the Symmetric Mean Absolute Percentage Error (SMAPE), which is commonly used for forecasting problems when dealing with data sources of varying value scales [26]- [28]. SMAPE is defined as and delivers an error value between 0% and 100%. It is furthermore utilized as the loss function for our chosen DL methods as it is invariant to absolute errors. We also investigate another commonly used metric in regression tasks, the Root Mean Square Error (RMSE), which is defined as and allows us to assess the goodness of our predictions in terms of actual similarity to the true values.

C. Time Series Datasets
We selected 9 heterogeneous and univariate datasets to investigate the applicability of our chosen methods on varying data. These datasets represent the expected load in a DSP system. The time series describe the sum of the events entering the source operators of a DSP job per second.
1) IoT Traffic: A synthetic dataset created using the SUMO [29] traffic simulator and the TAPAS cologne 4 simulation scenario. The data represents the number of vehicles on the streets per second over time.
2) NYC Taxi: A dataset from the NYC Taxi & Limousine Commission 5 on taxi rides in New York City. We aggregated the number of taxi rides of all providers during every five minutes over a three week period in January 2020.
3) Alibaba Cluster Traces: Production data originating from an Alibaba cluster 6 in 2018. We extract the start time of batch tasks over a 7-day period and aggregate them.
4) Google Cluster Traces: Workload traces recorded from eight different Google Borg cells during the month of May 2019 7 . From this trace we extracted information about instance events over a randomly selected period of 21 days. 5) Wikipedia Pageviews: We used the Wikipedia API 8 to extract the number of page views per hour for a period of three weeks in July 2019. Subsequently, we interpolate between the values to derive different sampling rates. The procedure is conducted both for the German and English Wikipedia, and thus results in two different datasets.
6) Avazu: This dataset is created by using a click-through rate prediction dataset from Kaggle 9 , aggregating the clicks per hour over time, and linearly interpolating between the aggregated values to obtain different sampling rates. 7) Hortonworks: Clickstream events taken from a tutorial on visualizing clickstream data provided by Hortonworks 10 . We extracted the event timestamps on a per second granularity and aggregate them to the respective granularities.
8) Retail Rocket: E-commerce data containing events of the Retail Rocket recommender system 11 . We construct our dataset by aggregating behaviour data, such as click events, over a three week period.

D. Dataset Adjustements
All datasets have been adjusted to resemble realistic event rates in DSP jobs. Following from the use cases described in Section II-A, we resampled the datasets to sampling rates of 5 minutes, 15 minutes, and 1 hour.
We assume normally distributed noise in the datasets. In order to estimate the expected relative error from the datasets with original granularity of only 1 hour, we made use of the aforementioned datasets with 5-minute granularity. First, we used their resampled variant with sampling rate of 1 hour and resampled it to a 5-minute sampling rate. Next, we interpolated the missing observations using a second order spline function and calculated the standard deviation of the differences between the interpolated 5-minute sampling rate dataset and the original 5-minute granularity dataset. The expected relative error is σ e ≈ 1%. Subsequently, we selected the datasets with original granularity of 1 hour and resampled them to a sampling rate of 5 minutes. The missing observations were interpolated. To simulate the aforementioned normally distributed noise we sampled i relative errors from a normal distribution N ∼ (0, σ e ), where i is the amount of observations in the respective dataset. These sampled errors were then multiplied with the corresponding observations and added to them. Finally, we resampled these new datasets also to a sampling rate of 15 minutes.
Additionally, we scaled and shifted all datasets to have a mean message/second rate of µ ≈ 108 000, and a standard deviation of σ ≈ 12 000. These lie mostly within a range of approximately 90 000 -150 000. This was done to make absolute metrics comparable across the datasets. These adjustments result in the final datasets at three different sampling rates.

E. Experimental Setup
The training of the models as well as inference was conducted on a dedicated machine equipped with a GPU. Specifications and software versions can be found in Table I. 1) Experiment Execution: Each of our experiments examines the forecasting capabilities of a certain method on a specific dataset. We conduct 189 experiments overall, exploring seven methods on nine datasets with three different sampling rates. For each sampling rate, we define a different forecast horizon: For the 5 minute interval, we aim at predicting only the next value, the 15 minute interval comes with a horizon of four values, and the one hour interval is associated with a prediction horizon of twelve. This reflects our different use cases and the corresponding prediction capabilities. For the DL methods, i.e. CNN and GRU, we split each dataset along the time domain into training, validation, and test subset (60%, 20%, 20%). The validation subset is used during hyperparameter optimization to abort unpromising trials and to determine the best trial. All other methods conduct a split into training and test subset (80%, 20%) and thus effectively train on more data. This is illustrated in Figure 1.
2) Training and Model Configuration: We fit the level smoothing factor α of SES models based on their achieved Akaike information criterion (AIC). For TES models, we additionally fit β and γ, the smoothing factors for trend and seasonality. Furthermore, we examine the effect of assuming an additive or multiplicative seasonality.
For training ARIMA models, we perform a hyperparameter search on p and q, and test the order of first-differencing with d = [0, 1]. For fitting SARIMA models, the additional seasonal hyperparameters P , D, and Q are integrated into the hyperparameter search. We set boundaries for P and Q, and additionally search explicitly the space defined by d × D = [0, 1] × [0, 1]. In the process, we assume a seasonal period of 24 hours. For both ARIMA and SARIMA, the AIC estimator is used to determine the best hyperparameters.
For Prophet, the hyperparameter optimization and fitting is handled entirely by the library.
For the machine learning models we search for optimal configurations of a variety of different hyperparameters such as number of layers, number of neurons, learning rate, and dropout rate. For both CNN and GRU, we are moreover especially interested in the optimal length of input sequences extracted from the training data. The details of the spanned hyperparameter searchspaces are described in our repository, along with further technical details.

A. Limitations
Since Prophet is primarily designed to detect long term seasonality, it appears to struggle with short sampling rates. When fitting it to data with 5 minute or 15 minute sampling rate, the library only predicts hourly data and interpolates between these data points during prediction. We thus decided to only include the hourly sampling rate model into our evaluation.
The coefficients for the SARIMA models are being computed analytically. At a sampling rate of 5 minutes and a daily seasonality, one seasonal period consists of 288 observations, which renders the computation infeasible in our scenario. Hence, we excluded the evaluation of SARIMA on the 5 minute sampling rate datasets.

B. Performance
The condensed results plots in Figure 2 together with the detailed insights given in Table II allow for a comprehensive discussion of the model performances.
From Figure 2a, we can infer that across all datasets and sampling rates, the DL methods are the best or among the best performing methods with a stable prediction performance. The stability aspect also holds true for TES, whereas all other classical methods are either experiencing difficulties for certain sampling rates, or are even not applicable to them. The reported SMAPE results are also confirmed by the reported RMSE results in Figure 2b. We have ensured to make the RMSE a valid metric by adjusting the datasets to be in the same range with a similar mean and standard deviation.
Summarizing Figure 2, we identify that the DL methods performed best across all use cases, with no universal alternative from the classical methods. We note that on average, TES outperforms our installed baselines across all sampling rates, while being comparably fast to train and stable in prediction performance. Meanwhile, ARIMA shows good prediction capabilities on the 5 minute and 15 minute sampling rate datasets, yet fails to capture seasonal patterns present in datasets with hourly sampling rate.
Complementing the averaged scores in Figure 2, we present detailed results with Table II. They indicate that the DL methods exhibit a similarly good performance over all experiments. In the rare cases of inferior performance to our baselines, the performance degradation affects both models in the majority of situations, leading to the assumption that patterns found in the test data were not present in the training data. In fact, for two datasets, namely the Google and Hortonworks datasets with a sampling rate of 15 minutes, there is not a single model that is able to outperform the baseline, confirming our previous interpretation of certain results.
On the other hand, for 5-minute sampling rate, several models can be identified, each of which outperforms the baselines across all corresponding datasets. Figure 3 shows an example of the different model behavior for the hourly sampled test data from Retail Rocket. It can be seen that the DL models as well as Prophet fit the seasonal pattern well, while the remaining classical models are more responsive to noise. Additionally, we note that methods which do not capture seasonality in their models perform poorly on the task to forecast the approaching 12 hours given hourly sampled data. Interestingly, Prophet performed rather poorly in this task as well, failing to beat the baseline models in most cases.
The results further reveal that for hourly sampling and forecast horizon of 12 observations, CNN is among the best predictors with the exception of two outliers. SARIMA works well on hourly data as it has short seasonal patterns and thus states a good alternative from the classical methods, but struggles with long-term seasonality as present in the data sampled at 15 minutes. GRU are the best performing models for the use case of 15 minute sampling and a forecast horizon of four samples, and are closely followed by the CNNs. ARIMA and TES perform reasonably similar and make for good alternatives from the classical methods. While the GRU models perform best on predicting observations with a forecast horizon of 1 at a sampling rate of 5 minutes, ARIMA performs almost as well across all datasets.
In conclusion, we find the DL methods as well as TES to be the most universal predictors, achieving good prediction results on the various datasets, sampling rates and hereby dataset sizes.

C. Duration
We measured the time needed to find optimal hyperparameters and fit the respective models, as well as the average time it takes a model to predict the next observations and possibly fine-tune it to the most recent observation. The results are visualized in Figure 4. As expected, the required time for training and fine-tuning depends on the amount of available training data, which is shown by the differences between the various sampling rates.
It can be observed that there are significant differences in the time needed for initial fitting of the models. While the methods based on exponential smoothing are superior to the ARIMA variants, it can also be seen that the more complex variants of the respective methods (i.e. TES and SARIMA) require more time due to the extended hyperparameter search space. In comparison, Prophet is slightly more time-demanding than exponential smoothing, yet notably faster than the ARIMA   methods. Although the DL methods are not directly comparable due to the utilization of different hardware, it is worth-mentioning that the training in general takes relatively long. Here, the training duration depends not only on the hyperparameter searchspace alone, but also on the specified configuration in terms of parallelism, maximum execution time, and preemptive termination of trials, as well as the total number of trials to investigate. When using the trained models for prediction, it can be observed that all classical methods are significantly slower than the DL methods. The main reason for this is that the classical models need to be updated to the most recent observations to adapt to changes in the timeseries. This also explains the differences in time needed for the individual sample rates. This is in contrast to our DL methods, where the model parameters after the initial training are preserved and used for prediction, and the models only need to be supplied the most recent observations as input data for the context update.
In summary, the DL methods require a notable amount of time for initial training but are fast when doing prediction, whereas the classical methods are faster to fit while requiring time-consuming updates constantly over time.
V. RELATED WORK TSF for load prediction is used by energy providers and electricity grid operators to plan ahead and meet demand and supply [30]. Nevertheless, it has also long been used in areas such as communication networks and cloud infrastructures. Understanding future load requirements for communication networks gives providers the ability to optimize resources allowing for better quality of service [31]- [33]. In cloud services, load prediction is used to balance resources within a data center as well as for scheduling live migrations [10], [11], [34]. Throughout all of these works, classical and DL methods have been used repeatedly. However, none has been directly compared under our defined requirements for performing TSF in DSP systems, such as minimal configuration and limited model inputs. In the context of DSP, TSF methods have been used in diverse forms and for varying reasons [9], [35]- [38]. While previous works successfully apply a selected method to a concrete problem, to the best of our knowledge, there is no related work that compares multiple TSF methods for DSP. Additionally, this paper formulates requirements for TSF for DSP and performs an evaluation on multiple real-world and one synthetic datasets from different domains.

VI. CONCLUSION
This paper presented an evaluation of TSF methods for DSP systems. The methods we assessed include multiple classical and two DL models: SES, TES, ARIMA, SARIMA, Prophet, GRU, and CNN. The methods were evaluated across nine datasets from the IoT, Web 2.0, and cluster monitoring domains. The results show that both CNN and GRU had the best prediction performance across the majority of the datasets, while requiring more time for initial model training. However, depending on the use case we found that there is always at least one classical model performing similarly well as the DL models, while being relatively fast to train. In general, the best performing models demonstrate to cope well even though the amount of training data was limited. In terms of configuration, it is more straightforward to optimally configure the diverse classical methods.
Based on our results, we deem both TES and the DL methods, and even a combination of these classes of approaches promising for use in the domain of DSP. Depending on the available resources and the use case at hand, one method might be preferable over the others.