译者序

• 1 引言

• 1.1 前期工作

• 1.2 Facebook 流量基础设施

• 1.3 面临的挑战

• 2 选择后端主机：数据中心内流量的一致性与无状态路由（四层负载均衡）

• 2.3.1 原理和流程

• 2.3.2 开销

• 2.3.3 实现细节

• 2.3.4 效果

• 2.3.5 限制

• 数据开销：TCP header 增加 6 个字节

• 运行时开销：不明显

• 监听的 socket 事件

• 维护 TCP flow -> server_id 的映射

• server_id 的分配和同步

• 2.2.1 容错性：后端故障对非相关连接的扰动

• 2.2.2 TCP 长连接面临的问题

• 2.2.3 QUIC 协议为什么不受影响

• connection_id

• 完全无状态四层路由

• 2.1 Katran (L4LB) 负载均衡机制

• 2.2 一致性哈希的局限性

• 2.3 TCP 连接解决方案：利用 BPF 将 backend server 信息嵌入 TCP Header

• 2.4 小结

• 3 选择 socket：服务的真正优雅发布（七层负载均衡）

• 3.3.1 方案设计

• 3.3.2 好处

• 3.3.3 发布过程中的流量切换详解

• 3.3.4 新老方案效果对比

• 3.3.5 小结

• 3.2.1 早期方案：socket takeover (or zero downtime restart)

• 3.2.2 其他方案调研：SO_REUSEPORT

• 3.2.3 思考

• 发布流程

• 存在的问题

• 3.1.1 发布流程

• 3.1.2 存在的问题

• 3.1 当前发布方式及存在的问题

• 3.2 不损失容量、快速且用户无感的发布

• 3.3 新方案：bpf_sk_reuseport

• 4 讨论

• 4.1 遇到的问题：CPU 毛刺（CPU spikes）甚至卡顿

• 4.2 Listening socket hashtable

• 4.3 bpf_sk_select_reuseport vs bpf_sk_lookup

1 引言

用户请求从公网到达 Facebook 的边界 L4LB 节点之后，往下会涉及到两个阶段（每个阶 段都包括了 L4/L7）的流量转发：

1.从 LB 节点负载均衡到特定主机

2.主机内：将流量负载均衡到不同socket

以上两个阶段都涉及到流量的一致性路由（consistent routing of packets）问题。本文介绍这一过程中面临的挑战，以及我们如何基于最新的 BPF/XDP 特性来应对这些挑战。

1.1 前期工作

2.基于 XDP 的防火墙（挡在 katran 前面）。

Facebook 两代软件 L4LB 对比。

1.2 Facebook 流量基础设施

从层次上来说，如下图所示，Facebook 的流量基础设施分为两层：

1.边界层（edge tiers），位于 PoP 点

2.数据中心层，我们称为 Origin DC

• 每层都有一套全功能 LB（L4+L7）

• Edge PoP 和 Origin DC 之间的 LB 通常是长链接

1.用户连接（user connections）在边界终结，

1.3 面临的挑战

这两个阶段都涉及到流量的高效、一致性路由（consistent routing）问题。

2 选择后端主机：数据中心内流量的一致性与无状态路由（四层负载均衡）

2.1 Katran (L4LB) 负载均衡机制

• 实现了一个 Maglev Hash 变种，通过一致性哈希选择后端；
• 在一致性哈希之上，还维护了自己的一个本地缓存来跟踪连接。这个设计是为了在某些后端维护或故障时，避免其他后端的哈希发生变化，后面会详细讨论。

int pick_host(packet* pkt) {
    if (is_in_local_cache(pkt))
        return local_cache[pkt]

    return consistent_hash(pkt) % server_ring
}

2.2 一致性哈希的局限性

2.2.1 容错性：后端故障对非相关连接的扰动

Maglev: A fast and reliable software network load balancer. OSDI 2016

• 横轴表示 backend 挂掉的百分比

• 纵轴是哈希表项（entries）变化的百分比，对应受影响连接的百分比

Google 放这张图是想说明：一部分后端发生变化时，其他后端受影响的概率非常小；但从我们的角度来说，以上这张图说明：即使后端挂掉的比例非常小， 整个哈希表还是会受影响，并不是完全无感知 —— 这就会 导致一部分流量被错误路由（misrouting）：

• 对于短连接来说，例如典型的 HTTP 应用，这个问题可能影响不大；

• 但对于 tcp 长连接，例如持续几个小时的视频流，这种扰动就不能忍了。

2.2.2 TCP 长连接面临的问题

int pick_host(packet* pkt) {
    if (is_in_local_cache(pkt))               // 场景一：ECMP shuffle 时（例如 LB 节点维护或故障），这里会 miss
        return local_cache[pkt]

    return consistent_hash(pkt) % server_ring // 场景二：后端维护或故障时，这里的好像有（较小）概率发生变化
}

1.如果 LB 升级、维护或发生故障，会导致路由器 ECMP shuffle，那原来路由到某个 LB 节点的 flow，可能会被重新路由到另一台 LB 上；虽然我们维护了 cache，但它是 LB node local 的，因此会发生 cache miss；

2.如果后端节点升级、维护或发生故障，那么根据前面 maglev 容错性的实验结果，会有一 部分（虽然比例不是很大）的 flow 受到影响，导致路由错误。

以上分析可以看出，“持续发布” L4 和 L7 服务会导致连接不稳定，降低整体可靠性。除了发布之外，我们随时都有大量服务器要维护，因此哈希 ring 发生变化（一致性哈希 发生扰动）是日常而非例外。任何时候发生 ECMP shuffle 和服务发布/主机维护，都会导 致一部分 active 连接受损，虽然量很小，但会降低整体的可靠性指标。

解决这个问题的一种方式是在所有 LB 节点间共享这个 local cache （类似于 L4LB 中的 session replication），但这是个很糟糕的主意 ，因为这就需要去解决另外一大堆分布式系统相关的问题，尤其我们不希望引入任何 会降低这个极快数据路径性能的东西。

2.2.3 QUIC 协议为什么不受影响

但对于 QUIC 来说，这都不是问题。

connection_id

QUIC 规范（RFC 9000）中允许 server 将任意信息嵌入到包的 connection_id 字段。

1.在 server 端将路由信息（routing information）嵌入到 connection_id 字段，并

2.要求客户端必须将这个信息带回来。

完全无状态四层路由

这样整条链路上都可以从包中提取这个 id，无需任何哈希或 cache 查找，最终实现的是一个 完全无状态的四层路由（completely stateless routing in L4）。

2.3 TCP 连接解决方案：利用 BPF 将 backend server 信息嵌入 TCP Header

2.3.1 原理和流程

以下图为例，我们来看下 LB 节点和 backend 故障时，其他 backend 上的原有连接如何做到不受影响：

• 客户端发起一个 SYN；
  

• 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 的，因此直接转发给这台机器。

2.3.2 开销

数据开销：TCP header 增加 6 个字节

struct tcp_opt {
    uint8_t  kind;
    uint8_t  len;
    uint32_t server_id;
}; // 6-bytes total

运行时开销：不明显

2.3.3 实现细节

监听的 socket 事件

switch (skops->op) {
    case BPF_SOCK_OPS_TCP_LISTEN_CB:
    case BPF_SOCK_OPS_PASSIVE_ESTABLISHED_CB:
    case BPF_SOCK_OPS_TCP_CONNECT_CB:
    case BPF_SOCK_OPS_ACTIVE_ESTABLISHED_CB:
    case BPF_SOCK_OPS_PARSE_HDR_OPT_CB:
    case BPF_SOCK_OPS_HDR_OPT_LEN_CB:
    case BPF_SOCK_OPS_WRITE_HDR_OPT_CB:
    . . .
}

维护 TCP flow -> server_id 的映射

在每个 LB 节点上用 bpf_sk_storage 来存储 per-flow server_id。也就是说，

1.对于建连包特殊处理，

2.建连之后会维护有 flow 信息（例如连接跟踪），

3.对于建连成功后的普通流量，从 flow 信息就能直接映射到 server_id， 不需要4.针对每个包去解析 TCP header。

server_id 的分配和同步

前面还没有提到如何分配 server_id，以及如何保证这些后端信息在负 载均衡器侧的时效性和有效性。

2.3.4 效果

2.3.5 限制

• 对典型的数据中心内部访问比较有用；
• 要用于数据中心外的 TCP 客户端，就要让后者将带给它们的 server_id 再带回来，但这个基本做不到；
• 即使它们带上了，网络中间处理节点（middleboxes）和防火墙（firewalls）也可能会将这些信息丢弃。

2.4 小结

• 这是一个完全无状态的方案
• 额外开销（CPU / memory）非常小，基本感知不到
• 其他竞品方案都非常复杂，例如在 hosts 之间共享状态，或者将 server_id 嵌入到 ECR (Echo Reply) 时间戳字段。

3 选择 socket：服务的真正优雅发布（七层负载均衡）

3.1 当前发布方式及存在的问题

3.1.1 发布流程

发布前状态：Proxygen 实例上有一些老连接，也在不断接受新连接，

• 拉出：拉出之后的实例不再接受新连接，但在一定时间窗口内，继续为老连接提供服务；
• 这个窗口称为 graceful shutdown（也叫 draining） period，例如设置为 5 或 10 分钟；

• 拉出一般是通过将 downstream service 的健康监测置为 false 来实现的，例如在这个例子中，就是让 Proxygen 返回给 katran 的健康监测是失败的。

• 发布新代码：graceful 窗口段过了之后，不管它上面还有没有老连接，直接开始升级。
• 一般来说，只要 graceful 时间段设置比较合适，一部分甚至全部老连接能够在这个 窗口内正常退出，从而不会引起用户可见的 spike；但另一方面，如果此时仍然有老 连接，那这些客户端就会收到 tcp reset。

• 部署新代码

• 关闭现有进程，创建一个新进程运行新代码




• 监听并接受新连接：升级之后的 Proxygen 开始正常工作， 最终达到和升级之前同等水平的一个连接状态。

3.1.2 存在的问题

3.2 不损失容量、快速且用户无感的发布

3.2.1 早期方案：socket takeover (or zero downtime restart)

发布流程

如下图所示，发布前，实例正常运行，同时提供 TCP 和 UDP 服务，其中，

• TCP socket 分为两部分：已接受的连接（编号 1~N）和监听新连接的 listening socket

• UDP socket，bind 在 VIP 上

接下来开始发布：

1.创建一个新实例

2.将 TCP listening socket 和 UDP VIP 迁移到新实例；老实例仍然 serving 现有 TCP 连接（ 1 ~ N ），

3.新实例开始接受新连接（ N+1 ~ +∞ ），包括新的 TCP 连接和新的 UDP 连接

4.老实例等待 drain

1.在发布期间不会导致系统容器降低，因为我们完全保留了老实例，另外创建了一个新实例

2.发布速度可以显着加快，因为此时可以并发发布多个实例

3.老连接被 reset 的概率可以大大降低，只要允许老实例有足够的 drain 窗口

存在的问题

• TCP 的状态维护在内核。
• UDP 协议 —— 尤其是维护连接状态的 UDP 协议，具体来说就是 QUIC —— 所有 状态维护在应用层而非内核，因此内核完全没有 QUIC 的上下文。

由于 socket 迁移是在内核做的，而内核没有 QUIC 上下文（在应用层维护），因此 当新老进程同时运行时，内核无法知道对于一个现有 UDP 连接的包，应该送给哪个进程 （因为对于 QUIC 没有 listening socket 或 accepted socket 的概念），因此有些包会到老进程，有些到新进程，如下图左边所示；

3.2.2 其他方案调研：SO_REUSEPORT

这自然使我们想到了 SO_REUSEPORT [6] : 它允许 多个 socket bind 到同一个 port。但这里仍然有一个问题：UDP 包的路由过程是非一致的（no consistent routing for UDP packets），如下图所示：

因此直接使用 SO_REUSEPORT 是不行的。

3.2.3 思考

2.过程能做到快速和可扩展，不存在明显性能瓶颈；

内核提供了很多功能，但并没有哪个功能是为专门这个场景设计的。因此要彻底解决问题，我们必须引入某种创新。

• 理论上：只要我们能控制主机内包的路由过程（routing of the packets within a host），那以上需求就很容易满足了。

• 实现上：仍然基于 SO_REUSEPORT 思想，但同时解决 UDP 的一致性路由和瓶颈问题。

最终我们引入了一个 socket 层负载均衡器 bpf_sk_reuseport。

3.3 新方案：bpf_sk_reuseport

3.3.1 方案设计

3.3.2 好处

7.最后，未来迭代非常灵活，能支持多种新场景的实验，例如让每个收到包从 CPU 负责处理该包，或者 NUMA 相关的调度。

3.3.3 发布过程中的流量切换详解

• key： <VIP>:<Port>

• value：socket 的文件描述符，与业务进程一一对应
  

如下图所示，即使新进程已经起来，但只要还没 ready（BPF map 中仍然指向老进程），

这也解决了扩展性问题，现在可以并发接收包（one-thread-per-socket），不用担心新进程启动时的 disruptions 或 misrouting 了：

3.3.4 新老方案效果对比

先来看发布过程对业务流量的扰动程度。下图是我们的生产数据中心某次发布的统计，图中有两条线：

• 一条是已发布的 server 百分比，

• 另一个条是同一时间的丢包数量，

再来看流量分发性能，分别对 socket takeover 和 bpf_sk_reuseport 两种方式加压：

• 控制组/对照组（左边）：3x 流量时开始丢包，

• 实验组（右边）：30x，因此还没有到分发瓶颈但 CPU 已经用满了，但即使这样丢包仍然很少。

3.3.5 遇到的坑

这个问题花了很长时间排查，因此有人在类型场景下遇到类似问题，很可能跟这个有关。相关内核 代码 [7] ， 修复见 patch [8] 。

3.3.6bpf_sk_select_reuseportvsbpf_sk_lookup

Cloudflare 引入了 `bpf_sk_lookup` [9] ，

This series proposes a new BPF program type named BPF_PROG_TYPE_SK_LOOKUP,
or BPF sk_lookup for short.

BPF sk_lookup program runs when transport layer is looking up a listening
socket for a new connection request (TCP), or when looking up an
unconnected socket for a packet (UDP).

This serves as a mechanism to overcome the limits of what bind() API allows
to express. Two use-cases driving this work are:

(1) steer packets destined to an IP range, fixed port to a single socket

192.0.2.0/24, port 80 -> NGINX socket

(2) steer packets destined to an IP address, any port to a single socket

198.51.100.1, any port -> L7 proxy socket