Moonbase

So far:

1. Ruby STM: First Round
2. Ruby STM: Round Two
3. STM Deadlocks
4. Ruby STM: Round the Third
5. Misplaced Optimism

Another feature I’d wanted for my Ruby STM library was the ability to assign a timeout to a (sub-)transaction. It’s obvious enough how to do this for transactions, but sub-transactions? Well, what does a timeout on a sub-transaction mean, anyway? And how would you implement it?

One of the chief difficulties is that a transaction can be retried arbitrarily many times. Say the sub-transaction times out, but the parent transaction retries. Should the sub-transaction be retried? Probably not—but if not, how do we associate a particular section of code with a sub-transaction? If so, do we simply restart the clock? What about reentrancy? Are any of those behaviors really useful?

Then I went back and reread Discolo, et al. As usual, seeing the problem formulated in Haskell made it a lot clearer— in the paper, the type of pollSTM is ArrayBlockingQueueSTM e -> STM (Maybe e), whereas the type of pollTimeoutSTM is ArrayBlockingQueueSTM e -> TimeDiff -> IO (Maybe e). In other words, timeouts don’t compose. You have to assign a timeout to an entire transaction, or not at all.

On the other hand, the concern I had in part two—that timeouts would require special treatment by the transaction scheduler—turned out to be unfounded. It’s true that transactions can block on each others’ locks, but they won’t do so for long periods of time. If a transaction needs to block for long periods (i.e. due to a retry), then it will release all of its locks and allow other transactions to proceed. As a result, something like the naive implementation of timeouts I had originally proposed should work just fine:

def timeout( duration )
  timed_out = Atomic::Variable.new
  Thread.new { sleep duration ; timed_out[] = true }
  Atomic.atomic do
    result = nil
    if Atomic.retries? { result = yield }
      Atomic.retry unless timed_out[]
      raise Atomic::TimeoutError
    end
    result
  end
end

The only additional requirement is a bit of logic to raise an error if someone attempts to call timeout from within an existing transaction.