Low-cost, accurate and scalable software configuration discovery is the key to simplifying many cloud management tasks. However, the lack of standardization across software configuration techniques has prevented the development of a fully automated and application independent configuration discovery solution. In this work, we present Columbus, an application-agnostic system to automatically discover environmental configuration parameters or Points of Variability (PoV) in clustered applications with high accuracy. Columbus uses the insight that even though configuration mechanisms and files vary across different software, the PoVs are encoded using a few common patterns. It uses a novel rule framework to annotate file content with PoVs and a Bayesian network to estimate confidence for annotated PoVs. Our experiments confirm that Columbus can accurately discover configuration for a diverse set of enterprise and cloud applications. It has subsequently been integrated in three real-world systems that analyze this information for discovery of distributed application dependencies, enterprise IT migration and virtual application configuration.

In this work, we argue that energy management should be a guiding principle for design and implementation of algorithms. Traditional complexity models for algorithms are simple and do not aid in design of energy-efficient algorithms. In this work, we conducted a large number of experiments to understand energy consumption for algorithms. We study the energy consumption for popular vector operations, matrix operations, sorting, and graph algorithms. We observed that the energy consumption for any given algorithm depends on the memory parallelism the algorithm can exhibit for a given data layout in the RAM with variations up to 100% for many popular algorithms. Our experiments validate the asymptotic energy complexity model presented in a companion paper [1] and brings out many practical insights. We show that reads can be more expensive in terms of energy than writes, and different data types can lead to different energy consumption. Our most important result is a theoretical and experimental quantification of the impact of parallel data sequences on energy consumption. We also observe that high memory parallelism can also increase energy consumption with multiple concurrent access sequences. We use insights from our experiments to propose algorithmic engineering techniques for practical energy efficient software.

In this work, we present Lean Virtual Disks (LVD), a new virtual disk format for virtualized servers. LVD transparently consolidates duplicate blocks across virtual machines to create a lean disk image, leading to a merged datapath for all virtual machines. This merged datapath allows efficient storage usage, reduction in disk I/O (read/write) by eliminating I/O for same content across VMs and efficient host cache utilization. LVD is motivated by clouds, where VMs are created from golden masters and use standardized middleware and management tools leading to high content similarity. We implement LVD as an extension of QCow2 and study its ability to improve common data center system management activities as well as improving application performance of popular I/O benchmark workloads. We observed that LVD reduced disk space and disk I/O by 70%, making applications run faster by 25% on an average.

Application performance has been and remains one of top five concerns since the inception of cloud computing. A primary determinant of application performance is multi-tenancy or sharing of hardware resources in clouds. While some hardware resources can be partitioned well among VMs (such as CPUs), many others cannot (such as memory bandwidth). In this paper, we focus on understanding the variability in application performance on a cloud and explore ways for an end customer to deal with it. Based on rigorous experiments using CloudSuite, a popular Web2.0 benchmark, running on EC2, we found that interference-induced performance degradation is a reality. On a private cloud testbed, we also observed that interference impacts the choice of best configuration values for applications and middleware. We posit that intelligent reconfiguration of application parameters presents a way for an end customer to reduce the impact of interference. However, tuning the application to deal with interference is challenging because of two fundamental reasons --- the configuration depends on the nature and degree of interference and there are inter-parameter dependencies. We design and implement the IC2 system (Interference-aware Cloud application Configuration) to address the challenges of detection and mitigation of performance interference in clouds. Compared to an interference-agnostic configuration, the proposed solution provides up to 29% and 40% improvement in average response time on EC2 and a private cloud testbed respectively.

Dynamic Virtual Machine (VM) consolidation dynamically adapts VM resource allocation to resource demands promising significant cost benefits for highly variable enterprise workloads. In this work, we analyze large enterprise workloads with the goal of understanding how effective are the VM consolidation variants in real world. We observe that burstiness in memory demand is much lower than the burstiness in CPU demand. Further, memory is the more constrained resource in virtualized servers, significantly reducing the potential gains due to dynamic consolidation. We study consolidation planning in four very large data centers and observe that the savings in facilities cost due to dynamic consolidation over static consolidation is not as large as estimated by past studies. Further, the savings over intelligent semi-static consolidation are surprisingly modest in most cases, putting a question mark over the applicability of dynamic consolidation in real world.

Storage clouds use economies of scale to host data for diverse enterprises. However, enterprises differ in the requirements for their data. In this work, we investigate the problem of resiliency or disaster recovery (DR) planning in a storage cloud. The resiliency requirements vary greatly between different enterprises and also between different datasets for the same enterprise. We present in this paper Resilient Storage Cloud Map (RSCMap), a generic cost-minimizing optimization framework for disaster recovery planning, where the cost function may be tailored to meet diverse objectives. We present fast algorithms that come up with a minimum cost DR plan, while meeting all the DR requirements associated with all the datasets hosted on the storage cloud. Our algorithms have strong theoretical properties: 2 factor approximation for bandwidth minimization and fixed parameter constant approximation for the general cost minimization problem. We perform a comprehensive experimental evaluation of RSCMap using models for a wide variety of replication solutions and show that RSCMap outperforms existing resiliency planning approaches.

In this work, we address problem determination in virtualized clouds. We show that high dynamism, resource sharing, frequent reconfiguration, high propensity to faults and automated management introduce significant new challenges towards fault diagnosis in clouds. Towards this, we propose CloudPD, a fault management framework for clouds. CloudPD leverages (i) a canonical representation of the operating environment to quantify the impact of sharing; (ii) an online learning process to tackle dynamism; (iii) a correlation-based performance models for higher detection accuracy; and (iv) an integrated end-to-end feedback loop to synergize with a cloud management ecosystem. Using a prototype implementation with cloud representative batch and transactional workloads like Hadoop, Olio and RUBiS, it is shown that CloudPD detects and diagnoses faults with low false positives (<; 16%) and high accuracy of 88%, 83% and 83%, respectively. In an enterprise trace-based case study, CloudPD diagnosed anomalies within 30 seconds and with an accuracy of 77%, demonstrating its effectiveness in real-life operations.

Virtualization has significantly reduced the cost of creating a new virtual machine and cheap storage allows VMs to be turned down when unused. This has led to a rapid proliferation of virtual machine images, both active and dormant, in the data center. System management technologies have not been able to keep pace with this growth and the management cost of keeping all virtual machines images, active as well as dormant, updated is significant. In this work, we present ImageElves, a system to rapidly, reliably and automatically propagate updates (e.g., patches, software installs, compliance checks) in a data center. ImageElves analyses all target images and creates reliable image patches using a very small number of online updates. Traditionally, updates are applied by taking the application offline, applying updates, and then restoring the application, a process that is unreliable and has an unpredictable downtime. With ImageElves, we propose a two phase process. In the first phase, images are analyzed to create an update signature and update manifest. In the second phase, downtime is taken and the manifest is applied offline on virtual images in a parallel, reliable and automated manner. This has two main advantages, (i) spontaneously apply updates to already dormant VMs, and (ii) all updates following this process are guaranteed to work reliably leading to reduced and predictable downtimes. ImageElves uses three key ideas: (i) a novel per-update profiling mechanism to divide VMs into equivalence classes, (ii) a background logging mechanism to convert updates on live instances into patches for dormant images, and (iii) a cross-difference mechanism to filter system-specific or random information (e.g., host name, IP address), while creating equivalence classes. We evaluated the ability of ImageElves to speed up mix of popular system management activities and observed upto 80% smaller update times for active instances and upto 90% reduction in update time for dormant instances.

Energy consumption has emerged as a first class computing resource for both server systems and personal computing devices. The growing importance of energy has led to rethink in hardware design, hypervisors, operating systems and compilers. Algorithm design is still relatively untouched by the importance of energy and algorithmic complexity models do not capture the energy consumed by an algorithm. In this paper, we propose a new complexity model to account for the energy used by an algorithm. Based on an abstract memory model (which was inspired by the popular DDR3 memory model and is similar to the parallel disk I/O model of Vitter and Shriver), we present a simple energy model that is a (weighted) sum of the time complexity of the algorithm and the number of 'parallel' I/O accesses made by the algorithm. We derive this simple model from a more complicated model that better models the ground truth and present some experimental justification for our model. We believe that the simplicity (and applicability) of this energy model is the main contribution of the paper. We present some sufficient conditions on algorithm behavior that allows us to bound the energy complexity of the algorithm in terms of its time complexity (in the RAM model) and its I/O complexity (in the I/O model). As corollaries, we obtain energy optimal algorithms for sorting (and its special cases like permutation), matrix transpose and (sparse) matrix vector multiplication.

Enterprise clouds today support an on demand resource allocation model and can provide resources requested by applications in a near online manner using virtual machine resizing or cloning. However, in order to take advantage of an on demand resource model, enterprise applications need to be automatically scaled in a way that makes the most efficient use of resources. In this work, we present the SmartScale automated scaling framework. SmartScale uses a combination of vertical (adding more resources to existing VM instances) and horizontal (adding more VM instances) scaling to ensure that the application is scaled in a manner that optimizes both resource usage and the reconfiguration cost incurred due to scaling. The SmartScale methodology is proactive and ensures that the application converges quickly to the desired scaling level even when the workload intensity changes significantly. We evaluate SmartScale using real production traces on Olio, an emerging cloud benchmark, running on a kvm-based cloud testbed. We present both theoretical and experimental evidence that comprehensively establish the effectiveness of SmartScale.

Cloud computing has emerged as an exciting hosting paradigm to drive up server utilization and reduce data center operational costs. Even though clouds present a single unified homogeneous resource pool view to end users, the underlying server landscape may differ in terms of functionality and reconfiguration capabilities (e.g., support for shared processors, live migration). In a private cloud setting where information on the resources as well as workloads are available, the placement of applications on clouds can leverage it to achieve better consolidation with performance guarantees. In this work, we present the design and implementation of CloudMap, a provisioning system for private clouds. Given an application's resource usage patterns, we match it with a server cluster with the appropriate level of reconfiguration capability. In this cluster, we place the application on a server that has existing workloads with complementary resource usage profile. CloudMap is implemented using a hybrid architecture with a global server cluster selection module and local cluster-specific server selection modules. Using production traces from live data centers, we demonstrate the effectiveness of CloudMap over existing placement methodologies.

In this work, we address the problem of selecting the best set of available services or web functionalities (single or composite) to provide a composite service at the minimum cost, while meeting QoS requirements. Our Recursive composition model captures the fact that the available service providers may include providers of single as well as composite services; an important feature that was not captured in earlier models. We show that Recursive Composition is an intrinsically harder problem to solve than other studied compositional models. We use the structure of the Recursive Composition model to design an efficient algorithm BGF-D with provable guarantees on cost. As an embodiment, we design and implement the ReComp architecture for Recursive Composition of web-services that implements the BGF-D algorithm. We present comprehensive theoretical and experimental evidence to establish the scalability and superiority of the proposed algorithm over existing approaches.

Miss rate curves (MRCs) are a fundamental concept in determining the impact of caches on an application's performance. In our research, we use MRCs to provision caches for applications in a consolidated environment. Current techniques for building MRCs at the CPU caches level require changes to the applications and are restricted to a few processor architectures [7], [22]. In this work, we investigate two techniques to partition shared L2 and L3 caches in a server and build MRCs for the VMs. These techniques make different trade-offs across accuracy, flexibility, and intrusiveness dimensions. The first technique is based on operating system (OS) page coloring and does not require change in commodity hardware or application. We improve upon existing page-coloring based approaches by identifying and overcoming a subtle but real problem of unequal associative cache sets loading to implement accurate cache allocation. Our second technique called Cache Grabber is even less intrusive and requires no changes in hardware, OS, or application. We present a comprehensive evaluation of the relative merits of these and other techniques to estimate MRCs. Our evaluation study enables a data center administrator to select the technique most suitable to his (her) specific data center to provision caches for consolidated applications.

Clouds allow enterprises to increase or decrease their resource allocation on demand in response to changes in workload intensity. Virtualization is one of the building blocks for cloud computing and provides the mechanisms to implement the dynamic allocation of resources. These dynamic reconfiguration actions lead to performance impact during the reconfiguration duration. In this paper, we model the cost of reconfiguring a cloud-based IT infrastructure in response to workload variations. We show that maintaining a cloud requires frequent reconfigurations necessitating both VM resizing and VM live migration, with live migration dominating reconfiguration costs. We design the CosMig model to predict the duration of live migration and its impact on application performance. Our model is based on parameters that are typically monitored in enterprise data centers. Further, the model faithfully captures the impact of shared resources in a virtualized environment. We experimentally validate the accuracy and effectiveness of CosMig using micro benchmarks and representative applications.

Shared data centers and clouds are gaining popularity because of their ability to reduce costs by increasing the utilization of server farms. In a shared server environment, a careful assignment of workload streams (all work-requests from a customer may constitute a stream) to servers is necessary to ensure good “end user” performance. In this work, we investigate the assignment of streams to servers in order to minimize an objective function, while ensuring that load is balanced across all the servers. The objective functions we optimize in this work include the overall expected waiting-time, overall probability of the wait exceeding a given value, and weighted versions of these measures. We obtain the optimal algorithm for a farm with 2 servers, if sharing of streams among servers is allowed. Based on the insights obtained, we design an efficient algorithm for the multiserver case. By rounding off this solution, we obtain a solution to the case where sharing of streams is not allowed. Our trace-driven evaluation study shows that our algorithms significantly outperform baseline methods. Our work enables high performance for web hosting services as well as emerging Application as a Service (AaaS) clouds. We also show that solutions in areas such as task-level scheduling and file assignment fall within our framework.

We present the design and implementation of ENDEAVOUR - a framework for integrated end-to-end disaster recovery (DR) planning. Unlike existing research that provides DR planning within a single layer of the IT stack (e.g. storage controller based replication), ENDEAVOUR can choose technologies and composition of technologies across multiple layers like virtual machines, databases and storage controllers. ENDEAVOUR uses a canonical model of available replication technologies at all layers, explores strategies to compose them, and performs a novel map-search-reduce heuristic to identify the best DR plans for given administrator requirements. We present a detailed analysis of ENDEAVOUR including empirical characterization of various DR technologies, their composition, and a end-to-end case study.

High Performance Computing applications and platforms have been typically designed without regard to power consumption. With increased awareness of energy cost, power management is now an issue even for compute-intensive server clusters. In this work, we investigate the use of power management techniques for high performance applications on modern power-efficient servers with virtualization support. We consider power management techniques such as dynamic consolidation and usage of dynamic power range enabled by low power states on servers. We identify application performance isolation and virtualization overhead with multiple virtual machines as the key bottlenecks for server consolidation. We perform a comprehensive experimental study to identify the scenarios where applications are isolated from each other. We also establish that the power consumed by HPC applications may be application dependent, non-linear and have a large dynamic range. We show that for HPC applications, working set size is a key parameter to take care of while placing applications on virtualized servers. We use the insights obtained from our experimental study to present a framework and methodology for power-aware application placement for HPC applications.

We investigate methodologies for placement and migration of logical data stores in virtualized storage systems leading to optimum system configuration in a dynamic workload scenario. The aim is to optimize the tradeoff between the performance or operational cost improvement resulting from changes in store placement, and the cost imposed by the involved data migration step. We propose a unified economic utility based framework in which the tradeoff can be formulated as a utility maximization problem where the utility of a configuration is defined as the difference between the benefit of a configuration and the cost of moving to the configuration. We present a storage management middleware framework and architecture Compass that allows systems designers to plug-in different placement as well as migration techniques for estimation of utilities associated with different configurations. The biggest obstacle in optimizing the placement benefit and migration cost tradeoff is the exponential number of possible configurations that one may have to evaluate. We present algorithms that explore the configuration space efficiently and compute a candidate set of configurations that optimize this cost-benefit tradeoff. Our algorithms have many desirable properties including local optimality. Comprehensive experimental studies demonstrate the efficacy of the proposed framework and exploration algorithms, as our algorithms outperform migration cost-oblivious placement strategies by up to 40% on real OLTP traces for many settings.

We present a new disk scheduling framework to address the needs of a shared multimedia service that provides differentiated multilevel quality-of-service for mixed-media workloads. In such a shared service, requests from different users have different associated performance objectives and utilities, in accordance with the negotiated service-level agreements (SLAs). Service providers typically provision resources only for average workload intensity, so it becomes important to handle workload surges in a way that maximizes the utility of the served requests. We capture the performance objectives and utilities associated with these multiclass diverse workloads in a unified framework and formulate the disk scheduling problem as a reward maximization problem. We map the reward maximization problem to a minimization problem on graphs and, by novel use of graph-theoretic techniques, design a scheduling algorithm that is computationally efficient and optimal in the class of seek-optimizing algorithms. Comprehensive experimental studies demonstrate that the proposed algorithm outperforms other disk schedulers under all loads, with the performance improvement approaching 100% under certain high load conditions. In contrast to existing schedulers, the proposed scheduler is extensible to new performance objectives (workload type) and utilities by simply altering the reward functions associated with the requests.

We investigate methodologies for placement and migration of logical data stores in virtualized storage systems leading to optimum system configuration in a dynamic workload scenario. The aim is to optimize the tradeoff between the performance or operational cost improvement resulting from changes in store placement, and the cost imposed by the involved data migration step. We propose a unified economic utility based framework in which the tradeoff can be formulated as a utility maximization problem where the utility of a configuration is defined as the difference between the benefit of a configuration and the cost of moving to the configuration. We present a storage management middleware framework and architecture Compass that allows systems designers to plug-in different placement as well as migration techniques for estimation of utilities associated with different configurations. The biggest obstacle in optimizing the placement benefit and migration cost tradeoff is the exponential number of possible configurations that one may have to evaluate. We present algorithms that explore the configuration space efficiently and compute a candidate set of configurations that optimize this cost-benefit tradeoff. Our algorithms have many desirable properties including local optimality. Comprehensive experimental studies demonstrate the efficacy of the proposed framework and exploration algorithms, as our algorithms outperform migration cost-oblivious placement strategies by up to 40% on real OLTP traces for many settings.

We investigate the placement of N enterprise data-stores (e.g., database tables, application data) across an array of disks with the aim of minimizing the response time averaged over all served requests, while balancing the load evenly across all the disks in the parallel disk array. Incorporating the non-FCFS serving discipline and non work-conserving nature of disk drives in formulation of the placement problem is difficult and current placement strategies do not take them into account. We present a novel formulation of the placement problem to incorporate these crucial features and identify the runlength of requests accessing a store as the most important criterion for placing the stores. We use these insights to design a fast (running time of N logN) placement algorithm that is optimal under the assumption that transfer times are small. Comprehensive experimental studies establish the efficacy of the proposed algorithm under a wide variety of workloads with the proposed algorithm reducing the response time for real storage traces by more than a factor of 2 under heterogeneous workload scenarios.

Logical reorganization of data and requirements of differentiated QoS in information systems necessitate bulk data migration by the underlying storage layer. Such data migration needs to ensure that regular client I/Os are not impacted significantly while migration is in progress. We formalize the data migration problem in a unified admission control framework that captures both the performance requirements of client I/Os and the constraints associated with migration. We propose an adaptive rate-control based data migration methodology, QoSMig, that achieves the optimal client performance in a differentiated QoS setting, while ensuring that the specified migration constraints are met QoSMig uses both long term averages and short term forecasts of client traffic to compute a migration schedule. We present an architecture based on Service Level Enforcement Discipline for Storage (SLEDS) that supports QoSMig. Our trace-driven experimental study demonstrates that QoSMig provides significantly better I/O performance as compared to existing migration methodologies.

We present a policy-based architecture STEPS for lifecycle management (LCM) in a mass scale distributed file system. The STEPS architecture is designed in the context of IBM's SAN file system (SFS) and leverages the parallelism and scalability offered by SFS, while providing a centralized point of control for policy-based management. The architecture uses novel concepts like policy cache and rate-controlled migration for efficient and non-intrusive execution of the LCM functions, while ensuring that the architecture scales with very large number of files. The architecture has been implemented and used for lifecycle management in a distributed deployment of SFS with heterogeneous data. We conduct experiments on the implementation to study the performance of the architecture. We observed that STEPS is highly scalable with increase in the number as well as the size of the file objects hosted by SFS. The performance study also demonstrated that most of the efficiency of policy execution is derived from policy cache. Further, a rate-control mechanism is necessary to ensure that users are isolated from LCM operations.

No abstract available.

Variability and diverseness among incoming requests to a service hosted on a finite capacity resource necessitates sophisticated request admission control techniques for providing guaranteed quality of service (QoS). We propose in this paper a service time based online admission control methodology for maximizing profits of a service provider. The proposed methodology chooses a subset of incoming requests such that the revenue of the provider is maximized. Admission control decision in our proposed system is based upon an estimate of the service time of the request, QoS bounds, prediction of arrivals and service times of requests to come in the short-term future, and rewards associated with servicing a request within its QoS bounds. Effectiveness of the proposed admission control methodology is demonstrated using experiments with a content-based messaging middleware service.