全部文章

Steam Inventory Value

公平的轮流,却饿着了新来的:修一个轮流收录价格的爬虫

我们的 Steam 价格爬虫按「谁逾期最久」在几个游戏之间分配很小的请求额度。这对已经在队里的游戏很公平,却让新加的游戏为了四分钟的工作等上两天。

4 分钟读完

Steam Inventory Value 用一份市场价格缓存来给 Steam 库存估值。一个跑在 Postgres 里的爬虫负责让缓存保持新鲜:每分钟最多抓两页某个游戏的市场目录,每页 100 件。额度故意设得很小,因为 Steam 会限制请求量。

每分钟两页,要分给我们支持的所有游戏。这篇文章讲我们当初怎么分、为什么这种分法对新游戏悄悄失效,以及后来加的一条小规则。

轮流的方式

每个游戏有一个更新间隔:Dota 2 和 CS2 是 6 小时,TF2 和 Rust 是 12 小时,Steam 卡片是 24 小时。爬虫每次挑相对于自己的间隔逾期最久的那个游戏:

select appid from crawl_apps
where enabled
order by (cycle_started_at is null) desc,
         extract(epoch from now() - cycle_started_at) / (refresh_hours * 3600) desc nulls first,
         sort
limit 1

一个间隔 6 小时、这一轮在 12 小时前开始的游戏,得分是 2.0;同样 12 小时前开始、但间隔是 24 小时的,得分是 0.5。得分最高的先收。一个游戏收完一轮就开始下一轮,时钟归零,排到最后。

这是加权的轮流。对已经在队里的游戏来说很公平:热门游戏轮到的次数多,也没有谁会永远被跳过。

没算清楚的一笔账

各个游戏的目录大小差很多:

游戏物品数页数
Steam 卡片约 325,0003,254
Team Fortress 244,617447
Dota 234,568346
CS213,352134
Rust5,57856

加起来大约 4,200 页。每分钟两页,全部收一遍大约要 35 小时。

所以没有任何一个游戏是按它的间隔在更新。稳定下来之后,每个游戏都在得分达到差不多同一个值时轮到,这个值就是总工作量除以额度。我们算出来大约是 2.2。「6 小时」的游戏大约每 13 小时更新一次,「24 小时」的大约每 53 小时一次。

这我们可以接受:缓存的价格 7 天内都有效,而且客人真正在等的物品是一件件单独查的,排在任何目录页前面。

出问题的地方

11 月 4 日我们加了 PUBG:357 件物品,四页的工作量。

新游戏从来没收过,所以会先收一次。它抓了第一页,时钟开始走,得分变成零。一天之后,它还停在 357 件里的 100 件。

代码没有错。PUBG 只是在等自己的得分超过那些已经逾期一天半的游戏。间隔 12 小时的话,大约要等 26 小时。隔天加的三个游戏间隔是 24 小时:它们要等大约 53 小时,才轮到那几分钟的收录。

后台的「立即重新收录」按钮也有同样的毛病:它把时钟清掉,游戏拿到一页,然后又排到最后。

修法

在稳定状态下公平的轮流,并没有规定新来的怎么加入。所以我们加了一条规则:还没收完过一轮的游戏排最前面,目录小的先。收完第一轮之后,它就跟其他游戏一样轮流。

用一个栏位记录收完过几轮:

alter table crawl_apps add column if not exists cycles_done int not null default 0;

推进进度的函数在一轮收完时加一,挑选的函数把还是零的游戏排到前面:

select appid from (
  select a.*,
    (a.cycles_done = 0 and (
      select count(*) from crawl_log l
      where l.appid = a.appid and l.kind = 'page'
        and l.status is distinct from 200 and l.at > now() - interval '1 hour'
    ) < 3) as catching_up
  from crawl_apps a
  where a.enabled
) a
order by catching_up desc,
         case when catching_up then coalesce(total, 0) end asc nulls last,
         (cycle_started_at is null) desc,
         extract(epoch from now() - cycle_started_at) / (refresh_hours * 3600) desc nulls first,
         sort
limit 1

里面那个条件是保险。如果一个游戏插了队,却每次请求都失败,它会挡住所有其他目录。所以新游戏的目录请求如果在最近一小时内失败三次,就先失去优先权,直到不再失败为止。

小的先收,是经典的「最短工作优先」:小目录几分钟就收完,这样在等的游戏最少。

动正式环境之前先检查

爬虫的 SQL 有测试,会在一个进程内的 Postgres(PGlite)里跑真正的迁移脚本。我们加了三个测试:新游戏先收完第一轮才恢复轮流、两个新游戏里小的先收、一直失败的新游戏不插队。

然后我们把新的排序当成一个只读查询,在正式环境跑了一次,看它会挑谁。结果列出四个在等的游戏,小的在前,后面是原来的轮流顺序,没有变。

结果

改动套用两分钟后,PUBG 收完了。下一个有 460 件物品的游戏,再过两分钟也收完了。趁它在跑,我们又排进了三个游戏。七个新游戏加起来约 17,700 件物品,在改动后一个半小时内全部收完。

代价是大目录在这段时间暂停了。价格有 7 天的有效期,没有人察觉。

我们学到的

  • 一个在成员之间公平的调度器,仍然需要一条「怎么加入」的规则。
  • 把工作量加起来算一算。我们的间隔写的是 6、12、24 小时,而额度实际能做到的大约是它们的 2.2 倍。那些间隔其实只是权重。
  • 任何能插队的东西,都要给它一个失去特权的办法。

试试看

Steam Inventory Value 免费、不用登录:https://steam.2cstudio.app。贴上 Steam 个人资料链接,它就会给整个库存估值。

作者:2C Studio,一间小工作室。

试试看

Steam Inventory Value

steam.2cstudio.app

更多文章