9 ms·

A few notes on message passing

151 points by srijan4 6y ago

chrisseaton 6y ago
The big problem nobody talks about with actors and message passing is non-determinism and state. If two otherwise independent processes A and B are sending messages to a single process C, it's non-deterministic which arrives at C first. This can create a race condition. C may respond differently depending on which messages arrives first - A's or B's. This is also effectively an example of shared mutable state - the state of C, which can be mutated whenever a message is received - is shared with A and B because they're communicating with it and their messages work differently based on the current state. Non-determinism, race-conditions, shared mutable state: the absolute opposite of what we want when dealing with concurrency and parallelism.
- zimpenfish 6y ago
  > The big problem nobody talks about with actors and message passing is non-determinism and state. Seems to be mentioned in the article, with an example: > If more than one process sends signals to a common process, they can arrive in any order even when you “know” that one of the signals was sent first.
  - chrisseaton 6y ago
    Right - that's what triggered my comment - but I think it's a bigger footgun than the article does. The problem is this corner case opens up all the fundamental issues I mention. When we include it we've got a big non-deterministic, racey, stateful, problem.
    - jerf 6y ago
      In practice, I don't think it is for real Erlang programs. If you need total order, route everything that needs that order through one process, and you have it. For instance, you can use that to impose total order on messages in a chat room. As long as "one chat room" is small enough for that to be practical even at your largest size, it works. If that doesn't work, don't use Erlang. No sarcasm. The process model is nice but does preclude certain high-performance patterns.
    - uwiger 6y ago
      Experience shows that it really isn't. The fundamental issues of non-deterministic ordering are inherent in the domain that Erlang was designed for, and the VM characteristics pretty closely reflect that. It turns out that people have comfortably written complex and scalable commercial systems in Erlang for decades, and many have noted that for people who understand the problem domain, the Erlang model feels intuitive. The problem of message order non-determinisim is real, but for orchestration logic in scenarios with multiple uncoordinated message sources, it's inescapable. What is important is that the programming environment helps you deal with it, and doesn't introduce additional - "accidental" - complexity. I discussed this topic at QCon 2010, and ran through some demos to illustrate where many commercial projects actually DO go wrong, and why the textbook Erlang model keeps you safe. https://www.infoq.com/presentations/Death-by-Accidental-Complexity/ https://www.infoq.com/presentations/Death-by-Accidental-Comp... The key guarantees that Erlang gives you here are: * Messages from A to B will all arrive (if they arrive) in the order in which they were sent, and you can detect if there is an interruption * A receiving process can decide in which order messages are processed. It turns out that people intuitively understand that if Alice and Bob each send me a message, independently of each other, I cannot know which message reaches me first. This mirrors a fundamental real-world constraint, and in a distributed processing environment, there really isn't much you can do about it. There are other concurrency-related problem domains, some for which the Erlang implementation, at least, is not ideal.
- deleted 6y ago
  [deleted]
- toast0 6y ago
  Often, the order of messages doesn't matter that much. When it does matter, there are a couple patterns to consider. a) be sure to give C whole requests, don't ask C for current data, modify it in A and then send it back to C (which is begging for B to send a modification in the mean time). C's mailbox enforces an ordering on requests (all calls will be handled in the order they are received, not in the order they are sent) b) rather than A sending to B and C, and B also sends to C, send only from A to B and from B to C. B sends along A's information. Downside is if B crashes before sending to C, A's information is lost. You could also have A send to C, and C replies to B, which then does work and sends back to C. c) when multiple processes are working on a single thing, try to combine them. A single process will find it hard to race with itself, and will have a clear order of events. I'm in the middle of cleaning up some code that had three processes around one thing (a state process, a reader and a writer), and there were so many weird and racy things because of the separation; putting it into one process means things can't change unexpectedly.
  - yellowapple 6y ago
    > be sure to give C whole requests, don't ask C for current data, modify it in A and then send it back to C (which is begging for B to send a modification in the mean time) A simple mitigation against these sorts of race conditions would be for C to maintain a version number alongside its data, then have any update requests send back that version number. If the message's version matches the current, then do the update and change the version number; else, reject the message with a reply directing the sender to reobtain the current data and try again. This way, if both A and B grab data from C and then simultaneously try to update that data in C, you won't lose any data. This is (relevantly to Erlang) exactly how CouchDB works.
    - catlifeonmars 6y ago
      I believe this is called “optimistic locking”
- ramy_d 6y ago
  Erlang has a bunch of tools to help enforce determinism or at least suss out concurrency issues. For example: you can specify multiple receive statements to process your queued messages in a specific order, there is also a process manager (pman:start()) that allows you to explore concurrency related events, and not to mention Mutex Semaphores as a pattern to mitigate those issues. There doesn't seem to be a real solution to deadlocks. I got the oreilly book in front of me and it's basically saying: be careful, but don't worry. And I don't think erlang has a shared mutable states. In fact a google search for "erlang shared mutable state" has you as the first result.
  - chrisseaton 6y ago
    > And I don't think erlang has a shared mutable states An actor has state. It's mutable - each message can modify it. It's shared - two process working with a shared actor share that state. To me, that's shared mutable state. It causes classic race conditions. (I know this is an unpopular opinion, and somewhat deliberately contrary and provocative, but ultimately truthful.)
    - ProfHewitt 6y ago
      For many practical applications, deterministic parallelism is hundreds of times slower than indeterminate computation. For a proof, see the following article: "Epistemology Cyberattacks" https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021
      - deleted 6y ago
        [deleted]
      - jiehong 6y ago
        Is this some badly auto generated text? Reads like some.
        ProfHewitt 6y ago
        Current auto generators cannot yet deal with such esoteric content. So it must be real ;-)
- dragonwriter 6y ago
  > The big problem nobody talks about with actors and message passing is non-determinism and state. People talk about that all the time with actors and message passing, since the actor model is largely a tool for structuring the management of those things (not usually for eliminating them, because for many problem domains those are inherent to the domain.)
- ProfHewitt 6y ago
  Indeterminacy (using arbiters) is crucial to the performance of digital computation. (Arbiters are used in the interconnect of many-core chips.) See the following for an explanation: "Physical Indeterminacy in Digital Computation" https://papers.ssrn.com/abstract=3459566 https://papers.ssrn.com/abstract=3459566
  - chrisseaton 6y ago
    You can program a completely deterministic parallel system using a simple fork-join model, can't you? No physical or timing factors interfere with that, can they?
    - j-pb 6y ago
      The guy you just responded to invented the Actor model. I'd guess he knows... Besides, such a fork join model might be theoretically free of timing and coordination in a system with infinite resources (bus widths, no cache coherence, an infinitely fast coordinator e.t.c.) but that's not what silicon looks like. The nice thing about the Actor model is exactly that it immediately exposes you to non-determinism, distributed state, and in Erlangs case, failure. It's what allows Erlang systems to "effortlessly" (you had to put the effort upfront) span many node clusters with arbitrary reliability in the face of failures. Somewhere else you write: > The problem is this corner case opens up all the fundamental issues I mention. When we include it we've got a big non-deterministic, racey, stateful, problem. That's not caused by the Actor model, but by the fundamental laws governing distributed systems. Distributed systems are inherently, non-deterministic, racey and statefull. Two generals dictates that you can't solve these issues, unless you're on a single writer system (which your scatter-gather algorithm is an example of, in which you will always be limited by the throughput of the process that organises your scatter-gather operations / your control plane). In which case, you might as well ignore all forms of concurrency and do one thing at a time, which will be faster anyways.
      - deleted 6y ago
        [deleted]
      - 6y ago
- africanboy 6y ago
  it's true, but that's a problem every other implementation suffer from. synchronization is a basic requirement in concurrency. in my experience the actor model implemented in Erlang provides simpler solutions to the problem as highlighted in this comment https://news.ycombinator.com/item?id=26535230 https://news.ycombinator.com/item?id=26535230 for example if B sends a message to C in response to a message from A, it could send back a specific response to A that will contact C on its behalf and avoid the non determinism the fact that the actor model provides strong guarantees about messaging order between two actors, makes it easier to reason about it and avoid the pitfalls associated with it it is also a well known problem citing the Pony lang FAQ So for example, if actors X and Y send to actor Z, there is no guarantee what order the messages will be processed by Z except that we can say, all messages sent by X will be processed in the order they were sent, as will all messages sent by Y. However, messages from X and Y can arrive at Z interleaved in any order that maintains the causal ordering of X to Z and Y to Z.
- westurner 6y ago
  > Luckily, global orders are rarely needed and are easy to impose yourself (outside distributed cases): just let all involved parties synchronize with a common process. When there are multiple agents/actors in a distributed system, and the timestamp resolution is datetime64, and clock synchronization and network latency are variable, and non-centralized resilience is necessary to eliminate single points of failure, global ordering is impractical to impossible because there is no natural unique key with which to impose a [partial] preorder [1][2]: there are key collisions when you try and merge the streams. Just don't cross the streams. [1] https://en.wikipedia.org/wiki/Preorder_(disambiguation) https://en.wikipedia.org/wiki/Preorder_(disambiguation) [2] https://en.wikipedia.org/wiki/Partially_ordered_set https://en.wikipedia.org/wiki/Partially_ordered_set The C in CAP theorem is for Consistency [3][4]. Sequential consistency is elusive because something probably has to block/lock somewhere unless you've optimally distributed the components of the CFG control flow graph. [3] https://en.wikipedia.org/wiki/Consistency_model https://en.wikipedia.org/wiki/Consistency_model [4] https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem FWIU, TLA+ can help find such issues. [5] [5] https://en.wikipedia.org/wiki/TLA%2B https://en.wikipedia.org/wiki/TLA%2B
  - codebje 6y ago
    Wouldn't a partial order be possible using logical clocks? Vector clocks probably don't satisfy "practical" but a hybrid logical clock is practical if you can assume clock synchronisation is within some modest delta.
    - toast0 6y ago
      > if you can assume clock synchronisation is within some modest delta. From experience with clocks, you should really be actively testing the delta, and not just assuming it.
      - codebje 6y ago
        The assumption would be the limit you actively test for.
- dnautics 6y ago
  Yeah but the way you're framing the problem is a bit crazy. If such a race condition is critical, then making A and B "otherwise independent" is a poorly designed architecture (and, yes, novices will do this, which is why there is a big admonition in the Elixir docs: https://hexdocs.pm/elixir/master/GenServer.html#module-when-not-to-use-a-genserver https://hexdocs.pm/elixir/master/GenServer.html#module-when-...). Maybe they should all be branching logic or state machine in the same actor and you shouldn't be coordinating with message passing? If for some reason A and B TRULY need to be asynchronous and independent (let's say they are tracking real-world things), AND order matters, then no amount of language or VM architecture will get you out of building a transactional lock, consensus system, or CRDT to guarantee sane results. That is just how the universe works.
- bmitc 6y ago
  > The big problem nobody talks about with actors and message passing is non-determinism and state. I have written a lot of actor-based systems, and I’m pretty sure this is heavily talked and thought about. The race condition situation you described is only a problem for people not used to concurrency and actors. It is bad form to have your actor depend on the order of messages it receives if it is intended to receive messages from multiple actors. So the situation you’ve described is simply bad actor programming. Often, a good way to program actors is to have them be finite state machines. Also, your shared mutable state reference does not meet any definition I have ever seen of “mutable”. In actor systems, yes, actors can receive the state of other actors, but that state is a copy. The internal state of an actor is not allowed to be mutated by an external process, typically.
  - mrkeen 6y ago
    > your shared mutable state reference does not meet any definition I have ever seen of "mutable" Of course it is! > The internal state of an actor is not allowed to be mutated by an external process Having A tell C to mutate its state instead of A just mutating C's state is just like using a 'private' keyword in another language - insofar as mutation is concerned. Race conditions do not care if you ran: a() { kindlyInformCToIncreaseXWheneverYouGetThisMessage(); } versus a() { c.x++; } It's still a mutation.
    - srijan4 6y ago
      But, the internal state is still changed by the owner process, in the owner process' context. The external process cannot change it's state behind it's back. Effectively, mutations to the internal state are "serialized" by the owner process, so it's easier to handle possible race conditions without using explicit locks/semaphores.
    - hnedeotes 6y ago
      This shows exactly the problem but perhaps not in the context you're thinking of. One of the biggest strengths in processes in Erlang is that they serialise access, this serialisation though isn't simply that they serialise or are written in a way of "run this once". It's more like processes are (or can be used) basically state machines. This pattern is pervasive and you can find it in the OTP library, the most common construct (although there's proper finite state machine OTP abstractions) is the gen_server. The gen_server, is a generic server interface that uses message passing. It can be described as the simplest of agents that has a baked in generic interface. Where your sample falls short is that, when you code the interface for a gen_server I'm (or can, usually will) codify any needed relationship between the state a process is in and what it can do with the "messages" it receives according to the state it is in. This allows me to completely forgo of any concern about how someone will use it without having to explicitly define handling of cases I didn't intend. If I have (pseudo code but completely codifiable): - when msg and msg == "get_status" and state == "receiving" -> reply, function_that_calculates_response(state), new_state = make_new_state(state) - when msg and state == "not_available" -> reply unavailable, new_state = state, continue_to: "recheck_assumptions" - when "recheck_assumptions" and state -> noreply, new_state = check_assumptions(state) - when msg, state -> reply bad_request, new_state = state Now I don't have to worry about any nook, escape hatch or other such in the language, that someone will rewrite the state of this process from another thread, or function call or whatever. Nowhere will a process be able to change the state of this process from outside the process meaning I can clearly define the states it can assume. I also don't need to write overly defensive code, or find out that in some given situation something changed the state outside of what I explicitly coded. In the previous example this means that if two processes (running in different schedulers, nodes, or wtv) both send a msg, the mental model of the receiving gen_server will be a consistent mailbox from which it picks msgs to process one at a time. If one of the msgs would force the gen_server to change its state, and another asks for the status, it won't happen that both of them can have their conditions evaluated at the same time, but the states differing. So if msg_1 changes the state, msg_2 will be interpreted on this new state. It can't happen that msg_1 is being processed, changes the state in some intermediate step, while msg_2 is interpreted in the same exact conditions as msg_1 (unless msg_1 leaves the state as it was). This is not true for some mutable code, you can have two functions from different threads or whatever, call a function on X concurrently, and the evaluations for these calls being done based on the same state, while then fun1 and fun2 operates on the state. Perhaps fun2 assumed that it was allowed because of being in a given state, but while doing its thing that assumed that, the state had been changed by fun1 that was running at the same time. It also means, that this process can do whatever it wants, including spawning new processes and whatever, to do their thing in different contexts but its state can only be mutated by itself. This then forces those things (or me when writing code) to explicitly define their interface and if I want to rely on the result of those things changing the state, I need to explicitly message pass it back, for which I will have the previously defined interfaces. This then when coupled with supervision, links or monitors can make for extremely resilient processes even when they encode complex flows between multiple parts in the presence of possible unknowns. Can you still bork it? Yes, but the area is much smaller and I guess after a while of working with it it's a very simple model that once understood is always the same. Are there areas where this is not the right away to do it and mutable is right? Probably yes, people point out performance issues but I think there's also some overstating about it, in most cases it seems it can be solved, but I can believe there are possible issues there so not a silver bullet. Sorry for the long winded post.
- tpetry 6y ago
  This behaviour is intended in erlang and it‘s very good. You don‘t start to develop the application with wrong concepts. Your ordering from different producers will work on a single machine, but the second you want to upgrade to a distributed system everything will fail. In erlang you start designing everything with a distributed system in mind.
  - deleted 6y ago
    [deleted]
- BlackFly 6y ago
  Suppose something goes on auction on a website. Two clients on opposite sides of the globe launch bids at the same time. Of course the response depends on which bid arrives at the auction server first. This is exactly what you want when dealing with concurrency and parallelism: one of those two clients will be assigned the bid at that price and the auction will continue. The same thing happens in real life. You cannot solve this problem by using a shared memory model: it isn't inherent to the actor model, it is inherent to the reality of some situations. I have seen some people avoid referring to scenarios like this as race condtions, but in general there are some situations where you generally need to assign a winner (you have a serial actor decide or you use a lock). It could be real (like the auction example) or it could be bad design where a system has been architected to be unnecessarily concurrent and events that are in reality serial are fired off in parallel and the network (or even the thread scheduler or something else) reorders them. Try to avoid creating unnecessary races, learn to identify real races.
JetAlone 6y ago
"Messages are always copied before being inserted into the queue. As wasteful as this may sound it greatly reduces garbage collection (GC) latency as the GC never has to look beyond a single process. Non-copying implementations have been tried in the past, but they turned out to be a bad fit as low latency is more important than sheer throughput for the kind of soft-realtime systems that Erlang is designed to build." So the alternative to copying the message would be to use a cross-process reference in memory that GC has to take the extra step of looking at two processes per message... I write a lot of higher level code than this and would be prone to overlook these kinds of details, but I want to get better at noticing performance gotchas. The architecture of the compiler and target assembly would have to be key to that.
- bcrosby95 6y ago
  > So the alternative to copying the message would be to use a cross-process reference in memory that GC has to take the extra step of looking at two processes per message At what point do you decide to make a copy? What if you pass a subset of the data to process C, which stores a subset of that data, then later passes it to process D? If you don't copy the data at any point in this series of steps, you need full blown cross-process GC which is counter to their goal.
  - deleted 6y ago
    [deleted]
- dnautics 6y ago
  > So the alternative to copying the message would be to use a cross-process reference in memory that GC has to take the extra step of looking at two processes per message To be frank, erlang already does this with binaries over some size limit (I think 64B)
javajosh 6y ago
>Messages are always copied before being inserted into the queue. As wasteful as this may sound it greatly reduces garbage collection (GC) latency as the GC never has to look beyond a single process. Non-copying implementations have been tried in the past, but they turned out to be a bad fit as low latency is more important than sheer throughput for the kind of soft-realtime systems that Erlang is designed to build. I do so wish there was a reference or link around "tried in the past".
- dnautics 6y ago
  So this isn't entirely true; binaries above a certain size have their own recounting, process independent GC going on in the BEAM; I wonder why the VM doesn't use a similar system for highly mobile data structures (copy to a common refcounted "scratchpad" on first send).
  - toast0 6y ago
    It would seem off heap messages could be a base for this. I've not gone all the way into the weeds on those, but it seems like it could be possible to start with sending a whole message to another process by bumping a refcount and adding a reference to that process's mailbox without needing to make a new copy. If that works, and is useful, you could extend by bumping the refcount, and adding a new type of subreference to a process's mailbox. I don't think you'd want to send something referencing multiple off-heap messages or adding some terms and a reference (although maybe, who knows), because that would be a lot of complexity. And you would also want to be sensitive to subreference memory leaks, like can happen with binaries where a binary is large, but only small subreferences stick around, leading to lots of wasted space (this is extra fun when you put a small subbinary into ets/mnesia and it lives forever (well until you restart beam, but that can be a long time).
    - strmpnk 6y ago
      This is sort of what Pony did with its ORCA based GC. It has some tricky edge cases to optimize in practice but it can be made to work especially well if data is immutable.
deleted 6y ago
[deleted]
choeger 6y ago
Out of curiosity: What happens with messages that are never received? Do they just pile up until the (not-so) receiving process OOMs? How does one debug such a program?
- srijan4 6y ago
  Yes, messages keep piling up and memory usage keeps increasing until the Erlang VM goes out of memory. To debug, there's a max_heap_size parameter which can be configured to log an error message when heap size of any process goes beyond a threshold, or it can even kill the process[0]. Although I don't know if this takes the "off-heap" messages into account. Also, there are lots of libraries which can provide a "top" like view of the running system. [0] - http://erlang.2086793.n4.nabble.com/Max-heap-size-td4716974.html http://erlang.2086793.n4.nabble.com/Max-heap-size-td4716974....
jorangreef 6y ago
Just an aside, but message passing also makes a huge difference if you want to implement a distributed consensus protocol such as Viewstamped Replication or Raft. Compared to typical request/response connection-oriented protocols (e.g. TCP or HTTP), message passing maps 1-to-1 to the distributed consensus domain, where the client can send a request message to the leader and then fully expect to get the response message back from another subsequent leader (after a view change or leader election). I ran into this while implementing Viewstamped Replication in Zig for https://github.com/coilhq/tigerbeetle https://github.com/coilhq/tigerbeetle, where we had a typical TCP request/response protocol to begin with, and then realized that a message bus would make things much easier. It's just really nice to be able to say, send this message to process A or process B (if you can) and not worry about much else beyond timeouts and retries, which are needed for distributed consensus anyway, and straight away it opens up the door for alternative underlying transport protocols such as QUIC or UDT, multicast etc. Message passing is just a really good abstraction to have in place above all this in general.
bullen 6y ago
I think erlangs strength is also it's weakness: structuring everything around messages instead of having complex memory model and concurrency. I always post these quotes until someone comes across that can explain them, so far 2 years later nobody have been able to: "While I'm on the topic of concurrency I should mention my far too brief chat with Doug Lea. He commented that multi-threaded Java these days far outperforms C, due to the memory management and a garbage collector. If I recall correctly he said "only 12 times faster than C means you haven't started optimizing"." - Martin Fowler https://martinfowler.com/bliki/OOPSLA2005.html https://martinfowler.com/bliki/OOPSLA2005.html "Many lock-free structures offer atomic-free read paths, notably concurrent containers in garbage collected languages, such as ConcurrentHashMap in Java. Languages without garbage collection have fewer straightforward options, mostly because safe memory reclamation is a hard problem..." - Travis Downs https://travisdowns.github.io/blog/2020/07/06/concurrency-costs.html https://travisdowns.github.io/blog/2020/07/06/concurrency-co...
- yetihehe 6y ago
  And erlang outperforms multi-threaded java single-handedly. I've made a system in java, which caps at about 6k threads, server starts to slow to a crawl. Similar system in erlang (newer version of server doing essentially the same tasks) is currently also servicing about 6k connections, but cpu utilisation is about 10%. Yeah, we could rewrite that old system to use some async library, but that's not multi threaded, just scheduled (like in erlang).
  - bullen 6y ago
    You need non-blocking IO, if you have more threads than cores you are doing it wrong. You cannot build a MMO server with erlang.
    - yetihehe 6y ago
      Why not? I have such server in plans, but that won't be soon (due to lack of time). If you have only as many threads as cores, that's not very MULTI threading, that's avoiding threads because of performance reasons.
amelius 6y ago
> Messages are always copied before being inserted into the queue. As wasteful as this may sound it greatly reduces garbage collection (GC) latency as the GC never has to look beyond a single process. This means there is no structural sharing, which can be troublesome with huge data structures. (Edit: not entirely true, see comments below)
- srijan4 6y ago
  The only sharing is for large binaries (>64 bytes)[0]. Like all messaging mechanisms, this can be handled by passing a reference or id, and the receiver fetching the actual large data from db/file/source of truth. [0] - http://erlang.2086793.n4.nabble.com/how-message-size-effects-performance-td2112663.html http://erlang.2086793.n4.nabble.com/how-message-size-effects...
  - amelius 6y ago
    > The only sharing is for large binaries Can you also share small objects by reference? (I.e. prevent serialization of a large tree composed of small objects) And refer to those objects through pointers (avoiding an expensive db layer)?
    - srijan4 6y ago
      > Can you also share small objects by reference? No. But, you can use a cheap cache layer instead of expensive db layer - ETS.
      - amelius 6y ago
        Ok, thanks!

151 points by srijan4 6y ago

The big problem nobody talks about with actors and message passing is non-determinism and state. If two otherwise independent processes A and B are sending messages to a single process C, it's non-deterministic which arrives at C first. This can create a race condition. C may respond differently depending on which messages arrives first - A's or B's. This is also effectively an example of shared mutable state - the state of C, which can be mutated whenever a message is received - is shared with A and B because they're communicating with it and their messages work differently based on the current state. Non-determinism, race-conditions, shared mutable state: the absolute opposite of what we want when dealing with concurrency and parallelism.

zimpenfish 6y ago
> The big problem nobody talks about with actors and message passing is non-determinism and state. Seems to be mentioned in the article, with an example: > If more than one process sends signals to a common process, they can arrive in any order even when you “know” that one of the signals was sent first.
- chrisseaton 6y ago
  Right - that's what triggered my comment - but I think it's a bigger footgun than the article does. The problem is this corner case opens up all the fundamental issues I mention. When we include it we've got a big non-deterministic, racey, stateful, problem.
  - jerf 6y ago
    In practice, I don't think it is for real Erlang programs. If you need total order, route everything that needs that order through one process, and you have it. For instance, you can use that to impose total order on messages in a chat room. As long as "one chat room" is small enough for that to be practical even at your largest size, it works. If that doesn't work, don't use Erlang. No sarcasm. The process model is nice but does preclude certain high-performance patterns.
  - uwiger 6y ago
    Experience shows that it really isn't. The fundamental issues of non-deterministic ordering are inherent in the domain that Erlang was designed for, and the VM characteristics pretty closely reflect that. It turns out that people have comfortably written complex and scalable commercial systems in Erlang for decades, and many have noted that for people who understand the problem domain, the Erlang model feels intuitive. The problem of message order non-determinisim is real, but for orchestration logic in scenarios with multiple uncoordinated message sources, it's inescapable. What is important is that the programming environment helps you deal with it, and doesn't introduce additional - "accidental" - complexity. I discussed this topic at QCon 2010, and ran through some demos to illustrate where many commercial projects actually DO go wrong, and why the textbook Erlang model keeps you safe. https://www.infoq.com/presentations/Death-by-Accidental-Complexity/ https://www.infoq.com/presentations/Death-by-Accidental-Comp... The key guarantees that Erlang gives you here are: * Messages from A to B will all arrive (if they arrive) in the order in which they were sent, and you can detect if there is an interruption * A receiving process can decide in which order messages are processed. It turns out that people intuitively understand that if Alice and Bob each send me a message, independently of each other, I cannot know which message reaches me first. This mirrors a fundamental real-world constraint, and in a distributed processing environment, there really isn't much you can do about it. There are other concurrency-related problem domains, some for which the Erlang implementation, at least, is not ideal.
deleted 6y ago
[deleted]
toast0 6y ago
Often, the order of messages doesn't matter that much. When it does matter, there are a couple patterns to consider. a) be sure to give C whole requests, don't ask C for current data, modify it in A and then send it back to C (which is begging for B to send a modification in the mean time). C's mailbox enforces an ordering on requests (all calls will be handled in the order they are received, not in the order they are sent) b) rather than A sending to B and C, and B also sends to C, send only from A to B and from B to C. B sends along A's information. Downside is if B crashes before sending to C, A's information is lost. You could also have A send to C, and C replies to B, which then does work and sends back to C. c) when multiple processes are working on a single thing, try to combine them. A single process will find it hard to race with itself, and will have a clear order of events. I'm in the middle of cleaning up some code that had three processes around one thing (a state process, a reader and a writer), and there were so many weird and racy things because of the separation; putting it into one process means things can't change unexpectedly.
- yellowapple 6y ago
  > be sure to give C whole requests, don't ask C for current data, modify it in A and then send it back to C (which is begging for B to send a modification in the mean time) A simple mitigation against these sorts of race conditions would be for C to maintain a version number alongside its data, then have any update requests send back that version number. If the message's version matches the current, then do the update and change the version number; else, reject the message with a reply directing the sender to reobtain the current data and try again. This way, if both A and B grab data from C and then simultaneously try to update that data in C, you won't lose any data. This is (relevantly to Erlang) exactly how CouchDB works.
  - catlifeonmars 6y ago
    I believe this is called “optimistic locking”
ramy_d 6y ago
Erlang has a bunch of tools to help enforce determinism or at least suss out concurrency issues. For example: you can specify multiple receive statements to process your queued messages in a specific order, there is also a process manager (pman:start()) that allows you to explore concurrency related events, and not to mention Mutex Semaphores as a pattern to mitigate those issues. There doesn't seem to be a real solution to deadlocks. I got the oreilly book in front of me and it's basically saying: be careful, but don't worry. And I don't think erlang has a shared mutable states. In fact a google search for "erlang shared mutable state" has you as the first result.
- chrisseaton 6y ago
  > And I don't think erlang has a shared mutable states An actor has state. It's mutable - each message can modify it. It's shared - two process working with a shared actor share that state. To me, that's shared mutable state. It causes classic race conditions. (I know this is an unpopular opinion, and somewhat deliberately contrary and provocative, but ultimately truthful.)
  - ProfHewitt 6y ago
    For many practical applications, deterministic parallelism is hundreds of times slower than indeterminate computation. For a proof, see the following article: "Epistemology Cyberattacks" https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021
    - deleted 6y ago
      [deleted]
    - jiehong 6y ago
      Is this some badly auto generated text? Reads like some.
      - ProfHewitt 6y ago
        Current auto generators cannot yet deal with such esoteric content. So it must be real ;-)
dragonwriter 6y ago
> The big problem nobody talks about with actors and message passing is non-determinism and state. People talk about that all the time with actors and message passing, since the actor model is largely a tool for structuring the management of those things (not usually for eliminating them, because for many problem domains those are inherent to the domain.)
ProfHewitt 6y ago
Indeterminacy (using arbiters) is crucial to the performance of digital computation. (Arbiters are used in the interconnect of many-core chips.) See the following for an explanation: "Physical Indeterminacy in Digital Computation" https://papers.ssrn.com/abstract=3459566 https://papers.ssrn.com/abstract=3459566
- chrisseaton 6y ago
  You can program a completely deterministic parallel system using a simple fork-join model, can't you? No physical or timing factors interfere with that, can they?
  - j-pb 6y ago
    The guy you just responded to invented the Actor model. I'd guess he knows... Besides, such a fork join model might be theoretically free of timing and coordination in a system with infinite resources (bus widths, no cache coherence, an infinitely fast coordinator e.t.c.) but that's not what silicon looks like. The nice thing about the Actor model is exactly that it immediately exposes you to non-determinism, distributed state, and in Erlangs case, failure. It's what allows Erlang systems to "effortlessly" (you had to put the effort upfront) span many node clusters with arbitrary reliability in the face of failures. Somewhere else you write: > The problem is this corner case opens up all the fundamental issues I mention. When we include it we've got a big non-deterministic, racey, stateful, problem. That's not caused by the Actor model, but by the fundamental laws governing distributed systems. Distributed systems are inherently, non-deterministic, racey and statefull. Two generals dictates that you can't solve these issues, unless you're on a single writer system (which your scatter-gather algorithm is an example of, in which you will always be limited by the throughput of the process that organises your scatter-gather operations / your control plane). In which case, you might as well ignore all forms of concurrency and do one thing at a time, which will be faster anyways.
    - deleted 6y ago
      [deleted]
    - 6y ago
africanboy 6y ago
it's true, but that's a problem every other implementation suffer from. synchronization is a basic requirement in concurrency. in my experience the actor model implemented in Erlang provides simpler solutions to the problem as highlighted in this comment https://news.ycombinator.com/item?id=26535230 https://news.ycombinator.com/item?id=26535230 for example if B sends a message to C in response to a message from A, it could send back a specific response to A that will contact C on its behalf and avoid the non determinism the fact that the actor model provides strong guarantees about messaging order between two actors, makes it easier to reason about it and avoid the pitfalls associated with it it is also a well known problem citing the Pony lang FAQ So for example, if actors X and Y send to actor Z, there is no guarantee what order the messages will be processed by Z except that we can say, all messages sent by X will be processed in the order they were sent, as will all messages sent by Y. However, messages from X and Y can arrive at Z interleaved in any order that maintains the causal ordering of X to Z and Y to Z.
westurner 6y ago
> Luckily, global orders are rarely needed and are easy to impose yourself (outside distributed cases): just let all involved parties synchronize with a common process. When there are multiple agents/actors in a distributed system, and the timestamp resolution is datetime64, and clock synchronization and network latency are variable, and non-centralized resilience is necessary to eliminate single points of failure, global ordering is impractical to impossible because there is no natural unique key with which to impose a [partial] preorder [1][2]: there are key collisions when you try and merge the streams. Just don't cross the streams. [1] https://en.wikipedia.org/wiki/Preorder_(disambiguation) https://en.wikipedia.org/wiki/Preorder_(disambiguation) [2] https://en.wikipedia.org/wiki/Partially_ordered_set https://en.wikipedia.org/wiki/Partially_ordered_set The C in CAP theorem is for Consistency [3][4]. Sequential consistency is elusive because something probably has to block/lock somewhere unless you've optimally distributed the components of the CFG control flow graph. [3] https://en.wikipedia.org/wiki/Consistency_model https://en.wikipedia.org/wiki/Consistency_model [4] https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem FWIU, TLA+ can help find such issues. [5] [5] https://en.wikipedia.org/wiki/TLA%2B https://en.wikipedia.org/wiki/TLA%2B
- codebje 6y ago
  Wouldn't a partial order be possible using logical clocks? Vector clocks probably don't satisfy "practical" but a hybrid logical clock is practical if you can assume clock synchronisation is within some modest delta.
  - toast0 6y ago
    > if you can assume clock synchronisation is within some modest delta. From experience with clocks, you should really be actively testing the delta, and not just assuming it.
    - codebje 6y ago
      The assumption would be the limit you actively test for.
dnautics 6y ago
Yeah but the way you're framing the problem is a bit crazy. If such a race condition is critical, then making A and B "otherwise independent" is a poorly designed architecture (and, yes, novices will do this, which is why there is a big admonition in the Elixir docs: https://hexdocs.pm/elixir/master/GenServer.html#module-when-not-to-use-a-genserver https://hexdocs.pm/elixir/master/GenServer.html#module-when-...). Maybe they should all be branching logic or state machine in the same actor and you shouldn't be coordinating with message passing? If for some reason A and B TRULY need to be asynchronous and independent (let's say they are tracking real-world things), AND order matters, then no amount of language or VM architecture will get you out of building a transactional lock, consensus system, or CRDT to guarantee sane results. That is just how the universe works.
bmitc 6y ago
> The big problem nobody talks about with actors and message passing is non-determinism and state. I have written a lot of actor-based systems, and I’m pretty sure this is heavily talked and thought about. The race condition situation you described is only a problem for people not used to concurrency and actors. It is bad form to have your actor depend on the order of messages it receives if it is intended to receive messages from multiple actors. So the situation you’ve described is simply bad actor programming. Often, a good way to program actors is to have them be finite state machines. Also, your shared mutable state reference does not meet any definition I have ever seen of “mutable”. In actor systems, yes, actors can receive the state of other actors, but that state is a copy. The internal state of an actor is not allowed to be mutated by an external process, typically.
- mrkeen 6y ago
  > your shared mutable state reference does not meet any definition I have ever seen of "mutable" Of course it is! > The internal state of an actor is not allowed to be mutated by an external process Having A tell C to mutate its state instead of A just mutating C's state is just like using a 'private' keyword in another language - insofar as mutation is concerned. Race conditions do not care if you ran: a() { kindlyInformCToIncreaseXWheneverYouGetThisMessage(); } versus a() { c.x++; } It's still a mutation.
  - srijan4 6y ago
    But, the internal state is still changed by the owner process, in the owner process' context. The external process cannot change it's state behind it's back. Effectively, mutations to the internal state are "serialized" by the owner process, so it's easier to handle possible race conditions without using explicit locks/semaphores.
  - hnedeotes 6y ago
    This shows exactly the problem but perhaps not in the context you're thinking of. One of the biggest strengths in processes in Erlang is that they serialise access, this serialisation though isn't simply that they serialise or are written in a way of "run this once". It's more like processes are (or can be used) basically state machines. This pattern is pervasive and you can find it in the OTP library, the most common construct (although there's proper finite state machine OTP abstractions) is the gen_server. The gen_server, is a generic server interface that uses message passing. It can be described as the simplest of agents that has a baked in generic interface. Where your sample falls short is that, when you code the interface for a gen_server I'm (or can, usually will) codify any needed relationship between the state a process is in and what it can do with the "messages" it receives according to the state it is in. This allows me to completely forgo of any concern about how someone will use it without having to explicitly define handling of cases I didn't intend. If I have (pseudo code but completely codifiable): - when msg and msg == "get_status" and state == "receiving" -> reply, function_that_calculates_response(state), new_state = make_new_state(state) - when msg and state == "not_available" -> reply unavailable, new_state = state, continue_to: "recheck_assumptions" - when "recheck_assumptions" and state -> noreply, new_state = check_assumptions(state) - when msg, state -> reply bad_request, new_state = state Now I don't have to worry about any nook, escape hatch or other such in the language, that someone will rewrite the state of this process from another thread, or function call or whatever. Nowhere will a process be able to change the state of this process from outside the process meaning I can clearly define the states it can assume. I also don't need to write overly defensive code, or find out that in some given situation something changed the state outside of what I explicitly coded. In the previous example this means that if two processes (running in different schedulers, nodes, or wtv) both send a msg, the mental model of the receiving gen_server will be a consistent mailbox from which it picks msgs to process one at a time. If one of the msgs would force the gen_server to change its state, and another asks for the status, it won't happen that both of them can have their conditions evaluated at the same time, but the states differing. So if msg_1 changes the state, msg_2 will be interpreted on this new state. It can't happen that msg_1 is being processed, changes the state in some intermediate step, while msg_2 is interpreted in the same exact conditions as msg_1 (unless msg_1 leaves the state as it was). This is not true for some mutable code, you can have two functions from different threads or whatever, call a function on X concurrently, and the evaluations for these calls being done based on the same state, while then fun1 and fun2 operates on the state. Perhaps fun2 assumed that it was allowed because of being in a given state, but while doing its thing that assumed that, the state had been changed by fun1 that was running at the same time. It also means, that this process can do whatever it wants, including spawning new processes and whatever, to do their thing in different contexts but its state can only be mutated by itself. This then forces those things (or me when writing code) to explicitly define their interface and if I want to rely on the result of those things changing the state, I need to explicitly message pass it back, for which I will have the previously defined interfaces. This then when coupled with supervision, links or monitors can make for extremely resilient processes even when they encode complex flows between multiple parts in the presence of possible unknowns. Can you still bork it? Yes, but the area is much smaller and I guess after a while of working with it it's a very simple model that once understood is always the same. Are there areas where this is not the right away to do it and mutable is right? Probably yes, people point out performance issues but I think there's also some overstating about it, in most cases it seems it can be solved, but I can believe there are possible issues there so not a silver bullet. Sorry for the long winded post.
tpetry 6y ago
This behaviour is intended in erlang and it‘s very good. You don‘t start to develop the application with wrong concepts. Your ordering from different producers will work on a single machine, but the second you want to upgrade to a distributed system everything will fail. In erlang you start designing everything with a distributed system in mind.
- deleted 6y ago
  [deleted]
BlackFly 6y ago
Suppose something goes on auction on a website. Two clients on opposite sides of the globe launch bids at the same time. Of course the response depends on which bid arrives at the auction server first. This is exactly what you want when dealing with concurrency and parallelism: one of those two clients will be assigned the bid at that price and the auction will continue. The same thing happens in real life. You cannot solve this problem by using a shared memory model: it isn't inherent to the actor model, it is inherent to the reality of some situations. I have seen some people avoid referring to scenarios like this as race condtions, but in general there are some situations where you generally need to assign a winner (you have a serial actor decide or you use a lock). It could be real (like the auction example) or it could be bad design where a system has been architected to be unnecessarily concurrent and events that are in reality serial are fired off in parallel and the network (or even the thread scheduler or something else) reorders them. Try to avoid creating unnecessary races, learn to identify real races.

JetAlone 6y ago

"Messages are always copied before being inserted into the queue. As wasteful as this may sound it greatly reduces garbage collection (GC) latency as the GC never has to look beyond a single process. Non-copying implementations have been tried in the past, but they turned out to be a bad fit as low latency is more important than sheer throughput for the kind of soft-realtime systems that Erlang is designed to build." So the alternative to copying the message would be to use a cross-process reference in memory that GC has to take the extra step of looking at two processes per message... I write a lot of higher level code than this and would be prone to overlook these kinds of details, but I want to get better at noticing performance gotchas. The architecture of the compiler and target assembly would have to be key to that.

bcrosby95 6y ago
> So the alternative to copying the message would be to use a cross-process reference in memory that GC has to take the extra step of looking at two processes per message At what point do you decide to make a copy? What if you pass a subset of the data to process C, which stores a subset of that data, then later passes it to process D? If you don't copy the data at any point in this series of steps, you need full blown cross-process GC which is counter to their goal.
- deleted 6y ago
  [deleted]
dnautics 6y ago
> So the alternative to copying the message would be to use a cross-process reference in memory that GC has to take the extra step of looking at two processes per message To be frank, erlang already does this with binaries over some size limit (I think 64B)

javajosh 6y ago

>Messages are always copied before being inserted into the queue. As wasteful as this may sound it greatly reduces garbage collection (GC) latency as the GC never has to look beyond a single process. Non-copying implementations have been tried in the past, but they turned out to be a bad fit as low latency is more important than sheer throughput for the kind of soft-realtime systems that Erlang is designed to build. I do so wish there was a reference or link around "tried in the past".

dnautics 6y ago
So this isn't entirely true; binaries above a certain size have their own recounting, process independent GC going on in the BEAM; I wonder why the VM doesn't use a similar system for highly mobile data structures (copy to a common refcounted "scratchpad" on first send).
- toast0 6y ago
  It would seem off heap messages could be a base for this. I've not gone all the way into the weeds on those, but it seems like it could be possible to start with sending a whole message to another process by bumping a refcount and adding a reference to that process's mailbox without needing to make a new copy. If that works, and is useful, you could extend by bumping the refcount, and adding a new type of subreference to a process's mailbox. I don't think you'd want to send something referencing multiple off-heap messages or adding some terms and a reference (although maybe, who knows), because that would be a lot of complexity. And you would also want to be sensitive to subreference memory leaks, like can happen with binaries where a binary is large, but only small subreferences stick around, leading to lots of wasted space (this is extra fun when you put a small subbinary into ets/mnesia and it lives forever (well until you restart beam, but that can be a long time).
  - strmpnk 6y ago
    This is sort of what Pony did with its ORCA based GC. It has some tricky edge cases to optimize in practice but it can be made to work especially well if data is immutable.

deleted 6y ago

[deleted]

choeger 6y ago

Out of curiosity: What happens with messages that are never received? Do they just pile up until the (not-so) receiving process OOMs? How does one debug such a program?

srijan4 6y ago
Yes, messages keep piling up and memory usage keeps increasing until the Erlang VM goes out of memory. To debug, there's a max_heap_size parameter which can be configured to log an error message when heap size of any process goes beyond a threshold, or it can even kill the process[0]. Although I don't know if this takes the "off-heap" messages into account. Also, there are lots of libraries which can provide a "top" like view of the running system. [0] - http://erlang.2086793.n4.nabble.com/Max-heap-size-td4716974.html http://erlang.2086793.n4.nabble.com/Max-heap-size-td4716974....

jorangreef 6y ago

Just an aside, but message passing also makes a huge difference if you want to implement a distributed consensus protocol such as Viewstamped Replication or Raft. Compared to typical request/response connection-oriented protocols (e.g. TCP or HTTP), message passing maps 1-to-1 to the distributed consensus domain, where the client can send a request message to the leader and then fully expect to get the response message back from another subsequent leader (after a view change or leader election). I ran into this while implementing Viewstamped Replication in Zig for https://github.com/coilhq/tigerbeetle https://github.com/coilhq/tigerbeetle, where we had a typical TCP request/response protocol to begin with, and then realized that a message bus would make things much easier. It's just really nice to be able to say, send this message to process A or process B (if you can) and not worry about much else beyond timeouts and retries, which are needed for distributed consensus anyway, and straight away it opens up the door for alternative underlying transport protocols such as QUIC or UDT, multicast etc. Message passing is just a really good abstraction to have in place above all this in general.

bullen 6y ago

I think erlangs strength is also it's weakness: structuring everything around messages instead of having complex memory model and concurrency. I always post these quotes until someone comes across that can explain them, so far 2 years later nobody have been able to: "While I'm on the topic of concurrency I should mention my far too brief chat with Doug Lea. He commented that multi-threaded Java these days far outperforms C, due to the memory management and a garbage collector. If I recall correctly he said "only 12 times faster than C means you haven't started optimizing"." - Martin Fowler https://martinfowler.com/bliki/OOPSLA2005.html https://martinfowler.com/bliki/OOPSLA2005.html "Many lock-free structures offer atomic-free read paths, notably concurrent containers in garbage collected languages, such as ConcurrentHashMap in Java. Languages without garbage collection have fewer straightforward options, mostly because safe memory reclamation is a hard problem..." - Travis Downs https://travisdowns.github.io/blog/2020/07/06/concurrency-costs.html https://travisdowns.github.io/blog/2020/07/06/concurrency-co...

yetihehe 6y ago
And erlang outperforms multi-threaded java single-handedly. I've made a system in java, which caps at about 6k threads, server starts to slow to a crawl. Similar system in erlang (newer version of server doing essentially the same tasks) is currently also servicing about 6k connections, but cpu utilisation is about 10%. Yeah, we could rewrite that old system to use some async library, but that's not multi threaded, just scheduled (like in erlang).
- bullen 6y ago
  You need non-blocking IO, if you have more threads than cores you are doing it wrong. You cannot build a MMO server with erlang.
  - yetihehe 6y ago
    Why not? I have such server in plans, but that won't be soon (due to lack of time). If you have only as many threads as cores, that's not very MULTI threading, that's avoiding threads because of performance reasons.

amelius 6y ago

> Messages are always copied before being inserted into the queue. As wasteful as this may sound it greatly reduces garbage collection (GC) latency as the GC never has to look beyond a single process. This means there is no structural sharing, which can be troublesome with huge data structures. (Edit: not entirely true, see comments below)

srijan4 6y ago
The only sharing is for large binaries (>64 bytes)[0]. Like all messaging mechanisms, this can be handled by passing a reference or id, and the receiver fetching the actual large data from db/file/source of truth. [0] - http://erlang.2086793.n4.nabble.com/how-message-size-effects-performance-td2112663.html http://erlang.2086793.n4.nabble.com/how-message-size-effects...
- amelius 6y ago
  > The only sharing is for large binaries Can you also share small objects by reference? (I.e. prevent serialization of a large tree composed of small objects) And refer to those objects through pointers (avoiding an expensive db layer)?
  - srijan4 6y ago
    > Can you also share small objects by reference? No. But, you can use a cheap cache layer instead of expensive db layer - ETS.
    - amelius 6y ago
      Ok, thanks!