基于MapReduce分級調(diào)度的試題庫組卷算法研究

苑立娟

摘 要：MapReduce調(diào)度算法包括默認(rèn)的FIFO調(diào)度策略、公平調(diào)度策略、計算能力調(diào)度策略，在試題庫組卷過程中采用的是分階段的任務(wù)方式來實現(xiàn)的，根據(jù)任務(wù)優(yōu)化MapReduce算法是本文要解決的問題。提出分級調(diào)度算法，把現(xiàn)有的調(diào)度策略在分級任務(wù)基礎(chǔ)之上分為多級模式，不斷趨近最終結(jié)果，根據(jù)任務(wù)的不同階段進(jìn)行分級分階調(diào)度符合不同階段不同需求。實驗表明，多階段調(diào)度算法能夠滿足試題庫組卷任務(wù)的檢索需求。

關(guān)鍵詞：云計算；MapReduce；分級調(diào)度；組卷

隨著云計算不斷的發(fā)展，各行各業(yè)都紛紛應(yīng)用這種高效、安全和便捷的大數(shù)據(jù)、分布式服務(wù)。高等院校也都紛紛涉足云計算，分布式存儲、MapReduce算法以及基于云計算的各種服務(wù)系統(tǒng)等都在高校研究中有所體現(xiàn)。高等院校考試系統(tǒng)的組卷過程是一個復(fù)雜的檢索過程，而這一過程正是云計算的強(qiáng)項，因此組卷算法如何利用云計算中的MapReduce編程模型來實現(xiàn)是本文研究的主要方向。MapReduce是Google公司開發(fā)的Hadoop框架中進(jìn)行分布式數(shù)據(jù)處理的一種編程模型。在組卷過程中主要關(guān)注兩個問題：一個是組卷參數(shù)分級問題、一個是組卷分級任務(wù)中的各個級別的檢索問題。MapReduce的任務(wù)調(diào)度過程是將一個任務(wù)分為多個子任務(wù)進(jìn)行并行處理，這個過程正好與組卷的任務(wù)有相同之處。MapReduce的調(diào)度分為：先進(jìn)先出、公平調(diào)度和計算能力評估調(diào)度。這幾個調(diào)度算法對于特定的組卷任務(wù)來說并不是最優(yōu)化的。試題庫組卷的過程可以分為多級多階段，將復(fù)雜的任務(wù)分層剝離。這樣化繁為簡，提高組卷的命中率和效率。本體提出了分級調(diào)度算法，該算法要解決的重要問題是：

首先，任務(wù)分級劃界。MapReduce會將一個任務(wù)分解為多個子任務(wù)，而試題庫組卷過程也是一個分級不斷靠近需求的過程，本文第一層級任務(wù)確定題型和分?jǐn)?shù)，第二層級任務(wù)根據(jù)題型和分?jǐn)?shù)確定試題個數(shù)，第三層級任務(wù)對難度系數(shù)進(jìn)行優(yōu)化，第四層級任務(wù)迭代微調(diào)。其次，層級上下文銜接。一層級任務(wù)完成后，應(yīng)該把結(jié)果及其參數(shù)傳遞給二層級，依次類推。

結(jié)合MapReduce的調(diào)度過程，本文提出了分級調(diào)度的概念，每級層調(diào)度選擇該層級的較為優(yōu)秀的調(diào)度方法。整個任務(wù)被分為多層有先后的子任務(wù)，每個任務(wù)為下層任務(wù)提供參數(shù)進(jìn)行參考，該層任務(wù)提交給適合執(zhí)行的對象來處理。

1 MapReduce任務(wù)調(diào)度過程

MapReduce是Hadoop框架的一種編程模式，是進(jìn)行分布式數(shù)據(jù)處理的。它的關(guān)鍵在于Map（地圖）和Reduce（化簡）。第一階段數(shù)據(jù)檢索過程，Map獲取系統(tǒng)或數(shù)據(jù)庫中的子數(shù)據(jù)，根據(jù)用戶設(shè)定好的Map函數(shù)將數(shù)據(jù)分為多個Key/Value對的子數(shù)據(jù)，排序后存儲與在客戶端。在化簡階段，Reduce任務(wù)讀取相應(yīng)的子數(shù)據(jù)，這樣任務(wù)被分為多個子任務(wù)并行處理，提高數(shù)據(jù)處理的效率。整個過程處于主節(jié)點的控制之下，JobTracker負(fù)責(zé)對眾多節(jié)點進(jìn)行掌控。

2 多級分層調(diào)度思想

試題庫組卷過程在本文中可分為四層到多層，基礎(chǔ)為四層，如果得不到優(yōu)化的結(jié)果，需要在最后一層進(jìn)行不斷迭代優(yōu)化來滿足用戶需求。四層任務(wù)從上到下依次是：題型確定層，該層需要很短的時間，時間可以忽略不計，只要獲取用戶設(shè)定的題型即可；分?jǐn)?shù)確定層，這一層同上，也是直接獲得；而題型確定層和分?jǐn)?shù)確定層之間的銜接問題應(yīng)該要處理好，思路在于M為一個完整的一次組卷過程，這個過程定義如下所示：M=f1（f2（T，F(xiàn)），…，fn），M表示一個完整組卷任務(wù)，f1是任務(wù)分解函數(shù)，f2表示一層和二層銜接函數(shù)，fn表示N-1層和N層的銜接函數(shù)。這樣首位呼應(yīng)的銜接方式，確保了能在一下層級中獲得上一層級的結(jié)果參數(shù)。緊接著就是難度系數(shù)確定層，獲得試題個數(shù)和分?jǐn)?shù)之后，根據(jù)個數(shù)和分?jǐn)?shù)的配比比例來進(jìn)行難度系統(tǒng)比例分配，這個分配過程要求用戶提供配比比例，例如1：2：3等，如果由上層函數(shù)傳遞過來的分?jǐn)?shù)為20分，很容易獲得難度個數(shù)比例，比例依次就是3：6：9+2，四舍五入最后多余的2道題則自動分配給難度最高的配比。當(dāng)然，根據(jù)用戶的設(shè)定的難度要求，這個2可以分配給難度系數(shù)為1的部分，也可以分配給難度系數(shù)為2的部分。這樣任務(wù)就在第三層有了詳細(xì)的處理過程，分配給調(diào)度器檢索任務(wù)變的更加簡單而有效了。當(dāng)三層級處理完畢后可以將結(jié)果參數(shù)傳遞給四層級，進(jìn)行題庫覆蓋任務(wù)的調(diào)度處理，那么這個過程同樣也被細(xì)化了。

3 算法實現(xiàn)的流程

定義M函數(shù)，M=（T，F(xiàn)，N，C）；T定義為題型，F(xiàn)為分?jǐn)?shù)，N為難度系數(shù)，C其他用戶要求參數(shù)類型。為任務(wù)1定義函數(shù)f1（T，F(xiàn)），通過MapReduce處理之后將結(jié)果x1賦值給函數(shù)f2，函數(shù)f2的定義為f2（N，x1），再次交給MapReduce處理將結(jié)果x2賦值給函數(shù)f3，f3定義為f3（x2，C）。將每個任務(wù)分別作為每個Mapper的輸入，每個Mapper處理一個任務(wù)的數(shù)據(jù)，按需求執(zhí)行運算（因為這里對數(shù)值和題目的比例不一樣，調(diào)用的方法不一樣）并產(chǎn)生結(jié)果，Reducer把多個Mapper的結(jié)果組合即完成一次組卷。Master主控程序?qū)⑷蝿?wù)分配給Worker。Map任務(wù)負(fù)責(zé)檢索，Reduce任務(wù)負(fù)責(zé)整合。Map任務(wù)根據(jù)條件進(jìn)行數(shù)據(jù)檢索，獲得符合要求的題目的鍵值數(shù)據(jù)，將其傳遞給用戶定義的Reduce（）函數(shù)。Map產(chǎn)生的中間結(jié)果對緩沖到內(nèi)存。Map函數(shù)緩沖的中間結(jié)果被定時寫到本地磁盤，這些數(shù)據(jù)根據(jù)需求利用分區(qū)函數(shù)被分別放置。這些中間結(jié)果即試題的位置信息發(fā)送給Master，Master負(fù)責(zé)把該位置信息傳遞給Reduce（）的Worker。通知傳遞后，Worker調(diào)用Map讀取本地機(jī)器上試題信息，讀取后標(biāo)記這些數(shù)據(jù)為被選用數(shù)據(jù)，即標(biāo)記該題被選用，選用次數(shù)加1。Reduce函數(shù)根據(jù)中間記過的key值進(jìn)行遍歷，把符合要求的數(shù)據(jù)集合后傳遞給Reduce，Reduce將結(jié)果存放在Master掌管的一個輸出文件中。

用戶程序綜合所有數(shù)據(jù)，形成最終結(jié)果。

4 測試與分析

通過實驗測試，本文介紹的分層級調(diào)度算法對于1500道題庫4種題型分?jǐn)?shù)為10，20，30，40難度系數(shù)比例為1：1：2，最終獲得結(jié)果耗時2.35秒，對于3000道題庫4種題型分?jǐn)?shù)和難度系數(shù)比例同上的要求，最終獲得結(jié)果耗時4.88秒，對于9000道題庫4中題型分?jǐn)?shù)和難度系數(shù)比例同上的要求，最終獲得結(jié)果耗時7.12秒?？梢垣@得效果是比較滿意的。隨著題庫數(shù)量的不斷增加時間耗時不斷的增加，但是其結(jié)果是趨于越來越少的。

5 結(jié)束語

本文提出的分層級的試題庫組卷算法基本滿足了用戶的要求，通過對任務(wù)的特定的層級進(jìn)行分析，針對不同層級的不同要求選取適應(yīng)的調(diào)度方式來滿足要求，同時能夠保證任務(wù)的并行性和時間的高效性。

[參考文獻(xiàn)]

[1]劉吉，陳香蘭.一種MapReduce實時調(diào)度算法設(shè)計及實現(xiàn).計算機(jī)系統(tǒng)應(yīng)用，2013，22（8）：116-123.

[2]白東玲，郭紹永.改進(jìn)的遺傳算法在智能組卷系統(tǒng)中的應(yīng)用研究.計算機(jī)與現(xiàn)代化，2013，（3）：25-28.

[3]李鋼.基于出題系統(tǒng)的隨機(jī)算法.軟件，2013，34（2）：84-85.

[4]王凱，吳泉源.一種多用戶MapReduce集群的作業(yè)調(diào)度算法的設(shè)計與實現(xiàn).計算機(jī)與現(xiàn)代化，2010，（10）：23-28.