►
From YouTube: Queueing Theory, In Practice: Performance Modelling in Cloud-Native Territory [I] - Eben Freeman
Description
Queueing Theory, In Practice: Performance Modelling in Cloud-Native Territory [I] - Eben Freeman, Honeycomb.io
Kubernetes and similar cloud-native infrastructure make it easier than ever to adjust a service's capacity based on variable demand. In practice, it's still hard to take observed metrics, and translate them into quantitative predictions about what will happen to service performance as load changes. Resource limits are often chosen by guesstimation, and teams are likely to find themselves reacting to slowdowns and bottlenecks, rather than anticipating them.
Queueing theory can help, by treating large-scale software systems as mathematical models. But it's not easy to translate between real-world systems and textbook models. This talk will cover practical techniques for turning operational data into actionable predictions. We'll show how to use results from queueing theory to develop a model of system performance. We'll discuss what data to gather in production to better inform its predictions -- for example, why it's important to capture the shape of a latency distribution, and not just a few percentiles. We'll also talk about some of the limitations and pitfalls of performance modelling.
About Eben Freeman
Now largely reformed after stints studying theoretical math and living as an itinerant rock climber, Eben is fascinated by tools that help humans better understand the systems they create. He works as an engineer at Honeycomb.io.
Join us for KubeCon + CloudNativeCon in Barcelona May 20 - 23, Shanghai June 24 - 26, and San Diego November 18 - 21! Learn more at https://kubecon.io. The conference features presentations from developers and end users of Kubernetes, Prometheus, Envoy and all of the other CNCF-hosted projects.
A
My
name
is
eben
and
in
my
day,
job
I
build
a
lot
of
cool
stuff
at
this
company
called
honeycomb
I/o
and
I'd
be
happy
to
talk
to
you
later
about
tracing
events
observability
for
distributed
systems,
some
of
the
stuff
we
did
here,
but
that's
not
what
we're
here
to
talk
about
today.
Instead
we're
here
to
talk
about
queuing
theory
now,
I
feel
like
like
a
lot
of
things
in
computer
science.
Queueing
theory
has
kind
of
a
naming
problem.
A
I,
don't
know
about
you,
but
I'm,
not
really
big,
on
queueing
waiting
around
in
lines
and
I'm,
not
too
enthusiastic
about
theory
either
unless
it
has
some
useful
application
for
what
I
do.
But
the
truth
is
the
queueing
theory
is
all
about
asking
and
then
answering
questions
that
we
have
as
system
operators.
It's
common
to
have
these
questions
that
are
relatively
difficult
to
answer.
A
You
know
if
we
have
something
that
we
scale
in
kubernetes
or
whatever
what
level
of
utilization
is
appropriate.
If
we
want
to
make
changes,
what
changes
should
we
make
to
improve
performance
and,
if
we're
not
willing
to
accept
just
pure
guesswork
as
an
answer,
then
queueing
theory
gives
us
both
the
vocabulary
and
the
toolkit
a
set
of
results,
theorems
developed
and
presented
by
some
really
smart
people
to
help
us
approximate
the
software
systems
that
we
build
with
simpler
models
that
we
can
either
reason
about
mentally
or
analyze.
A
Then
I
want
to
extend
that
to
talking
about
parallel
systems,
how
you
can
reason
about
load
strategies
and
how
you
can
use
something
called
the
universal
scalability
law
to
predict
how
your
system
will
scale
as
your
traffic
or
your
capacity
grows,
and
finally,
will
summarize
some
of
the
things
that
we
see
along
the
way
and
some
key
takeaways.
So
what
before
we
dive
in
an
important
and
essential
caveat,
any
model
is,
by
definition
a
flawed
representation
of
reality.
It
is
reductive,
otherwise
it
wouldn't
be
a
model,
it's
also
worthless,
unless
backed
by
real
data.
A
However,
if
you
do
get
gather
data
having
some
sort
of
model
helps
you
make
sense
of
it
instead
of
drowning
in
metrics.
You
can
ask
useful
questions
and
validate
your
assumptions.
If
your
service
has
some
sort
of
performance
bottleneck,
perhaps
you
can
identify
that
bottleneck
before
you
actually
hit
it
and
cause
an
outage.
If
you
want
to
create
a
benchmark,
you
can
use
queueing
theory
to
decide
whether
that
benchmark
is
a
plausible
representation
of
some
different
real-world
workload.
A
And
finally,
if
you're
planning
changes
that
might
be
expensive
to
make
re
architecture
is
something
you
can
use
queuing
theoretic
results
to
help
decide
whether
those
are
good
changes
or
not
what
their
effects
are
likely
to
be.
So,
let's
dive
in
by
talking
about
serial
systems
to
motivate
this
section,
I
want
to
talk
about
one
of
the
services
that
we
operate
at
honeycomb,
our
ingestion
API.
The
details
of
this
thing
aren't
too
important,
but
it
looks
like
a
lot
of
services
that
you
are
probably
familiar
with,
or
perhaps
you
run
yourself
it's
user
facing.
A
In
our
case
it
receives
ingestion
data
from
customer
infrastructure
kind
of
a
lot
of
data.
It's
stateless,
highly
concurrent
runs
across
many
servers.
It's
mostly
CPU
balanced
and
it's
supposed
to
be
low
latency,
which
for
us
means
target
Layton
sees
in
the
single-digit,
know
second
range
at
worse,
so
we
couldn't
really
run
this
thing
on
ec2.
We
could
run
it
as
a
stateless
service
on
kubernetes
as
well,
either
way.
That
means
that
we
could,
in
principle,
allocate
more
or
less
infinite
resources
to
this
thing.
Unfortunately,
that
would
also
cost
more
or
less
infinite
money.
A
Sir
question
is:
how
do
we
allocate
appropriate
resources
to
this
service?
How
do
we
provide
high
performance
at
a
reasonable
price
point?
There
are
a
couple
of
ways
that
we
could
approach
this
problem.
We
could
guess,
but
that
would
make
for
a
pretty
short
talk.
We
could
do
large-scale
production
scale.
Load
testing
either
generate
enormous
amounts
of
traffic
against
a
real
infrastructure
or
create
a
full-scale
copy
of
a
real
infrastructure
and
generate
enormous
amounts
of
traffic.
A
Against
that,
this
is
obviously
a
pretty
good
idea
like
it
would
be
a
worthy
undertaking,
but
it's
also
a
time
consuming
thing
for
a
resource
constrained
engineering
team
to
do
rigorously
so
I
want
to
explore
a
different
strategy.
We'll
do
some
small
experiments,
things
that
you
can
do
with
a
few
instances
with
limited
time
and
then
build
a
performance
model
that
will
help
us
take
the
results
of
our
experiments
and
reason
about
what
they
imply
for
our
production
system
makes
sense.
A
So
here's
the
idea
we
have
n
cores
available
to
run
this
thing.
We
know
it's
more
or
less
CPU
bounds
and
is
some
large
number.
But
what
can
we
do
with
just
one
core?
What's
the
maximal
single
core
throughput
of
this
service
to
answer
that
question?
Will
simulate
requests
arriving
uniformly
at
random
kind
of
like
the
requests
that
we
see
in
the
wild
and
we're
metal
and
we'll
measure
the
observed
latency
at
different
levels
of
throughput?
So
here's
what
this
looks
like
initially
we're
doing
pretty
good.
A
You
know
single-digit
millisecond
latency,
a
couple
thousand
requests
per
second
and
then
at
some
point
things
start
to
go
really
south.
So
that's
obviously
not
good
our
question.
Can
we
find
a
model
that
predicts
this
behavior
that
helps
us
identify
this
knee
and
the
response
time
curve
before
we
actually
hit
it?
That
will
then
let
us
extrapolate
from
production
data
to
say.
Okay,
this
is
the
maximum
safety
utilization
for
the
service.
A
Here's
the
idea,
because
we've
constrained
ourselves
to
a
single
core,
we're
going
to
use
a
single
Q
single
server
model.
So
we'll
say
we
just
have
a
server
which
is
some
sort
of
black
box
that
processes
tasks.
Tasks
arrived
independently.
If
the
server
is
busy,
those
tasks
might
have
to
wait
until
the
server
can
actually
work
on
them.
Do
its
data
processing
or
whatever.
Finally,
the
server
gets
to
the
task.
It
does
some
work.
It
returns
to
the
client
so.
A
Intuitively,
it's
pretty
clear
that
in
this
model
the
busier
the
service
is
the
longer
tasks
will
probably
have
to
wait
before
they
can
be
completed
kind
of
like
what
we
saw
in
the
picture.
The
busier
the
server
was,
the
greater
the
latency
was
and
our
question
as
well
as
a
function
of
throughput,
exactly
how
much
longer
so
that's
the
question
here
are
the
assumptions
we're
making
first,
we've
forgotten
completely
about
the
Linux
kernel.
A
A
First,
the
tests
arrive
independently
and
randomly
it's
some
average
rate
that
we'll
call
lambda,
say:
lambda
equals
3,000
requests
per
second
and
second,
that
the
server
takes
a
constant
time
as
the
service
time
say:
200
microseconds
to
actually
process
each
task
later,
we'll
revisit
these
assumptions
and
see
what
happens
when
we
relax
them
and
finally,
like
we've
said,
the
server
can
only
do
one
thing
at
once
and
it
doesn't
preempt
once
it
starts
a
task.
It
has
to
finish
it
so
step
3.
A
You
all
have
sets
phd's
right,
just
kidding
to
build
up
our
intuition
for
this
system.
Let's
draw
ourselves
a
picture
of
how
its
state
evolves
over
time.
The
state
of
the
server
changes
when
a
task
arrives.
The
server
goes
from
idle
to
busy
the
outstanding
work
at
the
server
goes
from
zero
to
s.
Then
the
server
works
on
the
task.
A
other
outstanding
work
goes
down.
Then
the
server
is
idle
again.
Another
task
arrives.
A
That's
the
same
thing
happens
now
intuitively
it's
pretty
clear
that
when
throughput
is
low,
the
server
is
mostly
idle
and
tasks
almost
never
have
to
queue
in
general.
They
can
be
served
immediately
and
latency
will
be
low.
However,
as
throughput
increases,
the
server
is
busy
more
of
the
time
and
it's
more
likely.
The
tasks
will
have
to
wait
in
this
diagram.
Let's
try
and
distinguish
the
waiting
time
for
a
task
which
is
blue
here
from
the
service
time
for
a
task
which
is
orange
here.
The
test
shows
up.
A
So
I'm
that
this
picture
can
we
talk
about
the
metric
that
we're
interested
in,
which
is
average
wait
time,
not
just
for
a
given
arbitrary
test,
but
in
general
over
a
large
set
of
tasks.
How
long
will
they
have
to
wait?
There
are
two
ways
that
we
can
identify
the
average
wait
time
in
this
picture.
The
first
is
the
average
weight
of
these
blue
parallelograms.
A
The
average
time
between
when
a
tasks
arrives
and
when
it's
ready
to
be
serviced
makes
sense,
but
the
other
way
that
we
can
identify
average
wait
time
is,
is
the
average
height
of
the
graph?
Remember
tests
arrive
independently
and
uniformly
at
random.
So
if
we
were
task-
and
we
show
up
at
some
random
point
in
time
right
here-
the
height
of
the
graph
at
that
point
represents
how
long
we'd
have
to
wait.
So
the
average
height
represents
the
average
wait
time.
A
If
this
is
giving
you
like
bad
high
school
geometry,
flashbacks
that's
Philly
fare,
but
bear
with
me,
because
there
will
be
some
cool
insight
at
the
end
of
this
little
exercise.
The
idea
is
that
will
relate
the
average
width
and
the
average
height
using
the
area
under
the
graph
and
then
solve
to
give
us
an
expression,
a
formula
for
the
wait
time
that
we
can
then
use
to
make
predictions.
So
over
a
long
time,
interval
T
the
area
under
the
graph
is
the
width.
A
The
time
span
T
times
the
average
height
of
the
graph,
which
we
already
said
was
the
average
wait
time.
Let's
call
that
W,
so
the
area
is
T
times
W.
On
the
other
hand,
we
have
all
these
tests
that
are
represented
both
by
a
triangle
in
this
diagram,
the
orange
triangle
representing
when
it's
being
serviced
and
a
parallelogram,
the
blue
parallelogram,
that's
representing
when
the
task
is
waiting.
A
Now
how
many
tests
are
there?
Well
over
sometimes
Fanty?
The
number
of
tests
is
a
function
of
the
arrival
rate
called
lambda,
so
putting
it
all
together,
we
have
this
kind
of
gnarly
expression
that
will
make
a
lot
more
sense
in
a
minute.
We
know
that
the
area
under
the
graph
is
lambda
t
s
squared
over
2,
plus
s
times
W,
which
we
also
know
is
the
area
under
the
graph
t
times
W.
A
This
is
great
because
we
can
relate
the
two
and
then
solve
for
W.
You
might
have
to
trust
me
on
two
algebraic
manipulation
here,
but
if
you
simplify
the
top
equation,
what
you
get
is
this
expression:
W
is
equal
to
lambda
s,
squared
over
2
times,
1
minus
lambda
s,
let's
bust
out
our
graphing
calculators
and
draw
a
picture
of
what
this
looks
like.
This
is
what
it
looks
like
as
the
server
becomes
saturated
as
the
throughput
lambda
grows.
The
wait
time
also
grows
without
bound.
A
This
looks
a
lot
like
the
picture
that
we
saw
in
our
experiment,
and
so
this
is
encouraging,
even
without
actually
fitting
this
to
the
data
that
we
gathered,
we
can
identify
three
utilization
regimes.
You
know
when
utilization
is
pretty
low,
there's
no
problem.
If
someone
comes
along
and
says
hey,
AB
and
I
think
we
should
run
this
thing
at
like
60
percent
utilization.
Instead,
that's
a
conversation
that
we
can
have
about
cost
of
performance
trade-offs.
If
someone
says
hey,
we
should
run
this
thing
at
90
percent
utilization.
A
That's
probably
a
bad
idea,
so
even
this
relatively
crude
model
gives
us
some
pretty
good
insights,
for
example,
if
we're
choosing
resource
limits
for
our
pods
there's
a
big
difference
between
going
from
a
little
bit
of
utilization
to
a
little
bit
more
utilization
when
your
utilization
is
low
and
growing
from
utilization
to
a
little
bit
more
utilization
when
your
utilization
is
high,
the
ladder
is
very,
very
bad,
so
this
is
great,
but
so
far
we've
just
been
theorizing.
We
don't
actually
know
that
this
model
correctly
describes
the
data
that
we
saw
in
practice.
A
I
mean
it
kind
of
looks
like
the
same
shape
same
shape
of
graph,
but
you
know:
is
it
good
or
is
it
just
some
that
we
made
up?
Well,
there's
a
way
to
assess
this
crudely?
Here's
what
we
can
do
we'll
choose
a
subset
of
our
real
data
and
the
subset.
Will
that
we'll
choose
is
the
data
that
we're
actually
likely
to
get
from
production
data
from
the
safe
regime.
The
low
utilization
regime
then
will
fit
our
model
to
those
data
points.
Well,
I
won't
go
into
the
tedious
details
of
how
you
would
do
this.
A
It's
pretty
simple
to
do
with
any
sort
of
statistical
software
package
like
R
or
numpy,
and
finally
we'll
compare
that
to
the
data
points
that
we've
withheld
from
our
training
set.
If
you
will-
and
so
in
this
case
the
fit
is
actually
strikingly
good.
So
this
is
encouraging.
It
means
that
we've
made
some
radical
assumptions,
but
still
come
up
with
a
parametric
model
that
pretty
well
describes
their
real
system
awesome.
A
There
are
some
bigger
lessons
that
we
can
take
away
from
this
model.
First,
in
this
type
of
system
and
really
in
any
type
of
system.
Improving
baseline
service
time
helps
a
lot
if
you
have
a
service,
and
you
find
some
sort
of
performance,
optimization
that
there's
just
straight-up
makes
it
faster.
That
is
the
most
impactful
thing
you
can
do.
Let's
see
why
that
is
here's
the
thought
experiment.
We
find
some
optimization
that
cuts
the
average
service
time
in
half
and
people
love
our
service,
because
it's
super
fast.
A
So
now
our
throughput
doubles
because
we
have
more
users.
What
happens
to
the
wait
time
using
our
equation.
We
can
see
what
happens
because
there's
a
factor
of
s
squared
in
the
numerator
of
this
equation.
The
numerator
is
twice
as
small.
On
the
other
hand,
the
changes
in
the
denominator
here
cancel
each
other
out,
so
the
denominator
stays
the
same.
What
does
that
mean?
Even
after
we
double
throughput,
the
wait
time
is
still
improved.
This
is
kind
of
awesome
right.
A
If
we
find
some
optimization
that
lets
us
cut
service
time,
a
half,
we
can
double
throughput
and
still
be
faster
than
we
were
before.
Alternatively,
we
can
more
than
double
throughput,
almost
triple
throughput
in
this
case
and
get
the
same
performance
that
we
had
before
to
me.
This
is
really
counterintuitive
and
really
compelling.
It
says
that
improving
baseline
service
time
doesn't
just
improve
user-facing
latency.
It
also
improves
our
own
capacity
to
handle
many
concurrent
requests.
So
this
is
a
powerful
thing
to
remember.
Investing
in
straight-up
performance
optimization
is
maybe
the
best
use
of
your
time.
A
The
second
lesson
is
that
variability
is
bad.
Remember
our
tests
were
arriving
at
random,
but
if
they
just
showed
up
at
perfectly
spaced
intervals,
every
200,
microseconds
or
something
would
never
have
to
wait,
even
if
the
server
is
highly
utilized.
Unfortunately,
that's
not
what
happens
in
reality,
so
the
slowdown
that
we
see
is
because
our
rivals
are
variable.
A
Similarly,
we
can
show
that
if
job
sizes
are
also
variable,
things
get
even
worse.
Here's
a
little
empirical
experiment.
We
choose
two
distributions
of
task
sizes,
one
the
green
distribution
is
all
jobs
are
the
same
size.
The
model
we
started
with
the
other.
The
average
is
the
same,
but
we
choose
from
a
long
tail
distribution.
So
job
sizes
are
variable.
A
You
can
run
through
a
sort
of
similar
geometric
argument
and
see
that
when
task
sizes
are
variable,
wait
time
is
even
worse
than
when
task
sizes
are
constant.
So
this
again
is
a
powerful
lesson
for
us
as
system
designers
and
operators.
It
means
that
it
behooves
us
first
to
measure
the
variability
in
our
tasks.
Using
you
know,
instrumentation
techniques
like
histograms
heat
maps,
distributed
tracing
for
outline
eye
analysis
and,
secondly,
to
minimize
variability
using
design
strategies
like
batching.
The
variability
of
a
batch
of
requests
will
always
be
less
than
the
variability
of
their
requests
taken.
A
Singly,
so
batching
helps
reduce
variability.
Similarly
aggressively
pre-empting
slow
tasks
or
applying
time
outs
can
help
reduce
the
impact
of
outlier
tasks
on
the
tests
that
queue
up
behind
it
and
finally,
client
back
pressure
and
currency
can
concurrency
control
help
limit
variability
in
arrival
rates
in
a
non-trivial
system.
A
So
this
is
great.
We've
learned
some
stuff,
but
we
don't
actually
just
have
one
core
or
one
server.
We
have
lots
and
lots.
So
what
can
you
say
about
the
performance
of
our
big
old
fleet
of
servers?
That's
what
I
want
to
talk
about
a
bit
in
the
second
half
of
this
talk
parallel
systems.
So
if
we
know
now
that
one
server
can
handle
T
requests
per
second
subject
to
one
of
our
latency
SLA
s,
do
we
need
n
servers
to
handle
n
times
T
requests
per
second?
A
Well,
it
depends
on
how
we
assign
tasks
to
servers
right.
There
are
lots
of
different
ways.
We
could
do
that.
We
could
always
assign
tasks
to
the
least
busy
server.
We
could
assign
tasks
randomly
and
round
robin
fashion
or
some
other
way.
We
could
always
assign
tasks
so
the
most
busy
server,
but
that's
probably
a
bad
idea
intuitively
it
depends
so
let's
do
a
little
simulation.
This
is
another
performance,
modeling
technique
that
I
find
pretty
compelling.
A
If
you
don't
know
how
to
reason,
analytically
about
something,
you
can
write
a
little
simulation
about
it,
like
I,
cooked
up
some
code
for
this,
you
could
do
it
too.
Here's
the
idea,
we're
going
to
simulate
N
equals,
say
16
servers
and
tasks
arriving
independently
at
randomly
and
then
when
a
new
test
shows
up,
we'll
assign
it
randomly
to
a
server
wait
until
the
server
finishes
it
and
then
measure
the
cumulative
latency
distribution
over
this
workload.
A
So
sometimes
because
we're
assigning
random
way,
a
bunch
of
tests
all
arrive
at
the
same
servers
and
then
at
the
same
server,
and
then
those
tasks
have
to
wait
and
so
there's
a
latency
tail.
On
the
other
hand,
if
we
take
the
same
workload
but
as
scientists
optimally
always
choose
the
least
busy
server,
then
it's
much
less
likely
that
a
task
will
have
to
wait.
A
A
We
can
reinforce
this
with
a
bit
of
a
probabilistic
argument.
If
we
have
one
utilization,
it's
a
one
server
at
some
utilization
row.
So
it's
busy
sixty
percent
of
the
time
and
a
new
task
shows
up
then
the
probability
that
the
new
test
will
have
to
wait
is
the
utilization
row,
sixty
percent,
but
if
we
have
n
servers
at
the
same
utilization,
rail
and
a
new
task
shows
up
the
probability
that
the
new
task
will
have
to
wait
is
the
probability
that
all
servers
are
busy
simultaneously,
which
is
much
less
than
row.
A
What
this
means
is
that,
in
theory,
if
we
have
many
servers,
higher
utilization
gives
us
the
same
queueing
probability.
If
we
have
n
times
more
traffic,
we'll
need
fewer
than
n
times
more
servers.
This
is
awesome
right.
It's
like
economies
of
scale
and
not
just
because
of
vendor
economies
of
scale,
but
because
of
actual
physical
improvement
and
the
efficiency
of
the
system.
This
is
great,
like
the
more
the
more
people
use
our
service,
the
cheaper.
It
is
to
run
awesome.
A
There's
just
one
problem
with
this
argument:
we're
assuming
that
we
can
optimally
assign
tasks
to
servers,
but
optimally
assigning
tasks
to
a
pool
of
servers
is
really
a
coordination
problem
disguise
we
all
have
to
agree
on
which
server
gets,
which
task
and
in
real
life
coordination
is
expensive.
There's
no
way
around
it.
We
can't
just
magically
pick
the
least
busy
server
with
our
psychic
powers
in
general.
We
need
some
sort
of
physical
coordination
mechanism
for
this
problem
of
stateless
request
assignment.
A
A
A
If
it
takes
us
some
constant
time
alpha
to
assign
a
task
say
just
the
time
it
takes
to
forward
it
from
the
load
balancer
to
the
backends,
and
we
have
n
tasks
to
process,
then
the
time
it
takes
us
overall
to
process
n
tasks
in
parallel
is
the
assignment
time,
which
is
alpha
times
n,
because
you
have
to
do
this
assignment
more
or
less
serially,
plus
the
service
time,
which
is
s.
The
throughput
here
is
a
number
of
tasks
n
divided
by
the
total
time.
As
a
graph.
A
This
looks
like
this
as
we
try
to
scale
our
throughput
scales
sub
linearly.
We
spend
more
and
more
of
our
time
just
assigning
tasks
to
servers
and
less
and
less
of
our
time
actually
working
on
the
tasks.
So
this
is
rough
and
if
you
can't
just
assign
tasks
in
constant
time,
if
we
have
to
do
something
that
depends
on
the
number
of
servers,
for
example,
go
talk
to
each
one
of
them
and
turn
and
figure
out
which
one
is
best.
Then
it's
even
grimmer
if
the
assignment
tests
grow.
A
This
is
one
example
of
what's
called
the
universal
scalability
law
in
action.
The
universal
scalability
law
says
that
the
scalability
of
more
or
less
any
parallel
computing
process
looks
like
this
graph.
You
find
parameters
alpha
that
describe
the
constant
assignment
cost
and
beta
that
describe
the
coordination
cost
and
can
model
the
scalability
using
this
equation.
Unless
you
can
find
ways
to
minimize
a
coordination
cross
costs
as
you
try
to
scale
your
system,
it
will
actually
perform
worse
and
worse.
So
this
is
pretty
rough
right.
A
A
So
what
we've
learned
from
this
is
that
making
scale
and
variant
design
decisions
is
really
hard
at
low.
Parallelism
is
better
for
us
to
try
and
coordinate,
because
it
makes
latency
more
predictable,
but
at
high
parallelism
coordination,
degrades
throughput
and
we're
better
off
just
assigning
things
randomly
otherwise,
we'll
spend
all
of
our
time
making
choices
and
none
of
our
time
actually
working
on
them.
A
A
So
here
are
two
pretty
neat
ideas
for
how
to
do
that.
The
first
we
do
it
approximately.
We
know
that
finding
the
very
best
out
of
n
servers
is
an
expensive
proposition,
but
choosing
one
randomly
is
kind
of
bad.
So
here's
the
idea
we'll
make
a
trade-off.
We'll
pick
two
at
random,
we'll
compare
those
two
and
then
we'll
always
choose
the
better
one
of
those
two.
A
A
This
is
not
just
like
some
theoretical
thing
that
someone
made
up
this
technique
is
used
in
the
sparrow
research
schedule,
scheduler
and
also
implemented
in
hedgy
Corpse
Nomad,
to
do
distributed
stateless
scheduling
with
low
latency
for
lots
of
short
tasks
like
cron
jobs
and
stuff.
It
uses
this
to
two
random
choices,
assignment
plus
some
optimizations
and
I,
really
like
this,
because
it's
a
relatively
straightforward,
very
effective
strategy.
A
A
The
second
idea
for
beating
this
quadratic
beta
penalty
I
call
iterative
partitioning
and
it
illustrates
how
the
universal
scalability
law
applies
not
just
to
this
problem
of
task
assignment,
but
to
any
parallel
process.
Here.
We're
going
to
talk
not
about
stateless
services,
but
about
stateful
services.
This
idea,
as
far
as
I
know,
was
invented
at
Facebook
to
empower
this
analytic
system
called
scuba
and
is
reincarnated
in
fashion
at
honeycomb,
where
I
work.
The
idea
is,
you
have
a
lot
of
analytical
data,
instrumentation
data
from
systems,
and
you
want
to
answer
questions
about
it
pretty
quickly.
A
You
know
which
requests
are
slow
or
how
is
my
site
performance
changing
over
time
and
the
way
you
do
that
is
by
distributing
your
query
over
lots
of
storage
nodes.
So
we
have
a
bunch
of
data.
We
have
a
bunch
of
storage
nodes.
Each
node
is
responsible
for
some
slice
of
the
data
and
we
want
to
answer
a
query
so
say
you
know
which
of
our
requests
was
slowest
over
the
past
week
or
something
all
of
the
nodes
participate
in
figuring
out
the
answer
to
that
query.
A
In
parallel,
so
first
leaf
nodes
read
a
different
disk
compute,
their
partial
results.
Here's
my
slow
score!
Here's
my
slowest
query,
here's
my
slowest
query
and
then
the
aggregator
node
merges
those
partial
results
together
and
returns
a
results
of
the
client.
It's
sort
of
like
a
MapReduce
like
thing,
and
so
we
can
choose
the
level
of
fan-out.
Here
again
we
can
distribute
the
data
across
lots
and
lots
and
lots
of
service
servers,
and
our
question
is
what
level
of
fan-out
is
optimal.
A
The
reason
that's
a
worthwhile
question
to
ask
is
because
there
are
two
parts
to
the
time
it
actually
takes
to
serve
a
query
with
this
distributed
query
system.
First,
there's
the
scan
time,
the
time
it
takes
for
each
leaf,
node
to
read
its
data
off
of
disk
and
figure
out
its
partial
result
and
then
there's
an
aggregation
time.
The
time
it
takes
to
merge
all
those
results
together.
A
The
scan
time
is
proportional
to
the
total
amount
of
data
divided
by
the
number
of
leaf
nodes
that
we
have
so
the
more
leaf
nodes
we
have.
The
better.
The
scan
time
is
the
less
work
each
leaf.
Node
has
to
do,
but
the
aggregation
time
is
proportional
to
the
number
of
partial
results.
So
the
more
leaf
nodes.
We
have
the
worse
the
aggregation
time
guess
putting
those
two
together
we
get
the
same
scalability
graph
that
we
saw
before
at
first.
A
As
we
add
more
nodes,
our
performance
improves
and
then,
as
we
add,
more
nodes,
our
performance
starts
to
degrade.
So
this
is
pretty
rough
right.
It
means
that
we
can't
scale
beyond
you
know
40
or
50
nodes
without
actually
regressing
performance,
which
is
a
tough
proposition.
If
you're
trying
to
be
I,
don't
know
a
web
scale
or
something
so
here's
the
idea,
instead
of
trying
to
do
all
the
aggregation
at
once,
we'll
do
it
iteratively
by
fanning
out
queries
across
multiple
levels.
A
We
know
that
the
throughput
gets
worse
for
a
very
large
fan-out,
so
we'll
make
the
fan-out
a
constant,
F
and
we'll
add
intermediate
aggregators
between
their
root
and
the
leaf
nodes.
Now
you
can
work
through
the
math
and
see
that
the
aggregation
time
is
no
longer
proportional
to
the
number
of
leaf
nodes.
It's
proportional
to
the
height
of
our
aggregation
tree,
which
is
proportional
to
the
log
of
the
total
number
of
servers
we
have
participating
in
this
system.
This
might
seem
a
little
abstract,
but
what
does
it
mean?
A
It
means
that
we,
as
we
add,
more
servers.
We
continue
to
scale
by
doing
this,
computation,
iteratively
and
aggregating
iteratively
we're
able
to
amortize
the
aggregation
costs
over
a
bunch
of
servers
and
continue
to
scale
even
to
very,
very
large
data
sets.
So
what
have
we
learned
again?
Making
scale
invariant
design
decisions
is
really
hard
because
performance
characteristics
at
low
scale
and
at
high
scale
are
very
different,
but
with
smart
compromises
we
can
produce
pretty
darn
good
results
with
randomized
choice.
We
can
approximate
optimal
assignment
very
cheaply
with
iterative
parallelization.
A
We
can
amortize
coordination
cost
across
more
of
our
service
and
the
universal
scalability
line.
Both
cases
helped
us
quantify
the
effect
of
these
choices
and
figure
out
how
to
design
better
systems
before
actually
building
them.
In
conclusion,
queueing
theory,
not
so
bad
model
building,
isn't
some
magic
thing
done
by
Wizards
with
PhDs.
All
you
have
to
do
is
state
your
goals,
state
the
assumptions
about
the
system,
you're
making
and
don't
be
afraid
you
can
bust
out
a
textbook
and
do
a
bunch
of
math.
But
you
can
also
draw
a
picture
to
reason
about
the
system.