背景在ovs交换机中，报文处理流程可以分为以下三个步骤：协议解析、表项查找和action执行，其中最耗时的步骤是tableitem为了进行搜索，流表中往往有大量的表项。如何根据数据包的信息快速找到对应的流表项是ovs交换机的一个重要功能。在openflow协议中，支持多级流表的形式，可以类比将一个复杂的函数打散成小的函数，实现管道的功能。详见下图：在上图中可以看到，一个数据包进入后，会经过多个流表，每个流表负责特定的功能。比如上图中表1中的流表项，只会匹配数据包中的L2信息。流表的处理使得整个数据包的查询形成一种流水线处理方式。ovs流缓存设计首先需要明确ovs中的多级流表存放在用户空间，流表的缓存存放在内核态。当一个数据包进入ovs时，首先会查询内核态中的缓存信息。如果命中，则直接执行相应的动作。否则通过netlink发送到用户空间，用户空间查找多级流表。要继续向控制器抛出消息信息，控制器会下发相应的规则。ovs和controller的关系可以参考我之前的博客。ovs中关于流表的查询经历了三个过程：微流缓存微流缓存的思想很简单，如下图所示：在多级流表的查询过程中，消息和每个流表的每个流表项都会进行比对，在这个过程中会耗费大量的时间。微流缓存的思想是将多级流表查询的结果按照一定的表项格式直接缓存在内核态，下次到达时同样的数据报文。在内核态使用hash方式直接命中时，二次时间复杂度为$O(1)$，微流缓存的劣势也很明显：实际上存在很多短命类型的流量，导致访问量低命中率因为MicroflowCache是??基于Hash的精确匹配查表，所以数据头的微小变化都会导致命中缓存失败（比如TTL）。MegaflowCache虽然是基于微流缓存的流表查询方式，但是数据报文二次命中的时间比较复杂。速度达到$O(1)$，但其真正的性能瓶颈在于用户空间的查询。如何减少数据包进入用户态是一个很重要的问题。为了解决精确匹配的问题，减少进入用户态的数据包数量，ovs使用megaflowcache代替microflowcache的匹配方式。Megaflowcache是??基于TTS（TupleSpaceSearchAlgorithm）的实现，使用模糊匹配代替microflowcache的精确匹配，通过增加内核态的查询时间（从1次hash搜索到k次，仍然是一个常数时间，与TTS算法中的表数有关），减少数据包进入用户态的次数，在TTS算法中会说明。megaflowcache的一个简单实现是将所有多级流表的级联结果存储在内核态中，如下图：将所有流表级联后的一张大表存储在内核态中。显然，这种方法简单粗暴，但是内存开销也很大。一个好的方法是使用'Lazy'方法，如下图，数据包先通过模糊匹配的方式检索内核中的表，如果所有表都匹配不到，则查询用户态，然后发送All将状态中查询到的条目合并为一个条目，然后插入到内核态的表中。需要注意的是，上图中的megaflowcache是??一张表。在实际的ovs实现中，因为使用了TTS，所以megaflow缓存是由多个表组成的链表。Microflowcache+MegaflowCache目前ovs版本采用的是第三种查询方式，即microflowcache和MegaflowCache结合，其中microflowcache作为一级缓存，MegaflowCache作为二级缓存.是多级流表返回的结果，但是是MegaflowCache中的最后一个hitindex。当一条数据报文到达时，首先通过对报文信息进行哈希处理，检查微流缓存中是否存储了对应的哈希值。如果存在，则查询对应哈希值指向的索引。该索引用于在对应的Megaflow链表中定位某一项。一个元素表，然后在这个元素表中查找。整体解释可能有点啰嗦。我也是第一次写博客，对ovs了解不够。涉及到很多细节，我不是很清楚。希望通过分享与大家交流。参考文献[PfaffB,PettitJ,KoponenT,etal.OpenvSwitch的设计与实现[C]//NSDI。2015,15:117-130.](https://www.usenix.org/system...OpenvSwitch流量查表分析TheDesignandImplementationofOpenvSwitch作者演讲ppt作者：yearsj转载请注明出处：https://segmentfault.com/a/11...
