Saturday, November 24, 2007

More on Multi-Threading Suneido

I am continuing to intermittently work on making a multi-threaded Suneido server (that will also run on Linux as well as Windows).

So far, I have stripped out all the Windows dependencies and just about have the socket stuff converted to ACE. It should not take too much more to get this working - but only single threaded.

In a sense, this is the easy part. The hard part is to add the required locking etc. to allow it to run safely without the multiple threads interfering with each other.

There are two sides to this - the database and the language run time (virtual machine).

On the database side, the data itself should not be a problem because it is immutable (never updated). When records are updated the new version is added to the end of the database file. (This is the main reason the database needs to be "compacted" periodically.) The primary reason for this is to support the multi-version optimistic database transactions but it also ends up being nice for multi-threading.

The indexes are the main issue in the database. The easiest solution is probably locking at a fairly granular level of entire indexes. There are schemes for locking individual index nodes, but this is tricky. It should be easy to use multiple readers OR single writer locking. The downside is that if there is a lot of updating it will end up being single-threaded again.

Ideally, I would like to support multiple readers concurrently with updating (but still only one writer at a time) similar to how multi-version optimistic transactions allow multiple readers to operate independently of updates. But I have not figured out any "easy" way to make the indexes similarly multi-version so readers are not blocked by updates.

This may not be critical because I am pretty sure read's are far more common than update's. I should really measure this instead of guessing!

The other side is the language virtual machine. This should not be too bad because there is not much shared mutable (updatable) data. The main shared data structure is the table of global definitions loaded from libraries. The only time this is modified is when a new definition needs to be loaded from a library. At one time I thought I could use the double checked locking pattern (DCLP) to avoid synchronizing every access, but DCLP has been found to be fatally flawed. In theory, with 32 bit values and an idempotent function it is still workable, but given the history it seems risky. Another way to avoid the synchronization overhead would be for each thread to have its own globals table "cache" and to load this from a shared synchronized table.

I am sure there are many other fun issues lurking in this project. I am still very paranoid about synchronization issues that do not show up until after deploying it to hundreds of customers. My first line defense will be to try to keep the locking simple so I can have a fair chance of convincing myself logically that it is "correct". (Although judging by DCLP, even very smart people can fail to catch concurrency flaws in even simple code.) The next line of defense will be some serious stress testing, probably on something like a quad core machine to increase the chances of conflicts.

No comments: