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

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

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.

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]:

In [4]:

```
plot_pareto_cdfs(pareto_results)
```

Out[4]:

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]:

In [8]:

```
plot_parallel_pareto_cdfs(1, parallel_results)
```

Out[8]: