Source-linked AI summary
R-Storm: Resource-Aware Scheduling in Storm
Boyang Peng, Mohammad Hosseini, Zhihao Hong, Reza Farivar, Roy Campbell
TL;DR
Storm’s default round-robin scheduler disregards resource demands and availability, motivating a more intelligent scheduling mechanism. R-Storm performs resource-aware task placement that supports hard and soft constraints while reducing network distance. Across micro-benchmarks and Yahoo! production topologies, it reports higher throughput and CPU utilization than default Storm.
Problem
Storm’s default round-robin scheduling ignores resource demands and cluster availability, limiting scheduling efficiency.
Method
R-Storm implements resource-aware Storm scheduling that satisfies hard and soft constraints and minimizes network distance between communicating components.
Results
30-47% higher throughput and 69-350% better CPU utilization occur for micro-benchmarks, while Yahoo! topologies achieve around 50% higher overall throughput than default Storm.
Takeaways & Limitations
R-Storm performs much better than default Storm for micro-benchmarks, Yahoo! production topologies, and scheduling multiple topologies.
Takeaways & Limitations
The evaluation assumes a homogeneous Storm cluster and models CPU resources with a rough point system because CPU usage is difficult to define.
Abstract
from arXiv · showhide
The era of big data has led to the emergence of new systems for real-time distributed stream processing, e.g., Apache Storm is one of the most popular stream processing systems in industry today. However, Storm, like many other stream processing systems lacks an intelligent scheduling mechanism. The default round-robin scheduling currently deployed in Storm disregards resource demands and availability, and can therefore be inefficient at times. We present R-Storm (Resource-Aware Storm), a system that implements resource-aware scheduling within Storm. R-Storm is designed to increase overall throughput by maximizing resource utilization while minimizing network latency. When scheduling tasks, R-Storm can satisfy both soft and hard resource constraints as well as minimizing network distance between components that communicate with each other. We evaluate R-Storm on set of micro-benchmark Storm applications as well as Storm applications used in production at Yahoo! Inc. From our experimental results we conclude that R-Storm achieves 30-47% higher throughput and 69-350% better CPU utilization than default Storm for the micro-benchmarks. For the Yahoo! Storm applications, R-Storm outperforms default Storm by around 50% based on overall throughput. We also demonstrate that R-Storm performs much better when scheduling multiple Storm applications than default Storm.
1. INTRODUCTION
Storm provides real-time distributed stream processing, but its default round-robin scheduler ignores resource demands and availability. R-Storm introduces resource-aware scheduling to improve throughput and utilization while accounting for communicating components.
- Storm processes unbounded data streams in an easy-to-program real-time computation framework.
- Default Storm places tasks using pseudo-random round robin without considering cluster resource availability or topology resource requirements.
- Ignoring resource demands can over-utilize or underutilize machines, causing failures, execution inefficiency, and unnecessary expenditures.
- R-Storm implements resource-aware scheduling within Storm and supports both hard and soft resource constraints.
- R-Storm also minimizes network distance between components that communicate with each other.
2. BACKGROUND
Storm represents real-time computation as topologies composed of stream-processing components and tasks distributed across worker nodes. Components can be parallelized, while Storm’s default scheduler distributes their tasks round robin across machines.
- A Storm topology is a computation graph describing data flow for unbounded real-time processing.
- Tuples are Storm’s basic data units, and streams are unbounded sequences of tuples.
- Components are processing operators implemented as spouts or bolts.
- Spouts emit source streams, while bolts consume, process, and potentially emit streams for downstream computation.
- Storm uses master and worker nodes: Nimbus schedules tasks, while supervisors run worker processes containing executors and tasks.
- Users specify component parallelization, but default round-robin placement commonly spreads tasks from one component across different physical machines.
3. PROBLEM DEFINITION
R-Storm’s scheduling problem assigns tasks to nodes while satisfying resource budgets and favoring nearby placement for communicating tasks. The formulation combines multiple, multidimensional, and quadratic knapsack characteristics, subject to real-time constraints.
- The scheduler must map every task to a machine without exceeding machine resource availability or violating task requirements.
- R-Storm models CPU, bandwidth, and memory as resource dimensions, with CPU and bandwidth soft constraints and memory a hard constraint.
- Users specify which constraints are soft or hard, reflecting whether overuse causes graceful degradation or catastrophic consequences.
- The formulation is a special knapsack optimization problem that must assign all tasks across multiple nodes under multiple constraints.
- Placing successive communicating tasks on the same node adds a quadratic objective favoring reduced network distance.
- Scheduling must remain simple and low-overhead because exact or complex knapsack algorithms may take too long for real-time operation and recovery.
4. R-STORM SCHEDULING ALGORITHM
R-Storm replaces Storm’s resource-oblivious scheduling with a heuristic that orders communicating tasks and assigns them to nearby nodes while respecting hard constraints. It models tasks and nodes in resource space, selects feasible nodes by distance, and aims to minimize resource waste and network latency.
- Algorithm overview: R-Storm uses simpler heuristic algorithms because optimal resource-aware scheduling can be computationally infeasible.The scheduling problem is related to knapsack problems, including the Quadratic Multiple 3-Dimensional Knapsack Problem.
- Algorithm overview: The algorithm accounts for network hierarchy, where inter-rack communication is slowest and intra-process communication is fastest.Its design uses network distance to reduce communication latency between tasks.
- Resource model: Tasks have CPU and bandwidth soft constraints plus a memory hard constraint, while nodes expose corresponding resource availability.The model represents task demand and node availability as vectors, generalizable to n-dimensional resource spaces; soft constraints may carry user-defined weights.
- Node selection: R-Storm selects a feasible node nearest to the task in resource space using Euclidean distance while avoiding hard-constraint violations.The distance function combines resource differences with network distance from a reference node.
- Algorithm overview: The scheduler prioritizes communicating components, violates no hard resource constraints, and minimizes resource waste on nodes.Task ordering uses breadth-first topology traversal, and node assignment is performed afterward through separate task-selection and node-selection procedures.
- Node selection: For the first task, R-Storm chooses the rack or sub-cluster with the most available resources, then selects its most resource-rich node as the reference node.Subsequent tasks are placed tightly around this reference node as resource constraints allow.
5. IMPLEMENTATION
R-Storm is implemented as a custom Storm version with a resource-aware scheduler, cluster state tracking, and APIs for specifying component demands and machine availability.
- Architecture: R-Storm modifies Storm so physical machines report resource availability to Nimbus, while a custom scheduler implements the scheduling functions.The scheduler runs within the Storm Nimbus daemon through the predefined IScheduler interface.
- Architecture: The implementation contains StatisticServer, GlobalState, and ResourceAwareScheduler modules.These modules collect performance statistics, store task placement and resource state, and execute the core scheduling algorithm.
- User API: Users specify resource demands for topology components, including memory and CPU load for each component instance.The APIs include setMemoryLoad and setCPULoad; the example assigns 1024.0 MB to a spout.
- User API: Administrators specify machine resource availability in storm.yaml, including memory capacity and CPU capacity.The configuration examples use supervisor.memory.capacity.mb and supervisor.cpu.capacity.
- Resource Model: CPU demand and availability use a point system that roughly estimates the percentage of a CPU core consumed by a task.For a typical setting, node CPU availability is represented as 100 times the number of cores.
6. EVALUATION
The evaluation compares R-Storm with Storm’s default scheduler on micro-benchmark, Yahoo production, and multiple-topology workloads. Across these settings, R-Storm improves throughput, CPU utilization, or both by accounting for resource demands and placement.
- Experimental Setup: The evaluation uses Emulab experiments comparing R-Storm and Storm’s default scheduler across micro-benchmark and industry topologies.Throughput is measured as the average throughput of the output bolts, with experiments running for about 15 minutes.
- Network Resource Bound: R-Storm delivers around 50%, 30%, and 47% higher throughput for Linear, Diamond, and Star network-bound topologies, respectively.The improvement is attributed to colocating communicating tasks on the same machine or server rack to reduce network latency.
- Computation Time Bound: R-Storm matches default Storm’s Linear throughput using 6 rather than 12 machines, with 69% higher average CPU utilization.For Diamond, R-Storm matches default Storm using 7 rather than 12 machines and achieves 91% higher CPU utilization; Star achieves 350% better utilization with higher throughput using half the machines.
- Computation Time Bound: A topology’s performance may reach a ceiling when component parallelism is unchanged, so adding machines does not necessarily improve throughput.Using unnecessary machines can also increase communication latency.
- Yahoo Topologies: R-Storm improves overall throughput by 50% for Yahoo’s Page Load topology and 47% for its Processing topology.These production topologies process advertising-platform event data for near-real-time analytical reporting.
- Yahoo Topologies: R-Storm’s average throughput is 25496 tuples/10sec for PageLoad versus 16695 tuples/10sec under default Storm.For Processing, R-Storm reaches 67115 tuples/10sec versus 10 tuples/sec under default Storm.
7. RELATED WORK
Related work addresses resource-aware scheduling in MapReduce, Storm, and System S, but differs from R-Storm in resource coverage, topology scope, scheduling mode, or algorithmic complexity.
- MapReduce Scheduling: Jorda et al.’s MapReduce scheduler accounts for memory and CPU capacities but does not include network constraints.Its placement algorithm is derived from a heuristic for the Class-Constrained Multiple Knapsack Problem, which is NP-hard.
- Storm Scheduling: Aniello et al. propose offline and online Storm schedulers, whereas R-Storm derives scheduling before topology execution.Their offline approach is limited to acyclic topologies, while R-Storm is not subject to that limitation.
- Storm Scheduling: The Aniello et al. online scheduler monitors CPU usage and seeks to rebalance topology placement after profiling it for a period.It considers CPU usage only and reports an average 20-30 percentage improvement in performance.
- System S Scheduling: The System S scheduler admits or rejects jobs, computes candidate processing nodes, and then determines fractional allocations of processing elements.Its approach accounts only for processing power and requires a relatively complex computation.
8. CONCLUSIONS
R-Storm replaces Storm’s resource-blind round-robin scheduling with resource-aware placement that accounts for constraints and communication distance. It improves throughput and CPU utilization across benchmark and Yahoo! workloads, with applicability to other DAG-based stream-processing systems.
- R-Storm satisfies soft and hard resource constraints while minimizing network distance between communicating components.
- 30-47% higher throughput and 69-350% better CPU utilization were achieved than default Storm for micro-benchmark topologies.
- Around 50% higher overall throughput was achieved than default Storm for Yahoo! production topologies.
- R-Storm performed much better than default Storm when scheduling multiple topologies.
- R-Storm’s concepts and algorithms are applicable to other DAG-based distributed stream-processing systems, including Twitter Heron and Apache Flink.