I was thinking about your mutex protected linked list when it occurred to me that Firebird might benefit from a piece of technology I call "cycle lock." Here is a description of the motivation and the technique.
Falcon, NuoDB, and AmorphousDB all use a hash table to map transaction ids into transaction objects. Typically, a hash table is protected with synchronization object with a shared lock for a look up and an exclusive lock for an insert or removal. A transaction id lookup, however, is necessary to determine record (or attribute in AmorphousDB) visibility, so transaction lookup is a very high volume operation. Even assuming almost no contention, the cost of two atomic operations per lookup is high undesirable. A hash table is an easy data structure to maintain lock free, using interlocked compare and swap instructions. The fly in the ointment is managing the transaction object lifetime after it has been carefully removed from the hash table. If it is simply deleted, another thread traversing the collision change might find itself with a pointer into trash. The solution is what I call cycle locking. With cycle locking, a thread entering a subsystem gets a single lock on the current "cycle", releasing it on exit. As long as the thread holds the cycle lock, pointers in non-interlocked data structures (e.g. the transaction hash table) are guaranteed valid. Periodically, a cycle manager wakes up, swaps the current cycle lock with an alternate lock, wait for an exclusive lock on the alternate lock (the lock for the previous cycle), does any necessary cleanup, and goes back to sleep. When the cycle manager gets the exclusive lock on the previous cycle, it knows that all threads from the previous cycle have finished, therefore there can be no pending references to objects from the previous cycle. A concrete example: A garbage collection thread decides that a transaction is fully mature (all active transactions would see it as committed) and can be garbage collected. It does a compare and swap to remove the transaction from the hash table. But rather than calling release on the transaction object and running the risk of crashing a concurrent thread, the garbage collector uses another compare and swap instruction to link the transaction object onto a "transaction purgatory" list hanging off the cycle manager object. When the cycle manager wakes up, it first does a compare and swap against the transaction purgatory listhead to simultaneously get a list of transaction objects to be released and to reset the transaction purgatory listhead to null. It then flips the cycle locks, gets an exclusive lock on the previous cycle, then releases the transaction objects with impunity. The cycle manager turns to be useful for all sorts other other periodic maintenance activities. One in particular is maintaining an object list (atoms, buffers, etc.) in effect LRU order. The dumb way to do this is to move an object to the front of the LRU list on every reference. With a cycle manager, each object has a cycle number which is updated on each access (simple non-interlocked assignment). The cycle manager can then make a single pass through the LRU chain moving any object accessed in the previous cycle to the front of the LRU chain. I suspect this would work very nicely with the Firebird page cache manager. ------------------------------------------------------------------------------ Learn Graph Databases - Download FREE O'Reilly Book "Graph Databases" is the definitive new guide to graph databases and their applications. Written by three acclaimed leaders in the field, this first edition is now available. Download your free book today! http://p.sf.net/sfu/13534_NeoTech Firebird-Devel mailing list, web interface at https://lists.sourceforge.net/lists/listinfo/firebird-devel
