[ANN] TransactionKit, Lockless Multi-Reader, Multi-Writer Transaction Capable Hash Tables

FROM : John Engelhart
DATE : Wed Apr 23 01:48:54 2008

All,

I've recently released the first version of TransactionKit, which is 
made of two main components: The core library, and a Foundation 
compatibility API layer.

Homepage: http://transactionkit.sourceforge.net/
Documentation: http://transactionkit.sourceforge.net/Documentation/index.html
SVN trunk is available at: http://transactionkit.svn.sourceforge.net/svnroot/transactionkit/trunk

TransactionKit is made available under a 3-clause BSD License.

As an aside, and begging the karma gods for forgiveness, I'm currently 
looking for a job.  I obviously would like to find work doing Cocoa 
programming, but I also have extensive experience in networking (ala 
sr. backbone engineer at a top tier 1 provider).  Physically in the 
greater Toronto (CA) metro area, US citizen, legal to work in both CA 
and US.  Working remotely has a certain appeal. :)

The core library is mostly C based, with a bit of Objective-C in the 
appropriate places for Objective-C compatibility.  The Objective-C 
parts in the core library are optional, and can be easily stripped 
away leaving just a C based core.

The Foundation API compatibility layer replicates the C based (not the 
newer 10.5 Objective-C based) NSHashTable and NSMapTable, along with a 
subclass / re-implementation of NSDictionary and NSMutableDictionary.

The development environment has been Mac OS X 10.5 on a G4 PPC system, 
though I expect it should work effortlessly on any 10.5 system.  The 
only thing I can think of off the top of my head that would prevent 
10.4 use is the fact that the Dictionary clones implement 
NSFastEnumeration, other than that I can't think of any 10.5 specific 
features it makes use of.  10.5 Garbage Collection is not supported 
nor are their plans to- I have simply not been able to get 10.5's GC 
system to work reliably under the grueling punishment of the synthetic 
stress tests that TransactionKit places on the proper accounting of 
resources by the memory allocation system.  This has not been from a 
lack of trying, I've just found the 10.5 GC system to be buggy and 
unreliable.  Examples include: compiler bugs that don't always insert 
write barriers (ala a typdefed struct assignment, such as 
MyExampleType = *initExampleType), or that the functions 
objc_atomicCompareAndSwapGlobalBarrier (and friends) were essentially 
no-ops until 10.5.2 (specifically, objc4-371.1).  Personally, I've 
found the 10.5 GC system extremely non-intuitive and ultimately 
impossible to correctly use in practice.  I think the section on "The 
Costs of Precise Pointer Identification" in http://www.hpl.hp.com/personal/Hans_Boehm/gc/conservative.html
  summarize many of the objections and problems I've encountered.

Full disclosure: If you're not familiar with the implications of 
"lockless" and "multithreading" combined in the same sentence, you 
should know that this library attempts to deal with some notoriously 
difficult to get right problems.  The common methodology in 
multithreading programming is to employ a mutual exclusion lock around 
a data structure to prevent simultaneous modifications by multiple 
threads at the same time.  TransactionKit uses a novel, experimental 
means to allow lockless modifications by multiple threads 
concurrently.  While some concurrent multiple writer data structures 
do exist, most are generally academic research grade problems / 
solutions.  TransactionKit is definitely a prototype and experimental 
in nature at this time.

- There are almost certainly bugs. -  While certainly unintentional, I 
think its proper to set your expectations now.  I think for most 
'simple' things, things should be mostly bug free.  Corner cases and 
the complicated nuances that crop up during multithreading concurrent 
use is where most of the bugs probably are, especially in dealing with 
the concept of "when" things happens relative to transaction start, 
commit, and rollback times.

While the ultimate goal is to have a highly portable C "core" and an 
Objective-C layer built on top of that, for right now it realistically 
only works on Mac OS X.  This is probably OK considering the 
audience :).  At this point, the C library is largely undocumented, 
but it really isn't that complicated: create a table, free a table, 
insert, get, and remove a key, along with begin, commit, and rollback 
a transaction.  Thats about it, really, and won't be further covered 
here.  The rest of this is regarding the Objective-C portion.

The Objective-C portion, specifically the Dictionary clones, are 
essentially straight, method for method, re-implementations of their 
foundation Dictionary counterparts.  There are two classes, 
TKDictionary and TKMutableDictionary. TKDictionary is a subclass of 
NSDictionary, and TKMutableDictionary is a subclass of TKDictionary. 
They "should" be drop in replacements for their Foundation 
equivalents, and interoperate invisibly with each other.  Where 
necessary, the TransactionKit Dictionaries determine the base class 
type and take the appropriate actions, such as in + 
dictionaryWithDictionary: or - isEqual:.

For now, no additional functionality is added to TransactionKits 
Dictionary replications, such as exposing the underling transaction 
capabilities of the core library.  The methods that perform the 
storing or retrieval of keys/objects in the dictionary have obviously 
been replaced with methods that use a TransactionKit backed hash 
table, but some of the other Foundation Dictionary methods are 
performed by creating a Foundation Dictionary clone of the current 
TransactionKit Dictionary and using the clone as a stand in.  This is 
done for such functions as + dictionaryWithContentsOfFile: and - 
description.

The area where the largest differences between Foundations and 
TransactionKits Dictionaries occurs is in the case of mutating the 
Mutable variety of Dictionaries and the specifics of enumerating the 
Mutable varieties contents.  For example, it is illegal to mutate the 
contents of a NSMutableDictionary under enumeration by any means, 
either NSEnumerator or NSFastEnumeration.  With TransactionKit, it's 
perfectly safe to mutate the contents of a dictionary thats being 
enumerated with no ill effects.  For example:

NSMutableDictionary *mutableDictionary = [NSMutableDictionary 
dictionary];
[mutableDictionary setObject:@"object 1" forKey:@"key 1"];
[mutableDictionary setObject:@"object 2" forKey:@"key 2"];

for(id obj in mutableDictionary) {
  NSLog(@"Object: %@", obj);
  [mutableDictionary removeObjectForKey:@"key 1"];
  [mutableDictionary removeObjectForKey:@"key 2"];
}

Using a NSMutableDictionary, this will obviously throw a mutation 
exception on the second iteration of the loop.  Switching the first 
line to:

TKMutableDictionary *mutableDictionary = [TKMutableDictionary 
dictionary];

and the situation changes: All keys are properly enumerated, even 
though all the keys are removed on the first iteration.  For brevity, 
only two keys are used in the example, but it extends to any amount of 
keys contained in the dictionary.  At the moment that enumeration 
begins, or in this NSFastEnumeration case the first call to - 
countByEnumeratingWithState:objects:count:, a snapshot of the contents 
of the dictionary are taken (really, wrapped in a transaction), and 
the contents of that frozen snapshot is what is enumerated.  Since the 
key removal happens after the point in time of the initial snapshot, 
it does not effect the keys that are to be enumerated.

While the above example demonstrates that it is possible to mutate the 
contents of a dictionary under enumeration by the thread that is 
performing the enumeration, the same principle holds true if the 
mutator is instead a different thread.  In other words, thread A can 
begin an enumeration, and then thread B can mutate the dictionary in 
the middle of thread As enumeration, causing no ill effects.  Safe, 
multithreaded concurrent reader and writer access to 
MutableDictionaries without any complicated locking protocol to observe.

Note: There is an obvious deficiency in the above example.  While 
enumeration will successfully extract all the keys from the point in 
time of the enumerations start, there is no practical way to retrieve 
the objects from the dictionary relative to the enumerations 
snapshot.  Again, this goes back to "adding APIs for functionality the 
original never anticipated": NSFastEnumeration protocol provides no 
easy way to pass 'additional' information back to the invoking 
for...in loop.  Using NSFastEnumeration, I could think of no easy way 
to gain access to the underlying transaction related to enumeration in 
progress.  For the time being, this point is "deferred for further 
consideration."  On the other hand, it's probably a trivial matter to 
add this functionality to the NSEnumeration based enumerators.  Its 
easy to imagine creating a key based NSEnumerator, then enumerating 
the keys of the enumerator as one normally would.  When an object for 
a key was needed, one could call an additional method of the key 
enumerator to retrieve the object using the NSEnumerators 
transaction.  Again, due to the prototype and experimental state of 
TransactionKit, these types of additions are postponed until later.

For those wondering what the magic is behind the lockless multireader, 
multiwriter hash tables is, it's actually pretty simple.  While I 
haven't done any extensive research to find out if the techniques used 
are truly novel, what digging I did do didn't turn up anything 
related.  All of the individual concepts have been put forth before, 
it just seems that no one combined things the way I did up till now, 
which is kind of surprising consider how "obvious" it is.  I'm not 
trying to make any fantastic claims that I've 'invented' something 
novel, only that I couldn't find any references that describes the 
technique I used.

The short version is this: TransactionKit uses a standard hash table 
that has Multi-version Concurrency Control (MVCC).  While there are 
many databases that use MVCC, I could not find any references to any 
uses of MVCC in a lighter weight data structure such as a hash table. 
For a quick overview of MVCC, see http://en.wikipedia.org/wiki/Multiversion_concurrency_control
  .

The basic concept is such: MVCC uses a 'timestamp' to record 
mutations.  This is how TransactionKit gains its transaction 
capability, with full begin, commit, and rollback capability.  A 
timestamp in this case is really just an atomically incrementing 
integer, a very common primitive available on virtually every modern 
architecture.  With a given timestamp, it is possible to "view" the 
contents of the hash table as it was when that timestamp was active. 
Later timestamps (mutations) are simply ignored as they happen "after" 
the timestamp being considered.

The hash table is your generic "collisions are chained" hash table. 
The hash chain is really a LIFO, or stack, in practice.  Virtually all 
modern architectures can perform a single "natural word" compare and 
swap operation atomically, and for practical purposes it's assumed 
that a "natural word" is equal in size to a pointer.  Using this 
primitive, it's possible to create a LIFO stack that atomically pushes 
and pops elements from the stack.  In fact, Mac OS X provides a set of 
functions for performing these very operations (OSAtomicEnqueue, 
OSAtomicDequeue, see `man atomic`).  This allows items to be added to 
the hash table atomically, but using this technique only the item on 
the top of the stack can be removed atomically.  Items in the middle 
can't be removed atomically as it requires being able to alter more 
than a single "natural word" atomically, something generally not 
possible.

The "trick" to being able to dequeue items that are in the middle of a 
hash chain atomically is to break the steps necessary to dequeue an 
item in to steps that can be performed atomically.  Reaching back to 
MVCC, we have a convenient, agreed to be all idea of "time" and when 
things happened.  The individual steps that need to be performed 
advance the MVCC timestamp counter by one, and the thread attempting 
to perform an individual step performs an atomic compare and swap of 
the location used to record when the event took place with the new 
timestamp.  If it "wins" the CAS, it can perform the actual operation.

The second half of the "trick" is to keep track of the lowest (oldest) 
possible transaction timestamp that is outstanding.  Once the lowest 
possible transaction outstanding is greater than a time stamp in 
question it is guaranteed that no thread can possible be referencing 
the value that was in place before the timestamp update, and the "next 
atomic step" can take place.

That's the basics, in a nutshell.  It uses simple, commonly available 
atomic primitives to create a lockless, multi-reader, multi-writer 
hash table that also happens to support begin, commit, and rollback 
style transactions.  While there is certainly some impact to keeping 
track of all the transaction housekeeping, performance is still pretty 
good.  Some benchmarks that I did comparing NSMapTables against 
TKMapTables, with NSMapTables guarded with an OSSpinLock, show 
TransactionKit to be fairly competitive.  Using NSInteger callbacks 
(keys and values nothing more than NSIntegers) and 16 threads, 
NSMapTable was bout 2.8 times faster than TKMapTable.  Using Object 
callbacks and NSNumber objects and 16 threads, TKMapTable was 23% to 
35% faster than NSMapTable.  This is probably due to the fact that 
objects extend the time that a table must remain exclusively locked to 
add and remove keys and values (a retain / release is required), along 
with a more complicated comparison (isEqual:, vs. a simple ==).  This 
was just a single cpu (G4 powerbook, 1.5GHz PPC), as I don't have a 
multi-CPU machine, but the performance benefits should continue to 
increase with the number of CPU's available.

Since the core primitives are lockless, this means the great bane to 
multithreaded programming, The Deadlock, is not possible.  This fact 
alone greatly simplifies multithreaded programming as making sure that 
all locks are properly balanced with unlocks, or that all locks are 
acquired in the correct order, no longer needs to be considered.  And 
since no thread blocks the use of a hash table from any other thread, 
a considerable amount of parallelism can be realized as well.  It's 
pretty useful stuff, but it's still a work in progress at this point. 
In know that for me, fully lockless, transaction capable basic 
collection objects would greatly simplify my multithreading programming.

As an implementation note, I decided to wrap transactions and 
enumerations in NSObject wrappers.  These are used in an autoreleased 
fashion so that even if "something" goes wrong in the middle of their 
use, they are in the autorelease pool.  The hope is that by using this 
technique transactions and hash table enumerations will "clear" 
themselves under most (all?) circumstances, such as an exception being 
thrown.  As soon as the underlying NSAutoreleasePool is popped, the 
transaction or enumeration will get dealloced, and will default to 
rolling back if it was not properly closed out.  It adds a bit of 
overhead, but it also greatly simplifies the tracking of such things.

If you're going to try TransactionKit out, you should be warned that 
there's obviously some rough edges.  One of those is documentation, 
but since I've been concentrating on pre-existing API's, I don't 
consider that to be a huge defect right now.  There's also almost 
certainly bugs here and there, so the idea of unwinding stack frames 
by hand and being able to almost reflexively spot pointers to stack 
variables, and which threads stack it refers to should be second 
nature to you.  When things go wrong, they will go wrong in a 
stunningly complex way.  Things seems fairly stable, though, and 
heavy, synthetic multithreaded stress tests don't result in either 
crashes or any memory loss, which is a pretty spectacular feat 
considering its all lockless.