Keep Calm and React with Foresight: Strategies for Low-Latency and Energy-Efficient Elastic Data Stream Processing

50 %
50 %
Information about Keep Calm and React with Foresight: Strategies for Low-Latency and...

Published on March 15, 2016

Author: tizianodem



2. INTRODUCTION The recent years have been characterized by an explosion of data streams generated by a variety of sources: social networks, sensors, stock markets... Data Stream Processing (DaSP) applications : real-time processing of continuous data streams with stringent Quality of Service (QoS) requirements in a very dynamic environment. Requirements: Parallelism to obtain performance Elasticity to handle dynamicity Cost effectiveness Goal: proposal of latency-aware and energy efficient scaling strategies with predictive capabilities

3. Stateful Operator BACKGROUND Applications are expressed as graphs of operators (vertices) that communicate through streams (edges). We will focus on stateful operators. In many contexts, the physical input stream conveys tuples belonging to multiple logical substreams. Examples from network monitoring, financial applications, social networks, ... Require to maintain separated state (e.g. window) for each substream and apply computation on a substream basis. Source Side

4. BACKGROUND Parallelized partitioned stateful operator: each state partition owned by an operator replica ○ Splitter distributes tuples using an hash function : →[1:n] The most used parallel schema, implemented in various DaSP frameworks (e.g. Storm) ○ Merger collects the results from the replicas REPLICA1 REPLICAn SPLITTER MERGER input stream output stream Scaling strategies will change the operator configuration ( e.g. number of replicas, CPU frequency,...) in order to face all the D-* challenges DYNAMICITY ○ the arrival rate; ○ keys frequency distribution; ○ processing time per tuple.

5. SYSTEM CONTROLLER disturbances MODEL PREDICTIVE CONTROL Model Predictive Control (MPC) approach: actions are taken by using a model to predict the future system behavior over a limited prediction horizon h. Optimizer System Model Disturbance Forecaster decision variables System observed through disturbances at each control step . Future values are estimated A system model is used to compare and evaluate alternative configurations An optimization problem is solved The result is a reconfiguration trajectory : Only the first one is applied

6. ELASTIC OPERATOR The parallel schema incorporates now the controller R R S M CONTROLLER Measured disturbances (for step -1): ○ ( A , A ): mean and standard deviation of inter-arrival time per triggering tuple; ○ { k } keys frequency distribution; ○ { k } computation time for each key. Decision variables: u( )= Number of replicas (n) and CPU frequency (f) System models: Used to predict the values of the QoS variables with a given configuration:

7. SYSTEM MODELS Latency (or more formally the response time): we use a Queueing Theory approach. For the control step is expressed as: To find WQ we model the operator as a G/G/1 queueing system (Kingman): Feedback mechanism to increase the precision Waiting Time Processing Time

8. SYSTEM MODELS Power : owing to the infinite nature of DaSP computations, minimize the instant power is the main solution to reduce energy consumption Power at step is proportional to the number of replicas, the CPU frequency and square of supply voltage (depends from f) Rationale: computation time is inversely proportional to frequency. That is, halving the frequency we will double the computation time but we will use less than half the Power. This model will be used to compare different operator configurations.

9. OPTIMIZATION The MPC-based strategies solve at each step the optimization problem:

10. EXPERIMENTS Our control strategies have been evaluated on an HFT application over a multicore HFT R R S M CONTROLLER Source Consumer financial quotes Two different datasets (2836 symbols): ○ a real one (trading day, accelerated 100x) ○ a synthetic (random walk arrival rate) All the dynamicity factors to handle. fitting on aggregated quotes Window of 1000 tuples, slide 25 tuples.

11. EVALUATION Two control strategies: ○ Lat-Node: resource cost depends on the number of used cores; ○ Lat-Power: resource cost depends on the power consumed. Arrival rate is predicted with Holt-Winter filter. We explicitly consider the case of =0. Control step = 1 second Strategies evaluated in terms of SASO properties: ○ Stability: no frequent reconfigurations; ○ Accuracy: minimize the QoS violations; ○ Settling time: find a stable configuration quickly; ○ Overshoot: no overestimating the configuration. Target architecture: dual CPU Intel Sandy Bridge Xeon E5-2650 16 physical cores with DVFS feature.

12. STABILITY Consider Lat-Node and synthetic workload we have: The switching cost act as a stabilizer.

13. STABILITY Considering all the scenarios: The switching cost reduce the number of reconfigurations. This effect is partially mitigated by increasing the horizon length.

14. ACCURACY We detect a QoS violation each time the average latency is higher than a threshold δ (δ=1.5 ms for Synt. WL, δ=7ms for Real WL) The switching cost allows the strategy to reach a better accuracy. This is partially offset by increasing the horizon length.

15. OVERSHOOT We considered the resource consumptions. The use of the switching cost causes overshoot. This can be mitigated by using a longer horizon

16. RESOURCE CONSUMPTION We studied the power consumption (CPU cores) of the Lat-Node and Lat- Power strategies Average power saving of 18.2% and 16.5%

17. SETTLING In cases of sudden workload challenges, the strategy should be able to reach rapidly the right configuration The switching cost reduces the average reconfiguration amplitude. Better settling time can be achieved with longer prediction horizons.

18. OTHER APPROACHES We compare our approach with a peak load configuration and two reactive strategies: ○ one based on policy rules; ○ an algorithm developed for IBM SPL, not intended for latency # Reconf. QoS Violations # Replicas Rule-based 47.42 76 6.89 SPL-strategy 40.18 230 4.63 Lat-Node 11 30 9.97 Peak-load - 15 12 Our approach has fewer reconfiguration with fewer violations (SPL strategy is throughput oriented)

19. CONCLUSIONS In this work we have studied and implemented strategies for elastic DaSP operators: ○ predictive approach by using MPC methods; ○ take into account power consumption, while providing latency guarantees; ○ our strategies exhibit good stability, accuracy and lower resources consumption; Future works: ○ extend the work on distributed memory architectures; ○ integrate the strategies in a complete graph context (not only an operator)

20. ADDITIONAL REFERENCE AND ATTRIBUTIONS References: ○ Artifact of the paper available at: https://github. com/tizianodem/elastic-hft ○ Application was developed in Fastflow, a C++ parallel programming framework for multicores: http://calvados.di.unipi. it/ ○ For energy statistics and CPU frequency scaling we used the Mammut library available at: https://github. com/DanieleDeSensi/Mammut Attribution ○ Icons used in slide 2 and 4 were designed by Freepik from www.

21. Thank you! Questions?

Add a comment

Related pages

Keep calm and react with foresight

Keep calm and react with foresight: strategies for low-latency and energy-efficient elastic data stream processing
Read more

Uri Verner - Citations

Keep Calm and React with Foresight: Strategies for Low-latency and Energy-efficient Elastic Data ... Scheduling processing of real-time data streams on ...
Read more

21. PPOPP 2016: Barcelona, Spain

comments, criticisms, and testimonials for the evaluation of our efforts by our public funders. If you want to share any thoughts that we may use in our ...
Read more

List of accepted papers - PPoPP 2016 - ...

List of accepted papers. ... Keep Calm and React with Foresight: Strategies for Low-Latency and Energy-Efficient Elastic Stream Processing Tiziano De ...
Read more

PPoPP 2016 - conference management system

PPoPP 2016 is the 21st ACM SIGPLAN Symposium ... Keep calm and react with foresight: strategies for low-latency and energy-efficient elastic data stream ...
Read more

Gabriele Mencagli - Publications

... Keep Calm and React with Foresight: Strategies for Low-latency and Energy-efficient Elastic Data ... strategies for elastic data stream processing.
Read more

Parallel type-checking with haskell using saturating LVars ...

Parallel type-checking with haskell using saturating LVars and stream generators. Authors: Ryan R. Newton: Indiana University: Ömer S. Ağacan: Indiana ...
Read more

Azure Automation: Authenticating to Azure using Azure ...

... low latency data access to build fast and ... Stream Analytics Real-time data stream processing from millions of ... Keep Calm and Automate On (using ...
Read more

BrainMass - 24/7 Academic Help

BrainMass is an online community of academic subject Experts that provide tutoring, ... Strategy and Business Analysis. ... Data Collection.
Read more