udp可靠性传输设计之kcp

udp传输本身是不可靠的，要做到可靠性传输，需要参考tcp的原理在用户层进行修改，所以在可靠性设计之前，需要弄明白tcp传输的一些原理。

tcp可靠性传输

tcp传输有一些机制可以保证可靠性传输：
1、ack机制，对方收到消息后会回应ack，当然有几种回应的方式，第一种就是收到一条回复一条，发送方需要收到上一条消息的ack后才能继续发送下一条消息，这种效率比较低，另一种是，连续发送多条消息，只需要回应一个ack即可，ack里面有序列号，代表这个序号之前的消息都接收到了，这个序列号也叫una，如果接收到的消息为1-2-3-5-6，丢失了4，那4-5-6都需要被重传，还有一种回应ack的方式是除了给出una，还给出了acklist，如果接收到的消息为1-2-3-5-6，那una是4，acklist是5-6，这样就可以实现选择性重传，发送方只需要重传4即可。这其实也就是ARQ的三种协议，书面语叫停等式、回退n帧、选择性重传。
2、序号机制，发出的消息都是带有seq序号的，这个在tcp的包头里面有一个序列号的字段专门用来表示序列号。
3、重排机制，有了序列号，接收方在接到数据后就可以做出排序处理，因为数据并不一定是有序到达接收方的，如只到了1-2-4，那要等待3的数据到来再插入到3的位置，这样排序好的数据才能给应用层使用。
4、窗口机制，这个主要用来限制发送方的发送速率，如果接收方没有剩余窗口可以接收新的数据了，那么发送方就不能继续发送数据了，否则数据会丢失，发送方也会定期去询问接收方是否有新的窗口可以接收数据了，一旦有了，就可以继续发送，因为接收方recvbuf里面的数据被应用层处理后，就会被删除，这时就有更多的窗口空间了。

kcp的优势

为什么有了tcp，还要设计可靠性udp传输呢？主要是为了传输的实时性，tcp当初的设计初衷就是要最大化的利用好带宽，实时性是次要的，所以才有慢启动环节，因为在当初带宽显得更重要，而kcp则利用tcp的10%-20%的带宽换取其30%-40%的传输速度，主要哪些方面可以提升速度呢？
1、重传的时机更快，tcp在丢包后，分别在2RTO、4RTO、8RTO、16RTO重传，而kcp可以选择1.5被的时间进行增长，数据可以更快的传输出去。
2、延迟ack，tcp为了更好的利用带宽，对接收到的数据做了延迟ack的处理，这样可以少发ack包，但是如果有出现丢包的情况，则比较慢才能发现，kcp是可以选择是否延迟ack，这样实时性更高。
3、tcp可以快速重传，即在连续几次收到同一个ack后，说明数据有丢失，则这个ack序号后面的数据都要重传，如果要做到选择性重传，需要发送方接收方都开启tcp_sack参数，而kcp由于是una＋ack机制，可以支持选择性重传，也支持快速重传。
4，kcp没有慢启动机制，遵循公平竞争的原则，争取最快的把数据发送出去。

kcp源码剖析

来看一下kcp的源码是怎么实现udp可靠性传输的。
核心的几个函数是ikcp_create、ikcp_update、ikcp_flush、ikcp_input、ikcp_recv、ikcp_send，其中ikcp_create只是创建kcp对象，比较简单，ikcp_update是需要定期调用的，根据外部传入的时钟current决定是否调用ikcp_flush。

ikcp_flush主要是调用ikcp_output来发送一些数据，这个ikcp_output其实是调用的kcp对象的output方法，这个方法是需要用户自己实现的，通过ikcp_setoutput设置该方法。主要发送一些ack，是否需要询问远端窗口大小，以及是否需要发送本端窗口大小，将数据从snd_queue中移到snd_buf中，然后发送snd_buf里面的第一次需要传输的数据，和已经需要超时重传（如果设置了nodelay，超时重传由2rto变为1.5rto）或者快速重传的数据（如果超时重传不满足而快速重传（有包被跳过了次resent未成功发送）满足，也会重传），发送的时候不是一个包一个包发送，而是放在一起，如果马上要超过了mtu，则立马先发一次。

ikcp_input是在udp接收到数据之后对数据进行解析处理，解析出una信息后会删除的snd_buf里面所有sn小于una的包，una代表所有sn小于una的包接收端都接收到了，所以发送端可以删除了，接收到的消息类型分为四种：
1、IKCP_CMD_ACK，这个代表发送消息后对端给出的回应，收到该类消息后代表之前发的sn包已经被接收了，所以也可以从snd_buf中删除sn的包了，同时由于回复的ack包里面还包含了ts时间戳，所以可以计算rtt来更新rto，并把ack包的最大sn计算出来，如果该最大值大于snd_buf中包的sn，说明有跳过一些包没有发送成功，即有丢包现象。
2、IKCP_CMD_PUSH，这个代表发送端有发送数据包过来，需要先把该包里面的sn记录下来放到acklist里面去，因为收到包以后后面需要回复ack进行确认，如果接收到的包的sn没有超过rcv_next＋rcv_wnd，即接收窗口还够的话，就把它放在rcv_buf中排好序的位置（如果已经有该sn的包了则丢弃），最后把rcv_buf里面的数据迁移到rcv_queue里面去，供应用程序读取，如果当前recv_queue还有空间（上一次满了），则下次ikcp_update时告诉远端那边本地窗口的大小（不再为0了，可以继续发数据了）。
3、IKCP_CMD_WASK，远端想询问本地窗口的大小，给probe变量置上IKCP_ASK_TELL的标志，下次ikcp_update时应该判断该标志来告诉对方本地的窗口大小即可。
4、IKCP_CMD_WINS，不做处理，这是远端告诉本地远端它的窗口大小，在上面已经解析出来了，已经存在rmt_wnd变量里面。

ikcp_send是上层用户调用的接口，这个比较简单，只是把要发送的数据根据mss分包后放入到snd_queue里面去，如果是流模式，数据比较大的话，还要设置包的frg字段，代表是第几个包，从高到低，最后一个是0代表是最后一个包了。甚至开始时如果上次snd_queue里面最后一个包没有达到mss，还要将本次数据取出一部分进行填充，剩下的数据才是进行frg再分包处理，这样把发送效率也用到了极致，发送过程中也不会被再分包。

ikcp_recv就是上层用户从rcv_queue里面接收数据了，首先看一下rcv_queue里面有多少数据，需要是完整的kcp包，如果frg是3（整包有3+1个包），但是rcv_queue里面只有3个数据包，说明没有接收完，所以要统计到frg等于0时有多少的数据量peeksize，如果你要读取的数据量比统计出来的数据量peeksize要小，这是不允许的，说明你没有把完整的一个kcp包读完，如果都没有问题，就可以把完整的kcp包数据读到buffer里面了，读完就可以删除recv_queue里面的包了，如果是peek模式则可以不删除（即ikcp_recv传入的大小是负数时），由于rcv_queue被腾出位置来了，所以可以把rcv_buf里面的包移到rcv_queue来了，如果读取数据之前rcv_queue是满的，从rcv_buf移数据到rcv_queue后rcv_queue还有空间，就可以在下次ikcp_update时告诉对端我方有窗口可以继续发送数据过来了。

总的来说，就是用户有数据要发送就先调用ikcp_send将数据分包先发送到snd_queue里面去，在程序下次调用ikcp_update时就会把数据调用output的接口发送出去，如果网络io接收到了新数据，需要用户先调用ikcp_input进行解析处理，处理后的数据会放入rcv_queue里面等待用户读取，所以用户需要调用ikcp_recv读取kcp完整包数据，这就是这几个核心函数参与的主要流程，也构成了kcp实现的核心思想。

通过阅读kcp的源码，也进一步加深了对tcp的理解，佩服kcp的作者能自己实现一个ARQ自动重传请求的协议来，这样的事算是一件很有意义的事，也是积累自己在行业的名声，与之学习。

本文作者： nephen
本文链接： https://www.nephen.cn/posts/3247a6fd/
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！