Resilient key management is particularly important for systems whose functionality depends on the high availability of cryptographically controlled data. A natural approach to achieving resilience implies the use of more distributed nodes as key managers, so that, in case something happens with one, some remain available. However, such distributed systems may experience network partitions, i.e. network splits that separate nodes in different disconnected islands. In this paper, we propose a decentralized key management solution that continues to operate in the event of network partitions and also conflict-free reintegrates back into a single system after partitions merge. Our solution encodes keys as conflict-free replicated data types and distributes the knowledge about them through a combination of push- and pull-based epidemics, and gossip protocol. We introduce a proof-of-concept implementation and evaluate it under different scenarios of network partitions and recoveries, concluding that the system correctly converges in limited time after partition events, that the overhead of spreading information about keys is bounded and that the latency of key-related client requests is acceptably low.

Offering consistent low latency remains a key challenge for distributed applications, especially when deployed on the cloud where virtual machines (VMs) suffer from capacity variability caused by co-located tenants. Replicating redundant requests was shown to be an effective mechanism to defend application performance from high capacity variability. While the prior art centers on single-tier systems, it still remains an open question how to design replication strategies for distributed multi-tier systems. In this paper, we design a first of its kind PArtial REplication system, sPARE, that replicates and dispatches read-only workloads for distributed multi-tier web applications. The two key components of sPARE are (i) the variability-aware replicator that coordinates the replication levels on all tiers via an iterative searching algorithm, and (ii) the replication-aware arbiter that uses a novel token-based arbitration algorithm (TAD) to dispatch requests in each tier. We evaluate sPARE on web serving and searching applications, i.e., MediaWiki and Solr, the former deployed on our private cloud and the latter on Amazon EC2. Our results based on various interference patterns and traffic loads show that sPARE is able to improve the tail latency of MediaWiki and Solr by a factor of almost 2.7x and 2.9x, respectively.

As use of cryptography increases in all areas of computing, efficient solutions for key management in distributed systems are needed. Large deployments in the cloud can require millions of keys for thousands of clients. The current approaches for serving keys are centralized components, which do not scale as desired. This work reports on the realization of a key manager that uses an untrusted distributed key-value store (KVS) and offers consistent key distribution over the Key-Management Interoperability Protocol (KMIP). To achieve confidentiality, it uses a key hierarchy where every key except a root key itself is encrypted by the respective parent key. The hierarchy also allows for key rotation and, ultimately, for secure deletion of data. The design permits key rotation to proceed concurrently with key-serving operations. A prototype was integrated with IBM Spectrum Scale, a highly scalable cluster file system, where it serves keys for file encryption. Linear scalability was achieved even under load from concurrent key updates. The implementation shows that the approach is viable, works as intended, and suitable for high-throughput key serving in cloud platforms.

A common pitfall when hosting applications in today's cloud environments is that virtual servers often experience varying execution speeds due to the interference from co-located virtual servers degrading the tail sojourn times specified in service level agreements. Motivated by the significance of tail sojourn times for cloud clusters, we develop a model of N parallel virtual server queues, each of which processes jobs in a processor sharing fashion under varying execution speeds governed by Markov-modulated processes. We derive the tail distribution of the workloads for each server and the approximation for the tail sojourn times based on large deviation analysis. Furthermore, we optimize the cluster sizes that fulfill the requirements of target tail sojourn times. Extensive simulation experiments show very good matches to the derived analysis in a variety of scenarios, i.e., large numbers of servers experiencing a high number of different execution speeds, under various traffic intensities, workload variations and cluster sizes. Finally, we apply our proposed analysis to estimating the tail sojourn times of a Wikipedia system hosted in a private cloud, and the testbed results strongly confirm the applicability and accuracy of our analysis.

Real-time processing of big data has become a core operation in various areas of business, such as extracting value from real-time social network data. Big data workloads in the wild show a strong temporal variability that not only poses the risk of slow responsiveness in data analysis, but also leads to a high risk of service outage. The recent development of batch streaming systems based on the MapReduce framework is shown effective on non-overloaded systems. However, little is known on how to enhance the performance of the batch streaming systems for bursty workloads. In this paper, we propose a latency-driven data controller, Dslash, which aims to process as much data as possible, while processing these as fast as the application target latency and system capacity allow. In particular, we implement Dslash on Spark Streaming - an emerging and complex batch streaming system. Dslash features include (i) placing data in an augmented distributed memory, (ii) shedding out-of-date data, (iii) improving the processing locality of Map tasks, and (iv) delaying data processing in transient overloads. Extensive evaluations on a large number of workloads show that Dslash can ensure stable and fast responsiveness compared to vanilla Spark Streaming systems.

Wimpy virtual instances equipped with small numbers of cores and RAM are popular public and private cloud offerings because of their low cost for hosting applications. The challenge is how to run latency-sensitive applications using such instances, which trade off performance for cost. In this study, we analytically and experimentally show that simultaneously scaling resources at coarse granularity and workloads, i.e., submitting multiple query clones to different servers, at fine granularity can overcome the performance disadvantages of wimpy VM instances and achieve stringent latency targets that are even lower than the average execution times of wimpy servers. To such an end, we first derive a closed-form analysis for the latency under any given VM provisioning and query replication level, considering cloning policies that can (not) terminate outstanding clones with (without) an overhead. Validated on trace-driven simulations, our analysis is able to accurately predict the latency and efficiently search for the optimal number of VMs and clones. Secondly, we develop a dual elastic scaler, DuoScale, that dynamically scales VMs and clones according to the workload dynamics so as to achieve the target latency in a cost-effective manner. The effectiveness of DuoScale lies on the observation that the application performance only scales sub-linearly with increasing vertical or horizontal resource provisioning, i.e., resources per VM or number of VMs. We evaluate DuoScale against VM-only scaling strategies via extensive trace-driven simulations as well as experimental results on a cloud test-bed. Our results show that DuoScale is able to achieve the stringent target latency by using clones on wimpy VMs with cost savings up to 50%, compared to scaling brawny VMs that have better performance at a higher unit cost.

Replicating redundant requests has been shown to be an effective mechanism to defend application performance from high capacity variability - the common pitfall in the cloud. While the prior art centers on single-tier systems, it still remains an open question how to design replication strategies for distributed multi-tier systems, where interference from neighboring workloads is entangled with complex tier interdependency. In this paper, we design a first of its kind PArtial REplication system, sPARE, that replicates and dispatches read-only workloads for multi-tier web applications, determining replication factors per tier. The two key components of sPARE are (i) the variability-aware replicator that coordinates the replication levels on all tiers via an iterative searching algorithm, and (ii) the replication-aware arbiter that uses a novel token-based arbitration algorithm (TAD) to dispatch requests in each tier. We evaluate sPARE on web serving and web searching applications, i.e., MediaWiki and Solr, deployed on our private cloud testbed. Our results based on various interference patterns and traffic loads show that sPARE is able to improve the tail latency of MediaWiki and Solr by a factor of almost 2.7x and 2.9x, respectively.

Peak loads are a challenge for streaming systems. Here we present Dslash, a latency-driven controller that keeps and processes as much data as the system resources allow in order to meet a target latency.

Service providers seek scalable and cost-effective cloud solutions for hosting their applications. Despite significant advances facilitating cloud services deployment and management, a number of challenges still remain. Service providers are confronted with time-varying workloads, inter-dependencies between components, performance variability of the procured virtual resources, and cost structures that differ from conventional data centers. Moreover, fulfilling service level agreements (SLAs), such as the throughput and response time percentiles, becomes of paramount importance for ensuring business advantages. In this dissertation paper, we explore service provisioning in clouds from multiple points of view. The aim is to best provide service replicas in the form of VMs to various applications, such that their tail throughputs and tail response times, as well as resource utilization, meet the SLAs in the most cost effective manner. In particular, we develop models, algorithms and replication strategies that consider multi-tier services provisioned in the cloud, investigate how a service provider can opportunistically take advantage of observed cloud performance variability and provide means of guaranteeing tail throughput and response times in the face of the aforementioned performance variability. Overall, this dissertation paper provides not only a multi-faceted approach to exploring several crucial aspects of cloud-hosted services, i.e., cost, tail throughput, and tail response times, but our proposed management strategies are also rigorously validated via trace-driven simulations and extensive experiments.

As modern service systems are pressured to provide competitive prices via cost-effective capacity planning, especially in the paradigm of cloud computing, service level agreements (SLAs) end up becoming ever more sophisticated, i.e., fulfilling targets of different percentiles of response times. However, it is no mean feat to predict even the average response times of real systems, or even abstracted queueing systems that typically simplify system details, and it gets even more complicated when trying to manage SLAs defined by various percentiles of response times. To efficiently capture these different percentiles, we first develop a novel and autonomic methodology — termed Burst Based Simulation, which combines burst profiling on real systems with complex, state-dependent simulations. Moreover, based on our methodology, we construct an analysis on SLA management: the prediction of SLA violations given a certain request pattern. We evaluate our approach on two types of service systems, virtualized and bare-metal, with wide ranges of SLAs and traffic loads. Our evaluation results show that our methodology is able to achieve an average error below 15% when predicting different response time percentiles, and accurately capture SLA violations.

The wide deployment of virtualization in datacenters catalyzes the emergence of virtual traffic that delivers the network demands between the physical network and the virtual machines hosting clients' services. Virtual traffic presents new opportunities for reducing physical network demands, as well as challenges of increasing management complexity. Given the plethora of prior art on virtualization technologies in datacenters, surprisingly little is still known about such virtual traffic, and its dependence on the physical network and virtual machines. This paper provides a multi-faceted analysis of the patterns and impacts of multiplexing the virtual traffic onto the physical network, particularly from the perspective of the network edge. We use a large collection of field data from production datacenters hosting a large number of diversified services from multiple enterprise tenants. Our first focus is on uncovering the temporal and spatial characteristics of the virtual and physical traffic, i.e., network demand growth and communication patterns, with special attention paid to the traffic of migrating virtual machines. The second focus is on characterizing the effect of network multiplexing in terms of communication locality, traffic load heterogeneity, and the dependency on CPU processing power at the edges of the network. Last but not least, we conduct a mirroring analysis on service QoS, defined by the service unavailability induced by network related issues, e.g., loads. We qualitatively and quantitatively discuss the implications and opportunities that virtual traffic presents for network capacity planning of virtualized networks and datacenters.

Today's web services are commonly hosted on clusters of servers that are often located within computing clouds, whose computational and storage resources can be highly heterogeneous. The workload served typically exhibits disparate computation patterns (e.g., CPU-intensive or IO-intensive), that fluctuate both in terms of volume and mix. The system heterogeneity together with workload diversity further exacerbates the challenge of effective distribution of load within a computing cloud. This paper presents a novel, mix-aware load-balancing algorithm, which aims to distribute requests sent by multiple applications in heterogeneous servers such that the application response times are minimized and system resources (e.g., CPU and IO) are equally utilized. To this end, the presented algorithm tries to not only balance the total number of requests seen by each server, but also to shape the requests received by each server into a certain "mix", that is analytically shown to be optimal for response time minimization. Our experimental results---based both on simulation and on a prototype implementation---show that the mix-aware algorithm achieves robust performance in most workload mixes as well as a consistent performance improvement in comparison with one of the most robust load-balancing schemes of the Apache server.

There is an emerging trend to deploy services in cloud environments due to their flexibility in providing virtual capacity and pay-as-you-go billing features. Cost-aware services demand computation capacity such as virtual machines (VMs) from a cloud operator according to the workload (i.e., service invocations) and pay for the amount of capacity used following billing contracts. However, as recent empirical studies show, the performance variability, i.e., non-uniform VM performance, is inherently higher than in private hosting platforms, since cloud platforms provide VMs running on top of typically heterogeneous hardware shared by multiple clients. Consequently, the provisioning of service capacity in a cloud needs to consider workload variability as well as varying VM performance. We propose an opportunistic service replication policy that leverages the variability in VM performance, as well as the on-demand billing features of the cloud. Our objective is to minimize the service provisioning costs by keeping a lower number of faster VMs, while maintaining target system utilization. Our evaluation results on traces collected from in-production systems show that the proposed policy achieves significant cost savings and low response times.

Service-oriented systems, consisting of atomic services and their compositions hosted in service composition execution engines (CEEs), are commonly deployed to deliver web applications. As the workloads of applications fluctuate over time, it is economical to autonomously and dynamically adjust system capacity, i.e., the number of replicas for atomic services and CEEs. In this paper, we propose a novel replica provisioning policy, Resos, which adjusts the number of CEE and service replicas periodically based on the predicted workloads such that all replicas are well utilized at the target values. In particular, Resos models the workload balance and dependency between CEE and service replicas by estimating the probability that threads of CEE replicas are not blocked by I/O. Moreover, we derive the analytical bounds of CEE effective utilization and illustrate the cause of low nominal utilization at CEE replicas. We evaluate Resos on a simulated service-oriented system, which hosts CEE and service replicas on multi-threaded servers. The evaluated workload is derived from utilization traces collected from production systems. Through simulation, we demonstrate that Resos effectively reduces the number of required replicas while maintaining target utilization and lowering the response times of requests.

Content distribution systems, such as on-demand video services [6], file-sharing networks [8,1], and content clouds [2], provide ubiquitous data access and data sharing for large numbers of end-users. To efficiently provide content access across geographic locations, content storage nodes with limited capacity are conventionally organized in a multi-layer architecture to facilitate vertical as well as horizontal peer content retrievals, each of which may have different bandwidth constraints and transport costs. Content management, i.e., caching strategies, is deployed to efficiently utilize storage nodes and further reduce network retrieval traffic and cost. An optimal system design of such a multi-layer system needs to accommodate the trade-offs between vertical communication, peer communication, storage capacity and the users' retrieval traffic, driven by caching policies. In this paper, we propose a generic optimization framework based on steady-state content diffusion to minimize the total content retrieval cost in multi-layer content distribution systems, while considering the aforementioned trade-offs. The derived optimal content diffusion can evaluate the optimality of caching policies, and dimension the size of the system and the node caching capacity. Furthermore, we develop Peer Aware Content Caching (PACC) policies based on the derived optimal content diffusion. Our simulation results show that PACC effectively caches content and minimizes vertical and horizontal content retrieval costs under different system scenarios.

Content cloud systems, e.g. CloudFront [1] and CloudBurst [2], in which content items are retrieved by end-users from the edge nodes of the cloud, are becoming increasingly popular. The retrieval latency in content clouds depends on content availability in the edge nodes, which in turn depends on the caching policy at the edge nodes. In case of local content unavailability (i.e., a cache miss), edge nodes resort to source selection strategies to retrieve the content items either vertically from the central server, or horizontally from other edge nodes. Consequently, managing the latency in content clouds needs to take into account several interrelated issues: asymmetric bandwidth and caching capacity for both source types as well as edge node heterogeneity in terms of caching policies and source selection strategies applied. In this paper, we study the problem of minimizing the retrieval latency considering both caching and retrieval capacity of the edge nodes and server simultaneously. We derive analytical models to evaluate the content retrieval latency under two source selection strategies, i.e., Random and Shortest-Queue, and three caching policies: selfish, collective, and a novel caching policy that we call the adaptive caching policy. Our analysis allows the quantification of the interrelated performance impacts of caching and retrieval capacity and the exploration of the corresponding design space. In particular, we show that the adaptive caching policy combined with Shortest-Queue selection scales well with various network configurations and adapts to the load changes in our simulation and analytical results.

Performance and scalability of service-oriented applications, such as Web service compositions or business processes, depend on the dynamically bound services. In order to handle an increasing number of clients, load-balancing techniques are important. In this paper we assume the presence of multiple functionally equivalent services and explore different load-balancing algorithms to dynamically select service bindings with the goal to reduce average service response time. Using mathematical queueing models of service performance and simulation, we compare different service selection algorithms, including Static Lottery, Round-Robin, and Shortest-Queue. Furthermore, we propose linear and quadratic Dynamic Lottery service selection algorithms, which assign and periodically update service selection probabilities according to monitored average service response time. Our simulation environment models both stateless and stateful services and offers a wide range of service performance models with different degrees in the variation of service response time. While the Shortest-Queue algorithm performs best in simulation settings with only stateless services or low variance of service response time, the Round-Robin and Dynamic Lottery algorithms work best in settings with stateful services and high variance of service performance.

In this paper we study the content retrieval delay in a hybrid content distribution system, e.g., emerging content clouds [1], where a requested content item can be vertically retrieved from the central server and horizontally retrieved from network nodes. The content retrieval delay depends on the load intensities of the retrieval sources, which have asymmetric system properties such as bandwidth and cache capacity. The retrieval traffic arises due to heterogeneous content availability, i.e., content diffusion resulting from the applied caching policies, and the selection of retrieval sources. To optimize the retrieval delay, the advantages of the network nodes should be utilized while also leveraging the caching and retrieval capacity of the server. The traffic loads and latency of a given combination of source selection and caching policy is derived based on the content diffusion and distribution in the entire system. The simulation and analytical results show that satisfactory content retrieval delay is achieved when the retrieval selection is load aware and the caching policies can effectively utilize the cache storage and retrieval capacity of both the network nodes and the server.