Haskell: TVar: Preventing Hunger

Question

I am considering using TVar to store some state in a web application (which can be recreated on reboot). However, the controversial aspects of TVar apply to me. It seems that a frequent short transaction can drive out long transactions, constantly interrupting them. In addition, since longer transactions continue to restart, this will increase the CPU load, which will further increase the length of these transactions. In the end, I feel that this can lead to the server becoming completely unresponsive.

Given this, I have the following questions:

(1) Can TVar (or another data type) use locks rather than simultaneous attempts / retries.

(2) Can TVar (or another data type) have some other competitive mechanism, that is, “allow transactions to start one second before another transaction starts”, or at least some of them guarantee the completion of transactions (i.e. a competing algorithm that prevents starvation for longer transactions).

Answer 1

This is just a problem if you have a lot of cheap transactions that update data and a few expensive ones that read it. Analytics on an updated dataset, perhaps.

If you are really worried about this, consider using the TVar flag. Set to false and make sure that it is false at the beginning of every cheap transaction, calling retry otherwise. Then just set it to true before entering your long transaction and set it to false when exiting. Alternatively, you can simply protect your fortune with TMVar . Your long-term calculation atomically accepts tmvar, does what it looks like, and then returns it. Other transactions take place entirely within one real STM transaction.

Remember also that a long STM transaction is a complex beast. Because of laziness, you can put expensive value in var cheaply. You can also quickly view a “snapshot” of data from a whole bunch of vars. To have a really long transaction, you need to read the whole chain of vars, and then, based on what you read, figure out which vars you are going to write new values ​​to (or read values ​​from), and this calculation itself should be expensive. You are probably not even in this scenario to get started!

Answer 2

I don’t think there is a way to guarantee freedom of hunger unless you change the runtime code of the STM system itself. In my opinion, the inclusion of locks to avoid disagreements between TVars leads to the fact that the goal is to have STM in the first place, since the whole point of using STM is to get rid of the classic error-based approach for parallel programming .

Of course, starvation can lead to significant performance losses, but only on the assumption that such large transactions are really necessary. One design principle that I try to keep in mind is to use TVars at a low level of detail. For example, instead of putting the whole Data.Map in TVar , which can cause a conflict every time a record is updated, you can use a more STM-friendly data structure, for example, skiplists [1].

[1] http://hackage.haskell.org/package/tskiplist

Answer 3

This was written as a commentary on one of Clinton's statements regarding Peters' response. But it has become long.

Please note that you have two bank accounts: A and B. Each of them is protected by its own lock. Now you have two transactions: the first transfers money from A to B, and the second - from B to A. First, it takes a lock on the source account and then on the target account, transfers the money and releases the locks. If you are unlucky that two transactions go deadlocked and nothing is done with these two accounts. If you do this in STM, they will work one after another. If you have endless many of the first kind, they can starve the second transaction. But you still do a lot. Although nothing happens with fixation.

STM guarantees that there are no data races with TVars! No way. With commit, you can come to that conclusion after a very thorough inspection of your code. And each line added can completely exclude your conclusion.