> For the complete documentation index, see [llms.txt](https://xyy94813.gitbook.io/x-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xyy94813.gitbook.io/x-note/ya-suo-suan-fa/hpack.md).

# HPACK

HPACK（HTTP/2 Header Compression）是 HTTP/2 中的头部压缩算法。 使用 HPACK 算法对头部信息进行压缩，可以减少头部的大小，提高数据传输的效率。

## 核心原理

对于每个要发送的首部字段，HPACK 使用整数编码来表示字段的名称和值。 其原理主要基于以下两个关键概念：

* 静态表（Static Table）
* 动态表（Dynamic Table）

编码过程：

1. 首先尝试在动态表中查找对应的字段。
2. 如果找到匹配的字段，则使用动态表中的索引来引用该字段。
3. 如果未找到匹配的字段，则在静态表中查找对应的字段，使用静态表的索引进行引用。
4. 如果仍未找到匹配的字段，则使用字面值编码，将字段的名称和值直接发送。

解码过程：

1. 初始化上下文： 接收端需要初始化一个上下文，包括静态表和动态表的初始状态。
2. 解码整数编码： 接收端根据 HPACK 规范解码整数编码，确定字段的名称和值的索引。 根据索引，接收端可以从静态表或动态表中获取对应的字段名称和值。
3. 解码字面值编码： 如果整数编码无法匹配字段的名称和值，则接收端需要解码字面值编码，直接获取字段的名称和值。
4. 更新上下文： 接收端根据解码的字段信息，更新动态表的状态。 如果解码的字段是新的字段，接收端将其添加到动态表中。 如果解码的字段是已经存在的字段，接收端可以根据需要更新动态表的状态，比如调整字段的位置或删除字段。
5. 还原头部信息： 接收端根据解码的字段信息，还原完整的头部信息。 通过使用静态表和动态表中的字段名称和值，接收端可以还原发送端发送的原始头部信息。

### 静态表

静态表是一个[预定义的首部字段表](https://httpwg.org/specs/rfc7541.html#static.table.definition)，包含了一些常见的 HTTP 首部字段和对应的值。

### 动态表

动态表是一个动态调整的首部字段表，用于存储请求和响应中使用的首部字段。

#### 动态表管理

使用 FIFO（First In, First Out）的方式来管理动态表。 当动态表已满时，新的字段会将最老的字段挤出。 动态表的大小是可以配置的，可以根据具体的需求进行调整。

为什么不使用 LRU？

1. 简化实现：HPACK 算法的设计目标之一是简化实现。
2. 减少计算和存储开销
3. 考虑实际场景：HTTP/2 的头部压缩主要是为了减少头部信息的大小，提高数据传输的效率。 在实际的 HTTP 请求和响应中，通常只有少数的首部字段会被频繁地使用。

可以通过 `SETTINGS_HEADER_TABLE_SIZE` 帧更新动态表大小

### 上下文维护

为了保持发送端和接收端的一致性，发送端需要维护一个上下文，包括动态表和静态表的状态。 接收端通过解码过程来还原发送端的上下文。

当用于双向通信时，例如在 HTTP 中，端点维护的编码和解码动态表是完全独立

### 索引地址空间

静态表和动态表被组合到单个索引地址空间中。

1 到静态表长度（含）之间的索引指的是静态表中的元素。 严格大于静态表长度的索引引用动态表中的元素。（减去静态表的长度即可找到动态表的索引）

## 原始类型

HPACK 编码使用两种基本类型：

* 无符号变长整数（unsigned variable-length integers）
* 八位字节字符串（strings of octets）

### 整数表示

**整数用于表示名称索引、标头字段索引或字符串长度。** 整数表示可以从八位字节内的任何位置开始。 为了实现优化处理，整数表示总是在八位字节的末尾结束。

整数由两部分表示：

* 填充当前八位字节的前缀。 如果最高位为 0，表示整数编码为增量编码（Incremental Indexing） 如果最高位为 1，表示整数编码为无增量编码（Non-Incremental Indexing）
* 当整数值不适合前缀时使用的可选八位字节列表。前缀的位数（称为 N）是整数表示的参数。

如果整数值足够小，即严格小于 $2^N - 1$，则将其编码在 N 位前缀内。 例如 （N = 5）:

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? |       Value       |
+---+---+---+-------------------+
```

否则，前缀的所有位都设置为 1，并且使用一个或多个八位位组的列表对减去 $2^N - 1$ 的值进行编码。

每个八位位组的最高有效位用作连续标志： 除了列表中的最后一个八位位组之外，其值设置为 1。 八位位组的剩余位用于对减少的值进行编码。

解码后的整数值（显示为 N = 5）：

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| ? | ? | ? | 1   1   1   1   1 |
+---+---+---+-------------------+
| 1 |    Value-(2^N-1) LSB      |
+---+---------------------------+
               ...
+---+---------------------------+
| 0 |    Value-(2^N-1) MSB      |
+---+---------------------------+
```

从八位位组列表中解码整数值首先要反转列表中八位位组的顺序。 然后，对于每个八位位组，其最高有效位被删除。 将八位位组的剩余位连接起来，并将结果值增加 $2^N - 1$ 以获得整数值。

这种整数表示允许无限大小的值。 **编码器也有可能发送大量零值，这可能会浪费八位字节，并可能用于溢出整数值。** 超出实现限制（值或八位字节长度）的整数编码必须被视为解码错误。

### 字符串文字表示

标头字段名称和标头字段值可以表示为字符串文字。 字符串文字被编码为八位位组序列，可以通过直接编码字符串文字的八位位组，也可以使用霍夫曼代码

字符串文字表示:

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| H |    String Length (7+)     |
+---+---------------------------+
|  String Data (Length octets)  |
+-------------------------------+
```

* H：一位标志 H，指示字符串的八位字节是否经过霍夫曼编码。 如果 H 为“0”，则编码数据是字符串文字的原始八位字节。 如果 H 为“1”，则编码数据是字符串文字的霍夫曼编码。
* 字符串长度：用于编码字符串文字的八位字节数，编码为带有 7 位前缀的整数
* 字符串数据：字符串文字的编码数据。

由于霍夫曼编码数据并不总是以八位字节边界结束，因此在其后面插入一些填充，直到下一个八位字节边界。 为了防止此填充被误解为字符串文字的一部分，使用与 EOS（字符串结尾）符号相对应的代码的最高有效位。

解码时，编码数据末尾的不完整代码将被视为填充并被丢弃。 严格长于 7 位的填充必须被视为解码错误。 与 EOS 符号代码的最高有效位不对应的填充必须被视为解码错误。 包含 EOS 符号的霍夫曼编码字符串文字必须被视为解码错误。

## 二进制格式

### 索引标头字段表示

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 1 |        Index (7+)         |
+---+---------------------------+
```

索引头字段以 `'1' 1-bit` 模式开始，后跟匹配头字段的索引，表示为带有 7 位前缀的整数

### 具有增量索引的文字标头字段

具有增量索引的文字标头字段 — 索引名称:

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |      Index (6+)       |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

具有增量索引的文字标头字段 — 新名称:

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 1 |           0           |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

具有增量索引表示形式的文字标头字段以 `'01' 2-bit` 模式开头

如果头字段名称与存储在静态表或动态表中的条目的头字段名称匹配，则可以使用该条目的索引来表示头字段名称。 在这种情况下，条目的索引表示为带有 6 位前缀的整数

否则，标头字段名称将表示为字符串文字。 使用值 0 代替 6 位索引，后跟标头字段名称。

任一形式的标头字段名称表示形式后跟表示为字符串文字的标头字段值

### 不带索引的文字标头字段

没有索引表示的文字标头字段会导致将标头字段附加到已解码的标头列表，而不更改动态表。

没有索引的文字标头字段 — 索引名称：

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |  Index (4+)   |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

不带索引的文字标头字段 — 新名称：

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |       0       |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

没有索引表示的文字标头字段以 `'0000' 4-bit` 开头

如果头字段名称与存储在静态表或动态表中的条目的头字段名称匹配，则可以使用该条目的索引来表示头字段名称。 在这种情况下，条目的索引表示为带有 4 位前缀的整数。*该值始终非零。*

否则，标头字段名称将表示为字符串文字。使用值 0 代替 4 位索引，后跟标头字段名称。

任一形式的标头字段名称表示形式后跟表示为字符串文字的标头字段值\\

### 文字标头字段从未被索引

文字标头字段从不索引表示会导致将标头字段附加到解码的标头列表，而不更改动态表。 中介体必须使用相同的表示形式来编码该头字段。

从未被索引的文字标头字段 — 索引名称:

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |  Index (4+)   |
+---+---+-----------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

从未索引的文字标头字段 — 新名称:

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |       0       |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

没有索引表示的文字标头字段以 `'0001' 4-bit` 开头

当标头字段表示为从未索引的文字标头字段时，它必须始终使用此特定文字表示形式进行编码。 特别是，当对等方发送其收到的标头字段（表示为从未索引的文字标头字段）时，它必须使用相同的表示形式来转发此标头字段。

这种表示形式旨在保护标头字段值，使其不会因压缩而面临风险

表示的编码与没有索引的文字头字段相同。

## 参考

* [RFC7541: HPACK Header Compression for HTTP/2](https://httpwg.org/specs/rfc7541.html)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://xyy94813.gitbook.io/x-note/ya-suo-suan-fa/hpack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.