Where communities thrive

Join over 1.5M+ people
Join over 100K+ communities
Free without limits
Create your own community

Explore more communities

cats-stm/community

People

Repo info

Activity

Christopher Davenport

@ChristopherDavenport

Do you have any work I could base investigation on? Would love to try to find whatever deadlock we’ve run into.

Tim Spence

@TimWSpence

Thanks Chris! Yeah, I’ve struggled to find time the last week. I would love to fix it too! I’ve got some stuff I’ll push tomorrow morning

Tim Spence

@TimWSpence

Hey @ChristopherDavenport I actually merged some of my changes as they fix some definite bugs around retries and they don’t always lock up when running the santa claus problem. I’ve also pushed to a branch debug-santa-claus that you might want to look at. At the moment, all it has is two print statements looping in fibers but the interesting thing is that they keep printing even when the santa problem stops so I don’t think we have thread deadlock. It looks to me like we aren’t correctly identifying/tracking opporunities to retry txns. The print shows that it gets stuck in a state where there are some pending transactions that never get retried

Oleg Pyzhcov

@oleg-py

It looks to me like we aren’t correctly identifying/tracking opporunities to retry txns

I had exactly the same issue in my STM, btw, and it was due to two threads acting on retries in parallel, one beginning a retry the very same moment another added one on top.

Everything just worked in a single thread setting
I ended up using a transaction ID to check "if a last-transaction-written has changed for any of the variables, retry immediately" (though it sounds easier than it was to actually fix, it took me several attempts)

Tim Spence

@TimWSpence

Thanks @oleg-py I keep meaning to check your implementation out, it looks really interesting! In theory, all my state is modified inside a global lock so mine shouldn’t have that problem but I could well have missed something!

Also a big fan of better monadic for btw :)

Oleg Pyzhcov

@oleg-py

If I understand your code correctly, you modify the var state in lock, but not the callbacks in AtomicReferences

You can also probably use STM.synchronized { ... } instead of semaphore for easy scala-js compatibility (synchronized does nothing on SJS, but using Java semaphore causes linking errors)

Tim Spence

@TimWSpence

@oleg-py when did you lock at the code? I believe that should no longer be the case but it is Friday evening so who knows :joy: If it is still true, I would definitely like to know!

Oleg Pyzhcov

@oleg-py

I looked yesterday :D Well, you still rerun pending without a lock (in flatTap), so it can race with adding them (with a lock). Also flatTap can cause problems wrt cancellation

Tim Spence

@TimWSpence

😂 But the set of txns to rerun is collected while the lock is held? Or am I just being a complete idiot?

Also thanks, what problems can it cause? I thought asyncwas uncancelable anyway?

Oleg Pyzhcov

@oleg-py

Yeah, but the code in flatTap isn't

Oleg Pyzhcov

@oleg-py

Didn't notice the collection - not sure it's enough though, because another transaction can happen just between the collection and execution

Tim Spence

@TimWSpence

THanks for the tip about synchronized! I tried that and moved the retry logic inside the lock but that doesn’t fix it

Which I think makes sense - if txn 1 succeeds and then txn 2 retries before 1 calls rerunPending, 2 shouldn’t be eligible to rerun anyway

I think :joy:

Oleg Pyzhcov

@oleg-py

Well, you might have a different problem with your implementation :D

Tim Spence

@TimWSpence

:joy: Thanks for the help anyway! I made the change to synchronized anyway - it also simplifies the logic as it’s safe to call while you already have the lock. Really struggling to see where the bug is hiding now...

Tim Spence

@TimWSpence

So I found the issue… TimWSpence/cats-stm#21 :joy: Seems like there might be some work to do on fairness - on my machine at least it seems to eventually only run the reindeer but apart from that it seems stable now

@ChristopherDavenport in particular :point_up:

Christopher Davenport

@ChristopherDavenport

Fairness is much better than deadlock.

Tim Spence

@TimWSpence

Agreed!! I’m making a release now so that we have a working release out there

Ross A. Baker

@rossabaker

:tada:

Tim Spence

@TimWSpence

a depressingly simple fix in the end

Christopher Davenport

@ChristopherDavenport

Well removing a succesful transaction seems… reasonable. :smile:

Ross A. Baker

@rossabaker

$1 to remove the line, $9999 to know which one to remove.

Christopher Davenport

@ChristopherDavenport

Note to self: Figure out how to get Ross’s consulting rates.

Tim Spence

@TimWSpence

😂

Ross A. Baker

@rossabaker

That one is often ascribed to Nikola Tesla visiting Henry Ford. Would have been a real good rate back then.

Christopher Davenport

@ChristopherDavenport

That change looks great. So now for transaction fairness. I think the way the problem is designed is that the action is happening on the side so once we always have all the reindeers, it wins via that actions.reduceLeft(_.orElse(_))

The print would need to take longer 0.01 seconds. Going to retry with higher values as it may be a matter of the concurrency rather than the atomicity.

Christopher Davenport

@ChristopherDavenport

So I introduced a CS to shift and no change to final behavior.

Christopher Davenport

@ChristopherDavenport

@TimWSpence So how are we doing? I’m still a little worried about our blockage here.

Tim Spence

@TimWSpence

@ChristopherDavenport sorry, haven’t had much time to work on this recently! What did you mean by blockage sorry? I’ve had a bit of a look into retry fairness but haven’t gotten to the bottom of it yet

PS you can see my attempted fix here: TimWSpence/cats-stm@11aef71 I might actually merge this anyway as it seems like the right thing to do - we will now retry transactions that have been waiting longer first. However it still doesn’t seem to fix the behaviour of the Santa Claus problem

Tim Spence

@TimWSpence

Oh sorry, I just re-read your previous comment. I’ll try combining my change above with the one you suggested and see if that fixes it

Christopher Davenport

@ChristopherDavenport

The issue is that without some level of fairness, we are in a position where I cant reliably expect an action that should logically occur to happen.

As in the elves are ready but they are never happening and not because they weren’t waiting. As obviously they were done.

Tim Spence

@TimWSpence

Yeah, so I believe the change linked above should fix the fairness. But I’m suspicous of this as well: https://github.com/TimWSpence/cats-stm/blob/master/examples/src/main/scala/io/github/timwspence/cats/stm/SantaClausProblem.scala#L74 I’m just trying to think through what that will do but creating new gates every time looks strange to me?

And yes, I agree that lack of fairness is a significant problem :joy:

Tim Spence

@TimWSpence

It think it is fine actually, it just wasn’t what I expected at first. Which leaves me back at square one :sob:

Christopher Davenport

@ChristopherDavenport

Yeah. :cry:

Tim Spence

@TimWSpence

Timer[IO].sleep(n.micros) this shouldn’t block a thread, should it? If I add a 0 to the random int bound then the whole program seems to block sometimes

Christopher Davenport

@ChristopherDavenport

It shouldn’t block on a thread I believe

Tim Spence

@TimWSpence

Yeah, I didn’t think so. I’ve probably done something else stupid

Tim Spence

@TimWSpence

@ChristopherDavenport good news! After a 7 month sebatical (to be fair, I was on paternity leave for quite a bit of it), I’ve fixed our issues with this :)

(Or at least the Santa Claus example now behaves as expected)

I’ve published 0.6.0 with the changes

Ross A. Baker

@rossabaker

:tada: Welcome back, and congrats!