5 ms·

This is a cool technical exploration of some concurrency ideas: but event loops combined with Rust's borrow checker actually make for a re-invention of the acto

This is a cool technical exploration of some concurrency ideas: but event loops combined with Rust's borrow checker actually make for a re-invention of the actor model from first principles. Languages like Pony, and the actor model more generally, were designed to prevent a whole class of concurrency bugs (same as Rust) - what's interesting is that, like this post shows, they also have unexpected problems with message causality. It makes me wonder if there's an even better abstraction out there which will solve this kind of concurrency bug, and what will arise after these are solved.

zzzcpan 6y ago
I'm pretty sure the exact problems the article describes can be solved with proper implementation of actor model, i.e. Erlang-style implementation, where actors can be killed, dying actors can cause messages to be send and messages can be received in specified order. Basically lack of proper richer actor primitives is what pushed them into the mess they are in.
- fzzzy 6y ago
  I agree with this. Supervision is an essential part of the erlang model.
- toast0 6y ago
  The problem described in the article could also exist if you followed the same messaging flow. Erlang and OTP may make it easier to have a better flow, but it's not a magic bullet. Plenty of ways to write race conditions and get unexpected message orderings (especially on a multinode system)
  - dnautics 6y ago
    Yeah this happens a lot, and in practice it's not a big deal. I noticed that when I redeploy, there's a nondeterministic flurry of errors in my system on the node that restarts. Finally I came to understand that this was race conditions. But it's honestly not a big deal. The system restarts anything in a funny state and moves on with its life. I feel like if you have something exquisitely race-condition sensitive that you aren't aware that it should be so, then you're not using OTP correctly.
mcintyre1994 6y ago
I haven't gotten to use it yet, but I think Pony would at least claim to prevent this problem. On https://tutorial.ponylang.io/types/at-a-glance.html https://tutorial.ponylang.io/types/at-a-glance.html it says: > All message passing is causal. (Not casual!) The word 'causal' is hyperlinked to https://courses.cs.vt.edu/~cs5204/fall00/causal.html https://courses.cs.vt.edu/~cs5204/fall00/causal.html which contains: > The purpose of causal ordering of messages is to insure that the same causal relationship for the "message send" events correspond with "message receive" events. (i.e. All the messages are processed in order that they were created.)
- ivanbakel 6y ago
  Not at all - in fact, the problem described in the article is a typical pitfall of the causal ordering system. In a simplified version: A -1-> B B -2-> C A ---3------> C The human expectation is that 2 happens "before" 3, because that's how it looks. The reality is that 1 happens before 3, and 1 happens before 2, but 2 and 3 have no causal relation - and the runtime is free to rearrange them in any order. That's why the solution is essentially A -1-> B B -2-> C B -3-> C Because then 2 really happens before 3.
  - mratsim 6y ago
    Everyone dealing with actors, multithreading, distributed systems should read about Vector Clocks: - https://en.wikipedia.org/wiki/Vector_clock https://en.wikipedia.org/wiki/Vector_clock - Detecting Causal Relationships in Distributed Computations:In Search of the Holy Grail, Schwarz et al - http://www.vs.inf.ethz.ch/publ/papers/holygrail.pdf http://www.vs.inf.ethz.ch/publ/papers/holygrail.pdf
    - hugey010 6y ago
      Now that's some CS I wasn't even aware of! Although, I'm confused why those process clocking topics are considered specific to distributed systems and not computation in general.
  - 6y ago
SAI_Peregrinus 6y ago
> and what will arise after these are solved. Look at unintuitive situations in special relativity. The unituitiveness is essentially a concurrency bug in our mental model of how the universe works, as opposed to how it actually works. Almost all of the issues are due to mistaken ideas about what it means for two events to happen "at the same time" or in a given order. I suspect programming concurrency will continue to create bugs because humans ideas of time don't actually match up to reality. Obviously not usually due to relativity, but there are all sorts of complexities in the underlying systems we program for that intuition doesn't capture well.
oconnor663 6y ago
I think the fundamentally tricky part is that sometimes you want your concurrent code to have this sort of nondeterministic behavior. I think the Rayon FAQ does a good job of summarizing the problem: https://github.com/rayon-rs/rayon/blob/master/FAQ.md#but-wait-isnt-rust-supposed-to-free-me-from-this-kind-of-thinking https://github.com/rayon-rs/rayon/blob/master/FAQ.md#but-wai... > Consider for example when you are conducting a search in parallel, say to find the shortest route. To avoid fruitless search, you might want to keep a cell with the shortest route you've found thus far. This way, when you are searching down some path that's already longer than this shortest route, you can just stop and avoid wasted effort...Now in this case, we really WANT to see results from other threads interjected into our execution!
- ivanbakel 6y ago
  Oh, certainly. You don't want programmers to go around insisting there's a global ordering to their message systems. But the problem I think could be solved is where programmers have a causal dependency, but they don't encode it in the program. The next generation of concurrent languages could have the killer correctness features for solving causality problems.
- polyglotfacto 6y ago
  Yes, I would say the tricky part is accurately modelling what you want. Also, instead of actual nondeterministic behavior, I think that you rather want different things to be deterministic. The article is an example of "task parallelism", where you have different threads doing different things on different (local) data. Having those threads communicate via message-passing is a nice way to model workflows crossing thread boundaries, and in that setup you usually want some sort of deterministic behavior related to the ordering of operations(for a given workflow). On the other hand, I think the Rayon example is a good case of "data parallelism", where you have workers doing "the same thing" on "the same (shared-)data". In such a case, perhaps locks and shared-data are a better fit than message-passing, and indeed what you're after is not necessarily some sort of sequential ordering of worker operations. However you still probably want the ability to make other deterministic assertions about the behavior of the workers. I wrote another article highlighting some of these "different determinism" at https://medium.com/@polyglot_factotum/rust-concurrency-five-easy-pieces-871f1c62906a?source=friends_link&sk=fa043036d86e078fd7a50c7f109c1163 https://medium.com/@polyglot_factotum/rust-concurrency-five-...
dnautics 6y ago
>It makes me wonder if there's an even better abstraction out there which will solve this kind of concurrency bug, and what will arise after these are solved. You could go the erlang way, which is to give up. Unexpected concurrency bug? Crash, then restart from a sane state. It's highly effective. Your VM is carved up into failure domains that reduce the blast radius of such a crash to the minimum reasonable collection of processes. This is what frameworks like pony don't get. The reason why erlang actors (aka microservices) are so effective is that they declare, define, and decouple failure domains, and assign responsibility over these failure domains to specific bits of code and ultimately specific teams.
- staticassertion 6y ago
  I agree with all of your post except for the premise - concurrency bugs won't necessarily lead to a crash, but often just a bad result.
  - dnautics 6y ago
    that's not the premise. Maybe I should reframe it this way: you should detect inconsistent results and use "crash" as a strategy to restore consistency. Also of importance is to log these events and work towards fixing the concurrency bug by addressing the root cause in the long run with application monitoring.
    - staticassertion 6y ago
      Ah, ok sure.
    - senderista 6y ago
      That’s one thing about Erlang that took me too long to grok: “let it crash” applies to bugs, not expected errors.
      - dnautics 6y ago
        Haha also i guess you might also decide that correctness is unimportant. How often does this bug happen? Is it a once-a-week thing with no user-facing effect? Just let it ride until you're scaling hard. Your labor as a programmer is expensive, no need to chase down every possible bug.

zzzcpan 6y ago

I'm pretty sure the exact problems the article describes can be solved with proper implementation of actor model, i.e. Erlang-style implementation, where actors can be killed, dying actors can cause messages to be send and messages can be received in specified order. Basically lack of proper richer actor primitives is what pushed them into the mess they are in.

fzzzy 6y ago
I agree with this. Supervision is an essential part of the erlang model.
toast0 6y ago
The problem described in the article could also exist if you followed the same messaging flow. Erlang and OTP may make it easier to have a better flow, but it's not a magic bullet. Plenty of ways to write race conditions and get unexpected message orderings (especially on a multinode system)
- dnautics 6y ago
  Yeah this happens a lot, and in practice it's not a big deal. I noticed that when I redeploy, there's a nondeterministic flurry of errors in my system on the node that restarts. Finally I came to understand that this was race conditions. But it's honestly not a big deal. The system restarts anything in a funny state and moves on with its life. I feel like if you have something exquisitely race-condition sensitive that you aren't aware that it should be so, then you're not using OTP correctly.

mcintyre1994 6y ago

I haven't gotten to use it yet, but I think Pony would at least claim to prevent this problem. On https://tutorial.ponylang.io/types/at-a-glance.html https://tutorial.ponylang.io/types/at-a-glance.html it says: > All message passing is causal. (Not casual!) The word 'causal' is hyperlinked to https://courses.cs.vt.edu/~cs5204/fall00/causal.html https://courses.cs.vt.edu/~cs5204/fall00/causal.html which contains: > The purpose of causal ordering of messages is to insure that the same causal relationship for the "message send" events correspond with "message receive" events. (i.e. All the messages are processed in order that they were created.)

ivanbakel 6y ago
Not at all - in fact, the problem described in the article is a typical pitfall of the causal ordering system. In a simplified version: A -1-> B B -2-> C A ---3------> C The human expectation is that 2 happens "before" 3, because that's how it looks. The reality is that 1 happens before 3, and 1 happens before 2, but 2 and 3 have no causal relation - and the runtime is free to rearrange them in any order. That's why the solution is essentially A -1-> B B -2-> C B -3-> C Because then 2 really happens before 3.
- mratsim 6y ago
  Everyone dealing with actors, multithreading, distributed systems should read about Vector Clocks: - https://en.wikipedia.org/wiki/Vector_clock https://en.wikipedia.org/wiki/Vector_clock - Detecting Causal Relationships in Distributed Computations:In Search of the Holy Grail, Schwarz et al - http://www.vs.inf.ethz.ch/publ/papers/holygrail.pdf http://www.vs.inf.ethz.ch/publ/papers/holygrail.pdf
  - hugey010 6y ago
    Now that's some CS I wasn't even aware of! Although, I'm confused why those process clocking topics are considered specific to distributed systems and not computation in general.
- 6y ago

SAI_Peregrinus 6y ago

> and what will arise after these are solved. Look at unintuitive situations in special relativity. The unituitiveness is essentially a concurrency bug in our mental model of how the universe works, as opposed to how it actually works. Almost all of the issues are due to mistaken ideas about what it means for two events to happen "at the same time" or in a given order. I suspect programming concurrency will continue to create bugs because humans ideas of time don't actually match up to reality. Obviously not usually due to relativity, but there are all sorts of complexities in the underlying systems we program for that intuition doesn't capture well.

oconnor663 6y ago

I think the fundamentally tricky part is that sometimes you want your concurrent code to have this sort of nondeterministic behavior. I think the Rayon FAQ does a good job of summarizing the problem: https://github.com/rayon-rs/rayon/blob/master/FAQ.md#but-wait-isnt-rust-supposed-to-free-me-from-this-kind-of-thinking https://github.com/rayon-rs/rayon/blob/master/FAQ.md#but-wai... > Consider for example when you are conducting a search in parallel, say to find the shortest route. To avoid fruitless search, you might want to keep a cell with the shortest route you've found thus far. This way, when you are searching down some path that's already longer than this shortest route, you can just stop and avoid wasted effort...Now in this case, we really WANT to see results from other threads interjected into our execution!

ivanbakel 6y ago
Oh, certainly. You don't want programmers to go around insisting there's a global ordering to their message systems. But the problem I think could be solved is where programmers have a causal dependency, but they don't encode it in the program. The next generation of concurrent languages could have the killer correctness features for solving causality problems.
polyglotfacto 6y ago
Yes, I would say the tricky part is accurately modelling what you want. Also, instead of actual nondeterministic behavior, I think that you rather want different things to be deterministic. The article is an example of "task parallelism", where you have different threads doing different things on different (local) data. Having those threads communicate via message-passing is a nice way to model workflows crossing thread boundaries, and in that setup you usually want some sort of deterministic behavior related to the ordering of operations(for a given workflow). On the other hand, I think the Rayon example is a good case of "data parallelism", where you have workers doing "the same thing" on "the same (shared-)data". In such a case, perhaps locks and shared-data are a better fit than message-passing, and indeed what you're after is not necessarily some sort of sequential ordering of worker operations. However you still probably want the ability to make other deterministic assertions about the behavior of the workers. I wrote another article highlighting some of these "different determinism" at https://medium.com/@polyglot_factotum/rust-concurrency-five-easy-pieces-871f1c62906a?source=friends_link&sk=fa043036d86e078fd7a50c7f109c1163 https://medium.com/@polyglot_factotum/rust-concurrency-five-...

dnautics 6y ago

>It makes me wonder if there's an even better abstraction out there which will solve this kind of concurrency bug, and what will arise after these are solved. You could go the erlang way, which is to give up. Unexpected concurrency bug? Crash, then restart from a sane state. It's highly effective. Your VM is carved up into failure domains that reduce the blast radius of such a crash to the minimum reasonable collection of processes. This is what frameworks like pony don't get. The reason why erlang actors (aka microservices) are so effective is that they declare, define, and decouple failure domains, and assign responsibility over these failure domains to specific bits of code and ultimately specific teams.

staticassertion 6y ago
I agree with all of your post except for the premise - concurrency bugs won't necessarily lead to a crash, but often just a bad result.
- dnautics 6y ago
  that's not the premise. Maybe I should reframe it this way: you should detect inconsistent results and use "crash" as a strategy to restore consistency. Also of importance is to log these events and work towards fixing the concurrency bug by addressing the root cause in the long run with application monitoring.
  - staticassertion 6y ago
    Ah, ok sure.
  - senderista 6y ago
    That’s one thing about Erlang that took me too long to grok: “let it crash” applies to bugs, not expected errors.
    - dnautics 6y ago
      Haha also i guess you might also decide that correctness is unimportant. How often does this bug happen? Is it a once-a-week thing with no user-facing effect? Just let it ride until you're scaling hard. Your labor as a programmer is expensive, no need to chase down every possible bug.