Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Redundancy Techniques for Latency Reduction in Cloud Systems
198
0
0.0
(
0
)
Added by
Gauri Joshi
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In cloud computing systems, assigning a task to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers, and reduce latency. But adding redundancy may result in higher cost of computing resources, as well as an increase in queueing delay due to higher traffic load. This work helps understand when and how redundancy gives a cost-efficient reduction in latency. For a general task service time distribution, we compare different redundancy strategies in terms of the number of redundant tasks, and time when they are issued and canceled. We get the insight that the log-concavity of the task service time creates a dichotomy of when adding redundancy helps. If the service time distribution is log-convex (i.e. log of the tail probability is convex) then adding maximum redundancy reduces both latency and cost. And if it is log-concave (i.e. log of the tail probability is concave), then less redundancy, and early cancellation of redundant tasks is more effective. Using these insights, we design a general redundancy strategy that achieves a good latency-cost trade-off for an arbitrary service time distribution. This work also generalizes and extends some results in the analysis of fork-join queues.
rate research
Read More
In cloud computing systems, assigning a job to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers. Although adding redundant replicas always reduces service time, the total computing time spent per job may be higher, thus increasing waiting time in queue. The total time spent per job is also proportional to the cost of computing resources. We analyze how different redundancy strategies, for eg. number of replicas, and the time when they are issued and canceled, affect the latency and computing cost. We get the insight that the log-concavity of the service time distribution is a key factor in determining whether adding redundancy reduces latency and cost. If the service distribution is log-convex, then adding maximum redundancy reduces both latency and cost. And if it is log-concave, then having fewer replicas and canceling the redundant requests early is more effective.
In cloud storage systems with a large number of servers, files are typically not stored in single servers. Instead, they are split, replicated (to ensure reliability in case of server malfunction) and stored in different servers. We analyze the mean latency of such a split-and-replicate cloud storage system under general sub-exponential service time. We present a novel scheduling scheme that utilizes the load-balancing policy of the textit{power of $d$ $(geq 2)$} choices. An alternative to split-and-replicate is to use erasure-codes, and recently, it has been observed that they can reduce latency in data access (see cite{longbo_delay} for details). We argue that under high redundancy (integer redundancy factor strictly greater than or equal to 2) regime, the mean latency of a coded system is upper bounded by that of a split-and-replicate system (with same replication factor) and the gap between these two is small. We validate this claim numerically under different service distributions such as exponential, shift plus exponential and the heavy-tailed Weibull distribution and compare the mean latency to that of an unsplit-replicated system. We observe that the coded system outperforms the unsplit-replication system by at least $20%$. Furthermore, we consider the mean latency for an erasure coded system with low redundancy (fractional redundancy factor between 1 and 2), a scenario which is more pragmatic, given the storage constraints (cite{rashmi_thesis}). However under this regime, we restrict ourselves to the special case of exponential service time distribution and use the randomized load balancing policy namely textit{batch-sampling}. We obtain an upper bound on mean delay that depends on the order statistics of the queue lengths, which, we further smooth out via a discrete to continuous approximation.
As numerous machine learning and other algorithms increase in complexity and data requirements, distributed computing becomes necessary to satisfy the growing computational and storage demands, because it enables parallel execution of smaller tasks that make up a large computing job. However, random fluctuations in task service times lead to straggling tasks with long execution times. Redundancy, in the form of task replication and erasure coding, provides diversity that allows a job to be completed when only a subset of redundant tasks is executed, thus removing the dependency on the straggling tasks. In situations of constrained resources (here a fixed number of parallel servers), increasing redundancy reduces the available resources for parallelism. In this paper, we characterize the diversity vs. parallelism trade-off and identify the optimal strategy, among replication, coding and splitting, which minimizes the expected job completion time. We consider three common service time distributions and establish three models that describe scaling of these distributions with the task size. We find that different distributions with different scaling models operate optimally at different levels of redundancy, and thus may require very different code rates.
The maximum possible throughput (or the rate of job completion) of a multi-server system is typically the sum of the service rates of individual servers. Recent work shows that launching multiple replicas of a job and canceling them as soon as one copy finishes can boost the throughput, especially when the service time distribution has high variability. This means that redundancy can, in fact, create synergy among servers such that their overall throughput is greater than the sum of individual servers. This work seeks to find the fundamental limit of the throughput boost achieved by job replication and the optimal replication policy to achieve it. While most previous works consider upfront replication policies, we expand the set of possible policies to delayed launch of replicas. The search for the optimal adaptive replication policy can be formulated as a Markov Decision Process, using which we propose two myopic replication policies, MaxRate and AdaRep, to adaptively replicate jobs. In order to quantify the optimality gap of these and other policies, we derive upper bounds on the service capacity, which provide fundamental limits on the throughput of queueing systems with redundancy.
The overall performance of the development of computing systems has been engrossed on enhancing demand from the client and enterprise domains. but, the intake of ever-increasing energy for computing systems has commenced to bound in increasing overall performance due to heavy electric payments and carbon dioxide emission. The growth in power consumption of server is increased continuously, and many researchers proposed, if this pattern repeats continuously, then the power consumption cost of a server over its lifespan would be higher than its hardware prices. The power intake troubles more for clusters, grids, and clouds, which encompass numerous thousand heterogeneous servers. Continuous efforts have been done to reduce the electricity intake of these massive-scale infrastructures. To identify the challenges and required future enhancements in the field of efficient energy consumption in Cloud Computing, it is necessary to synthesize and categorize the research and development done so far. In this paper, the authors discuss the reasons and problems associated with huge energy consumption by Cloud data centres and prepare a taxonomy of huge energy consumption problems and its related solutions. The authors cover all aspects of energy consumption by Cloud data centers and analyze many research papers to find the better solution for efficient energy consumption. This work gives an overall information regarding energy-consumption problems of Cloud data centres and energy-efficient solutions for this problem. The paper is concluded with a conversation of future enhancement and development in energy-efficient methods in Cloud Computing
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
