No, I’m not kidding…
Race Conditions are evil right?! When you have more than one thread racing to use a piece of shared data and that data is not protected by some kind of locking mechanism you can get intermittent nonsensical errors that cause hair loss, weight gain, and caffeine addiction.
The facts of life:
Consider a = a + b; Simple enough and very common. On the metal this works out to something like:
Step 1: Look at a and keep it in mind (put it in a register).
Step 2: Look at b and keep it in mind (put it in a different register).
Step 3: Add a and b together (put that in a register).
Step 4: Write down the new value of a (put the sum in memory).
Still pretty simple. Now suppose two threads are doing it without protection. There is no mutex or other locking mechanism protecting the value of a.
Most of the time one thread will get there first and finish first. The other thread comes later and nobody is surprised with the results. But suppose both threads get there at the same time:
Say the value of a starts off at 4 and the value of b is 2.
Thread 1 reads a (step 1).
Thread 2 reads a (step 1).
Thread 1 reads b (step 2).
Thread 2 reads b (step 2).
Thread 1 adds a and b (step 3).
Thread 2 adds a and b (step 3).
Thread 1 puts the result into a (step 4).
Thread 2 puts the result into a (step 4).
Now a has the value 6.
But a should be 8 because the process happened twice! As a result your program doesn’t work properly; your customer is frustrated; you pull out your hair trying to figure out why the computer can’t add sometimes; you become intimately familiar with the pizza delivery guy; and you’re up all night pumping caffeine.
This is why we are taught never to share data without protection. Most of the time there may be no consequences (one thread starts and finishes before the other). But occasionally the two threads will come together at the same time and change your life. It gets even stranger if you have 3 or more involved!
The trouble is that protection is complicated: It interrupts the flow of the program; it slows things down; and sometimes you just don’t think about it when you need to.
The story of RTSNF and MPPE:
All of this becomes critical when you’re building a database. I’m currently in the midst of adapting MicroNeil’s Multi-Path Pattern Engine (MPPE) technology for use in the Real-Time Message Sniffer engine (RTSNF).
RTSNF will allow us to scan messages even faster than the current engine which is based on MicroNeil’s folded token matrix technology. RTSNF will also have a smaller memory footprint (which will please OEMs and appliance developers). But the most interesting feature is that it will allow us to distribute new rules to all active SNF nodes within 90 seconds of their creation.
This means that most of the time we will be able to block new spam and virus outbreaks and their variants on all of our customer’s systems within 1 minute of when we see a new piece of spam or malware in our traps.
It also means that we have to be able to make real-time incremental changes to each rulebase without slowing down the message scanning process.
How do you do such a thing? You break the rules!
You’re saying race conditions aren’t evil?? You’re MAD!
(Yes, I am. It says so in my blog.)
Updating a database without causing corruption usually requires locking mechanisms that prevent partially updated data from being read by one thread while the data is being changed by another. If you don’t use a locking mechanism then race conditions virtually guarantee you will have unexpected (corrupted) results.
In the case of MPPE and RTSNF we get around this by carefully mapping out all of the possible states that can occur from race conditions at a very low level. Then we structure our data and our read and write processes so that they take advantage of the conditions we have mapped without producing errors.
This eliminates “unintended” part of the consequences and breaks the apparent link between race conditions and certain disaster. The result is that these engines never need to slow down to make an update. Pattern scans can continue at full speed on multiple threads while new updates are in progress.
Here is a simplified example:
Consider a string of symbols: ABCDEFG
Now imagine that each symbol is a kind of pointer that stands in for other data — such as a record in a database or a field in a record. We call this symbolic decomposition. So, for example, the structure ABCDEFG might represent an address in a contact list. The symbol A might represent the Name, B the box number, C the street, D the city, etc… Somewhere else there is a symbol that represents the entire structure ABCDEFG, and so on.
We want to update the record that is represented by D without first locking the data and stopping any threads that might read that data.
Each of these symbols are just numbers and so they can be manipulated atomically. When we tell the processor to change D to Q there is no way that processor or any other will see something in-between D and Q. Each will only see one or the other. With almost no exceptions you can count on this being the case when you are storing or retrieving a value that is equal in length to the processor’s word size or shorter. Some processors (and libraries) provide other atomic operations also — but for our purposes we want to use a mechanism that is virtually guaranteed to be ubiquitous and available right down to the machine code if we need it.
The trick is that without protection we can’t be sure when one thread will read any particular symbol in the context of when that symbol might be changed. So we have two possible outcomes when we change D to Q for each thread that might be reading that symbol. Either the reading thread will see the original D or it will see the updated Q.
This lack of synchronization means that some of the reading threads may get old results for some period of time while others get new results. That’s generally a bad thing at higher levels of abstraction such as when we are working with serialized transactions. However, we are working at a very low level where our application doesn’t require serialization. Note also that if we did need to support serialization at a higher level we could do that by leveraging these techniques to build constructs that satisfy those requirements.
So we’ve talked about using symbolic decomposition to represent our data. Using symbolic decomposition we can make changes using ubiquitous atomic operations (like writing or reading a single word of memory) and we can predict the outcomes of the race conditions we allow. This means we can structure our application to account for these conditions without error and therefore we can skip conventional data protection mechanisms.
There is one more piece to this technique that is important and might not be obvious so I’ll mention it quickly.
In order to leverage this technique you must also be very careful how you structure your updates. The updates must remain invisible until they are complete. Only the thread making the update should know anything about the change until it’s complete and ready to be posted. So, for example, if we want to change the city in our address that operation must be done this way:
The symbols ABCDEFG represent an address record in our database.
D represents a specific city name (a string field) in that record.
In order to change the city we first create a new string in empty space and represent that with some new symbol.
Q => “New City”
When we have allocated the new string, loaded the data into it, and acquired the new symbol we can swap it into our address record.
ABCDEFG becomes ABCQEFG
The entire creation of Q, no matter how complex that operation may be, MUST be completed before we make the higher level change. That’s a key ingredient to this secret sauce!
Now go enjoy breaking some rules! You know you want to 🙂