简介
硬件交换机采用TCAM(ternary content-addressable memory)用于高速报文分类和转发。而虚拟交换机使用多级缓存和流缓存来实现更高的转发速率。ovs-dpdk具有三层查找表/缓存。第一级表EMC(Exact Match Cache)，无法实施通配符匹配。 dpcls是第二级表，TSS(tuple space search) classifier。尽管它是由哈希表（即子表）实现的，但它可以作为通配符匹配表工作。第三级表是ofproto classifier表，其内容由符合OpenFlow的控制器管理。ovs-dpdk中三层缓存架构的图：
报文会遍历多个表，直到match，然后根据action对报文进行操作。在正常的部署中，处理几千个流很常见，所以EMC很快就饱和了，这样大多数的报文将与dpcls匹配，这里将成为ovs的性能关键。
classifier深入浅出
ovs第二级表使用TSS classifier对报文进行分类，为每个match类型匹配一个hash表。匹配报文IP字段一些流表示一个hash表，不同匹配项(比如MAC)的流表表示为另一个hash表。搜索TSS classifier需要对每一个元组进行匹配，TSS查找的复杂度不是最优的，但是相对于决策树classifier算法，还是更有效的。决策树最坏的情况时树的高度，即有N个子表的TSS classifier，复杂度为O(N)，并且大部分开销在hash计算中，下面列举一下TSS classifier的优势：
- 在几十万活跃的并行流表的情况下，controller依然会经常地添加删除流表。如果用决策树作为节点的插入和删除，会相当的消耗CPU，而hash表对于删除和添加需要较少的CPU周期。
- TSS具有O(N)的空间和时间复杂度，最坏的情况下，TSS的内存操作和hash表的数量相当，并且hash表的数目和数据库中的规则数目一样多，但是仍然比决策树好。
- TSS可以支持任意数量的包头字段。
使用几十个hash表，classifier查找意味着所有的子表都要遍历，直到match。hash表中的流表缓存项时唯一的，不会重叠。因为先匹配的就是唯一匹配，搜索操作终止。classifier中子表的顺序时随机的，并且在运行时创建和销毁，下图展示了多个hash表/子表的dpcls的数据流向：
使用子表的rank值优化dpcls
在OVS2.5中，每个PMD线程创建一个classifier实例。每次查询都遍历所有活动的子表，直到匹配。平均来说，一次dpcls的查找需要访问N/2的子表，N表示激活的子表，虽然单个hash表查找本身是快速的，但是由于查找之前的hash值计算拉低了性能。
为了解决这个问题，OVS2.6命中数对子表进行了排序。此外每个入端口创建一个dpcls实例。考虑到在实践过程中，发现入口的流量和命中的一个子表或者子表的一个小子集有强相关性。排名的目的是对子表进行排序，以使得最大命中子表将被优先排序并排列得更靠前。因此，这允许通过减少在查找中需要搜索的子表的平均数量来提高性能。
图下图描述了对应入端口的多个dpcls实例创建。在这种情况下，有三个入口端口，其中两个是物理端口（DPDK_1，DPDK_2）和一个用于VM_1的vHost-user端口。将为DPDK_1，DPDK_2和VM_1 vHost用户端口分别创建DPDK_1 dpcls，DPDK_2 dpcls和VM_1 dpcls实例。每个dpcls将管理来自其相应端口的数据包。例如，来自VM_1的vHost-user端口的报文由PMD线程1处理。从入口报文的报头字段计算哈希密钥，并且使用哈希密钥在第一级高速缓存EMC 1上进行查找。在未命中时，数据包由VM_1 dpcls处理。
Hash表怎么实现通配符匹配
这里我们将讨论如何使用哈希表来实现通配符匹配。让我们假设控制器下发一个流表，被称为Rule #1的规则如下：
Rule #1: Src IP = "21.2.10.*"因此匹配必须发生在前24位，其余8位是通配符。此规则可以由OVS命令下发，例如：
$ ovs-ofctl add-flow br0 dl_type=0x0800,nw_src=21.2.10.1/24,actions=output:2在插入上述规则的情况下，具有类似“21.2.10.5”或“21.2.10.123”的Src IP的报文应该匹配。当接收到类似“21.2.10.5”的数据包时，EMC和dpcls都会miss。 匹配流将在ofproto classifier找到。 学习机制将把找到的流表缓存到dpcls和EMC中。以下是仅关注dpcls内部的此用例的详细信息的描述。
子表存储规则
我们首先创建一个适当的Mask #1，然后存储带有通配符的Rule #1。Mask #1作为通配符的掩码，当在该位位置上需要匹配时，掩码的每个位将被设置为1; 否则，它将为0。在这种情况下，Mask #1为"0xFF.FF.FF.00"。然后将新的哈希表HT 1实例化为新的子表。
掩码被应用于规则（参见下图），并且结果值作为hash函数的输入。哈希输出将指向可以存储Rule #1的子表位置（我们不在此处考虑冲突，这不在本文档的范围之内）。
HT 1将收集Rule #1和其它相似规则（具有相同的字段和相同的通配符掩码）。例如，它可以存储另一个规则，例如：
Rule #1A: Src IP = "83.83.83.*"因为此规则指定Src IP - 并且没有其他字段，并且其掩码等于Mask #1。
请注意，如果我们要插入具有不同字段和/或不同掩码的新规则，我们需要创建一个新的子表。
Packet #1查找
源IP为21.2.10.99的Packet #1需要处理，将在唯一的现有hash表HT 1上搜索它（如下图所示）。源IP和Mask #1计算，然后计算hash以在子表中找到匹配条目。 在这种情况下，找到匹配条目然后命中。
再插入一条规则
现在让我们假设控制器添加第二个通配符规则，为了简单起见，仍然在源IP地址上，使用网络掩码16，从这里称为Rule #2。
Rule #2: Src IP = "7.2.*.*"$ ovs-ofctl add-flow br0 dl_type=0x0800,nw_src=7.2.21.15/26,actions=output:2使用上面插入的规则，具有类似“7.2.15.5”或“7.2.110.3”的Src IP的报文将匹配规则。基于最后2个字节中的通配符，创建适当的Mask #2，在这种情况下："0xFF.FF.00.00。"（参见下图）
注意，HT 1可以仅使用网络掩码"0xFF.FF.FF.00"来存储规则。这意味着必须创建新的子表HT 2来存储Rule #2。Mask #2应用于Rule #2，并且结果是用于hash计算的输入。结果值将指向将存储Rule #2的HT 2位置。
Packet #2查找
源IP为7.2.45.67的Packet #２需要处理，我们有两个活动的子表（HT 1和HT 2）。查找会在两个子表中重复进行。我们首先在HT 1子表根据掩码"0xFF.FF.FF.00"查找（如下图所示），源IP和Mask #２计算，然后计算hash以在子表中找到匹配条目。
结果我们在HT 1子表中没有找到对应的项，所以是miss。继续下下一个子表HT 2查找（见下图），重复上面的流程，只是掩码使用HT 2的掩码"0xFF.FF.00.00"
这次Packet #2匹配到了规则。
具有多个入端口的场景
此用例演示了在具有四个输入10G端口的Intel® Ethernet Controller X710 NIC卡上的classifier行为。 在每个端口上，专用PMD线程将处理传入流量。为了简单起见，下图仅示出了pmd60和pmd63作为port0和port3的PMD线程：
- dpcls处理了源IP为[21.2.10.99]和[7.2.45.67]的报文之后的信息
- EMC处理源IP为[21.2.10.99]和[7.2.45.67]的报文之后的信息
- pmd63处理端口3来的报文，图中展示处理IP为[5.5.5.1]的报文之后的信息
- pmd60收到的报文[21.2.10.2]在EMC中不会匹配，而是在Port 0 Classifier中匹配规则，然后新条目会添加到EMC
- pmd63收到的报文[5.5.5.8]在EMC中会miss，但是在Port 3 Classifier中会匹配规则，然后新条目会添加到EMC
详细的路径
OVS-DPDK具有三层查找表/缓存。传入数据包首先与EMC(Exact Match Cache)匹配，并在未命中的情况下发送到dpcls(megaflow高速缓存)。dpcls实现为TSS(tuple space search)，其支持对报文报头字段的任意逐位匹配。不匹配dpcls的数据包被发送到OpenFlow pipeline，也称为ofproto classifier，由下图所示的SDN控制器配置。
报文接收路径
PMD(poll mode driver)线程连续轮询列表中的输入端口。 从每个端口，它可以检索不超过NETDEV_MAX_BURST(32)的数据包数量。然后可以基于活动流规则的集合来对每个输入报文进行分类。 分类的目的是找到匹配的流，使得可以相应地处理报文。每个流对数据包进行分组，每个组将被处理以执行指定的操作。 下图显示了报文处理的阶段。
流表由dp_netdev_flow数据结构定义(不要与struct流混淆)，并存储到名为flow_table的hash表中。存储在流中的一些信息如下
- Rule
- Actions
- Statistics
- Batch (queue for processing the packets that matched this flow)
- Thread ID (owning this flow)
- Reference count
通常，flow和rule一词可互换使用; 但是，请注意，rule是flow的一部分。存储在dpcls子表中的条目是{rule, flow pointer}对。 然后可以将dpcls分类归纳为两步过程，其中：
- 通过查找，从子表中找到一个匹配的规则
- 执行相应流表的action
下图展示了报文分类和action执行的调用关系图
当接收到报文时，报头字段被提取并存储到miniflow数据结构中，miniflow是EMC处理的一部分。miniflow是数据包的压缩表示，有助于减少内存占用和cache line。
可以对分类的报文执行各种动作，例如将其转发到某个端口。可以使用其他操作，例如添加VLAN标记，删除数据包或将数据包发送到conntrack模块。
EMC调用关系图
EMC实现为hash表，其中匹配必须完全发生在整个miniflow结构上。当启用RSS模式时，hash值可以由NIC(network interface card)预先计算; 否则需要在软件中使用miniflow_hash_5tuple()计算hash。
在emc_processing()中，在miniflow提取和hash计算之后，在EMC中执行查找以匹配。当找到有效条目时，将执行精确匹配检查以将该条目与从报文提取的miniflow进行比较。在未命中的情况下，对下一个链接的条目重复检查（如果有的话）。如果未找到匹配，则将稍后针对dpcls（二级高速缓存）匹配报文。上图描述了精确匹配高速缓存中的报文处理的调用图。
Datapath Classifier调用关系图
下图展示了dpcls的调用关系图
正如我们上面说的，一次dpcls的查找会遍历所有的子表。从报文中提取的miniflow和子表的掩码得到一个查找关键字，下图展示了相关计算的调用
dpcls的查找会在多个子表中重复查找，直到匹配。如果miss，则会求助于ofproto table。如果命中，检索到的值是指向流表的指针，流表确定报文的动作。子表的查找涉及以下操作：
- 子表掩码会确定报文miniflow字段的子集的关注点，然后掩码和字段的子集生成一个查找关键字，比如上面提到的源IP的掩码，miniflow就只关心源IP字段
- 通过搜索关键字计算出hash值，然后根据hash值找到子表的条目
- 如果条目找到，由于存在冲突的可能性(hash表中经常会出现)，需要判断条目和搜索关键字是否匹配，不匹配则继续在hash值的链表上继续匹配。
由于dpcls带有通配符的属性，存储的条目也被成为megaflow，因为一个条目可以匹配多个报文，比如src IP = 21.2.10.*可以匹配源IP为21.2.10.1，21.2.10.2和21.2.10.88的报文都匹配上面的规则。另一方面，EMC中存储的是microflows(不是miniflow)
子表的创建和销毁
datapath classifier中子表的顺序是随机的，子表可以在运行时创建和销毁。每个子表可以收集具有特定预定义掩码的规则，当必须将新rule插入到classifier中时，遍历所有现有的子表，直到找到与rule掩码匹配的合适子表。 否则，将创建一个新的子表以存储新rule。下图描绘了子表创建调用图。
当子表中的最后一条rule被删除的时候，子表为空即销毁，下图展示了子表删除调用图
慢路径调用关系图
在dpcls查找未命中时，数据包将通过ofproto表进行分类，参见下图。dp_netdev_upcall()触发upcall。 ofproto层的回复将包含关于报文分类的所有信息。 除了执行操作之外，还将激活一个学习机制：将存储一个新流，将一个新的通配规则插入到dpcls中，并将一个精确匹配规则插入到EMC中。 这样，双层高速缓存将能够在将来直接管理类似的报文。
报文处理
根据活跃的流表对报文进行分类。根据匹配的流表，将接收到的报文分成组。每个组被排入特定于流表的批处理，如下图所示。
进入同一批处理的所有数据包将使用流表的action进行处理。为了提高报文的转发性能，属于同一流表的报文直接批处理了。在某些情况下，批处理中可能有非常少的数据包。在最坏的情况下，每个报文都命中不同的流表，因此每个批处理将仅有一个报文。当通过DPDK接口发送较少的报文时，这变得特别低效，因为它引起昂贵的MMIO写入。为了优化MMIO事务并提高性能，实现了中间队列。当它们的计数大于或等于32时，发送入队分组。下图描述了如何从emc_processing()和fast_path_processing()触发报文批处理。
action调用关系图
action是批量完成的。操作的典型示例是在输出接口上转发报文。下图描述了通过调用netdev_send()在输出端口上发送报文的情况。
报文转发到物理端口的例子
上面调用图描绘了从入口到执行action阶段的分组路径的整体图，其中命中的报文被转发到某个输出物理端口。
Intel处理器加速Classifier
hash表查找的平均时间复杂度是O(1)。高性能hash表的基本成分是良好的hash函数，其可以减少冲突和可以计算hash的速度。OVS-DPDK使用hash表实现了EMC和dpcls。如前所述，EMC查找可以利用NIC启用的RSS计算的哈希值。相反，在dpcls的哈希是完全计算在软件使用murmuhash3。提高dpcls的性能对于提高整体OVS-DPDK性能至关重要。
在OVS处理几千个流表的实际部署中，EMC由于容量有限(8192个条目)而迅速饱和。因此，大多数输入数据包将针对dpcls进行检查。虽然单个子表查找本质上是快速的，但是在几十个子表中看到显著的性能下降。classifier性能受损，因为必须对每个子表重复哈希值计算，直到找到匹配。为了加快hash计算，可以在Intel处理器上利用内置的CRC32内在函数。在具有Intel® Streaming SIMD Extensions instruction set支持的X86_64处理器上，可以通过在软件配置期间传递"-msse4.2"来使用CRC32内在函数。例如，为了利用内在性，OVS-DPDK可以使用适当的CFLAGS进行配置，如下所示。
./configure CFLAGS="-g -O2 -msse4.2"如果您使用的是不同的处理器，并且不知道要选择哪些标志，我们建议使用"-march = native"设置。这样，GCC将检测处理器并自动为其设置适当的标志。如果在目标机器之外编译OVS，请不要使用此方法。
./configure CFLAGS="-g -O2 -march=native"