Latency Tricks

By: Clark Gaebel [web] [keybase] [email]

Special thanks to reviewers: Ben Foppa [keybase], Norm Tasfi [web] [twitter]

The Setup

Servers take time to respond to messages. In many systems, the time it takes is commonly quite low (tens of milliseconds), while rare events cause it to be very high (hundreds of milliseconds, or even seconds) in other cases. The distribution of service latency in real systems tends to have a long, fat tail: many requests have a response latency of an order of magnitude or more higher than the average latency, but the vast majority are responded to in a reasonable amount of time.

Systems that have this property aren't just annoying. For soft realtime systems like websites, the infrequent requests that take a long time can frustrate users to the point of leaving. What's worse is that, as a user spends more time on the site, they have a higher likelihood of eventually hitting one of these frustrating events.

This problem is so common that it has a folk solution: replicate the service to multiple servers, and send to all of them at once. Whichever answers first has its results returned.

How does this strategy affect our latency? Intuitively, it will decrease. The average won't decrease by much, but the tail of the latency PDF will be dramatically reduced.

Before trying to answer this question, a single server's latency must be modeled {we need to model the latency of a single server}. The Pareto distribution is a common distribution with the properties mentioned above.

Pareto Distributions

PDF of a Pareto Distribution

The probability distribution function of a Pareto distribution

The cumulative distribution function of a Pareto distribution

A pareto distribution has two parameters: $x_m$ and $\alpha$.

$x_m$ is the minimum (and most common) latency, which determines how far to the right the PDF lies. In the above illustrations, $x_m = 1$.

$\alpha$ is the "shape", which defines how fat the tail of the PDF is. The lower it is, the more likely high latency events are to occur.

Let's explore this distribution a little. What does it look like with a variety of alphas? For that, we sample the distribution a few million times, sort the latencies into buckets, then plot it:

In [1]:
using Color
using Gadfly

addprocs(7)

@everywhere num_samples = 10000000 # Number of samples to simulate
@everywhere buckets     = 1000     # The number of buckets to split the PDF into for plotting.
@everywhere x_m         = 1        # Pareto parameter

# Maps a set of indexes into their proper bucket. Returns a vector
# of buckets and how many indexes mapped to each one.
@everywhere function bucket(indexes)
    len = maximum(indexes)
    r = zeros(Int32, len)
    for i = indexes
        @inbounds r[i] += 1
    end
    r
end

# Finds the pdf (exponential x scale) of a set of samples, split into `buckets` buckets.
# This returns a pair of vectors representing (latency, probability). Latencies
# are calculated on a exponential scale to make the graphs easier to interpret.
@everywhere function pdf_of(samples)
    logsamples = log(samples)
    min_, max_ = extrema(logsamples)
    stepwidth  = (max_ - min_) / buckets
    istepwidth = 1 / stepwidth
    # `eps` added to prevent `min_` from mapping to index 0.
    # `min` with `buckets` to prevent `max_` from mapping to an out of bounds value.
    indexes    = min(ceil((logsamples .- min_) .* istepwidth .+ eps()), buckets)
    bucketed   = bucket(convert(Array{Int32, 1}, indexes))
    normalized = bucketed .* (1 / length(logsamples))
    xs         = exp(linspace(min_ + stepwidth, max_ - stepwidth, buckets))
    (xs, normalized)
end

# The inverse CDF (aka Quantile) of the pareto distribution.
@everywhere function icdf_pareto(alpha, y)
    x_m ./ (1 .- y) .^ (1 / alpha)
end

# Samples the pareto distribution `num_samples` times.
@everywhere function pareto(alpha)
    unif = rand(num_samples)
    icdf_pareto(alpha, unif)
end

@everywhere function simulate_pareto(alpha)
    z            = pareto(alpha)
    (z_x, z_pdf) = pdf_of(z)
    z_cdf        = cumsum_kbn(z_pdf)
    (z_x, z_pdf, z_cdf, alpha)
end

function plot_pareto_pdfs(results)
    colors = colormap("Blues", length(results))
    layered_results = map(
        (k) -> layer(x=results[k][1], y=results[k][2], Geom.line, Theme(default_color=colors[k])),
        1:length(results))
    plot(layered_results...,
    Guide.XLabel("Latency"), Guide.YLabel("Pr(X = x)"), Guide.title("PDF"), Scale.x_log10,
        Guide.manual_color_key("Legend", map((result) -> "α=$(result[4])", results), colors))
end

function plot_pareto_cdfs(results)
    colors = colormap("Blues", length(results))
    layered_results = map(
        (k) -> layer(x=results[k][1], y=results[k][3], Geom.line, Theme(default_color=colors[k])),
        1:length(results))
    plot(layered_results...,
        Guide.XLabel("Latency"), Guide.YLabel("Pr(X ≤ x)"), Guide.title("CDF"), Scale.x_log10,
        Guide.manual_color_key("Legend", map((result) -> "α=$(result[4])", results), colors))
end

;
In [2]:
function make_pareto_results()
    # Let's look at alpha from 1-8, and 256 to explore the limit condition.
    alphas = [1:8]
    push!(alphas, 256)

    pmap(simulate_pareto, alphas)
end

pareto_results = make_pareto_results();
In [3]:
plot_pareto_pdfs(pareto_results)
Out[3]:
Latency 10-10 10-8 10-6 10-4 10-2 100 102 104 106 108 1010 1012 1014 1016 1018 10-8.0 10-7.5 10-7.0 10-6.5 10-6.0 10-5.5 10-5.0 10-4.5 10-4.0 10-3.5 10-3.0 10-2.5 10-2.0 10-1.5 10-1.0 10-0.5 100.0 100.5 101.0 101.5 102.0 102.5 103.0 103.5 104.0 104.5 105.0 105.5 106.0 106.5 107.0 107.5 108.0 108.5 109.0 109.5 1010.0 1010.5 1011.0 1011.5 1012.0 1012.5 1013.0 1013.5 1014.0 1014.5 1015.0 1015.5 1016.0 10-10 100 1010 1020 10-8.0 10-7.5 10-7.0 10-6.5 10-6.0 10-5.5 10-5.0 10-4.5 10-4.0 10-3.5 10-3.0 10-2.5 10-2.0 10-1.5 10-1.0 10-0.5 100.0 100.5 101.0 101.5 102.0 102.5 103.0 103.5 104.0 104.5 105.0 105.5 106.0 106.5 107.0 107.5 108.0 108.5 109.0 109.5 1010.0 1010.5 1011.0 1011.5 1012.0 1012.5 1013.0 1013.5 1014.0 1014.5 1015.0 1015.5 1016.0 α=1 α=2 α=3 α=4 α=5 α=6 α=7 α=8 α=256 Legend -0.025 -0.020 -0.015 -0.010 -0.005 0.000 0.005 0.010 0.015 0.020 0.025 0.030 0.035 0.040 0.045 -0.020 -0.019 -0.018 -0.017 -0.016 -0.015 -0.014 -0.013 -0.012 -0.011 -0.010 -0.009 -0.008 -0.007 -0.006 -0.005 -0.004 -0.003 -0.002 -0.001 0.000 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008 0.009 0.010 0.011 0.012 0.013 0.014 0.015 0.016 0.017 0.018 0.019 0.020 0.021 0.022 0.023 0.024 0.025 0.026 0.027 0.028 0.029 0.030 0.031 0.032 0.033 0.034 0.035 0.036 0.037 0.038 0.039 0.040 0.041 -0.04 -0.02 0.00 0.02 0.04 -0.022 -0.020 -0.018 -0.016 -0.014 -0.012 -0.010 -0.008 -0.006 -0.004 -0.002 0.000 0.002 0.004 0.006 0.008 0.010 0.012 0.014 0.016 0.018 0.020 0.022 0.024 0.026 0.028 0.030 0.032 0.034 0.036 0.038 0.040 Pr(X = x) PDF
In [4]:
plot_pareto_cdfs(pareto_results)
Out[4]:
Latency 10-10 10-8 10-6 10-4 10-2 100 102 104 106 108 1010 1012 1014 1016 1018 10-8.0 10-7.5 10-7.0 10-6.5 10-6.0 10-5.5 10-5.0 10-4.5 10-4.0 10-3.5 10-3.0 10-2.5 10-2.0 10-1.5 10-1.0 10-0.5 100.0 100.5 101.0 101.5 102.0 102.5 103.0 103.5 104.0 104.5 105.0 105.5 106.0 106.5 107.0 107.5 108.0 108.5 109.0 109.5 1010.0 1010.5 1011.0 1011.5 1012.0 1012.5 1013.0 1013.5 1014.0 1014.5 1015.0 1015.5 1016.0 10-10 100 1010 1020 10-8.0 10-7.5 10-7.0 10-6.5 10-6.0 10-5.5 10-5.0 10-4.5 10-4.0 10-3.5 10-3.0 10-2.5 10-2.0 10-1.5 10-1.0 10-0.5 100.0 100.5 101.0 101.5 102.0 102.5 103.0 103.5 104.0 104.5 105.0 105.5 106.0 106.5 107.0 107.5 108.0 108.5 109.0 109.5 1010.0 1010.5 1011.0 1011.5 1012.0 1012.5 1013.0 1013.5 1014.0 1014.5 1015.0 1015.5 1016.0 α=1 α=2 α=3 α=4 α=5 α=6 α=7 α=8 α=256 Legend -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5 -1.00 -0.95 -0.90 -0.85 -0.80 -0.75 -0.70 -0.65 -0.60 -0.55 -0.50 -0.45 -0.40 -0.35 -0.30 -0.25 -0.20 -0.15 -0.10 -0.05 0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 1.05 1.10 1.15 1.20 1.25 1.30 1.35 1.40 1.45 1.50 1.55 1.60 1.65 1.70 1.75 1.80 1.85 1.90 1.95 2.00 -1 0 1 2 -1.0 -0.9 -0.8 -0.7 -0.6 -0.5 -0.4 -0.3 -0.2 -0.1 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0 Pr(X ≤ x) CDF

Intuitively, the limit case of the Pareto distribution as $\alpha \to \infty$ is all the probability mass lying at $x_m$. As $\alpha$ gets smaller, our tails get fatter.

Modeling Parallel Servers

Now that we have a model of a single server, let's model what happens when a service is built out of multiple redundant servers as outlined above. We take the response from the first server to provide one, so the overall latency is the minimum latency of all the responses.

This is done in the code below. $N$ servers are placed in parallel, then the overall latency of the system is shown.

In [5]:
@everywhere function simulate_parallel_pareto(alphas)
    z = @parallel (min) for alpha = alphas
        pareto(alpha)
    end

    (z_x, z_pdf) = pdf_of(z)
    z_cdf        = cumsum_kbn(z_pdf)
    (z_x, z_pdf, z_cdf, length(alphas))
end

function make_parallel_pareto_results(alpha)
    num_servers = [1:8]
    push!(num_servers, 256)

    # Simulate `k` servers in parallel, each with the same alpha.
    pmap(simulate_parallel_pareto, map((k) -> fill(alpha, k), num_servers))
end

function plot_parallel_pareto_pdfs(alpha, results)
    colors = colormap("Blues", length(results))
    layered_results = map(
        (k) -> layer(x=results[k][1], y=results[k][2], Geom.line, Theme(default_color=colors[k])),
        1:length(results))
    plot(layered_results...,
    Guide.XLabel("Latency"), Guide.YLabel("Pr(X = x)"), Guide.title("PDF (α=$(alpha))"), Scale.x_log10,
        Guide.manual_color_key("Legend", map((result) -> "N=$(result[4])", results), colors))
end

function plot_parallel_pareto_cdfs(alpha, results)
    colors = colormap("Blues", length(results))
    layered_results = map(
    (k) -> layer(x=results[k][1][2:end-1], y=results[k][3][2:end-1], Geom.line, Theme(default_color=colors[k])),
        1:length(results))
    plot(layered_results...,
        Guide.XLabel("Latency"), Guide.YLabel("Pr(X ≤ x)"), Guide.title("CDF (α=$(alpha))"), Scale.y_log10, Scale.x_log10,
        Guide.manual_color_key("Legend", map((result) -> "N=$(result[4])", results), colors))
end

;
In [6]:
parallel_results = make_parallel_pareto_results(1);
In [7]:
plot_parallel_pareto_pdfs(1, parallel_results)
Out[7]:
Latency 10-10 10-8 10-6 10-4 10-2 100 102 104 106 108 1010 1012 1014 1016 1018 10-8.0 10-7.5 10-7.0 10-6.5 10-6.0 10-5.5 10-5.0 10-4.5 10-4.0 10-3.5 10-3.0 10-2.5 10-2.0 10-1.5 10-1.0 10-0.5 100.0 100.5 101.0 101.5 102.0 102.5 103.0 103.5 104.0 104.5 105.0 105.5 106.0 106.5 107.0 107.5 108.0 108.5 109.0 109.5 1010.0 1010.5 1011.0 1011.5 1012.0 1012.5 1013.0 1013.5 1014.0 1014.5 1015.0 1015.5 1016.0 10-10 100 1010 1020 10-8.0 10-7.5 10-7.0 10-6.5 10-6.0 10-5.5 10-5.0 10-4.5 10-4.0 10-3.5 10-3.0 10-2.5 10-2.0 10-1.5 10-1.0 10-0.5 100.0 100.5 101.0 101.5 102.0 102.5 103.0 103.5 104.0 104.5 105.0 105.5 106.0 106.5 107.0 107.5 108.0 108.5 109.0 109.5 1010.0 1010.5 1011.0 1011.5 1012.0 1012.5 1013.0 1013.5 1014.0 1014.5 1015.0 1015.5 1016.0 N=1 N=2 N=3 N=4 N=5 N=6 N=7 N=8 N=256 Legend -0.025 -0.020 -0.015 -0.010 -0.005 0.000 0.005 0.010 0.015 0.020 0.025 0.030 0.035 0.040 0.045 -0.020 -0.019 -0.018 -0.017 -0.016 -0.015 -0.014 -0.013 -0.012 -0.011 -0.010 -0.009 -0.008 -0.007 -0.006 -0.005 -0.004 -0.003 -0.002 -0.001 0.000 0.001 0.002 0.003 0.004 0.005 0.006 0.007 0.008 0.009 0.010 0.011 0.012 0.013 0.014 0.015 0.016 0.017 0.018 0.019 0.020 0.021 0.022 0.023 0.024 0.025 0.026 0.027 0.028 0.029 0.030 0.031 0.032 0.033 0.034 0.035 0.036 0.037 0.038 0.039 0.040 0.041 -0.04 -0.02 0.00 0.02 0.04 -0.022 -0.020 -0.018 -0.016 -0.014 -0.012 -0.010 -0.008 -0.006 -0.004 -0.002 0.000 0.002 0.004 0.006 0.008 0.010 0.012 0.014 0.016 0.018 0.020 0.022 0.024 0.026 0.028 0.030 0.032 0.034 0.036 0.038 0.040 Pr(X = x) PDF (α=1)
In [8]:
plot_parallel_pareto_cdfs(1, parallel_results)
Out[8]:
Latency 10-10 10-8 10-6 10-4 10-2 100 102 104 106 108 1010 1012 1014 1016 1018 10-8.0 10-7.5 10-7.0 10-6.5 10-6.0 10-5.5 10-5.0 10-4.5 10-4.0 10-3.5 10-3.0 10-2.5 10