云风的 BLOG

今天有同事问到，能不能不关闭 skynet 进程，直接重新加载一个 lua 服务。

简单的回答的不能。如果要详细回答，并非完全不行，但这个需求需要使用 skynet 的人自己定制出来。

其实，这涉及服务的热更新问题。由于 lua 的函数是 first class 对象，所以，它即好做热更新，又无法做成业务完全无关的。

容易做的一方面在于，lua 函数本身就是一个对象，只要你找到 lua vm 里的需要更新的函数对象被哪些地方应用，就可以生成（通过 load 新的脚本代码）新对象，取代值前的引用即可。

不容易做的一方面是，lua 完全不区分什么是代码，什么是数据，所以没有 C 语言中所谓符号表。所以并没有统一的地方可以查找 lua vm 里已有的函数。甚至函数也没有名字，你不能用名字索引出新版本的函数，替换掉老版本的。除非你的业务框架做了适当的约定。

另外，在 lua 中，所有函数都是闭包。如果你只想替换闭包中函数原型的实现，那么还需要做 upvalue 的重新关联。这是一个繁杂的过程，如果没有适当的约定，也无法彻底做对。btw, snax 里就做了一些约定，可以一定程度的做到热更新。

那么，直接把旧服务杀掉，启动一个新服务行不行？

如果服务是无状态的，或是你可以在停止服务前把状态保存再安全的地方，新服务启动后可以恢复状态的话，这是个不错的思路。

但是，对 skynet 框架而言，还有一个障碍：新的服务的地址和旧服务不同。

早期的 skynet 版本的 lua 服务是支持就地重启的，也就是并不关闭当前的服务，只是把 lua vm 关闭掉，然后重新开启一份新 lua vm 。这个特性从来没有人用过，所以我后来从 skynet 中移除了，这样可以简化实现。如果你有兴趣，可以从 github 的历史中找回来。

今天，同事又重提此事，希望还是可以支持这个特性，而因此引起的一些问题，他再另行解决。

他需要这个特性是因为不想每次修改一个服务的实现就重新启动整个系统，非常影响开发效率。我想了想，如果只是开发需要，未必需要修改 skynet 底层，使用一个额外的独立库也可以做到。

我便实现了这个东西：

https://github.com/cloudwu/skynet-reload

这个库只有一个 api ，在 require "reload" 后，返回一个函数。只要你在需要重启的服务内调用它（并传入启动参数），服务便会开启一个新的 lua vm 重新加载服务的脚本，顶替原有的服务。

这里有一个 test 程序做示范。它会初始化 echo_reload 服务，并不断向其发送消息。正常情况下， echo_reload 服务会延迟 1 秒后返回。但 echo_reload 服务自身在启动 4.5 秒后，会调用 reload 重启。

在演示中，你会看到，前四次 echo 请求都会成功，而第 5 次请求因为服务重启而异常；接下来的请求又能成功。

这里有几个小问题需要注意：

服务重启时，如果有对外的请求尚未回应（比如示例中的最后一次时钟请求），重启后的服务将收到这个回应。但由于没有对应的处理协程，而会抛出异常。这点是有可能改进的，比如在重启时，记录下发出的请求，记录下来，传递到新版服务中让其忽略。不过我觉得实现它的意义不大。

重启服务后，老版的 vm 并不会立刻关闭。而是要等再重启一次时，才会将上个版本关掉；且第一个版本的 vm 只能等服务推出时才会销毁。这会浪费一些内存，但如果只是开发期使用，不会有太大的影响。这样实现是为了简单，并不改变 skynet 原有的底层代码。

老版本的服务在销毁时，会触发一些 skynet 实现的 gc 方法。比如在 socket channel 模块中，gc 方法会关闭一些 socket fd ，这未必是你想见到的，需要留意。

那么如何让一个已经在运行的服务执行 reload 方法呢？

除了你预先留好控制指令外，还可以利用 debug console 的 inject 命令。

如果让重启后的服务获取到老版本 VM 中的状态数据呢？

老版本的 VM 并没有立刻销毁，所以理论上你可以取到所有的数据。不过目前这个库并没有给出接口，如果你有这个需要，欢迎继续完善它 :) 。还有一个简便的方法是在调用 reload 前，把所有需要继承的数据通过消息发送给自己。由于 reload 后，立刻由新版本接管服务的消息队列，所以就可以接纳这份数据了。

Posted by 云风 at 10:32 PM | Permalink | Comments (2)

skynet 的核心并没有规定怎样处理 TCP 的数据流，但在开发网络游戏时，我们往往需要按传统，把 TCP 连接上的数据流分割为一个个数据包。

将数据流转换为数据包，比较常见的做法是给数据包加一个长度信息，组装在数据流中。我个人比较推荐使用两个字节表示包长度。在 skynet 中提供了一个 GateServer 的模板来帮助用户实现这样一个网关。

这个网关模板采用推送的模式，一旦用户初始化完毕，就会自动分割连接上的数据流，按协议（两字节长度加内容）分割为数据包，回调处理函数。在回调函数中，你可以为新连接启动一个独立服务来处理这个连接上的请求，也可以在单一服务中处理。这些不在本文中讨论。

今天，我想介绍另一个模式来做这个分包的业务，下面给出的 example 相比套用 GateServer 模板可能更适合用户改造合适自己游戏的模块。

skynet 中启动和维持一个 C 服务都是非常廉价的。当然 lua 服务本质上也是一个 C 服务，但它之所以不那么廉价，是因为服务中启动了一个 lua VM 。如果 C 服务的数据结构简单，那么无论从内存角度，还是从 skynet 的消息调度器角度来看，都没有太大的负担。

我们可以为每个 TCP 连接都启动一个 C 服务来管理这个连接。对于连接上的输入数据流，这个服务负责解读两个字节的包头，并分割出数据包；对于输出数据流，这个服务负责给内部数据加上 size 打包。

当然，如果你愿意的话，还可以在这里做通讯的加密和解密工作。

和 GateServer 的推送模式不同，我们可以使用简单的请求回应模式。应用层（通常是 agent）向这个 C 实现的连接代理服务提起一个请求，索要一个数据包；如果当前数据包尚未接收完整，或没有新的数据，这个代理服务简单的挂起这个请求即可。每次从连接上分离出一个数据包后，就从未完成的请求队列中弹出一个请求，回应它。

有了这么一个连接代理服务，使用的 API 要简洁的多。只需要不断的请求新的数据包，一旦外部连接断开，请求抛出异常。而在你不方便处理外部数据时，让代理服务缓存住未处理的数据。这个代理服务可以自己实现超时管理。

如果一个连接上的数据需要先后由不同内部服务处理，请求模式要比推送模式方便。你可以先由认证服务统一对新连接做身份认证；待认证通过后，再分配 agent ，由 agent 接管。

如果担心请求回应模式对高频的输入流有延迟，完全可以使用流水线的方式去调用代理服务（即不等上个请求回应，就立刻提起下个数据请求）。

我的实现放在 https://github.com/cloudwu/skynet_package ，这是个和 skynet 主仓库分离的独立仓库。

有兴趣的同学可以在这个基础上修改使用。

这个库分三个部分 ：

1. skynet_package.c 编译出来的 package.so 是纯 C 实现的连接代理。一个 package 服务只管理一个 TCP 连接。只能在启动的时候初始化它管理的 fd ，并总是由管理服务启动它。

2. service/socket_proxyd.lua 是一个管理器服务，由它管理所有的 package 服务。由于 package 是一个 C 服务，所以并不通过 launcher 服务管理，在 debug console 里自然也无法列出。而这个管理器也就同时承担了查看所有 package 服务状态的职责。可以通过 debug console 给管理器发送 info 指令查看。

3. lualib/socket_proxy.lua 是一个封装好的库，避免直接向管理器或 package 代理发送消息。它有四个 API ：subscribe 可以将一个 fd 注册入管理器；read 可以从已注册的 fd 上读一个包；write 可以发送一个包；close 可以强制断开 fd 连接。

注意：和 gate 不同，这个库并不负责 listen 端口。你需要自己 listen，并在 accept 连接时，把 fd 注册进管理器。具体的使用例子可以看 test 下的 main.lua 。

test 目录下还有一个 client.lua ，是一个简单的客户端测试程序，可以把控制台上输入的字符串，加上两字节的包头，再发送出去；并可以按协议分包读回服务器发送过来的包。

这个测试程序实现了一个简单的 echo 服务，能回发任何接收到的包。一旦发现接收到 quit 则主动断开连接。

btw, 这个示例假定你使用的是 linux ，且已经下载编译了 skynet 放在 $HOME/skynet 目录下。如果你的环境不同，可以直接修改 Makefile 文件。

Posted by 云风 at 05:14 PM | Permalink | Comments (5)

这几天 AlphaGo 4:1 战胜了李世石，围棋积分网站 给了 AlphaGo 一个世界排名。在 3:1 的时候是世界第四，4:1 后上升到了世界第二。

我很好奇这个网站是如何给棋手打分的，便顺着链接指引翻了下 wikipedia 读了几篇 paper 。

下面是我的一些理解，由于我的数学基本功不太扎实，难免有错误，所以有兴趣的同学最好自己读论文 。

首先，如何定义等级分这个东西？

在一对一竞技类游戏中，假设规则是公平的，对战双方如果都能给出最优策略，那么胜负概率是完全均等的 50% 。如果我们假定冥冥之中存在一个绝对实力值，而实力高的人可以少犯错误，那么他就能以超过 50% 的概率战胜对手。

简化胜负结果背后复杂的过程，我们把全体选手按绝对实力值排名，排名靠前的选手对排名靠后的选手，胜率都是大于 50% 的。

由于实力强的人不一定对实力弱的人必胜，所以这个绝对实力值其实是一个概率相关数。胜率的高低可以看成是实力差异大小。根据若干比赛的结果，我们可以推算出代表实力值得后验概率。

比如有两个选手的实力为 A 和 B ，则 A 胜过 B 的概率就为 A / (A+B) 。（不考虑平局的情况）

有一组选手和足够的他们相互之间的比赛成绩的话，我们就可以根据 Bradley Terry 模型 推算出一组实力值，尽可能的符合他们之间的对战结果。

如果直接采用这样的数值表示实力（等级分），存在一个问题：在人类的大多数游戏中，参赛人的实力差别会很大。拿围棋举例，我这样的臭棋篓子，可以轻松碾压一个围棋新手（胜率超过 99%）；而随便一个业余高段也可以轻松碾压我；而他在职业选手中他的胜率却可能掉的非常低；而顶尖职业高手对一般职业选手的胜率也能很高。

这样，每个实力层次的数值都会远大于低一个层次的。结果就是顶尖选手的分值相比初学者就成了个天文数字。

一个叫 Elo 的物理教授发明了 elo 等级分，它采用指数形式表示上面的实力值。每提升 200 个 elo 分，对之前的胜率可以达到 76% ；100 个 elo 分差，胜率 64% 。

btw, 目前国际象棋的世界顶尖选手是 2800+ 分，围棋顶尖选手在 goratings 网站上有 3600+ 分，我个人理解是围棋可能高低手的实力差距更大。另外，在很多采用 elo 系统的电子竞技系统中，顶尖高手也在 3000 分+ 以上。

elo 是个好东西，它把选手的实力以一个非常直观的数字展现出来，在网络游戏中应用更为广泛。系统可以直接使用相近的 elo 分来匹配对手了。不过，elo 在中文维基以及上面的链接文章中的介绍并不准确。中文介绍中强调了 elo 的计算方法，但那仅仅是诸多方法中的一种（可能是实践中采用较多的一种）。而 elo 只是在数学上定义了分值得含义：相差 200 分则胜率达到 76% 。通过比赛结果去反推 elo ，让 elo 更符合结果的胜负比率，怎样的方法更准确，更高效（满足大量玩家大量比赛情况下的实时计算）一直是个难题。

让我们回头来看静态 Bradley Terry 模型，它可能更适合 AI 间的较量，通过短期大量比赛成绩，能够很准确的推算出实际的实力。 而在人类比赛中不太适用。因为人的水平是不稳定的，会随比赛次数增加和提升，也会因为身体因素下降。如果导入一长段时间的赛绩，采用静态分析就变得很不靠谱。

对于人类，等级分更接近一个针对时间 t 的一个函数，而不是一个固定值。对于利用不断发生的比赛来评估不同时间点上系统中每个选手的等级分，有很多方法。

目前用的比较多的是使用一个增量评分系统。也就是给每个新人一个基础分。当他们参加比赛后，每次赢一盘就从败者那里取得一些分，elo 系统就有了自我修正的能力。

同时，如果是弱者战胜强者，这时弱方胜利者取得的分更多一些；反之则少获得一些。这个多少，是由一个公式的参数系数控制的。这个公式和比赛前双方的 elo 有关。

这套方法实现简单，计算成本低，被广泛采用。但它有一个明显的缺陷：对每场比赛结果中蕴含的信息利用不足。

假设有这样一种情况：张三和李四一直在相互打比赛，不相伯仲。他们的 elo 理所当然的一致，也非常符合实际情况（elo 只表示相对实力）。在这个过程中，他们两人的实力都提高了，但由于并没有和外界交流，所以无法从 elo 绝对值中体现出来。

有一天，张三打败了一个外界高手，他的 elo 涨了上去（融入了更大的系统）。但是，李四的 elo 却保持不变。张三的那场比赛原本可以引入这个信息，但简单的增量评分系统却做不到这点。需要李四继续和张三比赛（拉低张三新获得的 elo ），或自己出去参赛（涨分）。

为了解决上面的问题，我们可以对最近发生的一系列比赛放在一起做之前提到的全局静态分析，同时对之前已经发生的比赛结果做一次衰退处理，降低过去比赛的权重。

这种方法可以解决增强评分系统的一些问题，它可以把每场比赛都放进系统中针对所有选手来考量。但这种方法也有瑕疵，最大的问题是，近期的比赛决定了新的一系列等级分的话，那些短期没有参赛的选手的 elo 估计就会偏差变大。（增量评分系统也有这个问题，但对暂时不参赛的选手的 elo 估计的偏差扩大的速度只是时间的平方根，要小的多）

而采用历史衰退处理的评分系统中，长期不参赛的选手复出后，评分可能有非常大的跳跃，而近期比赛频繁的选手，可能连胜多次却迟迟不涨分。衰退周期需要根据选手的比赛频率来定，当不同选手的参赛频率差距很大时，就很难确定这个周期。

动态 Bradley Terry 模型 就是为解决这一系列问题而提出的。它认为人的水平是随时间线性变化的，在极短时间内，人的水平变化不大，变化速度可快可慢，其可能的变化是呈正态分布的。

我们根据上个时间周期选手的 elo 值，考虑这段时间他可能的水平变化区间，再依据最近的整体比赛结果，可以迭代出新一轮的 elo 。

动态 Bradley Terry 模型的问题是计算量过大。WHR 的关键点在于提出了一个近似算法，可以增量更新比赛结果，用一个较小的时间代价迭代出新的一轮 elo 。在每场比赛结果后，对参赛选手用牛顿插值法直接估算出新的 elo ，而在有额外时间时，做多次迭代。

除了论文中给出的数学公式，还有一个开源的 Ruby 实现 ，可能更适合程序员理解。

这个 ruby 实现中，还针对围棋做了一点改进，可以同时考虑让子棋。也就是盘外规则因素对评价系统的影响。他的做法是，根据让子数，对胜率的估算做一个修正。即，如果 A 让子胜了 B 就认为 A 战胜了一个比 B 实际 elo 分更高的对手。

我认为这种修正同样可以用于有比分的对战系统，比如大比分战胜对手或是逼平一个比自己强很多的对手都可以根据结果做一些调整。

Posted by 云风 at 01:10 PM | Permalink | Comments (4)

本文分三个部分：一，什么时候有可能采用 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_send 和 rudp_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 的大小左右。

Posted by 云风 at 12:15 PM | Permalink | Comments (25)