資訊專欄INFORMATION COLUMN
摘要：目前版本的采用的是第三種查詢方式，也就是結(jié)合和，其中作為一級，作為二級，此時中存放的不再是多級流表返回的結(jié)果，而是上一次在中命中的索引。
背景
在ovs交換機(jī)中，報文的處理流程可以劃分為一下三個步驟：協(xié)議解析，表項查找和動作執(zhí)行，其中最耗時的步驟在于表項查找，往往一個流表中有數(shù)目巨大的表項，如何根據(jù)數(shù)據(jù)報文的信息快速的查找到對應(yīng)的流表項是ovs交換機(jī)的一個重要的功能。
在openflow協(xié)議中，支持多級流表的形式，可以類比于將一個復(fù)雜的功能進(jìn)行打散，分解成過個小的功能，實現(xiàn)一個流水線的功能，具體見下圖：
上圖中可以看到，一個數(shù)據(jù)報文進(jìn)入后，會經(jīng)過多個流表，每個流表負(fù)責(zé)特定的功能，比如上圖中table 1中的流表項只會與數(shù)據(jù)報文中L2層的信息進(jìn)行匹配，多個流表的處理使得整個數(shù)據(jù)報文的查詢形成一種流水線的處理方式。
ovs流cache設(shè)計首先需要明確的是，ovs中的多級流表存放在用戶空間，內(nèi)核態(tài)存放的是流表的緩存，數(shù)據(jù)報文進(jìn)入ovs的時候，首先會查詢內(nèi)核態(tài)的緩存信息，如果命中則直接執(zhí)行相應(yīng)的動作，否則通過netlink的方式發(fā)送到用戶空間，用戶空間查找多級流表，如果用戶態(tài)命中則將對應(yīng)的信息丟給內(nèi)核態(tài)進(jìn)行緩存，否則查詢不到，用戶態(tài)還要繼續(xù)將報文的信息丟給控制器，由控制器下發(fā)對應(yīng)的規(guī)則，有關(guān)ovs和控制器之間的關(guān)系可以參見我的上一個博客。
ovs中關(guān)于流表的查詢經(jīng)歷了三個過程：
microflow cachemicroflow cache的思想十分簡單，具體見下圖：
多級流表的查詢過程中，會將報文與每個流表的每個流表項進(jìn)行匹配，這個過程中耗費(fèi)的時間是很大的，microflow cache的想法就是將多級流表查詢之后的結(jié)果按照一定的表項格式直接緩存到內(nèi)核態(tài)中，然后下次同樣的數(shù)據(jù)報文到達(dá)時，直接通過hash的方法在內(nèi)核態(tài)中命中，第二次的時間復(fù)雜度為$O(1)$，
microflow cache的缺點也很明顯：
實際存在很多short-lived類型的流量，導(dǎo)致命中率低
由于Mircroflow Cache 基于Hash的精確匹配查表，數(shù)據(jù)頭中微小的改動都會導(dǎo)致無法命中cache（如TTL）
Megaflow Cache雖然基于microflow cache的流表查詢方式，能讓數(shù)據(jù)報文第二次命中的時間復(fù)雜度達(dá)到$O(1)$，但是其真正的性能瓶頸在于用戶空間的查詢，如何減少數(shù)據(jù)報文進(jìn)入用戶態(tài)，是一個很重要的問題。
為了解決精確匹配的問題，減少數(shù)據(jù)報文進(jìn)入用戶態(tài)，ovs采用了megaflow cache代替了microflow cache的匹配方式，megaflow cache是一種基于TTS（元組空間搜索算法）的實現(xiàn)方式，采用了模糊匹配取代microflow cache的精確匹配，通過增加在內(nèi)核態(tài)中查詢的時間（從1次hash查找到k次，仍然是常數(shù)時間內(nèi)，跟TTS算法中表的數(shù)量有關(guān)），減少數(shù)據(jù)報文進(jìn)入用戶態(tài)的次數(shù)，具體會在TTS算法中解釋。
一種樸素的megaflow cache實現(xiàn)方式就是，將所有多級流表的級聯(lián)結(jié)果存放在內(nèi)核態(tài)中，如下圖：
內(nèi)核態(tài)中存放著一張所有流表級聯(lián)之后的大表，顯而易見，這種做法簡單粗暴，但是內(nèi)存的開銷也是巨大的。
一種好的做法是，采用’Lazy‘的方式，如下圖所示，數(shù)據(jù)報文首先通過模糊匹配的方式檢索內(nèi)核中的表，如果所有的表都無法命中，則查詢用戶態(tài)，然后將用戶態(tài)的查詢出的所有表項合并成一條表項，再插入到內(nèi)核態(tài)的表中。
需要注意的是，上圖中megaflow cache是一張表，在實際的ovs實現(xiàn)中，因為采用了TTS，所以megaflow cache是多張表形成的鏈表。
microflow cache+Megaflow Cache目前版本的ovs采用的是第三種查詢方式，也就是結(jié)合microflow cache和Megaflow Cache，其中microflow cache作為一級cache，Megaflow Cache作為二級cache，此時microflow cache中存放的不再是多級流表返回的結(jié)果，而是上一次在Megaflow Cache中命中的索引。
數(shù)據(jù)報文到達(dá)時，首先通過對報文信息hash，查詢microflow cache中是否存放著對應(yīng)的hash值，如果存在則查詢對應(yīng)hash值所指向的索引，這個索引用來定位對應(yīng)的Megaflow鏈表中的某一個元素表，然后再在這個元素表中進(jìn)行查找。
整體的解釋起來可能有點拗口，本人也是第一次寫博客，對ovs了解的也不夠深入，其中涉及到很多細(xì)節(jié)也不是很清楚，希望通過分享的形式同大家交流。
參考資料
[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)載請注明出處：https://segmentfault.com/a/11...
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/25238.html
摘要：需要修改數(shù)據(jù)包的二層源目地址以及三層包頭的因為路由是逐跳轉(zhuǎn)發(fā)的，每一跳都需要做這些工作，即使是現(xiàn)在通過流表轉(zhuǎn)發(fā)，中間的轉(zhuǎn)發(fā)器直接轉(zhuǎn)發(fā)報文，到達(dá)倒數(shù)第一跳的時候還是需要把數(shù)據(jù)包的目的地址修改為接受端的地址。 前言 熟悉這款設(shè)備的同學(xué)，應(yīng)該也快到不惑之年了吧！這應(yīng)該是Cisco最古老的路由器了。上個世紀(jì)80年代至今，路由交換技術(shù)不斷發(fā)展，但是在這波瀾壯闊的變化之中，總有一些東西在嘈雜的機(jī)房...
摘要：需要修改數(shù)據(jù)包的二層源目地址以及三層包頭的因為路由是逐跳轉(zhuǎn)發(fā)的，每一跳都需要做這些工作，即使是現(xiàn)在通過流表轉(zhuǎn)發(fā)，中間的轉(zhuǎn)發(fā)器直接轉(zhuǎn)發(fā)報文，到達(dá)倒數(shù)第一跳的時候還是需要把數(shù)據(jù)包的目的地址修改為接受端的地址。 前言 熟悉這款設(shè)備的同學(xué)，應(yīng)該也快到不惑之年了吧！這應(yīng)該是Cisco最古老的路由器了。上個世紀(jì)80年代至今，路由交換技術(shù)不斷發(fā)展，但是在這波瀾壯闊的變化之中，總有一些東西在嘈雜的機(jī)房...
摘要：需要修改數(shù)據(jù)包的二層源目地址以及三層包頭的因為路由是逐跳轉(zhuǎn)發(fā)的，每一跳都需要做這些工作，即使是現(xiàn)在通過流表轉(zhuǎn)發(fā)，中間的轉(zhuǎn)發(fā)器直接轉(zhuǎn)發(fā)報文，到達(dá)倒數(shù)第一跳的時候還是需要把數(shù)據(jù)包的目的地址修改為接受端的地址。 前言 熟悉這款設(shè)備的同學(xué)，應(yīng)該也快到不惑之年了吧！這應(yīng)該是Cisco最古老的路由器了。上個世紀(jì)80年代至今，路由交換技術(shù)不斷發(fā)展，但是在這波瀾壯闊的變化之中，總有一些東西在嘈雜的機(jī)房...
閱讀 2096·2021-11-24 10:34
閱讀 3082·2021-11-22 11:58
閱讀 3732·2021-09-28 09:35
閱讀 1743·2019-08-30 15:53
閱讀 2794·2019-08-30 14:11
閱讀 1569·2019-08-29 17:31
閱讀 560·2019-08-26 13:53
閱讀 2155·2019-08-26 13:45
