Optimizing tail latency via workload and resource redundancy in cloud

Patent metadata

Field	Value
Publication number	US-11455197-B2
Application number	US-201916686453-A
Country	US
Kind code	B2
Filing date	Nov 18, 2019
Priority date	Sep 18, 2016
Publication date	Sep 27, 2022
Grant date	Sep 27, 2022

Abstract

A plurality of requests are received for computing processing. At least some of the plurality of requests are replicated. The requests are replicated based on a fractional replication factor. Each received request and each replicated request are transmitted to a computer resource for processing. At least some embodiments provide the capability for meeting tail latency targets with improved performance and reduced cost.

First claim

What is claimed is:

1. A computer-implemented method for performing computing processing comprising:
receiving a plurality of requests for computing processing;
replicating at least some of the plurality of requests, wherein the replicating is repeated for transmission to each of a plurality of computer resources based on a fractional replication factor prior to transmission of the plurality of requests;
transmitting each received request and each replicated request to a computer resource of the plurality of computer resources for processing;
determining a tail latency for performing the requested computing processing; and
incrementally increasing the fractional replication factor when the determined tail latency does not meet a target tail latency.

2. The method of claim 1 , wherein the replicating is performed by a process selected from a group of processes consisting of:
replicating selected requests, wherein the requests are selected based on a replication factor;
replicating requests a number of times on average based on a randomly generated quantity;
replicating each request with a different frequency;
replicating requests stochastically by building a probability distribution having only integer values with an average equal to the fractional replication factor and determining a replication factor for each request based on the probability distribution; and
replicating requests deterministically by defining a sequence of replication factors with an average equal to the fractional replication factor and determining a replication factor for each request based on the sequence.

3. The method of claim 1 , further comprising:
decreasing the fractional replication factor when the determined tail latency meets the target tail latency.

4. A computer-implemented method for performing computing processing comprising:
receiving a plurality of requests for computing processing;
replicating at least some of the plurality of requests, wherein the requests are replicated based on a fractional replication factor prior to transmission of the plurality of requests;
transmitting each received request and each replicated request to a computer resource for processing;
determining a tail latency for performing the requested computing processing;
incrementally increasing the fractional replication factor when the determined tail latency does not meet a target tail latency; and
increasing computing resources provisioned to perform the processing when the determined tail latency does not meet the target tail latency and increasing the fractional replication factor does not result in a decrease in the determined tail latency.

5. The method of claim 4 , wherein the computing resources comprise at least one of a virtual machine or a server.

6. The method of claim 4 , further comprising:
decreasing the fractional replication factor when the determined tail latency meets the target tail latency; and
decreasing the computing resources provisioned to perform the processing when the fractional replication factor has been decreased and the provisioned computing resources have been increased.

7. A computer program product for performing computing processing, the computer program product comprising a non-transitory computer readable storage having program instructions embodied therewith, the program instructions executable by a computer, to cause the computer to perform a method comprising:
receiving a plurality of requests for computing processing;
replicating at least some of the plurality of requests, wherein the replicating is repeated for transmission to each of a plurality of computer resources based on a fractional replication factor prior to transmission of the plurality of requests;
transmitting each received request and each replicated request to a computer resource of the plurality of computer resources for processing;
determining a tail latency for performing the requested computing processing; and
incrementally increasing the fractional replication factor when the determined tail latency does not meet a target tail latency.

8. The computer program product of claim 7 , wherein the replicating is performed by a process selected from a group of processes consisting of:
replicating selected requests, wherein the requests are selected based on a replication factor;
replicating requests a number of times on average based on a randomly generated quantity;
replicating each request with a different frequency;
replicating requests stochastically by building a probability distribution having only integer values with an average equal to the fractional replication factor and determining a replication factor for each request based on the probability distribution; and
replicating requests deterministically by defining a sequence of replication factors with an average equal to the fractional replication factor and determining a replication factor for each request based on the sequence.

9. The computer program product of claim 7 , further comprising program instructions for:
decreasing the fractional replication factor when the determined tail latency meets the target tail latency.

10. A computer program product for performing computing processing, the computer program product comprising a non-transitory computer readable storage having program instructions embodied therewith, the program instructions executable by a computer, to cause the computer to perform a method comprising: receiving a plurality of requests for computing processing;
replicating at least some of the plurality of requests, wherein the requests are replicated based on a fractional replication factor prior to transmission of the plurality of requests;
transmitting each received request and each replicated request to a computer resource for processing;
determining a tail latency for performing the requested computing processing;
incrementally increasing the fractional replication factor when the determined tail latency does not meet a target tail latency; and
increasing computing resources provisioned to perform the processing when the determined tail latency does not meet the target tail latency and increasing the fractional replication factor does not result in a decrease in the determined tail latency.

11. The computer program product of claim 10 , wherein the computing resources comprise at least one of a virtual machine or a server.

12. The computer program product of claim 10 , further comprising program instructions for:
decreasing the fractional replication factor when the determined tail latency meets the target tail latency; and
decreasing the computing resources provisioned to perform the processing when the fractional replication factor has been decreased and the provisioned computing resources have been increased.

13. A system for performing computing processing, the system comprising a processor, memory accessible by the processor, and computer program instructions stored in the memory and executable by the processor to perform:
receiving a plurality of requests for computing processing;
replicating at least some of the plurality of requests, wherein the replicating is repeated for transmission to each of a plurality of computer resources based on a fractional replication factor prior to transmission of the plurality of requests;
transmitting each received request and each replicated request to a computer resource of the plurality of computer resources for processing;
determining a tail latency for performing the requested computing processing; and
incrementally increasing the fractional replication factor when the determined tail latency does not meet a

Assignees

• IBM

Inventors

• Birke Robert
• Bjoerkqvist Mathias
• Chen Yiyu L
• Schmatz Martin L

Classifications

• G06F9/5061

  Partitioning or combining of resources · CPC title

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F9/505

  considering the load · CPC title