최근 알고리즘 경진대회를 개최할 일이 있었다. 여기서 이런 저런 사정으로 직접 알고리즘 채점 시스템을 만들게 됐다. BOJ에서 대회를 열기에는 행정력이 감당할 수 있는 수준 이상으로 필요했고, DomJudge등을 쓰기에는 서브 테스크나 컴파일 로그 제공 등등의 커스텀 부분이 부족했다.

이 글에서는 25명 가량이 참가하는 알고리즘 대회 재점 프로그램을 만들때 고려하면 좋을 점에 대해 써보려고 한다.

공개 테스트 케이스는 다 돌려주자

한 문제에는 “공개 테스트 케이스”와 “비공개 테스트 케이스”가 존재한다. “공개 테스트 케이스”는 설명에서 제공하는 예시 입력에 해당된다. 우리는 채점을 두 단계에 나눠서 진행 했었다: 1) 공개 테스트 케이스 전체를 돌려 보고 2) 그게 다 맞으면 비공개 테스트 케이스를 돌려보는 순서다. 당연한 말이지만, 공개 테스트케이스를 한번이라도 실패했으면 비공개 테스트 케이스로 넘어갈 필요도 없다.

빡빡하게 굴 대회가 아니라면 공개 테스트 케이스는 다 돌려주고 각 TC의 1) 컴파일 로그, 2) 출력, 3) 메모리 사용량과 4) 실행 시간을 전부 제공해 주자. 어짜피 관건은 비공개 테스트 케이스이다.

정확한 채점을 원한다면 Bare Metal를 쓰자

우선 “대회 서버”와 “채점 워커(서버)”를 분리해서 생각할 필요가 있다. “대회 서버”는 MySQL, Postgres와 같은 DBMS와 웹 서비스가 동작하는 서버다. “채점 워커”는 사용자가 제출한 코드를 컴파일 하고 실행하는 서버이다. 대회 서버는 높은 정확성을 요구하진 않는다. 웹페이지 조금 느려지는 수준이다. 그러나 “채점 서버”는 상당한 정확성을 요구받는다. CPU-Sensitive한 프로그램이 동작하는 중에 방해를 받으면 실행 시간이 크게 차이날 수 있기 때문이다. 그렇기 때문에, 가능하면 독립 서버를 추구해야 한다.

우리 팀은 물리 서버를 딱 1개만 보유중이다. 그나마도 12Core 64GB의 내부 개발용이다. 이 서버에는 실 서비스가 돌아가고 있기 때문에 채점 실행 시간에 영향을 끼칠 가능성이 높았다. 그래서 별도의 서버를 찾게 됐다. 딱 3일을 위한 서버가 필요하게 됐다.

사실 이런식의 단기간 임대 서버는 비용적인 측면에서 Cloud 서버가 적합하다. 일반적인 서버 호스팅(임대)는 1달 단위로 진행되기 때문에 버려지는 돈이 많다. 하지만 위와 같이 정확도 문제에 있어서 문제가 생길 가능성이 있다. 그렇기 때문에 Cloud Hosting이 제공하는 Bare Metal 상품군을 선택했다.

필자가 운영중인 서비스는 전부 Cloud에 올라가 있다. 이들 서버에서는 심심치 않게 CPU Steal이 관측된다. 운영중인 서비스들은 수평 확장을 통해서 이를 극복하지만 위와 같이 참가자가 제출한 코드는 수평확장이 불가능 하다.
CPU Steal은 언제든 불현듯이 올라올 수 있고, 이로 인해서 프로그램 동작 시간에 방해가 될 수 있을거라 판단했다.

여기서 사용한 것이 오라클의 Bare Metal Shape이다. 우리는 BM.Standard2.52를 사용했다. 하루로 치면 10만원 꼴이다. 세팅을 위해 대회 전날부터 개통하여 대회 끝날때 까지 깔끔하게 20만원치를 사용했다.

놀라웠던 부분은 Oracle Cloud infrastructure는 Bare Metal 상품군에 아래와 같이 BIOS급의 설정이 가능하다는 부분이다. Hyper Thread를 끌 수는 없었지만, 여기서 SMT를 끌 수 있었다.

첫번째 “Provision only a percentage of cores and disable the reset”를 50%로 설정하여 Hyper-Thread를 제외한 효과를 얻을수 있지 않을까 싶기도 하다.

그러면 프로비전에 필요한 코어를 제외한 순수한 코어를 받을 수 있다. 이 중 0번, 1번 코어에 IRQ 같은거를 몰빵하고 나머지 코어를 사용하면 된다. 아쉽게도 리눅스 커널로는 Hyper-Thread를 끌 수 없다. 대신 위의 BIOS급 설정에서 SMT를 껏기 때문에 3, 5, 7 ···· 홀수 코어만 실행하면 HyperThread를 끈 효과를 얻을 수 있을거라 판단했다.

사실, 그렇게 빡빡하게 굴어야 할 대회가 아니라면 이정도 까지 Hyper-Thread에 얽메일 필요는 없을 것 같다.

채점시 “시간 초과”가 발생하면 큐가 마비된다

대회를 진행하면서 뼈저리게 느끼게 된 부분이다. 우리 같은 경우에는 수백~수천개의 비공개 TC(테스트 케이스)를 준비 했다. 그 중에는 시간 초과와 메모리 초과를 저격하기 위한 TC도 꽤나 있었다. 아니라 다를까, 해당 TC에서 대량으로 시간 초과가 발생했다.

문제는 “대회 서버”에서 “채점 서버”로 채점 정보를 넘길때 FIFO로만 스케쥴링을 해서 한번 “시간 초과” 코드를 만나면 큐 전체가 일정 시간 멈추는 영향이 있었다. “대회 서버” 입장에서는 이미 “채점 서버”로 스캐쥴링을 한 상태기 때문에 멈출수도 없었다. 그래서 꼼짝없이 해당 TC들이 Hard Time Limit에 도달할 때 까지 채점을 기다려야 했다.

그래서 지금와서 생각하기에는 “하나의 제출당 최대 8개의 병렬 처리만 가능”하도록 하고, 그 중 한번이라도 “시간 초과”가 발생하면 해당 제출의 큐를 싹 다 제거해야 할 것 같다. 그래야지 특정 제출이 “시간 초과”에 해당돼도 다른 제출이 영향을 덜 받는다.

출력 길이 제한도 고려하자

채점 서버는 1) 최대 메모리 제한과 2) 최대 실행시간의 두가지 제한만을 가지고 있었다. 원래는 3) 최대 출력 길이 제한도 있었긴 한데, stdout을 프로그램이 직접 받는 대신, 파일에 쓰게 하면서 이 부분을 제외 했다.

대회가 끝난 뒤 채점 결과 기록을 열어보니 특정 제출은 출력이 최대 50MB에 달했다. 50MB * 수십개의 TC로 인해서 3시간 짜리 대회에서 채점 기록이 무려 500MB에 달했다. 이는 관리 측면에서도, 성능 측면에서도 좋지 못한것 같으니 출력 길이에도 제한을 꼭 걸자.

우리의 경우에는 50MB에서 그쳐서 다행이지만, 만약 무한 루프로 계속해서 더미 데이터를 쏟아냈다면 I/O가 부족해서 전체적인 프로그램의 실행 시간에 영향이 왔을수도 있을것 같다.

참고로, 채점 서버의 경우 혹시 IO 처리량이 부족해서 프로그램 실행 시간에 영향이 갈까봐 RamFS를 이용하여 입력·출력 파일 처리를 했다.
(최대 입력 항목수를 체크하기 위해) 한 문제에 30MB짜리 테스트 케이스가 두어개 있었는데, OCI의 기본 Boot Volume의 I/O Throughput이 22.56MB/s 정도라 해서 (추가비용을 내기 싫어서) RamFS를 적용했다

“단순 입출력 비교” 모드와 “소수점 비교” 모드가 필요하다

필자는 사실 알고리즘 경진대회를 주최한 경험이 없다. 그래서 간과했던 부분이 “소수점 답안”의 처리였다. 프로그램 출력 결과가 늘 똑같으면 문제가 없다. 하지만 소수점을 출력하는 프로그램의 경우 “소수점 6번째 자리 까지”등의 언급이 나온다.

물론, 소수점 비교 추가 구현 자체는 얼마 걸리지 않았다. 그러나 기존에 생각지도 못했던 기능이 추가된 것이기 때문에 코드가 좀 더러워졌다. 미 문제 출제자와 이야기 해서 “소수점 모드”가 필요한지 알아보자.

---

이제는 운영에 관한 부분이다.

NxFilter를 이용해서 잠시 네트워크를 차단하자

이번 경진대회는 인터넷은 허용하지만 ChatGPT, Bard, Bing과 같은 “AI 서비스는 불가”하도록 했다. 짜피 문제를 인터넷에 바로 검색한다고 해서 바로 나오는 것도 없다. 검색해서 바로 결과가 나오게 문제를 출제했다면 그게 문제이다. 또한 인터넷이 돼야지 공식 Document나 기본적인 아이디어를 검색할 수 있다.

이때 사용한 것이 NxFilter이다. NxFilter는 Blacklist, Whitelist, 그리고 쿼리 로깅을 지원하는 DNS 서버이다. IP 단위로 DNS서버의 접근 통제도 가능하기 때문에 특정 PC에서만 접속하도록 제한할 수 있다. 또한 DNS 기록을 통해서 사용자들이 무슨 사이트에 들어가는지 모니터링 할 수도 있다. 이를 통해서 최소한의 모니터링 인원으로 전반적인 모니터링이 가능하다

대회를 주최해 보니까, 다들 서로 풀기 바빠서 인터넷 검색도 거의 안했다. 처음에는 다들 인터넷을 풀어놓으면 “검색 잘 하는 사람이 승리하는 대회”가 되지 않을까 했는데, 이거는 기우에 가까웠다.
물론, 문제의 질이 떨어지면 그럴수도 있겠지만, 왠만큼 말로 풀어낸 문제의 경우에는 통하지 않는다.

접속 차단 뿐 아니라, 제한된 컴퓨터에서만 “대회 서버” 접속이 가능하게도 할 수 있다. DNS Redirection을 통해서 특정 쿼리가 오면 지정된 IP가 나오게 하면 된다. 이번 대회에서는 contest.com에 접속하면 대회 서버가 나오도록 설정했다.

NxFilter를 이용하면 1) 특정 컴퓨터에서만 대회 서버에 접속할 수 있고, 2) AI 서비스는 막으면서 3) 혹시 모를 부정행위를 모니터링 할 수 있는 좋은 방법을 찾을 수 있다.

그리고 당연한 것들

IDE, 컴파일러를 세팅할 수 있는 시간을 주자. 시험 주관기관이 IDE나 컴파일러 까지 책임지는것은 힘들다. 그러므로 시험 시작전에 1시간 정도의 여유를 줘서 각자 알아서 프로그램을 설치하는 시간을 주자

상장은 다이소나 문구점에서 “상장용지”라고 판매한다. 어짜피 상장들이 모두 규격화 되어 있으니 골라 잡으면 된다. 다만에 필자는 우진산업의 상장을 구매해서 사용했다. 아래의 상장 포맷을 활용했기 때문에 양심상… 상장 포맷 사용비라고 생각하고 구매해 사용했다: https://woojin79.com/article/%EC%83%81%EC%9E%A5%EC%9D%B8%EC%87%84-%EA%B4%80%EB%A0%A8/1002/614/

상장은 꼭 현장에서 인쇄해 보자. 한글 2020에서는 “이미지 투명도 조정”이라는 옵션으로 배경에 로고를 박았는데, 프린터가 연결된 PC에서는 한글 2014밖에 없어서 자칫하다간 상장 배부에 문제가 생길 뻔 했다.

문제 출제자는 알고리즘 문제를 많이 풀어본 사람에게 부탁하자. 이번 대회에서는 gkswns3708 님이 문제 출제를 전담해 줘서 원할하게 대회를 진행할 수 있었다. 아마 이 분이 없었다면 대회의 근간 자체가 흔들렸을것 같다.

처음에는 문제 출제에 별 생각을 하지 않았는데, 이번 대회를 해보고 생각이 엄청 바뀌었다. 문제 출제에는 생각보다 많은것들이 고려 돼야 한다. 난이도, 문항 처리 (알고리즘이 바로 드러나지 않도록), 테스트 케이스 준비, 시간 복잡도 저격 등등… 결국 문제가 대회의 질에 직접적으로 연관되기 때문에 꼭 전문가에게 부탁드리자.