Linux FQ 队列实现原理浅析
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 Pacing:https://lwn.net/Articles/199644/
然后会问,为什么该patch没有被applied,请看我上一节的解释。
好吧,时隔10多年,又来了一个:
[v2,net-next] tcp: internal implementation for pacing:https://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队列没有用呢,同时,能不能再多实现几个类似的队列呢?