OpenVSwitch数据面流表cache机制浅谈

稍许笔墨写了一篇关于OpenVSwitch(以下简称OVS)的文章：
https://blog.csdn.net/dog250/article/details/103492099
但有些事情并没有说清楚。

关于OVS的流表是如何映射成数据平面的Flow cache的，有必要单独写一篇文章来说一下。

下面的Paper描述了整个过程的来龙去脉，不可不读：
http://www.openvswitch.org//support/papers/nsdi2015.pdf

假设你已经读过了此Paper，至少已经大致扫过了一眼，下面谈谈我的看法。

---

OVS的流表可以抽象成下面的结构：

当然，为了解决match间的笛卡尔积问题，可以将上述的结构进行分解，最终形成一个多table级联的pipeline流表机构。

OVS的流表无论从结构上讲还是从匹配方式上看，都非常类似于iptables：

• 单条iptables rule按照“match与”的方式匹配。一个 O ( n ) O(n) O(n)时间复杂度的过程。
• 多条iptables rule按照“顺序或”的方式匹配。一个 O ( n ) O(n) O(n)时间复杂度的过程。
• 匹配结果可以jump到其它chain以解决match之间笛卡尔积问题。

我们类比来看，OVS流表项就是iptables规则：

• OVS的table就是iptables的chain。
• OVS的match就是iptables的match。
• OVS的Action就是iptables的target。

简直就是一回事。

那么，iptables的问题就是OVS流表的问题咯，是吗？是的， 但是OVS已经解决了 O ( n ) O(n) O(n)时间复杂度的匹配部分：

• 数据包被上传到ovs-vswitchd进程匹配OVS流表时并非顺序匹配的，而是采用了hashmap的方式。

理想的完美哈希的 O ( 1 ) O(1) O(1)过程如下：

但现实中，往往采用冲突链表来解决哈希冲突的问题：

那么，OVS流表既然采用了这种方式，还有什么问题呢？我之前不是很推崇用这种方式预处理iptables规则吗？我之前不是很推崇nf-HiPAC，ipset这种方案吗？

OVS的新问题到底在哪里？

先说结论， OVS的目标在于在保持高效的查找过程的前提下，尽可能少的将数据包交给慢速路径处理。

这意味着既需要减少算法的时间复杂度，又要尽可能最大化快速路径的匹配率。

---

NSDI2015里说了，OVS的流表匹配不仅仅是一个规则匹配问题，而是一个Flow cache生成的问题，这里就涉及到了流表和Flow cache的区别：

• 流表是复杂的，强调灵活和可编程。
• Flow cache是简单的，强调快速转发。

可以说，Flow cache是根据流表查找结果生成的cache，它是要被注入到内核或者硬件的数据平面转发路径的cache项。

那么，这里就涉及到了cache的形式，它有两种选择：

1. 精确的Flow cache。(OVS称为Microflow cache)
2. 模糊的Flow cache。(OVS称为Megaflow cache)

我们分别看一下。

假设流表中有下面的一条规则：

src IP=200.100.0.0/16 Action=DROP

此时到达一个数据包：

src IP=200.100.10.1 dst IP=100.100.100.100 proto=TCP sport=123 dport=80

其源地址是 200.100.10.1 ，快速路径中未命中任何Flow cache，此时它被交给慢速路径ovs-vswitchd处理查询流表，恰好匹配上述规则，根据精确Flow cache的生成规则，它将生成一条下面的Flow cache并注入内核：

src IP=200.100.10.1 Action=DROP

如果是模糊Flow cache，将会是下面的：

src IP=200.100.0.0/16 Action=DROP

我们来比较一下它们。

如果来自 200.100.0.0/16 网段的不同主机的数据包持续到达，由于源地址不同，精确Flow cache将会持续向慢速路径转交数据包，如果是短连接，那么情况会更加严重，看起来这是多么不明智，严重影响转发效率。

如果采用模糊Flow cache，那么即便在快速路径，也要为数据包执行一次最长前缀匹配算法，如果是Trie数据结构，那么时间复杂度将会是 O ( n l o g n ) O(nlog n) O(nlogn)，比精确Flow cache的 O ( 1 ) O(1) O(1)(理想情况的完美哈希假设下)要差一些。看样子模糊Flow cache的查询性能不如精确Flow cache。

很显然，长连接适用于精确Flow cache，而短连接则适用于模糊Flow cache。

OVS的做法是级联精确Flow cache和模糊Flow cache，也就是说，两类Flow cache全部内置，以多一次哈希查找的代价来平衡长连接和短连接最坏情况的性能损失，可谓精妙！

这里的关键在于， 查询性能相比向慢速路径上报数据包是无关紧要的。

现在的问题是， 模糊Flow cache要模糊到什么程度！

---

如果我们把一个match作为一个维度，那么一条具有N个match的Rule便拥有N个维度，所有的Rule作为一个集合，每条Rule必须全部去映射所有这N个维度各个match的数值，即便某一条Rule没有显示匹配某个match。

比方说，下面两条Rule：

src IP=1.2.3.4 Action=DROP
src IP=5.6.7.8 DPORT=8080 ACTION=NAT

显然，第一条Rule并没有DPORT这个match，然而它作为一个集合整体中的一员，还是隐含了这个match，只是没有显式表达而已，它隐含的DPORT match就是除了8080之外的所有值，于是上面的两条Rule等效于如下的Rule集合：

src IP=1.2.3.4 DPORT=1 Action=DROP
src IP=1.2.3.4 DPORT=2 Action=DROP
src IP=1.2.3.4 DPORT=3 Action=DROP
...
src IP=1.2.3.4 DPORT=8079 Action=DROP
src IP=5.6.7.8 DPORT=8080 ACTION=NAT
src IP=1.2.3.4 DPORT=8081 Action=DROP
src IP=1.2.3.4 DPORT=8082 Action=DROP
...
src IP=1.2.3.4 DPORT=65535 Action=DROP

盗用自己文章的两张图来说明这个多维匹配的原理：


这两个图来自下面的文章：
https://blog.csdn.net/dog250/article/details/77618319

也就是说，整个Rule集必须按照match最多的那条规则确定集合的维度个数，然后所有的Rule都需要基于这些维度进行match数值映射。考虑下面的两条Rule：

src IP=200.100.0.0/16 Action=DROP
src IP=5.6.7.8 DPORT=8080 ACTION=NAT

对于来自200.100.2.1，访问1234端口的数据包，按照上述的最大match维度匹配原则，即便是模糊Flow cache，也会生成下面的cache：

src IP=200.100.0.0/16 DPORT=1234 Action=DROP

此时如果是同样来自200.100.0.0/16网段的数据包访问不同于1234的其它端口，依然会发生cache miss，进而将数据包转交给慢速路径ovs-vswitchd处理。

模糊Flow cache的作用失效了！

解决方案之一就是，采用二次通配机制， 对于命中本来就没有某个match的Rule生成Flow cache时，其没有的那个match采用通配符替代具体值。 比如，数据包命中了Rule：

src IP=200.100.0.0/16 Action=DROP

这条Rule并没有DPORT这个match，所以生成cache时，会生成下面的cache：

src IP=200.100.0.0/16 DPORT=wildcast[1~8079/8081~65535] Action=DROP

---

代价只是在快速路径匹配模糊Flow cache时，多一次通配符运算。

然而，OVS没有采用这种方案(我自己的iptables规则预处理采用的就是这种方案)，而是发明了另一种令人哇塞的方案，即 Staged Lookup 。

Staged lookup生成的Flow cache恰到好处，最后连通配符都不需要。它的精髓在于：

1. 将所有match的一次hash计算过程分为逐渐加入新的match的N次hash计算过程。
2. 只要在第N次hash匹配时发生了不匹配，那么第N-1次(初始化为默认策略)的hash匹配结果就是最终结果。

比方说下面的Rule集合：

M1=m11 M2=m12 M3=m13 M4=m14 M5=m15 Action=A1
M1=m21 M2=m22 M3=m23 M4=m24 Action=A2
M1=m31 M3=m33 M4=m34 M5=m35 Action=A3
M1=m41 M2=m42 Action=A4

一个携带对应5个match的filed分别为f1，f2，f3，f4，f5的数据包在进行匹配查找的时候，不再进行如下hash计算：

H = hash(pkt.f1, pkt.f2, pkt.f3, pkt.f4, pkt.f5);
result = lookup(H, pkt);
return result;

而改成下面的过程：

H1 = hash(pkt.f1, pkt.f2);
result1 = lookup(H1, pkt);
if (!result1)
	return default;
	
H2 = hash(pkt.f1, pkt.f2, pkt.f3, pkt.f4);
result2 = lookup(H2, pkt);
if (!result2)
	return result1;
	
H3 = hash(pkt.f1, pkt.f2, pkt.f3, pkt.f4, pkt.f5);
result3 = lookup(H3, pkt);
if (!result3)
	return result2;

return result3;

这个新的过程将原来的5个match拆分成了3组：

match_group1 = {M1, M2}
match_group2 = {M1, M2, M3, M4}
match_group3 = {M1, M2, M3, M4, M5}

可以保证的是，match_groupN 如果匹配失败，那么 match_groupN 以上新加入的match一定会匹配失败，而 match_groupN-1 一定是一个答案，这意味着生成的Flow cache里可以不包括 result_N 以及以后加入的那些match：

Staged Lookup的本质其实是 “巧妙利用了hash计算的过程”， 考虑到hash计算是可增量进行的，这相当于在hash计算的过程中挂了HOOK。

为了理解这个过程，我们先来看一个标准的可增量hash的过程：

Staged Lookup的过程就是针对上述的标准流程进行了拆解：

非常之精妙！

上述对Staged Lookup的解释有个假设，即hash是可以 增量计算 的，如果是增量计算的hash，Staged Lookup并不会因为hash查找从一次增加到多次而变慢，相反，还会提高效率，因为：

1. hash计算的时间并没有变长，和拆解Stage之前是一样的。
2. hashmap查找次数确实变多了，但被因不匹配而提前退出的hash计算所抵消。

当然，如果每个hash计算的步骤都引入一个种子，那么整个计算过程将不再是增量的，这样确实会增加计算量，然而在OVS中，Stage被典型拆解为4个步骤，hash计算量是微不足道的。

Staged Lookup的原理就说到这里，现在，让我们看最后一个问题，即如何拆解Stage。这个还是看原文更加直观：

应该先匹配那些多样性小(即容易匹配成功的)的match，然后再匹配那些多样性大的match，这样可以 尽可能保证不匹配现象最容易在早期的Stage中被发现。 背后的假设是， 根据TCP/IP分层原则，被封装在越里面的数据，其多样性越广泛。【引用1】

引用1： 不可以独立看待这个结论，因为TCP/IP模型是沙漏型的，而不是倒金字塔，也就是说，独立地看，IP层是多样性最广的，它是腰部。而TCP/UDP层和链路层相对而言多样性并不广泛，TCP/UDP层仅仅有65535个端口，链路层仅仅能看到与当前设备直连的设备。

所以说，要结合业务模型来看待这个结论，我们说TCP的多样性广泛，是结合IP层一起说的，也就是说，我们说的是一个socket。

---

我对OVS的这个Staged Lookup机制是拍案叫绝的，因为它的思路和我之前优化iptables时颠倒Rule，match，Prio维度的思路是一致的。我没有想到的是，竟然还可以对增量计算的过程进行HOOK。

当然了，我说的这些，对于经理而言，应该都是没有意义的。

先就这么多吧。

---

浙江温州皮鞋湿，下雨进水不会胖。