| Article Index |
|---|
| MVCC STM GC'd Ref History |
| Detailed Description |
| Conclusion |
| All Pages |
When writing an MVCC-based STM I found that managing the value history on the Ref object was an issue. I needed to keep just enough history in memory for all transactions to access the appropriate values. This initially seemed to be an annoying problem to solve as the garbage collector would potentially GC too much of the history list. But after some thought I designed a way to have the garbage collector GC the right amount of the history list.
Other than being an interesting problem solved, I didn't think much more of it until I saw that the Clojure STM implementation manually tries to manage it's Ref history list. If the list is too small the transaction is retried and the list for that Ref is lengthened. A guess is made as to how long lists should be, so it's likely that the lists are a bit longer than required. I didn't look in to the implementation to see exactly what they are doing or how much extra code is required to get it to work, but either way it sounds unnecessarily complicated and inefficient. The GC is the best system to manage these sorts of lists.
The GC-based solution is very simple, doesn't require much code or memory overhead and more importantly, it's just correct. What needs to be in memory is in memory, what isn't needed is removed.
There may be a technical reason for why Clojure implements its STM the way it does. But anyway, I thought I'd document a way to manage history lists in these sort of systems in case anyone was interested. Like most (all?) STM implementations, transactions (threads) need to go to a common place to do something, probably to get a unique transaction time-stamp. The solution I designed is like this, it needs a unique time-stamp for each transaction. For the GC to do its work properly, I also need a list of all transactions. So instead of using one AtomicLong.incrementAndGet(), I have replaced it with one AtomicReference.compareAndSet().
