公众号关注 「奇妙的 Linux 世界」
设为「星标」，每天带你玩转 Linux ！
本文翻译自 Facebook 在 LPC 2021 大会上的一篇分享：From XDP to Socket: Routing of packets beyond XDP with BPF[1]。
标题可直译为《从 XDP 到 Socket 的（全路径）流量路由：XDP 不够，BPF 来凑》，因为 XDP 运行 在网卡上，而且在边界和流量入口，再往后的路径（尤其是到了内核协议栈）它就管不 到了，所以引入了其他一些 BPF 技术来“接力”这个路由过程。另外， 这里的“路由”并非狭义的路由器三层路由，而是泛指 L3-L7 流量转发。
由于译者水平有限，本文不免存在遗漏或错误之处。如有疑问，请查阅原文。
以下是译文。
用户请求从公网到达 Facebook 的边界 L4LB 节点之后，往下会涉及到两个阶段（每个阶 段都包括了 L4/L7）的流量转发：
从 LB 节点负载均衡到特定主机
主机内：将流量负载均衡到不同 socket
以上两个阶段都涉及到流量的一致性路由（consistent routing of packets）问题。本文介绍这一过程中面临的挑战，以及我们如何基于最新的 BPF/XDP 特性来应对这些挑战。
1.1 前期工作
几年前也是在 LPC 大会，我们分享了 Facebook 基于 XDP 开发的几种服务，例如
基于 XDP 的四层负载均衡器（L4LB）katran[2]， 从 2017 年开始，每个进入 facebook.com 的包都是经过 XDP 处理的；
-
边界层（edge tiers），位于 PoP 点
Edge PoP 和 Origin DC 之间的 LB 通常是长链接
Edge PoP LB 将 L7 流量路由到终端主机，
Origin DC LB 再将 L7 流量路由到最终的应用，例如 HHVM 服务。
1.3 面临的挑战
总结一下前面的内容：公网流量到达边界节点后，接下来会涉及 两个阶段的流量负载均衡（每个阶段都是 L4+L7），
宏观层面：LB 节点 -> 后端主机
微观层面（主机内）：主机内核 -> 主机内的不同 socket
这两个阶段都涉及到流量的高效、一致性路由（consistent routing）问题。
本文介绍这一过程中面临的挑战，以及我们是如何基于最新的 BPF/XDP 特性 来解决这些挑战的。具体来说，我们用到了两种类型的 BPF 程序：
BPF TCP header options[3]：解决主机外（宏观）负载均衡问题；
[4]（及相关 map 类型 ）：解决主机内（微观）负载均衡问题。
先看第一部分，从 LB 节点转发到 backend 机器时，如何来选择主机。这是四层负载均衡问题。
2.1 Katran (L4LB) 负载均衡机制
实现了一个 Maglev Hash 变种，通过一致性哈希选择后端；
在一致性哈希之上，还维护了自己的一个本地缓存来跟踪连接。这个设计是为了在某些后端维护或故障时，避免其他后端的哈希发生变化，后面会详细讨论。
用伪代码来表示 Katran 选择后端主机的逻辑：
这种机制非常有效，也非常高效（highly effective and efficient）。
2.2 一致性哈希的局限性
2.2.1 容错性：后端故障对非相关连接的扰动
横轴表示 backend 挂掉的百分比
纵轴是哈希表项（entries）变化的百分比，对应受影响连接的百分比
Google 放这张图是想说明：一部分后端发生变化时，其他后端受影响的概率非常小；但从我们的角度来说，以上这张图说明：即使后端挂掉的比例非常小， 整个哈希表还是会受影响，并不是完全无感知 —— 这就会 导致一部分流量被错误路由（misrouting）：
对于短连接来说，例如典型的 HTTP 应用，这个问题可能影响不大；
但对于 tcp 长连接，例如持续几个小时的视频流，这种扰动就不能忍了。
2.2.2 TCP 长连接面临的问题
首先要说明，高效 != 100% 有效。对于 TCP 长连接来说（例如视频），有两种场景会它们被 reset：
解释一下：
如果 LB 升级、维护或发生故障，会导致路由器 ECMP shuffle，那原来路由到某个 LB 节点的 flow，可能会被重新路由到另一台 LB 上；虽然我们维护了 cache，但它是 LB node local 的，因此会发生 cache miss；
如果后端节点升级、维护或发生故障，那么根据前面 maglev 容错性的实验结果，会有一 部分（虽然比例不是很大）的 flow 受到影响，导致路由错误。
以上分析可以看出，“持续发布” L4 和 L7 服务会导致连接不稳定，降低整体可靠性。除了发布之外，我们随时都有大量服务器要维护，因此哈希 ring 发生变化（一致性哈希 发生扰动）是日常而非例外。任何时候发生 ECMP shuffle 和服务发布/主机维护，都会导 致一部分 active 连接受损，虽然量很小，但会降低整体的可靠性指标。
解决这个问题的一种方式是在所有 LB 节点间共享这个 local cache （类似于 L4LB 中的 session replication），但这是个很糟糕的主意 ，因为这就需要去解决另外一大堆分布式系统相关的问题，尤其我们不希望引入任何 会降低这个极快数据路径性能的东西。
2.2.3 QUIC 协议为什么不受影响
但对于 QUIC 来说，这都不是问题。
QUIC 规范（RFC 9000）中允许 server 将任意信息嵌入到包的 字段。
Facebook 已经广泛使用 QUIC 协议，因此在 Facebook 内部，我们可以
在 server 端将路由信息（routing information）嵌入到 字段，并
要求客户端必须将这个信息带回来。
完全无状态四层路由
这样整条链路上都可以从包中提取这个 id，无需任何哈希或 cache 查找，最终实现的是一个 完全无状态的四层路由（completely stateless routing in L4）。
那能不能为 TCP 做类似的事情呢？答案是可以。这就要用到 BPF-TCP header option 了。
2.3 TCP 连接解决方案：利用 BPF 将 backend server 信息嵌入 TCP Header
2.3.1 原理和流程
基本思想：
编写一段 类型的 BPF 程序，attach 到 cgroup：
在 LISTEN, CONNECT, CONN_ESTD 等事件时会触发 BPF 程序的执行
BPF 程序可以获取包的 TCP Header，然后往其中写入路由信息（这里是 server_id），或者从中读取路由信息
在 L4LB 侧维护一个 server_id 缓存，记录仍然存活的 backend 主机
L4LB 第一次见这条 flow，因此通过一致性哈希为它选择一台 backend 主机，然后将包转发过去；
图中这台主机获取到自己的 server_id 是 42，然后将这个值写到 TCP header；
客户端主机收到包后，会解析这个 id 并存下来，后面发包时都会带上这个 server_id；
服务端应答 SYN+ACK，其中 服务端 BPF 程序将 server_id 嵌入到 TCP 头中；
假设过了一会发生故障，前面那台 L4LB 挂了（这会导致 ECMP 发生变化）；另外，某些 backend hosts 也挂了（这会 影响一致性哈希，原有连接接下来有小概率会受到影响），那么接下来，
客户端流量将被（数据中心基础设施）转发到另一台 L4LB；
这台新的 L4LB 解析客户端包的 TCP header，提取 server_id，查询 server_id 缓存（ 注意不是 Katran 的 node-local 连接缓存）之后发现 这台机器还是 active 的，因此直接转发给这台机器。
可以看到在 TCP Header 中引入了路由信息后，未发生故障的主机上的长连接就能够避免 因 L4LB 和主机挂掉而导致的 misrouting（会被直接 reset）。
2.3.2 开销
数据开销：TCP header 增加 6 个字节
运行时开销：不明显
需要在 L4LB 中解析 TCP header 中的 server_id 字段，理论上来说，这个开销跟代码实 现的好坏相关。我们测量了自己的实现，这个开销非常不明显。
2.3.3 实现细节
监听的 socket 事件
维护 TCP flow -> server_id 的映射
在每个 LB 节点上用 bpf_sk_storage 来存储 per-flow server_id。也就是说，
对于建连包特殊处理，
建连之后会维护有 flow 信息（例如连接跟踪），
对于建连成功后的普通流量，从 flow 信息就能直接映射到 server_id， 不需要针对每个包去解析 TCP header。
server_id 的分配和同步
前面还没有提到如何分配 server_id，以及如何保证这些后端信息在负 载均衡器侧的时效性和有效性。
我们有一个 offline 工作流，会给那些有业务在运行的主机随机分配 一个 id，然后将这个信息同步给 L4 和 L7 负载均衡器（Katran and Proxygen）， 后者拿到这些信息后会将其加载到自己的控制平面。因此这个系统不会有额外开销，只要 保证 LB 的元信息同步就行了。
由于这个机制同时适用于 QUIC 和 TCP，因此 pipeline 是同一个。
2.3.4 效果
对典型的数据中心内部访问比较有用；
要用于数据中心外的 TCP 客户端，就要让后者将带给它们的 server_id 再带回来，但这个基本做不到；
即使它们带上了，网络中间处理节点（middleboxes）和防火墙（firewalls）也可能会将这些信息丢弃。
2.4 小结
通过将 server_id 嵌入 TCP 头中，我们实现了一种 stateless routing 机制，
这是一个完全无状态的方案
额外开销（CPU / memory）非常小，基本感知不到
其他竞品方案都非常复杂，例如在 hosts 之间共享状态，或者将 server_id 嵌入到 ECR (Echo Reply) 时间戳字段。
前面介绍了流量如何从公网经过内网 LB 到达 backend 主机。再来看在主机内，如何路由流量来保证七层服务（L7 service）发布或重启时不损失任何流量。
这部分内容在 SIGCOMM 2020 论文中有详细介绍。想了解细节的可参考：
Facebook,Zero Downtime Release: Disruption-free Load Balancing of a Multi-Billion User Website[5]. SIGCOMM 2020
3.1 当前发布方式及存在的问题
L7LB Proxygen 自身也是一个七层服务，我们以它的升级为例来看一下当前发布流程。
3.1.1 发布流程
拉出一般是通过将 downstream service 的健康监测置为 false 来实现的，例如在这个例子中，就是让 Proxygen 返回给 katran 的健康监测是失败的。
部署新代码，
关闭现有进程，创建一个新进程运行新代码。
发布过程中，系统容量会降低。
从 graceful shutdown 开始，到新代码已经接入了正常量级的流量，这段时间内 系统容量并没有达到系统资源所能支撑的最大值， 例如三个 backend 本来最大能支撑 3N 个连接，那在升级其中一台的时间段内，系统能支撑的最大连接数就会小于 3N，在 2N~3N 之间。这也是为什么很多公司都避免在业务高峰（而是选择类似周日凌晨五点这样的时间点）做这种变更的原因之一。
发布周期太长
假设有 100 台机器，分成 100 个批次（phase），每次发布一台， 如果 graceful time 是 10 分钟，一次发布就需要 1000 分钟，显然是不可接受的。
本质上来说，这种方式扩展性太差，主机或实例数量一多效率就非常低了。
3.2 不损失容量、快速且用户无感的发布
以上分析引出的核心问题是：如何在用户无感知的前提下，不损失容量（without losing capacity）且非常快速（very high velocity）地完成发布。
3.2.1 早期方案：socket takeover (or zero downtime restart)
我们在早期自己实现了一个所谓的 zero downtime restart 或称 socket takeover 方案。具体细节见前面提到的 LPC 论文，这里只描述下大概原理：相比于等待老进程的连接完全退出再开始发布，我们的做法是直接创建一个新进程，然后通过一个唯 一的 local socket 将老进程中 TCP listen socket 和 UDP sockets 的文件描述符 （以及 SCM rights）转移到新进程。
发布流程
如下图所示，发布前，实例正常运行，同时提供 TCP 和 UDP 服务，其中，
TCP socket 分为两部分：已接受的连接（编号 1~N）和监听新连接的 listening socket
-
创建一个新实例
将 TCP listening socket 和 UDP VIP 迁移到新实例；老实例仍然 serving 现有 TCP 连接（），
新实例开始接受新连接（），包括新的 TCP 连接和新的 UDP 连接
老实例等待 drain
可以看到，这种方式：
在发布期间不会导致系统容器降低，因为我们完全保留了老实例，另外创建了一个新实例
发布速度可以显着加快，因为此时可以并发发布多个实例
老连接被 reset 的概率可以大大降低，只要允许老实例有足够的 drain 窗口
那么，这种方式有什么缺点吗？
存在的问题
一个显而易见的缺点是：这种发布方式需要更多的系统资源，因为对于每个要升级的实例 ，它的新老实例需要并行运行一段时间；而在之前发布模型是干掉老实例再创建新实例， 不会同时运行。
但我们今天要讨论的是另一个问题：UDP 流量的分发或称解复用（de-multiplex）。
TCP 的状态维护在内核。
UDP 协议 —— 尤其是维护连接状态的 UDP 协议，具体来说就是 QUIC —— 所有 状态维护在应用层而非内核，因此内核完全没有 QUIC 的上下文。
虽然能解决 QUIC 的问题，但可以看出，这种方式非常复杂和脆弱，涉及到大量进程间通信，需要维护许多状态。有没有简单的方式呢？
3.2.2 其他方案调研：SO_REUSEPORT
Socket takeover 方案复杂性和脆弱性的根源在于：为了做到客户端无感，我们在两个进程间共享了同一个 socket。因此要解决这个问题，就要避免在多个进程之间共享 socket。
另一方面，SO_REUSEPORT 还有性能问题，
TCP 是有一个独立线程负责接受连接，然后将新连接的文件描述符转给其他线程 ，这种机制在负载均衡器中非常典型，可以认为是在 socket 层做分发；
-
3.2.3 思考
我们后退一步，重新思考一下我们的核心需求是什么。有两点：
在内核中实现流量的无损切换，以便客户端完全无感知；
过程能做到快速和可扩展，不存在明显性能瓶颈；
内核提供了很多功能，但并没有哪个功能是为专门这个场景设计的。因此要彻底解决问题，我们必须引入某种创新。
理论上：只要我们能控制主机内包的路由过程（routing of the packets within a host），那以上需求就很容易满足了。
实现上：仍然基于 SO_REUSEPORT 思想，但同时解决 UDP 的一致性路由和瓶颈问题。
最终我们引入了一个 socket 层负载均衡器 bpf_sk_reuseport。
3.3 新方案：
3.3.1 方案设计
简单来说，
在 socket 层 attach 一段 BPF 程序，控制 TCP/UDP 流量的转发（负载均衡）:
通过一个 BPF map 维护配置信息，业务进程 ready 之后自己配置流量切换。
3.3.2 好处
这种设计的好处：
通用，能处理多种类型的协议。
在 VIP 层面，能更好地控制新进程（新实例）启动后的流量接入过程，例如
Proxygen 在启动时经常要做一些初始化操作，启动后做一些健康检测工作， 因此在真正开始干活之前还有一段并未 ready 接收请求/流量的窗口 —— 即使它此时已经 bind 到端口了。
在新方案中，我们无需关心这些，应用层自己会判断新进程什么时候可以接受流量 并通知 BPF 程序做流量切换；
性能方面，也解决了前面提到的 UDP 单线程瓶颈；
在包的路由（packet-level routing）方面，还支持根据 CPU 调整路由权重（adjust weight of traffic per-cpu）。例如在多租户环境中，CPU 的利用率可能并不均匀，可以根据自己的需要实现特定算法来调度，例如选择空闲的 CPU。
最后，未来迭代非常灵活，能支持多种新场景的实验，例如让每个收到包从 CPU 负责处理该包，或者 NUMA 相关的调度。
3.3.3 发布过程中的流量切换详解
用一个 类型的 BPF map 来配置转发规则，其中，
key：
value：socket 的文件描述符，与业务进程一一对应
已经维护了 flow -> socket 映射
如果 flow 存在，就就转发到对应的 socket；不存在在创建一个新映射，转发给新实例的 socket。
一条是已发布的 server 百分比，
实验组（右边）：30x，因此还没有到分发瓶颈但 CPU 已经用满了，但即使这样丢包仍然很少。
3.3.5 遇到的坑
生产环境遇到过一个严重问题：新老进程同时运行期间，观察到 CPU spike 甚至 host locking；但测试环境从来没出现过，而且在实现上我们也没有特别消耗 CPU 的逻辑。
排查之后发现，这个问题跟 BPF 程序没关系，直接原因是
在同一个 netns 内有大量 socket，
新老实例同时以支持和不支持 bpf_sk_reuseport 的方式 bind 到了同一端口，
bind() 实现中有一个 spin lock 会遍历一个很长的 hashtable bucket，
如果有大量 http endpoints，那 key 很可能就是 443 和 80；这会导致 CPU 毛刺甚至机器卡住。
这个问题花了很长时间排查，因此有人在类型场景下遇到类似问题，很可能跟这个有关。相关内核代码[7]， 修复见 patch[8]。
3.3.6 vs
Cloudflare 引入了 `bpf_sk_lookup`[9]，
更多信息，可参考他们的论文：
The ties that un-bind: decoupling IP from web services and sockets for robust addressing agility at CDN-scale, SIGCOMM 2021
可以看到，它也允许多个 socket bind 到同一个 port，因此与 功能有些重叠，因为二者都源于这样一种限制：在收包时，缺少从应用层直接命令内核选择哪个 socket 的控制能力。
但二者也是有区别的：
与 IP 地址所属的 socket family 是紧耦合的
则将 IP 与 socket 解耦 —— lets it pick any / netns
3.3.7 小结
本节介绍了我们的基于 BPF_PROG_TYPE_SK_REUSEPORT 和 BPF_MAP_TYPE_REUSEPORT_SOCKARRAY 实现的新一代发布技术，它能实现主机内新老实例流量的无损切换，优点：
简化了运维流程，去掉脆弱和复杂的进程间通信（IPC），减少了故障；
效率大幅提升，例如 UDP 性能 10x；
可靠性提升，例如避免了 UDP misrouting 问题和 TCP 三次握手时的竞争问题。
引用链接
[1]
From XDP to Socket: Routing of packets beyond XDP with BPF: https://linuxplumbersconf.org/event/11/contributions/950/
[2]katran: https://engineering.fb.com/2018/05/22/open-source/open-sourcing-katran-a-scalable-network-load-balancer/
[3]BPF TCP header options: https://lwn.net/Articles/827672/
[4]: http://archive.lwn.net:8080/netdev/20180808080131.3014367-1-kafai@fb.com/t/
[5]Zero Downtime Release: Disruption-free Load Balancing of a Multi-Billion User Website: https://dl.acm.org/doi/pdf/10.1145/3387514.3405885
[6]SO_REUSEPORT: https://lwn.net/Articles/542629/
[7]代码: https://github.com/torvalds/linux/blob/v5.10/net/ipv4/inet_connection_sock.c#L376
[8]patch: https://lore.kernel.org/lkml/20200601174049.377204943@linuxfoundation.org/
[9]: https://lwn.net/Articles/825103/
原文链接：https://arthurchiao.art/blog/facebook-from-xdp-to-socket-zh/
本文转载自：「云原生实验室」，原文：https://tinyurl.com/575t644f，版权归原作者所有。欢迎投稿，投稿邮箱: editor@hi-linux.com。
你可能还喜欢
点击下方图片即可阅读