Thread Safe Vectors in Vulcan

From Jim Starkey on the Firebird Development List 19th December 2004

The most significant internal difference between Firebird/Interbase and Vulcan are the respective approaches to thread safety. Firebird/Interbase has, in essence, one big mutex seized by THREAD_ENTER and and released by THREAD_EXIT. While safe and very cheap, it has the drawback that only one thread can be active within the engine at any one time, eliminating any possibility of exploiting an SMP system. Vulcan is based on fine-grained multi-threading, meaning that individual shared data structures within the engine are managed independently, and that any number of threads can be active within the engine simultaneously. The benefit of fine grain multi-threading is SMP performance; the cost is the overhead of synchronization. The cost of synchronization has two independent components. One is the resource cost (primarily cpu cycles) of the synchronization primitives themselves assuming no contention. The other is the cost of a thread stall when one thread encounters a resource held by another with an incompatible lock. Both costs are significant. The synchronization overhead is largely wasted on uniprocessor systems that get no benefit from SMP. The thread stall cost can be much worse, potentially reducing SMP performance to less than a uniprocessor by thread thrashing.

The name of the game is cheap and effective synchronization primitives, used wisely. There are two types of synchronization primitives, mutexes (mutual exclusion) and read/write locks (reads can share but writers needs exclusive control). Most of the literature deals with mutexes on the common, but misguided, belief that an increased overhead of the more complex read/write lock is unjustified in practice. A database engine contains a large number of dynamic data structures describing the physical database, a page cache, a meta data cache, transactions, compiled requests, etc. But while dynamic, once the engine is up and running, these data structures change very little, can be readily shared without actual contention. Under load, the ratio of shared to exclusive locks on internal structures if probably in the thousands to one. The belief that a read/write lock is more expensive than a mutex in the absence of contention is also wrong, each can be implemented with a little set up and a single interlocked machine instruction. What happens in the case of contention is irrelevant since each leads to a thread stall.

Vulcan uses two primary classes for thread synchronization. The first, SyncObject, is the lock itself, and is almost always a member of an object class to be protected. The Vulcan Relation class, for example, has four independent synchronization objects to protect different substructures:

SyncObject syncObject;
SyncObject syncGarbageCollection;
SyncObject syncTriggers;
SyncObject syncFormats;

A SyncObject is usually managed by second class, Sync, which is always used as a stack local. Sync handles the care and feeding of a SyncObject. The most convenient thing about Sync is it's destructor which always, always releases the lock on method or block exit. An example of Sync usage is:

void Relation::setFormat(fmt* format)
{
    Sync sync(&syncFormats, "Relation::setFormat");
    sync.lock(Exclusive);
    int formatVersion = format->fmt_version;
    rel_formats.checkSize(formatVersion, formatVersion+1);
    rel_formats[formatVersion] = format;
}

In the example above, the relation format vector is controlled by an explicit syncObject in the Relation object. This is perfectly ok, but got tedious. Rather than require the users of a vector manage synchronization of the vector, was there a way for a vector to manage access to itself? The issue isn't one of protecting slots of the vector, but to protect against one thread reading or writing the vector while another thread is extending it.

Vulcan uses a vector template class derived from one written by Mr. James Lowden. The template class has multiplied somewhat, having one version that formally deletes elements on destruction (DVector) and a slightly simpler version that doesn't worry about its elements (SVector, for scalar or simple vector). SVector, like std::vector, supports the C++ array index syntax to both read and write vector elements:

SVector foo (10);
foo [5] = "five";
const char *p = foo[5];

Mr. Lowden implemented the index operator like this:

template
class SVector
{
public:

    // by index operator
    Type& operator[](size_type n)
        {
        if( n < length )
            return buffer[n];

        throw OSRIBugcheck("vector index error");
        }

which essentially return the address of the element, allowing the invoking code to read or write the element.

The question at hand is how to morph SVector into SIVector (simple, interlocked vector). Clearly we need to throw a SyncObject as a class local to SIVector. It would then be tempting to throw a Sync into operator[] to protect the vector between the length check and the element return. Tempting, but wrong. Because when the operator returns the address of the element, there is a window where another thread could extend the internal vector, releasing the old version to which the first thread has a dangling pointer.

The solution was an nested element class for SIVector with cast and assignment operators that invoke thread safe methods in SIVector to do the work. The element class is defined as:

template
class SIVector

public:
    typedef unsigned int size_type;

    class Element
        {
        public:
            Element (SIVector *vec, int idx)
                {
                parent = vec;
                index = idx;
                }

            Element& operator = (Type newValue)
                {
                parent->set(index, newValue);
                return *this;
                }

            operator Type()
                {
                return parent->get(index);
                }

        protected:
            SIVector    *parent;
            int                index;
         };

The Element is used as the return value for the array index operator:

Element operator[](size_type n)
     {
     return Element(this,n);
     }

Element is never actually used, serving only as a vehicle for assignment and references to the template type, implemented as operator of Element, and which call the SIVector methods set and get, respectively:

Type get(size_type n)
     {
     Sync sync (&syncObject, "SIVector::get");
     sync.lock(Shared);

     if( n < length )
         return buffer[n];

     throw OSRIBugcheck("vector index error");
     }

 Type set(size_type n, Type newValue)
     {
     Sync sync (&syncObject, "SIVector::set");
     sync.lock(Shared);

     if( n >= length )
         throw OSRIBugcheck("vector index error");

     buffer[n] = newValue;

     return newValue;
     }