EEP 76: Priority Messages

Erlang/OTP Proposals Proposals: RFC
21

No, sorry, I think I wasn’t clear. I don’t want to suggest anything like multiple message queues.

My main point is, that in Erlang you can already fetch messages from your message queue out of order, using selective receive. Semantically, this language feature is enough to solve all the problems EEP 76 lists: first you do a selective receive that matches on the messages that need priority handling with a 0 timeout, and if you find none in the message queue, you pick the next (ordinary) message from the head of the queue.

The problem EEP 76 tries to solve is not that the language doesn’t have a way to handle priority messages out of order, but that their are performance issues with the existing solution when the message queue is long. EEP 76 wants to solve the performance issue by introducing new semantics (inserting priority messages before existing non-priority messages in the queue).

My suggestion is to change nothing about the semantics of message queues, but solve the performance problem. And I tried to say that we can speed up selective receives the same way we can speed up slow SELECT-s on a large DB table: by indexing the data!

Most of my previous post was about how we could describe indices based on message patterns using existing language features (such as match specifications and the process_flag/2 API), but those are just technical details. The main idea is to leave message sending/receiving semantics unchanged, and add indices to the message queue to speed up selective receives.

The big benefit is that the indices should be configured by the process that will do the selective receives, so you don’t have to modify both the sender and the receiver of the messages to use priority messages instead of regular ones when needed. All the code related to priority-handling of messages (the call to set up message queue indexing and the selective receive statement(s)) would likely stay close to each other, in the same module.

2 Likes
22

I’m not to fond of allowing unrestricted priority messaging due to concerns like the one @rvirding had.

@Maria-12648430 suggested to extend the priority_marked_message flag with aliases. I’m leaning towards removing the priority option of erlang:send/3 and instead only use aliases for passing priority messages, so that passing a message using a priority marked alias would imply it being a priority message. This way the receiver opt-in by creating a priority alias which it can pass to processes that are allowed to pass it priority messages. This also allows for processes that have access to the priority alias to share it with other processes. The EEP has not been updated with this yet, though.

I guess that this may also cover your completeness concerns.

2 Likes
23

This would be very expensive, compared to what the EEP propose, since these match-specs would need to be applied on all messages being received prior to being moved into the message queue. Some selective receives could perhaps to some extent be optimized by having knowledge about the match specifications, but it would at least be very problematic with the very common “match first message in the message queue” scenario (e.g. all gen_servers).

The Priority Messages in Transit section of EEP-76 gives a short description on how ordinary messages are handled (already today):

Ordinary messages are special since they are very common and the only action taken upon reception of an ordinary message is to add it to the end of the message queue. Due to this, the signal queue for incoming signals is arranged as a skip list where each non-ordinary message signal points to the next non-ordinary message signal. This way we can move a whole batch of ordinary messages into the message queue at once.

For example, if you today have 1000 ordinary messages in sequence in the internal signal queue, these are moved into the message queue with just a few pointer assignments. Having to apply match specifications on every message would significantly increase the cost of receiving messages.

Looking at the Long Message Queue Notification scenario, the receiver is typically already having issues keeping up with the amount of messages passed to it. It wont be helped by having to do a lot of extra work by applying match specifications on every message.

1 Like
24

You can also build this if you wanted to:

start() ->
   gen_server:start_link(?MODULE, [], []).

call(Pid, Msg) ->
   gen_server:call(Pid, Msg).

prio_call(Pid, Msg) ->
  {_, Alias} = erpc:call(node(Pid), erlang, process_info, [Pid, {dictionary, prio_alias}]),
  gen_server:call(Pid, Msg).

init([]) ->
  put(prio_alias, alias([priority])),
  {ok, nostate}.

Essentially allowing all processes to send priority calls, but with a bit of extra overhead :slight_smile:

2 Likes
25

Yet you did :slight_smile: “Patterns for indexing the message queue” is essentially that - every “pattern” is a separate message queue, and the message can be sent to multiple queues at once. Receives chooses the order in which to scan these queues. When no order is specified, it’s natural order of messages arrival.

With that, right after OTP 28 release, I’m sure to see some library on hex.pm that abuses aliases to implement priority_send function. Honestly, I’d rather see that in the BEAM…

26

Yes, another more efficient way would be to store the priority alias in ETS or persistent term. I don’t see a problem with that, though, since you still need to opt-in for it by creating the priority alias and sharing it.

Perhaps one should even make this scenario even easier by keeping the priority option of send/3 in combination with a process_flag({priority_marked_message, all}, true) flag, so the receiver can opt-in for priority messages from all processes that way. I, however, lean towards only using the priority alias since it to me feels a bit cleaner, but…

27

Perhaps I misunderstand, but I don’t see why that should be the case. Please elaborate.

28

Purely for familiarity/convenience/simplicity. Most likely, implemented as storing priority alias in the ETS table, and doing send/3 to a priority alias at will. Although I do like the elegance of priority alias, it is is less easily discoverable compared to send/3 function (or maybe I’m overthinking this0.

29

I see the analogy, but I think there are important differences between multiple message queues and a single message queue with indices for quickly finding messages matching certain patterns. For example:

  • The sender only sends one message, it doesn’t know it would do a send to multiple message queues.
  • When the receiver consumes a message, it’s removed from all the indices. With multiple message queues consuming a message from one queue shouldn’t consume a copy of the message from other queues.
30

Yes, it would be more expensive than what the EEP proposed, but I don’t think by much. And most importantly, the matching could be done by the sender process, not the receiver:

  1. Get the indices of the receiver (placing a shared read lock on the indices of the process)
  2. Run the matches and determine which indices to insert the message to
  3. Get the write lock on the receiver’s message queue
  4. With a few pointer operations add the message to the message queue (like today) plus all the indices
  5. Release locks

The sender already has a lot of work to do, like copying the entire message to the receiver’s heap. Running a match spec on top of that doesn’t seem to be unmanageable. Of course you could abuse this feature and add 1000 different indices to a process that look 100 levels deep into nested data structures, and that would be slow, but even that wouldn’t be the worst foot gun you can come up with with a little creativity, I bet.

31

Match specs can’t yield and are very awkward to work with. I’m loath to introduce anything new that uses them.

Furthermore, the sender cannot do anything with the receiver’s message queue, all it can do is append signals to the receiver’s signal queue where anything like indexes would cause a giant mess. I cannot see a way to make this work even if match specs weren’t their own can of worms, but I’ll defer to @rickard, he knows these parts better than I do.

3 Likes
32

I like the priority alias solution just from the perspective that I think long-term explicit mailboxes (and proper MPMC queues) would be a wonderful thing to have. Semantically, priority aliases seem like a more generic solution. They are conceptually very similar to a separate, explicit priority mailbox - extending the system with more mailbox options in the future, will be a much smaller semantic change, compared to what is currently in the proposal – very focused solely around the priority message problem.

3 Likes
33

For what it’s worth I’m also partial to having this work exclusively through aliases and the like. process_flag({priority_marked_message, all}, true) feels hacky, and in a sense so does the priority_exit_message / priority_monitor_message stuff too, I’d rather have them only set upon creation.

3 Likes
34

It would be nice to completely avoid the process flags. The monitor messages already (in the EEP) got the priority option for the monitor/3 BIF. Adding a link/2 BIF which also could take a priority option would solve the exit message due to a broken link. It should, of course, only effect the priority of the exit message for the process that passed the option. Exit messages due to exit/2 BIF calls could be solved by allowing aliases as well as pids (and ports) as first argument.

1 Like
35

In most cases it might be sufficient to just treat messages sent via an alias (any alias) as low-priority, and ones sent directly to the pid as high-priority. Maybe introduce a single process flag to enable this behavior specifically.

I may be mistaken, but this should cover most cases related to gen_server/supervisor interaction: all gen calls are sent via an alias already, creation of an alias for the info’s and such can be left to the user.

36

The signal order is guaranteed between entities (processes, ports), not their identity (pid, registered name, alias …), and we cannot break that without user consent. We can’t blindly change it even for gen behaviors.

37

Sorry, I am still of the opinion that allowing the sending process to explicitly find out how to send priority messages and send is the starting down the slopping path to hell. The messages I send from my processes are important and will be priority messages.

2 Likes
38

The receiving process must consent to it (and with aliases, explicitly provide a priority alias). A sender cannot unilaterally send priority messages.

39

I’ll start by saying I don’t think I am not the target audience of this proposal, so I’m likely to be missing context. So if this is all nonsensical, please ignore it.

With that said, I have a feeling that this becomes a contagious aspect of message handling that doesn’t solve the intended use in a desirable way.

Considering the long message queue priority message, for example, it seems necessary for the monitor and the process being monitored to accept priority messages, as the monitor must accept priority messages to then itself send priority messages to the monitored process. With that, it can continue ad nauseam - the monitor itself may have a large message queue that another monitor must handle in a prioritized way, correct?

This seems like it can also be an issue for more involved libraries, I believe. If a dependency accepts priority messages, I don’t necessarily know how my own messages (or others) will arrive. This leads to a situation where sending the order or possibly timestamps is necessary, so that a timestamped priority message can handle messages received previously - otherwise, how can you keep track of what has happened or not? This is essentially what the proposal aims to solve, but I don’t think it does - I think it kicks the can down the road, but there must be a terminating monitor process that can still fail due to not being able to accept messages quickly enough.

I’m very willing to accept that I just don’t comprehend the expected use case, and these aren’t problems. I just didn’t really see any discussion of these specific aspects, and they’ve been bugging me. Maybe it’d be prudent of the proposal to expose a practical example where this proposal solves a problem better than alternatives. Or, I didn’t properly understand the proposal and these are sufficiently considered.

I’d also like to say that a more efficient way to process messages while maintaining existing guarantees in general seems like a reasonable exploratory option, which is what dszoboszlay has brought up, as far as I understand. That specific alternative seems like it may not be appropriate, but it seems more ideal from a conceptual point of view, or at least worthy of exploring.

One idea is to (somehow) have essentially the opposite of how the selective receive optimization works - when a priority message is received, everything before it must be more efficient to identify. I’m not sure how/if that could work. I will say that a sudden cost to deal with that during runtime so that a process can still possibly handle previously received messages seems like a good goal, although this is a general problem with no absolute solution.

But, again, I am almost certainly not the targeted audience for this. I just think I’d be remiss to share my thoughts here if I’m understanding the potential implications correctly.

40

Process generally speaking already have to consent to the messages they receive by pattern matching on them. I believe part of the push back is that a process does not care who sent a message, but rather what the message is, and priority messages flip this inside out. In order to understand if something is a priority message or not, I have to look at the processes involved, and that’s runtime behaviour, which is harder to verify.

I also worry that relying on runtime behaviour, such as aliasing and distribution of said aliases, to control the priority messages may complicate correctness analysis in the future, or even general understanding of the code. If I am looking at a gen_server, which of the messages received can be sent by someone as a priority and which ones cannot? I’d generally strive to make it clearer both in the sender and the receiver that a given message is a priority.

Perhaps we should move the “burden of proof” of a priority message to the message itself. In the simplest option, we could designate that all messages tagged as 'PRIORITY' will be a priority first. I am not arguing this is a good idea as a whole but it has two clear benefits.

First, it makes it clear in the caller that it is a priority message:

Pid ! {'PRIORITY', do_some_work}

But most importantly, it is clear in the receiver that the message is a priority too:

receive
  {'PRIORITY', do_some_work} ->
end

This means that no one can race ahead and say “all my messages are important”, the receiver has full control over what messages matter, not who.

Of course, marking an atom as special comes with its downsides, so a variation of the above is to require the receiver to opt-in into priority messages:

process_flag(priority_messages_tag, 'FOCUS')

And now we allow any process to send a priority message, using the priority flag:

send(Pid, do_some_work, [priority])

With the difference that those messages will now be automatically wrapped in the tag of choice, in this case, the FOCUS tuple:

receive
  {'FOCUS', do_some_work} -> ...
end

Overall, the biggest benefit is that it is clear in the receiver which messages can be a priority, and the receiver focuses on the what, not on the who.

One potential downside is that the message we receive is not the message sent but that’s somewhat similar to how gen:call and gen:cast tag our messages behind the scenes (except there the tag happens in the caller, not the receiver).

Speaking of gen, they could also do the hard work of setting it all up, if you want to. When you start a gen_server, it sets priority_messages_tag to $gen_priority and introduce a new gen:send_priority function. Once a priority message is received, it is unwrapped and dispatched to the handle_priority/2 callback, so the user never has to worry about the underlying tagging. This also means I can immediately look at a gen_server code and see the patterns and messages that may be received out of order.

2 Likes