►
From YouTube: Distributed Consensus with Raft - CodeConf 2016
Description
Presented by John Feminella
Getting people to agree to things is sometimes hard. But implementing consensus with computers is harder. And distributed consensus with computers is really hard. How do we do it?
In this talk, we’ll explore one idea of how distributed consensus can work, which the authors call Raft, with several popular open-source implementations. Along the way, we’ll learn about why consensus is challenging, how Raft works in practice, and see a real live example of a system that depends on Raft.
About CodeConf
CodeConf improves the software community by providing a forum for thought-provoking talks and forging social connections. The fourth installment of the CodeConf series took place in Hollywood in 2016. This year's event focused on systems engineering projects, practices, and programs in the open source community.
For more information on this year's CodeConf, go to:
https://codeconf.com/
A
Hi
everyone
welcome
to
distributed
consensus
with
raft
or
can
John
describe
a
PhD
thesis
in
20
minutes
or
less,
let's
find
out
so
I'm
John
salmonella
I've
got
a
website.
There
is
also
a
Twitter
accounts
that
I
tweet
from.
If
you
would
reply
to
the
tweet
I,
just
posted
with
any
questions
you
have
I'd
be
more
than
happy
to
get
back
to
you
after
the
top
is
done
cool.
A
And
now
you
have
some
clients
and
agent,
that's
responsible
for
making
requests
that
store
values,
and
you
want
to
put
state
value
into
the
node
later
you'd
like
to
be
able
to
read
a
value,
and
you
want
that
value
to
be
the
same,
one
that
you
put
into
it
right,
because
otherwise,
if
you
can
put
one
value
in
and
get
a
different
value
out,
what's
the
point
of
storing
that.
So
if
we
have
a
system
that
does
that,
that
seems
pretty
easy
right.
A
If
we
can
put
something
somewhere
and
then
gets
the
same
value
out
that
we
put
in
then
we
seem
to
have
a
system
that
conforms
to
expected
behavior
what
happens
when
there's
more
than
one
party
that
has
to
agree
on
that
value.
That's
problem
of
distributed
consensus
so,
and
there's
more
than
one
part
even
has
to
come
to
revalue,
will
come
to
an
agreement
about
that
value.
You
have
a
consensus
problem
and
distributed.
A
Consensus
is
difficult
because
there's
a
lot
of
different
ways
to
try
to
come
to
agreement
and
not
all
didn't
work,
or
they
give
up
some
properties
in
exchange
for
others
and
there's
many
different
implementation
challenges,
but
they
all
fall
into
two
kinds
of
big
buckets.
The
first
bucket
is
called
symmetric
consensus
where
any
member
of
the
any
server
or
any
those
that's
participating
in
the
consensus
group
is
allowed
to
respond
to
requests.
Bethe
symmetric
consensus
is
where
a
leader
or
a
set
of
leaders
from
among
the
participating
members
is
allowed
to
respond
to
requests.
A
So
only
certain
members
are
allowed
to
respond.
If
you
can
think
of
this,
like
two
people
agreeing
to
go
to
lunch,
so
imagine
you
have
Alice
and
Bob
Alice
asked
Bob
over
email,
hey,
you
want
to
go
to
lunch
at
12:30
and
bob
says:
that's
not
great.
Now,
Alice
and
Bob
are
in
a
locality
bubble,
they're
close
together.
Their
messages
are
quick
to
be
sense
inputs
of
your
seeds.
A
So
you
can
imagine
that
this
is
not
maybe
going
to
lunch,
but
any
kind
of
message
that
two
people
might
want
to
exchange
where
to
go
for
lunch.
What
time
we
should
go
to
Vegas
when,
when
is
that
report,
do
any
kind
of
agreement
that
you
need
to
come
to
you
between
two
parties.
So
what
happens
if
the
two
parties
are
far
apart
whatever
if
Alice
and
Bob
aren't
right
next
to
each
other,
but
there
are
some
distance
away.
A
Well,
then,
when
Alice
sends
the
message
it
might
take
a
while
for
Bob
to
get
back
to
her
and
that's
a
problem,
because
if
it
takes
a
while
what
happens
if
Bob
doesn't
respond?
Well,
Alice
can't
tell
the
difference
between
Bob's,
not
responding
and
Bob.
Just
hasn't
responded
yet
right.
Those
two
situations
are
indistinguishable,
so
for
Alice
to
know
that
Bob
has
a
problem
responding.
We
can
see
that
Bob
as
a
problem,
responding
because
we're
above
the
level
of
Alice
and
Bob.
We
can
see
the
entire
system
from
Alice's
perspective
inside
that
bubble.
A
She
can
do
that.
There's
a
lot
of
difference.
That's
not
the
only
way
the
distributed
systems
can
fail
right,
but
two
of
the
most
problematic
are
fail.
Stop
failures!
That's
like
what
we
just
saw
where
Bob
doesn't
respond.
Bob
goes
away
and
Byzantine
failures
where
Bob
is
allowed
to
respond
with
any
message,
not
just
no
message
so
Bob
could
respond
with
a
harmful
message,
a
message:
that's
deliberately
long,
a
message
that
tells
Alice
you
self-destruct,
etc,
etc.
A
So
this
is
clearly
not
a
great
state
of
affairs
when
we
live
in
a
really
hostile
distributed
different
environment.
So
how
do
we?
How
do
we
cope
with
that
environment
and
the
answer?
How
do
we
cope
is
maybe
exemplified
by
something
called
the
two
generals
problem?
This
is
a
classic
academic
problem.
It's
been
studied
in
great
detail,
so
the
two
generals
problem
works
like
this.
There
are
two
generals
which
we'll
call
a
and
B
and
they
want
to
attack
a
city
and
they
need
to
Ford
major
attack,
or
else
the
city
will
repel
them.
A
So
the
city
is
capable
of
repelling
one,
but
not
both
of
the
generals
and
the
generals
coordinator
attacks
by
agreeing
on
a
time
that
they
will
attack.
We
do
this
by
one
general
sends
a
message
to
the
other
saying
I'm
going
to
attack
at
time
T.
You
should
also
attack
at
20:00
and
I'm,
going
to
wait
for
your
acknowledgment
so
that
we
can
be
sure
about
going
to
attack
at
the
same
time,
and
if
they
can
do
that
successfully,
they
will
destroy
the
city,
which
is
their
objective
now.
A
The
problem
is
that
the
city
has
spies
as
an
intercept
to
the
messages
that
the
generals
are
sending.
So
if
you
can
do
this,
then
it
can
block
or
alter
or
fabricate
any
message
at
once,
but
for
purposes.
If
this
will
just
say
that
it
can
only
block
the
message,
so
we
can
transform
the
message
into
something
else,
but
it
can
stop
the
messages
from
being
sent
and
if
we
can
do
that,
so
we
can
prove
it.
A
It's
actually
impossible
to
guarantee
success
so
be
open
next,
because
the
other
part
Asian
never
confirmed
the
receipt
of
the
first
message.
So
Alice
sent
a
message
to
Bob,
saying:
hey
attack.
At
this
time,
Bob
sent
a
response
blast
that
response
might
get
intercepted.
So
Bob
wants
to
wait
for
a
response,
but
now
Bob
is
in
exactly
the
same
position
that
Alice
was
a
second
ago,
so
there's
no
way
for
them
to
come
to
a
100%
guaranteed
agreement.
A
This
is
just
one
way
which
distributed
systems
are
really
difficult
and
there
are
the
very
there
are
some
existing
solutions
to
try
to
have
systems
come
to
an
agreement
about
values.
One
is
you
may
have
heard
of
is
called
blas
chains
and
cryptocurrency
to
use
this
as
a
strategy.
The
positive
block
chains
for
things
like
a
database
is
that
it's
really
slow.
You
have
to
do
a
lot
of
work
to
that
you're.
Basically
doing
very
hard
math
problems
all
the
time
and
most
of
your
work
is
spent
doing
the
math
problems,
not
on
exchanging
messages.
A
The
other
kind
of
approach
that's
been
popular
is
something
called
Paxos,
which
is
a
precursor
to
rafters.
We'll
talk
about
in
a
second
axis
is
a
very
difficult
algorithm
to
implement
it's
notorious
for
having
bugs
and
the
implementation,
even
though
it's
probably
correct.
So
if
you
implement
Paxos
correctly,
you
do
get
a
distributed
consensus
system,
but
it's
really
hard
to
implement
correctly,
so
it
has
lots
of
subtle,
bugs
and
typical
implementations,
and
so
on.
A
So
graph
maps
is
kind
of
a
successor
to
axis
and
that
we
try
to
make
an
algorithm
that
is
more
easily
explainable
and
that's
what
I
want
to
try
to
do
now.
The
goal
of
graphs
is
to
have
an
available,
replicated
state
machine,
so
available
means
that
if
you
have
a
raft
system,
you
get
meaningful
responses
from
some
log
in
the
system.
So
if
you
give
non
meaningful
responses
that,
like
HTTP
540
rating
or
whatever,
that
is
not
an
available
system,
so
we
want
to
be
as
available
as
possible.
We
also
wanted
to
be
replicated.
A
We
want
other
nodes
in
the
system
to
be
aware
of
the
logs.
That's
the
shared
idea
of
what
the
state
of
the
system
is,
and
we
want
to
have
a
state
machine
with
each
node
in
the
system,
such
that,
if
we
receive
a
list
of
commands
in
our
laws
executing
the
exact
same
commands
should
produce
the
exact
same
results.
It
was
a
state
machine
understanding,
what's
happening
in
the
system.
So
here's
what
a
typical
lab
system
might
look
like.
A
A
So
if
you
boot
up
your
wrap
cluster
and
it's
got
five
nodes,
then
you
have
five
followers
from
start,
but
after
some
amount
of
time
each
node
each
node
contains
a
randomized
timeout
value,
and
when
that
timeout
value
expires,
the
follower
becomes
a
candidate
and
it
starts
to
process.
That's
called
election.
We'll
talk
about
that
in
a
second.
If
the
candidate
gets
enough
votes
from
the
other
members
of
the
cluster,
it
becomes
a
leader
and
enough
votes
means
you
have
a
majority
of
the
nodes
in
the
cluster.
A
If
you
don't
get
enough
votes
before
you
timeout
again,
then
you
start
a
new
election.
You
keep
trying
to
do
this
until
somebody
wins.
If
you
are
the
leader,
you
could
step
down
to
become
a
better
leader.
If
you
discover
that
somebody
else
is
actually
in
a
better
state
than
you
are
so,
if
you're
the
leader
when
you're,
not
the
best
leader,
if
you
could
be
that
you
could
be
told
to
step
down
so
mass
device
view
the
world
of
time
in
two
terms,
a
term
is
an
integer
value
that
starts
at
zero.
A
Is
then
incremented
over
time,
depending
on
every
time
you
hold
an
election,
you
increment
the
term,
so
each
term
starts
with
an
election
and
during
the
election
you're
trying
to
figure
out
who
the
leader
is
once
you
figure
out
the
leader,
you
can
start
exchanging
messages,
you're
available
at
that
point.
So
once
you
have
a
leader,
your
cluster
is
available.
If
the
leader
dies,
somebody
gangsta's
poured
out
as
a
wall
as
their
server
or
whatever
not
a
problem.
The
eventually
one
of
the
nodes
will
time
out.
A
First
and
a
new
election
will
happen,
and
it
will
let
the
new
leader
in
the
cluster.
This
is:
if
the
election
takes
too
long,
don't
worry,
you
can
increment
the
term
again
and
you'll
hold
a
new
election.
Then,
at
that
point,
you'll
have
normal
operation
when
you
repeat
this
process
indefinitely,
but
we
hope
is
that
the
green
bars
are
much
much
longer
than
the
red
bars
right.
We
don't
want
to
be
spending
our
time
doing
elections.
We
want
to
be
spending
our
time,
exchanging
messages
arriving
in
consensus
for
people
making
requests
to
us.
A
Here's
out
election
works
election
is
free
steps.
You
increment
your
current
turn,
you
vote
for
yourself,
and
then
you
ask
for
votes
from
everyone
else,
and
we
want
some
want
some
properties
to
be
true
in
the
an
election.
So
first
we
want
there
to
be
at
most
one
winner
per
term.
We
don't
want
to
have
an
election
of
and
have
five
people
when
the
election
you
want
one
winner
out
of
that
election.
A
We
should
know
that
someone
will
win
and
we
do
that
by
selecting
a
election
time
out.
That
is
much
larger
than
the
amount
of
time.
We
think
it
should
take
to
send
messages
between
those
and
a
cluster.
So
if
it
takes
a
five
milliseconds
to
send
a
message,
you
don't
want.
Your
election
time
has
to
be
three
milliseconds,
because
you'll
never
be
able
to
send
a
message
before
you
timeout.
You
want
your
timeouts
to
be
much
larger
than
your
the
amount
of
time
it
takes
to
send
messages
between
things
in
the
cluster.
A
So
typically
that
looks
like
hundred
milliseconds
200
milliseconds
only
three
possibilities
in
election.
You
receive
the
majorities
you
become
the
leader.
You
receive
a
valid
heartbeat
from
another
leader
that
says:
hey
I'm,
the
leader.
You
should
become
a
follower
or
the
election
times
out
and
you
start
a
new
election.
So
here's,
if
you
receive
the
majority,
that
you
become
a
leader
and
you
tell
everyone
else.
A
If
you
receive
a
valid
heartbeat,
then
you
go
back
to
being
a
follower
or
if
the
election
turns
out,
you
keep
being
a
candidate,
and
you
start
a
new
election
by
incrementing
your
turn.
So,
let's
see
what
a
straightforward
election
would
look
like.
So
here's
a
rap
cluster
with
five
notes,
s1
s2,
s3,
s4
and
s5,
and
the
gray
ring
around
each
note-
tells
you
what
the
election
time
at
is
and
you'll
see
that
gradually
start
decrementing
to
notice
that
s2
is
about
to
become
about
to
become
a
candidate.
A
A
So
what
happens?
If
our?
What
happens?
If
we
have
some
problems
with
our
cluster,
can
we
still
have
an
election?
So
let's
say
we've
got
a
let's
say:
we've
got
a
situation
here
where
s4
and
s3
are
out
of
power.
Disabled,
so
they've
been
yanked
out
of
the
wall
and
we
only
have
three
members
alive
in
our
five-member
cluster
so
still
enough
to
get
a
majority,
but
but
some
of
our
nodes
are
unavailable.
A
So,
let's
see
what
happens
in
this
case
notice
that
s2
and
s1
have
election
time
outs
that
are
very
close
to
each
other,
so
it's
possible.
They
might
both
try
to
start
an
election
at
the
same
time.
Let's
see
what
happens
so
s2
sergeant
election
s1
such
an
election
at
the
same
time,
and
they
both
don't
get
it.
They
both
don't
get
three
votes
out
of
the
five,
so
it's
not
as
I'm
cuñado
him
can
become
to
the
leader.
So
we'll
we
start
I
can
do
election
time
out
as
two
times
out.
A
First,
this
time
it's
able
to
get
all
three
votes
and
becomes
the
leader,
so
s3
is
now
the
leader
or
Eskew
is
now
the
leader
and
Rebeck
internal
operational.
So
that's
that's
just
deciding
who
the
leader
is.
What
happens
when
we
want
to
exchange
information?
So
that's
the
laws
replication
part
of
raft,
so
a
login
Rastus
looks
like
a
piece
of
data.
It's
got
an
index
a
index
is
the
number
of
live
items
you
already
have
before
this
one.
A
So
if
you've
seen
six
items,
then
your
index
will
be
six
if
it
has
a
piece
of
as
a
piece
of
data
that
represents
the
thing
that
you're
storing
and
then
it
has
the
term
that
the
best
piece
of
data
is
associated
with.
So
if
you
receive
the
data
in
turn
or
piece
of
data
will
have
a
term
for
attached
to
it.
So
a
given
server's
log
is
a
list
of
these
log
entries
and
a
collection
of
logs
for
the
entire
cluster
just
looks
like
a
list
of
laws.
In
this
case.
A
Server
0
is
the
leader
and
it
has
one
entry,
but
the
other
two
servers
don't
yet
have
we
consider
a
entry
submitted
if
it's
not
a
majority
of
the
servers.
So
in
this
case
all
the
entries,
except
for
the
entry
in
position
for
that
server
0,
has
is
committed.
So
everything
else
is
committed,
but
the
entry
in
position
4
for
server
0,
is
not
whenever,
whenever
the
leader
wants
to
send
new
entries
to
the
other
servers,
it
does
that
by
including
the
previous
entries
term
and
index.
A
So
here
is
saying:
hey
I
I
want
to
send
you
this
piece
of
data
B
that
I
have
+
before
I.
Send
that
to
you
I'm,
going
to
also
send
you
a
piece
of
data
that
says
here's
what
comes
right
before
word
this
one,
so
that
you
can
check
that
you're,
not
only
getting
the
new
piece
of
data,
but
that
you
have
everything
that
came
before
if
you're
not
missing
pieces
of
data.
In
other
words,
so
we
also
want
logs
to
be
saved.
So
we
want.
A
If
we
commit
something-
and
we
know
it's
committed-
that
we
want
that-
we
want
to
have
to
be
persistent
for
all
the
future
leaders
in
the
cluster
as
well.
So
the
leaders
job
is
to
propagate
those
laws
to
its
followers.
So
here's
a
case
where
there
we
go
so
here's
a
case
where
the
the
leader
has
some
entries
in
its
laws
and
it's
going
to
propagate
those
entries,
one
of
the
time
to
the
other
followers
notice
that
every
time
it
says
that
it
resets
the
election
timeout
if
that
counts
as
a
heartbeat.
A
So
it's
telling
the
telling
the
other
members
of
a
cluster-
oh
hey,
I'm,
still
here,
here's
the
last
entry
that
you
need
to
update
your
stuff
with
also
known
as
let
me
rewind
a
little
bit
also
notice
that
the
dotted
lines
represent
entries
that
the
leader
isn't
sure
are
committed.
Yet
so
here
the
leader
knows
that
this
first
entry
is
committed
because
it's
stored
on
the
majority
of
servers
and
it's
gotten
responses
and
confirmations
that
that's
been
stored,
but
it
doesn't
know
about
that
to
them
until
everybody's
up-to-date.
A
So
there's
a
problem,
though,
because
we
don't
want
to
vote
for
someone
accidentally
who
might
be
a
worse
leader
than
we
are,
so
we
only
want
to
vote
for
people
that
are.
We
only
want
to
vote
for
people
that
we're
sure
would
be
better
leaders
than
we
would
be
if
we
were
a
candidate.
So
here's
what
that
looks
like
in
this
case
we've
got
a
five
hour.
Five
minutes
luster
again,
that's
five.
Just
timed
out
it's
starting
an
election
for
term
for
s1
has
some
records.
A
So
if
you
look
at
the
log,
s1
is
the
best
possible
leader
right
now,
but
s5
happened
to
time
out.
So
s5
should
be
able
to
get
votes
from
s1
and
it
should
be
able
to
get
folks
from
s3
because
both
of
those
are
better
logs
and
it
does
it's
still
possible,
but
s5s
we've
become
the
leader
and
you
have
to
get
a
majority
here,
we'll
see
what
happens
when
that
happens.
So,
let's
see
what
happens
when
I'm
in
this
situation,
occurrence
or
s5
is
about
to
start
a
new
election.
A
So
s5
did
not
win
the
election
because
it
only
got
two
out
of
the
three
votes
and
s
ones.
Part
B
2sq
got
their
first
and
Eskew
decided
not
to
vote
for
s5.
So
then
it's
just
a
normal
election
situation
where
one
interval
timeout
event.
This
guy
is
now
the
leader
and
it
will
tell
everyone
to
update
all
the
records
notice
that
when
it
told
everyone
to
update
their
records,
it's
going
to
overwrite
the
entries
and
s3
because
they're
not
committed
and
they're,
not
as
good
as
its
entries
from
turn
three.
A
So
how
do
you
decide
if
you
should
vote
for
someone
else?
So
you
don't
vote.
If
you
get
a
request
to
vote,
you
don't
vote
if
your
term
is
better
than
the
candidates
term.
So
if
you
want
term
six
and
you
get
a
request
to
vote
from
someone
who's
entering
five-
you
don't
vote
for
them.
She
returned
is
better.
You
also
don't
go
to
them
if
your
term
is
the
same
as
theirs,
but
your
index
is
better
than
the
candidates.
A
So
if
you
have
five
records
and
they
have
three
and
you're
both
on
term
95-
you're
not
going
to
vote
for
them
because
your
index
is
better
than
their
index.
So
in
this
case
s0
cannot
get
floats
from
s1
or
s2,
because
it's
term
is
worse.
Right
keeps
on
an
election
starts
for
term
or
let's
say
if
it
doesn't
have
entries
there
yet.
A
So
it's
never
going
to
vote
for
that's
never
going
to
go
for
one
or
two,
and
similarly
s1
can't
get
votes
from
s2,
because
if
indexes
works,
it's
missing
entries
of
s
to
s.
So
the
last
piece
of
this
puzzle
is
that
there
is
commitment
issues
in
the
certain
edge
cases,
the
first
big
edge
cases.
What
happens
if
server
0
is
the
servicer
as
a
leader
right
now
and
if
server
tooten
became
the
leader
for
term
5
entries
and
s
1.
A
If
this
entry
could
be
overwritten,
if
server
2
becomes
the
leader
right
because
it
was
propagated
at
server
1
with
both
from
server
to
server
2
would
go
through
itself.
Now
it's
got
a
majority
and
server
2
would
propagate
requests
to
overwrite
entry
3.
Even
though
entry
3
is
committed,
that's
a
big
problem.
We
thought
something
was
committed
and
it
got
over
it.
So
that's
that
all
those
entries
that
we
thought
were
committed
could
go
away
and
die.
A
So
we
need
a
new
rule,
which
is
we
only
consider
it
committed
if
first
its
majority
stored,
like
we
said
before,
we
also
need
to
add
a
new
piece
that
says
there's
at
least
one
entry
from
our
current
term.
That's
also
majority
stored,
so
in
this
case,
we're
in
this
case
we're
going
to
we're
going
to
consider
these
committed
because
they're
stored
on
a
majority
of
servers,
but
we're
also
considering
them
committed,
because
we
have
at
least
one
entry
from
term
for
the
leaders
current
term,
which
is
also
a
majority
stored.
A
So
less
that's
everything
we
need
to
make
distributed
consensus
with
wraps
takeaways
first,
if
the
facet
I
could
explain
this
in
exactly
20
minutes
off
is
something
you
can't
really
say
for
Texas
I
mean
if
you
look
at
the
you
look
at
the
paper
for
taxes,
I
think
it
would
take
you
20
minutes
to
read
the
table
of
contents.
Much
less,
be
much
less
explain
it
for
to
try
to
implement
it.
A
Second
is
if
you
get
really
strong
guarantees
for
what
is
a
relatively
small
set
of
relatively
simple
rules
about
how
to
exchange
information
and
how
to
share
information
amongst
members
in
the
cluster
and
third,
it
is
if
you're,
probably
already
using
it
if
you
use
cloud
foundry
or
kubernetes
or
dr.
swarm
you're
using
a
technology
called
fcd,
which
is
a
key
value
store
and
the
way
this
MCD
shares
information
with
other
members
of
an
SCV
cluster.
Is
you
guess
it
wrapped?
So,
if
you're
using
these
technologies,
you're
actually
already
using
an
implementation
of
that?