一種分布式Online Judge系統設計與實現

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

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

0 引言

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

1 相關研究

在線程序測評系統最早可追述到1960年，是計算機輔助教學系統中的一個分支［6］。隨著計算機技術的進步和互聯網技術的發展，該系統在功能和應用規模上均取得巨大進步。

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

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

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

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

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

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

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

2 分布式Online Judge系統方案

2.1 系統簡介與運行環境

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

文本分布式Online Judge 系統的開發運行環境如表1所示，系統運行環境交互如圖1所示。

Table 1 Development and operation environment表1 開發運行環境

Fig.1 Interaction of distributed Online Judge system operating environment圖1 分布式Online Judge系統運行環境交互

2.2 系統架構與功能模塊設計

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

Fig.2 Architecture of distributed Online Judge system圖2 分布式Online Judge系統架構

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

通過對不同Online Judge 平臺進行分析，本文根據實際需求及應用場景，主要實現Online Judge 系統以下功能模塊：

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

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

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

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

（4）公告系統。發布公告，所有人員可查看，發布口位于管理員后臺。

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

（6）任務調度器。使用服務器作為任務調度器，用TCP 協議監聽1102 端口，當Django 服務端將用戶評測數據發往次端口時，自動判斷評測類型，并轉發到相應的Docker評測機［20-21］。

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

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

3 數據庫設計

3.1 系統簡介與運行環境

分布式Online Judge 系統功能實現需要后端數據存儲功能，故本次開發所采用的數據庫為Mysql 5.6 Linux x86 64位版本。

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

3.2 數據庫表設計

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

Fig.5 Database structure圖5 數據庫結構

4 Online Judge系統實現及應用

4.1 用戶注冊

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

4.2 用戶登陸

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

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

（1）密鑰生成。在安全參數n上，生成公鑰（N，e）和密鑰（N，d），使得N=p*q，p、q素數長度為n，e互質φ（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 視圖層進行處理。該系統視圖層處理方式為：將數據保存到數據庫，根據用戶姓名、提交題目ID、提交時間用md5 生成唯一主鍵，即任務隊列的ID，Django 視圖層將任務隊列ID 傳給后端調度節點進行判題調度，判題節點根據隊列ID 取出數據庫中用戶提交的代碼，并進行評測，評測完成后，刷新數據庫評測狀態，從而實現代碼提交功能。

4.4 后端判題節點

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

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

4.5 管理員后臺

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

4.6 答題數據結果可視化

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

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

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

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

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

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

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

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

5 結語

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

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