⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Mar.25 2021
本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。
1. Open vSwitch 概述
正如我们在 网络虚拟化：基本概念 中所提到的 网络虚拟化 的概念， Open vSwitch 就是虚拟网络的开源实现。官方定义为：一个虚拟的网络多层交换机的软件实现。以下分段介绍一下 Open vSwitch的一些特点。
Open vSwitch 采用了 SDN 的思想，即它所构建的 vSwitch 实际上是 遵循 Openflow 协议的SDN交换机，北向还会存在一个本地的或者远程的 SDN控制器 来对这些 vSwitch进行控制。基于 SDN 的设计思路使得虚拟机集群的控制与管理变得更加方便。
Open vSwitch 具有分布式的特性，这点我们在 网络虚拟化：基本概念 也有稍微提到，分布式的特性使得底层物理服务器的分散性对上层虚拟机网络的构建是不可见的，因此可以 “透明” 地实现跨主机的虚拟机间通信。
Open vSwitch 既可以在 Hypervisor 中作为 SDN交换机 运行，又可以在专用的交换设备中作为控制堆栈来运行，因此它已经被移植到多个虚拟化平台，交换芯片组和网络硬件加速器上。比如，它是 XenServer（思杰的虚拟机平台）中默认的网络交换机，它支持 Xen, Linux KVM， Virtual Box等 hypervisor，移植到 Intel 的 hypervisor Hyper-V 上也是可行的。Open vSwitch 的 Linux 内核实现自从内核版本3.3之后就被合并入主线。
Open vSwitch的大多数源代码都是用与平台无关的C语言编写的，从而可以轻松移植到各种环境。
2. OpenFlow基础
如果你对 OpenFlow还没有基础的了解，可以查阅 OpenFlow 基础概念。
3. Open vSwitch 设计思路
此部分参考自论文：The Design and Implementation of Open vSwitch, NSDI' 15
(1) Open vSwitch 结构大览
正如我们上面所阐述的，OVS使用的是基于 Openflow 的SDN模型，在本地或者远端还存在着一个 SDN控制器 用于对流和流表进行增加、删除、更新、监控、获取统计数据等操作。而在本地操作系统上有两个比较主要的组成模块：ovs-vswitchd 和 datapath kernel module，前者是用户空间的常驻程序，功能有二：(a) 接收来自 SDN控制器 的流控制规则（称作 Action）；(b) 将转发规则缓存给后者，以加速转发操作。而后者是内核模块，负责对网络数据包做处理。以下我们借助一个数据包进入OVS被处理的流程，对系统的具体工作方式做阐述。
我们结合上图进行分析，当某条流的第一个 packet 到达时，在 datapath kernel path 并不清楚该如何处理这个 packet，它便会将这个 packet 递交给用户态的 ovs-vswitchd，ovs-vswitchd 存储着该把某种特定 packet 转发至哪个 port 或者 tunnel 的转发规则（来自 SDN 控制器），当然 Action 还可能会包括 对包的修改，对包的采样，或者丢弃包等。拿到对应的 Action 后， ovs-vswitchd 把数据包和相应的 Action 交还给 datapath kernel module，后者会将这个 Action 缓存起来，以应付后面到达的同种类型的 packet。
(2) OVS 流缓存 (Flow Cache) 设计
上面我们谈到了 OVS 由 ovs-vswitchd 和 datapath kernel module 两个组成部分组成，这一节我们结合一下 OVS 的开发历史来关心一下 OVS 具体是如何把转发规则缓存到内核模块中去的。
在2007年刚刚开始开发运行在 Linux 上的 OVS 的时候，工程师们当然会认为只有把数据包的转发逻辑做在内核里才会有比较好的性能，因此他们把所有的 OpenFlow 处理逻辑写在了一个内核模块里，所有的数据包到达内核后都得到内核模块里按照标准的 OpenFlow 标准过一遍所有的流表，然后再送上用户空间。但是这么做有几个弊端：
(a) 在内核里开发及其的困难，分布在系统里的其它内核模块也会不断更新，随时可能会被更改；
(b) 基于内核模块开发的 OVS 不被 Linux 的发布版本所接受（可能是因为太庞大冗杂了）；
(c) 直接使用 OpenFlow 流表组成的 pipeline 处理数据包会占用大量的 CPU 周期，导致虚拟机的运行收到一定的影响，得不偿失。（OpenFlow 在硬件 SDN 交换机上可能可以运行的很快，但是在通用的处理器上就很难做快了）。
因此就有了上面所讲述的，用户态模块实现 OpenFlow 逻辑 (i.e. ovs-vswitchd)，内核模块利用流表缓存实现数据包的处理 (i.e. datapath kernel module)，下面对 内核缓存的几个版本迭代所简要介绍，以了解各个设计的意义。
(a) OVS Cache V1: Microflow Cache (微流缓存)
初代的 OVS Cache，把内核里的缓存做成了一张单一的 Hash 表，这张 Hash 表的 Hash Key 覆盖了所有 OpenFlow 所支持的数据包头匹配字段，而 Hash Value 项则组合了针对某条流的若干 OpenFlow 流表组合出来的如上图所示，这种方案被称为 Microflow Cache (微流缓存)。这种方案是十分简单和轻巧的，因为它的内核实现完全就只是一张 Hash 表。同时我们很容易发现，这种方式可以照顾到每一条小流的具体规则，每一条缓存表项都是细粒度的。举个例子，对于一条单流来说，如果上层的控制器修改了其转发路径，那么这条单流的数据包会遇到 IP TTL 失效的问题，这时候内核模块就会去向用户空间询问针对这条单流的转发规则，可见微流缓存实现了对每一条小流的精细控制。
在 OVS 的论文中，它又提到另一个问题：从上面这个例子出发，我们可以发现 OVS 会有一个很重要的性能维度 —— 流表项建立时间 (flow setup time)，即从 “内核空间发生流规则匹配miss” 到 “用户空间将更新的流表项缓存到内核空间模块” 的时间。OVS 采用了几种方法来解决这个问题：
(a) Batch Flow Setup：通过“将针对单流的流表项规则打包再下放内核缓存”的方式，减少系统调用次数来提高下放性能。
(b) Multi-thread：在用户空间利用多线程，将下放的任务绑定多条线程上来充分利用CPU多核的优势。
(b) OVS Cache V2: Megaflow Cache (大流缓存)
基于 MicroFlow 的设计在实际测试中存在一个问题：由于 MicroFlow Cache 是一种细粒度的控制方案，在有大量的 短时小流 的情况下，会出现很多的 Cache Miss，不仅导致数据包要频繁穿越 内核态-用户态 边界，而且在用户态还需要针对大量的 Cache Miss 的小流数据包执行一长串的 OpenFlow 流表查询。如上图所示，我们把用户空间的流表 pipeline 成为 慢速路径 (slow path)，把内核空间的 cache 模块称为 快速路径 (fast path)。当有数据包通过慢速路径的比例上升时，OVS 的转发性能必定会下降。
OVS 认为相比于 Microflow Cache，Megaflow Cache (大流缓存)可以解决这个问题。Megaflow Cache 允许内核中缓存的表项不再是针对某一个具体的小流，而可以是小流的集合。这里我们举一个例子。
假设在慢速路径 OpenFlow 流表中存在这样一条表项：
| 匹配域 | Action |
|---|---|
| src IP=200.100.0.0/16 | DROP |
此时到达一个数据包：
| 数据包头 |
|---|
| src IP=200.100.10.1, dst IP=100.100.100.100, proto=TCP, sport=123, dport=80 |
假设快速路径中未命中任何 cache，此时它被交给慢速路径 ovs-vswitchd 处理查询流表。结合 OpenFlow 流表中的表项，根据 MicroFlow Cache 的生成规则，它将生成一条下面的 MicroFlow Cache 并注入内核：
| 匹配域 | Action |
|---|---|
| src IP=200.100.10.1 dst IP=100.100.100.100 proto=TCP sport=123 dport=80 | DROP |
如果是 Megaflow Cache，将会是下面的：
| 匹配域 | Action |
|---|---|
| src IP=200.100.0.0/16 | DROP |
因此可以发现，MetaFlow Cache 可以解决 MicroFlow Cache 中由于大量短连接带来的频繁内核 Cache miss 的问题。与 MicroFlow Cache 相比，它更接近于 OpenFlow流表，体现在于 (a) 它在匹配的时候支持任意域的组合，且 (b) 支持对流的集合的处理而非只针对单独小流。在具体的实现中，为了支持上述两点，MetaFlow Cache 做了两个事情：
( a) 为了实现自定义域的匹配：它所使用的 Hash 表不再是一张而是多张，每一种 Hash Key 的组合使用一张 Hash 表，以实现任意域的匹配，具体实现就是下文将要讲述的 元组空间搜索算法 (Turple Space Search)。每一个数据包到达 MegaFlow 表时，需要在多个 Hash 表中进行匹配，直到找到匹配的表项。
(3) 网包分类 (Packet Classification) 算法
网包分类 指的是在一张流表中一个网络数据包匹配到相应的处理规则的过程。我们都知道 OpenFlow 中采用了 多级流表技术，对于一个数据包可能需要 10+ 个的流表进行处理，而一张流表内可能有需要若干次的哈希操作才能匹配到目的流表项，因此总共加起来可能会有 100+ 次的哈希操作，所以数据包的处理将是花费时间的。基于这种背景，对于应用在网络虚拟化中的SDN流表来说，由于匹配的域 (field) 实在是太通用了，可能会是以太网地址、IPv4地址、IPv6地址、TCP和UDP端口等的任意组合，如果包分类器没有做好，网包分类将会在原有基础上更加花费时间。而且，在通用处理器上做基于算法的网包分类本身就是一件成本很高的事情。所以在OVS中必须对这个问题进行优化，因为 hypervisor 的首要任务是运行用户的工作负载 (i.e. VM)，花太多的资源在网络上反而会得不偿失。
OVS 在包分类器上采用的办法是 元组空间搜索算法 (Turple Space Search)，它为每一个匹配组合创建一张 hash 表，比如 (MAC src, MAC dest)，(IP src, IP dest, port src, port dest) 等。当每个包到达时，必须在所有的哈希表（对应所有匹配组合）中进行匹配，找出来所有匹配到的表项。若只有一条匹配项，则直接执行匹配项中对应的 Action；若有好几条匹配项，则执行优先级别最高的匹配项对应的 Action。在 ovs-vswitchd 和 datapath kernel module 中都是用这样的哈希表实现的，即内核空间 Megaflow Cache 采用的是这种设计，用户空间也使用这种设计实现了 OpenFlow 流表。值得注意的是，对于每一个数据包来说，虽然这样的搜索复杂度并不是最低的，但是它具有以下几个特点：
(a) Update 的复杂度是 `\O(1)`，这里的 Update 指的是将来自控制器的更新转化为 hash 表项的过程。在虚拟环境中，控制器的更新是十分频繁的，因此这样的特性对于更新操作来说是十分友好的。
(b) 这种方案使得域的匹配变得更加通用，可以任意组合，且不需要任何与算法相关的修改。
(c) 这种方案对内存的占用是随着流数量线性增长的。
附录：参考源
- https://www.usenix.org/system/files/conference/nsdi15/nsdi15-paper-pfaff.pdf, The Design and Implementation of Open vSwitch, NSDI’ 15
- https://www.youtube.com/watch?v=fmYpT0dT9fU&t=618s, NSDI ‘15 Presentation - The Design and Implementation of Open vSwitch