深入理解 Open vSwitch(三):流缓存设计

1、前言

我们在 《深入理解 Open vSwitch(二):体系结构》一文中提到,为了提高报文转发性能,Open vSwitch 在其快速路径 —— 内核模块 datapath 中维护相应的流缓存。因此,我们将在本文介绍 OVS 的流缓存设计。注意,本文基于 OVS 2.13.4 版本 进行讲解。

2、OVS 流缓存设计的改进过程

OVS 的流缓存设计经历了三个阶段:microflow 缓存、megaflow 缓存以及 microflow + megaflow 缓存。

2.1、microflow 缓存

在早期版本中, 为了提高报文转发性能,OVS 在内核模块中实现了整个 OpenFlow 处理流程。然而,由于开发和更新内核模块的难度较大,OVS 不得不放弃了这种实现方式。取而代之的是 microflow 缓存。microflow 的缓存条目是 OpenFlow 的查表结果(即 action),通过单个哈希表实现,哈希表的键为网络报文的特征值,值为 OpenFlow 查表的结果。microflow 缓存条目的粒度非常细,精确到单个传输连接的状态。

理想情况下,microflow 缓存可以在 O(1) 时间内完成查表。然而,由于 microflow 缓存维护的是单个网络连接的状态,因此在大量的短连接网络环境下,microflow 缓存的命中率会非常低,进而导致大部分报文被上送到(upcall)到用户态,并在用户态进行 OpenFlow 查表,这导致性能骤降。

2.2、megaflow 缓存

为了解决 microflow 缓存存在的问题,OVS 用 megaflow 缓存替代了 microflow 缓存。与 microflow 缓存支持精确查表不同,megaflow 缓存是支持通配查找的、单独一个的哈希表,因此其缓存条目的粒度更大,可以缓存比单个传输连接更为宽泛的状态。megaflow 基于 元组空间搜索算法(Tuple Space Search,简称 TSS) 实现,该算法会根据 OpenFlow 流表来创建若干个匹配项,且每个匹配项都对应哈希表中的哈希桶。假设存在 n 个匹配项,即存在 n 个哈希桶,那么,在最佳情况下只需要查询 1 个哈希桶就找到了匹配的规则,而在最坏情况下需要查询所有的哈希桶,也就是 n 个,因此 megaflow 缓存的平均查表次数为 (1 + n) / 2,即平均查表开销为 O(n/2)

可见,megaflow 缓存相比于 microflow 缓存,尽管可以减少报文进入用户空间查表的次数,但是增加了报文在内核空间查找哈希桶的次数。

2.3、microflow + megaflow 缓存

从上文可知,microflow 缓存 和 megaflow 缓存各有优劣:microflow 缓存通过单个哈希表实现,可以在 O(1) 时间内完成查表,然而在大量短连接的网络环境下,需要多次将报文上送到用户态,并在用户态查表;megaflow 缓存支持通配查找,减少了将报文上送到用户态查表的次数,但是由于基于 TSS 算法实现,由多个哈希桶组成,查找的时间复杂度为 O(n/2)(n 为 哈希桶的个数)。

为此,OVS 的改进方式是,同时保留了 microflow 和 megaflow 缓存,并将 microflow 作为一级缓存,megaflow 作为二级缓存。只不过现在的 microflow 的缓存条目不再是原来的查表结果,而是一个指向最近一次查找的 megaflow 表项(哈希桶)的索引值。这种流缓存的组织形式如图 1 所示:

image
图 1:OVS 流缓存组织形式

microflow 和 megaflow 缓存相结合的实现方式,保证了长连接流和短连接流的转发性能:对于长连接流,只需要两次查表(microflow + megaflow)就可以完成转发;对于短连接流,只需要在内核中多查几次哈希表(megaflow)就可以完成转发,而无需上送到用户态查表。

下图是三个流缓存组织形式的查表开销对比:

image

表 1:流缓存的查表开销

3、数据结构

3.1、mask_cache_entry 结构体

我们首先需要关注的是定义在 datapath/flow_table.h 文件中的 mask_cache_entry 结构体:

struct mask_cache_entry {
    u32 skb_hash;       // 数据报文 SKB 的 hash 值
    u32 mask_index;     // 最近一次匹配到的、掩码数组(struct mask_array)的索引值
};

mask_cache_entry 结构体缓存了 hash 值为 skb_hash 的数据报文最近一次所匹配的掩码数组的索引值,即 mask_indexmask_cache_entry 结构体所对应的就是 microflow 缓存。而这里提到的 掩码数组 是什么呢?请见下节讲解。

3.2、mask_array 结构体

定义在 datapath/flow_table.h 文件中的 mask_array 结构体,就是上节提到的掩码数组:

struct mask_array {
    struct rcu_head rcu;
    int count, max;                         // 当前已存储的掩码的数目、最大可存储的掩码的数目
    struct sw_flow_mask __rcu *masks[];     // 掩码数组
};

首先可以看到 mask_array 结构体使用了 Linux RCU(Read-Copy Update) 机制进行同步,由于本文主要讲解 OVS 的流缓存设计,因此对 RCU 不做赘述。

mask_array 结构体维护的是 sw_flow_mask 结构体的数组,countmax 分别表示该数组当前已存储的元素数目和最大可存储的元素数目。

sw_flow_mask 结构体定义在 datapath/flow.h 文件中,用于描述一个掩码,主要维护了匹配关键字(sw_flow_key)以及匹配关键字的有效范围(sw_flow_key_range):

struct sw_flow_mask {
    int ref_count;                      // 引用计数
    struct rcu_head rcu;                
    struct sw_flow_key_range range;     // 匹配关键字的有效范围
    struct sw_flow_key key;             // 匹配关键字
};

sw_flow_key 结构体定义在 datapath/flow.h 文件,用于描述一个匹配关键字,即从数据报文提取出来的报文特征;sw_flow_key_range 结构体定义在 datapath/flow.h 文件,用于描述匹配关键字的最小偏移和最大偏移。

3.3、table_instance 结构体

table_instance 结构体定义在 datapath/flow_table.h 文件:

struct table_instance {
    struct hlist_head *buckets;     // 哈希表,每个桶都是通过连接法来组织多个 flow
    unsigned int n_buckets;         // 哈希桶的数目
    struct rcu_head rcu;
    int node_ver;
    u32 hash_seed;
    bool keep_flows;
};

table_instance 结构体是 megaflow 缓存的实现,描述了一个流表实例,该流表通过单个哈希表的形式来组织所有 flow,哈希表的 key 是通过掩码 sw_flow_mask 与数据报文的匹配关键字 sw_flow_key 计算而得,同一个 key 下可能会有多个 flow,OVS 使用链表来解决这个哈希冲突的问题。buckets 表示哈希表的第一个哈希桶,n_buckets 表示哈希桶的数目。

OVS 是如何通过哈希表来组织 flow 的呢?我们还需要看看描述 flow 的数据结构,即定义在 datapath/flow_table.h 文件的 sw_flow 结构体:

struct sw_flow {
    struct rcu_head rcu;
    // 哈希桶链表
    struct {
        struct hlist_node node[2];
        u32 hash;
    } flow_table, ufid_table;
    int stats_last_writer;
    struct sw_flow_key key;                         // 该 flow 所对应的匹配关键字
    struct sw_flow_id id;                           // flow id
    struct cpumask cpu_used_mask;
    struct sw_flow_mask *mask;
    struct sw_flow_actions __rcu *sf_acts;          // flow 所对应的 action
    struct sw_flow_stats __rcu *stats[]; 
};

可见,sw_flow 结构体定义了类型为 struct hlist_node 的成员变量(flow_tableufid_table),而从上文可知,table_instance 结构体定义了类型为 struct hlist_head 的成员变量(buckets),这两个结构体均是 Linux 内核基础数据结构,分别用于定义哈希表中的链表头和链表节点,这里不做赘述。

3.4、flow_table 结构体

flow_table 结构体定义在 datapath/flow_table.h 文件:

struct flow_table {
    struct table_instance __rcu *ti;                // 用匹配关键字(struct sw_flow_key)组织的流表实例
    struct table_instance __rcu *ufid_ti;           // 用 ufid(unique flow identifier)组织的流表实例
    struct mask_cache_entry __percpu *mask_cache;   // 掩码索引值缓存项的数组,大小固定,为 256(MC_HASH_ENTRIES)
    struct mask_array __rcu *mask_array;            // 掩码的数组
    unsigned long last_rehash;
    unsigned int count;                             // 流表实例 ti 中存储的流表项数目
    unsigned int ufid_count;                        // 流表实例 ufid_ti 中存储的流表项数目
};

每个 OVS datapath 都会有专属的 flow_table 结构体,该结构体用于描述流表组织结构,从上面的代码块可以看出,flow_table 结构体维护了:

  • 两个 table_instance 流表实例,分别是使用匹配关键字组织的 ti 和使用 ufid 组织的 ufid_ti
  • 掩码索引值缓存项的数组 mask_cache,数组大小为 256(在初始化时定义);
  • 掩码数组 mask_array
  • 流表实例 ti 中存储的流表项数目 count
  • 流表实例 ufid_ti 中存储的流表项数目 ufid_count

3.5、小结

讲解完了这些 OVS 用于实现流缓存的基础数据结构,我们小结如下:

  1. mask_cache_entry 结构体是 microflow 缓存的实现,缓存了数据报文 SKB 的 hash 值与掩码数组索引值的对应关系,可以通过 SKB hash 值快速定位到对应的掩码数组元素;
  2. mask_array 结构体是掩码数组的实现,存储了 sw_flow_mask 结构体,通过数据报文的匹配关键字(sw_flow_key 结构体)与 sw_flow_mask 进行掩码计算得到 hash 值,可以快速定位到哈希表的桶;
  3. table_instance 结构体是 megaflow 缓存的实现,通过哈希表来组织各个 flow,同一个哈希桶内存在多个 flow,因此使用链表来解决冲突问题;通过第 2 步的掩码计算定位到某个哈希桶后,需要遍历所有的链表节点,比较每个 flow。

实现流缓存的数据结构的关系如图 2 所示:

image

图2:OVS 流缓存的数据结构

4、总结

本文讲解了 Open vSwitch 内核模块流缓存的三个阶段,分别是 microflow 缓存、megaflow 缓存以及如今的 microflow + megaflow 缓存,同时讲解了如今 OVS 实现流缓存的数据结构。

参考资料

2 comments:

    1. Thanks for your comment! Not yet. I’m still working hard, will become really good at network virtualization.

NANOKOK进行回复 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注