(energetic electronic music)
- Hi, I'm Pantazis Deligiannis.
I'm a senior research engineer at Microsoft Research,
where I have been working for the last four years.
Before joining Microsoft,
I did my PhD at Imperial College London,
where I was researching new techniques
for automatically finding concurrency bugs
in distributed systems.
At Microsoft Research, I'm part of a team
that is designing and applying
such automated testing techniques
on cloud services developed in Azure,
to make them more reliable.
So together with my MSR colleagues,
we created Coyote,
which is a .NET library and tool
for writing concurrency unit tests in C#.
Coyote provides APIs for writing these tests,
as well as program specifications,
and declaring sources of non-determinism in your program.
The tool focuses on task-based concurrency
and is able to take control of the task execution
during testing.
Coyote also provides advanced APIs
for writing and testing asynchronous actors
and state machines.
In the core of Coyote is a scheduler
that enumerates interleavings between tasks
and is able to replay any bug that is found by the tool.
And the secret sauce behind this technology
is efficient program search algorithms
that are able to find most bugs.
We should say here that Coyote
is not doing verification.
Instead, the program search is a best effort
in finding bugs under a given bound.
But what we have found in practice
is that this works really well.
Coyote is the result of years of research, engineering,
and deep engagements with internal product teams.
It is being used so far
by more than 15 critical production services inside Azure.
This includes services that manage
hundreds of thousands of customer VMs.
So it's really important that they operate reliably
and have no bugs.
We released Coyote as open source last year in March,
and hope that everyone writing such systems
can learn about Coyote and take advantage of it.
Let me give you a motivation of the problem.
Concurrency is a fundamental paradigm of computer science
and many software systems critical to the success
of companies like Microsoft are highly concurrent.
These systems include microservices,
such as the one that you can see here.
This example here is a typical service developed on Azure.
It was designed with an ASP.NET
microservice architecture
that allows it to scale horizontally
on a Kubernetes cluster.
The service can receive tens of thousands
of client requests at the same time,
and must carefully synchronize data accesses
in backend storage systems.
So how can we use Coyote
to test the correctness of the system
and ensure that we find all critical bugs?
This kind of bugs that we really do not want
to manifest in production
because they could lead to serious issues
such as service downtime or loss of customer data.
And who really wants this to happen in their service?
Today, developers rely on techniques
such as stress testing to weed out concurrency bugs.
However, these techniques are often ineffective,
with bugs escaping into production
and only manifesting in live sites,
making them very painful to debug.
But why is that?
Why concurrency testing is so much harder
than sequential testing?
So testing concurrent code should not be so hard.
And we believe that every developer, to be productive,
should be able to write unit test for concurrent code,
as simple as writing regular unit tests.
Welcome to Project Coyote.
We have been working on technology
to enable exactly this capability.
Let's first look at very simple example.
Here you can see sequential dictionary
with a simple set of APIs.
You can add a key in its value.
You can check if a key exists.
And you can remove a key.
Now the dictionary is not thread safe,
so threads are expected to take a lock
before they try to access the dictionary
to avoid race conditions.
Now, since the internal implementation of the dictionary
is sequential, someone could test it
by writing a simple test
like the one that you can see here on the code.
For example we could try
to add a few keys with their values.
We can then remove a key
and then we can assert that the key was indeed removed.
Okay, this was easy.
But what we do for a concurrent dictionary
as the one that you can see here,
which by design can allow a large number
of threads to access it at the same time
without holding a lock.
The underlying implementation of the dictionary
must make so that in the presence of concurrent accesses
the dictionary will still work as expected.
And for example, it will not end up losing values
or keys due to race conditions.
Now, how do we test this?
If we try to write a sequential test,
like in the previous example,
like the one that you can see here on the code,
it will not be really enough to cover corner cases
where the dictionary is accessed in parallel.
Hmm. What if we try to write a concurrent test
like this one
which spawns a bunch of tasks that access the dictionary
at the same time.
This seems like a better idea, right?
So the problem is that it is not guaranteed
that the tasks will execute in the right order,
that would cause a bug to manifest.
And let's say that we try to write a stress test
that tries to spawn like tons and tons of tasks
to stress test the dictionary.
We might actually find the bug,
but how do we replay
the same exact task order that led to the bug,
since we don't really control the execution of these tasks?
And this is where Coyote helps.
Coyote controls all these tasks
and other sources of concurrency in your program
and is able to explore the many possible execution paths
to discover concurrency bugs.
Okay. Let's see how you can use Coyote
to test the system that we saw earlier.
So Coyote allows you to write
what we call a concurrency unit test.
This test looks very similar to the one
that we saw earlier for the concurrent dictionary.
So what is happening here in the code,
is that we can first initialize the state of the test,
which includes mocks of external components,
as well as components of the service that we want to test.
Next, we spawned a bunch of concurrently executing tasks,
each one performing some request on the actual service.
Finally, we can wait for these tasks to terminate
and then assert that the state of the mock is consistent,
which in our case means that no data were lost
or corrupted by the service because of a bug.
Now, the cool thing is that Coyote is able to control
all the executing tasks and explore interleavings
and corner cases to find bugs.
Let's see now how Coyote works under the hood.
Now that we have written a concurrency unit test,
we can first compile our production code,
mocks, and tests into a binary.
Next, Coyote loads the binary and rewrites it
by inserting hooks and stubs
that allow Coyote to take control
of the C# tasks in your program.
Now that the binary is instrumented
we can run the concurrency unit test
as if it was any other regular unit test.
To find bugs, Coyote quickly executes each test
from beginning to the end, thousands of times,
each time exploring a different execution path
and task interleavings.
To achieve this, Coyote takes control
of the tasks in your program,
serializes the program execution,
and executes a single task at a time.
And this is where the magic happens.
While Coyote executes the serialized program,
it keeps track of all possible scheduling decisions
in each step of the execution.
You can think of a step
as a point during a program's execution
when some concurrent action is taken,
for example a new task is created,
or a task acquires a lock
or waits for another task to complete.
Now each time Coyote executes a concurrency unit test
it is able to explore different orders
of such scheduling decisions.
And this exploration is what allows Coyote
to expose concurrency bugs
deep inside your program's execution paths.
Now the cool thing is that once Coyote finds a bug,
it provides a trace that allows this bug
to be fully reproduced every single time.
And using this trace,
you can start the Visual Studio debugger
and happily debug the issue.
Let me show you now how you can use Coyote in practice.
You can easily install it from command line
by running "dotnet tool install"
using the Coyote package from NuGet.
Waiting a few seconds, and you can see
the latest version of Coyote
has now been successfully installed.
So there it is, you are ready to go.
So now you can see, if you run Coyote on your command line,
you can see that the tool is running
and you can get all the various options
that you can use to run the tool and, you know,
run the test in your program.
So let's try Coyote on a simple example.
What you can see here is a thread-safe bounded buffer
that allows multiple tasks to access the buffer
and put or get objects without holding any locks.
The cool thing is that this program contains a deadlock,
and I will show you in a bit
how Coyote can help us catch this bug.
I will not dive into details here,
but you can read about this program
and the bug it contains in our blog post.
So if I run the unmodified program,
you can see that we can quickly trigger the deadlock.
The program actually gets stuck, right?
Let's now try to run Coyote on it.
First, we need to run Coyote in rewriting mode,
which rewrites the DLL for testing,
and this allows Coyote to inject logic that takes control
of the tasks and concurrency APIs.
And now that we have rewritten the program, what we can do
is now we can now run Coyote in test mode,
let's say for 100 iterations
and see if it can catch the bug.
You can see that it actually finds the bug, right?
And now what we can do is we can use
a special mode of Coyote
called "replay" that allows us to replay any bug
that Coyote has previously found,
and Coyote is able to do that
because it produces a special file
that we call "schedule" that contains
all of the scheduling choices that Coyote did
in order to find the bug in the program that we just run.
So running this, as you can see,
it allows us to fully reproduce the bug.
And now you can run this special command called "break"
to attach the Visual Studio debugger
and happily debug the issue.
Feel free to check out the GitHub repository
of Project Coyote.
The code is open-source, it's available for everyone,
and we would love to receive your contributions.
You can also find our Coyote package in its NuGet page.
You can easily download it in your Visual Studio project,
and play with it and test your projects with this.
Please feel free to check out our website of Coyote,
which has core concepts, examples, case studies.
You can try things on your own.
You can read the documentation
of the various programming models that Coyote supports,
check out the APIs.
And importantly, it contains various tutorials
that you can follow in order to learn how to use Coyote
in practice and apply it on your source code.
If you want, you can check out also
our list of publications.
Over the last few years, we have published
in some of the top conferences in the area of concurrency
in programming languages, doing cutting edge research
in finding concurrency bugs in distributed systems.
Please check out our blog post
on how Coyote was used to find this tricky deadlock
in the bounded buffer example that we showed you earlier.
we would love to see your contributions.
Please try it out on your projects.
And we would love to hear of any hard concurrency bugs
that Coyote helped you find in your code.
Please feel free to send us your feedback.
Thank you for watching this video.
(energetic electronic music)