Software related stuff
Making and performing electronic music? Check out my AudioMulch software.
Software related stuff
When two parties communicate, what are the possible patterns of message exchange?
Here’s what I’ve come up with so far:
(Updated June 22, 2013 with causality arrows, failure modes, sequences and reordering, streams, non-deterministic communication.)
Also known as: procedure call, one-way, unidirectional, post, fire and forget, In-Only, Out-Only, request (R), trigger, event, notification, command, producer-consumer.
At this level “sending a message” is the ultimate primitive (although it decomposes into: prepare, post, transport, deliver, receive).
Also known as: unreliable transport.
A message may fail to be delivered, or the receiver may fail to process it (either intentionally or unintentionally). Sometimes message transport and processing is guaranteed to be reliable and these failure modes don’t arise.
Order of arrival may or may not be guaranteed.
Infinite stream:
Finite stream:
Also known as: Rx IObserver protocol.
Also known as: function call, round-trip, request/response (RR), In-Out, Out-In, call-response, request-result, remote procedure call, polling, solicit-response, query-response.
The reply may provide useful information, or simply acknowledge receipt of the request. The reply might be optional (“In Optional-Out”). Spector (1982) also considers the three message exchange: request/response/acknowledge-response (RRA) . This may not be necessary when message transport is reliable.
A single request results in a number of reply messages.
Also known as: progress callback.
Each reply reflects a phase of a progressive process.
Also known as: observer, periodic timer, streaming updates, event driven, Hollywood principle.
Note that this is not the same as the multi-point publish-subscribe distribution pattern.
The final acknowledgement is required for the subscriber to be sure that it won’t receive any further notifications.
An implicit subscription variant exists where notifications are sent without the client subscribing (like spam). Maybe that’s called Advertising.
Normal case:
Canceled case:
Also known as: one-shot timer, delay, asynchronous completion notification, future, cancelable-future, callback.
If both parties simultaneously send a message to the other there can’t be any guarantee about the order of arrival at each site. For example, a cancellation message could be sent while a notification is already in-flight, as shown below.
Do you know other patterns? Let us know in the comments.
I’m musing about message exchange patterns. Specifically, those relevant to reliable asynchronous message exchange between two threads in a concurrent shared memory system. I wrote this in an attempt to abstract the message exchange aspect of this post. I’ve focused here on message exchange events, ignoring the details of the items being exchanged. When you also consider the items being exchanged, higher-level patterns emerge (consider juggling patterns for example).
There are many areas of computing that study or use message exchange. They include: protocol design, real-time systems, distributed computing, SOAP MEP, MPI, bus communication protocols, and process calculi. I am not an expert in these fields but I am interested in what they can teach me about message exchange. There are some links to related resources at the end.
I have assumed that the two parties outlive the message exchange.
I have assumed that the two parties know how to address messages to each other — although often it is enough that the requestor know the address of the respondent, since the requestor can provide a return address to the respondent as part of the request.
Request-Reply, Request-Multi-reply and/or Send sequences can be concatenated to form longer back-and-forth conversations. Certain transactions such as two and three-phase commit require multiple request-reply pairs.
The relationship between endpoints may be symmetric: either party may be the initiator in the above exchanges; or asymmetric (as in master-slave, client-server relationships etc.).
WCF has a related concept called Service Contracts. WCF defines three types: Request-Reply, One-Way and Duplex.
Does the receiver know the identity of the sender? Does the message provide this information?
A reply is only possible if the receiver knows the sender’s identity. Sender could provide a return address, or receiver may already know the address. Are sender and receiver knowing participants in a fixed (or dynamic) topology? Does receiver retain or store sender’s identity? When does receiver need to do this? (Subscriptions are one case.)
Message bus architectures distribute events to subscribers without the sender knowing the identity of the receiver. Anonymizing servers provide a route between requestor and respondent without revealing the identity of the requestor to the respondent.
Some writers (eg. Spector 1982) are concerned with efficient and minimal primitives for message transport. SOAP Message Exchange Patterns are similarly concerned with mechanism.
You can also consider the purpose or role of a message. For example, a unidirectional message may be a command to perform an action, or it may be a notification that something has happened. Notifications can be further subdivided into those provided for informational purposes (“last lap of the race”) and those that require action (“evacuate now”).
This post from i8c on Basic Message Exchange Patterns makes an argument for considering more expressive patterns that capture the abstract purpose of a message exchange. It lists 10 communication patterns from SAP, broken into two layers: service communication patterns (query/response, request/confirmation, information, notification) and transaction communication patterns (information, notification, query, response, request, confirmation).
This article on Messaging Patterns in Service-Oriented Architecture also presents “higher level” patterns. For example, when considering unidirectional messages it distinguishes between Command messages, Event messages (notifications) and Document messages (information transfer).
Consider the difference between a command (sent with intent) and an event/notification (interpreted by the receiver).
Also consider command-query separation (and here).
Some message passing systems are concerned with managing the flow of data between processors in a computation (eg. HPC systems based on MPI), whereas others are concerned with reacting to external events or processing transactions (eg. operating system kernels, interactive systems).
By focusing on message exchange I have sidestepped the perspective of stateful protocols. Stateful protocols are (usually?) modeled as communicating state machines. Messages drive state transitions and the current state determines which messages are legal. (Searching for “communicating state machines” is a good place to start reading about this.)
I am interested in applying these patterns to messages passed between communicating computer programs, but the patterns appear in the real world too. Real-world examples include: sending a postcard, an exchange of letters in a legal or bureaucratic process, patterns of business communication, types of business transactions, subscribing to a periodical, marketing email workflows, customer service processes, and so on.
Please let me know in the comments if you can think of other patterns, book recommendations, good links or a more abstract (domain-neutral) treatment of this material.
I tried the following searches. Can you suggest other keywords or terms I have overlooked?
communication patterns | two party communication patterns | service communication patterns | transaction communication patterns | message passing theory | message exchange | message exchange theory | packet exchange theory | message exchange protocols | two party message exchange protocols | message communication theory | event driven patterns | event interaction ontology | event exchange patterns
Here are the suggestions for additional message exchange patterns that I’ve received so far (updated January 9, 2013):
Alex McLean @yaxu tweets:
how about scissors-paper-stone voting?
Me: good one. how to draw the picture? +not sure of utility since it is either biased (w/ defaults on ties) or non-wait-free (w/ retries)
on further thought it’s just a request-reply unless you have shared memory, in which case it’s not a message exchange.
reqest/reply: A proposes game along with “sealed” vote, B replies with it’s vote, then opens the seal. B must be honest.The replies should be simultaneous though / or be received/processed after they’ve all been sent.
There may be similar constraints around time sync protocols.. E.g. data not in the message but in time between send and replyMe: Indeed time sync protocols are something to consider. As for rock-paper-scissors and timing: www.youtube.com/watch?v=3nxjjztQKtY …
Yeah that’s related to Thor’s diplomatic reading between the lines too.ok how about DNA message that creates a third party?
thor magnusson @thormagnusson tweets:
Also: communication based on not willing to communicate: ignoring messages & breaking protocols. (Eg. Middle east & N-irland)
Also, Austin’s book “How to Do Things with Words” on speech acts, might be an interesting read. (BTW good #openresearch!)
Damian Stewart @damian0815 tweets:
Telephone pictionary. It’s just unreliable Send, but after several transmissions the unreliability becomes the message.
My Interaction Diagrams board on pinterest.
This is getting a bit lateral, but it might be useful…
Thanks for reading!
This post introduces some basic asynchronous message passing patterns that I’ve found useful while implementing real-time audio software. The patterns apply to in-process shared memory message passing. For the most part this post is intentionally abstract. I won’t talk too much about concrete implementations. I do assume that the implementation language is something like C/C++ and that the message queues are implemented using lock-free ring buffers or similar. For a motivation for this style of programming see my earlier post.
This post isn’t the whole story. Please keep in mind that there are various ways to combine the patterns, and you can layer additional schemes on top of them.
Meta
I wanted to enumerate these basic patterns to give me some clarity about this approach to writing concurrent software. While writing this post I started to look for a mathematical formalism that could capture the semantics of this kind of asynchronous message exchange. I looked at process algebras such as the actor model and pi-calculus but they didn’t seem to model asynchronous message exchange, distributed state and atomic state transitions the way I have done it here. To me the approach presented here seems similar to what you might use to model bureaucratic processes involving asynchronous exchange of paper forms and letters. If you know of an existing formalism that might be used to model these patterns please let me know in the comments, I’d love to hear about it. Thanks!
This post focuses on patterns of asynchronous message exchange between a pair of execution contexts.
I use the term “execution context” instead of “thread” because I’m thinking not only of threads but also of interrupt handlers, signal handlers, timer callbacks, and audio callbacks. An execution context might also be the methods of an object that only operates in one thread at a time, but may migrate between threads during the course of program execution.
Some execution contexts impose certain requirements, such as not blocking (see my earlier post for a discussion of what not to do in audio callbacks).
I assume that the contexts share the same address space, so it is possible to pass pointers to objects between contexts.
I assume that processing a message is atomic and non-re-entrant with respect to the receiving execution context.
When I talk about asynchronous message passing I have in mind an implementation where messages are communicated between threads using queues. The sender and receiver operate asynchronously. The sender doesn’t usually block or wait when sending a message. The receiver chooses when to collect and interpret messages. The queues are light-weight data structures often implemented using lock-free ring buffers. Writing to and reading from a queue are non-blocking operations. The diagram below illustrates the scheme:
In all of the diagrams in this post the left hand side is one context, the right hand side is another context (sometimes called the sender and receiver, or source and target). The half-headed arrow indicates that a message is passed asynchronously in the direction of the arrow by writing a message into the queue from one context and reading the message from the queue in the other context at some later time.
From the perspective of each of the two contexts, code for the above diagram might look something like this:
// execution context A:
{
// post a message:
q.write( m );
}
// ... some time later
// execution context B:
{
// receive and interpret pending messages
while( !q.empty() ){ // in this case we don’t block if the queue is empty
Message m = q.read();
interpret_message( m );
}
... continue other processing
}
I’ve shown messages being passed by value (i.e. copied into a ring buffer). For small messages and single-reader single-writer queues this usually works out well. I mention some other variations later.
To send a message in the opposite direction (from context B to context A) a second queue is needed:
For the rest of this post I’m not going to explicitly notate the contexts and queues: when you see a half-headed arrow it means that the message is being passed asynchronously from one context to another via a non-blocking queue.
There are different ways to connect between the various execution contexts and objects of a program with message queues. Some options that can be used in combination are:
A few concrete use cases are:
There are a number implementation details that I won’t go in to detail about here, including: message implementation strategies, queue implementation, and delivery mechanisms. In the future maybe I’ll write about these in more detail. For now I’ll give a brief sketch:
A message queue transports messages from one execution context to another. A message is a bundle of parameters along with some kind of selector that specifies how the message should be interpreted or executed. In principle there might only be one type of message, in which case only the parameters need to be enqueued. However, a message queue often transports a heterogeneous set of messages, thus usually some kind of selector is needed. For example, something like the following struct, with an enumeration used to indicate the message type (this is similar to a Win32 MSG structure):
enum MessageCommandCode { DO_ACTION_1, DO_ACTION_2, DO_ACTION_3};
struct Message{
enum MessageCommandCode commandCode; // receiver interprets the command code
int messageData1;
bool messageData2;
}
Or a function pointer that is executed when the message is interpreted (this is the way SuperCollider does it for example, see my article about SuperCollider internals for more info):
struct Message{
CommandFunctionPtr commandFunc; // receiver calls the commandFunction passing the message and context-specific state
int messageData1;
bool messageData2;
}
You could do something more elaborate with C++11 lambdas, functors etc. But keep in mind that in a lock-free scenario you want to keep things simple and avoid overheads or allocations when sending messages.
An important thing to notice is that an enumerated command code can be interpreted in multiple ways (for example, by different states in a state machine) where as a function pointer can only be executed in one way (the latter case is more like code blocks in Apple’s Grand Central Dispatch). There are pros and cons of each approach.
For efficiency and to avoid blocking I recommend that the message is moved in to the queue when sending, and moved out of the queue when receiving — data is transferred by value. An optimization is to initialize/construct the message in-place in the queue buffer, rather than copying it there. Similarly, messages can be interpreted/executed directly from queue storage. The queue may support variable-length messages.
If you want your message data to be more expressive you could use a union or object with different sub-types for each message type.
Message could be implemented as polymorphic Command objects (cf. Command Design Pattern) although allocating and passing polymorphic objects in queues might get complicated. Depending on the number of commands involved, introducing polymorphic messages using virtual functions might just be overkill.
Messages might be timestamped and stored in a priority queue in the target context for future execution. Or messages might represent prioritized work (such as disk i/o) to be performed by the target context in priority order.
Ultimately there are many choices here. There are trade-offs between simplicity of implementation, ease of extension and complexity and readability of both the client code and the message passing infrastructure code.
See also: Command Pattern, Command queue, Message queue, message/command implementation in SuperCollider.
This post focuses on situations where there is only ever a single-reader and single-writer to any queue. Partly this is because lock-free single-reader single-writer queues are relatively simple and efficient, and partly because they’re often all you need. That said, it is sometimes desirable or necessary to introduce multiple reader and/or multiple writer mechanisms: for example when a server thread has multiple clients sending it requests, or a single queue is used to distribute work to multiple worker threads. These cases can be implemented by using a lock at one end of a single-reader single-writer queue, or by using node-based lock-free queues such as the one by Michael and Scott.
The patterns in this post do not require or imply synchronous rendezvous or blocking/waiting when sending or receiving messages. A context might choose to block waiting for messages to arrive, or just as likely, it could poll the queue for new messages (without blocking) at certain synchronization points. Alternatively, some other mechanism might be used to ensure that the messages get processed. Some possible mechanisms are:
Periodic polling is often criticized, and for good reason. Please keep in mind that in the cases above that employ polling, there is already a periodic task that is running for other reasons. For example to generate audio or update the GUI.
Now, on to the patterns…
One simple use for a command queue is to send messages that changes (mutates) some context-local state in the receiver. In the example below, a message is sent to change the colour of node x to red:
Note that the message is asynchronous. There is no locking involved because the data structure x is local to the right hand context. The x.setColor(red) code is executed in the right hand context. For comparison, the equivalent code in a lock based system might look like this:
// alternative implementation using locks
Node& x;
Mutex m; // protects x
// ... in context A:
m.lock();
x.setColor(red);
m.unlock();
// ... in context B:
m.lock();
... all operations on the structure and x must be protected by the mutex...
m.unlock();
One way to think about it is that in a lock-based system, the data comes to the code (context A gets access to object x), whereas in the message passing case the function call and parameters are sent to the data structure x in the receiving context (the function executes on context B). If context A and B are running on separate CPUs you can imagine different cache transfer patterns if x is accessed from context A, compared to passing a message (containing a selector, a reference to x, and the colour red) to context B where x is already in the CPU’s cache.
In principle you could implement an asynchronous state request (”get”) message to asynchronously retrieve a state. This is a “pull” model:
More likely you’d use some form of asynchronous Observer pattern where changes to x in the right hand context trigger change notification messages to be sent to the left hand context. This is a “push” model:
In the classical Observer pattern the receiver explicitly attaches/subscribes and detaches/unsubscribes from receiving notifications. For state that is constantly in flux (such as audio levels for VU meters) you might always post periodic notifications rather than requiring explicit subscription.
Often, contexts operate in lock step, in the sense that a client knows (or categorically assumes) the state of the remote context. In this situation there is no need to explicitly request server state.
If there is a master/slave relationship between contexts/states the master can keep a local copy of the slave state — when the master needs to know the state of a slave it can synchronously query the local copy rather than sending an asynchronous message to the slave. Such mechanisms are akin to using a thread-local proxy cache with write-through semantics.
We assume shared memory, so transferring objects from one context to another requires only that an object pointer be passed in the message.
The generalized object transfer patterns below (Link, Unlink and Swap) deal only with transferring the visibility/availability of objects into or out of a context. They don’t say anything about the semantics of the transfer. For example they say nothing about whether the source context still references, manages, or owns the object after it has been transferred. More on that in a minute. First the patterns:
Move an object from source to target. Install in target data structure.
Remove an object from a target data structure and return to source.
Replace an object in the target context with a new object. Return the old one.
A new object is sent and installed in the receiver and the old object is returned. This mechanism can be used to implement atomic state update in O(1) time, even when the object is large or complex (such as a whole signal flow graph). It is related to using a double buffer or pointer-flip to quickly switch states.
It is often useful to overlay additional semantics on these object transfer operations. Potential semantics for object transfer include:
Semantics that enforce immutability, single-context access or a single-writer semantics can be useful because they can be used to avoid locks and blocking.
Note that things can get more interesting if you want to support these semantics and also allow the receiver to be destroyed prior to destroying the queue.
In non-garbage-collected languages such as C and C++ you need to manage object lifetimes by explicitly allocating and deleting objects. Often this is handled by having strong ownership semantics: a specific object or process is always responsible for allocating and/or destroying particular objects.
In some contexts (such as a real-time audio callback) it is not appropriate to invoke the memory allocator at all, therefore allocation must be performed in another context.
The following allocation/deallocation pattern deals with these scenarios by allocating the new object in the source context when performing a link operation, and deallocating the result in the source context after performing an unlink operation.
This pattern is useful when:
The above example shows literal allocation and destruction of the object, but other variations are possible including:
Create new object and install in target context using destination-context-local storage:
This pattern is useful when objects are always (or mostly) used locally in the receiving context, and allocation and deallocation can be implemented efficiently (e.g. using a simple freelist or O(1) allocator). There may be cache advantages to keeping objects local to a context. This pattern may also result in less complex memory management code in the receiving context if the objects are allocated and/or deallocated as the result of a number of different events, messages or state transitions.
Pre-allocating all needed resources is a common strategy for real-time memory management. Streaming systems usually have a known maximum number of buffers in-flight for a single stream. In these situations closed-loop circular buffer exchange can be used. A fixed number of objects is allocated and then cycled between contexts:
That’s it for the basic patterns.
As I said at the outset, this isn’t the whole picture. There are more involved patterns such as prioritized work lists, asynchronous state mirroring, and sub-object reference counting. You can implement transactions by combining messages so that a set of state transitions is always executed atomically with respect to the receiver. You might want to limit the amount of allocated memory by only having a certain number of messages/objects in-flight at any time. Hopefully I’ll get around to writing about these mechanisms in future posts.
I hope these basic patterns and my explanations give you a new way to think about implementing asynchronous message passing communication in concurrent applications. If you know of any other patterns, references or links on this topic please share them in the comments.
Making and performing electronic music? Check out my AudioMulch software.
Proudly powered by Wordpress and designed by code reduction