Recurring batch data pipelines are a staple of the modern enterprise-scale data warehouse. As a data warehouse scales to support more products and services, a growing number of interdependent pipelines running at various cadences can give rise to periodic resource bottlenecks for the cluster. This resource contention results in pipelines starting at unpredictable times each day and consequently variable landing times for the data artifacts they produce. The variability gets compounded by the dependency structure of the workload, and the resulting unpredictability can disrupt the project workstreams which consume this data. We present Clockwork, a delay-based global scheduling framework for data pipelines which improves landing time stability by spreading out tasks throughout the day. Whereas most scheduling algorithms optimize for makespan or average job completion times, Clockwork's execution plan optimizes for stability in task completion times while also targeting predefined pipeline SLOs. We present this new problem formulation and design a list scheduling algorithm based on its analytic properties. We also discuss how we estimate the resource requirements for our recurring pipelines, and the architecture for integrating Clockwork with Dataswarm, Facebook's existing data workflow management service. Online experiments comparing this novel scheduling algorithm and a previously proposed greedy procrastinating heuristic show tasks complete almost an hour earlier on average, while exhibiting lower landing time variance and producing significantly less competition for resources in the cluster.

Multiple teams at Facebook are tasked with monitoring compute and memory utilization metrics that are important for managing the efficiency of the codebase. An efficiency regression is characterized by instances where the CPU utilization or query per second (QPS) patterns of a function or endpoint experience an unexpected increase over its prior baseline. If the code changes responsible for these regressions get propagated to Facebook's fleet of web servers, the impact of the inefficient code will get compounded over billions of executions per day, carrying potential ramifications to Facebook's scaling efforts and the quality of the user experience. With a codebase ingesting in excess of 1,000 diffs across multiple pushes per day, it is important to have a real-time solution for detecting regressions that is not only scalable and high in recall, but also highly precise in order to avoid overrunning the remediation queue with thousands of false positives. This paper describes the end-to-end regression detection system designed and used at Facebook. The main detection algorithm is based on sequential statistics supplemented by signal processing transformations, and the performance of the algorithm was assessed with a mixture of online and offline tests across different use cases. We compare the performance of our algorithm against a simple benchmark as well as a commercial anomaly detection software solution.

Consider a wireless networking architecture, where multiple infrastructure access points (AP) dynamically offer (bid) service deals (modes) to a mobile over time. Akin to a market offer, each service deal is comprised of service/quality attributes (e.g, AP, rate) for a price (cost). The mobile dynamically selects the desirable deal at each time, so as to efficiently trade long term latency/quality for cumulative price. Offered service modes depend on the randomly fluctuating congestion state of the AP infrastructure. Dynamically switching from one service mode/deal to another, the mobile encounters `friction' (e.g. bandwidth loss, disconnection risk) and, hence, has an incentive to stick with the current deal for as long as this is significantly competitive. A model of this architecture is first developed, which allows for the formulation and computation of the optimal control for the mobile to accept an offered deal amongst many and switch into the corresponding service mode. A suite of low-complexity heuristic controls for mode switching is also discussed. The performance of the optimal and heuristic controls is probed via simulation. Finally, the `switching curve' structure of the optimal control is demonstrated on a simple system where the curves can be plotted.

Cloud infrastructures with virtualized CPU and memory resources have the potential for providing high quality of service at increased levels of energy efficiency. By dynamically tailoring the capacity of a virtual machine to workload demands, a cloud infrastructure can significantly reduce the number of physical resources it has online, saving on decreased power costs. These resource management techniques, however, have yet to gain widespread appeal among network engineers due to the significant delays and setup costs in activating or reconfiguring cloud resources. A further challenge is these "frictions" fluctuate through time, based on complex system-wide supply and demand "weather" patterns in the cloud as a whole. In this paper, we develop a loss queueing model for capacity provisioning for a virtual machine that draws its computation resources from the cloud under varying friction cost. We solve for the optimal control policy using dynamic programming and discuss its intuitive structural properties. Finally we run simulations to compare the performance of the optimal policy against two benchmarks and a heuristic policy.

Reducing energy consumption in data centers has been a persistent goal for the last decade. Advances in virtualization and dynamic power management have helped to curb excess utilization by sharing resources and running system components in lower energy states during periods of low traffic. However, switching components among virtual machines and energy states is subject to setup times and increased energy consumption to bring them online, and this combined with the innate burstiness of traffic in data centers are significant deterrents to the successful deployment of power management techniques. In this paper, we develop a queueing model with a controllable service rate that accounts for switching frictions within a setting that has a changing arrival rate. We solve for the optimal control policy using dynamic programming, and find it has intuitive structural properties. We compare its performance against benchmark heuristics, and the relative advantages among them in different scenarios are discussed.

Real-time internet traffic classification has potential applications in next-generation internet security and bandwidth management. Current machine learning-based algorithms for traffic classification, however, present scalability issues that would degrade system performance if executed to make control decisions on real-time streams. This tension gives rise to competing performance costs for traffic classification systems: higher throughput can be achieved at the expense of less stringent computation, and thus lower accuracy. In this paper, we develop a queueing model to explicitly weigh the tradeoff between accuracy and congestion costs in binary classification tasks of discretionary duration. We show the optimal control policy can be approximated well using standard dynamic programming techniques, and compare its performance against two benchmark policies. We also propose a simple heuristic based on constructing conic hulls, and show its performance is very close to optimal.

As smartphones, tablets, and other portable technologies become increasingly prevalent, scaling computational applications to run on these resource-constrained devices will continue to rise to the forefront of challenges in the wireless networking community. In particular, computing tasks which typically address a trade-off between robustness and efficiency, including emerging methods for intruder detection, cryptography, and context-aware applications, need to balance these two objectives against power to adequately transfer onto small systems with a limited power supply. In this paper, we present a queueing model that explicitly balances the competing objectives of minimizing latency, maximizing output quality, while regulating power consumption. We demonstrate the efficacy of this model against a sensible alternative heuristic, thus providing a general and integrated framework for evaluating the performance of quality-driven applications on resource-constrained devices.

Power management has become a critical issue for communication and computing infrastructures. In this paper, we develop systematic and heuristic algorithms for managing communication switches with multiple speed (throughput) modes. Switch speed is increased by activating additional network processor cores, voltage/frequency scaling of the electronics, etc. Higher speed modes burn more power. The developed power (speed) control algorithms are responsive to switch queue backlogs and aim to efficiently trade backlog vs. power costs, so as to minimize the long-run overall backlog and power cost. We first systematically model the system in a Dynamic Programming (DP) framework, where the optimal control can be computed in principle. Unfortunately, the complexity is so high that even for a 2 × 2 switch the computation time is practically infeasible. We therefore develop an Approximate Dynamic Programming (ADP) algorithm based on the Q-learning framework, which has good computation and performance properties. We also develop two low-complexity heuristic power controls, one based on a “myopic” view of the control problem, and the other on “congestion-awareness” of the standard maximum weight matching scheme. We study the performance of the Q-learning and heuristic controls against the optimal one (which we can practically compute only for the 2×2 switch case), and comment on their efficiency. We also extend the method and results to the general case of multiprocessor computing resources.