QPACK：一种用于有效表示 HTTP/3 中使用的 HTTP 字段的压缩格式。 这是 HPACK 压缩的一种变体，旨在减少队头阻塞。
为什么 HTTP/3 不使用 HPACK
如果 HPACK 用于 HTTP/3，由于所有流上帧之间的总排序的内置假设，它会导致字段部分出现队头阻塞。
QPACK 重用了 HPACK 的核心概念，但经过重新设计，可以在无序交付的情况下保持正确性，并具有实现灵活性，以在抵御队头阻塞的弹性和最佳压缩比之间取得平衡。 设计目标是在相同损耗条件下，接近 HPACK 的压缩比，同时显着减少队头阻塞。
快速对比 HPACK
压缩算法：QPACK 和 HPACK 使用的压缩算法不同。QPACK 使用了双向哈希表，可以在两个方向上进行压缩和解压缩，而 HPACK 使用的是哈夫曼编码和静态表。
动态表的处理：QPACK 中的动态表相对于 HPACK 更加灵活。在 QPACK 中，发送方和接收方都有自己的动态表，可以独立地进行增删操作，并且可以异步更新对方的动态表。而 HPACK 中的动态表是共享的，只有发送方可以修改它，并且需要在每个头部字段中包含索引来引用动态表中的条目。
首部字段索引：QPACK 和 HPACK 对于引用静态表中的字段和动态表中的字段使用了不同的索引编号。QPACK 使用了两个索引编号空间，一个用于静态表，一个用于动态表，从而提供更高的灵活性。
流水标记：QPACK 引入了流水标记（Stream Identifier），用于标识在流中传输的 QPACK 压缩块，以帮助接收方解压缩和处理这些块。
静态表
QPACK 静态表的索引从 0 开始，而 HPACK 静态表的索引从 1 开始。
动态表
动态表由按先进先出顺序维护的字段行列表组成。 QPACK 编码器和解码器共享一个最初为空的动态表。 编码器将条目添加到动态表中，并通过编码器流上的指令将它们发送到解码器；
动态表容量
动态表的大小是其条目大小的总和。
为了限制解码器的存储器要求，解码器限制编码器允许为动态表容量设置的最大值。 在 HTTP/3 中，这个限制是由解码器发送的 SETTINGS_QPACK_MAX_TABLE_CAPACITY 的值决定的
每当编码器减少动态表容量时，条目就会从动态表末尾逐出，直到动态表的大小小于或等于新表容量。 该机制可用于通过将容量设置为 0 来完全清除动态表中的条目，随后可以恢复该条目。
在将新条目添加到动态表之前，条目会从动态表的末尾逐出，直到动态表的大小小于或等于（表容量-新条目的大小）； 编码器不得导致动态表条目被驱逐，除非该条目是可驱逐的； 然后，新条目将添加到表中。
绝对索引（Absolute Indexing）
每个条目都拥有一个在该条目的生命周期内固定的绝对索引。 插入的第一个条目的绝对索引为 0；每次插入索引都会增加 1。
相对索引（Relative Indexing）
相对索引从零开始，并以与绝对指数相反的方向增加。 确定哪个条目的相对索引为 0 取决于引用的上下文。
在编码器指令中，相对索引 0 指的是动态表中最近插入的值。 请注意，这意味着在解释编码器流上的指令时，给定相对索引引用的条目将发生变化。
动态表索引示例 - 编码器流:
复制 +-----+---------------+-------+
| n-1 | ... | d | Absolute Index
+ - - +---------------+ - - - +
| 0 | ... | n-d-1 | Relative Index
+-----+---------------+-------+
^ |
| V
Insertion Point Dropping Point
n = count of entries inserted
d = count of entries dropped 与编码器指令不同，字段行表示中的相对索引是相对于编码字段部分开头的 Base 的； 这确保了即使编码字段部分和动态表更新无序处理，引用也是稳定的。
动态表索引示例 - 表示中的相对索引:
复制 Base
|
V
+-----+-----+-----+-----+-------+
| n-1 | n-2 | n-3 | ... | d | Absolute Index
+-----+-----+ - +-----+ - +
| 0 | ... | n-d-3 | Relative Index
+-----+-----+-------+
n = count of entries inserted
d = count of entries dropped
In this example, Base = n - 2 后基索引（Post-Base Indexing）
后基索引用于绝对索引大于或等于 Base 的条目的字段行表示，对于绝对索引等于 Base 的条目从 0 开始，并以与绝对索引相同的方向增加。
后基索引允许编码器一次性处理一个字段部分，并包括对处理该（或其他）字段部分时添加的条目的引用。
动态表索引示例 - 表示形式的后基索引：
复制 Base
|
V
+-----+-----+-----+-----+-----+
| n-1 | n-2 | n-3 | ... | d | Absolute Index
+-----+-----+-----+-----+-----+
| 1 | 0 | Post-Base Index
+-----+-----+
n = count of entries inserted
d = count of entries dropped
In this example, Base = n - 2 原始类型
整数表示
QPACK 基于 HPACK 中的格式，扩展了一些未使用的一些前缀。
QPACK 实现必须能够解码长度不超过 62 位的整数
字符串文字表示
与 HPACK 中一致
编码和解码
与 HPACK 一样，QPACK 使用两个表将字段行（“标头”）与索引相关联。
QPACK 定义了单向流，用于从编码器向解码器发送指令，以及解码器向编码器发送指令：
发送方不得关闭这些流中的任何一个，并且接收方不得请求发送方关闭这些流中的任何一个。
编码
编码器通过为列表中的每个字段行发出索引或文字表示，将标头或尾部部分转换为一系列表示。 索引表示通过用静态或动态表的索引替换文字名称和可能的值来实现高压缩。 对静态表和文字表示的引用不需要任何动态状态，并且永远不会有队头阻塞的风险。 如果编码器没有收到指示该条目在解码器处可用的确认，则对动态表的引用存在队头阻塞的风险。
为了确保不阻止编码器添加新条目，编码器可以避免引用接近驱逐的条目。 编码器可以发出重复指令并引用重复指令，而不是引用此类条目。
清除动态表条目：
复制 <-- Newer Entries Older Entries -->
(Larger Indices) (Smaller Indices)
+--------+---------------------------------+----------+
| Unused | Referenceable | Draining |
| Space | Entries | Entries |
+--------+---------------------------------+----------+
^ ^ ^
| | |
Insertion Point Draining Index Dropping
Point 确定哪些条目太接近驱逐而无法引用是编码器的偏好。 一种启发式方法是在动态表中定位固定数量的可用空间：未使用的空间或可以通过逐出非阻塞条目回收的空间。
由于 QUIC 不保证不同流上的数据之间的顺序，因此解码器可能会遇到引用尚未接收的动态表条目的表示。 每个编码字段部分都包含一个所需的插入计数，这是可以对字段部分进行解码的插入计数的最低可能值。
当解码器接收到所需插入计数大于其自身插入计数的编码字段部分时，该流无法立即处理并被视为“阻塞”；
编码器可以决定是否冒流被阻塞的风险。如果 SETTINGS_QPACK_BLOCKED_STREAMS 的值允许，通常可以通过引用仍在传输中的动态表条目来提高压缩效率，但如果存在丢失或重新排序，则流可能会在解码器处被阻塞。编码器可以通过仅引用已确认的动态表条目来避免阻塞风险，但这可能意味着使用文字。由于文字使编码字段部分变大，这可能会导致编码器因拥塞或流量控制限制而被阻塞。
编码器指令
编码器在编码器流上发送编码器指令以设置动态表的容量并添加动态表条目。 添加表项的指令可以使用现有的表项，以避免传输冗余信息。 该名称可以作为对静态或动态表中现有条目的引用或作为字符串文字来传输。 对于动态表中已存在的条目，也可以通过引用使用完整条目，从而创建重复条目。
设置动态表容量
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | Capacity (5+) |
+---+---+---+-------------------+ 插入名称索引
插入字段行——索引名称:
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | T | Name Index (6+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+ 插入文字名称
插入字段行——新名称:
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | H | Name Length (5+) |
+---+---+---+-------------------+
| Name String (Length bytes) |
+---+---------------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+ 复制
现有条目将重新插入动态表中，而无需重新发送名称或值。 这对于避免添加对旧条目的引用很有用，这可能会阻止插入新条目。
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | Index (5+) |
+---+---+---+-------------------+ 解码
解码器在解码器流上发送解码器指令，通知编码器有关字段部分和表更新的处理，以确保动态表的一致性。
与 HPACK 中一样，解码器处理一系列表示并发出相应的字段部分。 它还处理在编码器流上接收到的修改动态表的指令。 请注意，编码字段部分和编码器流指令到达不同的流。 这与 HPACK 不同，HPACK 中编码的字段部分（标头块）可以包含修改动态表的指令，并且没有专用的 HPACK 指令流。
收到编码字段后，解码器会检查 "要求插入计数"。 当所需插入计数小于或等于解码器的插入计数时，可立即处理字段部分。 否则，接收字段数据的数据流将被阻塞。
在阻塞期间，已编码的字段数据应保留在被阻塞数据流的流量控制窗口中。 在数据流解除阻塞之前，这些数据是不可用的，过早释放流量控制会使解码器容易受到内存耗尽攻击。 当解码器开始从流中读取的所有编码字段的插入计数大于或等于 "所需的插入计数 "时，流就会解除阻塞。
解码器通过在解码器流上发出解码器指令来发出以下事件信号进行状态同步：
确认指令
在处理其声明的所需插入计数不为零的编码字段部分后，解码器发出部分确认指令。
确认部分:
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | Stream ID (7+) |
+---+---------------------------+ 流取消（Stream Cancellation）
当流被重置或读取被放弃时，解码器发出流取消指令。 该指令以 '01' 2-bit 位模式开头，后跟编码为 6 位前缀整数的受影响流的流 ID。
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | Stream ID (6+) |
+---+---+-----------------------+ 插入计数增量
该指令将已知接收计数增加 Increment 参数的值。 解码器应发送一个增量值，将已知接收计数增加到迄今为止处理的动态表插入和重复的总数。
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | Increment (6+) |
+---+---+-----------------------+ 字段行格式
编码字段部分由前缀和本部分中定义的可能为空的表示序列组成。 每个表示对应于一条字段行。 这些表示引用特定状态下的静态表或动态表，但它们不会修改该状态。
编码字段部分在由封闭协议定义的流上的帧中携带。
编码字段部分前缀（Encoded Field Section Prefix）
每个编码字段部分都以两个整数为前缀。
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| Required Insert Count (8+) |
+---+---------------------------+
| S | Delta Base (7+) |
+---+---------------------------+
| Encoded Field Lines ...
+-------------------------------+ 所需插入计数标识处理编码字段部分所需的动态表的状态。 阻塞解码器使用所需插入计数来确定何时可以安全地处理其余字段部分。
复制 EncInsertCount = ReqInsertCount == 0 ? 0 : (ReqInsertCount mod (2 * MaxEntries)) + 1
# MaxEntries 为动态表可以拥有的最大条目数，最小的条目具有空名称和值字符串，大小为 32
MaxEntries = floor( MaxTableCapacity / 32 ) 解码器可以使用如下算法重建所需插入计数。
复制 FullRange = 2 * MaxEntries
if EncodedInsertCount == 0:
ReqInsertCount = 0
else:
if EncodedInsertCount > FullRange:
Error # QPACK_DECOMPRESSION_FAILED
# TotalNumberOfInserts is the total number of inserts into the decoder's dynamic table.
MaxValue = TotalNumberOfInserts + MaxEntries
# MaxWrapped is the largest possible value of
# ReqInsertCount that is 0 mod 2 * MaxEntries
MaxWrapped = floor(MaxValue / FullRange) * FullRange
ReqInsertCount = MaxWrapped + EncodedInsertCount - 1
# If ReqInsertCount exceeds MaxValue, the Encoder's value
# must have wrapped one fewer time
if ReqInsertCount > MaxValue:
if ReqInsertCount <= FullRange:
Error # QPACK_DECOMPRESSION_FAILED
ReqInsertCount -= FullRange
# Value of 0 must be encoded as 0.
if ReqInsertCount == 0:
Error # QPACK_DECOMPRESSION_FAILED 例如，动态表 200 bytes, 解码器已接收到 10 个插入。 编码值 4 代表字段部分的所需插入计数为 15
复制 MaxEntries = floor( MaxTableCapacity / 32 ) = (200 / 32) = 6
FullRange = 2 * MaxEntries = 6 * 2 = 12
MaxValue = TotalNumberOfInserts + MaxEntries = 10 + 6 = 16
MaxWrapped = floor(MaxValue / FullRange) * FullRange = floor(16/12) * 12 = 12
ReqInsertCount = MaxWrapped + EncodedInsertCount - 1 = 12 + 4 - 1 = 15
# ReqInsertCount < MaxValue => ReqInsertCount = 15 Base 用于解析动态表中的引用，使用一位符号（上述结构中的 “S” 部分）和 Delta Base 值相对于所需插入计数对 Base 进行编码。
符号位为 0 表示 Base 大于或等于 Required Insert Count 的值； 解码器将 Delta Base 的值添加到所需插入计数以确定 Base 的值。
复制 if Sign == 0:
Base = ReqInsertCount + DeltaBase
else:
Base = ReqInsertCount - DeltaBase - 1 Base 的值不能为负。如果所需插入计数的值小于或等于 Delta Base 的值，端点必须将符号位为 1 的字段块视为无效。
索引字段行（Indexed Field Line）
索引字段行表示标识静态表中的条目或动态表中绝对索引小于 Base 值的条目。
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | T | Index (6+) |
+---+---+-----------------------+ 带名称索引的文字字段行（Literal Field Line with Name Reference）
具有名称引用表示的文字字段行对字段行进行编码，其中字段名称与静态表中条目的字段名称或动态表中绝对索引小于 Base 值的条目的字段名称匹配。
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | N | T |Name Index (4+)|
+---+---+---+---+---------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+ "N”指示是否允许中间设备将此字段行添加到后续跃点上的动态表中。
“T”位指示引用是静态表还是动态表。 当 T=1 时，数字代表静态表索引；当 T=0 时，该数字是动态表中条目的相对索引
带有文字名称的文字字段行（Literal Field Line with Literal Name）
具有文字名称表示的文字字段行将字段名称和字段值编码为字符串文字。
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | N | H |NameLen(3+)|
+---+---+---+---+---+-----------+
| Name String (Length bytes) |
+---+---------------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+ 带后基索引的索引字段行（Indexed Field Line with Post-Base Index）
具有后基索引表示的索引字段行标识动态表中绝对索引大于或等于基值的条目。
带有后基名称索引的文字字段行（Literal Field Line with Post-Base Name Reference）
具有后基名称引用表示形式的文字字段行对字段行进行编码，其中字段名称与绝对索引大于或等于基值的动态表条目的字段名称相匹配。
复制 0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | N |NameIdx(3+)|
+---+---+---+---+---+-----------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+ "N”指示是否允许中间设备将此字段行添加到后续跃点（subsequent hops）上的动态表中。
潜在安全问题
使用压缩作为基于长度的预言来验证对压缩到共享压缩上下文中的秘密的猜测
参考
