Pure Danger Tech


CopyOnWriteArrayList concurrency fun

02 Feb 2009

I mentioned CopyOnWriteArrayList in the prior concurrency bugs post. Coincidentally, I happened to need to look at the source for it today and it relies on some nice but not particularly obvious concurrency code.

There are a couple of interesting patterns to ensure within the code that both reads and writes are safe. The key to both is that the data for the array is stored internally in a volatile array and that the values in the array are immutable. Both the volatile and the immutable aspects are important.

Reads against the list do not use synchronization. Instead they rely on always seeing the most recently modified version of the internal array due to the volatile. As you may or may not know, volatile arrays do not have volatile elements (probably a good topic for a concurrency bug post itself). So, a write to an index in the array would not necessarily be seen. However, the array is always immutable so this is never an issue. So that covers reads.

Writes are different. To protect against simultaneous writes, any mutation methods are synchronized (similar to Vector). Internally, the modification is done by first copying the original list, performing the modification, then swapping the volatile array with the new array. So the synchronization protected writes against writes. And the volatile array reference guarantees that reads and writes see a consistent array.

Iterators are supposed to see an old snapshot, so how does that happen? Well, when the iterator is created, it just gets a reference to the current array. Since it’s not going back to the variable in the original list, if that list replaces the array with a new instance, the iterator is no longer seeing the live array, just the array at the time it was created.

Good stuff.