This article describes the algorithm, implementation, and deployment experience of CacheSack, the admission algorithm for Google datacenter flash caches. CacheSack minimizes the dominant costs of Google’s datacenter flash caches: disk IO and flash footprint. CacheSack partitions cache traffic into disjoint categories, analyzes the observed cache benefit of each subset, and formulates a knapsack problem to assign the optimal admission policy to each subset. Prior to this work, Google datacenter flash cache admission policies were optimized manually, with most caches using the Lazy Adaptive Replacement Cache algorithm. Production experiments showed that CacheSack significantly outperforms the prior static admission policies for a 7.7% improvement of the total cost of ownership, as well as significant improvements in disk reads (9.5% reduction) and flash wearout (17.8% reduction).

Enterprise applications in virtualized environments are often subject to time-varying workloads with multiple seasonal patterns and trends. In order to ensure quality of service for such applications while avoiding over-provisioning, resources need to be dynamically adapted to accommodate the current workload demands. Many memory-intensive applications are not suitable for the traditional horizontal scaling approach often used for runtime performance management, as it relies on complex and expensive state replication. On the other hand, vertical scaling of memory often requires a restart of the application. In this paper, we propose a proactive approach to memory scaling for virtualized applications. It uses statistical forecasting to predict the future workload and reconfigure the memory size of the virtual machine of an application automatically. To this end, we propose an extended forecasting technique that leverages meta-knowledge, such as calendar information, to improve the forecast accuracy. In addition, we develop an application controller to adjust settings associated with application memory management during memory reconfiguration. Our evaluation using real-world traces shows that the forecast accuracy quantified with the MASE error metric can be improved by 11 - 59%. Furthermore, we demonstrate that the proactive approach can reduce the impact of reconfiguration on application availability by over 80% and significantly improve performance relative to a reactive controller.

Supporting QoS control mechanisms in shared storage arrays is constrained by the well-justified fear of impacting the system efficiency. This motivates our study of the trade off between fairness and efficiency in shared storage systems. We propose two adaptations that can be applied to existing IO scheduling mechanisms: the concurrency bound and the batch size. Although these knobs are well known, their impact on system performance and automatic adaptation based on current workload characteristics have not been studied before. Using synthetic benchmarks and trace workloads, we show that the adaptive proportional share algorithm achieves over 90% IO efficiency while maintaining the specified QoS requirements.

Virtualized datacenters strive to reduce costs through workload consolidation. Workloads exhibit a diverse set of IO behaviors and varying IO load that makes it difficult to estimate the IO performance on shared storage. As a result, system administrators often resort to gross overprovisioning or static partitioning of storage to meet application demands. In this paper, we introduce Pesto, a unified storage performance management system for heterogeneous virtualized datacenters. Pesto is the first system that completely automates storage performance management for virtualized datacenters, providing IO load balancing with cost-benefit analysis, per-device congestion management, and initial placement of new workloads.

Cloud computing demands cheap, always-on, and reliable storage. We describe Pahoehoe, a key-value cloud storage system we designed to store large objects cost-effectively with high availability. Pahoehoe stores objects across multiple data centers and provides eventual consistency so to be available during network partitions. Pahoehoe uses erasure codes to store objects with high reliability at low cost. Its use of erasure codes distinguishes Pahoehoe from other cloud storage systems, and presents a challenge for efficiently providing eventual consistency. We describe Pahoehoe's put, get, and convergence protocols-convergence being the decentralized protocol that ensures eventual consistency. We use simulated executions of Pahoehoe to evaluate the efficiency of convergence, in terms of message count and message bytes sent, for failure-free and expected failure scenarios (e.g., partitions and server unavailability). We describe and evaluate optimizations to the naïve convergence protocol that reduce the cost of convergence in all scenarios.

Virtualized data centers enable sharing of resources among hosted applications. However, it is difficult to satisfy service-level objectives(SLOs) of applications on shared infrastructure, as application workloads and resource consumption patterns change over time. In this paper, we present AutoControl, a resource control system that automatically adapts to dynamic workload changes to achieve application SLOs. AutoControl is a combination of an online model estimator and a novel multi-input, multi-output (MIMO) resource controller. The model estimator captures the complex relationship between application performance and resource allocations, while the MIMO controller allocates the right amount of multiple virtualized resources to achieve application SLOs. Our experimental evaluation with RUBiS and TPC-W benchmarks along with production-trace-driven workloads indicates that AutoControl can detect and mitigate CPU and disk I/O bottlenecks that occur over time and across multiple nodes by allocating each resource accordingly. We also show that AutoControl can be used to provide service differentiation according to the application priorities during resource contention.

Wireless mesh network deployments are popular as a cost-effective means to provide broadband connectivity to large user populations. As the network usage grows, network planners need to evolve an existing mesh network to provide additional capacity. In this paper, we study the problem of adding new capacity points (e.g., gateway nodes) to an existing mesh network. We first present a new technique for calculating gateway-limited fair capacity as a function of the contention at each gateway. Then, we present two online gateway placement algorithms that use local search operations to maximize the capacity gain on an existing network. A key challenge is that each gateway's capacity depends on the locations of other gateways and cannot be known in advance of determining a gateway placement. We address this challenge with two placement algorithms with different approaches to estimating the unknown gateway capacities. Our first placement algorithm, MinHopCount, is adapted from a solution to the facility location problem. MinHopCount minimizes path lengths and iteratively estimates the wireless capacity of each gateway location. Our second algorithm, MinContention, is adapted from a solution to the uncapacitated k-median problem and minimizes average contention on mesh nodes, i.e. the number of links in contention range of a mesh node and the number of routes using each link. We show that our gateway placement algorithms outperform a greedy heuristic by up to 64% on realistic topologies. For an example topology, we study the set of all possible gateway placements and find that there is large capacity gain between near-optimal and optimal placements, but the near-optimal placements found by local search are similar in configuration to the optimal.

Enterprise storage systems typically contain multiple storage tiers, each having its own performance, reliability, and recoverability. The primary motivation for this multi-tier organization is cost, as storage tier costs vary considerably. In this paper, we describe a file system called TierFS that stores files at multiple storage tiers while providing high recoverability at all tiers. To achieve this goal, TierFS uses several novel techniques that leverage coupling between multiple tiers to reduce data loss, take consistent snapshots across tiers, provide continuous data protection, and improve recovery time. We evaluate TierFS with analytical models, showing that TierFS can provide better recoverability than a conventional design of similar cost.

Data centers are often under-utilized due to over-provisioning as well as time-varying resource demands of typical enterprise applications. One approach to increase resource utilization is to consolidate applications in a shared infrastructure using virtualization. Meeting application-level quality of service (QoS) goals becomes a challenge in a consolidated environment as application resource needs differ. Furthermore, for multi-tier applications, the amount of resources needed to achieve their QoS goals might be different at each tier and may also depend on availability of resources in other tiers. In this paper, we develop an adaptive resource control system that dynamically adjusts the resource shares to individual tiers in order to meet application-level QoS goals while achieving high resource utilization in the data center. Our control system is developed using classical control theory, and we used a black-box system modeling approach to overcome the absence of first principle models for complex enterprise applications and systems. To evaluate our controllers, we built a testbed simulating a virtual data center using Xen virtual machines. We experimented with two multi-tier applications in this virtual data center: a two-tier implementation of RUBiS, an online auction site, and a two-tier Java implementation of TPC-W. Our results indicate that the proposed control system is able to maintain high resource utilization and meets QoS goals in spite of varying resource demands from the applications.

Modern storage systems are sophisticated. Simple directattached storage devices are giving way to storage systems that are shared, flexible, virtualized and network-attached. Today, storage systems have their own administrators, who use specialized tools and expertise to configure and manage storage resources. Although the separation of storage management and database management has many advantages, it also introduces problems. Database physical design and storage configuration are closely related tasks, and the separation makes it more difficult to achieve a good end-toend design. In this paper, we attempt to close this gap by addressing the problem of predicting the storage workload that will be generated by a database management system. Specifically, we show how to translate a database workload description, together with a database physical design, into a characterization of the storage workload that will result. Such a characterization can be used by a storage administrator to guide storage configuration. The ultimate goal of this work is to enable effective end-to-end design and configuration spanning both the database and storage system tiers. We present an empirical assessment of the cost of workload prediction as well as the accuracy of the result.

In this paper we extend the state-of-the-art in utilizing background knowledge for supervised classification by exploiting the semantic relationships between terms explicated in Ontologies. Preliminary evaluations indicate that the new approach generally improves precision and recall, more so for hard to classify cases and reveals patterns indicating the usefulness of such background knowledge.

Countering Distributed Denial of Service (DDoS) attacks is becoming ever more challenging with the vast resources and techniques increasingly available to attackers. In this paper, we consider sophisticated attacks that are protocol-compliant, non-intrusive, and utilize legitimate application-layer requests to overwhelm system resources. We characterize application-layer resource attacks as either request flooding, asymmetric, or repeated one-shot, on the basis of the application workload parameters that they exploit. To protect servers from these attacks, we propose a counter-mechanism that consists of a suspicion assignment mechanism and a DDoS-resilient scheduler, DDoS Shield. In contrast to prior work, our suspicion mechanism assigns a continuous valued vs. binary measure to each client session, and the scheduler utilizes these values to determine if and when to schedule a session’s requests. Using testbed experiments on a web application, we demonstrate the potency of these resource attacks and evaluate the efficacy of our counter-mechanism. For instance, we effect an asymmetric attack which overwhelms the server resources, increasing the response time of legitimate clients from 0.1 seconds to 10 seconds. Under the same attack scenario, DDoS Shield limits the effects of false-negatives and false-positives and improves the victims’ performance to 0.8 seconds.

Growth and usage trends for large decision support databases indicate that there is a need for architectures that scale the processing power as the dataset grows. To meet this need, several researchers have recently proposed active disk architectures which integrate substantial processing power and memory into disk units. In this paper, we evaluate Active Disks for decision support databases. First, we compare the performance of Active Disks with that of existing scalable server architectures: SMP-based conventional disk farms and commodity clusters of PCs. Second, we evaluate the impact of several design choices on the performance of Active Disks. We focus on the performance impact of interconnect bandwidth, amount of disk memory and disk-to-disk communication architecture on decision support workloads. Our results show that for identical disks, number of processors and I/O interconnect, Active Disks provide better price/performance than both SMP-based conventional disk farms and commodity cluster. Experiments evaluating the impact of design alternatives in Active Disk architectures indicate that: (1) for configurations up to 64 disks, a dual fibre channel arbitrated loop interconnect is sufficient even for the most communication-intensive decision support tasks: (2) most decision support task do not require a large amount of memory: and (3) direct disk-to-disk communication is necessary for achieving good performance on tasks that repartition all (or a large fraction of) their dataset.

Several application and technology trends indicate that it might be both profitable and feasible to move computation closer to the data that it processes. In this paper, we evaluate Active Disk architectures which integrate significant processing power and memory into a disk drive and allow application-specific code to be downloaded and executed on the data that is being read from (written to) disk. The key idea is to offload bulk of the processing to the diskresident processors and to use the host processor primarily for coordination, scheduling and combination of results from individual disks. To program Active Disks, we propose a stream-based programming model which allows disklets to be executed efficiently and safely. Simulation results for a suite of six algorithms from three application domains (commercial data warehouses, image processing and satellite data processing) indicate that for these algorithms, Active Disks outperform conventional-disk architectures.

In this study a robust color quantization method, which is based on a one-dimensional dynamic thresholding method, is introduced. The proposed method extracts a set of one-dimensional color intervals, each of which is ordered with respect to the distance to the reference color of that interval. The color intervals are then used to form the rows of the color similarity matrix for a given image. The selection of color palate is accomplished on the color similarity matrix by minimizing the total square error with respect to a threshold variable, which dynamically defines the color similarity for a given image. The experimental results indicate that the proposed method yields smaller quantization error and better visual appearance compared to the Heckbert's algorithm. It is faster than the existing color quantization methods.