四篇文章一張圖系列。(上一篇還是 18 年的事情。)
這篇文章主要介紹的是我(糊)的畢業設計《高並發黑盒測評系統的設計與實現》的時候的一些想法,並不是論文內容。主要在說工程化的競賽支持系統開發,對於一些開源的 OJ 實現並不合適,畢竟從人員水平,組織結構,底層基建等方面很難做到和能用一定資本支持,可以進行工程化開發的組織相同,有些開發組織也可能就是企業中的一個組(很典型的例子如字節 Kitex 的開發團隊是字節基架的一個組)。所以在小規模的開發上切忌照搬照抄,它是有用的,但是是沒用的。
CDOJ 是由 10-11 級(推測)的學長們編寫的測評系統。由於之前代碼托管在 Google Code 上,13 年遷到瞭 Github(存疑),Github 上可見最早的 commit 在 2012 年 12 月 18 日。後續又經歷瞭 2000 多次 commit,發佈瞭 9 版 release,於 2018 年 9 月 4 日結束生命周期,並正式轉向 Lutece。Lutece 後端的第一個 commit 在 2018 年 5 月 20 日,前端的第一個 commit 在 2018 年 9 月 23 日,測評端 Osiris 的第一個 commit 在 2018 年 4 月 14 日。項目初期前後端是耦合的,後期才把前端代碼從後端遷出(看起來是這樣)。目前前後端開發均在暫停中,不再實現新需求,測評端已歸檔。
我大概是在 2019 年 10 月接手瞭 Lutece 運維,那個時候需要導出趣味賽的代碼以便查重,然後需要抓一個運維,於是就抓瞭我。但是說運維也不是運維,畢竟啥也不會修,2020 年(具體出現第一起 bug 的時間已經忘瞭)學校切 IPv6 導致 Websocket 優先檢索 IPv6,超時瞭之後才降到 IPv4,導致測評結果實時刷新工作不正常,這個 bug 還是 21 年 5 月勞動節柱爺和沈爺修的,印象深刻,因為我在實習。這幾年的主要工作就是導出代碼和啟動後端,自動化運維沒有,打點沒有,bot 沒有,然後導致 Lutece 運行健康但是不健康,磁盤占用 70%,快拉閘瞭的感覺(之後收拾瞭一下硬盤,遷出瞭一些數據)。
然後因為 Osiris 還不支持 checker(應該是實現失誤),Java 不支持多個類(這個應該也是實現失誤),不支持交互題(本身設計上就不支持),不怎麼信得過 Python 的運行效率,和我一起在北京實習的同學中有一個是在做字節內部的後端,寫 Python 的,天天感覺寫個代碼要死要活,每天晚上互相吐槽工作的時候總有種沒眼看的感覺(甚至在某些方面覺得自己很輕松,但是他下班早)。所以調查瞭一下 containerd 的實現,發現可以用 libcontainer 偷懶,就大概想用 Go 重寫一下,在 21 年 8 月的時候終於把原型寫出來瞭(其實 21 年 2 月就開始需求分析瞭,但是 2-7 月在實習,7 月底 8 月初又在準備預推免),然後 9 月開始寫可迭代版,然後重寫瞭四遍(十分生草),改瞭目標,才在今年 3 月寫完瞭第一個可迭代版(半年啊半年)。
原本是真打算做一個完全體的,但是設計好瞭之後發現實現難度太大(重寫四遍的原因)。並且大概從 20 年下半年(也可能是 21 年上半年,具體時間點忘掉瞭),我們的域名就被禁止外網訪問瞭,於是 vjudge 用不瞭瞭,然後翻瞭翻 vjudge 上竟然翻出瞭兩個 CDOJ 相關題庫,一個是 UESTC,一個是 UESTC_old,沒怎麼搞明白是怎麼回事,但是這兩個部分取並就是目前 Lutece 的題庫的真子集,想瞭一下,把目標改小瞭,先支持一下 vjudge 復原。
首先,這是兩個完全不一樣的項目。CDOJ 是一個在線測評系統,CDOJ-Vjudge 是一個歸檔測評系統後端。
CDOJ-Vjudge 的誕生主要考慮到它和競賽中使用的測評系統實際上都屬於一種題目已歸檔的測評系統,可以認為在運行時是隻讀的,比賽時不會增刪改題,對於題目也很忌諱增刪改數據,歸檔的 Vjudge 也不存在這些操作,因此隻需要解決讀問題就可以瞭。調查需求時也問瞭教練,教練表示不太想公開 Lutece,主要是沒啥收益,還怕走 HDU 的老路,有些題涉及 SCOI 也不希望公開,但是對於已經公開 10 年的東西,也沒必要再下線瞭,所以把數據拷出來瞭一份,之前老 CDOJ 的數據刪瞭,頓時服務器磁盤就空瞭很多,因為原來 CDOJ 的數據庫都在 Lutece 的服務器上。
CDOJ-Vjudge 未來不會增刪改任何題目,如無必要也不會對數據進行任何增刪改,題目版本預期是截止到 2022 年暑假前集訓。
因為這種特殊的已歸檔屬性,有很多地方可以簡略設計,前臺服務的精力就可以放在比賽的管理上瞭,而對於 Vjudge,隻需要實現三個接口:
就行瞭。
第一個沒啥邏輯問題,就數據庫查詢,打包一下 response 完事。第三個也類似,做一下消息隊列用 redis 狀態更新就行瞭。問題就出在第二個功能點上。
從「測評」的底層邏輯來看,對「自動化測評器」的研究早在 1959 年就開始瞭。1959 年,一種「自動化測評器」(automatic grader)的初版在紐約的倫斯勒理工學院正式用在微分方程的課程教學中[1],之後對於自動化測評器的研究均聚焦於計算機的教學中,比如設計對於 Fortran 語言的自動化測評器。
從程序設計競賽的發展來看,最早的一次程序設計競賽應該是 1970 年的 First Annual Texas Collegiate Programming Championship,當時還是需要把程序紙帶交給裁判,裁判去手動運行,然後判為正確的話送給這個隊伍一個氣球。但是並沒有證據證明比賽使用瞭自動化測評器。隨著競賽的逐漸發展,這個測試過程變得自動化瞭,至少從 1990 年開始,ICPC WF 就開始使用自動化的測評系統(當年是 PC^2)來管理和運行比賽。
再後來,我們有瞭 OI,有瞭在線測評系統,有瞭競賽社區。隨著時間推移,選手的層次也從計算機專業的大學生,研究者變成瞭從小學到研究生應有盡有,從專業水平,理解能力,到細節上的對某種語言掌握的熟練度也參差不齊。我們開始發現有很多東西是我們從未考慮過的,我沒見過哪個比賽規則裡面寫瞭不讓使用 #pragma
,也沒見過不讓使用某些指令集來加快運算速度,也隻見過 NOI 禁止瞭內嵌匯編,ICPC 來說,能過編譯就行,但是需不需要禁止或允許,或者可不可以禁止或允許,這是我們未曾關心過的。
歸根結底,ICPC 競賽實際上是「程序設計競賽」,使用預編譯頭添加編譯參數也是一種可以的操作,使用內嵌匯編,指令集或多線程加快程序運行速度在程序實現的時候也比較常見,雖然對於「程序設計競賽」和「算法競賽」是否應該區分,怎麼區分,我也不想關心。
理想中的「測評」行為就是直接在裸機上指定程序輸入後運行程序,得到程序輸出後按照某一標準進行處理,得到對於這組輸入,程序運行是否正確。這裡就出現瞭一些問題:
現在的測評系統在最後一點上給出瞭各異的答案,但是前三點是趨同的,選手提交源代碼,放在沙箱裡運行,限制 CPU 時間和內存使用。但是評判結果中,有些系統使用的是 diff
,有些使用 testlib 提供的標準比較器,在 DOMjudge 中不會透露運行時間和內存,隻有一些簡單的通過與否的狀態,但是大多數 OJ 都會提供運行時間和內存,很多 OJ 還會提供部分輸入輸出,用戶的標準輸出和標準錯誤輸出作為參考。更多細節不再贅述瞭,各大 OJ 都自有想法和標準。
這種「測評」行為確實符合瞭這種混沌狀況,我們實際上對「程序設計競賽」應該使用何種標準來「測評」沒有更多的規范。借用遊戲方面的語言,這導致瞭一定的遊戲公平性喪失。比如 A 知道各種奇妙底層知識,B 有著通天的黑客技能,C 是一個正常選手,他們都可以利用他們的知識通過一道數據結構題,付出的努力可能是一樣的,但是他們使用的方法各不一樣。一個萌新看到瞭 A 使用各種底層技巧狂砍數據結構,那他可能會認為數據結構本身是不必要的,使用底層技巧是必要的,一個萌新看到瞭 B 各種 pwn 沙箱,docker 逃逸玩得一套一套,那我覺得他也不會把心思再放在怎麼去實現算法瞭。其他玩傢對於新手總有引導性,怎麼制定遊戲規則才能讓玩傢不走未曾設想的道路,這是需要考慮的。我們當然希望 C 選手是主導的,但是 AB 選手的存在是現實的。我覺得遊戲公平性也不能是非黑即白的,總有一些緩沖地帶來提高遊戲趣味性。
這項畢業設計就基於如上對於「測評」概念的思考,提出如下假設:
我們的目標是:
我們使用工作流(Workflows)描述一次測評過程,工作流是由階段(Stages)構成的拓撲結構,階段使用步驟(Phases)來細化。步驟由進程組(Processes Groups)和共享資源(Resources)來描述。對於一個進程,我們使用 libcontainer 中對於進程的描述,其中包括命令,環境變量,進程獨享資源,標準輸入輸出、錯誤輸出重定向等等。
這裡設計共享資源的原因是需要實現進程間的通訊,定義隻要資源被大於 1 個進程共享,就屬於共享資源。那麼連接兩個進程的管道就屬於一個共享資源瞭,同樣可以限制共享的 CPU 和內存,但是實際上這個限制並不重要。
對於每個步驟的運行,運行環境中應當保證隻存在必要的資源,如 CPU,內存等計算資源和文件,管道等文件。具體來說應使用白名單式的管理,例如對文件的新建,讀取和寫入等都應該經過審計。但也存在一些細節上的問題,比如很多 OJ(Lyrio,DOMjudge 等)都對 swap 內存使用加瞭限制,這裡是需要註意的。但是根據 cgroups v1 的文檔 5.3 節,把 swappiness
調成 0 就可以禁掉 swap 使用瞭。不過這樣操作比較激進,比如出現單個測評請求的運行不會導致內存使用超過物理內存,但是多個測評請求同時運行可能導致內存不足,那麼這種時候調整 swappiness
的策略可能導致因為內存互相占用產生 OOM。
實現上來說,主要的問題集中在多階段或者多步驟之間的文件傳遞和共享。比如編譯階段產生的二進制文件(可能有多個,比如 Java 編譯出來的二進制文件就可能有很多個,多份代碼也可以各自編譯出各自的二進制文件),步驟中產生的文件等。這些文件需要被系統統一管理,否則不能保證程序運行時能且隻能訪問到這個步驟中提供的文件資源。
一般來說,這種不能保證程序運行時能且隻能訪問到這個步驟中提供的文件資源,可能會產生讀答案文件,對沙箱任意寫的問題。對於前者是開發者都要避免的,並且代價不大,隻需要不將答案在運行中拷貝到選手所在的沙箱裡就行瞭。但是對沙箱寫的情況,一些沙箱並沒有做好控制。一些選擇 Linux 用戶的方式,還是避不開在同目錄下生成文件。這裡可以使用監控工具進行監控,比如 Go 的 fsnotify。但是監控文件也是有一定代價的,這種方式是不是最好的方式還需要進一步調查。
之後就是任務並行和裝載與卸載問題,感覺好難啊,需要在集群上工作的同時保證部署在單機時性能不降,感覺有點不可能,伸縮性要求太高瞭。Workflow 上也會有一些 Phase 是可以並行的,兩步之間其實都類似生產者和消費者模型。
最後實現上為瞭上線,把上面寫的 Workflow 模式全下瞭。
Web 端:GitHub - HeRaNO/cdoj-vjudge
Worker:GitHub - HeRaNO/cdoj-execution-worker
結論是,現狀是十分不健康的,因為很多人沒有意識到這是一個問題,或者認為這不是個問題,或者認為這是個十分簡單的問題,或者認為這個問題過於復雜,但不需要付出過多努力解決它。
以此提供服務的企業很多都沒有正確地認識問題,在牛客上的比賽有較大的時間測量問題,從隊內選手的體驗和昆明站選手的體驗,都認為牛客的時間測量是有問題的。在 LibreOJ 開發群裡也有很多企業花錢去部署 SYZOJ 或者 LibreOJ,裡面提問的甚至是客服,不是技術人員。然後問技術人員在哪兒,回下班瞭,當場血壓就爆棚,但是想瞭想,又不是互聯網企業,不需要降低缺陷響應時間。
例如牛客,它的目標用戶是企業和求職者,隻需要給他們提供一個能跑的環境就行,不需要競賽那樣穩定,所以牛客的技術團隊就不會把提升時間測量精度作為技術需求來看,當然也包括洛谷的整體架構提升問題。企業追求效益,不追求效益它就崩潰瞭,但需要指出的是,企業在推動競賽發展的過程中,作為太少,甚至說根本沒有作為。現如今沒有任何企業去推動競賽的環境標準化和通用化,開源的實現,測試 Benchmark 也沒有,甚至都很難知道他們的團隊是否可以理解現狀。社區的開發能力和水平也不足以支持這樣規模的開發,所以大傢都擺爛瞭。
實際上給競賽命題也是一團糨糊,甚至找不到一個明確的產品定位和產品評估方式。很多時候我們都沒有一個清晰的產品定位。
預期中的 CDOJ Vjudge 是一個中臺,希望 OJ 開發者將目光聚焦到某個領域,設計比賽或者題目展示功能隻設計到前臺的開發,但是對於提交測評等需求是中臺的開發,這兩者的方向是不同的,前臺需要關心的是業務實現,但是中臺更側重技術需求。我們希望的是 OJ 開發者集中於技術需求,將前臺業務代理給 Vjudge 這樣通用的前臺。因為前臺的需求是通用的,即使不需要對 OJ 本身有很多瞭解也能開發出來,但是它對高並發,高可用的開發技術要求很高。現如今 XCPCer 或者 OIer 根本接觸不到任何高並發場景,沒有開發這種前臺的能力,反而更適合開發中臺,去定義整體的測評流,開發測評部分的功能。大部分沒有參加過競賽,或者隻是淺嘗輒止的開發者對於測評過程的理解依賴於產品對此的描述,而產品人員的描述很大程度上又依賴於對產品整體的理解,現如今沒見過 XCPCer 或者 OIer 去當產品的,大部分都是研發。因此這部分淺嘗輒止的開發者開發出的測評端,用在真實的競賽場景下,在一些更加專業的眼光和審視下必然出現一些紕漏,這是層次和深度導致的。
字節實習的時候我不太感冒我做的電商業務,我也不怎麼覺得我做得需求有多麼重要,或者能帶來多大的收益。但是有兩個詞還是很有意義的:「不設邊界」和「不自嗨」。
我始終認為,軟件工程是一種感覺,或者說是一種意識。它不單單是對工程的把握,同時也是一種對用戶的思考。信息將你我相連,無論是開發者還是用戶,都無法逃過事物的普遍聯系,軟件隻是一個載體,最重要的是在它上面體現的,在這種聯系中人的價值。我們需要讓軟件做得更好,就逃不掉「柴米油鹽」——健壯的框架,充分的需求調研,細致的實現等等,這些工作都要通過開發者來實現,但是這些工作都足夠復雜,使得一個完全不懂開發的人無法把握。隻有從不斷的實踐中,開發者才會懂得什麼樣的需求調研是足夠充分的,什麼樣的架構是足夠健壯的,什麼樣的實現是足夠細致的。在這種實踐過程中,形成的方法論未必都能落實在紙面上描述,因為條件太復雜,環境太多樣,所以就形成瞭這種感覺,或者說這種意識。實踐過程不是開發者的自嗨,而是在生產環境中調查用戶的感受,用戶的使用情況,開發者的感覺應該是面向用戶的。我認為開發者不僅應該具有感知工程結構的能力,還應該有一種預知風險,甚至是公共關系風險等一類風險的能力。自嗨的工程,從某種角度上來說是脫離群眾的,那將是膚淺的,將受到時間和歷史批判的。自嗨的工程也是危險的,有很多時候是一種表面思考,或者三分鐘熱度,這對編程也是一種不利影響,代碼結構就順著這種三分鐘熱度大幅度變更,這是十分危險的。
我覺得目前我們給自己設的邊界太多,很多人都抱著一種嚴格的定義來思考競賽,但是越嚴格的限制雖然可能帶來瞭公平和形式化,但是很難讓人有創造力,俗話說就是沒活整瞭。沒活整的領域必然會導致衰落,目前黑盒測評系統也沒有更多的技術創新,或者說很多人認為不需要創新或者不能創新。黑盒測評系統是競賽的基礎工具,但它不應該是那種像錘子,螺絲刀等等一樣定型的工具。雖然說在這方面也有出題人沒活整瞭的因素存在,但是事物是聯系的,測評系統和出題人也可以互相影響,進而發展。
但是這兩個詞放在一起,就出現瞭一些重疊。有時候我們不設邊界,去探索未知,但是在他人眼裡就已經屬於自嗨瞭,或者我們真真正正就在這個未知領域自嗨瞭起來。有時候我們不自嗨,卻故步自封,不去思考怎樣發展而是思考怎麼打補丁。我認為,針對這一問題,使用用戶視角看待問題尤為重要。
我希望黑盒測評系統不會永遠沒活整瞭。或者說,真沒活整瞭的那天,固定題型題目的創意也就那些,如果加上題目上再沒活整瞭,競賽也涼瞭。
從研究和開發的角度來說,我連一篇中文綜述都沒找到,造個 OJ 或者改改 HUSTOJ 都能碩士畢業,這合理嗎。說實在的我感覺我論文比較水,因為我上來對著 OJ 輸出瞭 1w 多字的綜述和技術演進分析,傳到知網上竟然查重隻有 0.4%,這個領域連個全面一點的綜述都沒有,隻能說,
寫你嗎呢。
翻各種數據的時候翻到的奇奇怪怪的東西:
以上。