Erlang uses message passing to communicate between processes. How does it handle concurrent incoming messages? What data structure is used?
Asked
Active
Viewed 383 times
2 Answers
2
The process inbox is made of 2 lists.
The main one is a fifo where all the incoming messages are stored, waiting for the process to examine them in the exact order they were received. The second one is a stack to store the messages that won't match any clause in a given receive statement.
When the process executes a receive statement, it will try to "pattern match" the first message against each clause of the receive in the order they are declared until the first match occurs.
if no match is found, the message is removed from the fifo and stacked on the second list, then the process iterates with the next message (note that the process execution may be suspended in the mean time either because the fifo is empty, or because it has reached his "reduction quota")
if a match is found, the message is removed from the fifo, and the stacked messages are restored in the fifo in their original order
note that the pattern matching process includes the copy of any interesting stuff into the process variables for example if {request,write,Value,_} -> ... succeeds, that means that the examined message is a 4 elements tuple, whose first and second elements are respectively the atoms request and write, whose third element is successfully pattern matched against the variable Value: that means that Value is bound to this element if it was previously unbound, or that Value matches the element, and finally the fourth element is discarded. After this operation is completed, there is no mean to retrieve the original message
1
You may get some info out of checking out the erl_message primitive, erl_message.c, and its declaration file, erl_message.h.
You may also find these threads helpful (one, two), although I think your question is more about the data structures in play.
ERTS Structures
The erlang runtime system (erts) allocates a fragmented (linked) heap for the scheduling of message passing (see source). The ErlHeapFragment structure can be found here.
However, each process also has a pretty simple fifo queue structure to which they copy messages from the heap in order to consume them. Underlying the queue is a linked list, and there are mechanisms to bypass the heap and use the process queue directly. See here for more info on that guy.
Finally each process also has a stack (also implemented as a list) where messages that don't have a matching pattern in receive are placed. This acts as a way to store messages that might be important, but that the process has no way of handling (matching) until another, different message is received. This is part of how erlang has such powerful "hot-swapping" mechanisms.
Concurrent Message Passing Semantics
At a high level, the erts receives a message and places it in the heap (unless explicitly told not to), and each process is responsible for selecting messages to copy into its own process queue. From what I have read, the messages currently in the queue will be processed before copying from the heap again, but there is likely more nuance.
