5月, 2018 | 重归混沌的BLOG

We性质b和网游最大的不同也许就在于数据同步。

Web的工作流程（这里不包括页游）虽然也有很多变化，但是一般都大致分为三步。

1. 在浏览器输入网址，浏览器通过HTTP协议请求服务器加载数据，服务器在收到HTTP请求之后，从数据库加载相应的数据（有可能是HTML,JS等一些用于浏览器渲染的数据）并返回给客户端。这一步我称之为查询。

2. 浏览器收到服务器返回的数据之后，将数据渲染并呈现给用户。这一步我称之为渲染。

3. 用户在看到浏览器呈现的内容之后，根据需要去执行不同的操作，这些操作为导致浏览器将一些数据发往服务器进行处理，这一步我称为提交。

大部分Web逻辑除了在这三步之间循环之外，还有一个很重要的特点，那就是几乎很少与旁人进行实时交互。比如你在某论坛改了名字，也需要对方手动刷新才能看到。当然也有可以实现显示的，但那是极少功能才有的待遇（并且一般都是通过Hang住HTTP请求来实现的），这里不考虑这种情况。

因此，市面上对Web的高可伸缩性的研究，大都维绕着数据库来做。因为HTTP的数据同步量真的没有什么好研究的，这种模式几乎已经把数据同步量压缩到最低了。只有用户操作才会加载数据，这是多么节省的一种数据同步方式啊。

网游本身就是一个强交互的模式，玩家A做了一个操作，所有应该能看到玩家A的其他玩家都必须能看到玩家A做了什么操作（只是理论上，也许由于某种技能别人看不到）。

这样数据的同步量就会非常大，而且这种数据量，会随着同时在线的玩家的数量成指数性增加。

于是人们研究了各种减少数据同步量的算法，比如AOI、帧同步等。

这里我先私自把游戏分为开房间和大地图两种模式。

开房间模式的游戏,一般同一个房间的人数不会过多。所以最简单的做法就是，直接同步位置和状态。

每个人客户端移动过程中定时（比如10ms)广播坐标给房间内所有玩家，然后客户端根据收到的新坐标，做插值补偿。这又被称作影子跟随算法，即客户端实际表现的位置永远落后于其真正的位置。

如果客户端放了一个技能，就把这个技能效果广播给房间内的所有玩家。

但是这里会存在一个问题，如果这是一个延时类技能，比如几秒后生效，那么服务器在收到释放技能时就需要广播一次，当技能真正生效时，还需要再次广播一次。如果是一个每隔几秒就生效一次的buff就会更麻烦，每次buff生效，都要进行消息广播。数据量会远超于玩家的操作频次。

即然大部分数据量都是状态同步引起的，那么就把所有状态全部交给客户端自己运算，这就是帧同步的本质。客户端拥有整个游戏的全部运算逻辑，将整个游戏进程人为划分为逻辑帧，每个逻辑帧玩家上报自己的操作，由服务器进行房间内广播。客户端收到操作为自己还原各种状态。如果房间内有N个人，每个人操作M次，数据同步量只有M*N条消息，远低于之前的状态同步的数据量。这对于流量并不富裕的手机来说尤其是个好消息。

如何保证所有客户端逻辑和表现都一致，除了要做正确一逻辑帧操作还原外，还有一点很重要，就是复原随机逻辑（战斗中经常会有各种概率判断)。这一点可以通过伪随机序列来保证。

下面来看看大地图模式（这里的大地图模式，是指所有玩家在一张地图上，并且战斗过程中不切换场景）。

在大地图模式，所有玩家都在一张地图上行动，因此玩家数量与房间内的数量根本不是一个数据级（虽然有可能为了增加同时在线人数，会将地图进行分块处理。但即使如此，单块地图上的玩家也远大于房间内玩家数量)。

这也就意味着将数据（操作数据或状态数据）广播给地图上的所有玩家，是不现实的。所以必须要采用AOI算法，来选取需要收到这些数据的玩家。然后将这些数据组播给选取到的玩家。

在使用了AOI算法之后，一般来讲人数的量级与上面开房间模式需要同步的人数量级就差不多了。

那么是否使用了AOI之后，同样可以采用帧同步算法优化掉状态同步呢。

答案显然是否定的，上面也提到，所有的战斗系统一般都会有概率的存在，而一张大地图上必须也只可能有一个伪随机序列（因为玩家之间的视野是交错的）。这也就意味着所有的客户端不可能事先知道这个伪随机序列走到哪一步了（每场战斗都会使伪随机序列前进一步，如果要所有客户端都实时知道当前伪随机序列的进度，就必须在每一场战斗之后，将当前随机数广播给地图内所有玩家，这显然是不是现实的)。

从上面的分析可以得出一个结论，制约大地图模式使用帧同步算法的惟一因素，就是无法复原随机逻辑。那么如果我们游戏地图内没有随机因素（暂且不论是不是有可能），是否可以在AOI的基础上再使用帧同步算法的变种呢。

我们来分析几种情况来看看是否可行，这里需要强调一点，我们假设整个通信采用TCP（TCP具有FIFO性质）传输，服务器采用的是单线程模式。

1. 玩家B先看到了玩家A，然后玩家A被打了掉了5滴血，最终玩家A还有75滴血。

玩家B首先在视野内看到了玩家A，这时会同步到玩家A的血量为80.

然后B收到了玩家A被打的操作（这个操作固定伤5滴血）,玩家B将80减去5得出玩家A还有75滴血的结果。显然这是正确的。

虽然可能buff之类带时间的逻辑不好控制，但是相信经过合理的设计，逻辑上应该不会有太大问题。

2. 玩家B还没收看到玩家A，然后玩家A被打掉了5滴血。

玩家B收到玩家A被打的操作消息后，发现自己视野内还没有加载出玩家A的数据（注意是从服务器加载到的数据，不是客户端还没有把模型之类的数据加载完), 于是将消息抛弃。

之后，玩家B收到的从服务器请求来的数据，A的血量为75。显然这也没有错。

所以在没有伪随机存在的情况下，完全可以使用帧同步算法的理论，进一步优化状态同步。

很巧我们最近开发的游戏，大地图上的表现确实不需要伪随机序列。

这次分析再次告诉我，一定要认清算法的局限在哪里，这样才能根据实际情况灵活组合运用。别人不能用，并不是你就一定不能用。

在好几年前我已经中招过一次了，没想到最近一不留神又中招一次。不过这次的花样和上次又不太一样。

Bug的起因是，我需要一个函数，根据指定速度（可能不是整数)和距离来获取到达目的点的时间，于是就有了下面这样一段代码。

//#define TIME time(NULL)
#define TIME 1526796356
time_t foo(int distance, float speed)
{
        return TIME + distance / speed;
}
int main()
{
        printf("%ld\n", foo(30, 3.0f));
}

咋一看这代码几乎没毛病，严格遵循牛顿大神给出来的公式来算。

然而他的输出却是`1526796416`这样一个值。在思考了将近20分钟之后，我才恍然大悟。

根据《The C Programming Language》第二版中的A6.5节算术转换一节的内容

`
First, if either operand is long double, the other is converted to long double. Otherwise, if either operand is double, the other is converted to double.

Otherwise, if either operand is float, the other is converted to float.

Otherwise, the integral promotions are performed on’ both operands; then, if either operand is unsigned long int, the other is converted to unsigned long int

Otherwise, if one operand is long int and the other is unsigned int, the effect depends on whether a long int can represent all values of an unsigned int; if so, the unsigned int operand is converted to long int; if not, both are converted to unsigned long int

Otherwise, if one operand is long int, the other is converted to long int

Otherwise, if either operand is unsigned int, the other is converted to unsigned int

Otherwise, both operands have type int

There are two changes here. First, arithmetic on float operands may be done in single precision, rather than double; the first edition specified that all floating arithmetic was double precision. Second, shorter unsigned types, when combined with a larger signed type, do not propagate the unsigned property to the result type; in the first edition, the unsigned always dominated. The new rules are slightly more complicated, but reduce somewhat the surprises that may occur when an unsigned quantity meets signed. Unexpected results may still occur when an unsigned expression is compared to a signed expression of the same size.
`

代码`return TIME + distance / speed`在实际执行时会被转换成`return (float)TIME + (float)distance / speed`来执行。

之所以思考了那么久才发现问题，是因为在写代码时就知道编译器会进行类型提升。而从理论上来讲，编译器在进行数学运算时，总是会向最大值更大的类型进行转换，以保证隐式转换的正确性。所以首先就把这种错误是类型提升造成的可能给排除了。

这种理论本身也是正确的，因为float的最大值为`340282346638528859811704183484516925440`，可是我忽略了一个很重要的事实，就是float即然叫单精度，就说明它本身是有精度的。

来看一下float的构成.

float由1个符号位，8个指数位和23位尾数位构成，而精度完全是由23位尾数控制的，因此虽然float可以表示很大，但那是通过指数位进行跳跃（乘以2的N次方)来得到了，换句话说，float能表示的数其实是不连续的，而我们现在的time(NULL)值`1526796356（0101 1011 0000 0001 0000 0100 0100b)`已经使用了31位二进制了，它的二进制有效数字位为29位，已经超出了float中的尾数位。因此在int转向float时必然会丢失精度。

弄清楚了问题之后，只需要加个类型强制转换就可以解决问题了:

//#define TIME time(NULL)
#define TIME 1526796356
time_t foo(int distance, float speed)
{
        return TIME + (time_t)(distance / speed);
}

BTW. 在查阅文档时，发现了一个有意思的事，《The C Program Language》第二版在算术类型转换一节中特意标注，在第一版中，所有的float类型算术运算都是先转换成double再进行，而第二版的描述是float类型算术运算‘有可能’直接进行，而不是转换成double之后再进行。

月度归档： 2018年5月

谈谈我对数据同步的理解

又一个类型提升引起的Bug