一種分布式Online Judge系統(tǒng)設計與實現(xiàn)

曾 金，彭 玲，毛志斌，張耀峰

（1.湖北經(jīng)濟學院 信息管理學院；2.武漢大學 信息管理學院，湖北 武漢 430072；3.湖北經(jīng)濟學院 中國改革試點探索與評估協(xié)同創(chuàng)新中心湖北分中心，湖北 武漢 430205）

0 引言

教育部針對新工科、新文科建設提出新的評估方法，要求高等教育的整個教學環(huán)節(jié)要以數(shù)字化和虛擬化教學為目的，從而驅(qū)動整個教學活動和成果評價的新要求［1］。同時，隨著時代和科技發(fā)展，個人計算機已得到全面普及。伴隨著高級語言的出現(xiàn)與流行，計算機編程逐漸成為高校計算機科學與技術(shù)、大數(shù)據(jù)、人工智能、物聯(lián)網(wǎng)等專業(yè)的核心課程，并且這些專業(yè)都離不開上機編程［2］。在計算機編程類課程中，數(shù)據(jù)結(jié)構(gòu)與算法課程必不可少，任何計算機程序都是基于數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)編寫而成。目前，大多數(shù)高校計算機專業(yè)中，課堂教學偏重于理論，在算法代碼實現(xiàn)上訓練不足，導致多數(shù)學生在平時上機課或期末卷面考試中能考出較好成績，但在算法復現(xiàn)及應用上極為困難。在傳統(tǒng)實驗課上，學生在課上完成算法代碼后，教師逐一閱讀代碼、運行驗證代碼、調(diào)試代碼頗為不便，卷面考試也很難檢驗學生實際編程能力。因此，設計在線評測系統(tǒng)平臺是學科交叉融合改革的新探索，可極大程度地解決上述問題。判題服務器可以自動完成所有學生代碼的運行評測，可極大減輕教師負擔，并提供數(shù)據(jù)反饋，讓教師更有針對性地開展教學。因此，在計算機、大數(shù)據(jù)及人工智能專業(yè)學生培養(yǎng)中，可供在線使用的編程答題系統(tǒng)必不可少。設計一款好的Online Judge 系統(tǒng)，不僅可以解決傳統(tǒng)評分過程中存在的不公平問題［3］，還可以解決教育部對教學成果評估的需求。互聯(lián)網(wǎng)企業(yè)招聘中，算法考核是求職者在面試中的重要考核因素。該系統(tǒng)可模擬企業(yè)對招聘者知識掌握程度進行分析，有針對性地加強學生、求職者和在職人員對數(shù)據(jù)結(jié)構(gòu)和算法的實踐應用，促使其迅速提升編程能力［4-5］。

1 相關(guān)研究

在線程序測評系統(tǒng)最早可追述到1960年，是計算機輔助教學系統(tǒng)中的一個分支［6］。隨著計算機技術(shù)的進步和互聯(lián)網(wǎng)技術(shù)的發(fā)展，該系統(tǒng)在功能和應用規(guī)模上均取得巨大進步。

目前，國內(nèi)外有許多在線代碼評測平臺，主要分為兩類。一類主要是面向高校自主搭建的Online Judge 系統(tǒng)，例如北京大學的POJ［7］、浙江大學的ZOJ［8］、哈爾濱工業(yè)大學的HITOJ［9］等。此類Online Judge 的優(yōu)點在于高校教師可自主發(fā)布各類考試、比賽，資源豐富、題庫優(yōu)質(zhì)、靈活性好，能夠針對特定算法基礎(chǔ)模塊對學生所學知識進行鞏固和測驗。另一類是專門面向社會的大型公眾Online Judge平臺，例如LeetCode、UVA、CodeVS 等國內(nèi)外大型Online Judge 平臺，其優(yōu)點在于目標性強、專門針對企業(yè)招聘考試、較多算法題目，因而比較適合經(jīng)驗豐富的編程者［10］。無論是面向高校類的Online Judge 系統(tǒng)，還是面向社會的大型公眾Online Judge 平臺，均存在以下問題：

（1）傳統(tǒng)Online Judge系統(tǒng)開發(fā)存在穩(wěn)定性及開發(fā)文檔維護性不足等問題［11］。隨著計算機的普及，大量軟件及應用數(shù)據(jù)產(chǎn)生，硬件發(fā)展速度跟不上軟件性能，由此產(chǎn)生非常嚴重的問題，即規(guī)模大、復雜性高、容錯能力差的軟件穩(wěn)定性差，沒有系統(tǒng)的開發(fā)文檔導致維護難度非常大，傳統(tǒng)語言開發(fā)已無法滿足當下需求，這也是軟件危機的起源。

（2）開發(fā)語言存在跨平臺及效率低的缺陷［12］。分布式Online Judge 系統(tǒng)實現(xiàn)需要開源跨平臺面向?qū)ο蟮木幊陶Z言，這種語言具有非常豐富的擴展性，擁有良好的社區(qū)環(huán)境，使開發(fā)者們愿意貢獻出自己的源代碼。在使用過程中，可以借助功能強大的自帶庫和社區(qū)豐富的第三方庫，以最快的速度實現(xiàn)開發(fā)者想要實現(xiàn)的功能。由于開發(fā)環(huán)境語言友好且簡潔、易讀，用來解決一些簡單重復的工作可極大提升工作效率。

（3）服務器穩(wěn)定性及安全性不足［13］。Online Judge 系統(tǒng)最核心的部分在于判題節(jié)點的規(guī)劃與實現(xiàn)，在服務器端評測用戶提交的代碼，會極大地影響后端服務器的穩(wěn)定性。雖然已經(jīng)采用分布式架構(gòu)完成Online Judge 系統(tǒng)，但學生提交的代碼受硬件環(huán)境限制，需采用容器技術(shù)作為Judge Node 節(jié)點的核心技術(shù)實現(xiàn)。容器可以打包應用及所需要的依賴，在任意版本的Linux 和Windows 平臺上完成部署，極大地提高了程序穩(wěn)定性。此外，容器技術(shù)實現(xiàn)的沙盒隔離，可以防止常見Online Judge 系統(tǒng)被攻擊，例如在c/cpp 語言中使用include 造成服務器密碼或數(shù)據(jù)庫密碼外泄，在評測機進行程序編譯時被攻擊代碼卡死造成服務宕機。因此，使用好容器不僅可以保護服務器端的安全隱私，也可以在Judge 節(jié)點宕機時重新自動拉取鏡像，不會造成服務器判題節(jié)點效率降低。

（4）個性可視化分析有待提高［14］。目前，大部分Online Judge 系統(tǒng)在判題功能上較為完善和強大，但在用戶個性可視化功能展示上有待進一步提高，如對用戶編程能力的評估、強項與弱項的具體評估指標、時序評估體系可視化展示等，不能深層次挖掘用戶編程能力不足的原因并提供相應的改進建議。

自主研發(fā)的分布式Online Judge 系統(tǒng)不僅可以為學生提供鞏固基本數(shù)據(jù)結(jié)構(gòu)知識和提升算法編程思維能力的平臺，供教師發(fā)布課堂作業(yè)、考試任務，并對學生進行測試，還可用于學院舉辦編程比賽、選拔優(yōu)秀學員從而代表學校參加各類學科競賽，如ACM（美國計算機協(xié)會）/ICPC（國際大學生程序設計競賽）、藍橋杯、百度之星等賽事［15-16］。

該Online Judge 系統(tǒng)的優(yōu)勢在于利用Python 語言和Django 的特性，將數(shù)據(jù)庫與管理員后端結(jié)合起來，具有較強的容錯能力和穩(wěn)定性，方便后期維護，且可以跨平臺安裝使用；該系統(tǒng)還可以隨時調(diào)用功能強大的第三方庫以支持和彌補系統(tǒng)開發(fā)過程中存在的不足和缺陷，以最快的速度實現(xiàn)開發(fā)者想要實現(xiàn)的所有功能。該系統(tǒng)的創(chuàng)新之處在于其具有強大的數(shù)據(jù)可視化功能和測評體系，可對用戶編程能力進行實時的可視化分析和評價，并總結(jié)用戶評測不足，從而幫助用戶提高編程能力。

2 分布式Online Judge系統(tǒng)方案

2.1 系統(tǒng)簡介與運行環(huán)境

Online Judge 是一個在線代碼評測系統(tǒng)，其基于預先設定好的測試用例，對用戶提交的代碼進行編譯測試，并在測試結(jié)束后將數(shù)據(jù)返回給前端頁面，給用戶以直觀的體驗。Online Judge 系統(tǒng)可以幫助用戶鞏固數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，提高算法能力及時間、空間決策能力，還可為用戶參加編程比賽或作業(yè)測試提供練習平臺［17］。

文本分布式Online Judge 系統(tǒng)的開發(fā)運行環(huán)境如表1所示，系統(tǒng)運行環(huán)境交互如圖1所示。

Table 1 Development and operation environment表1 開發(fā)運行環(huán)境

Fig.1 Interaction of distributed Online Judge system operating environment圖1 分布式Online Judge系統(tǒng)運行環(huán)境交互

2.2 系統(tǒng)架構(gòu)與功能模塊設計

該分布式Online Judge 系統(tǒng)架構(gòu)主要分為4 個板塊：前端交互頁面、調(diào)度服務器端節(jié)點、端判題節(jié)點、數(shù)據(jù)存儲節(jié)點。用戶只需在前端頁面上提交評測代碼，Django 就會將前端數(shù)據(jù)寫入數(shù)據(jù)庫，并將代碼傳到后端調(diào)度節(jié)點，后端任務調(diào)度會將代碼加入評測隊列，完成評測后更新數(shù)據(jù)庫評測狀態(tài)。分布式Online Judge 系統(tǒng)架構(gòu)如圖2所示。

Fig.2 Architecture of distributed Online Judge system圖2 分布式Online Judge系統(tǒng)架構(gòu)

該系統(tǒng)基于B/S 架構(gòu)，管理員、學生、教師可通過計算機或其他移動設備進行操作，系統(tǒng)功能模塊設計讓如圖3所示。

通過對不同Online Judge 平臺進行分析，本文根據(jù)實際需求及應用場景，主要實現(xiàn)Online Judge 系統(tǒng)以下功能模塊：

Fig.3 Design of distributed Online Judge function module圖3 分布式Online Judge功能模塊設計

（1）用戶注冊。主要驗證用戶是否為本校學生，對接學校教務系統(tǒng)登錄數(shù)據(jù)庫，使用登錄爬蟲將用戶學號及密碼與學校教務系統(tǒng)進行對接驗證，驗證成功后，將用戶信息寫入本系統(tǒng)用戶數(shù)據(jù)庫。

（2）用戶登陸。通過Cookies 技術(shù)，保持用戶登陸狀態(tài)，只有在登陸狀態(tài)下，才能訪問試題列表、提交評測代碼等操作。

（3）試題系統(tǒng)。通過預先設定的密碼進入，指定或隨機形成試題集合，用于課堂任務、期末考試、比賽選拔人員等場景。

（4）公告系統(tǒng)。發(fā)布公告，所有人員可查看，發(fā)布口位于管理員后臺。

（5）管理員后臺。Django［18］是基于Python，可非常快速、簡單地進行開發(fā)，僅需少量代碼即可完成網(wǎng)站的簡單架構(gòu)。Django 基于MVC 模型，即Model 模板、View 視圖及Controller 控制器組成的設計模式［19］。MVC 模式可簡化后續(xù)對程序的修改和擴展，并可使某部分程序重復利用，極大提升開發(fā)效率。通過對Django Admin 后臺進行二次開發(fā)，使管理員能夠在后臺快速操作數(shù)據(jù)庫，即發(fā)布公告、增刪試題數(shù)據(jù)、查看用戶提交數(shù)據(jù)等操作，方便后期管理員操作，提高系統(tǒng)可維護性。Django MVC 模型如圖4所示。

（6）任務調(diào)度器。使用服務器作為任務調(diào)度器，用TCP 協(xié)議監(jiān)聽1102 端口，當Django 服務端將用戶評測數(shù)據(jù)發(fā)往次端口時，自動判斷評測類型，并轉(zhuǎn)發(fā)到相應的Docker評測機［20-21］。

Fig.4 Django MVC model圖4 Django MVC模型

（7）評測機。當Docker 沙盒里的評測機接收到判題請求時，自動識別題目序列號，并調(diào)用對應測試集進行限定時間、限定內(nèi)存的評測，并更新評測結(jié)果到數(shù)據(jù)庫［22］。

3 數(shù)據(jù)庫設計

3.1 系統(tǒng)簡介與運行環(huán)境

分布式Online Judge 系統(tǒng)功能實現(xiàn)需要后端數(shù)據(jù)存儲功能，故本次開發(fā)所采用的數(shù)據(jù)庫為Mysql 5.6 Linux x86 64位版本。

設計數(shù)據(jù)表需考慮整個系統(tǒng)功能，綜合考慮后構(gòu)建多個數(shù)據(jù)表結(jié)構(gòu)。在設計表時需考慮以下特性：①原始性：基本表中所有數(shù)據(jù)均為數(shù)據(jù)源創(chuàng)建時的原始數(shù)據(jù)；②演繹性：基本數(shù)據(jù)表可以進行多種組合，滿足系統(tǒng)各場景需求；③穩(wěn)定性：表的結(jié)構(gòu)穩(wěn)定，在系統(tǒng)設計完畢后，保持表結(jié)構(gòu)不被輕易更改；④原子性：表結(jié)構(gòu)中的所有字段均無法再細分。

3.2 數(shù)據(jù)庫表設計

基于設計庫的特性及分布式Online Judge 系統(tǒng)的應用場景，系統(tǒng)數(shù)據(jù)設計結(jié)構(gòu)主要分為以下5 張數(shù)據(jù)表：User-Info（用戶信息表）、（NoticeModel）通知公告表、ProblemSet-Model（試題信息表）、TestModel（比賽信息表）、CommitData（判題數(shù)據(jù)表）。數(shù)據(jù)庫結(jié)構(gòu)如圖5所示。

Fig.5 Database structure圖5 數(shù)據(jù)庫結(jié)構(gòu)

4 Online Judge系統(tǒng)實現(xiàn)及應用

4.1 用戶注冊

該分布式Online Judge 系統(tǒng)對非登錄用戶限制查看部分頁面，若要完整體驗整個系統(tǒng)，則需進行注冊。為保持信息安全，用戶注冊功能對接了本校教務系統(tǒng)，從而只對本校學生開放。

4.2 用戶登陸

為更好地服務學校，該系統(tǒng)通過爬蟲技術(shù)登錄學校教務系統(tǒng)，通過對學校教務系統(tǒng)登陸模塊的網(wǎng)絡抓包日志進行分析，發(fā)現(xiàn)學校教務系統(tǒng)的登陸認證方式為非對稱公私鑰登錄。登錄方式向登錄認證服務器申請公鑰，將申請到的公鑰信息解碼（信息為Base64 編碼加密）；對獲取到的參數(shù)信息與賬戶密碼共同進行Base64 加密，生成服務器所需密碼；用生成的高級加密標準密鑰（Advanced Encryption Standard，AES）［23］向服務器發(fā)起登陸請求，并保存登錄的Cookies 文件，保持登錄狀態(tài)。

AES 非對稱加密算法是目前最具影響力的算法，其基本原理為［24］：

（1）密鑰生成。在安全參數(shù)n上，生成公鑰（N，e）和密鑰（N，d），使得N=p*q，p、q素數(shù)長度為n，e互質(zhì)φ（n）=（p-1）（q-1）和d=［e-1modφ（N）］；

（2）加密。給定消息m∈Z*N，加密（N，e）（m）：=［memodN］；

（3）解密。給定密文c∈Z*N，解密（N，d）（c）：=［cdmodN］。

從登錄到密鑰生成，再到整個加密和解密過程的核心代碼如圖6所示。

Fig.6 Login encryption module decryption module core code圖6 登錄加密模解密模塊核心代碼

4.3 用戶代碼提交

用戶在前端頁面完成對應題目后，可通過前端頁面提交編寫的代碼，前端頁面收到提交代碼事件后，會異步將用戶代碼交給Django 視圖層進行處理。該系統(tǒng)視圖層處理方式為：將數(shù)據(jù)保存到數(shù)據(jù)庫，根據(jù)用戶姓名、提交題目ID、提交時間用md5 生成唯一主鍵，即任務隊列的ID，Django 視圖層將任務隊列ID 傳給后端調(diào)度節(jié)點進行判題調(diào)度，判題節(jié)點根據(jù)隊列ID 取出數(shù)據(jù)庫中用戶提交的代碼，并進行評測，評測完成后，刷新數(shù)據(jù)庫評測狀態(tài)，從而實現(xiàn)代碼提交功能。

4.4 后端判題節(jié)點

該分布式Online Judge 系統(tǒng)后端判題節(jié)點采用一對多的方式實現(xiàn)后端判題功能集群。隨著算力增大，通過分布式計算可實現(xiàn)在多臺服務器上平衡負載，提高計算效率。在實驗中，使用1 臺調(diào)度服務器和3 臺判題節(jié)點服務器，其中，調(diào)度服務使用輪詢調(diào)度算法。輪詢算法的主要實現(xiàn)原理是將前端用戶發(fā)來的判題服務請求由調(diào)度服務器輪流分配給多臺判題服務器，從1 到N（判題服務器個數(shù)），然后重新開始循環(huán)。由于調(diào)度服務器不用實現(xiàn)計算功能，故可快速完成任務調(diào)度分配，而判題節(jié)點服務器只需完成相應判題響應服務即可。由于多判題服務節(jié)點存在，即使某個判題節(jié)點宕機，也不影響整個服務運行。調(diào)度服務器由Nginx 框架實現(xiàn)，判題服務節(jié)點使用DOCKER 容器，將服務端口開放給調(diào)度服務器，構(gòu)建路由映射表，實現(xiàn)調(diào)度服務功能。

后端判題節(jié)點由兩部分組成：任務調(diào)度模塊和評測模塊。任務調(diào)度模塊的主要任務是監(jiān)聽TCP 端口（該系統(tǒng)使用1102 端口），由于Django 會將CommitID 通過TCP 協(xié)議發(fā)送數(shù)據(jù)給調(diào)度服務器，因而此模塊的Python 實現(xiàn)為監(jiān)聽事件，判題節(jié)點通過Python 的unittest 庫實現(xiàn)，該庫可以實現(xiàn)代碼的自動化測試并生成測試報告。

4.5 管理員后臺

為方便后續(xù)公告發(fā)布、試題增刪、比賽創(chuàng)建等操作，該系統(tǒng)還增加了管理員后臺頁面，管理員可通過預留的/admin 頁面進行管理員后臺登錄，登錄成功后可對整個系統(tǒng)數(shù)據(jù)進行增刪改查操作，適用于沒有網(wǎng)站維護經(jīng)驗的管理人員。

4.6 答題數(shù)據(jù)結(jié)果可視化

大多傳統(tǒng)判題系統(tǒng)僅有簡單的統(tǒng)計可視化功能，且均為基于靜態(tài)數(shù)據(jù)的可視化展示，并不具備深度分析的能力。該分布式Online Judge 系統(tǒng)除可視化功能強大外，還可實現(xiàn)動態(tài)及增量數(shù)據(jù)更新。數(shù)據(jù)可視化主要采用Echarts，使用多容器承載、Grid 組件及ajax 實時刷新，所有數(shù)據(jù)均從Mysql 數(shù)據(jù)庫中獲取。系統(tǒng)憑借良好的交互性，通過直接集成Echarts第三方開源數(shù)據(jù)可視化工具，更為快捷地將系統(tǒng)內(nèi)數(shù)據(jù)生成直觀生動、可交互、可個性化定制的數(shù)據(jù)可視化圖表，賦予學生、教師或管理員對數(shù)據(jù)進行分析整合的能力。

學生測評成績可視化功能展示將測評成績排名進行可視化呈現(xiàn)，可按班級、系、院、校分別排名。學生可通過條形圖看到每次測評的排名結(jié)果，學生個人測評班級排名可視化界面如圖7所示。

Fig.7 Student personal evaluation ranking圖7 學生個人測評排名

通過折線圖可詳細看到學生某季度測評均值，該結(jié)果自動匯總，生成個人成長曲線。學生個人測評結(jié)果分數(shù)匯總頁面如圖8所示。

Fig.8 Summary page of student personal evaluation score圖8 學生個人測評結(jié)果分數(shù)匯總頁面

教師和管理員通過后臺界面可以看到綜合測評結(jié)果維度可視化頁面展示，用來分析題型測評的不足。可視化雷達圖和柱狀圖主要從圖論、數(shù)論與組合數(shù)學、數(shù)據(jù)結(jié)構(gòu)、動態(tài)規(guī)劃搜索、計算幾何、算法基礎(chǔ)6 個維度構(gòu)建測評指標，從而分析年級排名和班級排名，從不同維度獲得排名結(jié)果。該可視化頁面可以從年級和班級2 個維度進行對比，得出學生在解題中薄弱的知識點，有針對性地在課堂上講解相關(guān)知識點。綜合測評結(jié)果雷達圖和柱狀圖可視化頁面如圖9、圖10所示。

Fig.9 Radar chart visualization page of comprehensive evaluation result圖9 綜合測評結(jié)果雷達圖可視化頁面

Fig.10 Histogram visualization page of comprehensive evaluation result圖10 綜合測評結(jié)果柱狀圖可視化頁面

5 結(jié)語

本文提出的系統(tǒng)使用Python3.6 作為主要開發(fā)語言、Django Rest Framework 作為后端框架、Centos7 系統(tǒng)作為OJ的服務環(huán)境，采用Bootstrap 完成前端頁面設計、Docker 容器技術(shù)完成沙盒隔離，并作為評測機的運行環(huán)境。考慮到性能問題，該系統(tǒng)使用分布式架構(gòu)以確保整個系統(tǒng)的安全性、高效性和穩(wěn)定性。在數(shù)據(jù)分析和可視化方面，該系統(tǒng)構(gòu)建種較為獨特的評測體系，并能夠生成簡版?zhèn)€人成績測評分析報告。

同時，該系統(tǒng)也存在一些不足，主要有3 點：①系統(tǒng)尚不能生成班級測評成績詳細分析報告功能頁面；②各項測評指標體系構(gòu)建需進一步細化，如：一級測評指標和二級測評指標科學構(gòu)建方法探索；③該系統(tǒng)最終可視化的本質(zhì)是希望借助大數(shù)據(jù)思想實現(xiàn)預測趨勢的功能。因此，后續(xù)將進一步完善該系統(tǒng)各班級測評成績分析報告和各項測評指標體系構(gòu)建，如一級測評指標體系維度（圖論、數(shù)論與組合數(shù)學、數(shù)據(jù)結(jié)構(gòu)、動態(tài)規(guī)劃搜索、計算幾何、算法基礎(chǔ)），二級測評指標體系維度（測評效率、測評題型復雜度、測評能力、測評方法等），更加深入地挖掘和分析數(shù)據(jù)可視化功能模塊，完善其預測功能。