Kyle Kingsbury: "Jepsen IV: Hope Springs Eternal"

So, um, the title of this talk is, "Jepsen IV:
Hope Springs Eternal."

There is in fact no Jepsen III. Don't go
looking for it. It doesn't exist. That

should tell you a little bit about what
we're going to discuss in the talk today.

My name is Kyle Kingsbury. You might know
me as "aphyr."

Um, I am scared and confused and excited
about computers all the time.

Uh, and today, I work at a new company
called Stripe.

Uh, we are a credit card company. Ah, we
help you sell goods and services via some

API, um, which is phenomenal, right?
Developers say, "Oh, I wanna take credit

cards. How do I do it? "Well, I could
build all this [PCI-complying]

infrastructure, or I could just make
[an HTP request] to some magical

rainbow in the sky, and everything will
work out just great.

We've all built APIs, right? They're not,
They're not real things. They're

abstractions. They're imaginary
constructs. So that's this rainbow up top.

That's our, that's our API, right?
But it's actually supported on this

steel girder framework, which is our code.
That's written in Ruby.

Um, and then that code rests on top of all
these libraries and the [Ruby VM].

Um, that's represented here by this big
pile of sticks. And those things in turn

rest on a pile of tires, which symbolize
our databases and [queues and

other associated systems]. Now does
anybody who's used a database--

Ah, how many of you have, actually?
Oh, very good. Less than I expected.

(Audience laughs as slide is changed}

Um, anybody who's used a database knows
everything is on fire all the time. Um,

and our job is to continue building the
tower higher and higher to try and get

away from the flames. Ah...
(Audience laughs again)

This is called the hierarchy of
abstraction. Ah, so as good information

hiders, we're trying to isolate the
terrible things happening down below

from the good things which our customers
think are happening.

Ah, and ideally it works. Ideally
customers continue to come to the

site. They make requests. Data flows
properly. Even though nodes internally are

failing and bad things are happening to
the network. That's the goal.

What kind of bad things am I talking about?
Well, if you've ever used a queue or a

database or any consistency system
whatsoever, ah, you know they can get into

split brain scenarios, where different
nodes believe different truths.

Or there might be foreign key problems,
where you go to look up a record and

it's gone. Or maybe you see read anomalies,
where you go to examine a record and,

ah, maybe you do a write, and you do a
read, and it's not there. Then you do

another read, and it comes back. You do
another, and it's gone. Right? Interesting

flip-flops in state can occur.
So, in the face of these problems, we want

to know, how likely are they to actually
affect our systems? Our--is our use of the

database correct? Is--is our software
likely to show these problems to users?

And the only way to do that is to measure
them. So Jepsen is a project I'm working

on to understand distributive systems
better. Ah, it's--it's code-based, it's

articles, it's talks, um, trying to put
pressure on vendors, trying to educate

users, uh, and figure out for myself what
consistency actually means.

In Jepsen, we take a systems-based
approach. Um, what is a system?

Well, anything you can put a box around.
Ah, which means pretty much everything

is a system. Ah, inside of the system
we're gonna have some interacting

components. Ah, they're gonna have
complicated and nuanced, um, things

happen between them. But our goal is that
if we draw a box around the system as a

whole, we should be able to characterize
what goes on inside the box, just based

on the interactions it has in its
environment. And hopefully these

interactions are simple. So at the edge,
when we're pushing things into a system

and taking things out, we should have
simple rules, like, maybe matter is

conserved, or maybe [format] is conserved,
or maybe if I put things into a cube they

come out again. Maybe if I write data into
a database, it should still be there in a

week. Those are simple, high-level rules.
And then internally, the database can do

whatever kind of locks and transformations
it wants to make those things happen.

Thinking about invariants for a minute--
like what sort of rules, what sort of

high-level properties could we want. We
might think about a simple program, right?

Like allocating a variable X set initially
to A will read the variable by [printing

it, that prints out] A, right, then we'll
say X equals B, print X. We all

know what this does, right? We've written
a program like this before.

What you think it does, is we start off
with a state A and we read it. And then

we'll change the state to B by performing
a write. And then we'll read B.

So we'll print A and then B.
Straightforward enough.

But this is not the only possible
interpretation of this program.

We could read B. We could read A. We could
do anything. The program doesn't have to

obey any laws unless we tell it to. So the
invariants in our head map the program's

structure--the sort of lexical structure
of the process--to the behaviors

which it's allowed to undergo.
Invariants are constraints that

apply to the history of the system. Like
what--what possible orderings of states

could we see? What possible ways could the
operations come together?

We might think about not just a single
thread of program, but a concurrent one,

where multiple processes interact with the
state at the same time. So here the top

process, ah, reads A and then B. That's--
that's crazy! Why did it change? Well,

it changed because a process on the bottom
performed a write with the value B. So

individual processes may not have the
whole story. But if we unify the whole

history from every process, we should get
something that follows the same rules.

But it's a little more complicated than
that because our systems aren't just

concurrent. They're also distributed. Now,
distributed systems have some

characteristic difference or some
characteristic distance between nodes.

It takes time for messages to propagate.
If I want to write a value to a register

in [D-Ram], I have to go off of the CPU,
into the memory controller, through a

bunch of caches, back onto some wire, like
eleven whole centimeters over in the

D-Ram, into the actual bit, and it flips.
And that takes, like, what?

A nanosecond? So then I have to come all
the way back, and that takes more time.

So whenever we're manipulating state
somewhere, it's gonna take a little bit of

time to go back and forth. And that time
means that things might be ambiguous.

We could see different orders. For
example, if I do a write of B, and I

concurrently begin a read, and then the
write completes, and the read completes,

one possible ordering, depending on how
those messages propagated, is that I see

the value B because the read arrives after
the write. But it could also see A if the

read arrives first. A or B. A or B. All
that changes is the ordering of the

messages. In an asynchronous network,
like the ones that we're usually working

with in IP, ah, we don't get to control
what those ordering are. So both,

both histories are valid. We have to
consider all possible interweavings with

the current operations. But it's not
infinitely bad because we're not allowed

to break the laws of physics. We can't go
back in time. If we're actually talking to

a single point of truth somewhere in the
system, then the earliest possible state

I could interact with is the one just
after I send my request. And the latest

possible state is the one just before I
receive a response. So you get some window

between invocation and response.
And that's the range of states we can

interact with. This property is
called linearizability.

And it's kind of the "gold standard" for,
um, both distributed and concurrent

systems. You want to have, ah, things like
atomic registers, like [u-textes], that

give you real-time guarantees on the
states you'll interact with.

And in u-text, when you lock it, nobody
else gets to claim it until you release it.

That's a really nice, strong property.
So when linearizability means that any

operations that are not concurrent are
ordered back to each other. It's not a

total order, right? We can still have
those windows of concurrency where

you could get A or B. But that only
happens when two operations overlap

in time. And that means that if I do a
write and the write completes and then

I begin a read, because those two aren't
concurrent, the read is guaranteed to see

the write, or some later state. So
everybody's gonna agree on the same order

events. We all see A, B, C, D. Everbody's
going to agree on when an operation is

visible. Once you've completed an
operation, you know everybody else is

gonna see it. And this means we get nice
invariants like no stale reads, like

mutual exclusion. Lots of systems rely on
these properties. But we don't have to be

that strong. This is a really rigid thing
to do. We could relax the time

constraints. We could let you go
backwards and forwards in time.

You could read something from the past and
write something from the future.

Well, how do you write to the future?
Well, you put your message in a

bottle and throw it in the ocean and
somebody else picks it up. Ah, if your

ocean is well-ordered, as mine is, um,
then this works just fine. Everything

arrives in order at your recipient, ah,
maybe on a different coast, and they apply

your operations, and they see the same
history of messages. They just see them a

week later. So all participants are going
to agree on the same order events.

They'll all see A, B, C. But they might
not agree on what time those things

happened. We can relax that invariant
still further. If you're thinking about a

transactional system, um, with lots of, um
different cells interacting, maybe like an

[SQL database], what do you give a
property like serializability?

Where we say that every transaction has
to fit somewhere into a single linear

history. But we don't have agree on when
it happened or even in what order.

Just as long as you can squeeze the
transaction somewhere.

So, in a serializable system, operations
happen in an order. We don't know

what it is. It's perfectly legal, for
example, in a register, to put all of

your writes to time infinity and all of
your reads to time zero and just have

[dev null] be your database. Um, that
doesn't seem very useful, right?

But it's a sort of trivial solution. If
you have a more complex system,

like an SQL database, where you're using
something like, "set this row, this

particular column, to be three if and
only if this thing plus that thing is

equal to this other thing when the time
is whatever. Those constraints are

actually a lot more difficult to preserve.
And so you get a stronger invariant out

of it. Finally we don't have to just have
a single line of history. We could

actually have a forking, diverging
history. In eventually consistent

systems, the constraint is that things
have to come together somehow.

So if we have a counter that's value is
zero, that counter could diverge. We could

have two distinct copies of it. And each
one of them could increment separately

and return one. And reads would show
one for a while. And then when the counter

has exchanged information, the value will
converge on two. If we do everything

right. So, eventually consistent systems
have to converge, and what that

convergence does, doesn't just mean they
have to agree on some value. Ideally they

should converge on the correct value. So
the correct value might be the most

recently-written value in the register.
The correct value might be a number

of increments that have occurred. It
depends on the semantics of the data

type that you're working with. Finally we
could imagine the variance to just order

two operations. Like a write and write or
a write and a read. And we get this family

of monotonic writes, monotonic reads,
writes follow reads, reads [yield] writes.