https://maimai.cn/article/detail?fid=1674483493&efid=UXVPILU_JTlqLrYhTkDStA
网络流量限速是一个经久不衰的话题，Linux 内核中已经实现了若干种流量限速的方式。
最简单的方式是通过定期采集速率，在超过指定的速率后直接丢包，但这种方案效果不佳，不能精准地将流量控制在指定的速率。
更成熟的方案都是把需要延迟发送的数据包缓冲在队列中，在合适的时间再进行发送，因此 Linux 内核中的 Traffic Control（简称 TC）层就成了实现透明的网络流量限速的最佳位置。
由于历史原因，TC 只有在出口方向上实现了有队列的 Qdisc (Queue discipline)，所以我们在这里提到的限速方案也都是在出口方向上实现的。入口方向上的限速比较困难，除了 TC 层缺少队列之外，还很难对流量的源头进行限速，因此我们在这里不予讨论。
传统的 TC 限速，是通过给网络设备添加单一的具有限速功能的 Qdisc （比如 HTB、TBF 等）来完成的。这些方案有一个共同的缺点，即依赖一把设备全局的 Qdisc spinlock 来进行同步。
这把锁很难进行优化，主要有两个原因：
上述传统方案在发送流量较大的时候会碰到这个全局锁的性能瓶颈。
针对传统方案的弊端，Linux 内核提供了一个「拆散」这把全局 spinlock 的软件方案：mq Qdisc。mq Qdisc 是一个很特殊的 Qdisc，它为网络设备的每一个硬件队列分别创建一个软件 Qdisc，再通过一个 ->attach()操作将它们挂载到各个硬件队列上，如图所示：
这样一来，每一个硬件队列上的 Qdisc（上图中「child Qdisc」）都有各自的 spinlock，一个锁被「拆」成了多个锁，从而改善了设备全局 spinlock 带来的性能问题。
需注意的是，mq Qdisc 本身并不实现任何限速机制，仅仅提供了一个框架，须和其它具有限速功能的 child Qdisc（HTB、SFQ 等）配合使用。
这样做有一个缺点：现在设备上的一个 Qdisc 被「拆」成了多个 child Qdisc，我们就只能分别对这些 child Qdisc 配置限速规则，从而失去了传统方案里对设备流量的全局控制。
针对传统 HTB 方案的缺点，Mellanox 网卡推出了一个通过硬件来实现限速的方案，给 HTB Qdisc 添加了「offload 模式」，模拟 mq Qdisc 的 ->attach() 操作：
每个硬件队列分别对应了一个 HTB 树形结构中最下层的流量类型 (leaf class)。传统 HTB Qdisc 里的分类逻辑现在被移到了 clsact Qdisc 里，例如：
$ tc qdisc add dev $DEV clsact
$ tc filter add dev $DEV egress protocol ip flower dst_port 80 \
action skbedit priority 1:10
梳理一下这种方案下的发包流程：
skb->priority；->ndo_select_queue()成员函数根据 skb->priority 将数据包分发到不同的硬件队列（对应不同的 HTB leaf class）里；但同样的，无论是基于 mq Qdisc 的软件方案，还是依赖于硬件特性的 offload 方案，它们都有一个最大的弊端：流量的类型、限速规则绑定在各个硬件队列上，没有办法根据业务的需求灵活地分配带宽。
ifb 方案为每一种流量类型新建一个软件 ifb 设备，在原发送设备的 clsact Qdisc 上对流量进行分类，通过 mirred action 将不同类型的流量转发到对应的 ifb 设备，再由各个 ifb 设备上的 TBF Qdisc 完成限速：
由于 ifb 设备的数量不受网络设备硬件队列个数的限制，ifb 方案（相比 mq Qdisc 方案和硬件 offload 方案）可以更灵活地满足业务所需的限速需求。然而，由于各个 ifb 设备上的限速由 TBF Qdisc 实现，仍然可能会出现多个 CPU 同时竞争同一把 spinlock 的情况：
如上图所示，假设某一时刻运行在 2 号、3 号和 4 号 CPU 上的进程同时发送 B 类流量（对应到 1 号 ifb 设备），那么这三个 CPU 就会竞争 1 号 ifb 设备上 TBF Qdisc 的 spinlock。
字节跳动系统部 STE 团队进行了以下验证：
经验证，server 端 64.4 秒内实际接收到的平均流量为 466 Mbits/sec。
针对上述各类方案的缺点，Eric Dumazet 等人提出了一种使用 clsact Qdsic + eBPF filter + mq Qdisc + fq Qdisc 的 EDT (Earliest Departure Time) 方案：
梳理一下这种方案下的发包流程：
skb->tstamp)；与 mq Qdisc 等方案相比，EDT 方案的一个优点，在于流量类别与硬件队列之间不存在对应关系：
如上图所示，发送同一类流量的 2 号、3 号、4 号 CPU 有机会把流量发送到不同的硬件队列上，有效解决了某一类大流量同时从多个 CPU 发送到某一个（或某几个）硬件队列（或 ifb 等虚拟设备）上带来的锁竞争问题。
需要注意的是，不管是发送相同还是不同类流量的两个 CPU 仍然有可能竞争同一个 fq Qdisc spinlock。
字节跳动系统部 STE 团队对 EDT 方案也做了类似的验证：
经验证，server 端 62.8 秒内实际接收到的平均流量为 489 Mbits/sec。简单来说，EDT 方案与 ifb 方案相比，「竞争 1 把锁」变成了「竞争 8 把锁」，从而在性能上获得了一定的优势。
通过在 eBPF filter 程序中修改 skb->queue_mapping，我们可以将 CPU 与发送设备的硬件队列一一绑定（例如 CPU 1 只能发送到硬件队列 1，等等），从而进一步减缓 CPU 之间的锁竞争。事实上，如果机器上 CPU 的数量小于等于发送设备的硬件队列数，这样操作可以完全避免 CPU 之间的锁竞争。
但这也带来一个问题，考虑：假设我们让 CPU 1 只能发到硬件队列 1，CPU 2 只能发到硬件队列 2。发送某类流量的进程甲，上一时刻运行在 CPU 1 上，发了一个数据包 A 到硬件队列 1 上；下一时刻它被调度到 CPU 2 上，发了一个数据包 B 到硬件队列 2 上。由于硬件队列 1 和 2 分别有自己的 fq Qdisc，维护着各自的数据包出队顺序，我们无法保证数据包 A 会先于数据包 B 出队——也就可能会有发包乱序的问题。
总的来说，我们认为 EDT 方案有三个优点：
按照 IP 目的地址把流量分为不同类型，并为每一类配置 100 Mbits/sec 的带宽：
#include <linux/types.h>
#include <bpf/bpf_helpers.h>
#include <linux/bpf.h>
#include <linux/if_ether.h>
#include <linux/pkt_cls.h>
#include <linux/swab.h>
#include <stdint.h>
#include <linux/ip.h>
struct bpf_elf_map {
__u32 type;
__u32 size_key;
__u32 size_value;
__u32 max_elem;
__u32 flags;
__u32 id;
__u32 pinning;
__u32 inner_id;
__u32 inner_idx;
};
#define NS_PER_SEC 1000000000ULL
#define PIN_GLOBAL_NS 2
#ifndef __section
# define __section(NAME) \
__attribute__((section(NAME), used))
#endif
struct bpf_elf_map __section("maps") rate_map = {
.type = BPF_MAP_TYPE_HASH,
.size_key = sizeof(__u32),
.size_value = sizeof(__u64),
.pinning = PIN_GLOBAL_NS,
.max_elem = 16,
};
struct bpf_elf_map __section("maps") tstamp_map = {
.type = BPF_MAP_TYPE_HASH,
.size_key = sizeof(__u32),
.size_value = sizeof(__u64),
.max_elem = 16,
};
int classifier(struct __sk_buff *skb)
{
void *data_end = (void *)(unsigned long long)skb->data_end;
__u64 *rate, *tstamp, delay_ns, now, init_rate = 12500000; /* 100 Mbits/sec */
void *data = (void *)(unsigned long long)skb->data;
struct iphdr *ip = data + sizeof(struct ethhdr);
struct ethhdr *eth = data;
__u64 len = skb->len;
long ret;
now = bpf_ktime_get_ns();
if (data + sizeof(struct ethhdr) > data_end)
return TC_ACT_OK;
if (eth->h_proto != ___constant_swab16(ETH_P_IP))
return TC_ACT_OK;
if (data + sizeof(struct ethhdr) + sizeof(struct iphdr) > data_end)
return TC_ACT_OK;
rate = bpf_map_lookup_elem(&rate_map, &ip->daddr);
if (!rate) {
bpf_map_update_elem(&rate_map, &ip->daddr, &init_rate, BPF_ANY);
bpf_map_update_elem(&tstamp_map, &ip->daddr, &now, BPF_ANY);
return TC_ACT_OK;
}
delay_ns = skb->len * NS_PER_SEC / (*rate);
tstamp = bpf_map_lookup_elem(&tstamp_map, &ip->daddr);
if (!tstamp) /* unlikely */
return TC_ACT_OK;
if (*tstamp < now) {
*tstamp = now + delay_ns;
skb->tstamp = now;
return TC_ACT_OK;
}
skb->tstamp = *tstamp;
__sync_fetch_and_add(tstamp, delay_ns);
return TC_ACT_OK;
}
char _license[] SEC("license") = "GPL";
# 1. 编译 example.c
clang -O2 -emit-llvm -c example.c -o - | llc -march=bpf -filetype=obj -o example.o
# 2. 安装 mq/fq Qdisc
tc qdisc add dev $DEV root handle 1: mq
NUM_TX_QUEUES=$(ls -d /sys/class/net/$DEV/queues/tx* | wc -l)
for (( i=1; i<=$NUM_TX_QUEUES; i++ ))
do
tc qdisc add dev $DEV parent 1:$(printf '%x' $i) \
handle $(printf '%x' $((i+1))): fq
done
# 3. 安装 clsact Qdisc, 加载 example.o
tc qdisc add dev $DEV clsact
tc filter add dev $DEV egress bpf direct-action obj example.o sec .text
# 4. (使用后) 卸载 Qdisc，清理 eBPF map
tc qdisc del dev $DEV clsact
rm -f /sys/fs/bpf/tc/globals/rate_map
tc qdisc del dev $DEV root handle 1: mq
我们把所有的方案放到一张表中对比不难看出 EDT 方案的总体优势：
EDT 方案的简洁性也决定了它只需要在内核中执行很少的代码，更复杂的带宽借用逻辑、burst 处理逻辑等都可以放到用户空间，进一步避免了在内核中使用额外的锁进行同步。
EDT 方案的不足之处是目前还无法和下层的 Qdisc 直接进行交互，从而实现更复杂的公平性逻辑。但是，字节跳动系统部 STE 团队正在开发的基于 eBPF 的 Qdisc 可以通过共享 eBPF map 达到这个目的，从而会让这个方案变得更加完善。
字节跳动系统部 STE 团队正在招聘，操作系统内核与虚拟化、系统基础软件与基础库、监控与智能运维、新硬件与软件协同设计等众多岗位虚位以待。
感兴趣的朋友请投递简历至：chenziying@bytedance.com。