OpenVSwitch实现浅谈（二）

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