摘要：目前版本的采用的是第三種查詢(xún)方式，也就是結(jié)合和，其中作為一級(jí)，作為二級(jí)，此時(shí)中存放的不再是多級(jí)流表返回的結(jié)果，而是上一次在中命中的索引。

在ovs交換機(jī)中，報(bào)文的處理流程可以劃分為一下三個(gè)步驟：協(xié)議解析，表項(xiàng)查找和動(dòng)作執(zhí)行，其中最耗時(shí)的步驟在于表項(xiàng)查找，往往一個(gè)流表中有數(shù)目巨大的表項(xiàng)，如何根據(jù)數(shù)據(jù)報(bào)文的信息快速的查找到對(duì)應(yīng)的流表項(xiàng)是ovs交換機(jī)的一個(gè)重要的功能。

在openflow協(xié)議中，支持多級(jí)流表的形式，可以類(lèi)比于將一個(gè)復(fù)雜的功能進(jìn)行打散，分解成過(guò)個(gè)小的功能，實(shí)現(xiàn)一個(gè)流水線(xiàn)的功能，具體見(jiàn)下圖：

上圖中可以看到，一個(gè)數(shù)據(jù)報(bào)文進(jìn)入后，會(huì)經(jīng)過(guò)多個(gè)流表，每個(gè)流表負(fù)責(zé)特定的功能，比如上圖中table 1中的流表項(xiàng)只會(huì)與數(shù)據(jù)報(bào)文中L2層的信息進(jìn)行匹配，多個(gè)流表的處理使得整個(gè)數(shù)據(jù)報(bào)文的查詢(xún)形成一種流水線(xiàn)的處理方式。

首先需要明確的是，ovs中的多級(jí)流表存放在用戶(hù)空間，內(nèi)核態(tài)存放的是流表的緩存，數(shù)據(jù)報(bào)文進(jìn)入ovs的時(shí)候，首先會(huì)查詢(xún)內(nèi)核態(tài)的緩存信息，如果命中則直接執(zhí)行相應(yīng)的動(dòng)作，否則通過(guò)netlink的方式發(fā)送到用戶(hù)空間，用戶(hù)空間查找多級(jí)流表，如果用戶(hù)態(tài)命中則將對(duì)應(yīng)的信息丟給內(nèi)核態(tài)進(jìn)行緩存，否則查詢(xún)不到，用戶(hù)態(tài)還要繼續(xù)將報(bào)文的信息丟給控制器，由控制器下發(fā)對(duì)應(yīng)的規(guī)則，有關(guān)ovs和控制器之間的關(guān)系可以參見(jiàn)我的上一個(gè)博客。

ovs中關(guān)于流表的查詢(xún)經(jīng)歷了三個(gè)過(guò)程：

microflow cache的思想十分簡(jiǎn)單，具體見(jiàn)下圖：

多級(jí)流表的查詢(xún)過(guò)程中，會(huì)將報(bào)文與每個(gè)流表的每個(gè)流表項(xiàng)進(jìn)行匹配，這個(gè)過(guò)程中耗費(fèi)的時(shí)間是很大的，microflow cache的想法就是將多級(jí)流表查詢(xún)之后的結(jié)果按照一定的表項(xiàng)格式直接緩存到內(nèi)核態(tài)中，然后下次同樣的數(shù)據(jù)報(bào)文到達(dá)時(shí)，直接通過(guò)hash的方法在內(nèi)核態(tài)中命中，第二次的時(shí)間復(fù)雜度為$O(1)$，

microflow cache的缺點(diǎn)也很明顯：

實(shí)際存在很多short-lived類(lèi)型的流量，導(dǎo)致命中率低

由于Mircroflow Cache 基于Hash的精確匹配查表，數(shù)據(jù)頭中微小的改動(dòng)都會(huì)導(dǎo)致無(wú)法命中cache（如TTL）

雖然基于microflow cache的流表查詢(xún)方式，能讓數(shù)據(jù)報(bào)文第二次命中的時(shí)間復(fù)雜度達(dá)到$O(1)$，但是其真正的性能瓶頸在于用戶(hù)空間的查詢(xún)，如何減少數(shù)據(jù)報(bào)文進(jìn)入用戶(hù)態(tài)，是一個(gè)很重要的問(wèn)題。

為了解決精確匹配的問(wèn)題，減少數(shù)據(jù)報(bào)文進(jìn)入用戶(hù)態(tài)，ovs采用了megaflow cache代替了microflow cache的匹配方式，megaflow cache是一種基于TTS（元組空間搜索算法）的實(shí)現(xiàn)方式，采用了模糊匹配取代microflow cache的精確匹配，通過(guò)增加在內(nèi)核態(tài)中查詢(xún)的時(shí)間（從1次hash查找到k次，仍然是常數(shù)時(shí)間內(nèi)，跟TTS算法中表的數(shù)量有關(guān)），減少數(shù)據(jù)報(bào)文進(jìn)入用戶(hù)態(tài)的次數(shù)，具體會(huì)在TTS算法中解釋。

一種樸素的megaflow cache實(shí)現(xiàn)方式就是，將所有多級(jí)流表的級(jí)聯(lián)結(jié)果存放在內(nèi)核態(tài)中，如下圖：

內(nèi)核態(tài)中存放著一張所有流表級(jí)聯(lián)之后的大表，顯而易見(jiàn)，這種做法簡(jiǎn)單粗暴，但是內(nèi)存的開(kāi)銷(xiāo)也是巨大的。

一種好的做法是，采用’Lazy‘的方式，如下圖所示，數(shù)據(jù)報(bào)文首先通過(guò)模糊匹配的方式檢索內(nèi)核中的表，如果所有的表都無(wú)法命中，則查詢(xún)用戶(hù)態(tài)，然后將用戶(hù)態(tài)的查詢(xún)出的所有表項(xiàng)合并成一條表項(xiàng)，再插入到內(nèi)核態(tài)的表中。

需要注意的是，上圖中megaflow cache是一張表，在實(shí)際的ovs實(shí)現(xiàn)中，因?yàn)椴捎昧薚TS，所以megaflow cache是多張表形成的鏈表。

目前版本的ovs采用的是第三種查詢(xún)方式，也就是結(jié)合microflow cache和Megaflow Cache，其中microflow cache作為一級(jí)cache，Megaflow Cache作為二級(jí)cache，此時(shí)microflow cache中存放的不再是多級(jí)流表返回的結(jié)果，而是上一次在Megaflow Cache中命中的索引。

數(shù)據(jù)報(bào)文到達(dá)時(shí)，首先通過(guò)對(duì)報(bào)文信息hash，查詢(xún)microflow cache中是否存放著對(duì)應(yīng)的hash值，如果存在則查詢(xún)對(duì)應(yīng)hash值所指向的索引，這個(gè)索引用來(lái)定位對(duì)應(yīng)的Megaflow鏈表中的某一個(gè)元素表，然后再在這個(gè)元素表中進(jìn)行查找。

整體的解釋起來(lái)可能有點(diǎn)拗口，本人也是第一次寫(xiě)博客，對(duì)ovs了解的也不夠深入，其中涉及到很多細(xì)節(jié)也不是很清楚，希望通過(guò)分享的形式同大家交流。

參考資料
[Pfaff B, Pettit J, Koponen T, et al. The Design and Implementation of Open vSwitch[C]//NSDI. 2015, 15: 117-130.](https://www.usenix.org/system...
Open vSwitch流表查找分析
The Design and Implementation of Open vSwitch 作者演講ppt

作者：yearsj
轉(zhuǎn)載請(qǐng)注明出處：https://segmentfault.com/a/11...