一種多路徑環境下的智能選路算法設計與實現

胡耀義

（中國石油集團工程設計有限責任公司 西南分公司，成都 610041）

一種多路徑環境下的智能選路算法設計與實現

胡耀義

（中國石油集團工程設計有限責任公司 西南分公司，成都 610041）

為解決目前一些多路徑軟件的選路算法需手動設置所帶來的盲目性問題，提出并設計了一種智能選擇選路算法的策略，進而實現了一種智能選路算法。該算法主要通過系統獨立的線程自動監控主機與存儲系統中各條物理路徑的I/O情況，動態地選擇一種較為恰當的選路算法進行最優路徑的選擇。該算法在多路徑環境下利用微軟MPIO框架實現，實驗表明，該算法具有較好的I/O傳輸性能。

網絡存儲；多路徑；智能選路算法；I/O；MPIO

隨著網絡存儲技術的不斷深入發展，多路徑技術已經成為整個網絡存儲系統中不可或缺的核心技術之一。這是因為主機多路徑在避免單路徑故障與提升I/O傳輸速率等方面具有獨特的優勢，而一種高效、可靠、穩定的選路算法不僅是一款多路徑軟件是否優秀的重要標志，也是主機與存儲系統之間I/O能夠高效傳輸的前提和保證。目前，市場上的一些多路徑軟件一般都通過手動方式來設置不同的選路算法，具有較高的盲目性，成為制約主機多路徑數據高效傳輸的主要因素之一。本文正是為解決上述弊端，提出并設計了一種多路徑環境下的智能選路算法，并在微軟MPIO[1]框架上進行具體實現與驗證分析。

1 智能選路算法設計

主機與存儲系統之間所有物理路徑上的I/O數據流處于一種相對均衡狀態，是多路徑選路算法需要解決的核心問題，而智能選路算法正是通過自動監控主機中的I/O數據流，并動態地分派當前的I/O到數據傳輸壓力相對較小的物理路徑上[2]來提高I/O傳輸效率的。

1.1 設計思想

在多路徑環境下，物理路徑上所對應的I/O數據隊列一般可分為3種情況：（1）各條物理路徑上所對應的I/O隊列個數和字節大小情況相當，即總體數據相差不是很大；（2）某些物理路徑上所對應的I/O隊列個數較大，而另外一些則較少，形成數據傳輸壓力不均衡；（3）某些路徑上所對應的I/O隊列字節較大，而另外一些物理路徑的情況反之，也形成了數據傳輸壓力的失衡[3]。

對于第1種情況，由于I/O隊列的個數和字節大小都處于一種相對均衡狀態，因此適合于時間和空間復雜度相對較小的輪詢調度算法，即在每條路徑上輪詢下發I/O。對于第2種情況，其特點為I/O隊列的個數在某些路徑之間相差較大，因此可以利用最小I/O隊列深度調度算法來選擇I/O隊列個數相對較小的路徑進行當前I/O數據的傳輸。而對于第3種情況，其特點是I/O隊列字節大小在某些路徑之間相差較大，所以將當前的I/O插入到數據傳輸壓力相對較小的隊列上是上策，故而利用最小I/O任務量調度算法來打破I/O不均衡狀態。

各種情況下的選路算法確定后，對于智能選路算法來說，如何自動地監控各條物理路徑上的I/O數據流就成為需要解決的關鍵問題。對于此問題的解決，本文的智能選路算法策略是：

（1）在操作系統內核中創建一個獨立的線程，而該線程的核心功能就是在一段時間間隔內（如：60 s），在各條物理路徑上進行一次未完成I/O數據流的統計，進而分析并確定一種選路算法。（2）由該選路算法進行具體的最優路徑選擇。對于主機第1次安裝多路徑或者由于其它原因導致系統復位的情況，系統默認的選路算法為輪詢調度算法。需要說明的是，在相同情況下，根據時間和空間復雜度的不同，動態選擇選路算法的優先順序為輪詢調度算法、最小I/O隊列深度調度算法和最小I/O任務量調度算法。

1.2 方案設計

假設有N（0＜N≤32）條路徑，主機與陣列間的路徑記為Pi(0＜i≤N)，路徑Pi上的每一個 I/O的大小記為Dij，該路徑上未完成的I/O個數記為Mi（Mi ≥ 0），下面就不同的情況分別進行設計：

1.2.1 當前算法是輪詢調度算法

1.2.2 當前算法是最小I/O隊列深度調度算法

1.2.3 當前算法是最小I/O任務量調度算法

上述3 種情況不管是選擇哪種選路算法，其最根本的目標就是讓每條路徑上的I/O 個數和任務量處于一種相對均衡狀態，在避免單路徑故障的同時，提高每條物理路徑的整體利用率和數據吞吐量。

2 基于MPIO框架的智能選路算法實現

2.1 MPIO及其接口

微軟MPIO 是Windows NT 系列操作系統優秀的多路徑軟件開發框架，在安裝其開發工具包MPIO DDK 后，可以在dsm.h 開頭文件中看到DSM_INIT_ DATA 數據結構，該結構體定義了所有基于MPIO框架的主機多路徑接口函數。該框架的多路徑開發首先需要實例化該結構體，即有：DSM_INIT_DATA MPIO_DSM[4]。

有了上面的實例化之后，就可以在DriverEntry主函數中實現DsmInquireDriver、DsmLBGetPath及DsmInterpretErrorEx等接口，并將相應實現的接口函數指針指向MPIO_DSM實例化成員中。本文所設計的選路算法需要實現的接口為DsmLBGetPath，同時需要在系統中創建一個獨立的線程自動監控I/O數據流，并選擇一種恰當的選路算法，此時，DsmLBGetPath則會根據已經確立的選路算法進行最優路徑的選擇。

2.2 MPIO框架的智能選路算法實現

對于該算法在微軟MPIO框架下的實現可以通過兩個步驟來完成。

（1）利用庫函數PsCreate-SystemThread創建一個獨立線程，該線程的主要功能是根據當前的I/O數據流情況選擇最優選路算法，該函數原型為：

NTSTATUS PsCreateSystemThread（ OUT PHANDLE ThreadHandle,IN ULONG DesiredAccess,

IN POBJECT_ATTRIBUTES Attributes,

IN HANDLE ProcessHandle,OUT PCLIENT_ID ClientId,

IN PKSTART_ROUTINE Start_Routine,IN PVOID Context）;

（2）自動監控I/O數據流并選擇一種最優選路算法，選路算法重置的時間間隔設為60 s，具體功能可以通過Start_Routine例程來實現。該例程需要實現兩個子例程： Least_Number_Fun(PDSM_ Context_Node PDsm_Context_Node)和Least_Task_ Fun(PDSM_Context_Node PDsm_Context_Node)，其中，PDSM_Context_Node為MPIO框架DSM上下文結構體。第1個子例程用于判斷是否適合于最小I/ O隊列深度調度算法，第2個子例程用來判斷是否適合于最小I/O任務量調度算法，有了這兩個子例程就可以實現3種具體選路算法的選擇。之后，可以在DsmLBGetPath接口中實現路徑選擇這一功能，其接口原型為：

3 實驗結果與數據分析

利用Windows Server 2008進行FC（2 GHz）雙路徑組網，在陣列端給主機映射一個邏輯單元號（LUN，Logical Unit Number）[5]，利用IOMeter進行磁盤性能測試，設置IOMeter測試工具的I/O塊長為1 MB和32 kB雙線程進行大壓力讀寫（均為75%讀，25%寫）。同時，為了構造智能選路算法所需求的異常場景，可以在系統正常工作后，將其一條鏈路斷開，等待一段時間后，恢復斷開的鏈路，當該鏈路開始正常工作時獲取一次I/O數據，重復上述操作。另外，為了保證測試數據的準確性和公平性，輪詢調度算法、最小IO隊列深度調度算法和最小IO任務量調度算法也采取同樣的措施，并在各種情況下分別測得其I/O性能數據，如表1所示。

在對上述4種方式的I/O性能統計中，輪詢調度算法的I/O數據總和為1 510.41 MB/s，平均值為188.80 MB/s；最小IO隊列深度調度算法的I/O數據總和為1 538.29 MB/s，平均值為192.29 MB/s；最小IO任務量調度算法的I/O數據總和為1 542 MB/s，平均值為192.75 MB/s；智能選擇算法的I/O數據總和為1 554.17 MB/s，平均值為194.27 MB/s。其中，智能選路算法的I/O平均值分別高出輪詢調度算法、最小IO隊列深度調度算法、最小IO任務量調度算法的比例為2.90%、1.03%、0.79%。

表1 不同算法I/O數據統計表（單位：MB/s）

圖1 I/O性能統計圖

從圖1的I/O性能統計圖可以看出，智能選擇算法的I/O統計數據曲線比較平滑穩定，沒有很大的波動。這也從另外一個方面說明，在引入智能選路算法后，每一條路徑上的I/O數據能夠處于一種相對均衡的狀態，沒有出現某一條路徑I/O過于空閑，而另外一條路徑壓力相對較大的情況。

4 結束語

本文提出并設計實現了一種多路徑環境下的智能選路算法，該算法通過自動地監控各條物理路徑上的I/O數據流來智能地選擇合適的選路算法。實驗結果表明，該智能選路算法具有較好的性能和I/O傳輸效率，消除了手動設置選路算法所帶來的盲目性問題，同時也消除了主機與存儲系統之間的單路徑故障問題。需要說明的是，盡管該智能選路算法是在微軟MPIO多路徑框架上進行了實現與驗證，但完全可以移植到Linux、Unix等其它操作系統上進行相應多路徑選路算法的應用。

[1]Microsoft Corporation.Microsoft Storage Technologies Multipath I/O [DB/OL].http://www.microsoft.com/windowsserversysterm/storage/technologies/mpio/default.mspx,2011-3-1.

[2]劉 明.存儲區域網絡冗余路徑[D].北京： 北京理工大學,2004.

[3]譚毓安,曹元大.冗余SCSI路徑驅動程序的設計與實現[J].北京理工大學學報， 2002， 22（5）： 604-607.

[4]Microsoft Corp.Windows Server High Availability with Microsoft MPIO [DB/OL].http://www.microsoft.com/MPIO,January 2009.

[5]Microsoft Corporation.Microsoft Multipath I/O Step-by-Step Guide [DB/OL].http://technet.microsoft.com/zh-cn/library/ ee619778(WS.10).aspx,2011-12-13.

[6]IS0/IEC 14776-454.Information technology SCSI Primary Command-4(SPC-4) [S].2009.

責任編輯 徐侃春

Intelligent routing algorithm in multi-path environment

HU Yaoyi
( CPE Southwest Company,Chengdu 610041,China)

This article proposed and designed an intelligent strategy to select path in order to solve the blindness problems caused by setting routing algorithm manually in some multi-path software,implemented an intelligent algorithm to select path.The algorithm could automatically monitor the I/O data streams of every path between host and storage system by an independent thread,and then dynamically select an appropriate routing algorithm to select an optimized route.The algorithm was implemented on the Microsoft MPIO framework in multi-path environment.The test results showed that this algorithm ran with a better I/O transfer performance.

network storage;multi-path;intelligent routing algorithm;I/O;MPIO

TP39

A

1005-8451（2016）10-0013-04

2016-01-28

胡耀義，工程師。