Coordinated transaction (CommitBarrier) fails because of time out

33 views
Skip to first unread message

Matthias Rahne

unread,
Mar 7, 2014, 11:36:21 AM3/7/14
to scala-stm-e...@googlegroups.com
Hi all,

I'm struggling with a problem, where the stm seems to find no successful back off strategy.
Let's illustrate this with the bank transfer example. I have a somewhat simplified class "Account" and an actor "Transaction" that starts a coordinated transaction between two transactors.

class Account(inBalance:Double) {

    val balance = Ref(inBalance)
}

class Transaction(from:Account, to:Account, amount:Double) extends Actor {
    val source = context.actorOf(Props(classOf[TransactionSource], from))
    val sink = context.actorOf(Props(classOf[TransactionSink], to))

    def receive = {
        case Execute =>
            implicit val timeout = Timeout(1 second)
            val coordinatedSource = Coordinated(Withdraw(amount))
            val coordinatedSink = coordinatedSource.coordinate(Deposit(amount))
            source ! coordinatedSource
            sink ! coordinatedSink
    }
}

class TransactionSource(account:Account) extends Transactor {
    def atomically = implicit txn ⇒ {
        case withdraw:Withdraw =>
            account.balance -= withdraw.amount
    }
}

class TransactionSink(account:Account) extends Transactor {
    def atomically = implicit txn ⇒ {
        case deposit:Deposit =>
            account.balance += deposit.amount
    }
}

If I execute two bank transactions on the same two accounts, the coordinated transactions fail most of the time because of a time out.

val account1 = new Account(10.0)
val account2 = new Account(10.0)

val transaction1 = system.actorOf(Props(classOf[Transaction], account1, account2, 1.0))
val transaction2 = system.actorOf(Props(classOf[Transaction], account1, account2, 2.0))

transaction1 ! Execute
transaction2 ! Execute

What is the reason for this and is there anything I can do about it?

Thanks,
Matthias


Matthias Rahne

unread,
Mar 8, 2014, 9:05:27 AM3/8/14
to scala-stm-e...@googlegroups.com
For greater clarity I removed the actor stuff and only used the CommitBarrier. The result is the same with the transactions failing most of the time because of a timeout.

val a1 = Ref(0)
val a2 = Ref(0)

val cb1 = CommitBarrier(1000)
val cb1m1 = cb1.addMember()
val cb1m2 = cb1.addMember()
val cb2 = CommitBarrier(1000)
val cb2m1 = cb2.addMember()
val cb2m2 = cb2.addMember()

val t1 = new Thread() {
override def run() {
cb1m1.atomic { implicit txn => a1() = a1() + 1 } 
}
}
val t2 = new Thread() {
override def run() {
cb1m2.atomic { implicit txn => a2() = a2() + 1 }
}
}
val t3 = new Thread() {
override def run() {
cb2m1.atomic { implicit txn => a1() = a1() + 1 }
}
}
val t4 = new Thread() {
override def run() {
cb2m2.atomic { implicit txn => a2() = a2() + 1 }
}
}

t1.start(); t2.start(); t3.start(); t4.start()
t1.join(); t2.join(); t3.join(); t4.join()

println(a1.single());
println(a2.single());

Nathan Bronson

unread,
Mar 8, 2014, 10:31:54 AM3/8/14
to scala-stm-e...@googlegroups.com
Thanks for simplifying, it is indeed a deadlock.

It's tricky: ScalaSTM internally assigns transactions priorities that are part of the way forward progress is guaranteed. In the current implementation the separate threads of a commit barrier have separate priorities, so when they are unified we effectively bypass some of the cycle prevention logic. There is a separate cycle detector for CommitBarrier unifications that can never succeed (such as two threads of a CommitBarrier both modifying the same Ref), but in this case the cycle is only an artifact of the schedule.

Intuitively we can solve this by synchronizing the priorities among the CommitBarrier members, but I haven't fully worked it out yet. There might be a complication around the read locks used when a big transaction is having trouble winning over small transactions (our solution to the starving elder pathology). I'll keep you posted on my progress.

 - Nathan


--

---
You received this message because you are subscribed to the Google Groups "Scala STM Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-stm-expert-...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.



--
Nathan Grasso Bronson
ngbr...@gmail.com

Matthias Rahne

unread,
Mar 10, 2014, 9:53:23 AM3/10/14
to scala-stm-e...@googlegroups.com
Many thanks for your reply and the insights given.

Regards
– Matthias
To unsubscribe from this group and stop receiving emails from it, send an email to scala-stm-expert-group+unsub...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.
Reply all
Reply to author
Forward
0 new messages