Message passing algorithms books/resources

Hey all!

I've been trying to use message passing (std's mpsc but also crossbeam's mpmc channels) exclusively as a way to handle concurrency in my code. I'm wondering if anyone has found a good resource/book on message-passing algorithm design. For the problems I'm thinking about I can come up with shared state solutions pretty easily, but I'm sure there are elegant, correct and performant message-passing algorithms too, I just don't know them.

To give my latest example: I have a large number of background tasks that need to be executed. I'd like to use multiple threads for it. Each task may generate additional tasks, but at some point they finish. The application's main thread needs to know when the work has finished.

I have a solution (see below), I just don't find it very elegant and I wanted to read some of the state-of-the-art in this field. My Googling isn't turning out too much: there's the occasional chapter in various books, but it mostly explains the concept of message passing and gives some trivial examples.

The best idea I have so far is to use an mpmc channel as a queue of sorts. A thread that receives a task message goes and executes it. If needed it sends more messages of tasks that need to be done. But termination is the hard part: how does the main thread now the job is done, and how do the worker threads know to stop waiting? You can't just rely on the channel becoming empty: there could be tasks in flight that can add more tasks. It's really easy to solve this by using an additional AtomicUsize to count tasks, but that feels like cheating, it's still shared memory. I could use a second channel consumed only by the main thread where each worker thread posts a message when they create and solve tasks. The main thread then basically counts up and down and when it reaches zero, the work is done. It can then send another message to the worker threads to have them shut down. But it doesn't feel like the world's most elegant solution.

P.S. I know about rayon and tokio. For various reasons neither is a very good fit for my code and I'd like to avoid them. Besides, I assume they use shared state internally, so that seems like cheating.

Regarding termination and the idea to use atomic usize: I suppose having one “management” thread that knows how many tasks there should be should be enough. The worker threads send messages regarding their progress (e. g. for each completed tasks, or for batches of tasks if they're really numerous) to the management thread; once all tasks are done, the management threads sends messages to the workers to shut them down. Crossbeam has select to listen to multiple channels at once if you want a separate shutdown signaling channel. Following this general approach of counting completed tasks, one should also make sure to handle correctly the case that a worker thread might panic, at least if a panic is not entirely unrealistic. Otherwise, some tasks might not become complete and the desired number never reached.

Or, in easier cases, the place where the tasks come from could know when they're done and Senders can be dropped as soon as they won't be used anymore. Once all copies of a Sender of a channel are dropped and the channel is empty, the Receiver will get a RecvError indicating the channel is not only empty but no new messages can ever come in the future; this can be immensely useful for properly shutting down threads. (The other end being dropped is the only reason why a channel operation (send/receive) can fail; you'd either consider/use the Err(...) case as an ordinary shutdown signal; or, if the program logic prescribes that the other end should never terminate first, you can .unwrap() on your channel operation to "propagate the panic" (assuming a panic was why the other end was unexpectedly shut down)).

1 Like

Right, that's the approach I was going for, but the problem seems generic enough, so it got me thinking: is there something better? Is this kind of management component/thread a common pattern in message-passing design? Isn't it a bit wasteful (this management thread is just incrementing and decrementing an int, basically)? It feels like writing shared-state code, but with messages. You know how you see a, let's say, Java programmer doing something in Rust and their Rust looks like Java. That's how this solution feels like to me :stuck_out_tongue:

And then what are some other typical patterns/algorithms you use for message-passing concurrency?

That's why I was asking if someone's read a good book or blog or something on it. I am going to dig a little into Erlang -- I know Erlang is quite big on message-passing, so maybe they have some good docs on it. But I figured I'd ask around here as well :slight_smile:

I had Erlang in mind here actually when trying to answer the question, I had a few lectures on its principles in a course multiple years ago, I remember that it has a hierarchical structure of ownership between the "threads", the owner would be responsible to handle when the child fails with an error. I don't remember too many details, but a hierarchical structure would, in my mind, mean that a management thread responsible for shutting things down when work is done, seems reasonable.

Erlang seemed pretty fun to me at the time, so looking into it a little bit should probably be interesting and worthwhile.

Also note that Erlang has a form of green threads, so you can fairly cheaply spawn many things; the closest thing in Rust is async, so Tokio is a reasonable option with message passing too IMO. I mean, it has channels like a mpsc, too; there are of course caveats, one should avoid blocking the run time with blocking or (longer-running) CPU-intensive operations, how straightforward this is, and how much benefit async gives you in the first place probably depends on the kind of problem / job that your system solves.


Regarding "cheating" or the prospect of creating a whole task that doesn't do much more than an atomic usize value: Rust makes safe shared-memory concurrency easy, so in cases where it's appropriate, one does not necessarily have to try too extremely hard to avoid it. Of course, once you have a dedicated "manegement" task for example, maybe you find things it can do that a atomic usize can't provide after all. But if not, I don't think using an atomic usize between your message passing will hurt. Regarding the concern that a system like reyon or Tokio "uses shared state internally", well... (intra-process) channels (like std's mpsc) use shared state internally, too, so that can't be a valid argument against them in the first place.


On an unrelated note...

One fun pattern that I think I remember from the examples I've seen in Erlang.. maybe(?).. is that messages sent through some channel can definitely contain (senders or receivers) of other channels. So you can send to some thread a request together with some "return envelope" to send the answer in so it correctly reaches the "address" of the sender.