[ANN] TransactionKit, Lockless Multi-Reader, Multi-Writer Transaction Capable Hash Tables
[ANN] TransactionKit, Lockless Multi-Reader, Multi-Writer Transaction Capable Hash Tables
- Subject: [ANN] TransactionKit, Lockless Multi-Reader, Multi-Writer Transaction Capable Hash Tables
- From: John Engelhart <email@hidden>
- Date: Tue, 22 Apr 2008 19:48:54 -0400
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.
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden