Beyond the Void
BYVoid
Vakuum開發筆記01 開天闢地
本文正體字版由OpenCC轉換

1.緣起

先驅——COGS

早在2008年,我自學PHP後開發了COGS,併成功用於學校內部的OJ,ruvtex。也曾經對外開放過,但是由於學校網絡不穩定,後來一直連不上了。我還把COGS推薦給了OOJ,只是直到現在都過於冷清。隨着COGS功能不斷完善,體系越來越龐大,Bug也非常多。限於當時水平,架構非常混亂,以至於到無法繼續維護的地步,於是我遺憾的宣佈了COGS的死亡。隨後我又萌生了一個重新設計的念頭,只是高二時期忙於NOI和文化課的學習,這一計劃就一直被擱置到NOI2009結束。

知識準備

NOI2009結束以後,我終於有了時間,可以進行我新的OJ的開發了。之前的COGS不敢開源,因爲寫的太爛,開源的話肯定會黑得萬劫不復。不過新的OJ不同,爲了提高對自己要求,我決定對其開源。

我在暑假時期閱讀了有關PHP高級開發、MVC架構、Javascript、CSS、Linux系統編程等大量書籍。受到經典的架構Zend Framework的啓發,起初決定用它開發,但是學習不久就發現Zend Framework過於龐大,學習難度太大,並且難以找到比較好的資料。在Zend Framework的官方網站上閱讀純英文的文檔實在太費力了,而且效果不好,始終沒有弄明白其本質。開源界有一個箴言,叫做“不要重新發明輪子”。什麼意思呢?就是說很多開發人員總是在做一些前人已經做過,而且做得很好的工作。比如libxml2已經是一個非常優秀的C語言XML庫了,你再自己寫一個XML解析庫,就是在浪費時間,儘管也許你做的不錯,但也最多算的上是“重新發明了輪子”。起初我非常篤信這句“箴言”,拼死也要學Zend Framework,做了大量的無用功。但後來細細一想,我們最初學算法、數據結構的時候,不是都是要自己實現每一個細節嗎?儘管庫函數可能已經做得很好了,如qsort,平衡樹。而我現在也是MVC架構的初學者,在對其理解不是很深刻的情況下,直接學習某個庫、某個架構,是非常不明智的行爲。因此我決定要“發明輪子”——自己開發一個合適的架構,就叫——BYVoid Framework Library(BFL)。

恰好當時父親的公司準備建一個產品介紹性網站,爲節約成本就把開發的任務交給了我。我想這是一個難得的練手的機會,決定用我的BFL開發。果然在開發的時候遇到了前所未有的問題,但是都一個個迎刃而解了,而且獲得了不少經驗,其中包括Apache2 .htaccess的設置。兩個星期以後,公司的網站製作完成,我的"MVC架構輕量級內容管理系統"也發佈了。

2.Vakuum誕生之初與架構設計

命名

2009年9月,我正式開始開發新的OJ。在開發先我想先起個名字——就像“沒有名字的船不會帶來好運”。起初準備叫vacuum,英語意思是“真空”,算是Beyond the Void的衍生。但是我不幸地發現這個名字已經在sourceforge上被佔用了,後來決定改名爲vakuum,即vacuum的德語拼寫方法。

基礎結構

Vakuum作爲一個OJ,我把它剖分爲了三個部分,vakuum-web,vakuum-judge和judger。vakuum-web是一個網站,用於和用戶交互,處理各種請求,它是一個PHP網站,應該能夠跨平臺vakuum-judge則是評測機終端,用於接收來自vakuum-web的評測任務,評測以後返回結果。而judger是評測的核心,其中包含編譯器compiler、執行器executor和檢查器checker三部分,分別用於編譯用戶程序、執行用戶程序和比對用戶輸出與測試數據。簡而言之,vakuum-web是一個用戶與核心的中介,而vakuum-judge則是judger的通信接口。我的目標是網站和評測分離,並允許多評測機協同工作,因此vakuum-web和vakuum-judge之間少不了通信。

通信設計

參考很多成熟OJ的結構,發現幾乎都是把vakuum-judge模塊實現爲一個常駐進程daemon,不斷檢查數據庫是否有新的任務出現,對其評測,但後寫回數據庫。多數設計都沒有分離vakuum-web和judger,即限定了只能有一個評測機,少數可以實現分離,但是實際上是多寫了一個通信程序。我的想法是vakuum-judge也用PHP實現,這樣就避免了自己寫一個socket通信程序,而且不需要額外獲得底層權限以常駐進程。這樣只需要接收來自vakuum-web的HTTP請求,對其處理,然後將結果寫回。可是這樣的一個同步傳輸方案有很大的問題,即vakuum-web發送請求以後需要長時間被阻塞在通信上,等待vakuum-judge評測的結束。如此一來加大了傳輸的風險,二來加重vakuum-web的服務器負載,三來還無法讓用戶看到評測的進度。因此我想出了一個異步傳輸方案,即vakuum-web只發送請求,完畢後就斷開連接,之後等待vakuum-judge的回傳即可。然而PHP有一個特性,就是用戶瀏覽器斷開連接以後,PHP腳本也會停止執行,vakuum-web是在模擬用戶瀏覽器發送請求,斷開鏈接以後就相當於瀏覽器按下了“停止”鍵,vakuum-judge正在執行的腳本不管到了哪裏都會停止。查資料以後才知道PHP有這樣的一個函數,ignore_user_abort(),忽略用戶中止,就是用來對付這種情況的。

隊列處理

通信方式設計很成功了,還有一個問題就是如何處理評測隊列。這是一個棘手的問題,要麼爲什麼有那麼多大型OJ經常卡在評測隊列上,出現Waiting長龍呢?幾乎所有的OJ都是寫了一個常駐進程的daemon處理隊列。我想爲了實現多評測機調度,這個daemon必須是現在vakuum-web端,但是這樣就違背了我當初vakuum-web能夠“跨平臺”的設想,而且vakuum-web必須獲得系統底層權限——不僅維護不便,還有安全隱患。

絞盡腦汁以後,我想出了“鏈式反應”的想法,其實也是受了通信設計方式的啓發。這種方法不需要獲得底層權限,不用額外寫一個daemon,能夠跨平臺,不用爲安全性額外操心,還可以充分利用先前寫好的代碼,究竟是什麼方法呢?其實就是用一個PHP進程來充當隊列處理器,這個隊列處理器不需要常駐內存,僅僅在用時纔會出現。就是當用戶提交一個評測任務以後,如果有空閒評測機的話,立即對任務進行處理,然後當vakuum-judge返回評測完畢的信號時,vakuum-web端再對評測任務隊列進行檢查,看看有沒有新的任務出現,如果有的話,立刻執行即可。這種方法很簡潔,而且支持多評測機協同工作,因爲每次結果返回時都要檢查隊列,就好像鏈式反應,或者多米諾骨牌一樣,只要處理了第一個,後面的就都會接着被處理。

這種隊列處理方法的唯一缺陷在於依賴評測機的返回信號,如果評測機那邊出了什麼問題,或者因爲通信原因vakuum-web沒有正常接收到信號,隊列就會被卡住。因此首先需要保證的是vakuum-judge需要絕對的安全和穩定,除非無可抗拒理由(如網線被拔),不會因爲任何原因而不正常返回信號。此外還要增加人工干預手段(如強制繼續處理隊列),避免真的不可抗拒原因的到來。

——————————————————————————————————

先到此爲止,歡迎繼續關注Vakuum開發筆記,下次將要寫的是評測機核心(judger)的設計。目前的開發進度停滯在後臺管理各種繁雜的細枝末節的處理上,下圖的是目前的後臺管理界面截圖。

點擊看全圖


上次修改時間 2017-05-22

相關日誌