Tuesday, 1 March 2011
Speaking at LJC about concurrency
I'm speaking at the next LJC event on concurrency (http://www.meetup.com/Londonjavacommunity/events/16701804/). I'll be doing the same talk that I gave with Martin Thompson at QCon. While it is the same material, the talk tends to take a different turn each time I give it.
Saturday, 5 February 2011
A Non-Blocking ConcurrentHash(Map|Trie)
Introducing ConcurrentHashTrie
While spending some time looking at Clojure's concurrency model, I did a little bit of research into their persistent collection implementation that uses Bagwell's Hash Array Mapped Tries. After a little bit of thought it occurred to me that you could apply the persistent collection model to an implementation of ConcurrentMap. The simple solution would be to maintain a reference to a persistent map within a single AtomicReference and apply a compareAndSet (CAS) operation each time an update to the map was performed. In Clojure terms, a ref and swap! operation. However a typical use of ConcurrentMap is for a simple cache in a web application scenario. With most web applications running with fairly significant numbers of threads (e.g. 100's) it's conceivable that the level of contention on a single compare and set operation would cause issues. Non-blocking concurrent operations like compare and set work really well at avoiding expensive user/kernel space transitions, but tend to break down when the number of mutator threads exceeds the number of available cores*. In fact thread contention on any concurrent access control structure is a killer for performance. The java.util.ConcurrentHashMap uses lock-striping as a mechanism to reduce contention on writes. If absolutely consistency across the ConcurrentMap was sacrificed (more information below), then a form of "CAS striping" could be applied to the ConcurrentHashTrie to reduce contention. This is implemented by replacing the AtomicReference with an AtomicReferenceArray and using a hash function to index into the array.
The Implementation
There are a number of implementations of the Bagwell Trie in JVM languages, however I couldn't find an implementation in plain old Java, so I wrote one myself. For the persistent collection it follows a fairly standard polymorphic tree design.
The core type of Node has 3 implementations. The key one is the BitMappedNode, which handles the vast majority of branch nodes and implements the funky hash code partition and population count operations that make up the Bagwell Trie structure. LeafNode holds the actual key/value pairs and ListNode is there to handle full collisions. The key mutator methods of ConcurrentMap: put, putIfAbsent, remove and replace are implemented using CAS operations on the rootTable, which is an AtomicReferenceArray
As mentioned earlier, the ConcurrentHashTrie is not consistent for operations that occur across the entire structure. While at first look this seems terrible, in practical terms it is not really an issue. The 2 main operations this impacts are size and iteration. The size operation in the ConcurrentHashTrie is not O(1), but is O(n) where n is the size of the rootTable (or the number of stripes). Because it has to iterate across all of the nodes in the rootTable (it doesn't need to traverse down the trees) and add all of their sizes it possible for the size of a Node to change after it has been read but before the result has been calculated. Anyone that has worked a concurrent structure before has probably found that the size value is basically useless. It is only ever indicative, as the size could change right after the method call returns, so locking the entire structure while calculating the size doesn't bring any benefit. Iteration follows the same pattern. It is possible that a node could have changed after being iterated over or just before being reached. However, it doesn't really matter as it is not really any different to the map changing just before iteration started or just after it completes (as long as iteration doesn't break part way through). Note that Cliff Click's NonBlockingHashMap exhibits similar behaviour during iteration and size operations.
Performance, The Good, The Bad and the... well mostly Bad
Cliff Click kindly included a performance testing tool with his high scale library which I've shamelessly ripped off and used to benchmark my implementation. Apparently he borrowed some code from Doug Lea to implement it. I changed a sum total of 1 line. Writing benchmarks, especially for concurrent code, is very tough (probably harder than writing the collection itself), so borrowing from the experts gives me some confidence that the numbers I produce will be useful.
So onto the results:
Do'h!!
Quite a bit slower than the java.util.ConcurrentHashMap. I didn't even bother comparing to the NonBlockingHashMap from the high scale library, the numbers would be too embarrassing.
The ConcurrentHashTrie2 is an alternative implementation that I experimented with. I suspected the polymorphic behaviour of the tree nodes was causing a significant performance hit due to a high number of v-table calls. The alternate implementation avoids the v-table overhead by packing all three behaviours into a single class (in a slight dirty fashion). I stole a couple of bits from the level variable to store a discriminator value. The Node class switches on the discriminator to determine the appropriate behaviour. As the results show, it didn't help much. I ran a number of other permutations and the results were largely the same.
Conclusion
So a question remains, is the approach fundamentally flawed or is my code just crap? I suspect the major cost is caused by heavy amount of memory allocation, copying and churn through the CPU cache caused by the path-copy nature of mutation operations. Also the read path isn't particularly quick. With a reasonably full map, reads will likely need to travels a couple of levels down the tree. With the traditional map, its a single hash and index operation.
* I really need a proper citation for this. However imagine 16 cores and a 100 threads trying to apply a compare and set operation to the same reference. Unlike a lock which will park the threads that fail to acquire the lock, non-blocking algorithms require the thread that fails to apply its change to discard its result and recompute its result, effectively spinning until is succeeds. With more CPU bound threads than cores, its possible that the system will end up thrashing.
While spending some time looking at Clojure's concurrency model, I did a little bit of research into their persistent collection implementation that uses Bagwell's Hash Array Mapped Tries. After a little bit of thought it occurred to me that you could apply the persistent collection model to an implementation of ConcurrentMap. The simple solution would be to maintain a reference to a persistent map within a single AtomicReference and apply a compareAndSet (CAS) operation each time an update to the map was performed. In Clojure terms, a ref and swap! operation. However a typical use of ConcurrentMap is for a simple cache in a web application scenario. With most web applications running with fairly significant numbers of threads (e.g. 100's) it's conceivable that the level of contention on a single compare and set operation would cause issues. Non-blocking concurrent operations like compare and set work really well at avoiding expensive user/kernel space transitions, but tend to break down when the number of mutator threads exceeds the number of available cores*. In fact thread contention on any concurrent access control structure is a killer for performance. The java.util.ConcurrentHashMap uses lock-striping as a mechanism to reduce contention on writes. If absolutely consistency across the ConcurrentMap was sacrificed (more information below), then a form of "CAS striping" could be applied to the ConcurrentHashTrie to reduce contention. This is implemented by replacing the AtomicReference with an AtomicReferenceArray and using a hash function to index into the array.
The Implementation
There are a number of implementations of the Bagwell Trie in JVM languages, however I couldn't find an implementation in plain old Java, so I wrote one myself. For the persistent collection it follows a fairly standard polymorphic tree design.
The core type of Node has 3 implementations. The key one is the BitMappedNode, which handles the vast majority of branch nodes and implements the funky hash code partition and population count operations that make up the Bagwell Trie structure. LeafNode holds the actual key/value pairs and ListNode is there to handle full collisions. The key mutator methods of ConcurrentMap: put, putIfAbsent, remove and replace are implemented using CAS operations on the rootTable, which is an AtomicReferenceArray
As mentioned earlier, the ConcurrentHashTrie is not consistent for operations that occur across the entire structure. While at first look this seems terrible, in practical terms it is not really an issue. The 2 main operations this impacts are size and iteration. The size operation in the ConcurrentHashTrie is not O(1), but is O(n) where n is the size of the rootTable (or the number of stripes). Because it has to iterate across all of the nodes in the rootTable (it doesn't need to traverse down the trees) and add all of their sizes it possible for the size of a Node to change after it has been read but before the result has been calculated. Anyone that has worked a concurrent structure before has probably found that the size value is basically useless. It is only ever indicative, as the size could change right after the method call returns, so locking the entire structure while calculating the size doesn't bring any benefit. Iteration follows the same pattern. It is possible that a node could have changed after being iterated over or just before being reached. However, it doesn't really matter as it is not really any different to the map changing just before iteration started or just after it completes (as long as iteration doesn't break part way through). Note that Cliff Click's NonBlockingHashMap exhibits similar behaviour during iteration and size operations.
Performance, The Good, The Bad and the... well mostly Bad
Cliff Click kindly included a performance testing tool with his high scale library which I've shamelessly ripped off and used to benchmark my implementation. Apparently he borrowed some code from Doug Lea to implement it. I changed a sum total of 1 line. Writing benchmarks, especially for concurrent code, is very tough (probably harder than writing the collection itself), so borrowing from the experts gives me some confidence that the numbers I produce will be useful.
So onto the results:
Do'h!!
Quite a bit slower than the java.util.ConcurrentHashMap. I didn't even bother comparing to the NonBlockingHashMap from the high scale library, the numbers would be too embarrassing.
The ConcurrentHashTrie2 is an alternative implementation that I experimented with. I suspected the polymorphic behaviour of the tree nodes was causing a significant performance hit due to a high number of v-table calls. The alternate implementation avoids the v-table overhead by packing all three behaviours into a single class (in a slight dirty fashion). I stole a couple of bits from the level variable to store a discriminator value. The Node class switches on the discriminator to determine the appropriate behaviour. As the results show, it didn't help much. I ran a number of other permutations and the results were largely the same.
Conclusion
So a question remains, is the approach fundamentally flawed or is my code just crap? I suspect the major cost is caused by heavy amount of memory allocation, copying and churn through the CPU cache caused by the path-copy nature of mutation operations. Also the read path isn't particularly quick. With a reasonably full map, reads will likely need to travels a couple of levels down the tree. With the traditional map, its a single hash and index operation.
* I really need a proper citation for this. However imagine 16 cores and a 100 threads trying to apply a compare and set operation to the same reference. Unlike a lock which will park the threads that fail to acquire the lock, non-blocking algorithms require the thread that fails to apply its change to discard its result and recompute its result, effectively spinning until is succeeds. With more CPU bound threads than cores, its possible that the system will end up thrashing.
Friday, 17 December 2010
QCon Talk Available Online
InfoQ have published the video of Martin and my talk from QCon.
A couple of quick apologies, I haven't done many videoed talks and I completely forgot the repeat the questions during the Q&A session. Martin and I were alternating between each of the slides, so watching the video might make you a little bit sea-sick.
A couple of quick apologies, I haven't done many videoed talks and I completely forgot the repeat the questions during the Q&A session. Martin and I were alternating between each of the slides, so watching the video might make you a little bit sea-sick.
Saturday, 20 November 2010
Clojure's Time/Concurrency Model - A Gentle Critique
While at QCon I sat through Stuart Halloway's talk on the Clojure time/concurrency model, it was very interesting. I watched a copy of Rich Hickey's talk on the same subject some time ago. I'm not going to rehash the entire model here, if you are unfamiliar with it, best to head straight to the source. However, I am going to offer a few (small) criticisms. In fact they are not criticisms of the model but more of the way it is presented.
First off I would like to say that I think the approach the Clojure guys are taking is excellent. I am currently playing with a small prototype application that is based on similar principals. Admittedly I'm using Scala rather than Clojure, but it just shows that their model can be generalised to other languages easily.
Focus On The Model
One of the enabling features of Clojure's concurrency model is the Hash Array Mapped Trie, which allows for a path copy based structure to be used for persistent vector and dictionary type structures. What was not presented during the talk - maybe all Clojure developers know this already - is how the path copy metaphor can (and should) be extended to your entire object model.
Consider an account management service that provides a function for updating an individual account's post code. An object graph for such as service could look something like this:
After an update to the post code for a specific account - using immutable objects to represent the model - the resulting object graph would like the following:
This closely follows the pattern displayed when updating one of the hash tries (q.v.) and retains the property that readers will always see a consistent view of the model no matter which part of the model the reader holds a reference to. If the reader needs a more up to date view of the object graph, it will have to re-enter the model through the accountRef atom. This brings me to my next point.
Identity vs. Entry Point
One of the questions that I asked was around whether there was any real applications built using this model. The response mentioned 2, one being a web framework. However, in both cases those systems only had a single reference, i.e. a single identity. When considering the concurrency model, this makes perfect sense, but from a data modelling or a domain modelling perspective the concept of identity is closely tied to the notion of entities. This use of terminology suggests that you implement a system that puts every entity behind a reference and while this may sound appealing initially, it has 2 negative effects. Firstly is clutters your domain model with an artificial construct, mixing an infrastructure concern (concurrency) with your domain logic. It is generally accepted that separation of concerns is a good thing, so heavily mixing concerns can be considered as bad. The second issue is that an operation that spans multiple entities is difficult to make consistent if all of the entities have individual references. For example, reading threads will be able to see the result of partially applied operations, unless you apply some extensive and complex bookkeeping to ensure that references are made visible in the right order. There is also a performance cost, but I talk about that later.
Using 'Identity' feels wrong as it adds confusion due existing definitions and/or usages of the term. I think a better term is 'Entry Point' or from Domain Driven Design 'Aggregate Root', as this is closer to what actually happening when the code interacts with the model. Another option would be to break the strong linkage between the concept of Identity and the use of Refs to represent them. Using the account service example above, the account repository provides a point with the domain model that code can enter and then reach other entities with that model. Maintaining the reference at the level of the repository allows operations that modify an number of entities that exist below that aggregation point can be made visible as a single atomic action, providing simple, clean transaction semantics.
It's Not Free
One of the statements that irked me the most was around that using Atoms, STM or Agents from a read perspective is free. It's fast, cheap, non-blocking, runs in user-space, but it is NOT free. Using Atoms as an example, the swap! function on the Atom uses an AtomicReference to compare and swap the values after a change has occurred. On the metal this is using a machine level compare and exchange operation (on Intel this is a LOCK CMPXCHG). In order to ensure visibility of the changes the CPU has take out a memory bus lock (or cache lock on newer x86 CPUs) and flush the pipeline. Therefore if your reading thread happened to try and dereference the atom (or potentially any other operation) it won't be able to have its load instruction pipelined along with the write. The slow down is small (and getting smaller on newer CPUs, e.g. Nehalem's CMPXCHG instruction is 40% faster than Core 2) but can't be considered cheaper than a normal non-volatile object reference. A reference within an AtomicReference is declared volatile. Volatile variables are accessed differently to standard variables in that the JVM generates instructions that enforce ordering, which restricts both the compiler's (Hotspot) and the CPU's ability to optimise said instructions. I have anecdotal evidence of code littered with volatile references slowing down significantly.
The other area around performance is the use of completely immutable structures to represent your domain model. Before I get flamed into oblivion, I'm not going to make blanket statement that mutable structures are faster than immutable ones. Before making a judgement it is worth ensuring you understand the behaviour of your own program, specifically the read/write bias. If you have a very high write bias (like in a financial exchange) there is cost to using pure immutable structures. There is a significant memory allocation and copying hit on a write, plus the system will create a lot of garbage (which may cost you in GC pauses). As operations within your application shift toward a read bias, then immutable structures make a lot more sense as the data can be shared.
First off I would like to say that I think the approach the Clojure guys are taking is excellent. I am currently playing with a small prototype application that is based on similar principals. Admittedly I'm using Scala rather than Clojure, but it just shows that their model can be generalised to other languages easily.
Focus On The Model
One of the enabling features of Clojure's concurrency model is the Hash Array Mapped Trie, which allows for a path copy based structure to be used for persistent vector and dictionary type structures. What was not presented during the talk - maybe all Clojure developers know this already - is how the path copy metaphor can (and should) be extended to your entire object model.
Consider an account management service that provides a function for updating an individual account's post code. An object graph for such as service could look something like this:
After an update to the post code for a specific account - using immutable objects to represent the model - the resulting object graph would like the following:
This closely follows the pattern displayed when updating one of the hash tries (q.v.) and retains the property that readers will always see a consistent view of the model no matter which part of the model the reader holds a reference to. If the reader needs a more up to date view of the object graph, it will have to re-enter the model through the accountRef atom. This brings me to my next point.
Identity vs. Entry Point
One of the questions that I asked was around whether there was any real applications built using this model. The response mentioned 2, one being a web framework. However, in both cases those systems only had a single reference, i.e. a single identity. When considering the concurrency model, this makes perfect sense, but from a data modelling or a domain modelling perspective the concept of identity is closely tied to the notion of entities. This use of terminology suggests that you implement a system that puts every entity behind a reference and while this may sound appealing initially, it has 2 negative effects. Firstly is clutters your domain model with an artificial construct, mixing an infrastructure concern (concurrency) with your domain logic. It is generally accepted that separation of concerns is a good thing, so heavily mixing concerns can be considered as bad. The second issue is that an operation that spans multiple entities is difficult to make consistent if all of the entities have individual references. For example, reading threads will be able to see the result of partially applied operations, unless you apply some extensive and complex bookkeeping to ensure that references are made visible in the right order. There is also a performance cost, but I talk about that later.
Using 'Identity' feels wrong as it adds confusion due existing definitions and/or usages of the term. I think a better term is 'Entry Point' or from Domain Driven Design 'Aggregate Root', as this is closer to what actually happening when the code interacts with the model. Another option would be to break the strong linkage between the concept of Identity and the use of Refs to represent them. Using the account service example above, the account repository provides a point with the domain model that code can enter and then reach other entities with that model. Maintaining the reference at the level of the repository allows operations that modify an number of entities that exist below that aggregation point can be made visible as a single atomic action, providing simple, clean transaction semantics.
It's Not Free
One of the statements that irked me the most was around that using Atoms, STM or Agents from a read perspective is free. It's fast, cheap, non-blocking, runs in user-space, but it is NOT free. Using Atoms as an example, the swap! function on the Atom uses an AtomicReference to compare and swap the values after a change has occurred. On the metal this is using a machine level compare and exchange operation (on Intel this is a LOCK CMPXCHG). In order to ensure visibility of the changes the CPU has take out a memory bus lock (or cache lock on newer x86 CPUs) and flush the pipeline. Therefore if your reading thread happened to try and dereference the atom (or potentially any other operation) it won't be able to have its load instruction pipelined along with the write. The slow down is small (and getting smaller on newer CPUs, e.g. Nehalem's CMPXCHG instruction is 40% faster than Core 2) but can't be considered cheaper than a normal non-volatile object reference. A reference within an AtomicReference is declared volatile. Volatile variables are accessed differently to standard variables in that the JVM generates instructions that enforce ordering, which restricts both the compiler's (Hotspot) and the CPU's ability to optimise said instructions. I have anecdotal evidence of code littered with volatile references slowing down significantly.
The other area around performance is the use of completely immutable structures to represent your domain model. Before I get flamed into oblivion, I'm not going to make blanket statement that mutable structures are faster than immutable ones. Before making a judgement it is worth ensuring you understand the behaviour of your own program, specifically the read/write bias. If you have a very high write bias (like in a financial exchange) there is cost to using pure immutable structures. There is a significant memory allocation and copying hit on a write, plus the system will create a lot of garbage (which may cost you in GC pauses). As operations within your application shift toward a read bias, then immutable structures make a lot more sense as the data can be shared.
Sunday, 14 November 2010
Talk Slides Available
Slides from the talk that Martin Thompson and I gave at QCon San Francisco are now available on-line.
Wednesday, 27 October 2010
LMAX Launch
After 3 years of hard work (admittedly only about 1.5 for me), my place of work has finally launched its flagship product LMAX Trader. It's been really exciting to see the fruits of our labour go live and seeing some the reaction in the press. The marketing messaging talks about being the world's first multi-asset retail exchange, real time margining etc, etc.
What's even more interesting is the technology. Some challenging latency and throughput requirements have led us to take a very back to basics approach to the design and eschewed most of the typical solutions in the enterprise software space. The back end is heavily asynchronous with a funky high-performance reliable messaging system, with custom persistence (journal-based). For retail users almost all of the data is delivered over long poll/comet to a single page GWT UI.
It's an incredibly interesting place to work (today our B.A. started modelling our client accounting system using Feynman diagrams). Now that we're live I'm hoping to blog about some of the things I've been working on.
The CTO and I are off to San Francisco next week to speak at QCon (under the Architecture Anarchists track) about some of the challenges we faced and some of the solutions we devised. It will hopefully be interesting for those interested in HPC and concurrency.
Thursday, 24 June 2010
Long time between updates
I've managed to find some time out from my day job (crazy busy at the moment) to drop in an update to the Mono - RabbitMQ/AMQP integration. The RabbitMQ client is now at version 1.8 and up to date with the latest from the RabbitMQ team.
Subscribe to:
Posts (Atom)