OpenVSwitch，不论是用户空间的ovs-vswitchd，还是内核空间的kernel datapath，最核心都是要实现一个查找算法。对于ovs-vswitchd，需要根据网络数据包的特征（2-4层包头，metadata）从一个个的OpenFlow Table中查找OpenFlow规则。对于kernel datapath，也需要根据网络数据包的特征，从cache中查找datapath actions。OpenVSwitch实现了一个统一的查找算法：TSS（Tuple Space Search），这本质上是一个hash 查找算法。

OpenFlow规则查找

OpenFlow规则基于Match-Action而实现。直观上看的话，Match实现更简单，只需要匹配就行。但是在实际中，为了让包的处理性能达到可用的程度，实现Match比实现Action要复杂的多。因为Match可以是2-4层协议Header中的任意field或者任意的metadata。假设有一条OpenFlow规则匹配了源MAC，目的MAC，源IP，目的IP，源端口，目的端口，那么对于所有需要经过OpenFlow处理网络数据包，都需要将自己的Header中这些filed与这条OpenFlow进行对比，以确保自己匹配或者不匹配这条OpenFlow规则。假设有10000条这样的OpenFlow规则，那么这个网络数据包最坏情况下需要与这10000条规则的Match做对比，才知道自己匹配或者不配。如果OpenFlow有200个这样的table，每个table都有10000条OpenFlow规则呢？所以，直接匹配是没有实际意义的。因为实际环境中，OpenFlow规则很容易达到数万条甚至数十万条。就算OpenVSwitch分了内核空间和用户空间程序，只有首包需要走OpenFlow pipeline，但是光是首包这样处理，也会大大降低网络性能，同时要消耗大量CPU。而OpenVSwitch作为运行在主机的软件交换机，应该尽量减少CPU的消耗，把CPU留给workload。

因此在用户空间，ovs-vswitchd基于TSS实现OpenFlow的匹配，以减少Match所需要的时间。以前面的OpenFlow规则为例，对于需要匹配的源MAC，目的MAC，源IP，目的IP，源端口，目的端口这些具体值，hash成一个散列值，这样10000条规则对应10000个散列值。对于任何需要经过OpenFlow处理的网络数据包，先将其源MAC，目的MAC，源IP，目的IP，源端口，目的端口hash成一个散列值，然后在OpenFlow规则对应的散列值中查找。根据hash的特性，查找时间复杂度为O(1)，就是说，不论有多少条OpenFlow规则，都能在固定时间确认匹配或者不匹配。在一个OpenFlow Table中，可能同时存在多种匹配类型，有的只匹配MAC地址，有的只匹配in_port，对于不同的Match，OpenVSwitch会将其分类，每一类Match构成一个hash table。一个OpenFlow Table里有多少种不同的Match，就会有多少个hash table。当一个网络包需要经过一个OpenFlow Table处理时，网络数据包会在所有的hash table中进行查找，如果所有的hash table都不匹配，那么网络包就miss了，默认会drop掉；如果匹配了一个hash table，那么就按照hash table里具体那一条规则的action执行；如果有多个hash table匹配，那么就看优先级，优先级高的胜出。因此，在下发OpenFlow规则时，应当尽量将相同的Match的OpenFlow规则下发在一个Table中。这样可以减少一个Table中生成的hash table的数量。虽然这算是一个不强的限制，但是本身也符合实际，因为一个OpenFlow Table通常被指定实现某个网络功能，因此会包含大量相同Match的OpenFlow规则。

虽然查找算法很多，但是TSS具有以下优点，使其比其他算法更适合OpenVSwitch和SDN的场景：

• O(1) 的更新时间。前面只看了查找时间，但是SDN控制器同时可能会频繁的更新OpenFlow规则，因此更新时间的性能也很重要。
• hash算法对于任意的OpenFlow Match Field都适用，不论是4层协议的Header还是metadata，还是OpenVSwitch自己扩展的寄存器。
• TSS对内存的消耗是线性的，也就是OpenFlow的规则数与TSS消耗的内存成正比。

实际使用中，在一个OpenFlow Table中查找OpenFlow规则的性能很重要，但是如何在多个Table中查找也很重要。一个实际环境中的OpenFlow table数，通常会在几十左右，这些table共同构成了OpenFlow的pipeline。导致Table数变多的因素有两个：第一是模块化的设计，使得每个table专注一个功能，随着网络功能的增多，对应的table也变多了；第二就是处理向量积的问题，例如匹配目的IP为100个离散的IP，且目的端口是离散的100个端口，这个时候，要么在一个table里面写10000（100*100）条OpenFlow规则，要么在两个Table里面分别写100条规则，这种情况下，为了节省OpenFlow规则数，相应的table数就要增加。

因此，缩短OpenFlow pipeline，对于性能的提升也很重要。

Microflow Caching

如前一篇所述，OVS内核模块早期基于名为microflow的cache。microflow也是基于Match-Action而实现，但是它的Match包含了所有OpenFlow可能的匹配的值，也就是2-4层包头和一些metadata。如果用前面描述的TSS查找算法去实现microflow cache，只需要一个hash table即可，因为这里只有一种match。

只要microflow cache已经建立了，可以实现OVS内核模块的快速查找转发，因为只需要查找一次Hash table就可以完成转发。所以现在的问题是如何快速的建立microflow cache。microflow cache的建立是一个被动的过程，当一个网络数据包在microflow cache对应的hash table中查找失败的时候，会从OVS内核模块上送到ovs-vswitchd，由ovs-vswitchd通过OpenFlow pipeline处理之后，下发这个网络数据包对应的datapath actions，进而建立网络数据包到datapath actions的对应关系。所以cache建立的时间，由两部分组成：第一部分是网络包在用户态ovs-vswitchd进程走OpenFlow pipeline所需要的时间，这个在前一小节介绍过；第二部分是网络包上送的比例。

从整体上来说，越低的网络包上送比例，就能越快的建立cache，进而有越高的网络性能。而通过microflow cache实现的OVS内核模块，无疑每个不同传输层连接都需要将自己的首包上送到ovs-vswitchd。甚至同一个网络连接都需要多次上送网络包，例如因为网络多路径导致IP TTL的不同，也会导致microflow cache查找失败（miss）。对于大量的短连接来说，会有大量的首包上送。因此microflow cache在实际应用的时候并不能达到一个很好的性能。

Megaflow Caching

如果我们来看下面一条OpenFlow流表规则。

priority=200,ip,nw_dst=10.0.0.0/16 actions=output:1

它的作用就是匹配所有目的IP是10.0.0.0/16的网络包，从网卡1送出。对于下面的传输层连接，对应的action都是一样的。

11.0.0.2:5742 -> 10.0.0.10:3306
11.0.0.2:5743 -> 10.0.0.10:3306
11.0.0.2:5744 -> 10.0.0.11:3306
11.0.0.3:5742 -> 10.0.0.10:3306

但是对应于microflow cache来说，就要有4条cache，需要上送4次ovs-vswitchd。但是实际上，如果在kernel datapath如果有下面一条cache，只匹配目的IP地址：

ip,nw_dst=10.0.0.0/16 actions=output:1

那么数以亿计的传输层连接，可以在OVS内核模块，仅通过这条cache，完成转发。因为只有一条cache，所以也只有一次上送ovs-vswitchd。这样能大大减少内核态向用户态上送的次数，从而提升网络性能。这样一条非精确匹配的cache，被OpenVSwitch称为megaflow。

Megaflow能提升网络性能的前提是，大量的网络的连接可以共用一组datapath action。因为这样，在microflow cache中对应的Hashtable里面，就会有大量的key拥有相同的value，这些key本身存在合并的可能。

Megaflow cache更像是一个OpenFlow Table，因为它支持任意形式的packet field matching。类似的，OpenVSwitch也是通过TSS来实现megaflow cache，由于现在Match有多种类型，所以对应于megaflow cache最终会有多个hash table。OVS内核模块转发时，一个网络数据包需要在这多个hash table中进行查找。在OpenVSwitch中，megaflow对应的hash table数称为Mask。同时相比OpenFlow Table，megaflow cache有一些简化，一个是它没有priority，这样在TSS查找时，只要找到了就可以立刻终止查找（不用考虑更高优先级）；第二个，为了避免混淆，userspace只会下发非重合的megaflow cache，这样一个网络包只会跟一条megaflow cache匹配；第三，megaflow cache只有一个table，而不像OpenFlow是由多个table组成的pipeline。

OpenVSwitch提供命令打开或者关闭Megaflow cache。

ovs-appctl upcall/disable-megaflows
ovs-appctl upcall/enable-megaflows

Microflow vs Megaflow

应该说，Megaflow和Microflow各有优缺点。Microflow的优点是，只有一个Hash table，一旦cache建立，内核中只需要查找一次Hash table即可完成转发，缺点是每个不同的网络连接都需要一次内核空间上送用户空间，这有点多。Megaflow的优点是，合并了拥有相同的datapath action的网络连接所对应的cache，对于所有这些网络连接，只需要一次内核空间上送用户空间，缺点是cache建立以后，要查多次Hash table。如果每个Hash table命中的概率一样，那么平均需要查找 (n+1)/2 次hash table，最坏要查n个hash table。

选择Megaflow还是Microflow，就要看实际中究竟是内核空间上送用户空间的消耗大，还是在内核模块转发时，多查几次hash table代价大。对于长连接占多数的网络流量来说，Microflow占优势，对于短连接占多数的网络流量来说，Megaflow占优势。那在实现OVS内核模块时，究竟应该选用哪种cache模型。俗话说，小孩子才做选择，成年人全部都要。所以OVS内核模块采用Microflow+Megaflow的两级cache模式。

Microflow作为第一级cache，还是匹配所有OpenFlow可能的匹配的值，但是这时对应的Action不再是Datapath action，而是送到某个Megaflow的Hash table。当网络包送到kernel datapath时，会先在Microflow cache中查找，如果找到了，那么再接着送到相应的Megaflow hash table继续查找；如果没有找到，网络包会在kernel datapath的Megaflow cache中继续查找，如果找到了，会增加Microflow cache的记录，将后继类似的包直接指向相应的Megaflow Hash table；如果在Megaflow还是没有找到，那么就要上送ovs-vswitchd，通过OpenFlow pipeline生成Megaflow cache。

这样不论Megaflow cache有多少个hash table，对于长连接来说，只需要查找两次hash table即可完成转发，长连接的性能得到了保证。对于短连接来说，因为Megaflow cache的存在，也不用频繁的上送ovs-vswitchd，只需要在OVS内核模块多查几次hash table就行，短连接的性能也得到了保证。

这里似乎看起来没有问题，但是因为Megaflow现在是采用模糊匹配，究竟怎么生成Megaflow成了个问题。Megaflow应当尽量模糊，以匹配更多的网络连接，从而减少上送ovs-vswitchd的次数，下一篇看看OpenFlow的定义下，如何生成尽量模糊的Megaflow Cache。