弹性下一跳组¶
弹性组是一种下一跳组,旨在最大程度地减少在组构成和组成下一跳权重发生变化时,流路由中断。
弹性哈希组背后的思想最好通过与传统多路径下一跳组的对比来解释,传统多路径下一跳组使用 RFC 2992 中描述的哈希阈值算法。
为了选择下一跳,哈希阈值算法首先为组中的每个下一跳分配一个哈希范围,然后通过比较 SKB 哈希与各个范围来选择下一跳。当一个下一跳从组中移除时,范围会被重新计算,这导致哈希空间的一部分从一个下一跳重新分配给另一个下一跳。RFC 2992 如此说明
+-------+-------+-------+-------+-------+
| 1 | 2 | 3 | 4 | 5 |
+-------+-+-----+---+---+-----+-+-------+
| 1 | 2 | 4 | 5 |
+---------+---------+---------+---------+
Before and after deletion of next hop 3
under the hash-threshold algorithm.
请注意,下一跳 2 如何将部分哈希空间让给下一跳 1,以及下一跳 4 让给下一跳 5。虽然旧的和新的分配通常会有一些重叠,但一些流量流会改变它们解析到的下一跳。
如果多路径组用于多个服务器之间的负载均衡,这种哈希空间重新分配会导致一个问题,即来自单个流的数据包突然到达一个不期望它们的服务器。这可能导致 TCP 连接被重置。
如果多路径组用于负载均衡到同一服务器的可用路径之间,问题在于沿途不同的延迟和乱序会导致数据包以错误的顺序到达,从而导致应用程序性能下降。
为了缓解上述流重定向,弹性下一跳组在哈希空间及其组成下一跳之间插入了另一层间接:一个哈希表。选择算法使用 SKB 哈希来选择一个哈希表桶,然后读取该桶包含的下一跳,并将流量转发到那里。
这种间接带来了重要特性。在哈希阈值算法中,与下一跳关联的哈希范围必须是连续的。有了哈希表,哈希表桶和各个下一跳之间的映射是任意的。因此,当一个下一跳被删除时,包含它的桶会被简单地重新分配给其他下一跳
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|1|2|2|2|2|3|3|3|3|4|4|4|4|5|5|5|5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
v v v v
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|1|2|2|2|2|1|2|4|5|4|4|4|4|5|5|5|5|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Before and after deletion of next hop 3
under the resilient hashing algorithm.
当组中下一跳的权重改变时,可以选择一部分当前未用于转发流量的桶,并利用这些桶来满足新的下一跳分配需求,同时保持“忙碌”的桶不变。这样,已建立的流理想情况下会继续通过与下一跳组更改前相同的路径转发到相同的端点。
算法¶
简而言之,该算法的工作原理如下。根据其权重和哈希表中桶的数量,每个下一跳都应分配一定数量的桶。根据源代码,我们将此数量称为下一跳的“需求计数”。如果发生可能导致桶分配更改的事件,将更新各个下一跳的需求计数。
桶数量少于其需求计数的下一跳被称为“欠重”。桶数量多于其需求计数的下一跳被称为“过重”。如果组中没有过重(因此也没有欠重)的下一跳,则称该组为“平衡”。
每个桶都维护一个上次使用计时器。每当数据包通过一个桶转发时,该计时器都会更新为当前的 jiffies 值。弹性组的一个属性是“空闲计时器”,它是指一个桶在不被流量击中多长时间后才会被认为是“空闲”的。不空闲的桶是忙碌的。
在为下一跳分配需求计数后,会运行一个“维护”算法。对于桶
未分配下一跳,或
其下一跳已被移除,或
空闲且其下一跳过重,
维护会将桶引用的下一跳更改为某个欠重的下一跳。如果在以这种方式考虑所有桶后,仍然存在欠重的下一跳,则会安排另一次维护运行在未来的时间。
可能没有足够的“空闲”桶来满足所有下一跳的更新需求计数。弹性组的另一个属性是“不平衡计时器”。此计时器可以设置为 0,在这种情况下,表将保持不平衡状态,直到出现空闲桶为止,可能永远不会。如果设置为非零值,该值表示允许表保持不平衡状态的时间段。
考虑到这一点,我们将上述条件列表更新为再增加一项。因此,桶
如果其下一跳过重,并且表处于不平衡状态的时间量超过了不平衡计时器(如果该计时器非零),
... 也会被迁移。
卸载和驱动程序反馈¶
卸载弹性组时,在下一跳之间分配桶的算法仍然在软件中。驱动程序通过以下三种方式接收下一跳组的更新通知
类型为
NH_NOTIFIER_INFO_TYPE_RES_TABLE
的完整组通知。这仅在首次创建组并填充桶后使用。类型为
NH_NOTIFIER_INFO_TYPE_RES_BUCKET
的单桶通知,用于通知已建立组内的单个迁移。预替换通知,
NEXTHOP_EVENT_RES_TABLE_PRE_REPLACE
。这在替换组之前发送,是驱动程序在将任何内容提交到硬件之前否决组的一种方式。
一些单桶通知是强制的,如通知中的“force”标志所示。这些用于例如与桶关联的下一跳已被移除,并且桶确实必须迁移的情况。
驱动程序可以通过返回错误代码来覆盖非强制通知。这样做的用例是,驱动程序通知硬件应该迁移桶,但硬件发现桶实际上已被流量击中。
硬件报告桶忙碌的第二种方式是通过 nexthop_res_grp_activity_update()
API。以这种方式识别为忙碌的桶被视为已被流量击中。
卸载的桶应标记为“offload”或“trap”。这是通过 nexthop_bucket_set_hw_flags()
API 完成的。
Netlink UAPI¶
弹性组替换¶
弹性组的配置方式与其它多路径组相同,均使用 RTM_NEWNEXTHOP
消息。以下更改适用于 netlink 消息中传递的属性
NHA_GROUP_TYPE
对于弹性组,应为
NEXTHOP_GRP_TYPE_RES
。
NHA_RES_GROUP
一个嵌套结构,包含弹性组特有的属性。
NHA_RES_GROUP
负载
NHA_RES_GROUP_BUCKETS
哈希表中的桶数。
NHA_RES_GROUP_IDLE_TIMER
空闲计时器,单位为 clock_t。
NHA_RES_GROUP_UNBALANCED_TIMER
不平衡计时器,单位为 clock_t。
下一跳获取¶
获取弹性下一跳组的请求使用 RTM_GETNEXTHOP
消息,其方式与其它下一跳获取请求完全相同。响应属性与上面引用的替换属性匹配,但 NHA_RES_GROUP
负载将包含以下属性
NHA_RES_GROUP_UNBALANCED_TIME
弹性组处于不平衡状态的时长,单位为 clock_t。
桶获取¶
不带 NLM_F_DUMP
标志的 RTM_GETNEXTHOPBUCKET
消息用于请求单个桶。获取请求中识别的属性是
NHA_ID
桶所属的下一跳组的 ID。
NHA_RES_BUCKET
包含桶特定属性的嵌套结构。
NHA_RES_BUCKET
负载
NHA_RES_BUCKET_INDEX
桶在弹性表中的索引。
桶转储¶
带有 NLM_F_DUMP
标志的 RTM_GETNEXTHOPBUCKET
消息用于请求匹配桶的转储。转储请求中识别的属性是
NHA_ID
如果指定,将转储限制为仅具有此 ID 的下一跳组。
NHA_OIF
如果指定,将转储限制为包含使用此 ifindex 设备的下一跳的桶。
NHA_MASTER
如果指定,将转储限制为包含使用此 ifindex 的 VRF 中设备的下一跳的桶。
NHA_RES_BUCKET
包含桶特定属性的嵌套结构。
NHA_RES_BUCKET
负载
NHA_RES_BUCKET_NH_ID
如果指定,将转储限制为仅包含具有此 ID 的下一跳的桶。
用法¶
为了说明用法,请考虑以下命令
# ip nexthop add id 1 via 192.0.2.2 dev eth0
# ip nexthop add id 2 via 192.0.2.3 dev eth0
# ip nexthop add id 10 group 1/2 type resilient \
buckets 8 idle_timer 60 unbalanced_timer 300
最后一条命令创建了一个弹性下一跳组。它将有 8 个桶(这是一个异常低的数字,此处仅用于演示目的),每个桶在没有流量命中它至少 60 秒后将被认为是空闲的,如果表保持不平衡状态 300 秒,它将被强制恢复平衡。
更改下一跳权重会导致桶分配发生变化
# ip nexthop replace id 10 group 1,3/2 type resilient
这可以通过查看单个桶来确认
# ip nexthop bucket show id 10
id 10 index 0 idle_time 5.59 nhid 1
id 10 index 1 idle_time 5.59 nhid 1
id 10 index 2 idle_time 8.74 nhid 2
id 10 index 3 idle_time 8.74 nhid 2
id 10 index 4 idle_time 8.74 nhid 1
id 10 index 5 idle_time 8.74 nhid 1
id 10 index 6 idle_time 8.74 nhid 1
id 10 index 7 idle_time 8.74 nhid 1
注意两个空闲时间较短的桶。这些是在下一跳替换命令后迁移的桶,以满足下一跳 1 需要分配 6 个桶而不是 4 个的新需求。
Netdevsim¶
netdevsim 驱动程序实现了弹性组的模拟卸载,并暴露了 debugfs 接口,允许将单个桶标记为忙碌。例如,以下命令将下一跳组 10 中的桶 23 标记为活动状态
# echo 10 23 > /sys/kernel/debug/netdevsim/netdevsim10/fib/nexthop_bucket_activity
此外,另一个 debugfs 接口可用于配置下一次迁移桶的尝试应失败
# echo 1 > /sys/kernel/debug/netdevsim/netdevsim10/fib/fail_nexthop_bucket_replace
除了作为示例之外,netdevsim 暴露的接口在自动化测试中很有用,tools/testing/selftests/drivers/net/netdevsim/nexthop.sh
利用它们来测试算法。