Retransmission and the Duplicate Request Cache

A client sends a rename and the reply never arrives. The network dropped the response, or the server died before sending it, or the server executed the rename and then died before sending it. From the client’s position these three cases are identical: no bytes came back. Its only available action is to send the request again, and doing so risks performing the rename twice — which for a rename is harmless, but for an append or a create is not.

Every remote filesystem protocol has to answer this. The answer in the ONC RPC family is a pair of mechanisms: a client that resends until it gets an answer, and a server that remembers which requests it has already answered so that the second copy produces the first copy’s reply instead of a second execution.

The window in which a request has no observable outcome

Consider the timeline. The client writes a request to a socket and starts a timer. The server receives it, performs the operation, and writes a reply. If the reply is lost in transit, the server’s state has changed and the client does not know. If the request is lost, nothing has changed and the client does not know that either. The protocol cannot close this window; it can only make the client’s recovery safe.

Two properties are in tension. At-least-once delivery — resend until acknowledged — guarantees the operation eventually happens, but permits repeats. At-most-once execution guarantees it happens no more than once, but permits the operation never to happen at all if the client gives up. Filesystem protocols generally want at-most-once execution combined with a client policy that retries long enough that “never” becomes unlikely.

The RPC layer makes the repeat detectable rather than deduplicating blindly. Each call carries a 32-bit transaction identifier, the xid, chosen by the client, and the reply echoes it. The protocol treats the xid as a value to compare for equality and nothing else; it does not require the client to change it, and it does not forbid reuse. A client that times out may therefore resend under the same xid, which is what makes retransmission of a single logical operation recognisable, or pick a new one, which leaves the server’s cache unable to match the copy to the original. In practice clients resend under the original xid, because the cache is only useful if they do. The sketch below is schematic, with the table and hash helpers standing for whatever a server implements; the key fields and the two states are the substance.

struct call_key {
    uint32_t xid;
    uint32_t client_addr;
    uint32_t proc;
};

static struct cached_reply drc_busy = { .state = REPLY_IN_PROGRESS };

/* Look up before dispatch: a hit means the reply was already computed. */
struct cached_reply *drc_lookup(const struct call_key *k)
{
    struct cached_reply *r = hash_find(&drc, k);

    if (!r)
        return NULL;
    if (r->state == REPLY_IN_PROGRESS)
        return &drc_busy;   /* original still running: no second copy */
    return r;               /* state == REPLY_DONE */
}

The REPLY_IN_PROGRESS state matters as much as the cached bytes. Without it, a request that takes longer than the client’s timeout is retransmitted while the server is still working on the first copy, and the server begins a second execution concurrently. Marking the entry before dispatch and filling it afterwards means the duplicate is parked, or dropped, rather than duplicated.

What the cache must hold, and what it must not

A cache entry needs the key, a pointer to the reply bytes, and enough metadata to expire it. The key must include the client’s address, because xids are chosen independently by each client and two clients can pick the same 32-bit value; a cache keyed on xid alone would hand one client another’s reply. Including the procedure number guards against a client reusing an xid for a different operation after wrapping.

Size is the real constraint. A reply to a small metadata operation is a few hundred bytes. A reply to a read of a megabyte is a megabyte, and a server holding the last few thousand replies would be holding gigabytes of data it has already sent. Practical servers therefore cache selectively: small replies are retained, and large data replies are either truncated to the status header or skipped entirely, on the reasoning that a repeated read is idempotent and can simply be re-executed. A retransmitted read costs a second disk read, which is cheaper than pinning a megabyte of memory for the length of the retransmission window.

Expiry is by age, not by count alone, because the useful window is bounded by how long a client will keep retrying. If a cached reply is dropped while the client is still resending, the duplicate is executed again — and for a non-idempotent operation that is the failure the cache exists to prevent. The window is therefore set to cover the client’s retransmission budget, which in turn is why a client configured to retry for a very long time forces a server to keep entries longer or to accept duplicates.

The cache is also per-connection in some implementations and global in others. Over UDP the server has no connection state at all, so the cache is a global table indexed by client address. Over TCP, an implementation may keep the cache global and rely on the transport to prevent most duplicates, or scope entries to the connection, which reduces false sharing but loses the ability to deduplicate across a reconnect.

Making operations safe to repeat

Caching replies reduces duplicates but cannot eliminate them, because the cache is finite and the retransmission window is long. The protocol therefore also requires that individual operations be written to tolerate repetition. This is where the procedure design does most of its work, and it is not uniform across the procedure set.

Operations that read state are naturally repeatable. A lookup returns the same answer; a read at a fixed offset returns the same bytes unless someone wrote in between; a get-attributes call returns whatever is currently true. Repeating any of them costs work but cannot corrupt anything. The read case is what makes the large-reply exclusion above tolerable: a retransmitted read is safe to re-execute precisely because it names its offset explicitly rather than relying on a remembered position, which is the same property that lets the file handle stand in for a descriptor.

Operations that create names need care, and the protocol handles it by letting the client state what it wants. Version 3’s create carries a mode. In guarded mode the server must fail if the name already exists, which is what a caller wants when the file is supposed to be new. In unchecked mode the server skips that test and creates or truncates as instructed, leaving the client to determine afterwards whether the name was already there. In exclusive mode the client supplies a verifier and the server records it, so that a retransmitted create can be recognised as the same request and answered as a success rather than as a conflict. That third mode is the one designed for the retransmission case: the server can tell a repeat apart from a genuine second attempt to create the same name.

A remove has a subtler treatment. The server reports what it sees: if the second execution finds no such name, the reply is the ordinary missing-file error, not a fabricated success. The client is the party that understands the retransmission, so it is the client that converts that error into the desired end state — the name is gone, which is what the remove wanted. The conversion happens on the side that knows the request was a repeat.

The awkward cases are operations whose effect depends on prior state in a way the server cannot reconstruct. A write that appends to the current end, or a set-attributes call that sets a timestamp to “now”, produces a different result on the second execution. NFS version 3 sidesteps this by not offering append semantics at the protocol level: a write carries an explicit offset, and the client that wants append behaviour must determine the size and write there, accepting the race. Timestamp-setting calls carry an explicit time, or a flag meaning “server’s current time”, and the latter is the one that can differ on repeat.

The three states a request can leave behind

A repeated request can encounter the server in one of three conditions, and each demands a different response.

If the cache has the completed reply, the server resends those exact bytes. This is the ideal case: the client cannot tell that anything was retried.

If the cache has no entry and the operation is idempotent, the server simply executes it again. The result is correct, the cost is duplicated work, and no one notices.

If the cache has no entry and the operation is not idempotent, the server has a genuine problem: it cannot know whether an earlier copy ran. The available choices are to execute and risk a double effect, to refuse and risk having already succeeded, or to fail in a way the client can disambiguate by re-reading state. Implementations generally execute, because the client that resends has usually already waited long enough that refusing would be worse, and because the window in which the cache lacks the entry is narrow.

A fourth case exists on the server side rather than the client side: the operation completed and the reply was cached, but the server crashes before the cache is written anywhere durable. After restart the cache is empty, the client resends, and the operation runs again. This is the reason state recovery after a restart cannot rely on the reply cache, and the reason servers that keep durable state need a separate recovery protocol.

Transport differences that change the shape of the problem

Over UDP, retransmission is the RPC layer’s job. The client picks a timeout, doubles it on each failure, and stops after a configured number of attempts or a total elapsed budget. Because UDP provides no ordering and no delivery guarantee, the client can also receive a late reply to an earlier attempt after it has already moved on, which is harmless as long as the xid matches and the client accepts the reply for the operation it is waiting on.

Over TCP, retransmission is the transport’s job. The RPC layer sends once and TCP handles loss, so the duplicate-request problem changes form: a duplicate arises mainly when the connection breaks and the client reconnects. If the reply was lost because the connection died, the client reconnects and resends, and the server’s cache is the only thing standing between the client and a second execution. TCP also introduces a subtler issue: a connection that breaks may have a request still in flight at the server, so the server can be executing an operation whose client has already given up on that connection and reconnected elsewhere.

Version 4.1 replaced this whole arrangement with sessions. Each session has a fixed number of slots, each slot has a sequence identifier, and a request names a slot and a sequence number. The server tracks the highest sequence it has seen per slot, so the number of requests a client can have in flight is bounded by the slot count rather than by how many it chooses to send. Replay detection is built on that ordering: a retransmitted request reuses its sequence number, and the server keeps one cached reply per slot so it can resend the original answer rather than re-execute; a request that arrives with a sequence older than the last one that was processed is out of order and is rejected with a sequence error. The mechanism is a bounded window with explicit replay detection rather than a best-effort cache keyed on a transaction identifier, and it gives the server a defined way to tell a client which replies it must resend after a failure.