接口慢了两百毫秒,最后是一张表的问题

难度 ★☆☆☆☆ · 前置:无 | 一句话结论:这次变慢跟算法的复杂度没关系,是一张按 id 逐个查的表被写成了链表遍历。

2023 年 6 月我入职第三天,组长把后台一个订单列表接口丢给我,说它比上线前慢了两百毫秒,让我先把日志翻一遍。我点头点得很快,心里想的是两百毫秒能有多难找,日志一拉不就看见了。那天下午我在测试环境点了十几遍,浏览器网络面板里那一条一直停在三百一十毫秒上下,上线前的基线没人记得,能对上的只有组长那句话。

结果我找了三个多小时。

我先把应用日志拉开。每次请求收尾之前都跟着一串一模一样的行,一行一个订单号,一千行,紧挨着的是查库耗时,个位数毫秒。剩下的两百多毫秒在这份日志里找不到出处,它不在 SQL 里,也不在那段序列化里,像是从请求自己身上长出来的。我把日志按耗时重排了一遍,排在最前的是查库,第二位是写日志,两个加起来离三百毫秒还差着一大截。

那会儿我刚学 Go 不到一个月。

我能想到的费时间的去处就那几个:SQL 慢、响应体大、日志写太多、机器不行。就按这个顺序往下排,一个一个试。这个做法很土,就是把怀疑的地方一处一处量一遍,量到哪一处跟总数对不上,就把那一处划掉。它也慢,可有个好处:划掉的地方不会回来找你。那天我在纸上画了一条三百一十毫秒的时间轴,把查库、序列化、写日志三块按量到的数标上去,三块加起来只占一小半,中间空着一段谁也对不上的空白。排到最后,纸上只剩一条没标数的横线。没人教过我怎么排,我就这么一路往下划。

SQL 和序列化都不用再看了

第一条查得最快。EXPLAIN 出来,索引走的是 idx_created_at,扫描行数跟返回条数对得上,没有回表,也没有临时表。我又把这条 SQL 单独拎到客户端里跑,跑十次都停在一个量级上。

数据库这边没话说。

第二条花了半天。响应体三百多 KB,序列化确实要花时间,可那部分时间在旧版本里一样要花,它撑不起新旧之间那两百毫秒。我把两个版本的响应体各抓了一份逐字段对比,字段数一样,只有两个字段的值变了。这个接口上线三个月,结构体总共加过两个字段,加字段那次的发布记录我还翻到了,那天没有人报慢。

两条都排掉之后,剩下的只有那段取数的代码。它四十来行,我念第一遍觉得没问题,念第二遍还是觉得没问题,第三遍才开始怀疑自己根本没看懂它在干什么。

那张表其实是条链

问题在一个字段上。

结构体叫 order,前面是 id、金额、下单时间,最后一个字段是 next *order。表是从库里捞出来的最近订单,落进内存以后被串成一条单链表,头插法,最新的挂最前面。取数的地方是个双层循环,外层是请求里那一千个 id,内层从链表头开始一个一个往下比,比中了就跳出。链表没有下标,要找第几个只能从头数过去,平均要走过五百个节点。

1
2
3
4
5
6
for p := orderListHead; p != nil; p = p.next {
if p.id == id {
sink += p.amount
break
}
}

一次请求五十万次比较。

全花在找一个本来就躺在里面的元素上。写这段的人没做错什么,他要的只是按 id 找到那一条,链表也能做到。不对的地方在于它是在一个本该按下标取的地方,用了一个没有下标的容器。

我在自己机器上把这一千行重放了一遍

改法我想了半天,最后定下来只有一句:换成切片,取的时候按下标。改之前我想先量一次,看看这一处到底值多少。线上那个接口我没权限挂分析工具,就把这段取数原样抄回自己机器,规模缩到一千行,两边各跑一遍。机器是这台笔记本,windows/amd64,每组跑五次取中位数。

1
cd _local/ds-exp/d0 && go test -bench='Lookup' -benchmem -count=5
写法 一千次查找
链表,每次从头走 993 µs
切片,按下标取 1.24 µs

八百倍。

这个数出来的时候我在椅子上坐了一会儿。在我脑子里,链表慢是慢,慢个两三倍顶天了,何况它插入删除是 O(1),切片往中间插是 O(n),教科书上写得清清楚楚,我一直觉得这笔交换是划算的。八百倍这个数没法用划算或者不划算来形容,它更像是两个东西根本不在一个量级上,只是碰巧都被写成 O(n)。

我把这八百倍拆成两笔账。

一笔是走路。链表版每查一条都要从头数,一千次查找走掉五十万个节点;切片版取一千次,走的是一块连续内存。另一笔是每一步的价钱。五十万步花了 993 µs,一步不到两纳秒;切片取一千次花 1.24 µs,一次一纳秒出头。两笔乘起来才是八百,走路那笔占五百倍,单价那笔只占一点六倍。这个拆法有点扫兴,它说明八百倍里的大头是走得太多,不是缓存。可再往下问一句:链表为什么非得走那么多步?因为它没有下标。它为什么没有下标?因为它的元素不在同一块内存里,只能靠 next 一个个指过去。切片取一个元素是一次地址加法,链表取一个元素是一次指针追逐。被换掉的东西就在这里,只是它平时藏在两行代码的差别里,看不见。我把这段取数抄回去之前还想过另一条路,把链表接成一个 map,id 到指针,查一次就是一次哈希。那条路能跑通,可它等于把链表整个拆掉重做,还要多占一份键值对的内存;换成切片只需要改一行容器声明。我选后者,不是因为它更快,是因为它改得少,回滚起来也少。

不挨着要贵多少,我又量了一组。

同一份数据,节点挨着和散着差五十七倍

一千万个 int64,装进三种容器,做的都是同一件事:顺序遍历一遍求和。

容器 一千万次遍历
扁平切片 13.5 ms
链表,节点顺序分配 30.4 ms
链表,节点打散分配 1735.9 ms

最上面两行差 2.2 倍,最后两行差 57 倍。三份数据一模一样,三份的 O(n) 一模一样,唯一的区别是节点在内存里挨不挨着。同一份链表,同一段遍历代码,把节点建好之后随机洗一遍再串回去,就从 30.4 ms 变成 1735.9 ms。

这里没有算法的事。

内存不是按元素读的,是按行读的,一行六十四字节。节点挨着的时候,读第一个顺手把后面几个的地址也捎回来了,预取器跟得上;节点散着的时候,每读一个都得等一次内存,等的几十纳秒里核在空转,预取器也猜不出下一个在哪儿。

链表节点在内存里挨着放和散着放的两种布局

指针追到哪儿,就得等到哪儿。

把三组数叠在一起,那张订单表的问题就清楚了。链表让它多走了五百倍的路,散着放的节点又让每一步贵出几十倍。这两笔账我只能在本地分开量,线上叠起来到底是多少我没法验证,只能说方向是定的:如果那批订单的节点像业务代码里常见的那样散着,八百倍只会更大。

O 一样,常数项差三个数量级

跟链表没关系的地方也能撞上同一件事。一百万个 int64 乘二,装进一个新切片,两种写法:一种从空切片开始 append,一种先 make 出长度再按下标写。

写法 耗时 分配次数 分配字节
空切片 append 14.9 ms 37 次 41.7 MB
预分配长度,按下标写 3.5 ms 1 次 8.0 MB

同一件事两种写法的耗时与分配次数对比

循环次数一样,O 也一样,一个 14.9 ms,一个 3.5 ms。差的那四倍多不在算法里,在两件事上:那块内存涨了 37 回,每涨一回都要把老数据搬到新地址;以及多出来的三十几兆字节,搬来搬去全在内存里兜圈子。

空切片 append 每次容量不够都要申请一块更大的,把老数据整块搬过去,再释放旧的。搬的时候除了读写带宽,还得等 GC 来收拾那些被扔掉的老块。预分配把这两件事一次省掉。我拿这组数去问过一个比我早两年入职的同事,他说这不就是 make 的时候给个长度吗。我说是啊。他说那你写这么长一篇干什么。我当时没答上来,过了一会儿才想清楚:知道要给长度,和知道为什么该给长度,中间隔着一次把 37 次分配到 1 次分配数出来的过程。前者会忘,后者不会。

这三组数放在一起,是我这段时间最大的收获:O 只告诉你增长的方向,不告诉你起点在哪儿。 同一张复杂度表上,链表和切片都记作 O(n);落到机器上,八百倍差不多是三个数量级的差距。800 倍、57 倍、4.3 倍,没有一个能靠复杂度分析推出来,每一个都得把代码跑起来。

我原来以为这类事靠背,背下每条数据该装进哪个结构。后来发现装法是可以算的:先问这条数据以后要按什么取,按下标、按 key、还是按一段范围;再问一次要碰多少条;最后问这些节点是不是一起建出来的。三个问题问完,能选的容器通常只剩一两个。

这三问可以一直往下钻。这里不讲刷题,刷题练的是从零推一个解法;工程里更多时候是从一堆已经躺在磁盘上的数据里挑一个摆法,两件事用的不是同一套力气。往下每碰到一个结构,我都是这个路子:先问它把什么变便宜了,再问便宜在哪一步,最后把数跑出来。量不出来的地方我会写量不出来,不拿形容词顶上。

便签上那三条

那个接口最后改了多少行我没数,改法就是前面那一句:链表换成切片,取的时候按下标。改完我给自己定了三条规矩,写在便签上贴在显示器右边框。

第一条,动手之前先问取法。按下标取的,别用链表;按 key 取的,先想哈希;按范围取的,才轮到树。取法定不下来的时候,说明我还没想清楚这段代码在干什么。

第二条,容器要有下标。

能在切片上按下标解决的事,不引入指针。链表在我手里只留两种场合:只在两头动,或者我在实现一个已经有人用惯了的结构。

第三条,改之前先量。

量不出来就先别改,因为你分不清自己是在优化,还是在换一种写法。这条最费时间,也最容易被跳过。

三条写完,便签刚好占满半张,右边还剩一块空白,等着往下加。