Linux 核心 | 網路流量限速方案大 PK

語言: CN / TW / HK

網路流量限速是一個經久不衰的話題,Linux 核心中已經實現了若干種流量限速的方式。

最簡單的方式是通過定期採集速率,在超過指定的速率後直接丟包,但這種方案效果不佳,不能精準地將流量控制在指定的速率。

更成熟的方案都是把需要延遲傳送的資料包緩衝在佇列中,在合適的時間再進行傳送,因此 Linux 核心中的 Traffic Control(簡稱 TC)層就成了實現透明的網路流量限速的最佳位置。

由於歷史原因,TC 只有在出口方向上實現了有佇列的 Qdisc (Queue discipline),所以我們在這裡提到的限速方案也都是在出口方向上實現的。入口方向上的限速比較困難,除了 TC 層缺少佇列之外,還很難對流量的源頭進行限速,因此我們在這裡不予討論。

1. 傳統限速方案

傳統的 TC 限速,是通過給網路裝置新增單一的具有限速功能的 Qdisc (比如 HTB、TBF 等)來完成的。這些方案有一個共同的缺點, 即依賴一把裝置全域性的 Qdisc spinlock 來進行同步

這把鎖很難進行優化,主要有兩個原因:

  1. 資料包的入隊、出隊都是寫操作,且都不是原子操作,因此需要使用鎖來同步;

  2. 這些 Qdisc 實現的都是裝置全域性的限速,其中一部分(如 HTB Qdisc)還允許不同流量型別 (class) 之間互相借用頻寬,因此更需要一把全域性鎖來進行統一協調。

上述傳統方案在傳送流量較大的時候會碰到這個全域性鎖的效能瓶頸。

2. mq Qdisc 方案

針對傳統方案的弊端,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 配置限速規則,從而失去了傳統方案裡對裝置流量的全域性控制。

3. HTB 硬體 offload 方案

針對傳統 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

梳理一下這種方案下的發包流程:

  1. 安裝在 clsact Qdisc 上的 filter 對資料包進行分類,設定 skb->priority
  2. Mellanox 網絡卡驅動註冊的 ->ndo_select_queue() 成員函式根據 skb->priority 將資料包分發到不同的硬體佇列(對應不同的 HTB leaf class)裡;
  3. 最終由硬體完成限速。

但同樣的,無論是基於 mq Qdisc 的軟體方案,還是依賴於硬體特性的 offload 方案,它們都有一個最大的弊端: 流量的型別、限速規則繫結在各個硬體佇列上,沒有辦法根據業務的需求靈活地分配頻寬

4. ifb 方案

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 團隊進行了以下驗證:

  1. 在 eth0 裝置上安裝 clsact Qdisc,並設定 mirred 規則,轉發出口方向 A 類流量至 ifb0;

  2. 在 ifb0 裝置上安裝 TBF Qdisc,並給 A 類流量設定 500 Mbits/sec 的頻寬限制;

  3. 啟動 96 個 iperf client 程序全速向 eth0 裝置傳送 A 類流量,分別繫結到 96 個 CPU 上。

經驗證,server 端 64.4 秒內實際接收到的平均流量為 466 Mbits/sec

5. EDT 方案

針對上述各類方案的缺點,Eric Dumazet 等人提出了一種使用 clsact Qdsic + eBPF filter + mq Qdisc + fq Qdisc 的 EDT (Earliest Departure Time) 方案:

梳理一下這種方案下的發包流程:

  1. 資料包先統一經過一個安裝在 clsact Qdisc 出口方向上的 eBPF filter。這個 eBPF filter 程式包含著主要的限速邏輯;它會根據某一個數據包所屬流量類別的頻寬來計算這個資料包的預計傳送時間,並給它蓋一個時間戳 ( skb->tstamp );
  2. 隨後,資料包被分發到裝置的各個硬體佇列,且每個硬體佇列都有一個自己的 fq Qdisc;

  3. 最後,fq Qdisc 按照時間戳對資料包進行排序, 並確保每個資料包最終出隊的時間都不早於資料包上的時間戳 ,從而達到限速的目的。

與 mq Qdisc 等方案相比,EDT 方案的一個優點, 在於流量類別與硬體佇列之間不存在對應關係

如上圖所示,傳送同一類流量的 2 號、3 號、4 號 CPU 有機會把流量傳送到不同的硬體佇列上,有效解決了 某一類大流量 同時從多個 CPU 傳送到某一個(或某幾個)硬體佇列(或 ifb 等虛擬裝置)上帶來的鎖競爭問題。

需要注意的是,不管是傳送相同還是不同類流量的兩個 CPU 仍然有可能 競爭同一個 fq Qdisc spinlock。

位元組跳動系統部 STE 團隊對 EDT 方案也做了類似的驗證:

  1. 在 eth0 裝置上安裝 mq Qdisc;

  2. 為 eth0 裝置的 8 個硬體佇列分別安裝 fq Qdisc;

  3. 在 eth0 裝置上安裝 clsact Qdisc,並掛載 eBPF filter 程式,對 A 類流量設定 500 Mbits/sec 的頻寬限制;

  4. 同樣地,啟動 96 個 iperf client 程序全速向 eth0 裝置傳送 A 類流量,並分別繫結到 96 個 CPU 上。

經驗證,server 端 62.8 秒內實際接收到的平均流量為 489 Mbits/sec 。簡單來說,EDT 方案與 ifb 方案相比,「競爭 1 把鎖」變成了「競爭 8 把鎖」,從而在效能上獲得了一定的優勢。

可選操作:將 CPU 與硬體佇列繫結

通過在 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 方案小結

總的來說,我們認為 EDT 方案有三個優點:

  1. 可以減輕(甚至 徹底避免)鎖的競爭,尤其是針對某一類流量傳送速度很高的情況;

  2. 可以完全根據業務的需求直接進行限速,而不是為底層的硬體佇列分別分配頻寬(如 mq Qdisc 等方案)。底層的 fq Qdisc 僅負責執行上層 eBPF 程式碼中計算好的限速決策;

  3. 核心程式碼邏輯簡單,可以把更多邏輯放到使用者空間,可擴充套件性強。例如,可以在使用者空間執行一個守護程序,實時監控各類流量的實際傳送速率,並通過更新 eBPF map 的方式實現頻寬借用等需求。

示例 eBPF 程式碼 (example.c)

按照 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

6. 總結

我們把所有的方案放到一張表中對比不難看出 EDT 方案的總體優勢:

EDT 方案的簡潔性也決定了它只需要在核心中執行很少的程式碼,更復雜的頻寬借用邏輯、burst 處理邏輯等都可以放到使用者空間,進一步避免了在核心中使用額外的鎖進行同步。

EDT 方案的不足之處是目前還無法和下層的 Qdisc 直接進行互動,從而實現更復雜的公平性邏輯。但是,位元組跳動系統部 STE 團隊正在開發的基於 eBPF 的 Qdisc 可以通過共享 eBPF map 達到這個目的,從而會讓這個方案變得更加完善。

7. 參考資料

  1. Yossi Kuperman, Maxim Mikityanskiy, Rony Efraim, 'Hierarchical QoS Hardware Offload (HTB)', Proceedings of Netdev 0x14, THE Technical Conference on Linux Networking, August 2020,

    https://legacy.netdevconf.info/0x14/pub/papers/44/0x14-paper44-talk-paper.pdf.

  2. Stanislav Fomichev, Eric Dumazet, Willem de Bruijn, Vlad Dumitrescu, Bill Sommerfeld, Peter Oskolkov, 'Replacing HTB with EDT and BPF', Proceedings of Netdev 0x14, THE Technical Conference on Linux Networking, August 2020,

    https://legacy.netdevconf.info/0x14/pub/papers/55/0x14-paper55-talk-paper.pdf.

加入我們

位元組跳動系統部 STE 團隊正在招聘,作業系統核心與虛擬化、系統基礎軟體與基礎庫、監控與智慧運維、新硬體與軟體協同設計等眾多崗位虛位以待。

感興趣的朋友請投遞簡歷至: [email protected]