国服开发杂谈

Starmie

每日积分赛

源代码: server/chat-plugins/ps-china-auto-tour.ts

需求是：1. 输入一个比赛日程表，在指定房间按时开赛；2. 比赛结束后根据选手成绩发放奖励。

先做一套聊天指令，让房间管理员可以创建、修改和保存比赛日程表。日程表记录了每场比赛的时间、规则、积分奖励、开赛时提示的额外信息等。时间可以设置为以一周/一天/一小时为周期，比如在每天每个小时的30分开赛，或者在每周三晚8:30开赛。然后我们就可以从日程表里选取开赛时间最近的场次，定时开赛。

注意一下定时的技巧，由于时间差可能长达一天或数天，直接往目标时间t去setTimeout是会积累下来误差的。这里采用的做法是取一个小的时间差ε=5s，先开一个长计时到t-ε，再开一个短计时到t。其实最初的设想是做一个10:1递归套娃计时器，这样大概可以精确到CPU时钟周期的级别，但后来想想实在没有必要。

开赛时要在房间里广播一堆东西，这里有个坑就是它必须传入一个用户和服务器对话的上下文环境。显然我们这里没有一个发起tour的用户，smogon应该是没有考虑到tour可能直接由服务器发起的情况。那么我们只能手写一个broadcastContext来充当这个环境，而类型检查的问题就只能ts-ignore了。

PS自带的房间赛功能是通过server模块里的Tournaments.Tournament实现的，roommod以上权限可以通过/tour create指令在服务器生成一个Tournament对象。我们修改这个对象的onTournamentEnd()方法，使其在完赛后执行我们的奖励结算工作。

奖励分两部分，一个是按胜利场次奖励国服积分，一个是给冠军发蛋。如果账号上没有国服积分就会发到大号上，如果账号上没有宠物系统存档也会把蛋发到大号上。具体怎么找的大号以后再讲。加分这里还有一个坑，修改国服积分要写ladder文件，以前这个函数是异步的，平常用起来没问题，但如果短时间内给多人加分就会进入死锁，进而磁盘IO暴涨，服务器崩溃。Tour结算正好符合这个情况，所以第一次开积分赛时服务器挂了，国服积分文件也没了。还好我有备份，后来把加分函数改成同步再加锁就好了。

每场比赛结束后会把比赛过程写进一个log文件里，便于管理和debug。再选取日程表里的下一场比赛，计时等待。

Scale

好赞我顶

EgoXim

瑞斯拜，投标标题：海星哥的小黄鸭

Starmie

队伍数据库

源代码: server/chat-plugins/ps-china-team-database.ts

这个一开始是给WCOP中国队用的，算是个军改民项目。近期得空做了一些用户体验和安全性能方面的优化，于是可以公开出来造福大家了。

自从20年WCOP改为全8OU， @fsk 就用SQLite做了个Smogon 8OU比赛数据库。其原理是Smogon比赛服上的rep链接都是公开的，我们只需要遍历rep编号就能获取比赛服上一段时间内的所有8OU replay，然后从replay里抓出双方选手ID和队伍配置组成一行数据落库。

但这个数据库躺了两年没发挥什么作用，我觉得主要问题是用起来比较繁琐。你如果按选手id检索吧，我为啥不去ReplayScouter呢？你如果按宝可梦检索吧，搜万金油的重复率太高很难得到有效信息，冷门怪的使用场景一般也已经作为名场面刻在大家的记忆里了。还有一个办法就是按队伍检索，输入六只宝可梦获取这个队伍的所有replay，最好还能给出那些改了一两只的相似队伍的信息。那么我们就需要对数据库做一点改造了。

比赛服上每年会新增几万条8OU Replay，这个数据量其实是比较小的，因为环境变化我们基本只需要关注一年以内的。但是你如果对每个队伍都要去搜 A(6,6)=720 种排列方式，那还是顶不住的。所以我们的第一步是，为每个队伍生成一条与排列无关的标签。这里有很多种做法，最容易想到的也最容易实现的是把队伍按精灵编号排序后取个哈希值。但是它有一个弊端就是不支持模糊匹配。假设我们输入了一个队伍，想要查找数据库里有5只或4只相同宝可梦的队伍信息，怎样的标签可以支持这个需求呢？

让我们从队伍信息本身的特点入手。虽然队伍中的每个位置都有900种可能，但绝大多数情况下我们只需要关注从RU到OU的150多种可能性，那么我们可以使用一个160维的one-hot向量代表一只宝可梦。队伍中的宝可梦不能重复，那么一个队伍就是一个6-hot向量，如果出现了冷门宝可梦或者他就少带一只，在后续步骤里也没有大碍。由于每一维上只有可能是0或1，我们可以用5个32位整型数字表示这一个160维向量，也就是上文提到的与排列顺序无关的队伍标签。当然NodeJS里并没有32位整型这种东西，这里取32位你可以理解为强迫症。

我们以每个队伍对应的标签（5个数字）为索引建库。每输入一个队伍，我们先计算它的标签，再遍历库中所有标签和它做按位与运算。我们看一下运算结果的二进制表达，有几个1就代表这两个队伍有几只相同宝可梦。假设我们数据库里有100000个队伍，那么检索一个队伍需要做500000次位运算，众所周知这就相当于691轻取ACM金牌的时间复杂度，上世纪的老爷机也跑不出一秒了。不过CPU里并没有这个数1的电路，得用移位来做，但即使这样在服务器上也能保证查询速度在百毫秒数量级。

可能有小朋友要问，既然这个数据库查询速度这么快，为什么还有30秒CD呢？主要是因为把相似队伍抓出来之后我还得转换成html字符串再发给你，有时候一下搜出一百来个队伍，这个字符串处理还是比较吃CPU的。当然我得看看阿里云的监控，不排除降到10秒或者5秒的可能性。至于为什么非得转换成html字符串，那是因为PS不让我改前端，这就涉及到PS本身的结构问题，我们以后细讲。

shuo硕德er

@Starmie 斯国一内

cbz123

starmie为什么是神

zero found

听我说谢谢你四大麦

小箜篌

四大买我的超人

Starmie

@Starmie 在国服开发杂谈中说：

我们修改这个对象的onTournamentEnd()方法

用B类的静态方法替换A类的某个实例的动态方法，这是不守面向对象基本法的，只能在无法无天的脚本语言里实现。国服里还有两处这样的实现，分别是Ladder和Battle类。这种做法其实是上不得台面的，在类型安全和垃圾回收上可能有各种各样的问题。但有一点好处无法替代，就是不需要改动A类的代码。所以这是在二次开发中由于原作者没有留好接口，不得已而为之的。

但今天我老板给我推销这个。背景是我手上有一个项目算是基于PyTorch的二次开发，这样做不仅我这边写着方便，而且对于用户来说也更傻瓜了。但这可是开源项目啊，是要我把法外狂徒四个字贴贵司脸上吗？

当然，这不重要。只要能省我两小时工作量，我就觉得他是这个👍。你说上不得台面？不不不，这反而是高端技巧！要有道路自信，让那群老古董们颤抖吧！

Starmie

Pokemon Showdown 结构概要上

上周给国服升级了https，借这个机会讲一下PS整体结构。这篇文章将帮助你理解：当你使用PS时，你的浏览器里发生了什么，你的网卡上发生了什么，对应的PS服务器上又发生了什么。

0. 我奶奶都能听懂的计算机网络导论

简化了很多内容，因此会多处表述不严谨，而且我只讲我需要讲的
每台机器连接到公网后会有一个IPV4地址，比如国服服务器的IPV4地址就是 47.94.147.145
每台机器有很多个端口，机器上运行的程序（服务）可以监听一个或多个端口，比如国服论坛就通过 80 端口接收用户发来的数据，那么国服论坛这个程序的地址就是 47.94.147.145:80
当你访问某个网站时，你的机器会从某个随机端口向该网站的服务器发送一些IP数据包，然后服务器会给你回复另一些IP数据包
IP数据包里面有TCP数据包，TCP数据包里面有HTTP数据包或WebSocket数据包
使用HTTP协议访问网站时会默认走80端口，所以这个80是可以缺省的，只有当你访问的不是80端口时才需要指定，比如国服测试服：47.94.147.145:8000
有一种服务器叫做域名服务器（DNS），当你使用域名访问某个网站时，会先从域名服务器拿到这个网站的IP地址和端口，比如 *.one 的域名服务器就会把 pschina.one 解析到 47.94.147.145:80
你的浏览器是一个JS运行环境，当它访问某个网站时会根据其设置拿到一些前端（client）代码，使用这些代码绘制网页内容，并和后端（server）通信，这里的后端指的是和业务相关的服务器
前端会在你的浏览器里记录一些用户数据，这个叫做Cookies，比如你的队伍库就保存在Cookies里
我们主要介绍中心式的服务结构：每个用户的浏览器上都有一套前端代码，而它们要访问的后端只有一套，但这一套后端可以分布在多个IP地址和端口上分别负责不同的功能
HTTPS的意思是“加密的HTTP”，其加密原理是网站把自己的RSA公钥上传到某个公认的中间商，用户使用从中间商拿到的公钥加密自己发给网站的数据，网站服务器收到后使用私钥解密
使用HTTPS协议访问网站时会默认走443端口

1. play.pokemonshowdown.com

这是获取PS公用前端的地址，同时是公用账号服务器（login server）
pokemonshowdown.com（104.22.63.197）是PS的主页，也是PS自己的域名服务器，它会把 play.pokemonshowdown.com 解析到 172.67.4.23
psim.us （104.22.11.234）也是PS自己的域名服务器，它会把各个子服务器（*.psim.us）解析到对应的地址，比如把 china.psim.us 解析到 39.96.50.192
当你访问 play.pokemonshowdown.com 时，前端会和默认后端 sim2.psim.us（104.22.11.234）通信，这个就是官服
当你访问 xxx.psim.us 时，浏览器会先去 play.pokemonshowdow.com 获取前端资源，再和指定后端 xxx.psim.us 通信
你的账号和密码也保存在 play.pokemonshowdown.com，这时它作为账号服务器，无论你在官服国服还是比赛服，账号的登入登出都是和它通信确认的
Replay 都保存在公用回放服务器（login server）replay.pokemonshowdown.com 上，它的IP地址也是 172.67.4.23，当然这不一定是一台机器，很有可能是一个集群的入口
当且仅当使用PS公用前端时才可以访问公用账号服务器和公用回放服务器
PS前端和账号服务器的代码也是开源的，Github仓库分别是 https://github.com/smogon/pokemon-showdown-client 和 https://github.com/smogon/pokemon-showdown-loginserver

（未完待续）

Starmie

@Starmie 在国服开发杂谈中说：

不过CPU里并没有这个数1的电路，得用移位来做

这两天更新队伍数据库，又看到这段移位数 1 的代码：

let simVal = 0;
for (let j = 0; j < teamCodeLength; j++) {
    const simCode = teamCode[j] & targetTeamCode[j];
    for (let x = simCode; x > 0; x >>= 1) {
        simVal += x & 1;
    }
}

对每一个 32 位的simCode它都最多需要循环高达 32 次，让我觉得CPU很累，想给它减负。但短暂思考后没有好的思路，在认识到我并没有比去年的自己更聪明之后，决定试一下来自FPGA的馊主意：查表！

具体来说就是，直接把simCode的所有可能值对应的 1 的个数存下来，计算simVal时直接查就可以了。当然我存不下 32 位（43 亿）的表，但 4 位（16）或者 8 位（256）还是可以的嘛！这样至少不用每次只移一位了：

const simValLUT = [
    0, 1, 1, 2, 1, 2, 2, 3,
    1, 2, 2, 3, 2, 3, 3, 4,
];
let simVal = 0;
for (let j = 0; j < teamCodeLength; j++) {
    const simCode = teamCode[j] & targetTeamCode[j];
    for (let x = simCode; x > 0; x >>= 4) {
        simVal += simValLUT[x & 15];
    }
}

这样改完之后一测试，居然变慢了，查表是个负优化！当然这也并不奇怪，因为和FPGA的硬件LUT不同，这个simValLUT是在内存里的，而相对访问寄存器和做位运算来说，访问内存是一件很慢的事。当然现代CPU单核可以有64KB的一级缓存，所以在遍历队伍库的过程中这个simValLUT被读取一次之后就被备份在一级缓存里了，而且碰撞率很高。但访问一次一级缓存也需要 4 个CPU时钟周期，在移位上省下来的时间就这样又被花出去了。

但我不甘心，还是想把这个丑陋的移位算法干掉。于是今天我灵机一动去问了New Bing：

它先是给出了一个一模一样的移位算法：

我寻思这是把我当小学生呢，继续刁难它：

终于大的来了：

它并没有按我的要求删除循环，但确实变快了很多。让我们翻译一下：

let simVal = 0;
for (let j = 0; j < teamCodeLength; j++) {
    const simCode = teamCode[j] & targetTeamCode[j];
    for (let x = simCode; x > 0; x &= x - 1) {
        simVal++;
    }
}

看似只改了一点，但是这样处理一个 32 位的simCode最多只需要循环 6 次，而且处理一组 5 个的teamCode最多只需要运算 5 + 6 = 11 次，这是十倍的优化！

细说原理：x &= x - 1可以将x的最后一个 1 变成 0，因为减法借位只影响最后一个 1 及之后的数。比如：

  1011100  // 92
& 1011011  // 92 - 1 = 91
----------
  1011000  // 88 = 92 - 4: 倒数第三位 1 变成了 0

正如New Bing所说，新算法的迭代次数和 1 的个数是相等的。而受限于队伍长度，一组simCode最多只包含 6 个 1，x &= x - 1在这个场景的下降速度是飞快的。

感谢New Bing，现在我们有了新的美妙的队伍数据库查询算法，查询速度提升到 1 毫秒以内啦！

xujing691691

@Starmie 这东西就是以前那个树状数组的lowbit(x) = x&(-x) 获得最低一位的1...我看到这个需求第一反应就是这个函数
然后如果是c++的话可以考虑一下stl里面的bitset，原理大概就是这东西是把32个连续的位压缩成int，对两个位组作逻辑运算的复杂度会除一个32的常数，里面有count()方法，可以试试看
不过这东西是不是负优化还不好说
edit:晚上回去我试试

Starmie

@xujing691691 JS没法操作内存，我甚至没法确定这五个数字在内存里是连续的orz
但确实可以试试用C/C++写一套外置的队伍数据库，但这样维护起来就很恶心了
另外JS的内置number类很神奇，我也不知道是怎么实现的
edit: 发现一个叫做Uint32Array的东西，这个应该是连续的了

xujing691691

@Starmie
突然发现npm里面有个bitset包(这不巧了吗.jpg)然后研究了一下

实验数据：随便取了一个32位含有6个1的数字

记录两个时间，分别是不用这个类的老方法(&=(x-1))、和拿已经预处理好的Bitset算的时间

看起来好像还是直接干拔快

然后我去简单看了一下这个包的源代码

74c1e1ae-f747-4509-8c40-373265eafe5d-Q0YU7$T.jpg

然后我想看看这东西是咋实现的，简单又翻了翻源码，发现了个函数

容易发现这个方法的时间复杂度是固定的，在稀疏下的场合应用不怎么好，但是很稳定，然后我试了一下1多的场合，这个方法明显比上面的按位减快很多，但是有一个问题是这个方法还是不够优，毕竟这个乘法看着很吓人

鸽了
edit:前面一边试队伍一边写的自己逻辑都看不下去...精简了下语言
edit2: https://zhuanlan.zhihu.com/p/341488123
这里面讲的比较详细，其中好像没有那个大乘法，所以那个乘法为什么会跑的效率还行呢...搞不明白
edit3:
我错了，我忘了vue里面调用方法的效率奇低无比

随便找了一下知乎的这个算法，看了一下时间

按位&的问题是计数器的加法和x的判空不得不忽略，这样导致开销远大于大量移位和&的算法

半熟。

美妙のspeed