# How QPACK Dynamic Table Works in XQUIC's HTTP/3 Implementation

> Discover how XQUIC's QPACK dynamic table achieves efficient HTTP/3 header compression. Learn about its synchronized FIFO buffer, 2-D hash table, and ring memory for optimized performance.

- Repository: [Alibaba/xquic](https://github.com/alibaba/xquic)
- Tags: internals
- Published: 2026-02-24

---

**XQUIC implements the QPACK dynamic table as a synchronized FIFO buffer living on both encoder and decoder sides, using a 2-D hash table for lookups and ring memory for storage, while coordinating via SET_DYNAMIC_TABLE_CAPACITY and INSERT_COUNT_INCREMENT instructions to enable efficient HTTP/3 header compression without head-of-line blocking.**

XQUIC, Alibaba’s open-source QUIC protocol stack, implements RFC 9204’s QPACK specification to compress HTTP/3 headers. The **QPACK dynamic table** stores recently transmitted header name-value pairs on both client and server, allowing subsequent requests to reference entries by index rather than transmitting full strings. This mechanism reduces wire size while respecting QUIC’s multiplexed stream constraints through careful synchronization between encoder and decoder states.

## Core Data Structure of the Dynamic Table

At the heart of XQUIC’s implementation lies the `xqc_dtable_t` structure defined in [`src/http3/qpack/dtable/xqc_dtable.c`](https://github.com/alibaba/xquic/blob/main/src/http3/qpack/dtable/xqc_dtable.c). This structure wraps three specialized utilities to balance fast lookup with memory-efficient storage:

- **2-D hash table** (`ht2d`): Maps name-value pairs to their table indices for duplicate detection
- **Ring array** (`entries`): Maintains FIFO ordering required for proper eviction semantics
- **Ring memory** (`rmem`): Provides contiguous storage for the actual name and value strings

```c
/* src/http3/qpack/dtable/xqc_dtable.c */
typedef struct xqc_dtable_s {
    xqc_2d_hash_table_t    *ht2d;      /* name/value → entry */
    xqc_rarray_t           *entries;   /* ordered FIFO of entries */
    xqc_ring_mem_t         *rmem;      /* raw bytes of name/value strings */
    uint64_t                insert_cnt;/* total inserts since creation */
    uint64_t                first_idx; /* absolute index of the first entry */
    size_t                  capacity;  /* max bytes (name+value+32) */
    size_t                  used;      /* current occupied bytes */
    uint64_t                byte_sum;  /* sum of all sizes (for eviction) */
    uint64_t                min_ref;   /* lowest still‑referenced index */
    xqc_log_t              *log;
} xqc_dtable_t;

```

The `capacity` field represents the **max dynamic table capacity** advertised by the peer via HTTP/3 SETTINGS. Crucially, `min_ref` tracks the lowest index still referenced by in-flight streams, ensuring the encoder never evicts entries that blocked streams depend on—a safety guarantee required by the QPACK specification.

## Encoder-Side Dynamic Table Operations

The encoder manages the dynamic table through a lifecycle that balances insertion opportunities against memory constraints and peer acknowledgment state.

### Table Creation and Capacity Management

When `xqc_encoder_create` initializes the encoder in [`src/http3/qpack/xqc_encoder.c`](https://github.com/alibaba/xquic/blob/main/src/http3/qpack/xqc_encoder.c), it allocates the dynamic table with `need_hash = 1` because the encoder must detect duplicate entries for optimal compression. The encoder maintains two capacity values:

1. **Maximum capacity** (`max_entries`): Immutable limit set by `xqc_encoder_set_max_dtable_cap` when processing the peer’s initial SETTINGS frame
2. **Effective capacity** (`enc->dtable_cap`): Current operating limit set via `xqc_encoder_set_dtable_cap`, which recomputes name and entry size limits and emits a **SET_DYNAMIC_TABLE_CAPACITY** instruction to the decoder

### Entry Insertion and Eviction

When encoding headers, the encoder evaluates whether to insert a new entry based on `enc->name_len_limit` and `enc->entry_size_limit`. If insertion is permitted, `xqc_dtable_add` (line 393 in [`xqc_dtable.c`](https://github.com/alibaba/xquic/blob/main/xqc_dtable.c)) allocates space in ring memory, stores the strings, and updates the 2-D hash table.

If adding an entry would exceed `enc->dtable_cap`, `xqc_dtable_make_space` (lines 336-385) triggers eviction. The function repeatedly calls `xqc_dtable_pop_entry`, but only removes entries whose absolute index is less than `enc->min_ref`, guaranteeing that in-flight references remain valid.

### Blocked Stream Handling

When a header block references a dynamic entry with an index greater than the current **Known Received Count** (`krc`), the stream enters a blocked state. The encoder adds the stream to `enc->blocked_list` via `xqc_encoder_add_blocked_stream` (lines 197-226) and avoids insertions that would increase the Required Insert Count. Once the decoder acknowledges receipt via **INSERT_COUNT_INCREMENT**, `xqc_encoder_unblock_streams` resumes the flow.

## Decoder-Side Dynamic Table Operations

The decoder maintains a mirror of the dynamic table but operates with different constraints and responsibilities.

### Table Creation Without Hash Table

In [`src/http3/qpack/xqc_decoder.c`](https://github.com/alibaba/xquic/blob/main/src/http3/qpack/xqc_decoder.c), `xqc_decoder_create` (lines 23-31) initializes the dynamic table **without** the 2-D hash structure. The decoder only needs to retrieve entries by absolute index, not look up name-value pairs, reducing memory overhead.

### Processing Encoder Instructions

As the decoder receives encoder instructions on the QPACK control stream, `xqc_qpack_on_encoder_ins` in [`src/http3/qpack/xqc_qpack.c`](https://github.com/alibaba/xquic/blob/main/src/http3/qpack/xqc_qpack.c) (lines 53-78) dispatches to specific handlers:

- **INSERT_WITH_NAME_REF**: `xqc_decoder_insert_name_ref` adds an entry referencing the static table or existing dynamic entry
- **INSERT_LITERAL**: `xqc_decoder_insert_literal` inserts a literal name-value pair
- **DUPLICATE**: `xqc_decoder_duplicate` copies an existing dynamic entry to the front

### Required Insert Count Validation

Before decoding a header block, the decoder validates the *Required Insert Count* (RIC) encoded in the field section prefix. In `xqc_decoder_dec_header` → `xqc_rep_decode_prefix` (line 176), if `RIC > insert_cnt`, the decoder returns `blocked = true`, forcing the application to wait for additional encoder instructions before decoding can proceed.

### Acknowledgment and Synchronization

After successfully decoding, the decoder sends **INSERT_COUNT_INCREMENT** via `xqc_qpack_notify_insert_cnt_increment` and **SECTION_ACK** via `xqc_qpack_notify_section_ack` (lines 45-71 in [`xqc_qpack.c`](https://github.com/alibaba/xquic/blob/main/xqc_qpack.c)). These instructions allow the encoder to advance `krc` and unblock waiting streams.

## Synchronizing Encoder and Decoder States

XQUIC keeps the dynamic tables consistent through four critical instruction types exchanged between peers:

| Instruction | Direction | Purpose |
|-------------|-----------|---------|
| **SET_DYNAMIC_TABLE_CAPACITY** | Encoder → Decoder | Advertises the effective capacity limit; decoder stores `max_ents` for RIC validation |
| **INSERT_WITH_NAME_REF / INSERT_LITERAL / DUPLICATE** | Encoder → Decoder | Adds entries to the decoder’s table; encoder updates its own table and tracks acknowledgment state |
| **INSERT_COUNT_INCREMENT** | Decoder → Encoder | Signals that `increment` new entries are acknowledged; encoder updates `krc` and evicts eligible entries |
| **SECTION_ACK** | Decoder → Encoder | Confirms complete processing of a specific stream’s header block; clears blocked-stream state |

All instruction parsing logic resides in [`src/http3/qpack/xqc_qpack.c`](https://github.com/alibaba/xquic/blob/main/src/http3/qpack/xqc_qpack.c) within `xqc_qpack_process_encoder` and `xqc_qpack_process_decoder`, which handle raw byte parsing and callback invocation.

## Practical Implementation Example

The following pattern demonstrates the complete lifecycle of QPACK dynamic table usage in XQUIC:

```c
/* 1️⃣ Create a QPACK handler with local capacity limits */
xqc_qpack_ins_cb_t ins_cb = {
    .get_buf_cb  = my_get_ins_buf,   /* allocate buffer for instructions */
    .write_ins_cb = my_write_ins,    /* send on the control stream */
};
xqc_qpack_t *qpk = xqc_qpack_create(16*1024, 16*1024, log, &ins_cb, NULL);

/* 2️⃣ Set effective capacity after receiving peer SETTINGS */
xqc_qpack_set_dtable_cap(qpk, 8*1024);   /* effective cap = min(local, peer) */

/* 3️⃣ Encode headers using the dynamic table */
xqc_http_headers_t hdrs = {0};             /* populate with :method, :path, etc. */
xqc_var_buf_t *rep_buf = my_rep_buf();       /* buffer for encoded field section */
xqc_qpack_enc_headers(qpk, stream_id, &hdrs, rep_buf);

/* 4️⃣ Send encoded field section on the request stream */

/* 5️⃣ Decode on the server side */
xqc_rep_ctx_t *req_ctx = xqc_qpack_create_req_ctx(stream_id);
xqc_http_headers_t decoded = {0};
xqc_bool_t blocked = XQC_FALSE;
xqc_qpack_dec_headers(qpk, req_ctx,
                      rep_buf->data, rep_buf->data_len,
                      &decoded, XQC_TRUE, &blocked);

/* 6️⃣ Handle blocking: if blocked == true, wait for INSERT_COUNT_INCREMENT 
   from the encoder, then retry step 5 */

```

## Summary

- **Dynamic table structure**: XQUIC uses `xqc_dtable_t` combining a 2-D hash table for encoder lookups, a ring array for FIFO ordering, and ring memory for compact string storage.
- **Encoder responsibilities**: Manages capacity limits via `xqc_encoder_set_dtable_cap`, inserts entries through `xqc_dtable_add`, and evicts only entries below `min_ref` to protect in-flight references.
- **Decoder responsibilities**: Maintains entry storage without hashing, validates Required Insert Count against current `insert_cnt`, and acknowledges progress via **INSERT_COUNT_INCREMENT**.
- **Synchronization mechanism**: Explicit QPACK instructions ensure both sides share identical table states while respecting HTTP/3’s requirement to avoid head-of-line blocking on individual streams.

## Frequently Asked Questions

### How does XQUIC prevent evicting dynamic table entries that are still in use?

XQUIC tracks the `min_ref` field in `xqc_dtable_t`, which represents the lowest absolute index still referenced by any in-flight header block. During eviction in `xqc_dtable_make_space`, entries are only removed if their index is strictly less than `enc->min_ref`. This guarantees that blocked streams waiting for acknowledgments never encounter missing references.

### What is the difference between the encoder's maximum capacity and effective capacity?

The **maximum capacity** (`max_entries`) is an immutable limit set once when the encoder receives the peer’s initial SETTINGS frame via `xqc_encoder_set_max_dtable_cap`. The **effective capacity** (`enc->dtable_cap`) is the currently active limit set by `xqc_encoder_set_dtable_cap`, which may be lower than the maximum to conserve memory or match updated peer constraints. The effective capacity determines actual insertion limits and triggers **SET_DYNAMIC_TABLE_CAPACITY** instructions.

### Why does the XQUIC decoder not use a 2-D hash table for the dynamic table?

The decoder only needs to retrieve existing entries by their absolute index when processing encoded header blocks with dynamic references. Unlike the encoder, which must detect duplicate name-value pairs to avoid redundant insertions, the decoder never performs lookups by content. Omitting the 2-D hash table in `xqc_decoder_create` reduces memory footprint while maintaining full specification compliance.

### How does XQUIC handle streams blocked on dynamic table references?

When the encoder generates a header block referencing an entry with an index greater than the decoder’s known received count (`krc`), it adds the stream to `enc->blocked_list` via `xqc_encoder_add_blocked_stream`. The encoder then avoids insertions that would increase the Required Insert Count for that stream. Once the decoder acknowledges receipt of the missing entries via **INSERT_COUNT_INCREMENT**, `xqc_encoder_unblock_streams` removes the stream from the blocked list and allows encoding to proceed.