简介🔗

最近花了大概三周的时间写了一个通过dota2阵容来查录像id的HTTP接口dota2-match-finder，这里简单写篇博客记录一下。由于我不会写前端，所以没有界面，只有一个简单的HTTP接口，当然后端部分算是比较齐全的，如果最终补上前端界面之类的东西，那么效果会类似于这个现有的网页：combo。做这个事情的缘起也是因为这个网页，我之前偶尔会需要这个功能，比如偶尔刷到什么dota2视频，想看看什么段位，这时候用来找录像是很不错的，不过我感觉这个网页速度挺慢的，而且一些早期的录像应该也是找不到（这个问题很难解决）。我对这个事情正好有一些兴趣，失业也有时间就随便写了一下。

原理🔗

首先说一下为什么能做这件事，所有的dota2公开对局，服务器上都会有记录，V社提供了网页API可以查询，用户只需要在steam上有过一些消费就能获取一个key用来请求这些API，但是V社本身并没有直接提供类似的功能接口，所以如果我们要做这个事情，我们首先需要做的就是获取到这些比赛数据。在公开的API里，有一个API可以用来获取最多100盘比赛的比较详细的信息，而且这个API可以指定一个起始编号，返回从这个编号开始的最近的若干场比赛数据。最终这些数据会以json或者xml的格式返回，我们需要做的就是解析这些文本，再将我们感兴趣的数据保存到数据库里方便后续查询。

返回示例如下：

{
  "result": {
    "status": 1,
    "matches": [
      {
        "players": [
          {
            "player_slot": 0,
            "hero_id": 10,
            "item_0": 1,
            ...
          },
          ...
        ],
        "radiant_win": true,
        "start_time": 1730544120,
        "match_id": 8015500293,
        "match_seq_num": 6742154810,
        ...
      },
      ...
    ]
  }
}

这里为了简洁去掉了大部分的字段，在这些字段里，对我们做这个事情来说，所需要关注的字段只有match_id, match_seq_num以及各个玩家的player_slot和hero_id，match_id和match_seq_num都是一场比赛的有序编号，至于他们之间的区别我并不太清楚，一般我们在客户端或者数据网站使用的是match_id，但这个API需要我们提供的是match_seq_num，而player_slot记录了玩家是天辉还是夜魇，hero_id则记录了玩家使用的是什么英雄，通过这些信息我们就能知道一场比赛的比赛编号和阵容，从而实现我们的目的。这一步我们要做的就是解析这些数据并将其存到一个数据库内。

假设我们已经获取到了我们所需的比赛数据，下一步我们就需要考虑，如何保存这些数据，以及如何查询这些数据来达到比较快的查询速度。最简单的方式，就是原样保存这些数据之后，每次查询时依次获取每条比赛记录，判断是否符合特定阵容来进行筛选。从这种最简单粗暴的方式进行优化，我们有两个可能的优化方向，第一个是减少需要查询的数据量，这就要说到一个常用的优化方法：倒排索引。

倒排索引🔗

倒排索引是一种常用于搜索引擎优化的方法，一般搜索引擎需要快速的查询出同时包含用户提供的若干关键字的网页，倒排索引的思路就是建立一个从关键字到网页编号的倒排索引，比如用户查询A和B这两个关键字时，搜索引擎的后端就分别把包含A和包含B的网页编号取出，再进行求交运算，即可得到同时包含A和B的网页编号。这个方法是典型的用空间来换时间，因为除了原本的网页信息之外，还需要保存这个可能规模非常大的索引。而这个方法能提高查询速度的原因之一就是他减少了我们查询时需要读取的数据量，之前我们需要把所有记录全部读取一遍，现在通过这个索引我们就能只读取自己所需的那一小部分了。

具体到我们这里的问题来说，我们希望用户查询时，能够像opendota combos那样，指定双方的阵容（不假定具体的阵营），我们可以分别保存比赛的原始数据，再维护一个(hero_id, side)到match_id的索引。这样用户指定两个阵容时，我们能够通过正反两次查询得到所有满足要求的比赛编号，再具体查询编号对应的比赛数据返回给用户。

这里我们需要应对的第一个问题是存储空间的问题，dota2目前为止大概有几十亿场比赛数据，在不考虑原始数据的情况下，以每场比赛10人，比赛编号是一个64位整数算，未压缩的索引需要占用大约 50_0000_0000 * 10 * 8 / 1024 / 1024 / 1024 = 372.5GiB，考虑压缩率为0.2，那么我们也需要74.5GiB的存储空间用来保存这些索引。假设我们只保存我们所需的最小的数据量，一场比赛的比赛id和10个英雄id，我们大概需要83.8GiB，考虑压缩率之后大概为16.7GiB（很理想，实际上大约为65GiB），可以看到索引的空间还超过了原始比赛的空间。

另外一个需要考虑的问题就是求交运算，按照opendota的数据，英雄出场率一般在0.5-26%不等，那么这个比赛编号的集合最小也达到了2500万的规模，这个大小对于求交运算来说显然有点过大了，甚至于要把这么多比赛编号加载到内存里就需要大概0.18GiB内存。所以如果我们要采用倒排索引的方法，而且我们最终想要收集到所有的数据，那么我们需要根据比赛编号的另一个特征进行优化。那就是比赛编号都是有序的，虽然貌似没有明确的地方表示这些比赛编号是完全有序的，但我们完全可以认为至少绝大部分的比赛编号是按照顺序生成的，在这个前提下，我们可以对比赛编号分段处理，比如每100万一个段，而且这样在我们返回时，也可以优先返回最近的比赛。

位运算🔗

另一个我们可以尝试的优化方向则是如何进行筛选，如果我们不做任何优化，那么之前的筛选是一个子集判定问题，即用户提供了一个阵容组合，我们对每一场比赛，都判定这个特定的阵容组合是否是该比赛的阵容的子集。而当碰到类似这样的问题时，我们总是容易想到使用位运算来做一定的优化，这是因为位运算的按位与或者按位或都非常适合用来做集合元素数量有限情况下的子集判定。而通用情况下，我们一般需要使用哈希表来做，相比之下，哈希表的速度就会慢一些。具体到dota2，我们的阵容是一个hero_id的集合，目前dota2的英雄id在1-145之间，0表示未知英雄，1-145之间还有一些数字未使用，但可以看到，所有英雄id都在u8的范围也就是0-255内，即使考虑到将来的更新，我们也能比较自信的认为，有生之年dota2的英雄id也不会超过255，因此我们可以使用1个256位的二进制整数来表示一个阵容的掩码，这样通过对掩码进行按位与或者按位或运算，我们就可以轻松的判定一场比赛是否有特定的英雄组合。当然，这里考虑到我们的需求，我们实际上需要2个256位的二进制整数，分别用于表示天辉和夜魇的英雄组合掩码。

进一步优化？🔗

位运算和倒排索引其实是不太能结合起来的，因为使用倒排索引的时候，子集判定被转化成了集合求交的问题，也就不需要位运算了，但是如果我们只是采用倒排索引用空间换时间的思路，而不实际用倒排索引的思路，我们实际上可以用大概10倍的空间换大概10倍的查询速度。简单来说就是我们构建一个倒排索引，但是相比之前只保存比赛编号的索引，这个索引里我们同时保存比赛编号和掩码，同时我们不将所有用户指定的英雄的索引读取出来，而是在其中选择一个出场率最低的英雄，只在这个英雄对应的索引里查询，查询也不是求交，而是做掩码操作。但这个方法几乎要求10倍的存储空间，而带来的查询速度提升则取决于英雄的出场率，处于4-200倍之间，感觉对存储空间的利用不够，尤其是对于希望减少使用存储空间的我们来说。

实现🔗

最终我们的要做的事情大概分为三步：收集，保存，查询。至于使用的语言，我能够使用的比较熟练的语言有C/C++/Python/Rust，这里我们选择Rust。

收集🔗

收集这一步，网络方面请求HTTP接口有现成的库(reqwest)可以解决，而且Rust这边还能用上比较时髦的异步编程，这也是不错的，虽然我们其实也不算很需要异步。这一步真正工作量比较大的部分是结果的解析，得益于rust优秀的类型系统和宏，以及serde库优秀的设计，实际上解析非常简单，我们只需要定义对应的结构体，就能通过自动推导Serialize和Deserialize这两个trait，直接使用serde_json来进行对应的解析。

收集部分比较麻烦的是V社对API的请求频率限制，目前DOTA2每分钟的比赛场次大概在300到1200盘左右，按每次100盘算，我们需要大概每5-20秒请求一次才能跟上最新数据，同时我们还需要尽可能的收集历史数据。而实际上只需要大概8秒请求1次就会触发V社的Too Many Request响应，虽然这并不是硬性的限制，但是我们实际上能请求的频率也是比较有限的。我们也不太可能做分布式的收集，所以基本上要将之前的历史数据收集齐是没戏了。

对于历史数据，由于API指定的是起始编号，我们采取了从后往前，对历史数据分段进行收集的策略，每段内部我们从前往后进行收集，同时我们记录下已经收集完毕的分段，方便当收集中断之后恢复。

保存🔗

收集部分完成后，需要考虑的就是如何保存的问题，这里包括选择什么数据库，具体保存那些内容，这里稍微提一下，我是在阿里云买了一个99块1年的低端VPS做这个事情，配置大概是2GiB内存，40GiB硬盘，存储空间显然非常有限，我们最好是尽量减少存储空间的使用。因此我们最终选择放弃倒排索引，所有的比赛数据里，我们也只选择存储绝对必要的内容。至于掩码部分，由于直接存储掩码要求差不多2倍的存储空间，所以我们直接保存2个阵容数组，而选择在查询时动态生成掩码。最终在Rust里，我们保存的数据看起来是这样的

pub struct MatchDraft {
  pub match_id: u64,
  pub radiant: [u8; 5],
  pub dire: [u8; 5],
}

将原始数据转换成这里的数据是比较简单的，这里我假定了每盘比赛双方都是5v5，偶尔V社的服务器会返回一些有问题的比赛数据，对于我们来说一般会碰到的问题是双方的阵容不是5v5，而是6v4或者其他情况，比如8042629407，我基本上选择忽略这些极少数的奇怪数据。

数据库方面我最终选择了ClickHouse，因为这个基本上是我接触的比较多的数据库了，而且我对CH的性能和功能也比较满意，当然CH对我的低端VPS来说算是一个很大的负担，不过我暂时还没有找到其他更合适的替代品。

出乎意料的，使用Rust将数据写入CH或者从CH查询数据都相当简单，CH官方的Rust接口设计的相当易于使用，通过自动推导Row/Serialize/Deserialize这三个trait，我们就能很简单的做到插入和查询，同时我们还能做一些比较简单的创建数据库和表的操作，这基本上已经可以满足我们这里所有的需求。

另外值得一提的是为了提升插入性能，我们需要收集一大批数据再一次性插入，这是因为我们使用的是CH的MergeTree引擎，每条插入都会创建一个临时表，然后在后台进行多表合并。如果你用了大量的插入，那么这些后台合并操作会消耗很多系统资源。由于我们每次请求API都能获得最多100场比赛数据，不过我还是默认设置成等收集到1000场比赛数据才进行一次插入。

查询🔗

这部分我们需要提供一个HTTP接口，我选择了axum这个crate，当然这也是因为这个是我稍微接触过的相关crate，这个使用起来也比较愉快，在接到请求时，我通过用户提供的参数来构造一个SQL语句来向CH进行查询，再将返回的数据返回给用户，相当直观。

如果你想尝试一下这个接口，那么这里我给一个简单的示例：

DOTA2里敌法师的英雄id是1，斧王的英雄id是2，假如我们想要查询一些斧王对敌法师的比赛，那么我们可以用curl构造一个这样的HTTP请求。

curl -X POST "http://120.27.145.242:8888/" --header "Content-Type: application/json" --data '{"team1": [1], "team2": [2], "count": 10, "offset": 0}'

这里的ip和端口当然是我服务器的公网ip和服务绑定的端口，count是场次，默认为10，最大为100, offset是分页的参数，默认为0。返回的结果大概是类似这样的：

[{"match_id":8049200000,"radiant":[63,42,2,31,61],"dire":[86,1,114,121,75]},{"match_id":8049196697,"radiant":[121,56,71,2,101],"dire":[51,86,1,15,97]},{"match_id":8049194746,"radiant":[2,8,103,39,63],"dire":[145,45,1,21,131]},{"match_id":8049194081,"radiant":[1,72,104,84,68],"dire":[2,22,88,39,99]},{"match_id":8049191156,"radiant":[75,86,36,1,71],"dire":[89,126,35,2,14]},{"match_id":8049189562,"radiant":[2,104,6,135,33],"dire":[72,43,126,1,37]},{"match_id":8049189309,"radiant":[61,6,67,19,1],"dire":[2,8,91,41,47]},{"match_id":8049188191,"radiant":[123,5,58,1,89],"dire":[2,48,64,45,14]},{"match_id":8049187394,"radiant":[45,135,1,102,74],"dire":[39,6,2,131,27]},{"match_id":8049186263,"radiant":[60,1,10,85,30],"dire":[97,94,2,51,101]}]

由于我并没有保存其他数据，所以这里能获取的只有比赛id和双方阵容，如果你想看到具体数据，或者下载对应的录像，你可以去类似opendota，dotabuf这样的DOTA2数据网站，或者官方客户端。

当然由于这个程序只从11月22号晚上开始收集，并且在DOTA2高峰期时，V社的API限制让我们无法跟上最新数据，一场比赛的数据可能需要大约几分钟甚至几个小时才能进入数据库，所以如果你找之前或者特别新的比赛，你很有可能是找不到的。

总之这就是全部内容了，整个仓库其实目前只有大概900行代码，很多部分也是做的非常粗糙，不过我也没有太多热情去做这个事情了，如果我有很多高性能服务器能让我玩耍，那我可能更有兴趣去优化这个东西，不过目前只能说就这样吧。