Saturday, April 09, 2011

Clojure: State Management

Those unfamiliar with Clojure are often interested in how you manage changing state within your applications. If you've heard a few things about Clojure but haven't really looked at it, I wouldn't be surprised if you thought it was impossible to write a "real" application with Clojure since "everything is immutable". I've even heard a developer that I respect make the mistake of saying: we're not going to use Clojure because it doesn't handle state well.

Clearly, state management in Clojure is greatly misunderstood.

I actually had a hard time not calling this blog entry "Clojure, it's about state". I think state shapes Clojure more than any other influence; it's the core of the language (as far as I can tell). Rich Hickey has clearly spent a lot of time thinking about state - there's an essay at http://clojure.org/state which describes common problems with a traditional approach to state management and Clojure's solutions.

Rich's essay does a good job of succinctly discussing his views on state; you should read it before you continue with this entry. The remainder of this entry will give examples of how you can manage state using Clojure's functions.

At the end of Rich's essay he says:
In the local case, since Clojure does not have mutable local variables, instead of building up values in a mutating loop, you can instead do it functionally with recur or reduce.
Before we get to reduce, let's start with the simplest example. You have an array of ints and you want to double each integer. In a language with mutable state you can loop through the array and build a new array with each integer doubled.
for (int i=0; i < nums.length; i++) {
result.add(nums[i] * 2);
}
In Clojure you would build the new array by calling the map function with a function that doubles each value. (I'm using Clojure 1.2)

user=> (map (fn [i] (* i 2)) [1 2 3])
(2 4 6)
If you're new to Clojure there's a few things worth mentioning. "user=>" is a REPL prompt. You enter some text and hit enter and the text is evaluated. If you've completed the list (closed the parenthesis), the results of evaluating that list will be printed to the following line.

I remember what I thought the first time I looked at a lisp, and I know the code might not look like readable code, so here's a version that breaks up a few of the concepts and might make it easier to digest the example.
user=> (defn double-int [i] (* i 2))
#'user/double-int
user=> (def the-array [1 2 3])
#'user/the-array
user=> (map double-int the-array)
(2 4 6)
In the first Clojure example you call the fn function to create an anonymous function, that was then passed to the map function (to be applied to each element of the array). The map function is a high order function that can take an anonymous function (example 1) or a named function (double-int, example 2). In Clojure (def ...) is a special form that allows you to define a var and defn is a function that allows you to easily define a function and assign it to a var. The syntax for defn is pretty straightforward, the first argument is the name, the second argument is the argument list of the new function, and any additional forms are the body of the function you are defining.

Once you get used to Clojure's syntax you can even have a bit of fun with your function naming that might result in concise and maintainable code.
user=> (defn *2 [i] (* 2 i))
#'user/*2
user=> (map *2 [1 2 3])
(2 4 6)
but, I digress.

Similarly, you may want to sum the numbers from an array.
for (int i = 0; i < nums.length; i++) {
result += nums[i];
}
You can achieve goal of reducing an array to a single value in Clojure using the reduce function.
user=> (reduce + [1 2 3])
6
Clojure has several functions that allow you to create new values from existing values, which should be enough to solve any problem where you would traditionally use local mutable variables.

For non-local mutable state you generally have 3 options: atoms, refs, and agents.

When I started programming in Clojure, atoms were my primary choice for mutable state. Atoms are very easy to use and only require that you know a few functions to interact with them. Let's assume we're building a trading application that needs to keep around the current price of Apple. Our application will call our apple-price-update function when a new price is received and we'll need to keep that price around for (possible) later usage. The example below shows how you can use an atom to track the current price of Apple.
user=> (def apple-price (atom nil))
#'user/apple-price
user=> (defn update-apple-price [new-price] (reset! apple-price new-price))
#'user/update-apple-price
user=> @apple-price
nil
user=> (update-apple-price 300.00)
300.0
user=> @apple-price
300.0
user=> (update-apple-price 301.00)
301.0
user=> (update-apple-price 302.00)
302.0
user=> @apple-price
302.0
The above example demonstrates how you can create a new atom and reset its value with each price update. The reset! function sets the value of the atom synchronously and returns its new value. You can also query the price of apple at any time using @ (or deref).

If you're coming from a Java background the example above should be the easiest to relate to. Each time we call the update-apple-price function our state is set to a new value. However, atoms provide much more value than simply being a variable that you can reset.

You may remember the following example from Java Concurrency in Practice.
@NotThreadSafe
public class UnsafeSequence {
private int value;

/**
* Returns a unique value.
*/
public int getNext() {
return value++;
}
}
The book explains why this could cause potential problems.
The problem with UnsafeSequence is that with some unlucky timing, two threads could call getNext and receive the same value. The increment notation, nextValue++, may appear to be a single operation, but is in fact three separate operations: read the value, add one to it, and write out the new value. Since operations in multiple threads may be arbitrarily interleaved by the runtime, it is possible for two threads to read the value at the same time, both see the same value, and then both add one to it. The result is that the same sequence number is returned from multiple calls in different threads.
We could write a get-next function using a Clojure atom and the same race condition would not be a concern.
user=> (def uniq-id (atom 0))
#'user/uniq-id
user=> (defn get-next [] (swap! uniq-id inc))
#'user/get-next
user=> (get-next)
1
user=> (get-next)
2
The above code demonstrates the result of calling get-next multiple times (the inc function just adds one to the value passed in). Since we aren't in a multithreaded environment the example isn't exactly breathtaking; however, what's actually happening under the covers is described very well on clojure.org/atoms -
[Y]ou change the value by applying a function to the old value. This is done in an atomic manner by swap! Internally, swap! reads the current value, applies the function to it, and attempts to compare-and-set it in. Since another thread may have changed the value in the intervening time, it may have to retry, and does so in a spin loop. The net effect is that the value will always be the result of the application of the supplied function to a current value, atomically.
Also, remember that changes to atoms are synchronous, so our get-next function will never return the same value twice.

(note: while Java already provides an AtomicInteger class for handling this issue - that's not the point. The point of the example is to show that an Atom is safe to use across threads.)

If you're truly interested in verifying that an atom is safe across threads, The Joy of Clojure provides the following snippet of code (as well as a wonderful explanation of all things Clojure, including mutability).
(import '(java.util.concurrent Executors)) 

(def *pool* (Executors/newFixedThreadPool
(+ 2 (.availableProcessors (Runtime/getRuntime)))))

(defn dothreads [f & {thread-count :threads exec-count :times :or {thread-count 1 exec-count 1}}]
(dotimes [t thread-count]
(.submit *pool* #(dotimes [_ exec-count] (f)))))

(def ticks (atom 0))
(defn tick [] (swap! ticks inc))
(dothreads tick :threads 1000 :times 100)
@ticks ;=> 100000
There you have it, 1000 threads updated ticks 100 times without issue.

Atoms work wonderfully when you want to insure atomic updates to an individual piece of state; however, it probably wont be long before you find yourself wanting to coordinate some type of state update. For example, if you're running an online store, when a customer cancels an order the order is either active or cancelled; however, the order should never be active and cancelled. If you were to keep a set of active orders and a set of cancelled orders, you would never want to have an order be in both sets at the same time. Clojure addresses this issue by using refs. Refs are similar to atoms, but they also participate in coordinated updates.

The following example shows the cancel-order function moving an order-id from the active orders set into the cancelled orders set.
user=> (def active-orders (ref #{2 3 4}))
#'user/active-orders
user=> (def cancelled-orders (ref #{1}))
#'user/cancelled-orders
user=> (defn cancel-order [id]
(dosync
(commute active-orders disj id)
(commute cancelled-orders conj id)))
#'user/cancel-order
user=> (cancel-order 2)
#{1 2}
user=> @active-orders
#{3 4}
user=> @cancelled-orders
#{1 2}
As you can see from the example, we're moving an order id from active to cancelled. Again, our REPL session doesn't show the power of what's going on with a ref, but clojure.org/refs contains a good explanation -
All changes made to Refs during a transaction (via ref-set, alter or commute) will appear to occur at a single point in the 'Ref world' timeline (its 'write point').
The above quote is actually only 1 item in a 10 point list that discusses what's actually going on. It's worth reviewing the list a few times until you feel comfortable with everything that's going on. But, you don't need to completely understand everything to get started. You can begin to experiment with refs anytime you know you need coordinated changes to more than one piece of state.

When you first begin to look at refs you may wonder if you should use commute or alter. For most cases commute will provide more concurrency and is preferred; however, you may need to guarantee that the ref has not been updated during the life of the current transaction. This is generally the case where alter comes into play. The following example shows using commute to update two values. The example demonstrates that the pairs are always updated only once; however, it also shows that the function is simply applied to the current value, so the incrementing is not sequential and @uid can be dereferenced to the same value multiple times.
user=> (def uid (ref 0))
#'user/uid
user=> (def used-id (ref []))
#'user/used-id
user=> (defn use-id []
(dosync
(commute uid inc)
(commute used-id conj @uid)))
#'user/use-id
user=> (dothreads use-id :threads 10 :times 10)
nil
user=> @used-id
[1 2 3 4 5 6 7 8 9 10 ... 89 92 92 94 93 94 97 97 99 100]
The above example shows that commute simply applies regardless of the underlying value. As a result, you may see duplicate values and gaps in your sequence (shown in the 90s in our output). If you wanted to ensure that the value didn't change during your transaction you could switch to alter. The following example shows the behavior of changing from commute to alter.
user=> (def uid (ref 0))                       
#'user/uid
user=> (def used-id (ref []))
#'user/used-id
user=> (defn use-id []
(dosync
(alter uid inc)
(alter used-id conj @uid)))
#'user/use-id
user=> (dothreads use-id :threads 10 :times 10)
nil
user=> @used-id
[1 2 3 4 5 6 7 8 9 10 ... 91 92 93 94 95 96 97 98 99 100]
There are more advanced examples using refs in The Joy of Clojure for those of you looking to discuss corner case conditions.

Last, but not least, agents are also available. From clojure.org/agents -
Like Refs, Agents provide shared access to mutable state. Where Refs support coordinated, synchronous change of multiple locations, Agents provide independent, asynchronous change of individual locations.
While I understand agents conceptually, I haven't used them much in practice. Some people love them, and the last team I was on switched to using agents heavily in one of our applications shortly after I left. But, I personally don't have enough experience to say exactly where I think they fit in. I'm sure that will be a topic for a future blog post.

Between Rich's essay and the examples above I hope a few things have become clear:
  • Clojure has plenty of support for managing state
  • Rich's distinction between identity and value allows Clojure to benefit from immutable structures while also allowing identity reassignment.
  • Clojure, it's about state.