All right, for those of you who may know me, and I know that there are a few in the audience
who do you know that I am, in fact, not Alfonso.
Unfortunately, Alfonso couldn't make it, so I'm jumping in for him.
So today, we're going to be talking about random seats and state machines, and basically
I'm going to show you how we employ in something called deterministic simulation testing
at polar signals in rust.
We've actually done this before and go as well.
If you're interested in that, you can come and talk to me afterwards.
But long story short, we ended up building a new database.
And if you're interested in that, you can check out Tours Talk from yesterday in the database
room where he talked about, you know.
The decisions that went into that, the technologies, and so on.
If you don't know at all what deterministic simulation testing is, that's okay.
We'll go over everything.
But before we dive into the details, I want to kind of set the setting why this is interesting,
why this is useful.
And for that, we do actually have Alfonso joining us.
So basically, a couple of years ago, Alfonso worked at a different database company.
We're not a database company, but we happen to build one.
And there is a bug that he had been assigned to that was incredibly hard to reproduce.
It only ever produced and very, very large machines over a very long period of time.
So, you know, we probably all have been in this kind of situation in our careers that we had
bug reports that were very, very hard to reproduce.
So, that's ultimately kind of the setting of all of this.
And Alfonso was trying to reproduce this with really expensive machines.
And he thought, you know, I can just add a little bit of latency here and there and I'll
tickle out the bug.
And he thought he reproduced it, but it turns out that was actually not it.
It was just a fluke, and it could not really reproduce it.
And so, you know, time goes by, you can reproduce this bug.
And, you know, other priorities come up.
You can still not reproduce this, so eventually, you know, you just kind of kind of give up.
And your organization says, nobody can reproduce this.
We have other work here, so I'd rather have you work on this other thing.
So, ultimately, you know, the way we can think of this is, there's this bug down here,
the red dot, and there's this, you know, very high dimensional state space that can
possibly reach this bug, or possibly not, right?
And so, there are a gazillion combinations of things that may cost this bug, but ultimately
what we want is one reproducible path that will always deterministically lead to this reproduction,
right?
That is the wish that we all have that we can actually reproduce these really difficult
bugs reliably.
And so, the true problem about all of this is randomness.
The world is random, right?
Like hardware fails randomly.
Users behave in random ways.
There's a bunch of things that is completely out of our control, but it is a reality that
we have to work with.
And so, this is the reason why these things are so freaking hard to reproduce, right?
And then even if we do reproduce, sorry, if we do, if we do manage to find the fix for
this bug, we still can definitively say that we have actually, in fact, this bug, right?
If we can't actually reproduce it, how can we ever say for sure that we have, in fact,
fixed it.
And these bugs can be really expensive, right?
We saw a funzer earlier, he spun up, you know, 16 of these really expensive machines,
and the company happened to allow him to do this because it was a very high priority bug
at the time.
And so, companies and, you know, individuals end up spending a lot of money on bugs as
well, potentially unnecessarily.
And eventually, this can cause, you know, unhappy customers, unhappy users of your software,
if you simply cannot, can never fix these bugs because you can reproduce them, and ultimately
fix them.
So, deterministic simulation testing is kind of the, one of the answers that we believe
can help with these problems.
And this was originally kind of popularized by FoundationDB, and the way that FoundationDB
kind of went about this is they built this actor framework in C++, where they, and they built
this framework specifically such that they built and accompanying simulator that they could
simulate all of these failures and, and, and ran them way, it's, right?
And so, that spark kind of, a number of companies to try and go up and do this themselves,
Tiger Beatles, fairly popular for doing this, but there are a number of companies that maybe
we haven't even heard of the, the storage team at Dropbox actually did this in the early 2010s
already as well.
A bunch of other companies have started started to do this, and a quick shout out to
businesses as well.
They basically, when one step further, they're the folks that originally did this with
FoundationDB, and they've built a deterministic hypervisor so that you don't actually
have to care about any of this in your application, and you can kind of try and explore
this state space, the deterministically using their hypervisor and then also replay it
deterministically.
It's mind-blowing technology.
Anyways, we're far too poor to pay for, for, for businesses, so we thought, you know, if
we're already building something from scratch, we think we can build a simulator for ourselves.
And so ultimately, there are four ingredients of randomness that we end up needing to control.
The first one is event ordering, and ultimately what this means for us, and this is also
one of the reasons why we ended up choosing Rust for our new database, is we need to be
able to deterministically genuinely, deterministically execute an order of events in our system.
And what that means is concretely on hardware is that for our simulator and our simulation
test suite, they only to run on a single thread, because the moment that we go multi-threaded,
we're already not deterministic anymore.
And so, you know, in the very concretely what this means for our Rust application is that
we use the like single-threaded Tokyo executor to make that happen.
And then randomness, you know, very concretely, this can be random number generators,
but also I'll go into this a little bit later.
They're like implicit things that, you know, cause randomness as well.
Time is a really difficult one, and this is one that we found was particularly difficult
to control if it's not something that you think about from day one of your application,
because, you know, if you end up calling, you know, time, time now somewhere in your program,
you've kind of already lost, right?
Like you need to be able to kind of see the time throughout the entire program.
And then the very last thing, and this is ultimately how you end up really tickling out
all the bugs of your code, you can randomly inject failures into in this simulator at any
point in time.
So once we can control all of these, we can actually build a test suite that we run
against our system, we check some invariants about our system, and we can, you know, randomly
control what happens.
And so how do we structure our code to make that happen?
So ultimately what we do is we have to relatively simple trade, the state machine, that
implements the receive and the tick function.
And ultimately, receive can be, you know, a response to any request that any other state
machine may have produced, or a response to a request that a state machine has done.
So, you know, let's say the state machine wants to do a request to some external system
or something like that.
So that way we can kind of control everything that happens external to the particular component.
And tick, you know, either is there for periodic work generation.
So, like, you know, some component does something on a schedule, but also, you can use it
to kind of trigger timeouts and stuff like that.
And the reason why we want this to be kind of separate is so that we can actually control
this time component, right?
And we need to always think about that these are state machines.
So, like, every time that we call any of these functions, we mutate the state machine in
some way, and output some messages to be consumed by others.
And so that is actually something that Tyler Nealy of this led project, originally kind
of came up with this trait for sled as well.
And so we kind of just tried this out and happened to work quite well for us as well.
So again, kind of taking a quick step back, why do we do this?
So, we had two talks, earlier this day, today, in the rest room, we basically build a
profiler and we built this database as a back end storage for this profiler.
And then yesterday, we also had a talk in the database room, which happened to be in this
room as well, that, you know, talks a little bit more about the architecture.
But this talk is really just about how do we test this database, right?
So, I just wanted to give you this in case you're interested in why do we do all of this.
But on a very high level, the way that our system looks is that we have clients, clients
push data, we have a component that we call the ingestor, that kind of buffers up data,
and then ultimately flushes it to object storage.
And then synchronously, there is a compaction component that regularly compacts data.
Again, this isn't like the real, they're like a handful more components in the real system,
but conceptually, this is how the system works, right?
And so, the way that this end works in production and in the simulator is as follows.
So, the simulator is essentially just a message bus.
We saw that with our state machine interface, everything consumes and produces messages, right?
And so, these are just messages that then go onto this, are cute into this message bus.
And all of the components that we see here are just state machines.
And in production, we have a separate driver for these state machines that actually take
on a real interval, actually work with real networks, et cetera.
And what's kind of nice about this is also that we can use a state machine to represent
external components.
So, obviously, we're not in writing the code for a GCS or S3 or something like that,
but we can write a state machine that kind of acts as if we did, and we can control
various failures and behaviors of those components, even if we don't fully control them.
And so, like I said, work is produced on a tick and then transformed on receive.
So, let's do this, I'll give you a real example of what this would look like in our testing
harness.
So, here we can see we've kind of initialized our queue with a bunch of ticks of our client.
And again, our client is also just a state machine.
And so, we tick and the client does its mutation of the state machine and ends up producing
a new message onto the message queue.
So, now the client says, I want the ingester to receive a write.
And so, then the other components actually go about and receive this message, process it,
and so on.
And so, that's how, ultimately, we can produce a set of events in our system.
And we can already see kind of, since we control this entire thing, I did this quite
quickly, but like we can also, because we control all of this, we can reorder events randomly,
we can drop events, right?
Like we can do all sorts of interesting things that would be incredibly difficult to reproduce
in a real environment, right?
Potentially, potentially, we're testing even things that maybe are completely impossible, right?
But maybe it's this one thing where something needs to be shut down for three years, and
then come back online, and we can test all of those things.
So, yeah, randomness, like I said, is something we need to control quite tightly, and something
like this, and more generally, we need to write our entire system to be deterministic, right?
So, this is something that's quite tricky to do, and so, obviously, there are kind
of two kinds of randomness that would need to broadly care about quite deeply.
One is, you know, I think the really obvious one, random number generators that are
actually used by our software, that, you know, choose what next thing to execute or something
like that.
I'm obviously making something up, but, and the other thing is things that are implicit,
so like hash map iterations, maybe different the next time that we run the same code,
then it was the last time.
So, we need to take a lot of care that, you know, every execution is actually deterministic,
and every execution of the same input events will actually produce the same outputs.
And so, one kind of neat trick that we found to ensure this is that we actually can test
determinism, because what I've just said is, for the same inputs, we always must be getting
the same outputs, and so, what we just do is we run the test harness with the same seed
multiple times, and if that ends up generating a different set of events produced by those
state machines again, then we've just proven that our system is in fact not deterministic,
and then we can go and try to fix that determinism, right, so that we can make sure that
when we do get a failure, it is actually deterministically reproducible.
So, like I said, some of the, some things that we can do with deterministic simulation
testing, because we control all of those four variables, including time, is we can say,
you know, an ingester is supposed to tick, but it's actually only going to tick in six
years, or I guess in five years, right, something that would be incredibly hard to do
in real life, right, like how, who in their right mind would wait for actual five years of
a production machine being online to test something, right, whereas for us it's just saying
this tick has happened in five years in the future, and so this is really cool, because all
the sudden we're no longer constrained by, like, real time, right, we're only constrained
by how many CPU cycles can we actually run on a machine, right, and so what that means is we
can simulate, you know, tens or hundreds of years of production sequences of events, every
single day, right, and so this allows us to then find if there are any sequences that are, you
potentially harmful for our system. So once again, let's look at an example of what could be
interesting to simulate here, or what are the interesting things that are simulator might
end up simulating, because, again, we originally randomly seed our simulator to try and explore
random sequences of events, right, so one of the things that we could have is that, you know,
we have on our message buzz, this message that our object storage is supposed to persist something,
right, so one of the things that we can do is actually just say, this never happens, so ultimately
what that means is the ingester should eventually retry, right, but another interesting that could
happen is the right actually succeeds, but the acknowledgement is dropped, right, so all of these
things, at any point in time, our simulator can decide, you know, now I'm not going to deliver
this message, or now I'm going to restart this component, it's going to lose all of its state,
and our system needs to be able to ultimately recover from this, and at all points in time,
the invariance of our system might help must hold true, like snapshot isolation and what have
you that we want to make sure are always true about our system, so I've talked a lot now about
kind of the result or the ingredients that go into it, so what are some of the things that we found
with this, so we've found some pretty devastating bugs using this methodology, so we found
duplicate data being persisted in our system, we found cases of data loss, we found partial
commits, we found random crashes of our system that shouldn't have happened, right, just about everything
that you could possibly think of, and just so that you can actually visualize what this looks like
in our CI, all that happens is that we generate a random seed at the start, we run our test
suite with this random seed, it originally seeds our message queue with a number of actions,
and then we just kind of let it go and do a thing, and like I said, we test a bunch of
invariance about it the entire time, and if ever one of those variants don't hold true,
we've found a bug, and one of the things that has been really interesting about this is that we
actually have this true sequence of events, right, but it turns out this can be a lot of things,
right, like we originally seeded with 64 events, but you know potentially hundreds of things can happen,
and it can be quite difficult to understand what is the thing that has actually led to this bug,
right, like yes we can now we're able to reproduce it, but still understanding what led to the
bug is yet another thing, so one of the really cool things that we found to be really useful
is that we have a sequence of events, right, so we can actually visualize this for you know
our small tool humans to actually understand what has happened, so I'm just have a random example here,
where we can see you know we have random sets of clients, random sets of ingestors,
that all end up talking to each other, we have a random restart in the middle that happened
and so yeah, this is just a random example of what you know a sequence like that may
may look like, I'm going to have to go relatively quick, but like I said we've kind of tried this
before and go, and with go what we had to do we kind of had to do you know unspeakable things
to the runtime to make it deterministic, and that that did work, and it is kind of easier to do
actually because once you make the runtime the deterministic you actually sort of get all the benefits
out of that quite easily, however debugging with these state machines ends up being a little bit
simpler, but one thing that definitely can be understated is changing your mental model about
your system to always have to be within state machines is very different from the kind of you know
suffering engineering that we've been exposed to before. I personally do think that this is a good
thing because we always do think about the ultimate mutations in our system, but it can be quite
difficult to kind of map what we want to do onto these state machines, and the simulator itself
is actually really hard work, like it is software that needs as much care as any other test
suite, any other software, so like if we start to neglect this it you know starts to start to show
just like any other software. So yeah, the ST is not magic we need to put a lot of thought into it
we thought about you know is there something better that we can do than just random seed that we start
start with maybe we can start at some interesting state and then start to explore from there
or we've previously determined this state is interesting and everything from there could be
interesting to explore, right? There are a lot of things that can definitely be done. I said
that I already said that we sometimes have to deal with a huge number of events and figure out
what was the actual sequence, well we actually control the simulator, right? So we can try to shrink
to the minimum amount of events that need to happen to actually reproduce the same
same state, we call this the shrinking. So yeah with all of these ingredients and a lot of hard work
you know we try to get rid of any unpredictable bugs and try to not have you know very critical
bugs like this ever hit production through this testing. Thank you.
Questions? We have a couple of questions.
Thank you for the talk. I have a question when you have a specific seed. Can you speak up? I can't
hear. If you have a seed that triggers a specific issue and you fix your state motions
or can you ensure that the fix is correct because the seed will not match the new state
machines to trigger the bug? Yeah great question. So basically you're saying how do we make sure
that when we change the code that we're actually testing the same state space? So I mean we can
test that by making sure that the log is the same, right? So if we actually do have the same
the same sequence of events then we know that it is in fact the same thing. Obviously only
leading up until the thing where we've proven that the invariant was violated, right? Does that make sense?
I think you can have to talk outside because it's very interesting. Thank you very much.
Thank you very much.