用 Rust 从零开始写 QUIC：Reliability
理论相关
什么是 reliability
在 TCP RFC 里面，就很明确的说明了 TCP 的几个核心特点，其中之一就是 reliability。更具体的说，作为传输层会承诺将数据有序、准确且完整的发送给接收方，哪怕在网络环境不佳，可能出现丢包和乱序的情况下，这就是 reliability，这也是 TCP 相比较 UDP 来说，最大的区别之一。
TCP 如何实现 reliability
首先 TCP 需要知道，数据怎么算是被有序、准确并且完整的传输到了对端。众所周知，TCP 在自己的报文头中专门设置了 Sequence Number 和 Acknowledgment Number 字段，接收方会根据 Sequence Number 来处理数据，确保数据按着发送顺序抛给更上层协议处理，同时会使用 Acknowledgment Number 记录当前接收数据序列号从头开始连续区间数据的最大 Sequence Number 值，返回给发送方。
接下来的任务就交给了发送方，发送方需要根据接收方返回数据包中的 Acknowledgment Number 字段，来判断已经发送的数据中，到底有哪些数据是已经被对端确认了，有哪些没有被确认，需要被再次重传。而出于传输效率因素的考虑，发送方重传的频率和选择是需要被限制的，在判断没有被确认数据包是否需要重传的过程，一般被叫做丢包检测。
基于以上的策略，TCP 就完成了 reliability 能力的实现。但是这里其实有非常多的细节没有提及，除了丢包检测的各种细节以外，甚至接收方回应 ack 的策略也有非常多的细节，比如回应 ack 的时机，在接收方不需要发送数据的情况下，什么时候需要立即回应，什么时候需要延迟回应。简单举个例子就是很多人喜欢在网络编程时候主动关闭掉 TCP Nagle 算法，就是典型的为了传输效率，选择了延迟回应。
丢包检测机制
其实我一直理解 TCP 的丢包检测机制主要依赖两个机制，一个是发送方接收到数据回应时的丢包判断（判断是否需要立即重传），另外一个是发送方迟迟没有接收到回应后的超时重传。
第一个机制，最广为人知的，就是快速重传和快速恢复机制，即发送方连续收到 3 个重复的 ack 时，就需要快速重传没有被确认的数据，这个 RFC 5681 给出了详细的指导。当然这里依然还有很多细节，比如说究竟重传哪些数据，以及为了传输效率，拥塞窗口应该怎么变化等等。
第二个机制超时重传，其实就是一个兜底机制，当发送方超过多长时间没有收到数据确认，那么就会主动重传未被确认的数据，这里的超时时间，就是我们熟悉的 retransmission timeout，即 RTO。接下来就是聊怎么计算 RTO 了，这也是超时重传的核心。RTO 是和 RTT 密切相关的，换而言之 RTO 是依赖 RTT 计算出来的。那什么是 RTT 呢？RTT (round trip time) 就是当前网络通道返回一次的实时耗时，从 RTT 的定义，我们就可以知道 RTT 是可以反映出网络通道的实时状态的，这也是为什么 RTO 需要依赖 RTT 来计算出来。根据 RFC 6298，RTO 默认值为 1s，计算公式是 RTO = SRTT + 4 × RTTVAR，其中 SRTT 是 RTT 的平滑估计，RTTVAR 是 RTT 的偏差。
最后的话，在下面 QUIC reliability 实现的介绍中，会详细介绍下如何统计 RTT 的细节，毕竟在这块 QUIC 吸取了 TCP 的经验教训，有着很大的进步。在绝大部分场景下，第一个机制比第二个机制会更容易触发，毕竟超时重传中，RTO 的时间相对会更长一些，更偏向于是一个兜底的机制。
TCP 在 reliability 上面的演进
换而言之就是 TCP reliability 实现有哪些缺陷，毕竟 TCP 是一个出现非常早的协议。我第一个想到的就是 Acknowledgment Number 字段其实携带的信息量是远远不够的，这个很容易理解，Acknowledgment Number 只能表达是接收方累积接收连续数据的最大值，如果接收数据有空洞，后续数据即使已经接收到了，接收方也无法告知发送方，这样的话，发送方不得不重传所有未被确认的数据包，这样会影响传输效率。
这也是为什么会有 Selective Acknowledgment (SACK)，
SACK 是一个通过 TCP option 协商出来的一个增强功能，在 TCP payload 上面按照约定格式，携带除了 Acknowledgment Number 之前的数据，接收方还接收到了哪些数据，可以帮助发送方更精准的发送没有被确认的数据。顺便这里还想提一下 Negative Acknowledgment (NACK)，不同于 SACK， NACK 表达的是接收方有哪些数据没有收到，换而言之是接收方要求发送方补发哪些数据。我第一次接触到 NACK 还是在 WebRTC 里面，不过致力于实时通信的领域，采用 NACK 的策略更为正常，因为很多时候音视频通信中，是不需要确保每一个数据包都能抵达接收方的，只需要特定的关键数据确保传输。当然按我的理解， TCP 作为一个通用的传输层协议，是没有支持 NACK 这种更激进的策略。
另外就是 Recent Acknowledgment (RACK) ，需要澄清的一点是，RACK 并不像 SACK 或者 NACK 那样，是对数据确认信息的补充，RACK 是对快速重传和快速恢复机制的补充。因为快速重传机制也存在一定的缺陷，更具体的说，快速重传机制要求连续收到三个重复的 ack 之后，才判断出现丢包，这样的话，在高延迟的网络环境下，丢包检查的效率非常低，另外在乱序频繁网络环境，重复的 ack 并不一定代表丢包，可能出现误判。
针对这样的情况，RACK 引入了时间因素来辅助帮忙判断是否发生了丢包，而不是仅仅依赖重复 ack 的数量。具体的说，RACK 会记录每个已经发送数据包的发送时间，然后每次收到数据包后，都会找到出已经被确认的数据包中最大的发送时间，拿这个最大发送时间去依次和没有被确认的数据包发送时间比较，如果差值大于某个时间阈值，那么就判断没被确认的数据包算是丢失了，需要重新发送。这里 RACK 可以有效的提升丢包判断的效率，如果只是单个数据包丢失，RACK 配合着 SACK 可以更快的检测出单个数据包丢失了，而不是傻傻的等待对端重复 ACK 三次。
最后的话，超时重传机制的缺陷就是有一点慢，特别是在尾部丢包的场景中，会比较影响性能。什么是尾部丢包，其实就是发送方发了一段数据后，暂时没有数据要发送，而最后被发送的最后几个数据包丢失了。按照 TCP 原有的实现，因为已经没有了发送方数据包的驱动，接收方很难通过数据响应的方式，让发送方根据 ACK 的信息，来判断数据包丢失，所以最后只能走到超时重传的兜底，往往超时重传时间会相对较长一些。
针对这么一个场景，Tail Loss Probe (TLP) 提供了一种解决方案，即每次数据发送完之后，都会启动一个 TLP 的定时器，如果数据迟迟没有被确认，那么就启动这个定时器，让发送方主动发送一个探测包，这个定时器的时间，我们在这里称之为 Probe Timeout (PTO)，PTO 的计算公式是 smoothed_rtt + max(4*rttvar, kGranularity) + max_ack_delay 。相比较 Retransmission Timeout (RTO) 来说，PTO 虽然计算方式相似，但因为 PTO 可以在多个数据包触发超时的情况下发送多个探测包，同时 PTO 对拥塞窗口的影响比起 RTO 来说会更小，所以在现代的网络环境下（比如乱序和丢包更常见的无线网络下）， PTO 恢复起来会比 RTO 更有效率。
QUIC 在实现 reliability 和 TCP 的区别
前面说了这么多，都是为了帮助理解 QUIC 的 reliability 实现，虽然说 QUIC 在 reliability 的实现上，和 TCP 有很多相似之处，毕竟都是传输层协议，并且都是想完成同样的事情。但是 QUIC 因为像之前说的那样，没有历史包袱，可以吸收 TCP 在设计上的经验教训，所以 QUIC 实现中有很多和 TCP 不一样的地方。
RTT 计算
在上面提及的 RTO 还是 PTO，又或者是 RACK 中的时间阈值，都是依赖 RTT 计算出来的，毕竟 RTT 能够实时反应出网络链路的真实情况。那么对于 RTT 的精准计算就至关重要。但是还是因为 TCP 的缺陷，Sequence Number 和 Acknowledgment Number 字段能够携带的信息量太少，在 TCP 协议中，想要准确计算出 RTT，可以说是千难万难。其中面临最蛋疼的问题，就是重传数据和之前已发送的数据一样，也是使用相同的 Sequence Number。这意味着发送方很难计算 RTT，毕竟对端确认了我已经发送的数据包，但是这被确认了的数据包，究竟是首次发送的数据包，还是我重发的数据包，这没人知道。在这个问题上，TCP 有非常多的 RTT 统计算法，但是没有哪个算法是完美的。
而 QUIC 就不一样了，QUIC 解决这个问题的方法很简单，确保 QUIC 的 packet number 是永远自增的，那么每次 QUIC 的数据包被确认，那一定确认的是之前唯一被发送的那个，永远是一一对应的。这里，肯定有人问，如果 QUIC packet number 一直递增，那么 QUIC 传输的数据，怎么确保是有序的。QUIC 这里其实是使用了额外的字段去维护传输数据的顺序，比如说 QUIC Crypto frame 和 QUIC Stream frame 中的 offset 字段，就是专门来确保不同数据流的传输都是有序的。这其实就反应了 TCP Sequence Number 的本质问题，实际上是把 TCP 报文序号和 TCP 数据序列号都耦合在了一起，信令通道和数据通道一把抓了。
除此之外，QUIC 考虑到接收方可能存在延迟确认的情况，在设计 ACK frame 的时候，特别加了 ACK Delay 字段，让接收方主动告知应用层额外的响应延迟。这样的话，RTT 的统计准确性还要再上一层楼。
SACK 实现
QUIC ACK frame 中的 ranges 字段设计，更多是参考了 SACK 算法的实现。ranges 携带了 QUIC 接收方收到的数据包号区间。但是相比较 SACK 只能告知三个区间的限制（话说我第一次知道 TCP SACK 最多只能携带三个区间，这点咋够），QUIC ACK ranges 的支持区间个数要多得多。另外还有就是 SACK 是支持 Reneging 的，也就是意味着 SACK 确认的区间不一定准，SACK 可以回撤之前确认的区间，发送方需要再次重发。
这个 SACK Reneging 的设计，我也是第一次接触，有点震惊，如果是这样，那发送方不就是被耍了吗，实现上逻辑也会复杂不少。我很好奇这么设计的原因，仔细研究了下 RFC 2018，看起来原因是担心接收方的缓冲区空间不足，所以才让接收方可以丢弃这种优先级不高的数据，然后反悔 SACK 已经确认的区间。嗯，我虽然觉得这种情况下，不如让 flow control 来介入，另外接收方内存宝贵，那发送方的内存就不值钱吗？但是我觉得大佬当年这么设计肯定是有道理的，可能接收方存在的安全隐患更值得重视一些。最后，感谢 QUIC 这种直接禁止掉 Reneging 的行为，让我在实现的时候简单好多。
只使用 PTO 定时器
上面说到，在针对尾部丢包的场景，TCP 引入了 TLP 的机制。QUIC 协议为了更加简化实现，将使用 PTO 定时器来替换掉原来的 TLP 定时器和 RTO 定时器。除了实现简单的好处以外，PTO 定时器可以比 RTO 定时器更激进一些，这意味着效率更高。因为上文说过的，PTO 定时器只是发探测包，代价更小。所以 PTO 定时器不仅能处理好尾部丢包的场景，更能成为丢包探测的兜底机制，让协议在出现丢包的情况下，快速的进入丢包探测的状态，从而更快的重传恢复。
编码实现细节
聊完理论基础，我想把这个功能拆分为几个核心问题，把核心问题处理好，那功能的实现就水到渠成了。
怎么处理接收方的响应
这里本质上是要做两件事情，一个是利用接收方响应包的 Packet Number 来维护自己生成 ACK Frame 的依赖信息，另外就是如果对方回应中携带 ACK Frame 的话，我们也需要更新我们已发送队列以及进行丢包检测。
怎么处理 QUIC Packet Number 更新
首先是怎么处理 QUIC Packet Number，之所以处理 QUIC Packet Number，这是因为 QUIC 是全双工的传输协议，所以做为发送方，也需要维护相关信息来组装 ACK Frame 来回应对端。接下来，我们看一下 QUIC ACK Frame 究竟携带了哪些信息，一种是 ACK Delay，即提升我们统计计算 RTT 的精度，另外一种就是类似 SACK 接收到哪些数据包的序列号确认区间。
其中，后一种是我们需要不断通过处理对方发送过来的 QUIC Packet Number 来维护的核心信息。这里，我不太想描述太多 ACK Frame 是如何组织描述这些确认接收数据包序列号区间的，因为这些在 QUIC RFC都描述的非常清晰。核心是，我们怎么去维护构建响应 ACK Frame 的信息。
在实时维护构建响应 ACK Frame 的信息，本质上就是在维护我们已经接收到数据包的序列号区间。所以，我们接收到一个新的 QUIC packet 之后，我们会拿 QUIC Packet Number 去和现有的序列号区间进行比对更新。举个简单的例子，当前维护的接收数据包的序列号区间是 [3, 5], [8, 9], 如果接收到的数据包序列号是 7，那么序列号区间就应该被更新为 [3, 5], [7, 9]，这里无非是对序列号区间的增加、合并和修改。
这里，我想讨论一个特殊情况，即如果区间个数大小超过限制了怎么办，首先 QUIC 没有明确对区间个数大小做出限制（如果说有上限，也是一个单独 ACK Frame 必须要被一个 QUIC Packet 所能容纳，即不要超过 MTU），但是作为实现方，我们肯定需要有一个上限，我这边简单设置了上限为 18。接下来，就是如果发现维护的区间个数超出上限，我会看引发新增区间的 packet number 是最新的数据包，还是老的数据包。如果是最新的数据包，那么就自动淘汰老的确认区间，因为新的确认区间对于网络性能更重要，老的确认区间就依赖对端的重传机制来兜底。如果是很老的数据包，我会单独保存起来，并且立即返回一个单独里 ACK frame 来通知对端已经确认，不影响现有确认区间的维护。
什么时候回应 ACK frame
在接收方更新完本方的 ACK Frame 的构造依赖信息之后，还有一个非常关键的事情需要决定，就是 ACK frame 什么时候回应对端。这个其实就是 ACK 回应频率。ACK 的响应频率其实会影响着传输性能，比如说丢包检查算法一般都是依赖 ACK Frame 的情况进行判断，所以频率太低了（即延迟响应）肯定会影响性能。同时，如果太多 ACK Frame 的发送，也会影响传输性能，这个也很容易理解。
所以 QUIC RFC 中建议我们：接收方在收到至少两个引发 ACK 的数据包之后，再立即发送 ACK 响应。如果接收方判断不需要立即回应 ACK，那么也需要确保在握手协商的本端 MAX ACK Delay 时间范围内把 ACK 响应发送出去，同时使用 ACK frame 中的 ACK Delay 字段提示对端。当然这里存在一些特殊情况，比如说为了提升握手的性能，如果是握手阶段的 ACK 响应，需要及时回应。另外如果出现了乱序的数据包，那么也需要立即回应 ACK，来确保传输质量。
怎么处理 ACK frame
当收到 ACK Frame 的时候，接收方主要会去做以下几项工作。第一件事，理所应当去遍历整个已发送队列，查看究竟有哪些 QUIC Frame 是被确认了。这里需要特别注意的是，根据 QUIC Frame 的类型不同，我们需要有不同的处理方式。比如像 Crypto 和 Stream Frame 被确认了，我们需要去做的事情就不大一样，因为 Crypto 握手的发送数据完全由 QUIC 协议栈接管，所以其实只要销毁掉对应的已发送数据即可。但是 Stream Frame 的设计中，有 QUIC Stream 状态的管理，另外如果 QUIC Stream 发送队列是满了，然后因为被对端确认而腾出了空间，QUIC 协议栈还要通知上层出现了可写事件。
而 QUIC ACK Frame 也需要特别的处理，因为我们刚才一直在说对自身 ACK Frame 的构造信息的维护，但是没说什么时候需要去清理这些构造信息。其实当已发送的 ACK frame 被对端确认之后，就是一个清理的良机。QUIC RFC 特别提到了，可以将被确认的 ACK Frame 中 Largest_acked 之前的区间统统清理掉。这个操作我很喜欢，因为减少了很多实现的复杂度。
第二件事情，当然是触发我们的 RTT 估算流程了，不过 QUIC RFC 额外做了一些要求，比如 Largest_acked 信息必须被更新，以及 ACK Frame 确认的 QUIC 数据包中必须要有 ACK 引发 frame。这些要求，我理解都是为了确保 RTT 统计的准确性而设置的。最后一件事情，就是实现丢包检测了，不过这个我想放在下面细说。
如何发送数据
什么时候进行重传
一句话描述，丢包探测决定了什么时候重传，PTO 定时器可以提升丢包探测效率。丢包探测在什么时候执行，这个问题，上面刚刚讨论过，就是收到 ACK Frame 的时候，就会进行丢包检测。至于什么算是丢包，QUIC RFC 融合了上文提及的 RACK，基于 ACK 响应，从时间和频率两个维度来判断是否发生了丢包。这里稍微需要注意的是，基于时间阈值的判断，如果没有发现有丢包发生，是会设置一个定时器，是当前已发送数据中最接近当前时间的阈值，如果定时器触发，再去处理丢包事件。
再回到 PTO 定时器，那 PTO 定时器通过发送 ACK 引发包，来触发 ACK Frame 的响应，来加速丢包探测。这里也有几个需要特别注意的地方，首先我们知道 PTO 定时器的超时时间是基于 RTT 计算出来的，但是这个超时时间一般会大于 QUIC 丢包探测定时器的时间，这同时也意味着 PTO 定时器的代价其实也很大，一旦 PTO 定时器触发之后，我们需要多做一些事情。
比如说，QUIC RFC 推荐我们尽量跳变 PTO 探测包的 Packet Number，来触发对端及时响应 ACK，而不是延迟响应 ACK。这里比较有意思的是，QUIC 是支持 Packet Number 跳变的，这样做还可以尽可能的规避流量被人嗅探，并且仔细想，QUIC packet number 略微跳变，也不会影响 reliability 功能的正常运行。但是我们这里，还是使用连续发送两个 PTO 探测包，来确保对端及时响应 ACK，因为一般对端收到两个 ACK 触发包就会立刻响应 ACK，这样做恢复起来会比序列号跳变更有效率，毕竟多发送了数据包。
最后，PTO 探测包具体是什么，在不同的情况下，也有不同的答案。正常的话，在没有数据要发送的情况下，PTO 探测包是 Ping frame。如果是握手阶段的话，一般 PTO 探测包是握手包，比如 Crypto frame 之类的，这样的话，可以加速握手完成。但是我看了下作为 server 的 NGNIX QUIC 实现，我发现 NGINX PTO 探测包在握手阶段也是发送 Ping frame 作为探测帧，这里可能出于是对服务端资源保护的考虑。在有数据要发送的情况下，PTO 的探测包往往是 Stream frame 或者 Crypto frame 这种。
重传的优先级
正常的话，重传的数据量是要受到拥塞窗口和 flow control 的控制，当然这些我还没实现，所以可以先不考虑。剩下的就是，我们要重传哪些数据了。这里，不管是为了网络传输性能快速恢复，还是为了帮助接收方回收内存，都是应该先发送重传数据，然后再发送新的数据。稍微需要注意的是，我们 packet number 是持续递增的。
测试
我在写完这个 reliability 功能之后，最大的感受就是我之前写了好多 bug。果然和我想的一样，开坑一个新项目不难，难的是怎么确保新项目的质量。我这里遇到一个比较大的问题，就是由于 QUIC 协议栈基础功能还没有完成，我没办法添加一些自动化测试来保证质量。甚至在这次 reliability 的实现中，我也没办法测试到实现的所有细节，毕竟我现在连基础的收发数据能力还不具备。只能临时靠测试用例来覆盖一些我担心的场景。除了测试用例，我还打算后面使用模糊测试，来提升 feather-quic 的鲁棒性，确保只在无法恢复的情况下抛异常，能够按照符合 QUIC 协议设计的方式，来正确处理各种异常情况。
在我完成基础功能之后，我会考虑使用 quic-interop-runner 来进行 QUIC 协议栈的测试，在后续基础能力保证稳定之后，我会再考虑性能方面的测试和优化。最后，我觉得代码数量有点多，也得想办法精简一下。还有整个项目的 crate 结构还得再调整一下。
尾声
读到这里，想必大家也都能看出来，我对传输协议的 QOS 不是很在行，其实在动手实现 QUIC reliability 之前，我只知道 TCP 的快速重传以及超时重传，当然也了解一点 SACK 和 NACK。还是 QUIC 协议引入了很多新的机制，让我在实现过程中，学到了很多，比如了解到了 TCP RACK-TLP 的优化，以及 QUIC 很多优化的细节。
还有我本来打算 1 月份就更新的博客，结果一直偷懒，拖到了 3 月份。其实有点想鸽掉这个小项目，但是有同事跟我说，看到我的博客觉得写的不错，不管怎么样我都当真了😂。虽然里面有很多错误（不管是理论认知上的，还是代码层面上的），但是有时候这个项目写起来还挺有意思的。最后惯例放一下 PR 地址，还有下一个功能，我准备实现 QUIC 数据传输的能力，即支持 QUIC Stream。