Article Preview
TopIntroduction
The goal of an autonomic load balancing system (Ganek & Corbi, 2003; IBM, 2006; Huebscher & McCann, 2008; Sterritt, 2005) is to distribute load across multiple processors in such a way as to optimize system performance. An autonomic load balancing system will continuously monitor the performance of the system across all processors, and decide if a new policy for distributing work is warranted. For instance, one processor may be highly overloaded, and work will need to be redirected from that processor to other processors. It may require that even some of the existing load on that processor be moved to another processor.
In this paper we focus on a specialized domain of computation called Adaptive Query Processing (AQP), which uses a form of partitioned parallel processing to provide scalable query processing. Since this technique performs at the speed of the slowest participant, it has prompted several proposals for adaptivity specifically aimed at load balance (Gounaris et al., 2005; Raman, Han, & Narang, 2005; Shah et al., 2003). These proposals differ from most work on dynamic load balancing for parallel databases (DeWitt et al., 1992; Rahm & Marek, 1993) in changing load balance within, rather than between, queries. An evaluation and comparison of these approaches can be found in Paton et al. (2006, 2009).
Most AQP approaches for deciding when to adapt use only current machine load levels to make their decision. In this paper we explore a probabilistic approach that uses past performance (machine load levels) over a period of time to predict future performance. This prediction is then used to decide when to adapt. We provide empirical evidence for the effectiveness of our approach by comparing it to other algorithms in the literature. An initial version of this algorithm was presented in Yellin, Buenabad-Chávez, and Paton (2008). This paper expands upon that work providing new theoretical results, new variations on the algorithm, and more focused experiments to validate the efficacy of the approach. The experimental approach used to evaluate our approach is based upon the approach in Paton et al. (2009). We chose to keep the same experimental setting in order to better evaluate our approach directly against previous benchmarks. Part of the contribution of this paper is to show that using some fairly straightforward adaptive techniques to decide when to adapt, performance can be significantly improved.
The rest of this paper is organized as follows. In the next section we present the AQP problem and prior work on this problem. We focus on two existing algorithms, Flux (Shah et al., 2003) and RevisedDelta (Paton et al., 2009). The former is the seminal work in AQP upon which almost all other research is based, while the latter is the work that inspired the prAdapt algorithm in this paper. We also provide a theoretical framework to analyze the effectiveness of different approaches. In Appendix A and Appendix B we show that under the assumption that the immediate future will imitate the recent past, and under some additional assumptions, RevisedDelta (or a slight variant) is the optimal algorithm. However, the assumption that the future will imitate the past is not always valid, and for that reason in the section following the next one we describe the prAdapt algorithm, which attempts to probabilistically predict the future given the past. In the Experimental Methodology section we describe our methodology and in the Results Section we state the results of our experiments comparing prAdapt to Flux and to RevisedDelta. prAdapt has several parameters, and we also provide experimental evidence as to the effect of these parameters on the performance of the algorithm. The last section presents our conclusion, additional related work, and directions for future research.