Linux FQ 队列实现原理浅析

2020年6月8日 0 作者 oceansw

enqueue入队过程

上一张图:
这里写图片描述

详细描述了fq队列的入队过程,其中着重理解几个数据结构:

  • sock作为键的红黑树:用于关联skb和flow
  • next_time作为键的红黑树:用于保存未来被调度的flow,并决定timer唤醒时间以调度skb
  • new_list:用于保存新创建尚未发包的flow链表,用于优先调度触发第一包
  • old_list:用于保存正在被调度的flow。

dequeue调度过程

dequeue操作要比enqueue操作更复杂一些,先看一张图:
这里写图片描述

这是一个相对动态的过程,由Linux的hrtimer来驱动,其超时时间则取决于每一个flow的最近要发送的skb的时间,诸多flow中的时间取最小,这明显倾向于使用红黑树来实现,我们来看一下dequeue的核心代码:

static struct sk_buff *fq_dequeue(struct Qdisc *sch)
{
    ...
    /* 将红黑树上已经到期的flow从红黑树上摘除,加入old_list准备开始被调度 */
    fq_check_throttled(q, now); 
begin:
    /* 优先无条件调度新创建的flow上的skb,触发其第一包发送,以计算next_time */
    head = &q->new_flows;
    if (!head->first) {
        /* 如果没有新创建的flow,则调度old_list已经创建且被调度的flow */
        head = &q->old_flows;
        if (!head->first) {
            /* 设置最短的超时,延后执行dequeue */
            qdisc_watchdog_schedule_ns(&q->watchdog,
                               q->time_next_delayed_flow);
            return NULL;
        }
    }
    /* 从head到tail的顺序调度 */
    f = head->first;

    if (unlikely(f->head && now < f->time_next_packet)) {
        /* 同一个flow的skb链表依次被调度,然而由于pacing,当前skb允许发送的时间 */
        /* 在当前时间之后,则终止当前flow,将其插入delay rb-tree,同时调度old_list */
        /* 下一个flow */
        head->first = f->next;
        fq_flow_set_throttled(q, f); // 冒泡找到最近的expires
        goto begin;
    }

    /* 取出被调度的skb,根据pacing rate计算下一个包发送的时间 */
    skb = fq_dequeue_head(sch, f);

    //if (f->credit > 0 || !q->rate_enable)
    if (!q->rate_enable)
        goto out;

    rate = skb->sk->sk_pacing_rate;
    plen = qdisc_pkt_len(skb);

    len = (u64)plen * NSEC_PER_SEC;
    do_div(len, rate);
    f->time_next_packet = now + len;

out:
    return skb;
}

此其中的核心是

f->time_next_packet

这就是红黑树节点的键值。

速率pacing rate

Linux FQ中给定一个flow的pacing rate来计算发送下一个skb的时间依然沿用了传统的方案,即根据当前skb的长度来计算下一个skb发送的时间,依托于公式:

Δt=ΔSvΔt=ΔSv

很显然的事情,这里的ΔSΔS就是当前skb的长度,此公式的含义即,发送当前的skb一共需要ΔtΔt的时间,Linux的实现显然是粗粒度粗糙的:

len = (u64)plen * NSEC_PER_SEC;
do_div(len, rate);
f->time_next_packet = now + len;

它是基于skb来做pacing发送的,而不是基于字节来做pacing发送的,这也是主机和线路之间的矛盾,不多说。

和O(1)调度器以及CFS调度器比较

其实,FQ机制也CFS进程调度器以及磁盘IO的公平队列是完全一致的实现:
这里写图片描述

和CFS不同的是,FQ同时维护了一个正在被调度flow队列,即old_list(此处我们忽略作为开场作用的new_list),显然在CFS中,CPU时间同时只能分配给一个task,这是不同。观察这个old_list,会发现这是一个静态优先级数据结构,它和O(1)调度器非常类似:
这里写图片描述

这个和磁盘IO公平队列几乎是完全一致的,时间片可以分配给多个entry。


后面两个小节说一下pacing的实现,而不是FQ。说白了pacing的实现并不一定非得用FQ,FQ的主要要解决的问题是如何用单一的timer去驱动任意多和flow,使其都能按照自己的pacing发送数据。然而,我们能不能把这个锅甩给Linux的调度器呢?

我自己实现的TCP Pacing机制

说起FQ,不得不提的是Google BBR拥塞控制算法,前年在初次接触BBR时被这个Pacing建议弄得着迷,说实话Linux TCP Pacing机制以及FQ早已有之,然而直到BBR才结合在一起起作用,我当时在想,既然TCP本身就是per flow的,干嘛还要Qdisc层再维护一个flow表,并且我发现这个FQ实现的公平队列在高并发TCP流时,其调度时间并不准确,所以我倾向于在TCP层直接实现Pacing:
彻底实现Linux TCP的Pacing发送逻辑-普通timer版https://blog.csdn.net/dog250/article/details/54424629
彻底实现Linux TCP的Pacing发送逻辑-高精度hrtimer版https://blog.csdn.net/dog250/article/details/54424751
我起初认为这可行,是因为我觉得TCP反正也有那么多timer了,再多一个也不多。然而却忽略了两个问题:

  • 高速率TCP
    pacing rate极大时,timer将会频繁超时,为Linux调度子系统造成压力。
  • 高并发流
    多个TCP流接连超时,将会持续加重Linux调度子系统的负担。

所以说,单流测试OK,不代表真的就可用。

OK,此问题何解?

一个timer调度100000条TCP连接不是吃力吗?100000个timer每一个调度一个TCP连接不是调度器吃力吗?看来简单的甩锅是不妥的,解法是,干嘛不搞固定的10个timer,或者5个,或者20个,或者30个,看你的CPU配置了,只要是固定的数量的timer就行,以10个timer为例,一个timer平均只要对付10000条TCP流就好了,数量级的差异!

FQ只需要多加一个层次就能解决问题!

社区的internal TCP Pacing补丁

你可以先读一下这个:
TCP Pacinghttps://lwn.net/Articles/199644/
然后会问,为什么该patch没有被applied,请看我上一节的解释。

好吧,时隔10多年,又来了一个:
[v2,net-next] tcp: internal implementation for pacinghttps://patchwork.ozlabs.org/patch/762899/
几乎是一样的东西。不多说。

插队策略

FQ针对retransmit的数据包实现了一个插队策略:

// flow_queue_add/* add skb to flow queue
 * flow queue is a linked list, kind of FIFO, except for TCP retransmits
 * We special case tcp retransmits to be transmitted before other packets.
 * We rely on fact that TCP retransmits are unlikely, so we do not waste
 * a separate queue or a pointer.
 * head->  [retrans pkt 1]
 *         [retrans pkt 2]
 *         [ normal pkt 1]
 *         [ normal pkt 2]
 *         [ normal pkt 3]
 * tail->  [ normal pkt 4]
 */

这里还有没有别的花式插队或者花式避让策略呢?比方说针对纯ACK,小包,持续大包中的小包,持续小包中的大包。这个就不细说了,类比一下我们在排队时来了一帮穿制服的人…然后还有道路上的特种车辆这种,嗯,我们还有FQ的internal队列没有用呢,同时,能不能再多实现几个类似的队列呢?