Misplaced Optimism (Ruby STM, Round 3.5)
Earlier:
For Round Two, I identified optimistic concurrency control as a desirable feature for our STM implementation. In a nutshell, optimistic concurrency control means avoiding locks in favor of methods to passively detect whether a transaction reads inconsistent data during its execution, and retrying it if so. In this sense, GHC’s STM implementation is entirely optimistic; it uses a versioning scheme to detect if one transaction has conflicted with another. Meanwhile, Ennals’ C STM implementation (after which my STM library was originally patterned) uses locking for writes, but an even more optimistic strategy for reads.
The trouble with optimistic strategies is that validation only at the end of a transaction isn’t sufficient, becuase one of the possible outcomes of working with inconsistent state is an infinite loop. On the other hand, validating the transaction at every read (which would prevent the loop) is prohibitively expensive. Additionally, the loop might not involve any transactional operations (involving only local variables, say) which would otherwise provide us an easy foothold to perform periodic validation. So, we are faced with periodically interrupting the transaction at arbitrary points to ensure that it is still valid, and that requires the connivance of the scheduler.
Sadly, hooking into Ruby’s thread scheduler isn’t an easy option for a pure Ruby library, or even for a C extension. As a result, Ruby STM will remain entirely lock-based for now. Next time, we’ll take a look at timeouts, which turn out to be easier than expected to implement in some ways, but much more difficult in others.