Hi，欢迎来到 卡瓦邦噶！我是 laixintao，现在生活在新加坡。我的工作是 SRE，喜欢在终端完成大部分工作，对各种技术都感兴趣。我从 2013 年开始写这个博客，写的内容很广泛，运维的方法论，编程的思考，工作的感悟，除了技术内容之外，还会分享一些读书感想，旅行游记，电影和音乐等。欢迎留下你的评论。
声明：本博客内容仅代表本人观点，和我的雇主无关。本博客承诺不含有 AI 生成的内容，所有内容未加说明均为博主原创，一经发布自动进入公有领域，本人放弃所有权利。转载无需本人同意。但是依然建议在转载的时候留下本博客的链接，因为这里的很多内容在发布之后会还会不断地继续更新和追加内容。
问题是这样，我们有 2 组服务器，A 组和 B 组，一部分用户从 A 组下载文件，一部分从 B 组下载文件。分成 2 组的初衷是，B 组用户下载量通常比较大，并且是离线服务，意味着可以慢一些，但不能影响 A 组用户。现在的问题是，A 组 和 B 组最终下载的来源都是 S3，依然存在共享资源，会出现问题：在下载量比较大的时候，占用全部的 S3 上传带宽，导致 A 组用户收到影响。
我们希望限制 B 到 S3 的带宽，比如 10Gbps.
有几个限制：
这个问题的难点在于：流量整形一般都是做在 egress 的，因为 egress 天然有一个 queue，发送端可以决定在什么时候发出去 packet，从而把发送速率可以稳定控制在一个想要的比例。
但是我们这里的场景是 ingress，对于 ingress 是没有 queue 的，流量整形一般也无法作用在 ingress ——因为包已经被物理网卡收到，DMA 完成，作为 ingress 侧是无法决定这个包什么时候到达的，只能决定怎么处理这个包。所以 ingress 侧一般是 classification, action，即 drop。
基于 Drop 的 policing（真形象的名字，超速开罚单的警察） 就有一个问题：由于 TCP 的拥塞控制机制，发送的带宽会逐渐上涨，最终会超过 10Gb。限流开始生效时，sender 瞬时发送速率超过 10 Gbit/s，并持续消耗 policer 的 token；当 token 不足时，后续 packet 被判定为 exceed 并丢弃。
大量包被丢弃导致 TCP 的发送端认为发生了拥塞，会大幅下降 cwnd。实际测试，如果用 policing，实际能跑的速度大概在 5-7Gb，而且不稳定。
以下是一个模拟环境，使用 policing 限速在 1Gbps，其 throughput 如下图所示：
再看 window scaling，可以看到 outstanding bytes 的上包络线呈现出明显的 AIMD/CUBIC loss-response 特征；结合 sender 侧的 ss -ti 可以确认 cwnd 在 loss 后也发生了类似下降——在上升到一定的大小之后，就会因为超过 policing 的限速而被 drop 一些，TCP 在发现有丢包之后，就降低 cwnd，从而降低发送速度，符合 AIMD。（这个环境用的拥塞算法是 cubic，默认的参数 cat /sys/module/tcp_cubic/parameters/beta 是 717，下降的比例是 717/1024 ≈ 0.7，和图中相符，图中是从 500kb 下降到 350kb）。
这样用户就不高兴了：为什么实际只能用到 5Gb 左右，不是说好了 10Gb 的吗？
如果要做到规整的 10Gb，这里就需要用到流量整形了，traffic shaping。
Linux 有一个特殊的驱动：ifb，全称是 Intermediate Functional Block，是一个虚拟网络设备，主要用来把原本的 ingress 流量重定向到一个“可做 egress qdisc”的设备上，从而实现 ingress shaping。
本质上，就是在收包链路上加一个网卡绕一下，这个网卡会调用 egress 的代码，这样我们就可以使用 tc 原来的逻辑做 egress 的 traffic shaping 了。
加上 ifb 虚拟网卡之后，包的路线如下：
在 ifb_xmit() 的时候，看起来是一个负责发送包的代码，实际上它的逻辑是：修改 skb 的 dev 为原来真实的进来的那个 dev1，（而不是 ifb 这个虚拟的），然后进入到 netif_receive_skb() kernel 网络栈里面。
这样，我们就可以用这个 egress 的 qdisc 做 shaping 了。
实现的代码如下：
第一步，创建 ifb 虚拟接口，并且把流量从物理网卡 redirect 到 ifb：
|
1 2 3 4 5 6 7 8 9 |
modprobe ifb ip link add ifb0 type ifb ip link set ifb0 up tc qdisc add dev bond0 handle ffff: ingress tc filter add dev bond0 parent ffff: protocol ip u32 \ match u32 0 0 \ action mirred egress redirect dev ifb0 |
第二步，创建一个 HTB，有 2 个 class，一个有限速 10Gb，另一个没有，可以跑到物理线速。
|
1 2 3 4 5 6 7 8 9 10 |
tc qdisc add dev ifb0 root handle 1: htb default 20 tc class add dev ifb0 parent 1: classid 1:1 \ htb rate 50gbit ceil 50gbit tc class add dev ifb0 parent 1:1 classid 1:10 \ htb rate 10gbit ceil 10gbit tc class add dev ifb0 parent 1:1 classid 1:20 \ htb rate 50gbit ceil 50gbit |
第三步，把要限速的 IP 放到 1:10 class：
|
1 2 3 |
tc filter add dev ifb0 parent 1: protocol ip prio 1 u32 \ match ip src $ip/32 \ flowid 1:10 |
然后测试吞吐，证明实际的 throughput 稳定在 956 Mbits/sec。
这样就达到了我们的目的：这条链路的速度稳定地使用限速 1Gbps 左右。
有几个小问题值得讨论。
为什么是 950 Mbits/sec 而不是 1Gbits/sec？
tc 做限制的时候，计算的是 skb 的 size，1500 Bytes，而这张图（以及使用的 iperf3 的显示）是计算的 TCP 的 body，即 MSS，1448 Bytes。1000 × 1448 / 1500 ≈ 965 Mbit/s。
在 cwnd 的图里面，刚开始的时候有一些丢包，为什么？
TCP 启动时通常先经过 slow start，cwnd 快速增长；进入 congestion avoidance 后，CUBIC 按三次函数继续探测可用带宽。发生 loss 后，它记录此前的窗口位置并降低 cwnd，随后重新逼近旧的 Wmax。
在这个图里面，只有一开始的时候有 loss，后续几乎没有 loss，贴着 throughput 发，说明 traffic shaping 做的不错。
按照 TCP 的拥塞控制算法，AIMD，即使是 traffic shaping 不也应该在最大窗口附近震荡吗？为什么这个图看起来这么平滑？
一个原因是，在逐渐逼近 1Gbps 的时候，limit 已经不是 cwnd 了，这种情况下 cubic 不会再激进地增加 cwnd2。通过 ss -ti 可以看到，大部分的时间卡在 sndbuf_limited:4688ms(29.6%)。
|
1 2 |
ESTAB 0 3646016 [::ffff:10.10.10.2]:5201 [::ffff:10.10.10.1]:59444 cubic wscale:13,13 rto:228 rtt:24.801/0.155 ato:40 mss:1448 pmtu:1500 rcvmss:536 advmss:1448 cwnd:2918 ssthresh:1717 bytes_sent:1893410080 bytes_acked:1889764624 byt es_received:37 segs_out:1307809 segs_in:652610 data_segs_out:1307808 data_segs_in:1 send 1.36Gbps lastrcv:15848 pacing_rate 1.64Gbps delivery_rate 961Mbps delivered:1305291 app_limited busy:15848ms rwnd_limited:12ms(0.1%) sndbuf_limited:4688ms(29.6%) unacked:2518 rcv_space:14600 rcv_ssthresh:42230 notsent:560 minrtt:3.024 |
如果调整一下参数，扩大 wmem，cwnd 实际也会震荡的。
最后一个问题也是最关键的问题，为什么在 traffic shaping 之后，cwnd 的变化速度变得这么平滑了呢？都是一样的 cubic 算法，为什么不像 policing 那样剧烈下降？以及为什么这里 send buffer 出现了瓶颈？
使用 policing 时，包进入 ingress 只有 2 中 action：
使用 ifb 的 traffic shaping 之后，ingress 的包进入物理网卡，被 mirror 到 ifb，然后在这里经过 queue 排队。经过流量整形之后，包到达 kernel 的网络栈，然后发出 ack。这里的关键是，tc 添加了一个漏斗，大量的包（当然，buffer 需要内存的，内存是有限的，如果大到一定的程度就只能 drop 了）进来之后都存起来，然后用固定的流速放出去。只有被放出去的包才进入网络栈，只有进入了网络栈，kernel 才会给 sender 发回去 ack，此时，sender 的 cwnd 才有了新的空闲，新的包得以发送。
再换一个角度解释一下，从 sender 的角度，假设 cwnd 是 4，sender 发送了 4 个包，在收到 ACK 之前，无法再发送新的包了。这时候，receiver 的 shaper 每秒通过一个包，即每秒会发回来一个 ack，这样，后续的每一秒，比如5，6，7，8，sender 都可以再发送一个包到网络上。
send buffer 是另一层限制。TCP 已经发送但尚未被 ACK 的数据仍然需要保留在 send buffer 中，以便发生丢包时重传。因此 IFB shaping 不仅延迟 ACK、限制 cwnd 中空间的释放，也会延迟 TCP send buffer 中已发送数据的释放。当 send buffer 不够大时，sender 甚至可能在 cwnd 尚未用满之前就受到 send buffer 限制。
所以 IFB 以固定速率释放数据后，ACK 也以相应的节奏返回。ACK 一方面释放 cwnd 中的 outstanding 空间，另一方面使已经确认的数据可以从 send buffer 中清除。两者共同使 sender 的发送节奏逐渐跟随 shaper 的速率。
即，网络上最多可以飞多少，是 cwnd/rwnd 等窗口决定；什么时候可以继续注入新 packet，则由 ACK clock 驱动。（而 ACK 也会让总的 cwnd 提高）。
以上就叫做 TCP 的 self-clocking3，ACK 本身就像“时钟脉冲”，会决定发送速度。
这个机制有一个关键就是包没有被丢弃，只是 ack 的时间晚了一些，如果包被丢了（比如 policing），那么 cwnd 会下降，无法匀速发送。
if (!tcp_is_cwnd_limited(sk)) return; https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_cubic.c?utm_source=chatgpt.com#L326 ↩︎ICMP 一直是我最喜欢的协议，在没有机器/设备的登录权限的时候，ICMP (ping) 可以让我在 debug 的时候获得很多关键的信息：网络通不通，延迟多少，有没有环路，经过了哪些设备，等等。其中比较关键的机制，一个是 ping 工具，即 echo/reply 机制；另一个是在 TTL 耗尽的时候发回来 ICMP 错误信息1，这是 traceroute 工具实现的基础原理。
在网上经常有人贴出来一些奇奇怪怪的 traceroute 结果2，有人找到很长的 traceroute 会很兴奋。所以…… 我想我们能不能用系统的方法找到 traceroute 比较长的 IP 呢？
虽然这个问题没有什么实际的意义，但是本文在探索这个问题的时候会遇到一些常见的技术，还是挺有意思的。
实验 traceroute 的起点，我们设置在新加坡。
新加坡是一个重要的交通枢纽。这是在写这篇文章的时候，新加坡附近起降的飞机（PS，新加坡的樟宜机场是我最喜欢的机场，如果你路过新加坡的话，建议给樟宜机场预留多 2 个小时的时间逛一逛）。
也是一个重要的海上枢纽。
在网络方面，新加坡也有丰富的海底光缆。
所以，预期最长的 hop 不会太高，现在世界的互联网越来越扁平了，一般一个互联网 IP 可以在 10-20 个 hop 触达。我用了一台 DigitalOcean 的机器来做这个实验，用它来 traceroute 1.1.1.1 只需要 8 跳，延迟在 1ms 左右。
回到本文的问题：找到一个 traceroute 最长的 IP，直观的方法就是 traceroute 每一个互联网的 IP。（本文只讨论 IPv4）
traceroute 对每一跳发 3 个包，超时时间 5s，最长 hop 尝试 30 跳。假设平均 15 跳完成，15 跳 × 3 探针 × ~100ms RTT = 5s，如果 IP ping 不通，那么 traceroute 可能要花 2min 以上。即使按照 5s 来算，我们 traceroute 整个互联网也需要：4,294,967,296 × 5 秒 = 21,474,836,480 秒 ≈ 680 年。如果开 1000 个并发，也需要 680 年 ÷ 1000 = 0.68 年 ≈ 248 天，大约8个月的时间。
怎样加快呢？
先来看一下现在的时间花在哪里了。traceroute 的逻辑是：对于目标 IP，发送 TTL=1 的包，等待回复，然后再重复 2 次；接下来换 TTL=2 的包，发送，等待回复，重复 3 次……
这样有两个问题：
对于本文的这个项目，我们是想找出来 traceroute 最长的一个 IP，而并不关心具体的路径。
要求高性能，我们换一个方式：不再使用发送——等待，我们设计两个程序，一个给所有的 IP 一起发送包，另一个监听收到的回应，如果是 ICMP 的 reply 包，就记录此 IP 可以 ping 通，如果收到其他的 ICMP 类型的包，直接丢弃即可。这样就完全没有等待时间了，而且之后两个程序，上下文切换的问题也解决了。
但是这就有了一个新的问题：我们怎么知道收到的包对应的 TTL 是多少呢？仅通过收到的 ICMP Time Exceeded 包是无法知道 TTL 消耗了多少的，怎么找到最长的 TTL 呢？
为了区分出来 TTL，我们分多轮进行扫描，先对所有的 IP 发送 TTL=1 的包，接收程序如果收到了 ICMP reply 的回应，说明这些 IP 在 TTL=1 的时候就能 ping 通，由于我们要找的是 TTL 越长越好，所以这些 IP可以直接淘汰了。接下来我们把 TTL=1 不能 ping 通的包，用 TTL=2 再发送一轮，如果能收到 ICMP reply，那么也可以淘汰了…… 假设我们在 TTL=30 的时候有一些 IP 能 ping 通，但是在 TTL=31 以及之后的时候没有任何 IP 可以 ping 通，那就说明这些 TTL=30 的 IP 就是胜者。
这样需要多久呢？
DigitalOcean 页面解释：All other Droplets have a maximum network throughput limit of 2 Gbps3. 每一个 ICMP 包的大小是：Ethernet 14 + IP 20 + ICMP 8 + payload 32 = 74 bytes，所以，理论上我们可以跑到：
2 Gbps ÷ (74 bytes × 8 bits) = 2,000,000,000 ÷ 592 ≈ 3,378,378 pps ≈ 3.4M pps
Ping 一次整个互联网只需要：
4,294,967,296 （2^32，所有的 IPv4 数量） ÷ 3,400,000 ≈ 1263 秒 ≈ 21 分钟
但是为了避免 overload 接受端（大量网段在同一个区域），以及中间设备可能存在的 conntrack，我们把速度限制在 100K pps，这样，只用了全速的 2.7%，ping 一次需要的时间是：
4,294,967,296 ÷ 100,000 ≈ 42,950 秒 ≈ 11.9 小时
对于我们的场景来说，也足够了。
使用我们自己的方式来发送 ping 包并且能跳过不需要的 conntrack 功能，就需要使用 kernel bypass 技术：
在收包程序上，直接看这个 IP 是不是一个合法的 ICMP reply，如果是，就记录 ping 通，如果不是就放通或丢弃。
但是 XDP 是运行在 kernel 的程序，如何把 ICMP reply 里面的 IP 信息记录到文件中呢？
Ring buffer4 在网络领域是一个非常常用的数据结构，它本质上是一个 buffer，生产方可以往里面写，消费方从里面读，是两个指针。它天然适合网络的原因是，buffer 的 head 和 tail 是相接的，自然而然就可以实现「如果生产方生产的速度太快，丢弃（覆盖）最早到达并且还没有处理的包」。（对于 BPF ring buffer，如果用户态消费得不够快、buffer 没有剩余空间，新的记录会写入失败。）
使用 BPF ring buffer （BPF_MAP_TYPE_RINGBUF），作为 kernel space 和 user space 的桥梁——kernel 往这个 ring buffer 里面不断写入可以 ping 通的 IP，用户态读出来这个 IP 记录到文件中。
接下来我们看用户态的程序。怎么存储这些 IP 呢？
我们可以使用一个 txt 文件不断 append IP，但是这样查找起来的话就是 O(n) 了。（不过我们只需要最后的几个赢家，大部分情况不需要查找，所以……还好啦）。另一个方案是使用一个数据库，比如 sqlite，查找快，不过大量写入的时候就有瓶颈。
看起来用最简单的文本好一些。
如果按照一个 IP 一行的格式，xxx.xxx.xxx.xxx\n，一共是 16 bytes，16 bytes * 2^32 就是 64GiB （最坏的情况）。
ping 一次就需要 64GiB！这也太多了，作为一个 hobby project，我们的目标是使用一个 $5 的 DigitalOcean VPS 来完成这个任务，磁盘只有 25GiB，远远不够。
有哪些字符可以简化呢？乍一看，首先是每一个 IP 的一个点，以及，IP 的每一个段实际有效数据是 0-255，但是可以表示的容量是 0-999，所以有很大一部分空间浪费了。
诶等等，IP 不就是 4 个 bytes 吗？这样的话我们可以把 IP 转化成一个 32位的 int：
|
1 2 |
>>> import ipaddress; int(ipaddress.IPv4Address('192.168.0.1')) 3232235521 |
这样的话每 4 bytes 是一个 IP 总共是 16GiB，缩小了 4 倍！而且，4 bytes 里面每一个组合都是一个合法的 IP ，完全没有空间的浪费。
等等，「每一个组合都是一个合法的 IP」——那是不是就意味着，我们从 0 数到 2^32，每一个位置都有一个 IP？这样的话，可以让每一个位置的 bit 位，如果是 1，表示这个 IP 能够 ping 通，如果是 0，表示 ping 不通（默认，文件初始化为 0）。而这个 bit 所在的 index（比如，是文件的第 3232235521 比特位，就表示 192.168.0.1 这个 IP），就表示 IP。
恭喜我们自己！我们刚刚发明了 bitmap！
但是每次 seek 过去，把要写入的 bit 组合成一个 byte，调用 syscall write，这也太麻烦了！
mmap 可以帮我们把文件映射到内存地址空间，我们只要操作内存就可以了，操作系统会在后台帮我们同步——定期把内存的修改写入到文件中。这可太方便了！
这样，我们 ping 一轮，就有一个 512 MiB（Exactly 512 MiB!） 的文件，里面存储了这一轮 ping 通的 IP。然后我们拿 bit 是 0 的 index 作为 IP，做下一轮的 ping，能通的 IP 会越来越少，直到得到一个冠军。
其实互联网大部分 IP 是 ping 不通的，尤其是我们刚开始使用比较小的 TTL。所以我们的文件的大部分内容都是 0，只有一小部分是 1，而且 1 的部分通常是连续的。因为 IP 是按连续的段分配给不通的组织，一般来说，一个段要么都可以通，要么都不通。
那么我们可以省略中间的 0 的部分吗？这样的话可以节省一大部分磁盘。
答案是可以！这叫做 Sparse file，或者叫 file hole。比如我可以创建一个 10PB 的超大文件：
|
1 2 3 |
$ truncate -s 10240T super.big.file $ ls -hl super.big.file -rw-r--r-- 1 xintao.lai staff 10P Aug 19 18:17 super.big.file |
然后实际占用的空间，使用 du 查看，是 0：
|
1 2 |
$ du -sh super.big.file 0 super.big.file |
使用非常简单，seek 到 EOF 以后的位置，随后再 write，中间没有写过的区域形成 hole （注意，不是 write 0）。
我们可以先用 ftruncate 调用，创建一个 sparse file，然后用 mmap 只修改需要写为 1 的部分，这样，其实只有 1 占用空间了。
实际运行还有很多问题，比如 IP 不稳定，有时候回复 ping 有时候不回复有时候回复；有些 IP 使用另一个 IP 回复 ping；有些 IP 不减 TTL 导致产生无限环路，等等。
最后我找到 34 跳的就放弃了：
代码放在这里了：https://github.com/laixintao/traceroute-the-world 有兴趣的读者可以自己跑跑看。
代码是 AI 写的，但是这篇博客是我自己纯手写的。这年头能读的博客不多了，但是可以放心的是，这个博客不会有大批量 AI 生成的文字。
by Kahlil Gibran
Your children are not your children.
They are the sons and daughters of Life's longing for itself.
They come through you but not from you,
And though they are with you, yet they belong not to you.
You may give them your love but not your thoughts.
For they have their own thoughts.
You may house their bodies but not their souls,
For their souls dwell in the house of tomorrow, which you cannot visit, not even in your dreams.
You may strive to be like them, but seek not to make them like you.
For life goes not backward nor tarries with yesterday.
You are the bows from which your children as living arrows are sent forth.
The archer sees the mark upon the path of the infinite,
and He bends you with His might that His arrows may go swift and far.
Let your bending in the archer's hand be for gladness;
For even as he loves the arrow that flies, so He loves also the bow that is stable.
时间过得真快，Rick and Morty 已经播出 13 年了。
在试播集的时候，Rick 说的这句话——「你、你的人生还长着呢，而且你的肛门现在还又紧又有弹性」——我就不理解，为什么肛门不会紧？
“Y-y-you’ve got your whole life ahead of you, and your anal cavity is still taught, yet malleable”
但 13 年之后，我理解了 Rick……
由于肛门不再紧致的问题，所以我上厕所不会带手机玩。厕所里有一块太太买的硅藻泥脚垫（非常好用），上面有一圈比较「正能量」的文字，如下：
由于已经使用半年了，看着比较脏。读者可能也不会有我这么多的时间去转着圈读。所以我把这段话抄下来：
Life comes in a package.
This package includes happiness and sorrow,
failure and success,
hope and despair.
Life is a learning process.
Experiences in life teach us new lessons and make us a better person.
With each passing day we learn to handle various situations.
平平无奇的一段话。但是我读过一百遍了，在某一天突然发现，这说的真有道理。
—— Life comes in a package.
如果没有失败，成功就没有意义。正是因为有失败的几率，成功才变得值得庆祝。
如果没有悲伤，幸福也容易被忽视。
读过一些讲如何处理情绪的书，其中共同提到的一个技巧是，不要与情绪对抗，要观察情绪，就如同对待天气，认识到情绪的变化，就如同天气会变化，让情绪过去。
但很难做到，不知道如何操作。
我海藻泥开悟之后，一旦想，Life comes in a package, 就非常容易理解情绪的变化了。那些焦虑，是因为关爱和担心；伤心，也是因为爱。
生活是一个过程，而不是一个结果。当人老了，回顾自己的一生的时候，看到的不会是最后到达的点，而是曾经走过的所有的路。
这样一想，路上无论遇到什么，都不会是遗憾了，无论遇到什么，都可以勇敢地去面对。
