Resource Management

Many communication protocols operate by sending individual messages or requests over a single, fifo communication channel. If processing a message takes a long time, it makes little sense to wait for the message to be fully processed before accessing the next message from the communication channel. Instead, one usually moves the message elsewhere in memory, freeing up the communication channel and allowing to pop the next message almost immediately. The actual, slow message processing can then be done by another thread or via non-blocking IO.

Unfortunately, memory is finite, so there has to be a limit on how many messages can be copied elsewhere. Once that limit is reached, the process can either crash (not good), or it must wait for messages to finish processing, essentially leaving us with the same problem as we started with.

In some sense, there is no way around that. However, we would prefer if the communication partner knew when this was about to happen; it could then throttle its more expensive messages, so that its cheaper messages could still be processed without delay. This is crucial to implementing logically independent communication channels on top of a single physical communication channel.

Here, we describe a simple way of maintaining independent message buffers for each logical communication channel. When receiving a message that will take a long time to process, a peers moves it into the message buffer for that kind of messages. This keeps the main communication channel responsive. If a message buffer has insufficient capacity for new messages, the other peer is informed in advance, so that it does not send messages that cannot be buffered.

Requirements

To describe our approach more precisely, we need to introduce some terminology. One peer — the client — sends messages to the other peer — the server. Messages belong to logical communication channels, and the server maintains a fifo buffer for each logical channel. Some messages do not belong to any logical channel — those are messages that can always be processed immediately and in negligible time, so they are never moved to any buffer. In particular, our approach adds its own message kinds for exchanging metadata about the buffers. All of these control messages do not belong to any channel — if buffer management required buffer capacity in the first place, things could quickly go wrong.

We now present some properties we would like our solution to fulfil.

The server should be able to inform the client about its remaining buffer capacities for its logical channels, and keep these values up to date as it buffers and processes (thus freeing buffer space) messages. The client should be able to rely on this information: if the server promises buffer capability, it must deliver.

The server should be able to resize its buffers to cope with competing resource demands. Increasing buffer capacity is unproblematic, but we will see that decreasing buffer capacity requires cooperation with the client in some situations.

Finally, the client should be able to optimistically send messages even though their corresponding buffer might be full — by the time the messages arrive at the server, the buffer space might have become available after all. The server must be able to reject and drop such optimistically transmitted messages, however. When it does, it must inform the client, because the client always needs to maintain accurate (if delayed) information about all buffer states.

Solution Overview

To satisfy these requirements, our solution builds on the concept of guarantees. The server sends guarantees of available buffer space to the client per logical channel; the client tracks its available guarantees and knows that all of its messages that do not exceed the guarantees will be buffered.

This diagram shows the statekeeping for only a single logical channel. The full session state consists of an independent copy for every different logical channel a protocol defines.

When the server increases a buffer’s capacity, it gives that many guarantees (measured in bytes) for the corresponding logical channel to the client. When establishing the connection, the client has no guarantees, and the server typically starts by sending guarantees equal to its initial buffer capacities. Conceptually, the server begins its operation by increasing its buffer capacities from zero to their actual starting amounts.

The second way of giving guarantees occurs when the server has processed a buffered message and thus frees up buffer space. It then communicates the amount of buffer space that was freed up, and for which logical channel. The server need not communicate this immediately, it is free to send only the occasional update that aggregates guarantees that stem from processing several messages from the same logical channel.

When the server wishes to reduce the capacity of some buffer, it simply processes messages from that buffer without informing the client. This decreases the overall amount of guarantees in the system by the correct amount.

This technique is only applicable when the server has some buffered messages; it does not allow it to reduce buffer capacity for empty buffers. But the server cannot simply decrease the buffer size and then inform the client: while that information is travelling to the client, the client might send messages on this logical channel, fully expecting them to be buffered by the server.

To solve this problem, we introduce a mechanism for the client to absolve the server of some absolute amount of its unused guarantees on some logical channel, and we add a way for the server to ask for such absolution. Asking for absolution takes the form of specifying the logical channel and the number of guarantees the server would like the client to keep. Upon receiving this request, the client absolves the server of exactly the amount needed to reach the desired number of guarantees. If the client already has fewer guarantees by the time the request for absolution arrives, the client simply ignores the request.

Taken together, these techniques make for a stable system where the client never overwhelms the buffer capacity of the server. As a final addition, however, we want to allow the client to optimistically send data even though it might have no corresponding guarantees. The server may, after all, have freed up buffer space by the time the optimistically transmitted messages arrive.

If the server has insufficient buffer capacity when an optimistically transmitted message arrives, the server drops it without any processing. This requires us to add a certain degree of retransmission logic to the protocol, since the client must be informed of the message dropping.

To keep the complexity of the retransmission logic minimal, we adopt a simplistic solution: when the server drops an optimistically11The server is still not allowed to drop messages for which it had previously guaranteed buffer capacity. transmitted message, it must keep dropping all messages on the same logical channel, until it receives an apology message for that logical channel from the client. The server informs the client that it has started to drop messages, at which point the client can send an apology and can then resume normal operation.

This approach comes with two subtleties. First, the server must never buffer partial messages — if it can buffer all but one byte of a message, it must still drop the full message and all subsequent ones until the apology. Second, the server must issue guarantees for all the optimistic message bytes that it did manage to buffer, before informing the client that it has started to drop messages. This is necessary so that the client can reconstruct exactly which of its messages got dropped, and which still made it through.

Message Types

The following pseudo-types summarise the different kinds of control messages that this approach introduces. The parameter C is a type with one value for each logical channel. Each message pertains to exactly one logical channel, specified by its channel field.

Data Handles

In this section, we discuss a common special case of resource control: that of maintaining numeric identifiers for shared context between two peers. For example, a peer might send a large piece of data, give it a numeric identifier, and then reference the data through its identifier rather than repeatedly including the data in future messages.

Depositing data like this with the other peer requires them to spend resources (memory), so immediately questions of resource control and throttling arise. We first sketch a lightweight approach to maintaining data handles without considering resource concerns, and then show how to implement that approach on top of logical channels such that resource concerns are addressed.

Requirements

We consider a client who asks a server to bind some data of some type to numeric resource handles. The same protocol might use multiple types of data, each with its own independent handle types (and independent resource control).

Since both the client and the server must keep track of all resource handles, they should both be able to remove bindings. We call this operation freeing a resource handle.

Note that we only discuss resource handles that live during a particular protocol run between two peers. We do not consider the problem of persisting peer-specific state across sessions.

Managing Resource Handles

We use consecutive natural numbers as resource handles. For each handle type, both peers keep track of the least number that has not yet been assigned as a handle of that type. In order to bind a value to a resource handle, the client simply transmits the data and its type. The least number that had not been assigned before becomes the resource handle of the transmitted data. Both peers add the new mapping into some data structure they can use to later dereference the resource handle into its value.

The main issue in maintaining resource handles is that of coordinating freeing over an asynchronous communication channel. Suppose one peer removes a handle-to-value binding from their local mapping, sends a message to inform the other peer, but that peer has concurrently sent some message that pertains to the resource handle in question. Everything breaks! Hence, freeing must be a three-step process:

1. one peer sends a message that proposes to free a resource handle (and, in doing so, that peer commits to not referring to that handle in any of its future messages),
2. the other peer, upon receiving that proposal, marks the corresponding handle-to-value binding in its local mapping for deletion22We explain below why the binding cannot be deleted immediately. and sends a confirmation message,
3. the first peer, upon receiving the confirmation, can then also mark the handle-to-value binding in its local mapping for deletion.

There is no need to use separate message types for proposals and confirmations of freeing: peers react to a proposal to free by sending their own proposal to free the same resource handle. Receiving a proposal to free a resource handle after having sent such a proposal oneself confirms that the handle-to-value binding can be removed from the local mapping. A nice side effect of this approach is that it gracefully handles concurrent proposals to free the same resource handle by both peers.

Why do the peers merely mark mappings for deletion rather than immediately removing them? Because they might still buffer unprocessed messages for some logical channels that reference the resource handle being freed. To deal with this, a peer can keep a counter with every resource handle that gets incremented whenever a message that references the resource handle is moved to a buffer. Whenever such a message has been fully processed, the counter is decremented again. The peer locally deletes a binding if it is marked for deletion while its counter is zero, or if its counter reaches zero after it has been marked for deletion.

Resource Control

Adding handle-to-value bindings to local mappings requires space, so the server should have a way to throttle the client. We use a simple solution: for each handle type, the messages for binding new resource handles are sent over their own logical channel. Throttling that logical channel controls the number of resource handles that can be created.

Crucially, guarantees for the logical channel for issuing resource handles of some handle type must guarantee not only that the messages will be buffered, but that they will be processed and the resource handles will be boundIf bindings are to be stored in a complex data structure with a fragmented memory layout, the server must issue guarantees based on conservative approximations of memory usage.. This ensures that the client knows which resource handles are safe to reference.

The client may send optimistic messages on such a logical channel. The client may even reference these optimistically bound resource handles in arbitrary other messages. When the server receives a message that references a resource handle that is greater than the greatest resource handle it has bound of that handle type, it must first check whether it has unprocessed messages for binding resource handles of this type, and process as many of them as possible.

If processing those messages binds the resource handle in question, the server can then resume processing the optimistic reference to that resource handle as if nothing had happened. If, however, it then still has not bound the resource handle in question, then the message for binding the resource handle must have been dropped, and the server has already sent a AnnounceDropping message, from which the client can infer that its optimistic reference to the resource handle could not be processed either. The server then simply drops the message without any further processing.

Message Types

The following pseudo-types summarise the messages for maintaining resource handles. The parameter H is a type with one value for each handle type. Each message pertains to exactly one handle type, specified by its handle_type field. BindHandle messages belong to logical channels determined by their handle_type field, FreeHandle messages are control messages that do not belong to any logical channel.