OutputStream

Yesterday Martin Krasser posted an article by Martin Fowler on Twitter, discussing the Disruptor Framework for Concurrency. It's is an impressive framework boasting 6 million transactions per second in a single thread.

We got into a discussion on Twitter and Google+ (Google+ FTW for both allowing a long form discussion and a linkable URL) about whether or not the business logic could be considered referentially transparent. I think we're both right. Disruptor certainly outright encourages the business logic to be full of side effects since it's all running in a single thread, as Martin emphasized, and I doubt the term "referentially transparent" ever crossed the minds of Disruptor's creators, so the implementation is what it is, but the bird's eye view shows a system of repeatable inputs and outputs via Event Sourcing, which, abstractly speaking, describes a system that is referentially transparent. The discussion made me think of this video where Brian Beckman tells us not to fear monads, because we'd have invented them ourselves anyway.

Anyhow, what I most immediately fell in love with upon reading about Disruptor was how it flew in the face of the concurrency sages of our time. Everything you read these days tells you to watch out for variables that must be declared volatile or make sure they're processed through a synchronization block, and if you don't do that, use the actors pattern or completely and totally embrace immutability with a dash of STM mixed in. Disruptor says fooey to all of that, and declares that CPU cache is something that ought not be wasted, and shows that when it's not wasted, massive performance gains can be made. That's neat! But when should we use it?

I think you should use it when your business logic comprises a much larger share of your application than the side effect producing aspects of your system do; and I think this is fairly rare. Take Twitter, for example. The business logic in Twitter could probably be written in about a day (maybe less). It's basically making sure posts are under 140 characters, verifying the user is who they say they are, and distributing tweets to followers. There's more, but it's not that complicated. On the other hand, Twitter's side effect aspects of their system are a massive pain. Robert Scoble not only has 200K followers, but he follows 32K himself, and he tweets like a madman. The business logic isn't difficult, but the CAP theorem aspects of the system are. Using Disruptor would probably hurt Twitter rather than help. LMAX, creators of Disruptor, are building a large retail trading platform. That's hard business logic. It's nice they don't have to worry about concurrency issues when writing it. Disruptor makes a lot of sense for them.

I spend most of my time these days building a web crawler. The crawler does a lot of feature processing and extraction that's set aside for machine learning. The feature processing is processor intensive, but I don't think it would benefit from using Disruptor. The bottleneck I deal with is network IO. I think I'll stick with the advice of our concurrency sages for the time being.

A comment was posted to my previous entry on STM about the performance of STM. I tried to post a comment in reply but posterous was cutting off half of the text (grrr), so I figured I'd make a blog entry of it. 

STM is fast enough for you not to worry about it 99.99% of the time, and if you read the Akka docs on STM, it becomes pretty clear that you'd better make a REALLY GOOD CASE for fine grained locking and synchronization, for example:

"A transaction is automatically retried when it runs into some read or write conflict, until the operation completes, an exception (throwable) is thrown or when there are too many retries. When a read or writeconflict is encountered, the transaction uses a bounded exponential backoff to prevent cause more contention and give other transactions some room to complete."

and

"It can happen for the first few executions that you get a few failures of execution that lead to unexpected retries, even though there is not any read or writeconflict. The cause of this is that speculative transaction configuration/selection is used. There are transactions optimized for a single transactional object, for 1..n and for n to unlimited. So based on the execution of the transaction, the system learns; it begins with a cheap one and upgrades to more expensive ones. Once it has learned, it will reuse this knowledge. It can be activated/deactivated using the speculative property on the TransactionFactory. In most cases it is best use the default value (enabled) so you get more out of performance."

Why aren't we talking about Software Transactional Memory (STM)? The answer is simple: actors have long been included in the standard library, while STM won't make an appearance in the standard library until version 2.9.1, and all of the Scala books have a chapter entitled something to the effect of "Concurrency and Actors" that focuses mostly on the actors pattern while never mentioning STM. Due to this, all of the talk at conferences and local meetups tends to focus on the actors pattern when the topic of concurrency arises, and why not? I've personally initiated at least a dozen conversations on actors, because I've read those books, and I've watched Joe Armstrong say he achieved nine nines with the actors pattern.

With all of that hype out there, I spent about a year futzing with the actors pattern and STM, and I've come to the belief that, when it comes to solving concurrency woes, 9.75 times out of 10 the actors pattern is a square peg in a round hole, while STM solves those woes nearly all the time, and more importantly: IT'S DEAD SIMPLE!

That said, I intend to help others see the light with the small example below:

Suppose I have a small bank with only two accounts, and all that can happen at this bank is money can be transferred from one account to the other. A "correct" program to achieve this would look something like:

This program is really easy for any programmer to understand, and it's correct when a single thread is performing the transfers, but when multiple threads are performing the transfers, bad things happen. I think most people in the Scalasphere are familiar with the problems concurrent programs face, so I don't think I need to talk much more about it, but if you aren't familiar, I suggest watching every minute of this presentation by Brian Goetz, and reading his awesome book on concurrency.

So how can we make this program work in a concurrent environment with STM? It's actually pretty easy:

Initially, what's great about this is that it's nearly the same as the easily understandable program that is correct in a single threaded environment, but with a few differences. I'll discuss the details of this example, but first let's discuss a little bit about what STM is.

STM is an alternative to lock-based synchronization. In essence it places a guard around a specified memory location (in our example we've placed it around the "accounts" map). The guard is called a Ref. You can only gain access to the memory location by initiating a transaction with an atomic block. Once inside the atomic block, you can gain access to the data in the memory location through the Ref and make modifications. Modifications are isolated, so changes can only be seen within the scope of the atomic block.  When the transaction ends, an attempt is made to update the memory location atomically.  However, it may be that another thread has committed a transaction before the attempt. If this is the case, the logic inside of an atomic block is retried until an update can be made. There are some implications we'll get into, but first let's walk through the example above.

First, I've added the "scala.concurrent.stm._" import. This is ScalaSTM, which is slated for release with Scala 2.9.1 (you can also try Akka), but you can use it now. Next, I turned the Account class into an immutable case class, and made the credit and debit methods return copies of itself with modified balances. Next, the accounts map has become accountsRef, which is now a Ref object that wraps an immutable map. Next, the body of the transfer function now contains an atomic block, which supplies an implicit transaction that you'll never use, but is used the STM internals. Inside the atomic block, the immutable map wrapped by the Ref is accessed by calling it's apply function. The business logic is carried out, and the updated accounts map is placed back in the accountsRef with "accountsRef() = accounts". It's dead simple really, and 99.99% of your STM code will look exactly like this, so if you understood this paragraph, you've understood almost everything you need to know about how to use STM.

That said, an important implication of this is that the atomic block must be referentially transparent, which means you should be able to replace it with it's value. I know that's a fairly opaque definition, so let's look at some rules of thumb with examples breaking them that really screw things up with STM.

First, your atomic block should not have side effects; i.e. it should be pure. Take a look at this example:

In this example, a method called "applyTransferFees" is called from within the atomic block — for the sake of this example suppose that it calls a web service, which is a side effect. If the atomic block fails to update the accountsRef due to another thread getting there first, the atomic block will be retried, and the applyTransferFees method will be invoked again, which will cause the client to be billed multiple times for only one transfer. A better way to achieve the same thing is to have the atomic block return a boolean, like so:

Next, you must embrace immutability. The Ref only guards access to a memory location, however it does nothing to guard the internals of the items it's guarding. Imagine that it was guarding a java.util.HashMap. A couple of bad things can happen in this case. First look at this example:

This example is another example with side effects. Imagine a situation where the atomic block needs to be called again. Although the accountsRef will not be updated from the first failed attempt, it does not matter, because really this example is updating the protected memory location (the HashMap) with the same memory location. This is due to the fact that the put method on java.util.HashMap uses side effects to update its internal structure, so all of the business logic inside the atomic block will get tried over and over all while updating the same map every other thread is updating (i.e. very bad!). The + method on the Scala immutable map in the previous examples returns a new map, which is a new memory location, meaning the new maps returned by + are only visible to the call stack of the atomic block. Another similar example would be:

In this example, no logic is carried out inside of the atomic block, but the java.util.HashMap escapes the Ref by being returned from the atomic block and is handed off to a method called "crazyThreads", which undoubtedly performs all sorts of nastiness on the map that the Ref is helpless to prevent.

Another example that may be less obvious is the case where the accounts map is immutable, but the Account class has mutable state. For example, what if we made a thread safe version of the Account class with a mutable balance, and modified the program to use it, like so:

Here, again, the credit and debit methods have the side effect of updating the mutable balance of their account, so if the atomic block is retried, those values will be modified multiple times, which is not what you want. I made the Account class thread safe just to point out that it doesn't matter — mutability is what matters! Another consequence of this is you should construct your classes to be ENTIRELY immutable. You may be tempted to use things like java.util.Date, but again, that's a mutable class, so it's prone to problems. For cases where you need dates, switch to Joda Time — it's better anyway.

Finally, the business logic inside of the atomic block cannot depend upon values outside of the block. Often it is tempting to pull the value guarded by the Ref out of the Ref, perform operations upon it and use those values later to update the Ref again. This is bad because, even if the atomic block isn't retried, you're introducing race conditions. For example:

In this example, the accounts map is pulled out of the Ref in one atomic block and then used inside of another. By the time the second atomic block is entered, another thread may have updated the map guarded by the Ref, which means the data in the local accounts map is old, which is the age old race condition. Make sure that business logic inside atomic blocks is self contained. This includes values needed to determine things inside the atomic block. For example, let's say we wanted to change our program so that any transfer occuring at a time divisible by 1234 gets a credit of $1 (dumb scenario, I know). Here is the wrong way:

It's wrong because if the atomic block is retried it's possible that the time on the first attempt was divisible by 1234, but after the retry the time might not be divisible by 1234, so you could credit an account incorrectly. The correct way is to put the timestamp inside of the atomic block, like so:

So in conclusion, if you can ensure referentially transparent atomic blocks by following these rules of thumb — which I feel is pretty easy to do if your projects begin as Scala projects — then STM is probably the best choice for you because it allows your code to look much like it would without any concurrency controls, and it involves very little extra thought and fear.

For more information, I'd check out:

• ScalaSTM
• Akka
• Simon Peyton Jones' 15 minute presentation on STM at OSCON
• And Rich Hickey's presentations
  • Persistent Data Structures and Managed References
  • Are we there yet?
  • Clojure

   

TRENDS

The flashy "trends" headline is indicative of how cool the newest trends are that I picked up on at Scala eXchange in London last week.  What are they? Parallel Collections? Actors (hah!)? Enterprise Monads?  Wrong. (But you should watch Alex Prokopec's presentation on parallel collections anyway because it has some rad animations.)

So what are they?

1: Blocking is EVIL™

Remember how cool it felt when you started up your first ExecutorService, submitted a Callable<T>, and got back a typed Future<T>? And then remember when you submitted a whole lot of them in Scala and got back a nice typed List[Future[T]] that you map(_.get)'d across to get a nice clean List[T] on the other side in just a few lines of code? It felt great didn't it?  Well it was EVIL™.

Now — if you're cool — you're gonna switch to either Akka's functional futures or Scalaz's Promises. Why? More details forthcoming, stay tuned!

2: No More Exception Bubbling

This has been the eternal debate — nearly as controversial as where your curly braces go — ever since I can remember.  Should you catch an exception or let it bubble up to the main thread? Main thread? It's 2011, who has things running in the main thread?  No, you're gonna silently lose that exception and spend several hours scratching your head wondering what went wrong — and that's just the practical reason for giving up exceptions.  The cool reason to give them up is because exceptions break referential transparency, which isn't germane to the functional style, and therefore uncool. So what you're going to do is swith to using Either[Throwable, T], Box[T], or Validation[E+, A+] — more details forthcoming, stay tuned!

3. Nobody is talking about STM

Why? I dunno, but I plan on covering it quite a bit, so stay tuned!

I gave two short talks at Scala eXchange, one on Unfiltered and one on Software Transactional Memory. You can view them both here:

Unfiltered: http://skillsmatter.com/podcast/scala/lightning-talks-talk-2-at-scalax
STM: http://skillsmatter.com/podcast/scala/lightning-talks-talk-1-at-scalax

I completely spaced some verbiage I had planned for STM, namely that it's the three first letters in ACID (atomic, consistent, and isolated), which probably would have answered a question I received from @oxbow_lakes before he asked, and overall I feel that 15 minutes was probably too short a time to spend on STM.  30 probably would have been better. Nonetheless I'm happy with it, and I feel the Unfiltered talk went over really well.