KCP 1.4源码分析

KCP是基于UDP协议之上的ARQ协议实现。TCP虽然使用的更广泛，但是在某些实时性要求更高的领域（如实时音视频、即时在线游戏等），会更倾向于使用基于UDP的可靠传输协议。

在项目的官网上，对KCP是这么介绍的：

KCP是一个快速可靠协议，能以比 TCP 浪费 10%-20% 的带宽的代价，换取平均延迟降低 30%-40%，且最大延迟降低三倍的传输效果。纯算法实现，并不负责底层协议（如UDP）的收发，需要使用者自己定义下层数据包的发送方式，以 callback的方式提供给 KCP。 连时钟都需要外部传递进来，内部不会有任何一次系统调用。

UDP并不是一个可靠的传输协议，如果数据没有发送成功并不会自动重传，KCP基于UDP协议之上实现了自己的ARQ协议，所以在继续介绍KCP协议之前，先大体了解一下ARQ协议。

ARQ的两种模式

KCP在UDP之上，自己实现了可靠性的算法，即给UDP加上了诸如超时重传、流量控制等机制，这些都是为了保证ARQ协议的运作。

ARQ协议(Automatic Repeat-reQuest)，即自动重传请求，是传输层的错误纠正协议之一，它通过使用确认和超时两个机制，在不可靠的网络上实现可靠的信息传输。

ARQ的实现通常有如下两种模式。

停等ARQ协议（stop-and-wait）

停等ARQ协议，意味着每个数据在发送出去之后，在没有收到对端的接收回复之前，将一直等待下去，而不会继续发送新的数据包。如果超时还未收到应答，就会自动重传数据包，以保证数据的可靠性。

下图是两种情况下停等协议的示意图：

• 上图：正常不出错情况下运行的停等协议，消息2必须在发送方收到了消息1的对端确认回复之后才能发送出去。
• 下图：出错情况下运行的停等协议，发送方发现消息1超时还未收到应答，就触发了针对消息1的重传机制。在这之前消息2都不会被发出去。

协议栈如何确认这个“超时时间”呢？答案是根据数据往返时间动态估算出来的RTO（Retransmission TimeOut，重传超时时间）时间来确认的。

连续ARQ协议（Continuous ARQ）

可以看到，停等协议的机制是“一应一答”式的，对带宽的利用率不高，传输效率不高。

连续ARQ协议，可以一次性发送多个数据，而不必像停等协议那样需要等待上一个数据包的确认回复才能继续发送数据。

在使用连续ARQ协议的时候，接收方也并不会针对每一个收到的数据包进行确认应答，而只需应答确认最大的那个数据包，这时就认为在此之前的数据包都收到了。

这种模式称为“UNA（unacknowledge，即第一个未应答数据包的序列号，小于该序列号的数据包都已经确认被接收到）”模式，与之对应的是，停等协议是ACK模式。

然而，即便是可以一次发送多个数据包，也不意味着可以不受控制的发送数据，因为还要受到几种流量窗口的限制，这部分被称为“流量控制”。

拥塞窗口更多是对网络上经过的网络设备总体网络情况的一个预估。因为在真正发送数据时，并不清楚这时候的网络情况，因此启动时拥塞窗口会有一个初始值，然后根据以下几种算法进行动态的调整：

• 慢启动：在启动时让拥塞窗口缓慢扩张。
• 退半避让：在发生网络拥堵时让拥塞窗口大小减半。
• 快重传：在网络恢复时尽快的将数据发送出去。

拥塞窗口是对外部网络情况的一种动态的检测，而滑动窗口则是进程本身接收缓冲区的控制，滑动窗口就是接收方用来通知发送方本方接收缓冲区大小的。由于一个网络进程分为协议层和应用层，如果协议层接收数据很快，但是应用层消费数据很慢，这个滑动窗口就会缩小，通过这种方式来通知对端放缓数据的发送，因为接收方已经忙不过来了。

KCP作为一个ARQ协议，内部就是要实现对以上这些机制的支持。

如果对TCP协议的实现有一些了解，可以看到上述的对端确认回复、超时重传、拥塞窗口、滑动窗口等概念，在TCP中就有，KCP自己实现的ARQ机制，与TCP对比起来有如下的不同点：

• 在TCP中，超时之后的RTO时间直接翻倍（即RTO*2），而在KCP启用了快速模式之后，RTO的超时时间是*1.5，避免RTO时间的快速增长。
• TCP协议在丢包时会直接重传丢的那个包之后的所有数据包，KCP只会选择性的重传真正丢失的数据包。
• TCP为了充分利用带宽，会延迟发送ACK应答对端，这样会导致计算出来的RTT时间过大，KCP的ACK是否延迟发送则可以调节。
• KCP 正常模式同 TCP 一样使用公平退让法则，即发送窗口大小由：发送缓存大小、接收端剩余接收缓存大小、丢包退让及慢启动这四要素决定。但传送及时性要求很高的小数据时，可选择通过配置跳过后两步，仅用前两项来控制发送频率。

本文基于KCP 1.4版本对其实现做分析。

在展开讨论之前，首先介绍相关的术语概念。

• ARQ：Automatic Repeat-reQuest，自动重传请求协议。KCP就是其中一种ARQ协议的实现。
• MTU：Maximum Transmission Unit，最大传输单元，链路层规定的每一帧最大长度，通常为1500字节。
• MSS：Maximum Segment Size，最大分段大小。通常为MTU-协议头大小。
• RTT：Round-Trip Time，数据往返时间，即发出消息到接收到对端消息应答之间的时间差。
• RTO：Retransmission TimeOut，重传超时时间，根据收集到的RTT时间估算。
• rwnd：Receive Window，接收窗口大小，接收端通过该数据通知发送端本方接收窗口大小。
• cwnd：Congestion Window，拥塞窗口大小，影响发送方发送数据大小。
• ack：acknowledge，接收端接收到一个数据包之后，通过应答该数据包序列号来通知发送端接收成功。
• una：unacknowledge，即第一个未应答数据包的序列号，小于该序列号的数据包都已经确认被接收到。
• ssthresh：Slow Start threshold，慢启动阈值，用于在发生拥塞的情况下控制窗口的增长速度。

每个KCP数据报文，其定义如下，注释中描述了每个字段的含义：

在这里，挑其中几个重点的字段来展开说说，其他的字段已经在上面的注释中有描述。

• conv：该字段是会话编号，由于UDP协议不是基于链接的，因此通信的双方需要会话编号一致才能进行通信。

• cmd：指令类型，具体有以下这几种：

  • IKCP_CMD_PUSH：传送数据。
  • IKCP_CMD_ACK：应答接收到数据包。
  • IKCP_CMD_WASK：探测接收端接收窗口大小。
  • IKCP_CMD_WINS：通知接收窗口大小。
• frg：分片编号，当发送的数据超过MTU大小时，就会将数据分片来发送，该字段就是用来存储分片编号，值从大到小，比如有4个分片，则从第一块分片到第四块分片的报文，该字段依次为3、2、1、0。
• fastack：用于快速重传的字段，具体的使用在后面展开详细的讨论。

需要说明的是，以上只是报文在内存中的表示，当写入报文时报文的头部数据如下（由于KCP文档中有这部分的图示就直接引用了）：

KCP结构体

除了上面定义每个报文的结构体之外，kcp协议栈还有一个负责记录kcp协议栈信息的结构体IKCPCB。

其定义及成员的注释如下：

kcp库对外的接口中，首先需要调用ikcp_create函数创建该结构体，才能继续后面的工作。

从上面定义的数据结构中，还看到了其中有队列指针，不难想象每个报文数据都是某种队列中的元素，确实也是这样，在KCP中定义了以下几个和报文相关的队列：

• snd_queue、nsnd_que：发送队列以及其大小。
• snd_buf、nsnd_buf：发送缓冲区及其大小。
• rcv_queue、nrcv_que：接收队列以及其大小。
• rcv_buf、nrcv_buf：接收缓冲区及其大小。

为什么发送和接收两端，既有缓冲区又有队列？在KCP中，队列是应用层可以直接进行读写的区域，而缓冲区则是KCP协议层接收和发送数据的区域了，如图所示：

在发送报文时，用户层调用ikcp_send函数，该函数最终会分配报文结构体指针，然后添加到发送队列snd_queue的末尾；而在KCP协议栈真正调用系统接口发送数据出去的时候，将从snd_queue队列中将报文取出，放入snd_buf缓冲区中再进行发送。接收报文的流程反之，这里就不再阐述了。

了解了相关的数据结构，这里开始分析核心流程。先来看看整体的框架。

KCP的实现中，把两个部分留给应用层来做：

• 具体收发数据的流程，通过将ikcp_setoutput函数留给应用层注册来进行数据发送，KCP自己并不负责这一块。
• 何时驱动KCP进行数据的收发，即KCP内部并没有实现一个定时器，定期检查条件来触发收发流程，而是提供了ikcp_update函数给应用层，通过该函数来驱动KCP协议栈的运作。

除此以外，KCP提供另外几个函数的作用如下：

• ikcp_input：当应用层接收到数据时，通过该函数通知KCP协议栈对接收到的数据进行解析，最终会生成报文存储到前面提到的接收队列rcv_queue中。
• ikcp_recv：上一步调用ikcp_input函数完成对接收到的报文的解析之后，ikcp_recv函数将解析完成的报文重新拼装到buffer中返回给用户层。
• ikcp_send：用户层发送数据，最终会将待发送的数据编码成一个个的KCP报文存入snd_queue中。
• ikcp_update：用户层调用该函数，来驱动KCP协议栈进行具体的协议收发、拥塞控制等流程，这些流程实际最终由函数ikcp_flush完成，但是用户层并不会直接调用这个函数。

整个流程中涉及到的函数及流程如下图：

（出自：KCP 协议与源码分析（一）_老雍的博客-CSDN博客_kcp）

在这里先对上图做简单的解释，下面再展开详细的分析：

• 图中中轴的函数是ikcp_create，负责创建kcp协议栈结构体指针；而真正需要发送数据时，需要用户层自己调用ikcp_update函数驱动kcp协议栈工作。
• 图的左边是用户层与协议栈的交互。用户调用ikcp_send函数，将用户缓冲区的数据，根据KCP协议拼装成报文放到发送队列snd_queue中。而当用户需要从协议栈接收数据时，会调用ikcp_recv函数，该函数会将在接收队列recv_queue中的报文反序列化成用户层缓冲数据，返回给应用层。
• 图的右边是协议栈与网络之间的交互。首先ikcp_flush函数，会将发送队列snd_queue中的报文移动到发送缓冲区中，最终调用用户通过ikcp_output函数注册发送函数发送出去；同时，当收到网络层的数据时，会调用ikcp_input函数将这些数据以kcp协议的形式解析出来，放入到接收缓冲区snd_buf中。

以下对其中的核心流程做分析。

ikcp_input函数

ikcp_input函数是用户层接收到数据时调用的第一个函数，其传入的参数是收到数据的缓冲区。因为用户层接收到的数据，都没有经过KCP协议的解析，所以首先调用ikcp_input函数进行协议解析。又由于一个报文中可能存在多个KCP协议包，所以会遍历这个用户层数据缓冲区进行多次的KCP协议解析。KCP协议，按照其包头中带的指令类型，可能有以下几种：

IKCP_CMD_ACK

对端应答ack报。处理流程如下：

• 调用ikcp_update_ack函数更新RTT估算值。
• 由于收到了对端的ack，所以调用ikcp_parse_ack函数，遍历当前的发送缓冲区snd_buf删除对应该应答序列号的报文，因为该报文对端已经应答收到了，不需要再重发了。
• 调用ikcp_shrink_buf函数更新snd_una。
• 快速重传逻辑的处理，这部分在函数ikcp_parse_fastack中。

ikcp_update_ack函数用于更新RTT相关的估算值，包括：

• rx_rttval：rtt平均值，为最近4次rtt的平均值。
• rx_srtt：ack接收rtt平滑值为最近8次的平均值。
• rx_minrto：最小RTO，系统启动时配置，在nodelay的情况下值为IKCP_RTO_NDL，否则就是IKCP_RTO_MIN。

• rx_rto：估算出来的rto值，为平滑值+max（interval，平均值），在[rx_minrto,IKCP_RTO_MAX]之间。

  static void ikcp_update_ack(ikcpcb *kcp, IINT32 rtt)
  IINT32 rto = 0;
  if (kcp->rx_srtt == 0) { // 当前没有rtt加权平均值
  // 以这次RTT值来设置
  kcp->rx_srtt = rtt;
  // 平均值要除以2
  kcp->rx_rttval = rtt / 2;
  } else {
  // 计算两者之差
  long delta = rtt - kcp->rx_srtt;
  if (delta < 0) delta = -delta;
  // 算平均值，可以看到平均值是最近4次的平均
  kcp->rx_rttval = (3 * kcp->rx_rttval + delta) / 4;
  // 算加权值，加权值是最近8次加权值的平均
  kcp->rx_srtt = (7 * kcp->rx_srtt + rtt) / 8;
  // 不能小于1
  if (kcp->rx_srtt < 1) kcp->rx_srtt = 1;
  // 计算RTO值：平滑值+max（interval，平均值）
  rto = kcp->rx_srtt + _imax_(kcp->interval, 4 * kcp->rx_rttval);
  // 最终在[rx_minrto,IKCP_RTO_MAX]之间
  kcp->rx_rto = _ibound_(kcp->rx_minrto, rto, IKCP_RTO_MAX);

可见，以上流程最终要算出来当前KCP协议栈的rx_rto，这个值最终会影响每个报文的超时发送时间，这在后面的发送流程中再解释。

另外还需要专门聊一下ikcp_parse_fastack函数，以及快速重传的处理。快速重传的原理是这样的：假设当前有序列号[1,2,3]的报文等待对端应答，当KCP协议栈收到报文2的ack时，知道报文1被跳过1次了；同样的，当收到报文3的ack时，报文1又被跳过1次。

这里的“跳过次数”就存储在IKCPSEG.fastack成员中，KCP协议栈提供ikcp_nodelay函数可以配置快速重传值resend，当报文的跳过次数超过resend时，就马上重传该报文，不会等待报文超时，一定程度上加速报文的重传降低了延迟。

IKCP_CMD_PUSH

传送数据的指令，此时解析最终会进入ikcp_parse_data函数中，该函数流程如下：

• 首先会通过报文序列号判断是否在当前接收窗口以内（_itimediff(sn, kcp->rcv_nxt + kcp->rcv_wnd) >= 0），或者已经接收过了（_itimediff(sn, kcp->rcv_nxt) < 0），这两种情况都删除报文返回，不做进一步处理。
• 根据报文序列号在rcv_buf判断当前接收缓冲区中是否已经存在同序列号的报文，如果已经存在说明是重复接收的，也删除报文不再处理。
• 以上两步都通过了，说明是首次接收该序列号的报文，将把该报文放入接收缓冲区rcv_buf中。
• 由于rcv_queue中的报文才是最终面向用户层的，而上面的操作可能让rcv_buf接收缓冲区非空存在新的报文了，所以接下来将rcv_buf中的报文移动到rcv_queue中。

IKCP_CMD_WASK

对端请求探测窗口大小，此时会把探测标志位加上IKCP_ASK_TELL，下一次发送数据时带上窗口大小通知对端。

IKCP_CMD_WINS

通知窗口大小。

快速应答处理

前面的处理完毕之后，可能会收到新的ack报文，这时就需要更新KCP协议栈的拥塞窗口大小。

如果当前拥塞窗口大小小于对端的窗口大小（kcp->cwnd < kcp->rmt_wnd），那么需要增加拥塞窗口大小，区分两种情况：

• 如果拥塞窗口大小小于慢启动阈值（kcp->cwnd < kcp->ssthresh）：递增拥塞窗口大小。

• 否则：

  • 拥塞窗口增量递增1/16；
  • 如果当前拥塞窗口递增后小于增量的情况下才递增。

• 最后，拥塞窗口不能超过对端窗口大小。

  // 前面处理完毕之后，最新的una更大，说明接收到了新的ack
  if (_itimediff(kcp->snd_una, prev_una) > 0) {
  if (kcp->cwnd < kcp->rmt_wnd) { // 拥塞窗口小于对端窗口
  IUINT32 mss = kcp->mss;
  if (kcp->cwnd < kcp->ssthresh) { // 拥塞窗口小于慢启动阈值
  kcp->cwnd++; // 递增拥塞窗口
  kcp->incr += mss; // 递增mss
  } else { // 拥塞窗口大于等于慢启动阈值
  // 不能小于mss了
  if (kcp->incr < mss) kcp->incr = mss;
  // 增加 mss + 1/16 mss
  kcp->incr += (mss * mss) / kcp->incr + (mss / 16);
  // 只有在拥塞窗口递增后不超过incr的情况下才允许加一
  if ((kcp->cwnd + 1) * mss <= kcp->incr) {
  kcp->cwnd++;
  if (kcp->cwnd > kcp->rmt_wnd) { // 拥塞窗口不能比对端窗口大
  kcp->cwnd = kcp->rmt_wnd;
  kcp->incr = kcp->rmt_wnd * mss;

ikcp_recv函数

前面的ikcp_input解析完毕之后，将用户缓冲区的数据解析到一个一个的报文放到了接收队列rcv_queue中，ikcp_recv函数就负责将这些报文重新组装起来放入用户缓冲区返回给用户层。

之所以这里还需要“组装”，是因为对端发送的数据由于超过MTU所以被KCP协议栈分成多个报文发送了。所以这里需要兼容多个分片的情况，如果待接收报文的所有分片没有接收完毕，那么不能处理。接收完毕或者不分片的情况下，就遍历这些报文将数据拷贝到缓冲区中。

上面的步骤完成之后，如果接收缓冲区rcv_buf还有报文，那么依然是把这部分报文移动到接收队列中，等待下一次ikcp_recv调用。

ikcp_send

ikcp_send函数是用户层发送数据的接口，最终会将用户传入的缓冲区数据，组装成KCP报文，放入发送队列snd_queue中。

这里需要注意两种情况。

• 如果是流模式，那么首先KCP会取出发送队列当前的最后报文的结构体，如果当前报文还有空间就将部分数据拷贝过去。
• 如果数据超过MSS大小，那么需要对数据分片，即将数据分为多个KCP报文发送。

ikcp_update和ikcp_flush

前面的ikcp_send只是将待发送数据组装成KCP报文放到发送队列中了，具体的发送流程由调用ikcp_update函数来驱动完成的。

KCP协议栈中，并没有任何的自定义定时器，即自己并不会主动来根据时间驱动来完成工作，这部分都留给了用户层，由用户层主动调用ikcp_update来完成这些工作。ikcp_update函数的处理其实很简单，会判断上一次刷新（flush）时间与这次的间隔，来判断是否调用ikcp_flush函数来完成工作，所以这里真正工作的是ikcp_flush函数，下面就来重点分析这个函数的实现。

ikcp_flush函数本质就是根据当前的情况，封装KCP报文，将这些报文放到发送缓冲区snd_buf中，发送到对端。除此之外，还需要重新计算流控、拥塞窗口等参数。总体来看，需要完成以下的工作：

处理ACK应答

首先，ikcp_flush函数将编码IKCP_CMD_ACK类型的指令，应答收到了对端那些报文。

探测对端窗口

在对端通知窗口为0（即kcp->rmt_wnd == 0）情况下，需要探测对端当前窗口大小，即需要发送IKCP_ASK_SEND类型的报文。

在这里，涉及到KCP协议栈ikcpcb结构体的几个参数：

• probe_wait：存储下一次探测窗口的时间间隔，该参数的初始值为IKCP_PROBE_INIT，每次新的探测间隔时间将在当前基础上递增当前的1/2，但是最高不超过IKCP_PROBE_LIMIT。
• ts_probe：存储下一次探测时间，不难知道这个值每次都是根据当前时间加上probe_wait计算出来的。

在当前时间超过ts_probe（即_itimediff(kcp->current, kcp->ts_probe) >= 0）的情况下，probe探测标志位就要加上IKCP_ASK_SEND，表示需要给对端发送探测窗口的报文了。

以上已经处理了IKCP_CMD_ACK、IKCP_ASK_SEND、IKCP_ASK_TELL这三个类型的指令了，接下来就是处理IKCP_CMD_PUSH类型的数据了，这部分数据都已经在前面的ikcp_send由用户层传入的缓冲区解析拼装到发送队列snd_queue中了。

接下来，就可以遍历发送队列snd_queue中的报文移动到发送队列snd_buf中，进行实际的报文发送了。

但是，并不是所有当前在发送队列中的报文都能在一次flush过程被发送出去，要考虑三个窗口的大小：

• 首先不能超过发送窗口（snd_wnd）和对端窗口（rmt_wnd）的大小。
• 在开启流控（kcp->nocwnd == 0）的情况下，还不能超过当前流控窗口（cwnd）的大小。

前面的流程算出来发送时的窗口大小，接下来就按照这个窗口大小将snd_queue的报文取下来放入snd_buf中了。

以上已经根据流控窗口选出了待发送的报文放在发送缓冲区snd_buf里了，接下来就是具体的发送流程了。

针对每个报文，在发送之前要计算它的几个参数：

• xmit：发送次数，每发送一次该计数递增，如果一个报文的发送次数超过了dead_link，那么认为网络已经断了不再尝试发送。

• rto：用来计算重传超时时间的，初始值就是KCP协议栈当前估算出来的RTO值，在发生重传的情况下这个值会增加：

  • 在非急速模式下，每次递增的值也是KCP协议栈估算出来的RTO值。（segment->rto += kcp->rx_rto;）
  • 急速模式下，每次递增的值也是KCP协议栈估算出来的RTO值的二分之一。（segment->rto += kcp->rx_rto / 2）
• resendts：根据当前时间加上rto时间计算出来的下次重传时间。

来看看发送报文需要考虑的几种情况：

• 首次发送（segment->xmit == 0）：设置xmit为1，rto为kcp->rx_rto，以及重传时间为当前时间加上rto（segment->resendts = current + segment->rto + rtomin）。
• 因为超时发生的重传（_itimediff(current, segment->resendts) >= 0）：递增xmit计数值，增加rto时间，以及更新下次重传时间resendts，并且标记发生了丢包（lost=1）。
• 快速重传（segment->fastack >= resent）：前面已经分析过快速重传参数fastack的作用，这里就不再阐述了。

通过以上分析，可以知道除了第一种情况是正常发送之外，还发生了超时重传以及快速重传，根据这些情况，需要更新一下KCP协议栈的参数。

分以下两种情况处理：

在发生快速重传的情况下，会挑战ssthresh为当前发送窗口的一半大小，同时拥塞窗口为ssthresh + resent大小：

在发生超时丢包的情况下，慢启动阈值调整为旧的拥塞窗口的一半，但是不能小于IKCP_THRESH_MIN，而新的拥塞窗口值变成1：

• KCP: 快速可靠的ARQ协议 - Kaiyuan’s Blog | May the force be with me