QPACK and the Cost of a Shared Header Table

HPACK compresses header fields by maintaining a table that both endpoints update in the same order. An encoder inserts a field into the table and then refers to it by index; the decoder applies the same insertions in the same order and arrives at the same table. The scheme depends on total ordering, and total ordering is exactly what QUIC does not provide. Two header blocks sent on different streams can arrive in either order, and a decoder that receives a block referring to an entry it has not yet been told about has no way to reconstruct the field.

The obvious fix — serialize all header blocks — would reintroduce the head-of-line blocking that QUIC was built to remove. QPACK’s answer is to keep the shared table but to decouple the table’s state from the order in which blocks are delivered, at the cost of a new failure mode: a block that cannot be decoded until a future instruction arrives.

What changed from HPACK

HPACK’s dynamic table is indexed relative to the most recent insertion, and both directions of the connection share one table. In HTTP/2 that is safe because the framing layer delivers header blocks in the order they were sent. The table is also updated implicitly: an indexed field in a header block can cause an insertion, so decoding a block changes the table state.

QPACK separates the two functions. The table is updated only by explicit instructions on a dedicated encoder stream, never as a side effect of decoding a header block. A header block is therefore a pure function of the table state at the moment it is decoded plus its own contents, which means a decoder can decode any block for which it has the required table state, regardless of what other blocks have arrived.

There is one table per direction, not one per connection. The encoder’s table holds entries that the encoder has inserted and the decoder will mirror; the decoder’s own inserts go the other way on the other encoder stream. This matters for reasoning about state: an endpoint’s send-side table and receive-side table are independent, and the capacity setting is advertised separately for each.

The static table is shared and never changes. It holds 99 entries of common field names and name-value pairs, indexed from zero, including :authority, :path with /, content-length with 0, and the usual cache-control values. A reference to a static entry costs a few bits and needs no coordination at all, which is why the most common fields in a request are almost always represented statically. Because the table is indexed from zero rather than from one as in HPACK, an implementation that reuses an HPACK encoder’s index arithmetic will be off by one.

Absolute indices, relative indices, and the base

Every dynamic table entry has an absolute index that starts at zero for the first insertion and increases by one for each subsequent insertion. Absolute indices are never reused, even after entries are evicted, so a reference to absolute index 7 always means the same entry or means that the entry has been evicted.

On the wire, entries are referenced by a relative index, which counts backward from a position called the base. The base is chosen by the encoder per header block, and it is signalled in the block’s prefix as a delta from the block’s Required Insert Count. A relative index of zero refers to the entry immediately before the base; higher values refer further back. The encoder chooses the base so that the entries it wants to reference are within reach and so that the decoder can determine, from the prefix alone, what table state it needs.

The Required Insert Count in the prefix is the absolute index of the most recent entry the block depends on, plus one, encoded modulo a value derived from the maximum number of entries the table can hold. The modulo encoding keeps the field small, and it is unambiguous because a decoder never needs to distinguish between insert counts that are further apart than the table’s capacity: an entry older than the capacity has been evicted and cannot be referenced. The encoder computes the field as the Required Insert Count modulo twice the maximum entry count, plus one, with zero reserved for the case where the block references nothing in the dynamic table.

/* RFC 9204 section 4.5.1.1: decode the Required Insert Count. */
static uint64_t decode_ric(uint64_t encoded, uint64_t max_entries,
                           uint64_t total_inserts)
{
    if (encoded == 0) return 0;
    uint64_t full_range = 2 * max_entries;
    if (encoded > full_range) return UINT64_MAX;         /* error */
    uint64_t max_value = total_inserts + max_entries;
    uint64_t max_wrapped = (max_value / full_range) * full_range;
    uint64_t ric = max_wrapped + encoded - 1;
    if (ric > max_value) {
        if (ric <= full_range) return UINT64_MAX;        /* error */
        ric -= full_range;
    }
    return ric;                                          /* zero is an error */
}

The wrap-around logic exists because the encoder’s count and the decoder’s are separated by the network. The decoder knows how many insertions it has actually processed, and the encoded field selects the one value in the recent window whose residue matches. The bound on the table is what makes the window small enough for the field to stay short.

Two streams, and what each carries

The encoder stream is a one-way channel from encoder to decoder carrying instructions that modify the table. Set Dynamic Table Capacity changes the table’s size; Insert With Name Reference adds an entry whose name comes from the static or dynamic table; Insert With Literal Name adds an entry with both name and value spelled out; Duplicate copies an existing entry to the front. All of them are varint-prefixed instructions with a pattern in the high bits identifying the type.

The decoder stream runs the other way and carries feedback. Section Acknowledgment tells the encoder that a header block has been decoded, naming the stream it was on. Stream Cancellation tells the encoder that a stream was reset or abandoned, so the encoder can stop tracking it. Insert Count Increment tells the encoder how many insertions the decoder has processed, which is how the encoder learns that entries have become safe to reference.

The two streams are unidirectional and each endpoint has its own pair, created as the transport-level unidirectional streams that HTTP/3 framing and control streams describes. Because they are QUIC streams, they are ordered and reliable, which is what makes the instructions meaningful: an insertion is applied in the order it was sent, and an acknowledgement refers to a block that the decoder has fully processed. The ordering guarantee is per stream, which is exactly the granularity the table needs.

Blocked streams, and why the limit exists

A header block whose Required Insert Count exceeds the number of insertions the decoder has processed cannot be decoded yet. The decoder must either buffer the block and wait, or treat it as an error. Buffering is the normal case, and the stream is then described as blocked.

The number of streams that may be blocked simultaneously is bounded by a setting the decoder advertises, SETTINGS_QPACK_BLOCKED_STREAMS. An encoder must not allow more than that many blocks to be waiting, and the bound is what keeps the decoder’s memory predictable. A decoder that advertises zero forbids blocking entirely, which forces the encoder to reference only entries it knows have arrived — a safe configuration that gives up most of the compression benefit for requests that follow a burst of new fields.

The encoder’s problem is that it cannot know, at the moment it writes a block, whether the decoder has processed the insertions the block depends on. It knows only what the decoder stream has told it, and that information lags by a round trip. The encoder therefore tracks, for each stream, which insertions it has referenced, and it avoids referencing entries whose acknowledgement has not arrived when the blocked-stream budget is exhausted. This is a scheduling problem rather than a correctness one, and different encoders resolve it differently: some avoid the dynamic table for the first few requests on a connection, some limit references to entries known to be old enough.

The wait itself is not a round trip in the common case. An encoder that inserts an entry and immediately references it on the same stream has created a dependency that is satisfied as soon as the encoder stream’s bytes arrive, which may be in the same packet. The pathological case is a reference to an entry inserted after the block was written, which requires the decoder to wait for both the insertion and the block’s own arrival.

Eviction, and the entries that must not go

The table is a bounded buffer with a capacity in bytes, and the number of entries it can hold is the capacity divided by 32, rounded down, because each entry is charged a fixed overhead of 32 bytes plus the length of its name and value. An insertion that would exceed the capacity evicts entries from the oldest end until it fits, and an entry larger than the whole capacity cannot be inserted at all.

Eviction is where the two directions of the protocol have to agree. The encoder may evict an entry, but the decoder must not evict it while a header block that references it is still in flight. If the decoder dropped it, the block could not be decoded. QPACK handles this by requiring that an entry not be evicted while it is referenced by any unacknowledged block, and by making the encoder’s capacity instruction effective only after the decoder has acknowledged it. An encoder that reduces the table capacity must wait for the reduction to be acknowledged before it relies on the smaller size, because the decoder may still be holding entries the encoder believes are gone.

The acknowledgement machinery is what makes this tractable. Because the encoder learns which blocks have been decoded and how many insertions have been processed, it can compute a safe eviction point: the oldest entry that no outstanding block references. The cost is that the table cannot be used at full efficiency when acknowledgements are delayed, which is the same round-trip penalty that motivates the blocked-stream limit.

Where the design pays for itself

QPACK is more complex than HPACK, and the complexity buys one property: a header block never blocks a different stream. That is the same property the transport provides for data, extended to the compressed representation of the headers.

The price is visible in three places. The encoder stream is a shared resource, and a large insertion can delay the availability of later insertions for every stream. The blocked-stream limit forces a trade between compression ratio and concurrency. And the decoder must maintain a table whose state depends on instructions that may arrive out of order relative to the blocks that use them, which is more state than HPACK’s single ordered table.

For a connection carrying many small requests with similar headers, the dynamic table earns its keep: a repeated user-agent or accept-encoding becomes a single index after the first occurrence, and the static table covers the pseudo-headers for free. For a connection carrying a handful of requests, the table is mostly overhead, and an encoder that never inserts anything is entirely conformant. The setting that governs the table’s capacity is advertised in each direction, so a client and a server can make that choice independently, which is the practical resolution: the mechanism is available where it pays and can be disabled where it does not.

The interaction with the transport’s flow control is worth noting, since the encoder stream consumes connection-level credit like any other stream. A peer that stops reading the encoder stream stalls the table, and a table that stops advancing forces the encoder back to literal representations. The credit accounting described in two-level flow control therefore applies to compression state as well as to body bytes.