Hello everybody, thank you very much for being here today, I am Dominic Torno, I am the founder
and CEO of Resonate where we focus on a distributed async of eight, programming model,
to make distributed applications did simple. I am also the author of Think Distributed
Systems, which is currently part of a many publications early access program. The book focuses
on dependable models to empower you to reason confidently about distributed systems. I spend
most of my time on distributed systems and distributed systems are known for their complexity.
We all just know that distributed systems are really, really complex, but what edits core
makes distributed systems so complex and there are two reasons, two fundamental sources
of complexity. The first is non-deterministic partial order introduced by concurrency.
In a distributed system we do not know what happens next and the second is non-deterministic
partial failure introduced by distribution. In a distributed system we simply do not know
what will fail next. So as an aside feel free to take pictures throughout the presentation
and I have marked some slides as a harm moment to highlight what I think are like the most
insightful slides of the presentation. This is one of my favorites. Now let's consider a simple
very abstract example to develop an intuition. We have two processes, P and Q, each consisting
of three atomic actions, three steps. So first let's introduce sequentiality. The defining
characteristic of sequentiality is total order and total application. A sequential system
executes one step at a time in a predetermined sequence. So consequently the sequential
composition of P and Q leads to exactly one possible execution. There is no room for alternative
behavior. But then we introduce concurrency and the defining characteristic of concurrency
is non-deterministic partial order. So consequently the concurrent composition of P and Q already
leads to 20 distinct steps of possible executions. And then lastly let's introduce distribution
and the defining characteristic of distribution is non-deterministic partial failure. So consequently
the distributed composition of P and Q leads to 69 distinct possible executions. And in a real
system some of these executions are very common while others are exceedingly rare. So for example
imagine a scenario where a server accepts a connection at the exact moment a configuration reload is
a highly unlikely sequence of events. So now let's do a simple thought experiment given that we
have 69 distinct traces. So let's assume 10% of these traces are the happy path. They occur 90%
of the time. And 90% of these traces are edge cases. They only occur 10% of the time. It turns out
if we non-deterministically pick a trace according to this probability distribution one thousand times
the chances of missing at least one trace are almost 100%. So these rare traces provide the ideal
breeding ground for the dreaded heisenberg. The term heisenberg is inspired by the heisenberg
uncertainty principle from quantum mechanics. Heisenbergs are elusive. The rarity of the traces
that height them makes them really hard to produce. And by the off chance we actually produce one
it's almost impossible to reproduce them. And now take a moment to imagine the behavior space
of a real world distributed system where dozens or even hundreds of processes and each of these
processes has dozens or hundreds of steps. So the number of possible executions grows combinatorially
and that phenomenon is aptly called behavior state explosion. But concurrency and distribution
they don't just expand the behavior space. They make reasoning about a system almost incomprehensible.
Concurrency and distribution introduce daunting uncertainty. And this uncertainty is the true
challenge we face when we design distributed systems. So there is a direct correlation between
certainty and confidence. When I am certain about my application I am confident in my
application's correctness. So making changes adding new features or even deploying to production
on a Friday afternoon no problem. With deterministic simulation testing you have a key component
to achieving this level of certainty and confidence by methodically exploring the behavior space
scaling across space and time. So throughout the rest of this presentation we build a foundational
understanding of distributed simulation testing step by step. And then we build a dependable
mental model so you can all decide with confidence if deterministic simulation testing is the
right approach for you. So let's begin by grounding our discussion with a mental model of
software systems. For our discussion we will think of a software system as being partitioned
into two distinct entities. The environment and the application that is the highest level
system model that is universal applicable. What's in? What's out? The environment represents
everything that is not the object that we are developing and testing and the application represents
everything that is the object that we are developing and testing. Now our goal is to test the
application. To achieve this the application under testing conditions must closely resemble
the application under production conditions. Any deviation must be non-material otherwise we're
risking to test something fundamentally different. However our goal is not to test the environment.
The environment is only a means to facilitate the test. So therefore the environment under testing
conditions does not have to resemble the environment under production conditions at all. We are
free to replace completely mock any component in the environment as we see fit. Now question is
how do we delineate between the environment and the application and there is no universal answer
where you delineate depends entirely on your requirements. So here we see an example of a web
application composed of three distinct components. A client on the left of web server in the
center and a database server on the right. A reasonable choice is to assign the client to the environment
while treating the web server and the database server as part of the application. The focus is on testing
the web server and database server in composition. But a reasonable alternative is to assign both
the client and the database server to the environment and treat the web server as the application.
The focus then is on testing the web server and isolation. Now now that we have a mental model
of software systems, then is a software system correct and how do we establish the correctness
of a software system. Correctness is not absolute correctness is relative to a specification.
For example think of your parents. I bet most of you had at least I had one parents who is
strict and one parent who is more lenient. So the very same behavior my behavior one parent usually
my mother she would scold me for it whereas my dad would cut me some slack. So the same
implementation can be considered correct or incorrect depending entirely on the specification that we
choose to apply. Now as Leslie Lambert explores in his foundational work specifying systems,
software systems can be understood as state machines. Right. The state machine is remarkably
simple but very powerful reasoning tool. A state machine consists of three components, a set of states,
set of initial states, you just want and a next state relation that determines how we transition
from one state to the next. When we execute a state machine, the state machine generates a trace,
a trace is the sequence of states that represents the systems behavior over time.
Traces are at the heart of how we reason about software systems. Each trace represents a unique
execution of the system. Now a state machine is non-deterministic, if it presents a choice.
Right. Or in more sinister terms, if it presents some ambiguity. So in this example from S1,
we may transition to S2 or to S3. This is reflected in the set of possible traces given the
initial state of S1. In this example from S1, we may generate two distinct traces,
S1 to S2 or S1 to S3. So given the same initial state, we may witness different traces.
The state machine is deterministic. If the next state relationship is a function,
that is if the state machine does not present any choice. In a deterministic state machine,
there is no ambiguity, just a single predictable path forward. And this is also reflected in the
possible traces given the initial state of S1. So in this example, in S1, there is only one
trace that we can possibly generate. That is from S1 to S2 to S3. So the same initial state,
we will always witness the same trace.
Or coming back to the specification and implementation relationship that we discussed earlier,
in effect, a specification is a set of traces. These traces represent all the valid behaviors
allowed by the specification. So an implementation is correct with respect to a specification
if every possible trace of the implementation is also a trace of the specification.
And consequently, an implementation is incorrect with respect to the specification.
If some traces of the implementation are not traces of the specification.
So how can we establish correctness? There are two possibilities. There is software verification
and there is software testing. Software verification aims to prove that all traces of the
implementation are within the specification. Software testing aims to find and software testing
so in software testing aims to find some traces outside of the specification.
So in summary, if the verification asserts, the system is correct.
So the verification asserts, there is no correctness violation. No correctness violation
will ever occur. If the test asserts the system is correct, the test merely asserts
that no correctness violation has yet occurred. We may find one later.
So testing is essentially a search problem. We are the goal is to find traces of the
implementation that violate the specification, that violate correctness.
Now how can we increase the confidence in a system's correctness?
By increasing test coverage, and test coverage has two key dimensions, space and time.
So to scale across space, we extend our test by extending the number of distinct traces
covered by the test. And to scale across time, we extend our test by increasing the length
of distinct traces. However, extending the number of distinct traces is difficult.
Remember our initial example and our thought experiment randomly stimulating the system
will just produce more of the same. If we run the test a thousand times,
about 900 times, we will just test the happy path. And we will omit a lot of the edge cases
that are the ones that hide the bugs, especially the heisenbergs. Now additionally,
extending the length of distinct traces is also difficult. Many systems have actual timing
constraints. There are timeouts around crash detection, for example. There are timeouts around
message loss detection. We allow the other side to respond within 10 seconds, within 20 seconds.
For example, the time intervals driving rate limit algorithms. There are time intervals
1 minute, 5 minute, 10 minutes. So increasing the length of trace increases actual testing time.
Now deterministic simulation testing enables you to scale across space.
By controlling the scheduling and the failure injection. And therefore increasing the number
of distinct traces. Instead of blindly picking from the happy path, we are intentionally picking
from the edge cases. And on top of that deterministic simulation testing enables you to scale
across time by virtualizing time. And therefore when we increase the length of the trace,
we do not actually increase the length of the world clock time. It takes to run the trace.
And lastly, and that is one of the key achievements of deterministic simulation testing. And also,
the defining characteristic deterministic simulation testing enables you to reproduce a trace.
By ensuring that for every single starting state, there is only one possible trace
through the system. So once you find a bug, you can reproduce that trace by putting the system in
the same starting state. Now to be methodical and to ensure reproducibility, we construct the system.
So that is we construct both the environment and the application so that the behavior of the system
only depends on the initial state of the environment and the initial state of the application.
Now the core idea is to substitute the environment with simulator. Remember, we are allowed to replace
any component of the environment that we see fit. Deterministic simulation testing repeatedly
executes an application in a simulated environment under changing initial conditions. Monitoring
that the correctness constraints are maintained across all executions. And in practice,
that means constructing the system to control otherwise non-deterministic factors.
Like for example, incoming requests, but also crashes, message losses, and of course time.
So on a high level, we have to think about implementing this simulator. We have to think about
two core interactions. Requests from the environment to the application and requests from the
application to the environment. The first represents the application input and output. Think of for example
the web client in our initial example. And the second represents the application side effects,
like talking to the network or reading and writing to the file system. Here, think of the
database server, the initial example. Now by controlling, scheduling and failure injection in the
simulated environment, given a deterministic application, we can deterministically generate
an arbitrary amount of distinct traces of an arbitrary length. Now, who is doing deterministic
simulation testing today? Deterministic simulation testing is still fairly new and it is also
still fairly involved, because making sure that your application itself is deterministic and
then building a deterministic environment for it is quite an investment. But a few companies
have adopted deterministic simulation testing. So for example, foundation db. It's widely
regarded as the trailblazer in deterministic simulation testing. Tiger beetle db, wildly
regarded as the one that spread the word about deterministic simulation testing. And then we have
others like for example polar signals, tools or my company resonate. Each project though took
a different approach in designing and developing its application and designing and developing its
simulator. So there is very little common ground. There are no ready-made libraries.
But additionally, there is antithesis. That is the first company that offers deterministic simulation
testing as a service by implementing their own deterministic hypervisor. Now, if you're curious
about deterministic simulation testing and would like to dive deeper into deterministic simulation
testing, the nuances and also how to structure a simulator. You're on the CEO of Tiger beetle and
I will host a webinar this Thursday discussing deterministic simulation testing in depth. So if you're
interested, please join us. And so as a conclusion, deterministic simulation testing requires a
real investment. However, the pay off based on like personal experience is significant.
Deterministic simulation testing enables you to methodically test the behavior space of your system
by scaling across space and time, making tests and traces reproducible. So then you get to
squash the highs and the highs and the highs and the highs. And with that, thank you very much for
extending my talk. I just want to let you know that mining publications offered a discount on my
book for the first time. If you are interested, and once again, thank you very much and I
hope you enjoy the rest of the conference.
Yes, please.
So at some point in your conclusion, this long talks work on TLA plus?
Yes, actually work with bulletin shaking. That is a very nice question. So
the question for anybody who couldn't hear was about TLA plus a temporal logic of actions
that was discussed in the book that I refer in specifying systems. And
it's a language to specify systems and it comes with a tool for model checking.
So it can also methodically test the behavior space of their model. But there is where the difference
lies. In TLA plus, you specify your system, but it is a model. It's not the implementation of your
system. So there you model check and that's basically deterministic simulation test. You model
check the model. With deterministic simulation testing, you actually model check if you
so say, you actually model check the implementation. So that is where I think one can draw a good
line, good mental model for that. Yes, please.
Mm-hmm. So for model checking, I am not an expert in implementing model checkers,
but for model checking as far as I know, they have a very methodical exploration of the state space.
And what they also on top of that, what they can do is basically they calculate what's
I believe called symmetry sets, where this basically is equivalent to that, therefore I completely
skip it. So that is something that for example, for our simulator that we implement, we do not
actually implement an actual search algorithm. So what instead, what we fall back on is basically
the small world slash small data hypothesis that the most interesting side effects come about
when you have a lot of need for coordination and content in your system. So therefore instead of
like firing off 10 requests over a thousand accounts, for example, right, we fire off 10 requests
of a thousand requests over 10 accounts in order to make sure that there is a lot of conflict in the
system. And without we were able to find a lot of the really interesting bugs, even without a
guided search. But I know that antithesis, whereas I'm not an expert in antithesis, but a
tithesis has a few APIs that you can include in your application to actually guide their search.
So with that, you can more methodically find the interesting, the interesting traces.
Thanks a lot.
Thank you.