►
From YouTube: LeitMotif: An Abstraction for Debugging Distributed Applications - Mania Abdi, Northeastern U
Description
Join us for Kubernetes Forums Bengaluru and Delhi - learn more at kubecon.io
Don't miss KubeCon + CloudNativeCon 2020 events in Amsterdam March 30 - April 2, Shanghai July 28-30 and Boston November 17-20! Learn more at kubecon.io. The conference features presentations from developers and end users of Kubernetes, Prometheus, Envoy, and all of the other CNCF-hosted projects
LeitMotif: An Abstraction for Debugging Distributed Applications - Mania Abdi, Northeastern University
Abstractions, such as APIs, allow developers to build complex distributed applications out of smaller building blocks. In contrast, there are very few abstractions available to limit the amount of complexity engineers must deal with when diagnosing problems in production applications. This mismatch means that diagnosis will continue to become more challenging as systems continue to scale. We present the workflow motif abstraction, instantiations of which capture frequent or important processing patterns observed in the workflow of requests. We argue that use of motifs can make existing diagnosis techniques more powerful and enable new use cases. We discuss features needed from distributed tracing infrastructures to generate useful motifs, progress on modifying frequent-subgraph mining algorithms to identify motifs from traces, and initial experiences using motifs to debug problems.
A
So
hello,
everyone,
my
name,
is
Manya
and
I
am
PhD
student
at
Northeastern.
Today,
I'm
talking
about
my
teases
project,
workflow
motif
an
abstraction
for
building
distributed
systems.
This
is
a
joint
work
with
my
advisers
at
Northeastern
and
tops,
and
our
collaborators
at
Boston
University,
Red,
Hat
and
Status
Street
I.
A
Want
to
start
the
talk
with
contrasting
how
we
build
this
complex
distributed
systems
versus
how
we
debug
them
today
distributed
systems
are
amazingly
large-scale
and
complex,
and
the
way
we
are
building
this
complex,
distributed
systems
by
leveraging
abstractions
abstractions
are
the
fundamental
building
blocks
of
the
distributed
systems
that
let
developers
build
complex,
distributed
applications
what
they
do.
They
mitigate
the
amount
of
complexity
that
developers
has
to
deal
with.
They
allow
developers
to
build
these
really
complex,
distributed
applications
from
simpler
building
blocks
that
provide
specific
functionality,
while
hiding
the
details
of
the
building.
A
Those
building
blocks
example
of
abstractions
include
a
POS
that
allows
distributed
systems
to
build
out
of
other
distributed
applications
such
as
leader
election
in
consensus
protocols
or
libraries,
which
provide
commonly
used
codes.
Another
abstraction
is
the
clean
separation
of
different
layers
in
data
centers.
That,
for
example,
allows
for
separated
stacked
layers
of
network
networking,
virtualization
and
application.
This
allows
developers
to
write
codes
for
upper
layer
applications
while
they
don't
care
about
what
is
happening
underneath.
A
In
contrast,
when
the
debug
distributed
system,
typically,
we
use
less
abstraction.
We
use
less
sophisticated
abstraction.
In
fact,
the
de-facto
approach
to
debug
these
systems
is
to
use
no
abstraction.
We
use
receive
use
user,
like
views
user
like
or
we
might
look
at
the
raw
logs
such
as
these,
such
as
these
graphs
that
I
show
that
I've
shown
here
and
which
shows
the
activities
in
the
system
and
shows
how
the
system
is
processed
by
the
how
the
requests
are
processed
by
the
distributed
system.
A
What
we
have
observed
in
the
tracers
show
that
there
are
repetitive
patterns
within
and
across
many
traces,
and
these
patterns
are
repetitive
building
blocks
of
how
distributed
systems
behave.
We
believe
that
understanding
the
performance
of
these
patterns,
how
they
differ
from
engineer
how
they
differs
from
engineers,
perspectives
and
how
they
combine,
combine
to
process
request.
Workflow
will
inform
a
wide
range
of
diagnosis
tasks
in
this
world.
We
are
exploring
the
utility
of
extracting
these
repetitive
patterns
to
build
a
novel
abstraction
for
distributed
network
diagnosis,
distributed
applications
called
workflow
motif.
A
A
We
largely
make
up
how
requests
are
processed
example
of
recurrent
patterns,
may
include
the
work
done
in
consensus
protocols
or
the
work
done
for
tearaway
replication
in
a
storage
systems
and
how
workflow
motives
help
diagnosis
is
by
hiding
the
complexity
during
diagnosis,
by
allowing
distributed
systems
to
understood
in
terms
of
their
building
blocks,
instead
of
in
terms
of
very
specific
and
detailed
behavior.
I
want
to
explain
the
features
of
workflow
motif
with
an
example.
A
Here
is
a
simplified
write,
request
in
a
distributed
storage
system,
and
this
workflow
consists
of
the
world
in
both
client-side
and
the
storage
annoyed
note.
Workflow
motives
are
frequent
processing
patterns
across
and
within
different
requests.
So,
for
example,
in
this
graph
motif,
one
represent
the
work
done
for
reading
metadata
from
metadata
server
and
the
motive
to
represent
the
work
done
for
TV
replication
right
also
word
follow
motives
are
hierarchical
and
composable
means
that
a
large
motif
can
be
composed
of
smaller
motives.
This
allows
larger
motives
to
hide
complexity
of
a
smaller
motives.
A
A
The
key
enabler
for
building
workflow
motive
is
end-to-end
tracing
or
workflow
centric
tracing,
and
here
is
the
basic
explanation
of
how
workflow
centric
tracing
work.
This
figure
shows
the
deployment
of
a
distributed
storage
that
keeps
the
data
a
table
of
store
that
manage
the
data
representation,
an
application,
client
that
reads
the
data
or
writes
the
data
and
to
capture
the
request.
Both
flow
workflow
centric
infrastructure
used
trace
points
which
are
embedded
within
the
service
and
code
base.
A
Trace
points
are
just
like
logging
points
and
they
can
be
added
manually
or
they
can
be
instrumented
into
the
libraries
that
we
are
using,
or
even
they
can
be
added
during
the
runtime
example
of
Lola,
and
they
also
can
capture
the
low-level.
Behaviors
and
example
of
low-level
behaviors
is,
for
example,
super
CPU
utilization
or
the
queue
lengths
or,
for
example,
other
order
states
of
the
node.
So
when
a
user
start
execution,
the
tracing
infrastructure
propagates
a
contents
across
the
request
with
such
as,
for
example,
request
ID
or
span
ID,
and
then
it's
stitched
together.
A
A
Our
approach
to
build
a
workflow
motive
is
to
exploit
frequent
sub
graph
mining
algorithm,
and
these
algorithm
help
us
to
find
similar
patterns
within
and
across
traces
that
we
have.
They
also
count
for
the
number
of
occurrences
in
the
system,
so
this
algorithm
are
widely
used
in
the
world
of
biology
for
finding,
for
example,
DNA
matching
or
they
are
using
in
chemistry
community
for
detecting
similar
components
and
we
are
using
frequency
up.
A
They
are
mining
to
find
common
patterns
that
we
are
finding
in
the
execution
traces
and,
as
you
can
see
in
this
figure,
this
is
again
the
write,
a
part
of
the
write
request,
workflow
and,
as
you
can
see,
this
is
the
pattern
for
writing.
This
is
the
pipeline
pattern
for
writing
the
tree
barrier,
application
of
data
and
each
part
shows
the
write
requests
to
a
disk.
A
However,
this
application,
these
algorithms
are
expensive
and
we
think
that
by
applying
some
constraints
and
some
domain
knowledge,
we
can
make
them
simpler
and
make
them
applicable
and
through
the
diagnosis
tasks.
So
now,
with
an
example.
Let's
look.
How
workflow
motif
can
help
us
to
improve
the
debugging
experience.
Back
to
our
previous
example,
the
performance
team
engineer
wants
to
explore
how
the
system
works
and
what
is
the
performance
of
the
like
scan
from
a
table,
so
he
expects
his
command
to
be
processed
in
10
seconds.
A
However,
our
really
after
reading
the
data
he
figured
out
that
okay,
it
takes
50
seconds
instead
of
10
seconds,
so
he
decides
to
enable
instrumentation,
and
then
he
and
then
he
collects
traces.
So
after
that
he
runs
a
workflow
motif
and
the
workflow
motif
find
these
frequent
patterns
within
the
traces.
So
he
fought.
He
observed
that
the
Tabler
store
divides
his
requests
into
a
smaller
region
into
a
smaller
reads
and
then
read
them
sequentially,
instead
of
read
them
in
parallel.
A
So
he
observed
that
if
he
reads
the,
if
these
reads
were
issued
in
parallel,
he
could
get
a
better
performance
and
he
identified
this
as
an
optimization
point
and
send
his
observation
to
the
developer
team
for
optimization
or
performance
improvement.
And
here
is
their
software
components
and
operation
for
our
workflow
motif
framework
and
its
goal
is
to
run
alongside
the
distributed
application
and
mind
motifs
from
the
traces
of
request
workflow
and
make
these
motifs
available
to
diagnosis,
tools
and
engineers.
A
We
use
this
framework
to
measure
the
effectiveness
of
using
motifs
to
quickly
diagnose
the
problem
in
a
running
system.
The
workflow
centering
in
this
picture
of
figure,
the
workflow
centric
tracing,
captures
the
workflow
of
how
system
works
and
the
traces
for
us
and
then
they
are
stored
in
a
trace
database.
The
workflow
motif
Suites
traces
from
from
the
trace
database
and
builds
the
workflow
motives
from
them,
and
then
we
can
query
those
motives
or
we
can
annotate
the
traces
for
the
most
common
behavior.
A
Here
is
the
formal
definition
of
a
subgraph,
but
in
general,
a
frequent
subgraph
in
is
a
frequent
patterns
or
frequent
graphs.
That
happens
for
a
certain
amount
of
time
in
a
set
of
graphs
or
between
or
across
a
set
of
graphs.
And
here
we
build
on
the
standard
definition
of
a
frequent
sub
graph
in
order
to
fully
define
a
workflow
motive.
A
We
start
from
a
workflow
centric
tracing
trace,
T
and
then,
which
is
a
weighted
acyclic
graph,
and
each
vertices
in
the
trace
represent
a
trace
point
like
a
function
or
a
span
or
a
library
call
or
an
RPC,
and
as
representants
that
happens
before
relationship
between
these
trace
points,
the
edge
weights
indicates
the
latencies
between
successive
trace
points
and
a
single-layer
trace.
F
is
a
trace
created
by
a
slicing
that
traced
he
into
smaller
parts
and
so
even
a
set
of
single
layer
traces.
A
The
number
of
times
that
a
processing
pattern
P
occurs
within
all
the
traces
is,
is
called
Sigma
and
if
the
Sigma
is
larger
than
a
Terra
sholde,
we
identify
that
as
a
frequent
but
for
identify.
But,
unlike
the
frequent
pattern,
mining
algorithm
here
for
identifying
for
identifying
a
pattern
to
be
for
identifying
a
pattern
to
be
frequent,
we
don't
need
to
match
the
edge
to
the
edge
weights.
A
Our
definition
of
workflow
motive
is
similar
to
frequent
pattern.
Frequent
subgraph,
infrequent
pattern,
mining
tools
and
it
accounts
for
edge
direction
and
frequency
within
and
across
graphs
and
additionally
includes
performance
characteristics.
Our
definition
satisfy
the
definition
of
the
abstraction,
which
means
that
it
allows
us
to
how
to
hide.
The
complexity.
To
understand,
allows
us
to
understand
the
complexity
in
terms
of
simpler
building
blocks,
instead
of
detailed,
detailed
knowledge
and
now
I
want
to
discuss
that
the
requirements
we
have
from
the
work
flow
motive
to
build
the
frequent
to
build.
A
Such
Marroquin
processing
patterns
should
be
identified
as
separate
motive,
not
as
the
same
motive,
for
example,
in
this
figure,
shows
different
execution
order
of
a
read
request
and
a
write
request
in
safe
rado
SCADA,
which
is
a
distributed
storage
system,
and
this
could
happen
for
several
reason.
For
example,
the
first
reason
could
be
correct
execution
in
lower
stack
and
then
the
engineers
can
use
it
for
understanding
the
system
behavior.
The
second
one
could
be
just
an
implementation
bug
instead
of
having.
A
So
the
workflow
motif
should
be
able
to
identify
this
behavior
and
should
be
able
to
identify
this
behavior.
The
second
requirement
is
that
we
need
to
find
workflow
motifs
that
are
within
the
traces
and
across
traces.
For
example,
there
may
be
some
patterns
that
happens
across
many
many
traces,
but
does
not
happen
within
a
single
trace,
and
also
there
are
some
workflow
motifs
that
could
happen
within
a
single
trace
for
multiple
times.
A
A
Now
I
want
to
discuss
the
frequent
subgraph
mining
tools
that
we
are
exploring
for
building
the
workflow
motive.
One
of
the
first
tools
is
FS
j,
which
is
frequent,
subgraph
mining
tool
if
it
is
a
joint
based
model
which
means
that
it's
a
start
with
the
very
smallest
sub
graphs
and
then
it
tries
to
add
edges
and
build
frequent
sub
graphs
one
by
one.
So,
unfortunately,
this
tool
is
not
scalable,
it
also
does
not
have
the
edge
direction
and,
moreover,
it
doesn't
look
for
the
traces
within
the
graph.
A
It's
also
a
look
for
the
motifs
or
frequent
patterns
across
graphs,
although
it's
not
the
tool
that
we
like
to
use
because
it
doesn't
follow
our
requirement.
This
is
the
very
basic
tools
that
all
all
other
tools
are
kind
of
based
on
this
one.
The
second
tool
that
we
observed
was
Gaston
again.
Unfortunately,
it
only
runs
on
a
single
machine.
It
does
not
run
on
a
distributed
system,
and
so
it
is
not
a
scalable.
A
It
does
not
follow
the
edge
order
and
also
it
only
looks
for
frequent
patterns
across
races,
but
this
has
very,
very
interesting.
Behavior
and
the
algorithm
has
a
very
interest
in
behavior.
It
first
looks
for
frequent
passes
and
then
it
looks
for
frequent
trees
and
then
it
works
looks
for
frequent
graphs,
so
it
allows
it
to
find
first
less
complicated
patterns
and
then
build
on
more
complicated
patterns.
And,
interestingly,
this
is
the
behavior
that
adapts
very
well
to
the
nature
of
work
flow
traces.
A
A
We
also
look
at
arabesque,
which
is
a
distributed
graph
mining
framework,
and
it
follows
the
pattern
grows
like
like
FSG
it.
It
follows
a
pattern,
girls
solution
and
it
allows
for
finding
frequent
patterns
within
and
across
graphs.
However,
it
does
not
support
edge
direction
and
but
it
is
an
open
source
and
we
can
combine
these
approach
with
other
approaches
to
build
a
to
satisfy
our
requirement
and
the
last
approach
is
ASAP,
which
is
the
newest
one,
and
it
allows
for
sampling
for
finding
frequent
patterns
and
it,
but
it's
not
open
source.
A
So
our
approach
is
to
build
on
building
on
these
existing
frequent
patterns.
We
want
to
use
arabesque
which
were
wise,
distributed
graph
mining
for
us.
We
want
to
use
Graeme
to
provide
across
stories
and
with
interest
with
interest
patterns
and
also
allows
us
to
to
meet
our
age
Direction
requirement.
We
want
to
use
Gaston
to
be
used
to
be
able
to
start
from
less
complicated
patterns
and
then
make
a
more
complicated
one,
and
then
we
want
to
use-
or
we
want
to
adapt
the
ASAP
approach
to
be
able
to
support
sampling
for
less
overhead.
A
Here
is
a
preliminary
results
of
the
some
of
the
patterns
we
could
find
in
HDFS
traces.
We
captured
some
workflows
from
from
HDFS,
and
then
we
run
guests
on
one
of
the
tools
on
these
traces.
The
right
one
shows
how
a
read
blog,
how
a
read
blog
motives
look
like
and
the
left
one
shows
they
read
from
network
motif.
A
We
think
that
this
workflow
motive
is
really
a
powerful
tool
and
we
want
to
look
at
some
of
the
use
cases.
One
of
the
use
cases
could
be
compare
and
contrast.
Tracers.
For
example,
we
can
run
workflow
motif
under
traces,
find
the
frequent
patterns
and
then
chop
each
trace
into
its
frequent
patterns
and
then
compare
those
frequent
patterns
together
to
example,
find
the,
for
example,
find
their
performance
anomalies
or
to
find
the
structural
anomalies.
A
The
other
one
is
system
optimization
that,
for
example,
we
can
find
motifs
that
are
at
the
tail
latency
of
execution
and
then
report
those
for
optimization.
The
other
use
case
could
be
finding
a
structural
anomalies
anomalies
during
execution
by
finding
the
most
frequent
ones
and
then
filter
those
and
then
find
the
less
frequent
ones,
which
means
that
there
was
a
normally
in
the
system.
B
A
Currently,
we
are
using
traces
that
are
in
the
form
of
graphs
and
we
use
x-rays
traces,
but
before
using
x-rays,
traces,
we
play
it
with
traces
we
captured
from
a
year
and
then
from
the
traces
we
captured
from
jäger.
We
try
to
build
a
graph
execution
graph
and
run
on
those,
but
currently
we
are
using
x-rays.
D
A
Not
only,
for
example,
because
these
the
span
mother
is
also
hierarchical,
it
could
consist
of
a
very
small
portion
of
like
just
a
function
to
the
very,
very
large
one
like
that.
The
parent
that
the
roots
trace
is
just
the
overall
right
request,
for
example,
which
kind
of
maybe
thousand
or
even
more
than
that,
so
our
model
is
to
build
from
the
very
small
one
find
the
patterns
that
are
very
fine
granular
to
the
patterns
that
are
very
coarse-grained.