Online Judge (grader) design

ดองบล็อคไปเสียนานมากในขณะที่เกมก็เริ่มมีเกมที่มันเล่นจนแบบว่าไม่รู้จะเล่นยังไงให้สนุกแล้วจนต้องดรอปไปอยู่บ้าง

ในภาคซอฟต์แวร์จะมีกิจกรรมอยู่อันนึงครับคือ SOSCamp เป็นการติวโปรแกรมมิ่งให้น้องใหม่ซึ่งก็จะมีการทำโจทย์ พอทำโจทย์ก็ต้องมีระบบตรวจ เพื่อนรีเควสมานานมากกกแล้วว่าอยากรู้ design ของระบบก็เลยเขียนสักหน่อย

Overall

ระบบแบ่งเป็น 3 ส่วนครับคือ UI, API, Grader ซึ่งผมเลือกเป็น PHP หมดเลยเพราะช่วงนั้นเห่อ Laravel และ Silex นิดๆ และถ้ามีคนจะช่วยทำ ใช้ Silex บน PHP น่าจะง่ายกว่าใช้ Django โดยเฉพาะคนที่เขียน Java มา คือ Silex ค่อนข้างจะ low level มาก เขียนอะไรๆ มันจะตรงไปตรงมาไม่มีลัดเท่าไร แล้วก็ PHP Class มันหน้าตาเกือบ Java ตัด type

UI

ตัว UI เขียนด้วย AngularJS ทั้งหมดเลยเพราะผมอยากลองเล่น AngularJS พอดี เขียนเสร็จก็เรียนรู้มันไปเยอะแต่รู้สึกว่ายากอยู่ ตอนหลังมารื้อทำใหม่แล้วเอาระบบ resolve ออกพบว่าเขียนง่ายขึ้นเป็นกอง

ด้วยสไตล์ของ Angular อยู่แล้ว ตัว UI ทั้งหมดออกแบบเป็นแบบ single page app คือมี HTML file เดียวรันทุกอย่าง ไม่มีการเปลี่ยนหน้าใดๆ นอกจากการใช้ AJAX ดึงข้อมูลมาแสดง ตรงนี้การเลือกใช้ Angular + Angular-ui-router ทำให้เขียนง่ายและดีมากๆ

ข้อดีอย่างนึงของการทำ Single page app คือมันบังคับให้ทุกอย่างเป็น API พอจะทำใหม่ก็ทำได้ง่ายๆ แค่เขียนตัวครอบ API ขึ้นมาใหม่ จบ

API

ฝั่ง API ใช้ Silex ครับ ผมลองเขียนแบบ OOP ดูโดยทำคลาสที่สามารถ extend มันมาแล้วระบุชื่อ Eloquent model และ URL (Eloquent เป็น library สำหรับต่อ database ของ Laravel ซึ่งผมดึงมาใช้เดี่ยวๆ ไม่เอา Laravel มาทั้งตัว เป็น ORM ตัวเดียวใน PHP ที่ผมชอบ) จะได้เป็น API ที่สามารถ List, read, write ลง database ได้ทันทีพร้อมระบบ access control ซึ่งก็ลดเวลาพัฒนาไปได้มาก ตอนหลังผมแกะระบบตัวนี้ไปใช้ในระบบลงทะเบียนงานบายเนียร์ด้วย วันเดียวก็เขียนระบบเสร็จ

Grader

ส่วนสำคัญที่สุดของโปรแกรมแน่นอนว่าต้องเป็นตัวเกรดเดอร์เอง ซึ่งตัวเกรดเดอร์นั้นใช้ไลบรารีหลายตัวช่วยในการพัฒนา (ผมคิดว่าบางตัวเป็น extra ไม่ใช้ก็ได้ แต่ใช้แล้วมันทำให้โปรแกรมเท่ขึ้น พวก Symfony/Console Symfony/Process พวกนี้)

ตัว grader จะต่อเข้ากับคิวงานกลาง ซึ่งระบบเก็บคิวงานที่ผมใช้คือโปรแกรม beanstalkd และใช้ library pheanstalk เพื่อเชื่อมต่อจาก PHP เมื่อมีการส่งงานเข้ามาใน API ก็จะโยนรายละเอียดงานเข้าไปใน beanstalk

ตัว grader ที่ต่อกับคิวงานนั้นจะมี infinite loop รับงานใหม่อยู่ เมื่อได้รับงานแล้วก็จะเข้าสู่ logic ในการตรวจ ซึ่งจะมีกระบวนการคือ

1. รันโค้ด generate test case

ตัวระบบ test case generator ผมอยากให้มันทรงพลัง สุ่มโจทย์ได้ และเป็นธรรมชาติที่สุด ก็เลยใช้วิธีเขียนโปรแกรมมาครอบโปรแกรมที่ใส่ไว้ในโจทย์ ข้อเสียคือรองรับการส่งได้แค่ภาษาที่มีโปรแกรมครอบ

หน้าที่ของโปรแกรมครอบไม่ยากครับ ขั้นแรกโปรแกรมจะ include โปรแกรมที่โจทย์กำหนดเข้ามา (ใน Java ใช้ reflection, Python ใช้ exec ซึ่งผมว่าไม่ดีเพราะ __name__ มันไม่เปลี่ยน, PHP ใช้ include) ทีนี้ขั้นต่อมาจะแยกตามภาษา

  • PHP: มันคือ echo json_encode(run()); นั่นล่ะครับ
  • Java: มันจะส่ง LinkedList<String> เข้าไปโดย pass by reference แล้วเอา LinkedList ตัวนั้นส่งเข้า GSON ออกมา
  • Python: ผมจำไม่ชัวร์แต่น่าจะประมาณว่าเอา for in วนเพื่อทำเป็น list แล้วโยนใส่ json.dumps

จริงๆ มันก็ดูไม่ช่วยเท่าไรนะ แต่ผมว่า python เนี่ยมันเขียนสนุกดีตรงที่ yield รัวๆ ไม่ต้องเอาข้อมูลไปพักใส่ array อะไรแล้ว return ออกมาทีเดียวเหมือนภาษาอื่นๆ (PHP ก็มี yield แต่มันใหม่เกินไป)

2. คอมไพล์โค้ดเฉลยและโค้ดคำตอบ

มาถึงขั้นตอนสำคัญครับคือการคอมไพล์โค้ด ซึ่งก็ไม่มีอะไรยากเท่าไรคือรัน compiler ตามแต่ภาษาแล้วให้มันออกมาที่ไฟล์ที่กำหนดก็เสร็จ แต่ความยุ่งยากอยู่ที่ Java ซึ่งชื่อคลาสจะต้องเป็นไปตามชื่อไฟล์ด้วย ผมก็เลยใช้วิธีโกงๆ คือตั้งชื่อไฟล์ว่า Input.java แล้วคอมไพล์ ถ้ามันผ่านก็จบ ไม่ผ่านตัว javac จะบอกมาว่า should be named ….java ก็ให้โปรแกรมมันอ่าน error ตัวนี้ไปแล้ว rename file ให้ (และเก็บชื่อคลาสไว้ด้วยเพราะตอนรันต้องใช้)

3. Run

ขั้นตอนการรันก็รันแบบตรงไปตรงมาครับ ทีนี้จะพูดถึงเทคนิคการ sandbox หรือป้องกันความปลอดภัยของโค้ดสักหน่อย ซึ่งจริงๆ มันทำงานมาตั้งแต่ส่วน generate test case แล้ว

ตัว grader จะใช้โปรแกรม docker ในการรันครับ ซึ่งหลักการคร่าวๆ ของ docker มันคือการใช้ความสามารถ namespace, cgroup ของ linux kernel ใหม่ๆ ช่วยแยกการทำงาน คนที่อยู่ namespace อื่นๆ จะมองไม่เห็นกันเอง แต่ข้างนอกสุดมองเห็นข้างในได้ นอกจากนี้มันยังสามารถกำหนดทรัพยากรให้ cgroup ได้อีกด้วย (คล้ายๆ virtualization แบบ virtualbox อะไรพวกนี้อะครับ แต่มัน overhead ต่ำกว่ามากเพราะรันอยู่ใน kernel ตัวเดียวกันเลย)

ข้อดีอย่างนึงของ docker คือสภาวะข้างในมันคงที่ถ้าเราก๊อปไป นั่นหมายความว่าถ้าเราเซตดีๆ version ของ compiler, runtime, library จะเหมือนกันหมดเลยถึงเราจะกระจาย grader ไปหลายๆ เครื่องก็ตาม

ทีนี้เวลารันด้วยความสามารถจำกัดทรัพยากรก็ทำให้สะดวกโยธินในการจัดการแล้วครับ

  • memory limit บังคับด้วย cgroup ได้เลยตรงๆ
  • networking ก็บังคับได้เลยว่าไม่ให้มีการ์ดแลน
  • time limit อันนี้ใช้ symfony/process จับเวลาเอา ถ้าเกินแล้วก็สั่งให้ docker kill ทิ้ง
  • privileges ก็สั่งให้ docker รันใน user ปกติ (ปกติ docker จะรันด้วย root) ก็เรียบร้อย

4. Cleanup

เสร็จแล้วก่อนจะจากก็ต้องลบไฟล์พวกที่เป็นผลจากการคอมไพล์ต่างๆ และตัว container ออก (ใส่เข้ามาทีหลังตอนเทส fork bomb ดู) เป็นอันเสร็จ

5. Submit

ตัว grader จะส่งงาน 2 รอบคือตอนที่ได้งานมา (เพื่อแสดงสถานะ grading) และเมื่อเสร็จแล้วจะส่งข้อมูลกลับเข้าไปใน API อีกครั้งหนึ่ง ซึ่งก็เป็น JSON ธรรมดา โดยอาศัยการยึนยันตัวแบบ shared secret คือ API, grader จะมี string ตัวหนึ่งเปรียบเสมือนรหัสผ่านที่ต้องส่งให้ API ทุกครั้งที่จะอัพเดตสถานะงาน

อื่นๆ

จริงๆ แล้วไม่ใช้ docker ก็ได้นะครับ เช่น elab ใช้โปรแกรม box ถ้าผมจำไม่ผิดมันจะใช้ความสามารถ ptrace คือเมื่อโปรแกรมลูกมีการเรียกฟังก์ชั่นของระบบ โปรแกรมแม่ (นั่นคือ box) จะถูกถามว่าอนุญาตหรือไม่ก่อนที่จะทำงานได้ (chrome เก่าๆ รู้สึกว่าจะใช้เทคนิคนี้เหมือนกันบนลินุกซ์) ตอนหลัง box มีรุ่นใหม่คือ isolate ซึ่งก็ใช้ cgroup เหมือนกัน แต่ผมเดาว่าน่าจะ overhead น้อยกว่า docker

(ผมไม่ได้เช็ค fact ตรงนี้นะ ไปค้นดูละเอียดๆ เองดูก่อนถ้าจะลองทำดู)

หรือจะใช้วิธีดิบเถื่อนรันไปตรงๆ เลยก็ได้ ซึ่งผมเดาว่ารุ่นพี่คงจะใช้กันเพราะมันเขียนง่ายดี แต่อาศัยความเชื่อใจว่าจะไม่มีใครส่งอะไรน่ากลัวเข้าไปในระบบ ยิ่งบางทีไม่ได้เขียน time limit ไว้ด้วย ส่ง infinite loop เข้าไปก็เรียบร้อย

ผมคิดไว้ทีนึงว่าวิธีนึงที่ทำให้มันเร็วขึ้นคือรัน docker แช่ไว้เลยแล้วข้างในมีโปรแกรมที่เขียนในภาษานั้นๆ แล้วข้างนอกแค่บอกให้รันโค้ด ซึ่งมันจะตัด overhead เรื่องการ start, stop ตัว docker และ runtime ของภาษานั้นๆ ไปได้พอสมควรเลย แต่ข้อเสียคือเรื่อง memory leak และการ limit ต่างๆ จะทำได้ยากกว่า ใน source ของ grader จะมีคลาส EnhancedJava อยู่ซึ่งผมก็ใช้หลักการตรงนี้ แต่เขียนไม่เสร็จเพราะเขียนๆ ไปแล้วนึกถึงเรื่องการจับ limit นี่แหละแล้วคิดว่าเลิกทำดีกว่า ให้ผมคุมเองน่าจะมีปัญหา security ตามมาแหงๆ

Codejam Qualification Round 2014

โค้ดแจมปีนี้โจทย์ชักจะยากขึ้นเรื่อยๆ ครับ (ผมยังติดใจความง่ายของ 2011 อยู่เลยเนี่ย)

ปีนี้ผมดันทำ A เสร็จแล้วไปลุย C เลย ปรากฏว่าไม่ผ่านแล้วหมดแรงอยู่ตรงนั้น กว่าจะกลับมาทำ B ก็ห้าทุ่ม -_-‘ (ผมเองรู้สึกว่าผม burnout มาสักพักแล้ว ไม่ได้โค้ดแบบจริงจังมาสักสามสี่วันได้ หลังจากจัดเกมงูไปยาวๆ)

โค้ดปีนี้ครับ (Gist มันแยกไฟล์ไม่ได้ ผมลืมไปว่าต้องโพสต์แยกกัน)

A

ข้อ A ใช้วิธีง่ายๆ ครับคือหา intersect มา แล้วดูว่ามีกี่ตัว ถ้ามีตัวเดียวก็ตอบตัวนั้นเลย

B

ข้อ B ผมเสียเวลาบั๊กไปหลายพักเพราะคำนวณ timeToTargetIfFarm ผิด ลืมคิดเวลาเก็บเงินซื้อฟาร์มไป (และมีคิดติดลบด้วย) พอแก้เติม max(0, cookie-farm) ไปให้ถูก และ timeToTargetIfFarm += timeToNextFarm ก็เรียบร้อย ผ่านไปถึง B-large เลย

C

ข้อ C ผมใช้วิธีถมดำแล้วถมขาวจากซ้ายบนเอา โดยคิดเอาว่าต้องถมกี่แถวแล้วลองถมดู เช็คคำตอบด้วยการจิ้มซ้ายบนสุดแล้วหาว่ามีจุดที่ไม่ได้เปิดมั้ย ถ้าไม่มีก็ตอบ แต่ผิด ไม่รู้ผิดอะไรเหมือนกัน :/

D

ข้อ D โจทย์ยาวมากครับ และมันไม่ได้ให้วิธีคิดมาด้วย ผมเองไม่ถนัดโจทย์แนวๆ optimization/game theory เลยเลยข้ามไปเลยแล้วกัน

จริงๆ ข้อ B ถ้าเป็นปีก่อนๆ ผมคงจะข้ามไปด้วย แต่ปีนีั้เห็นหลายคนทำแล้วเลยว่าจะทำมั่ง และ grader ผมเองเคยออกโจทย์แนวๆ นี้เหมือนกัน (แต่เป็น int หมด) เลยเอาวิธีคิดเดียวกับข้อที่ตัวเองออกมาใช้

-qv