How do you test and demonstrate that you have properly prevented a race condition?

Question

Suppose I'm building a web application using Django. Some of the views need to touch multiple database tables or rows, and there is some kind of state consistency that I need to ensure among the records.

Here is a simple example, albeit a bit stupid. Suppose we're talking about an application for the management of class enrollment at a University.

• A student may enroll in a class only if that class is actually marked as open for enrollment.
• The school may freely toggle the class's open-to-enrollment status as long as there is no student currently enrolled.
  • If there is any student already enrolled in a certain class, the school may not immediately close the class from enrollment and cancel it. The school would first need to send some kind of notification to the enrolled students and then wait for either 2 days or receiving all of the students' acknowledgement, whichever happens first.

So if in the database, a class is both closed from enrollment and has enrolled students, it is clearly in an inconsistent state. One way that can happen is if we forget to lock the class row in the views that handle open-to-enrollment status and student enrollment: the school may be trying to close the class from enrollment and a student may be trying to enroll at the same time. So, being a good engineer, I know I'm supposed to lock the class row. But even if I do that, how do I test and demonstrate that I have successfully prevented a race condition?

I mean, wouldn't that entail trying to cause a race condition on purpose? How would one even do that? Isn't that all about timing? If, in my tests, I naïvely fire two requests at the same time and I don't end up with an inconsistent state, how do I know it's because my row locking is correct and not because the two requests actually just missed each other?

Answer 1

Sometimes you have some control over the timing, and you can intentionally force a race in a test. When you are using a guarantee of an external system like a database, you usually can't control the timing that precisely.

In that situation, we explicitly call out the requirement during our planning as an acceptance criteria. "Must prevent an inconsistent state." That highlights the problem before anyone even starts designing a solution, it makes it more visible during code reviews, and ensures the product owner will ask us about it before we can call it done. That by itself goes a long way to making a design that's fairly easy to verify by inspection.

If you need more confidence than that, pretty much the best you can do is a stress test. Make requests a few hundred times using several threads and keep checking for an inconsistent state. You're basically increasing the probability of it occurring. Purposely break your code once to run your test so you know it can catch the problem, and how often to expect it.

That sort of test is usually too time consuming or too difficult to fully automate for ongoing regression tests you run with every pull request, but they are very useful for one-time verification of a feature or bug fix.

Answer 2

One possibility is to replace the scheduler with one that is under your control.

That is essentially how Microsoft Research's CHESS tool works. It uses static analysis to try and determine all possible data dependencies and interleavings of execution paths of your code, and then runs the code with all the possible interleavings by replacing the standard library's concurrency framework with its own.

CHESS has been used successfully for, among other things, the Windows NT kernel and the .NET concurrency libraries.

CHESS only supports C++ and .NET, but there is no reason why a similar tool couldn't be implemented for Python. In particular, PyPy might be a good candidate, since I believe its concurrency semantics are already designed to be modular. In fact, at least at the beginning, PyPy had two pluggable concurrency models, one using OS threads similar to CPython but more fine-grained locking (no GIL) and one using stackless microthreads compatible with the concurrency model of Stackless Python.

So, it should definitely be possible to create a tool like CHESS for Python as well. And with some clever integration with Django and its request model, it should be possible to write some quite beautiful concurrency-related unit tests.

When you think about it, this all comes down to Dependency Injection, really. The scheduler is a dependency of your code. It should be injected so you can replace it.

Note that CHESS, specifically, is about automatically finding concurrency errors, hence why it tries to find all possible interleavings. In your case, that's actually much more complex than you need: you know which interleavings can cause you trouble and you only need to generate those specific ones. This is much easier, it only requires being able to control the scheduler.

Answer 3

If you really want to automate this kind of test, your best bet is probably to build a specific "test mode" into the code section which handles the race condition. When this test mode is activated, there should be an artificial delay activated inside the critical section.

To make this work robustly and quick, I would not make this "delay" really based on some timer, but simply wait as long as a second thread signals it reached it's critical section, too. So the whole test sequence could look like this

• start one thread for the first transaction in "test mode"

• when the first thread asynchronously waits for the signal, start a second thread which tries a "colliding" operation (without any delay). The test is successful when this operation fails

• let the second thread signal the first one it can continue, wait until the first thread acknowledges it has left the critical section

• try the colliding operation again from the second thread, it should work now.

Of course, I guess the hard part here is to make sure the the "test mode" itself does not shadow other race conditions (or worse, adds new ones).

The only other way of "demonstrating" that you have prevented a race condition I can think of (besides the idea of a stress test, see Karl Bielefeldt's answer) is having a second pair of eyes review your code. Ideally, you use both techniques in conjunction.