« 用 2d 缩放及斜切变换模拟斜视角下的旋转 | 返回首页 | 浅谈 WHR 全历史排名 »

可靠 UDP 传输

本文分三个部分:一,什么时候有可能采用 UDP 通讯而不是用 TCP 更好;二,一个可靠的 UDP 通讯模块的 API 接口该如何设计;三,一个简单的实现。


首先,我一直是非常反对在 UDP 协议上实现一个可靠传输协议的,即类似 TCP over UDP 的东西。

TCP 已经够复杂了,几乎不太可能重新设计的更好。如果用 UDP 再实现一个可靠传输协议,而表现的比 TCP 效果更好,那么多半只是在部分情况下的优势;或是霸道的占用了过量的资源,而 TCP 在设计时则是很友好的,以整个网络的通畅为更高准则的。

对于后者,我心里相当排斥。如果大家都想独占网络带宽,那么只会让每个人都无法获得高质量通讯。

在网络游戏,尤其是移动网络上的网络游戏制作圈里,不断的有人期望基于 UDP 协议通讯来获得更快的响应速度,而又想让通讯流像 TCP 一般可靠。我也时常思考这个问题,到底该怎么做这件事?

如果基于 UDP 可以做的比 TCP 更好,那么一定是放弃了点 TCP 需要做到的东西。

一条路是寄希望于业务逻辑上允许信息丢失:比如,在同步状态中,如果状态是有实效性的,那么过期的状态信息就是可丢失的。这需要每次或周期性的全量状态信息同步,每个新的全量状态信息都可以取代旧的信息。或者在同步玩家在场景中的位置时可以用这样的策略。不过在实际操作中,我发现一旦允许中间状态丢失,业务层将会特别难写。真正可以全量同步状态的场合也非常少。

那么,不允许信息丢失,但允许包乱序会不会改善? 一旦所有的包都一定能送达,即丢失的包会用某种机制重传,那么事实上你同样也可以保证次序。只需要和 TCP 一样在每个包中加个序号即可。唯一有优势的地方是,即使中间有包晚到了,业务层有可能先拿到后面的包处理。

什么情况下是包次序无关的呢?最常见的场合就是一问一答的请求回应。采用这种方式的, UDP 在互联网上最为广泛的应用,就是 DNS 查询了。

在网络状况不好的时候,我们可以看到有时采用短连接反而能获得比长连接更好的用户体验。不同的短连接互不影响,无所谓哪个回应先到达。如果某个请求超时,可以立刻重新建立一条新的短连接重发请求。这时,丢包重发其实是放在业务层来做了。而一问一答式的小数据量通讯,正是 TCP 的弱项:正常的 TCP 连接建立就需要三次交互,确定通讯完毕还需要四次交互。如果你建立一次通讯只为了传输很少量的一整块数据,那么明显是一种浪费。这也是为什么 google 的 QUIC 对传统的 http over TCP 有改善的空间。

我的思考结论就是:在 UDP 协议之上,实现一个带超时的请求回应机制,让业务层负责超时重发,有可能取得比 TCP 通讯更好的效果。但其前提是:单个请求或回应的包不应该过大,最好不要超过一个 MTU ,在互联网上大约是 500 多字节。


如果有需要在 UDP 上建立一个可靠通讯模块,怎样的 API 比较好呢?

看了几个开源实现,我认为一个最糟糕的地方是,通讯模块本身和 UDP 绑的太死,也就是这个模块本身负责了 UDP 包的收发。

如果把这样的开源库简单拿过来用倒是容易,但如果想整合入以有的网络层就会相对困难。其实,建立一个可靠通讯协议,最主要解决的问题还是如果利用不可靠的数据传输,实现一个协议来达到可靠传输(保证次序不丢包)的问题。而使用怎样的通讯 API 是次要的。

所以,我认为整个模块应该只提供输入和输出数据包的接口,和网络通讯 api 无关。

struct rudp_package {
     struct rudp_package *next;
     char *buffer;
     int sz;
};

struct rudp * rudp_new(int send_delay, int expired_time);
void rudp_delete(struct rudp *);

// return the size of new package, 0 where no new package
// -1 corrupt connection
int rudp_recv(struct rudp *U, char buffer[MAX_PACKAGE]);

// send a new package out
void rudp_send(struct rudp *U, const char *buffer, int sz);

// should call every frame with the time tick, or a new package is coming.
// return the package should be send out.
struct rudp_package * rudp_update(struct rudp *U, const void * buffer, int sz, int tick);

一般在网络游戏或其它需要低延迟的应用中,我们都需要定期保持心跳,以检查连接质量。所以必然会周期性的调用维持用的 api ,这和一般网络应该是不同的。

这里提供了一个 rudp_update 的 api 要求业务层按时间周期调用,当然也可以在同一时间片内调用多次,用传入的参数 tick 做区分。如果 tick 为 0 表示是在同一时间片内,不用急着处理数据,当 tick 大于 0 时,才表示时间流逝,这时可以合并上个时间周期内的数据集中处理。

rudp_update 的每次调用均可以传入一个实际收到的 UDP 包(可以是一个完整的 UDP 包,也可以是一部分),这个包数据是一个黑盒子,业务层不必了解细节。它的编码依赖对端采用的相同的 rudp 模块。

每次调用都有可能输出一系列需要发送出去的 UDP 包。这些数据包是由过去的 rudp_send 调用压入的数据产生的,同时也包含了最近接收到的数据包中发现的,对端可能需要重传的数据,以及在没有通讯数据时插入的心跳包等。

总的来说,rudp_update 内部做了所有的可靠化通讯需要的数据组织工作。使用的人传入从 UDP socket 上收到的数据(不包括数据加密或其它数据组织工作),并从中获取需要发送到 UDP socekt 的数据。

而业务层的数据收发只需要调用 rudp_sendrudp_recv 即可。其中,rudp_recv 保证数据包按次序输出;rudp_send 也并不真正发送这些数据包,而是堆积在 rudp 对象内,等待下一个时间片。

rudp_new 创建 rudp 对象时,有两个参数可配置。send delay 表示数据累积多少个时间周期 tick 数才打包在一起发送。expired time 表示已发送的包至少保留多少个时间周期。和 TCP 不同,我们既然使用 udp 通讯,就是希望高响应速度,所以即使数据抱迟迟没有送达,它们也不必保留太长时间,而只需要通知业务层异常即可。


我花了两天时间设计一个可靠传输协议,并做了一个简单的实现。

这两天一共设计了三个版本,前两个版本都因为过多考虑协议的紧凑性而导致了实现太复杂,而在我的实现超过 700 行 C 代码后推翻重写了。

最后一个实现出来的版本是这样的:

通讯是双向的,每边都可以是数据生产方 P 或数据消费方 C。

每个逻辑包都有一个 16bit 的序号,从 0 开始编码,如果超过 64K 则回到 0 。通讯过程中,如果收到一个数据包和之前的数据包 id 相差正负 32K ,则做一下更合理的调整。例如,如果之前收到的序号为 2 ,而下一个包是 FFFF ,则认为是 2 这个序号的前三个,而不是向后一个很远的序号。

若干逻辑包可以打包在一个物理包内,但一个物理包尽可能的保证在 512 字节内,超过则分成多个包。但每个逻辑包都不会分拆在不同的物理包中。

如果需要生产方 P 重发一个特定序号的包,消费方 C 可以发起一个请求。多个请求可以打包在同一个物理包内,也可以和待发送的逻辑包打包在一起。

这里采用请求机制,而不是 TCP 那样的确认机制,是因为在特定条件下,请求机制实现更简单。正常网络状况下,无论是缺少包(发现收到的逻辑包序号不连续)再向对端请求,还是让消费方 C 去确认收到了哪些包,生产方 P 发现未请求的包主动重发;都是极其稀少的事情,其差别可以忽略。

主要区别在于,采用请求重发机制要求 P 方尽可能的保留已发出的数据,正常通讯条件下, 缺少确认机制会导致 P 不敢随意丢弃过去发出的数据。但在这里,我们可以依据超时来清理过期的数据,也就回避了这个问题。

除此之外,我们还需要在没有数据时,有可以维持心跳的空包,以及发生异常时通知对方异常的机制。

最终,有四类固定格式的数据:

  • 0 心跳包
  • 1 连接异常
  • 2 请求包 (+2 id)
  • 3 异常包 (+2 id)

后两种数据需要跟上两字节的序号(采用大端编码)

普通的数据包可以直接采取长度 + id + 数据的方式。

这五类数据均可以统一采用 tag + 数据的方式编码。如果是前四种数据,就在 tag 部分直接编码 0~3 ,如果是最后一种数据包,则将 tag 编码为编码 (数据长度 + 4)

tag 采用 1 或 2 字节编码。如果 tag < 127 编码为 1 字节,tag 是 128 到 32K 间时,编码为两字节;其中第一字节高位为 1 。tag 不能超过 32K 。

我在 github 上放了一个只经过非常简单测试的代码实现。https://github.com/cloudwu/rudp 仅供参考,真想拿去用的同学风险自负。好在实现并不复杂,只有 500+ 行 C 代码,有 bug 也比较容易查。

注: 我定义了一个宏 GENERAL_PACKAGE ,为了测试方便定义为 128 。实际使用的时候应该调整为 MTU 的大小左右。

Comments

在收到存活包后,array_insert(&U->send_again, U->recv_id_min);
什么作用

单个请求或回应的包不应该过大,最好不要超过一个 MTU ,在互联网上大约是 500 多字节。

这个是怎么计算出来的?MTU不是一般都是1500字节么?

本来写了第二部分,没发上来,这个博客应该改进一下

我也一度很反感udp产生改善论调的主张。
udp和tcp在底层ip传输上没有本质的区别,原则上看udp重传构造的可靠连接和tcp自带的可靠只是把ack放在协议层还是上层逻辑的问题。难道交换层次结构本身也能具备什么魔力么?
但实际上tcp->tunel/socks5->udp的代理程序确实让卡顿的电影不卡了,加载速度变快了。让人不得不想这中间产生的区别是什么。
实际的实验让我找到一些来自现实世界的解答,如果归于理想的逻辑,确确实实这两者不会也不该产生这类性能特性上的差异,但现实世界不是理想模型,网络的构造和信息交换情况也不像家里的局域网这么清爽,真实世界的交换网络中的交换机节点和数据节点决定网络的实际表现。交换机和路由器的低资源配备决定了机械式的转发,重发,流控模式。这种机械式行为模式,确保了ip交换在每台交换机和路由所能触及范围内的可靠和有效。但这不意味在更大的尺度上的效能。
从这个角度再来看待udp和tcp的差异,无非是在udp的模式上我们拿了2样东西回来。
1.顺序,同时是流控方式:基于状态的代码模式决定的数据顺序。 tcp把数据确保数据序列的工作在网络传输时,层层 包包,顺序保证,用起来确实方便。但也消除了数据并发传输的可能。这很大程度上直接形成了tcp的流控模式,从编程的形式上tcp无需流控,你不拿走对方就丢不出来。代码的顺序化,和收发的顺序在影响传输性能。但udp模式在这方面有本质的不同,数据传送时没有前后这一说,你拿到的数据也是如此。交换机,网卡根本不考虑序列的要求,从传输上这很牛叉,但这种模式与Coding的顺序式思维不相符,偶尔有无状态的数据可以直接套用这个思维,但对于具备时间和序列要求的场景,这就显得十分难用。因此大多情况下udp fake tcp必须要做数据序列重整。端对端的序列重建和步步紧等的局部重整,在整体行为上确实可以减少延迟。

2.链路特性,更是流控方式。 一旦转入udp,链路的管理就从路由器的问题变成你的问题了。还要不要等ack,对方是否还在,我能发送多快这一系列的问题在你建立socket的第一个瞬间就变坑了。貌似少了connect的动作,但实际需要考虑的问题变得更多了起来,但此时你具备的信息也是路由器不具备的例如带宽,端对端延迟,实际的丢包率,如果这些都用来作为链路可靠性和流控的参数,你或许能'预测',发送速率,ack的时间,重发的速度。

都是些半桶水罢了。。。
可靠传输的核心是阻塞控制,简单点说,一条马路(10MB)同时允许10辆汽车通过,现在上面有2台,那么再放8台是刚好适合的。放少了,浪费带宽;放多了,会导致越来越阻塞,最后网络瘫痪(TCP基于友好,是遇到这种情况就暂停,过一会儿再测试,称为慢启动)。
在相同的网络环境下,特别是跨网(比如说电信与联通),UDP有可能比TCP块120倍。这是几年内严格测试得出的结论。
顺便说一句,纸上谈兵谁都会,例如固定MTU。但是可以很负责的告诉你,很多路由特别是企业路由,仅允许每次通过512字节的UDP。所以QQ是会在登录期间测试这个值。

在clear_send_expired里面有个会导致内存泄露的bug,
U->free_list = last;应该改成
U->free_list = U->send_history.head;

在clear_send_expired里面有个会导致内存泄露的bug,
U->free_list = last;应该改成
U->free_list = U->send_history.head;

在clear_send_expired里面有个会导致内存泄露的bug,
U->free_list = last;应该改成
U->free_list = U->send_history.head;

static void
clear_send_expired(struct rudp *U, int tick) {
struct message *m = U->send_history.head;
struct message *last = NULL;
while (m) {
if (m->tick >= tick) {
break;
}
last = m;
m = m->next;
}
if (last) {
// free all the messages before tick
last->next = U->free_list;
U->free_list = last;
}
U->send_history.head = m;
if (m == NULL) {
U->send_history.tail = NULL;
}
}
这个函数U->free_list = last,是不是错了,应该U->free_list = U->send_history.head吧,否则会造成内存泄露啊

@daemon
你们针对enet做了哪些改造啊?

Sip协议用udp传输差不多也是这个思路,在T1定时器内没有收到响应,就重传,然后定时器时长加倍。。。

对了,tftp协议也是RFC标准

除了dns查询,还有tftp协议(一种简单的文件传输协议)也是基于udp的,该协议也是基于应答,包长度限制512字节,支持多个命令。

http://www.hiv123.com 这个好像也是这种形势

基本上你的算法和UNREAL3中的是一致的,也是采用请求机制,无请求默认消息包对方已收到,发送方需要一个发送缓存区,一个缓存的数据包超过心跳时间就会清掉,如果缓存满了,就是网络出了问题,弹框异常了。

unreal3 实现了UDP 摸拟TCP,事实证明是比TCP传输更流畅,包大小不超过576,也就是MTU大小,牺牲了TCP的一个功能:如果网络状态良好,程序崩溃导致的socket销毁,通讯另一端是马上能知道的。UDP无连接,另一端就无法及时知道,只能依赖心跳。应该说,有成熟稳定的UDP可靠传输从理论上来说也是比TCP更流畅的

似乎和RTP有些接近,每个RTP包有个序列,20ms发送一个某个大小范围内的包,网络侧可以算出QoS

@xtaci

以前听说过,但是没看过. 刚才看了一下.

其实我不太关心协议设计和实现. 这个总会结合实际使用的反馈有新的改进想法.

但是我比较关心 API 设计, 这关系到是否能够更好的和别的模块整合到一起.

我不太喜欢传递 C callback 的设计, 有了 callback , 模块就纠缠在一起了. 也不适合跨语言使用.

当然,再封装一次可以把 callback 屏蔽掉.

https://github.com/skywind3000/kcp
看过这个项目么?

@Ryan 给你看几篇论文,我们实际开发过程里也基本上验证了,也踩过坑。
1.On Latency and Player Actions in Online Games
2.The effects of loss and latency on user performance in unreal tournament 2003
3.Matchmaking in multi-player on-line games studying user traces to improve the user experience

我一直认为udp就是为了不可靠传输为生的,把它实现为可靠的udp,是违背了udp的本意。再说可靠的udp能在游戏带来了多少的好处?云风有在游戏项目里用过吗?

题外话:公司搬到广州了?

@daemon

这篇的重点是第二部分,一组合理的 api (和网络层无关)

其次是第一部分,尽量不要做这件事。

最后才轮到第三部分,怎么实现对我不重要。如果要选实现,我选最简短的那份。

接上,在国内最好udp包大小最好不超过576,我们踩过坑(国内一些设备制造商没有严格遵循rfc标准),576最安全,fps,moba,球,车类的上行包大多数不超过100字节,下行不超过300,所以大多数情形下不会因为分包造成有效payload减少

tcp麻烦的是在wifi情况下的rto问题,fps,moba对延时很敏感,所以基本上都用udp,有过球类游戏用过tcp,统计发现比较糟糕。另外,为啥要自己造轮子哦? 用enet改造一下就能用了

Post a comment

非这个主题相关的留言请到:留言本