It's Actors All The Way Down

The Actor Model explicitly avoids placing constraints on message delivery order beyond causality [1]. Messages may not be delivered before the message which caused them to be sent. In other words, time can’t flow backward. Beyond that, messages arrive in a non-deterministic order. This can sometimes have surprising consequences. Two messages sent in sequence from one actor to another may not arrive in order. This is like two network packets which, due to differences in routing delays, may arrive out-of-order.

Some systems that support actors (such as Erlang) actually do impose a stronger ordering constraint. In some applications, maintaining message order between two actors is important. However, rather than pay the cost of maintaining order for all messages, we would prefer to add that constraint when it is actually required. An order-constrained message channel is easy to create and integrate wherever it is needed in an application.

Message Labels

Our strategy for maintaining message delivery order is based on attaching a label from a defined sequence to each message. The initial label and sequence must be agreed upon by both ends of the channel. If an unbounded series of messages is to be passed, the label sequence should be cyclical. And the cycle should be significantly longer than the expected number of messages in-transit at any given time. To keep our example simple, we will use a linear sequence of integer labels, starting from zero.

Generally, message labels will be attached by the actor that originates the messages. Labels can also be added by a transparent proxy like this:

LET ordered_label_beh(ordered, label, next) = \any.[
	SEND (label, any) TO ordered
	BECOME ordered_label_beh(ordered, next(label), next)
]

When an actor with ordered_label_beh receives any message, it attaches the current label to the message and sends it to the ordered destination. Then the actor will use the next function to generate the next label in the sequence, and update itself accordingly.

Ordered Proxy

On the destination end of the channel, we have a proxy that expects sequence-labelled messages and will re-order them if they arrive out-of-order. We will need a couple of general utility behaviors to implement our proxy.

LET sink_beh = \_.[]
LET forward_beh(next) = \msg.[ SEND msg TO next ]

An actor with sink_beh will ignore any messages it receives.

An actor with forward_beh will forward any messages it receives on to the next actor, specified when the forwarding actor was created.

An ordered proxy is created knowing the delegate that should receive the ordered messages (without labels), the starting label, and the next function used to generate the label sequence.

LET ordered_proxy_beh(delegate, label, next) = \msg.[
	BECOME ordered_root_beh(NEW sink_beh, delegate, label, next)
	SEND msg TO SELF
]

The ordered proxy keeps track of delayed messages. However, the strategy used to track and re-order messages is an implementation detail. Therefore the ordered_proxy_beh is actually just a lazy constructor for the real implementation. When an actor with ordered_proxy_beh receives a message, it replaces its behavior with ordered_root_beh, and re-sends the message msg to itself.

Proxy Root

The proxy root is the true implementation of an ordered proxy. It receives sequence-labelled messages. If the label matches the expected sequence, it has arrived in-order, so the message is passed on to the delegate (after removing the label). Otherwise, the message has arrived out-of-order, so it is stored for later delivery.

LET ordered_root_beh(delayed, delegate, label, next) = \(label', any).[
	CASE label' OF
	$label : [
		SEND any TO delegate
		LET label'' = $next(label)
		SEND label'' TO delayed
		BECOME ordered_root_beh(delayed, delegate, label'', next)
	]
	_ : [
		CREATE delayed' WITH 
			ordered_delay_beh(SELF, delayed, label', any)
		BECOME ordered_root_beh(delayed', delegate, label, next)
	]
	END
]

When an actor with ordered_root_beh receives a labelled message, it checks the label’ in the message against the expected label. If the labels match, the un-labelled message any is forwarded to the delegate. The next function is used to generate label”, the next expected label in the sequence, which is sent to the chain of delayed message-holders and used to update the behavior of the current actor.

If the labels do not match, a new delayed’ message-holder is created, and linked into the delayed-message chain.

Delayed Messages

Delayed messages are linked together into a chain, starting with the proxy root. When the root is updated with a new sequence label, the new expected label value is passed through the chain. If the new label matches the label of a delayed message, that message is re-issued to the root, which will now deliver it because its place in the sequence has arrived.

LET ordered_delay_beh(root, delayed, label, any) = \label'.[
	CASE label' OF
	$label : [
		SEND (label, any) TO root
		BECOME forward_beh(delayed)
	]
	_ : [
		SEND label' TO delayed
	]
	END
]

When an actor with ordered_delay_beh receives a label’ message that matches the label of the delayed message it holds, the delayed message is re-sent to the proxy root for delivery, and this actor becomes a transparent forwarder. Otherwise the label’ is passed on to the rest of the delayed chain.

As previously noted, the potentially growing chain of forwarding actors can be systematically eliminated by the garbage collector. If this feature is not available, further steps would be required in order to prune the unnecessary forwarders.

Test Fixtures

Testing these behaviors requires that we arrange to deliver messages out-of-order. Instead of using ordered_label_beh to generate labelled messages, we will explicitly label a set of test messages.

LET labels = $(0, \n.add(n, 1))
CREATE proxy WITH ordered_proxy_beh(println, labels)
SEND (3, #w) TO proxy
SEND (1, #y) TO proxy
SEND (2, #x) TO proxy
SEND (0, #z) TO proxy

The starting label (zero) and sequence-generating function (increment) are packaged up into the labels variable, which is used to initialize ordered_proxy_beh. Then we send a series of messages with out-of-order labels. The resulting output should be:

#z
#y
#x
#w

Explicit specification of out-of-order delivery makes a good unit test. A non-deterministic, but more realistic way to exercise the code is to simulate variable delivery delays for each message. We can do that by introducing an actor to play the role of the network.

LET net_beh(cust, base, range) = \msg.[
	SEND (k_random, range) TO random
	CREATE k_random WITH \n.[
		SEND (add(base, n), msg, cust) TO timer
	]
]
CREATE net WITH net_beh(proxy, 0, 1000)

The net actor propagates messages to a customer cust after a random delay from base to base+range. This should perturb the delivery order, although not in a predictable manner.

Next we create an actor to supply a series of sequence-labelled messages from a NIL-terminated list.

LET src_beh(cust, n, succ) = \list.[
	CASE list OF
	(h, t) : [
		SEND (n, h) TO cust
		BECOME src_beh(cust, succ(n), succ)
		SEND t TO SELF
	]
	END
]
CREATE src WITH src_beh(net, labels)
SEND (#a, #b, #c, #d, #e, #f, #g, #h, #i, #j, #k, NIL) TO src

The src actor uses the labels definition to generate and apply sequence labels to a list of messages. The message at the head h of the list is given the current label, the actor’s behavior is updated with the next generated label, and the tail t of the list is sent back to the same actor for further processing.

The test configuration connects src to net, and net to the ordered proxy. Labels are attached by src. Random delays are introduced by net, which should cause some out-of-order deliveries. The labels are removed by proxy, which then sends the original message to the console via println. Despite the re-ordering of messages due to random delays, the messages will be printed in the order they appeared in the src list.

Summary

Although message delivery order is sometimes important in an application, there is a cost to requiring it for all messaging in a system. We would prefer to incur this cost only when delivery order actually matters. We have shown a simple mechanism for ensuring message delivery order between two endpoints in a pure actor-based system. This mechanism is easy to incorporate where in-order message delivery is required.

References

[1]

W. D. Clinger. Foundations of Actor Semantics. AITR-633, MIT AI Lab, 1981.