►
From YouTube: Deep Dive: etcd - Jingyi Hu, Google
Description
Join us for Kubernetes Forums Seoul, Sydney, 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
Deep Dive: etcd - Jingyi Hu, Google
etcd, a distributed key-value store, is the most critical component to Kubernetes control plane to provide strong consistency and durability of cluster metadata. etcd implements Raft consensus algorithm to distribute the data across multiple nodes. All data replication is done by Raft. Did you know etcd Raft package is also used in many other projects? CockroachDB shares etcd Raft implementation for its group membership protocol. TiKV ported etcd Raft to Rust, which is originally written in Go, and uses it to implement their distributed transactional data base. This session will cover the basics of Raft consensus algorithms, its implementation details, and future roadmap of Raft package.
https://sched.co/Nrqh
A
A
If
you're,
you
know
raft,
and
you
want
to
start
reading
or
you
just
started
reading
the
raft
source
code,
I'm,
hoping
that
this
presentation
will
give
you
a
nice
starting
point
on
reading
the
code
and
also
for
those
who
wants
to
understand
the
relationship
between
at
City
and
raft,
basically,
how
at
city
uses
raft
or
why
raft
is
important
to
at
CD
we're
gonna
talk
about
this
in
this
talk.
Also,
if
you
are
writing
your
own
project,
your
own
application,
you
want
to
import.
You
want
to
embed
raft
package.
A
A
A
We're
gonna
talk
about
third
point,
which
is
the
implementation
details
of
the
raft
and
after
the
third
point,
we're
gonna
revisit
the
second
point,
because
by
then
we're
gonna
have
more
details
to
talk
about,
and
last
we're
gonna
talk
about
some
of
the
ongoing
effort
effort,
I'm
aware
of
in
the
raft.
Okay,
all
right
so
raft
recap
first
quickly,
some
concepts.
What
is
a
quorum?
A
quorum
is
basically
maturity.
So
if
Q
1
and
Q
2
are
quorum,
their
intersection
is
not
empty.
So
what
is
the
crown?
A
For
example,
if
you
have
a
cluster
of
size
1,
so
one
server
in
your
cluster,
the
quorum
is
one.
If
you
have
two
servers,
your
core
on
is
two,
but
then
you
have
three
servers.
Your
quorum
is
not
three
is
two
because
you
can
pick
any
two
out
of
the
three
and
you
can
find
intersection
node
between
the
quorum
right.
So
in
this
example,
where
you
have
five
five
servers
in
your
cluster,
the
Krone
is
three.
A
B
A
Long
as
there
is
agreement
among
the
quorum,
what
does
that
mean?
So
in
this
example,
you
don't
need
all
five
servers
to
be
available
for
you
to
serve
the
client.
You
can
have
at
most
two
servers
unavailable
at
the
moment,
but
as
long
as
you
have
quorum,
which
is
three
and
if
they
Greece
to
something
you
can,
the
entire
cluster
can
still
serve
client
right.
A
So
what
is
the
problem
raft
tries
to
solve?
Imagine
you
have
a
collection
of
servers.
Each
server
is
a
state
machine,
for
example,
in
at
CD
is
a
key
value
store
right,
you
can
write
keys,
you
can
read
keys.
It
is
a
state
machine.
You
have
a
cluster
of
servers.
Each
server
is
a
state
machine.
Then,
when
the
client
interact
with
this
cluster,
how
do
you
make
sure
that,
from
clients
view
this
cluster
of
servers
behaves
like
a
single
state
machine,
a
single,
reliable
state
machine?
A
So,
for
example,
the
client
my
at
this
moment
right
it
choose
to
issue
a
write
command.
It
writes
a
key
value
to
the
state
machine
and
one
of
the
servers
in
your
cluster
served
this
request.
Let's
say
server
a
and
the
next
moment
the
client
wants
to
read
that
key,
but
server
a
is
not
available
at
that.
Time
is
a
different
server.
Let's
say
server
be
served
the
client.
How
do
you
make
sure
server?
B's
local
state
machine
has
the
same
state
so
that
when
it
serves
the
client,
it
returns
the
correct
result
right.
A
A
So
if
these
state
machines,
if
they
all
have
the
same
initial
state,
which
you
have
to
make
sure
right,
so
whatever
bootstrapping
process
you
are
using,
you
have
to
make
sure
when
these
server
starts.
They're
gonna
have
the
same
initial
State
and
then,
if
you
can
somehow
achieve
this,
if
you
can
make
sure
that
each
server
also
has
the
same
input
sequence,
then
it's
guaranteed
that
basically
they're
so
for
these
state
machines
right.
A
Going
to
have
the
same
state
and
output
right,
so
the
problem
becomes.
How
do
you
achieve
this?
How
rough
does
it
so?
The
raft
consensus
protocol
achieve
this
by
basically
doing
this
it
it
manages
the
replicate
right,
a
headlock,
so
whatever
the
the
request,
the
client
wants
to
execute
on
the
state
machine.
It
first
needs
to
be
write
to
this
to
a
log
which
is
managed
by
the
consensus
protocol.
A
If
these
are
the
same,
then,
when
they
input
to
a
state
machines
with
initial
same
initial
state,
then
the
problem
is
solved
right
now.
How
does
raft
actually
does
it?
Roughly
speaking,
it
has
two
parts.
First
is
leader
election?
The
second
is
how
leader
replicate
its
logs
to
the
rest
of
the
servers
in
the
cluster,
so
we're
gonna.
First
sorry
we're
gonna.
First
talk
about
leader
election.
A
raft
node
in
the
cluster
can
be
either
a
candidate,
a
follower
or
a
leader
so
term.
What
is
the
term?
A
term
is
basically
a
logic
clock.
A
In
the
raft
starting
of
each
term,
there
is
going
to
be
a
election,
so
each
node
can
vote
for
one
node
in
a
given
term.
When
a
node
gets
majority
of
the
votes.
Remember
the
quorum
will
talk
about.
So
if
you
get
votes
from
a
quorum,
then
it
becomes
a
leader,
so
you
can
have
at
most
one
leader
in
your
term.
Now,
once
a
leader
is
elected,
it
manages
the
rest
of
the
term.
The
leader
will
periodically
send
out
a
heartbeat
messages
to
make
sure
everybody
else
knows
that
the
leader
is
still
presence
right.
A
C
B
A
Replicate
its
own
log
to
the
other
raft
node
in
the
cluster
when
maturity
of
the
node
in
the
cluster
has
this
particular
log
entry.
So
basically
the
logs
are
indexed.
There
is
log
entry,
0,
1,
2,
3,
4
right,
so
the
leader
is
trying
to
replicate
these
logs
to
the
followers.
The
leader
also
monitors
everybody's
progress.
A
So
when,
when
it's
marked
as
committed
it
is,
it
is
safe
for
everybody
to
apply
that
log
right.
In
our
previous
an
example.
Let's
say
leader
finds
out
so
it
let's
say,
leader
has
10
lakhs
right
from
0
to
9
and
it
remember
it
tries
to
replicate
logs
to
other
nodes
right.
Let's
say:
there's
two
other
nodes:
node
a
and
node
B.
Besides
from
the
leader
right
so
node
a
has
log
0,
1,
2,
3
and
node
B
has
0
1,
2,
3
4,
for
example,
then
well,
I!
A
Guess,
since
the
leader
and
node
B
they
they
both
have
log
entry
for
right
so
from
0
to
4.
They
are
all
basically
committed
because
you
have
majority
of
node.
Have
those
logs
once
committed
it's
it's
safe
to
apply
those
logs,
so
each
each
local
node
is
gonna,
know
from
the
leader
which
logs
are
committed
and
it's
gonna
apply
those
logs
right
all
right.
So
now,
let's
talk
about
how
raft
uses
at
City.
This
graph
is
basically
the
same
as
the
one
we
just
saw.
A
Remember
we
already
explained
how
a
raft
can
help
to
solve
the
replicated
state
machine
problem
right
now
in
this
graph.
It's
basically
the
same
here
is
just
a
client.
This
is
an
example
application.
It's
a
city
code
o
is
a
command
line
tool,
it
empaths
the
@cd
client
library.
Another
example
can
be
in
Cabrini
kubernetes
api
server,
also
ambassadors,
client
v3,
which
can
talks
to
the
at
CD
cluster.
A
Now,
when
a
client
sends
a
request
to
the
server,
the
request
is
relative
to
the
raft
consensus
module
for
this
example.
Let's
say
this
server
is
a
follower,
it's
not
a
leader
right.
So
let's
say
this
is
the
cluster,
and
this
is
one
of
the
server
in
the
cluster
and
it's
not
a
leader,
it's
a
follower.
A
So
once
the
request
is
relative
to
the
raft
module,
it's
going
to
be
forwarded
to
the
raft
leader,
the
raft
leader
will
append
that
request
to
its
own
raft
log,
and
then
it
will
tries
to
replicate
that
log
entry
to
other
nodes,
for
example.
This
note
showed
here
right.
This
is
a
follower
and
once
he
knows,
maturity
of
the
node
has
that
particular
raft
entry.
It's
going
to
be
marked
as
committed,
and
now
this
server
knows.
A
Ok,
that
particular
log
entry
is
committed,
so
I
can
apply
that
so
it
now
it's
going
to
be
applied
to
this
state
machine
which,
in
at
CD,
is
multi-version
concurrency
control,
key
value
store.
So
it's
gonna
apply
that
to
this
machine.
Remember
that
log
could
be.
It
is
a
request
from
the
client
right,
for
example,
it
can
be
read
a
key
or
write
a
key
value,
so
whatever
the
output
is,
if
your
writing
is
gonna,
tell
you
ok,
write
successful
if
your
reading
is
gonna
return,
the
the
value
of
that
key
right.
B
A
B
A
The
design
philosophy
for
the
raft
package
in
@cd
is
that
it
tries
to
keep
it
minimalistic,
meaning
that
the
raft
package
does
not
implement
Network
transport
between
the
raft
nodes.
Remember
there
are
going
to
be
messages
between
raft
notes
right,
like
just
like.
We
saw
the
leader,
my
replicators
locks
to
the
follower,
but
this
package
does
not
implement
network
transport
also,
it
does
not
implement
the
persistent
storage
layer,
so
whoever
is
using.
This
raft
package
needs
to
implement
network
transport
and
persistent
storage
layer
by
including
less
in
the
raft
package.
A
It
makes
the
package
more
flexible,
because
now
you
can
choose
your
own
implementation.
It
also
makes
the
behavior
of
the
raft
package
to
be
deterministic
as
a
result.
The
raft
well
deterministic
has
is
a
very,
very
nice
thing,
because
if
the
behavior
of
the
raft
package
is
deterministic,
it
usually
means
it's
easier
to
implement
is
easier
to
test.
It's
also
easier
to
argue
its
correctness,
so
the
raft
itself
is
actually
modeled
as
a
state
machine.
Now
let
me
go
back
to
the
to
this
to
this
graph.
A
Now
we're
just
going
to
focus
on
the
raft
package
implementation
itself
right.
So
we're
not
talking
about
this
state
machine
here,
we're
talking
about
raft
and
we're
saying
the
raft
is
modeled
as
a
state
machine
right.
Just
remember
all
right
so
raft
is
a
state
machine.
Then
what
is
its
state?
What
is
its
input
and
output?
How
does
state
transition
between
each
other
so
now
we're
gonna
dive
a
little
bit
into
the
code.
A
Just
a
quick
disclaimer,
the
code
I'm
showing
here
is
mostly
pseudocode,
so
that
they
can
actually
fit
in
the
screen,
and
you
can
still
see
it,
but
they
look
very
similar
to
the
actual
source
code.
So
when
you
see
this
and
then
later,
when
you
read
the
source
code,
it's
going
to
be
very
familiar
and
you're
it's
easier
for
you
to
understand
what
the
source
code
does
alright.
So
the
state
here
is
basically
wrapped
into
this
structure
called
raft
you
can
see
there
is
a
node
ID
there's
a
term.
A
Remember
term
is
like
a
clock
vote.
Each
member
can
vote
for
one
node
in
a
term,
so
this
indicates
which
node
a
voted.
This
is
the
the
log
we
talk
about,
like
how
remember
we
said
raft.
Consensus
protocol
helps
manages
the
log
to
make
sure
that
log
on
each
node
is
the
same.
This
is
the
log
and
the
state
basically
says
a
wrap
can
be
either
a
leader,
a
candidate
or
follower.
This
is
an
interesting
function.
It's
a
called
stop
function.
It
has
different.
Implementations
depends
on.
A
If
you
are
a
leader,
it's
going
to
be
a
step
leader
function.
If
you're
a
follower,
it's
a
step.
Follower
function
right
et
cetera.
Now,
what's
what's
the
input
to
the
raft
state
machine?
It
is
a
message.
What
is
the
message?
First,
it
has
a
type,
so
messages
are
of
different
types.
For
example,
you
can
have
a
message
vote,
which
is
for
requesting
a
vote
or
a
message
append,
which
is
used
by
the
leader
when
they
tries
to
replicate
its
logs
to
other
nodes.
A
It's
gonna
issue,
a
message
with
a
message:
Japan
type
2
is
the
destination
node
from
is
where
the
message
is
from
we're.
Gonna
skip
this
and
entries.
So
a
message
can
a
message
can
carry
a
whole
bunch
of
entries,
for
example,
when
the
leader
tries
to
replicate
logs
from
itself
to
the
followers
it's
gonna
increase.
Include
the
ref
log
entries
here:
ok,.
A
What's
the
output
of
this
raft
state
machine,
the
output
is
wrapped
in
into
this
structure,
which
is
called
ready.
It
means
these
are
ready
to
be
consumed
to
be
processed
by
whoever
is
using
the
raft
package
all
right.
So
first
one
is
the
state
of
the
raft
next
one.
This
state
needs
to
be
saved
to
the
storage,
because
remember,
the
raft
package
itself
does
not
include
implementation
of
persistent
storage
right
and
these
is
these
are
the
entry
that
needs
to
be
saved
to
storage.
A
These
are
the
committed
entries
which
are
remember
safe,
to
be
applied
to
this,
to
the
key
value
store,
and
these
are
the
messages
remember.
The
raft
package
does
not
implement
network
transport,
so
it's
whoever
is
using
the
wrap
package
needs
to
consume
this
consume
these
messages
and
actually
deliver
these
messages
to
their
destinations.
That's
why
they
are,
including
in
the
in
output.
Now
how
do
the
state
transition
the
core
function
is
going
to
be
the
function
called
step
with
the
capital
S
step
function,
advance
the
raft
state
machine
using
the
given
input.
A
A
The
thing
here:
if
we
look
into
this
function,
it
eventually
calls
this
function
and,
in
the
beginning,
there's
some
common
logic
for
no
matter
whether
you're
a
leader
or
candidate
or
follower,
and
then
it
calls
this
lowercased
step
function,
which
is
different,
depends
on
whether
you're
a
leader
than
this
function
is
going
to
be
called
step,
leader,
etc.
Right,
so
it
depends
on
your
state.
This
function
is
going
to
be
different.
Now,
let's
go
to
an
example
in
terms.
A
Okay,
now,
let's
say
we
want
to
propose
a
change
to
the
KB
store
right.
Remember,
let's
quickly,
go
back
to
this
slides
when
a
client
request
to
execute
a
command,
for
example,
a
read
command
or
write
command.
The
key
value
store,
it's
gonna,
so
how
it's
gonna
do
is
gonna
propose
a
change
the
raft.
So
this
is
the
example
we're
gonna
talk
about,
so
the
first
function
is
proposed
function.
A
A
Now
what
this
function
does
is
it
generates
a
message
and
feed
that
message
as
input
to
servers
local
raft
state
machine.
In
this
example,
let's
assume
it's
a
follower
who
is
serving
the
client
request?
Okay,
so
what's
in
this
message,
you
can
see
the
type
is
message
prop
and
it
includes
the
entries.
This
is
the
data
remember.
This
corresponds
to
the
client
request
right.
So
this
is
the
data.
So
this
message:
let's
call
it
message-
a
goes
to
into
the
follower
raft
state
machine.
A
Now,
if
you
go
to
the
source
code,
remember
it's
going
to
be
sent
to
the
step
function,
which
eventually,
because
it
is
a
follower.
It
eventually
goes
to
step
follower
function.
Now
this
function
depends
on
its
input.
Message
is
gonna,
do
different
things
right.
It's
gonna
execute
different
code
path
in
this
example,
because
our
input
message
is
of
this
type.
So
it
goes
to
this
code
path
and
what
it
does
is
basically
mark
a
destination
node
to
be
the
leader
of
the
raft
cluster
and
sent
that
message.
A
What
that
stent
mean
because
remember
raft
package
does
not
actually
implement
network
transport
between
the
rough
notes
right.
So,
if
you
look
at
this
send
function,
this
is
basically
marking
this
function.
This
message
is
from
myself
and
then
it's
simply
append
this
message
a
right.
This
is
the
message
and
that
is
appended
to
its
local
message
queue
and
this
message
queue
is
going
to
be
so
remember.
The
raft
state
machines
output
is
something
called
a
ready
right.
It's
a
ready
structure.
A
Let's
just
quickly
go
back
through
to
make
sure
everybody
still
remembers,
so
this
is
the
output
of
the
raft
state
machine
right.
We
just
saw
its
input
now
its
output
is
going
to
include
this.
This
message
a
see
this
message
a
is
appended
to
this
message.
Q
then
it's
going
to
be
included
in
this
message.
So
what's
the
output
of
this
follower
a
raft
state
machine,
it's
going
to
be
a
ready
structure,
but
for
simplicity,
we're
just
tracking
the
messages.
Okay,
the
ready
has
other
fields
but
we're
just
tracking
the
messages.
A
So
it
basically
is
the
same
message
right
but
marked
from
as
from
itself
and
to
to
the
leader.
We
call
this
message
be
now.
Whoever
is
using.
This
wrap
package
needs
to
needs
to
process
those
messages
needs
to
process
these
messages
from
the
output
of
the
raft
state
machine
right
in
this
case,
these
messages
will
be
sent
to
their
destinations.
A
So
let's
look
at
the
leader
here.
This
message
is
this
is
the
same
message.
B
is
going
to
be
so
remember.
You
need
to
implement
the
network
transport
right
so
that
Network
transport
implementation
needs
to
forward
the
message.
B
from
the
followers
output
to
this
leaders
input
now
it's
here.
Let's
look
at
that
leaders
function
again.
This
is
the
message
be
here,
and
it's
of
this
type
message
prop.
So,
let's
see
what
leader
does
it?
First,
a
pens
all
the
entries
from
this
message
to
its
own
raft
log?
A
This
is
what
it
does
and
then
this
function
tries
to
append
its
raft
logs
to
two
other
raft
nodes
in
this
cluster.
So
let's
say
we
have
two
other
nodes
in
this
cluster:
it's
gonna
for
each
of
those
nodes.
It's
gonna
call
this
function,
which
is
a
new
message
of
a
different
type.
Now
message:
Japan,
because
now
we're
trying
to
replicate
or
the
leaders
own
log
to
other
nodes
right
is
that
pier
then
entries
includes
leaders.
Own
entry
commits
we're
gonna
talk
about
later,
so
this
is
basically
I'll
actually
already
talk
about
it
right.
A
So
when
Lee
cuz
leader
leader
monitors
each
knows
progress,
will
majority
of
those
already
have
a
certain
entry?
Is
gonna
be
marked
as
committed
right.
So
this
is
leader
telling
everybody
the
progress
of
the
entire
cluster,
which
means
like
which,
which
ref
logs
are
actually
committed,
and
after
he
generates
this.
This
message
is
gonna.
A
What
I'm
trying
to
show
here
is
how
to
read
how
to
how
to
read
a
source
code
like
given,
given
an
an
input
based
on
whatever
the
current
state
is
whether
you're
a
leader
whether
you're
a
follower,
it's
gonna
have
different
state
transition
and
in
return
it's
going
to
generate
more
messages
and
maybe
more
entries,
and
they
are
going
to
show
up
in
the
rav
state
machines
output,
which
is
the
structure
we
called
ready
right.
So
maybe,
let's
just
fast
forward
to
the
last
step
of
this
example,
which
so
what
we
have
saying.
A
We've
saying
that
we've
saying
the
clients
request,
which
is
the
message
a
including
this
message,
a
was
forwarded
to
the
leader
right.
We
saw
a
step
its
forwarded
to
the
leader
appended
leaders,
local
RAF,
log
and
leader,
tries
to
replicate
that
RAF
lock
to
other
nodes
in
this
cluster,
and
eventually
it's
going
to
be
successful.
So,
let's
say
most
of
the
knows
already
has
this
new
raft
entry
and
the
leader
knows
that
and
leader
marks
that
new
raft
entry
as
committed
and
eventually
is
going
to
send
a
message
with
the
updated
committed
index.
A
What
happens,
then?
Is
that
because
remember
this
new
raft
raft
log
entry
is
committed
from
the
output
of
this
followers
raft
state
machine
from
its
output.
You're
gonna
see
that
new
raft
entry
show
up
here
as
committed
entries.
Now
it's
ready
to
be
applied
alright.
So
this
is
the
graph
we
just
saw
earlier
we're
going
to
talk
about
with
more
details,
because
now
we
see
more
details.
First,
we
don't
care
about
the
client
side
now,
so
the
first
thing
we
we
know
is
that
the
raft
package
does
not
implement
persistent
storage
interface.
A
It
does
not
implement
Network
transport
between
the
raft
nodes,
so
these
are
actually,
if
you
are
using
the
wrap
package,
you
need
to
implement
these
and
then,
if
you're,
using
this
this
raft
package,
you
are
probably
going
to
with
something
like
this.
A
handling
loop,
you're
gonna,
need
to
consume
and
process
all
the
output
from
your
local
raft
state
machine.
So
this
gives
you
the
ready
structure.
We
just
saw
it's
stored
in
here.
The
first
thing
you
should
do
is
this
storage
is
your
own
implementation
of
the
storage
interface?
A
You
need
to
save
the
state,
save
the
entries,
and
then
the
next
step
is
that
this
is
your
own
implementation
of
the
network
transport
between
the
raft
nodes.
You
need
to
send
those
messages.
Remember
you
are
responsible
for
actually
delivering
those
messages
and
then
for
all
the
committed
entries
it's
safe
to
be
applied.
So,
what's
the
lifecycle
of
a
client
request,
a
client
request
is
first
going
to
be
remember
it's
going
to
be
relative
to
the
raft
and
it's
gonna
call.
A
This
proposed
function,
which
generates
a
message,
a
raft
message
right
and
within
the
raft
consensus
protocol,
it's
gonna,
so
the
local
raft
state
machine
is
gonna
generate
based
on
that
raft
message.
It's
gonna
generate
a
whole
bunch
of
new
raft
messages
and
be
sent
to
other
node.
Another
node
in
return
might
generate
other
messages
right,
so
it's
back
and
forth.
But
eventually,
if
that
raft,
log
entry
is
committed,
which
means
most
node
has
that
entry.
A
A
All
right
so
quickly,
this
is
on
some
of
the
ongoing
efforts.
I'm
aware
of
the
first
one
is
actually
completed,
so
the
raft
package
itself
supports
learner
and
normal
team
member
actually
for
a
while
now,
but
recently
at
sea
server
also
adds
support
for
learner
and
normal
team
member.
If
you're
interested
here's
the
link
for
you
to
start
another
ongoing
effort
is
that
there
is
a
raft
membership.
There
is
joint
consensus
for
a
raft
membership
reconfiguration,
which
is
different
than
the
current
membership
reconfiguration
implementation
in
raft,
if
you're
interested
there.
A
C
A
A
B
A
Leader
show
miss
entire
cluster
young
women
guy
applied
on
I,
know.
I
can
trailer
nominees
at
local
that
you
go
deep
on
y'all
yeah
y'all
tongue,
slowly,
she
I
applied
at
all
high
one
donation
yeah,
but
latest
the
chicken
soil
the
sending
children
are.
You
got
twitching
shoulder
she
hold
my
attention
just
authorizing
to
me.
I'll
apply
that
this
year,
commander
Moodle
apply
one
lady.