JMK 트레이더 레벨 1. 스킬포인트 뭐찍지?

새 파이썬 대몬 아키텍처

• 일단 채점 서버 자체를 EC2 위에 올릴 순 없다. 외부 모니터링도 문제가 되고, 멀티 서버 돌릴 때 (그 날이 과연 오긴 올까)
• 아마존 EC2 쓰면 스케일링이 쉬워진다. 그냥 서버 더 열어달라고 하면 됨~ :-) 인스턴스간에 CPU 파워가 대략 일정하니 time limit consistency 문제도 어느정도 해결된다.
• 원래 생각했던 것처럼 채점서버별로 스레드를 하나씩 돌려서 producer-consumer 모델로 구현. 단 GIL 이 무서우니 multiprocessing 패키지를 써서 별개의 프로세스로.
• SQLite 에 멀티프로세스에서 액세스하면 매우 귀찮음. (그렇다고 MySQL 쓰긴 싫다 -_ -;) 그냥 db 접근하는 것은 메인 프로세스로 한정하자.
• Notification 프로세스는 지금과 같은 형태로. 3번 연속 실패하면 3분 쉬었다가 다시 하는 식.
• 로깅에 이메일 보내주는 기능을 추가해서, 1) 서버가 맛이 가서 재부팅했다 2) 웹서버 접근에 실패했다 등등의 오류가 발생했을 때 나한테 이메일 보내는 것으로.. 'ㅅ'

채점서버 프로세스는:

1. 큐에서 작업을 받는다
2. 아마존에 소스코드 보내서 컴파일 & 실행. 시간 제한 + 5초가 흐르도록 답이 없으면 인스턴스 강제 리셋하고 런타임 에러 보낸다.
3. 서버가 시작된지 55분이 되면 마지막 20분 동안 서브미션이 없었나 확인하고 없으면 서버

이걸 위해 할 수 있어야 하는 일은

1. EBS Snapshot 으로부터 새 인스턴스를 얻고 핸들을 반환받음
2. 인스턴스에 원격으로 명령 내려서 실행 / 결과 넘겨받기 (이거 그냥 ssh 로 해서 표준출력 받아와야 하나.. 사실 그게 제일 간단하긴 함...)
3. 인스턴스 리셋

이런걸 하려면 Python API 를 쓰면 좋으나.. 버전 따라가기도 귀찮고.. 그냥 아마존에서 나오는 커맨드라인 유틸리티를 쓴다. 스냅샷 내에는 이런 스크립트를 만들어 둬야겠군:

1. 답안 번호, 문제번호를 넘겨받고 웹서버에 접근해서 소스코드와 채점 데이터, 채점 스크립트를 가져옴 (30초 갭을 두고 3회 연속 실패시에는 별도의 오류 결과로 끝)
2. 알아서 적당히 잘 컴파일 해주는 스크립트
3. 알아서 잘 실행해 주고 채점해 주는 스크립트

EBS Snapshot 을 만들 때는

1. 프로그램 실행하는 데 사용할 계정 만들고 (가능하면 chroot jail 에 넣음)
2. 각종 컴파일러 깔아두고
3. 해당 사용자에게 네트워크 액세스 막고...

이렇게 하면 좀 되려나?

Online judging with Amazon EC2

AOJ 에 해야 하는 수많은 작업들의 탑 리스트에 있는 것이 다른 언어의 지원이다. 딴건 다 그렇다 치고, 자바와 파이썬 정도만 지원할 수 있어도 potential user pool 이 훨씬 늘어날 거라고 생각하기 때문이다. (그전에 모의고사 문제나 좀 올려두던가...)

그런데 남의 프로그램을 받아다 내 컴퓨터에서 돌린다는 온라인 저지의 특성상 샌드박싱은 필수적이다. 지금은 제출된 프로그램을 띄운 뒤 부모 프로세스에서 메모리 사용량과 실행 시간을 감시하고, ptrace 를 이용해 시스템콜을 가로채는 방식으로 프로그램을 검증하고 있다. 그런데, 컴파일되는 언어들이라면 모르겠지만 VM 위에서 돌아가는 언어를 이런 식으로 검증할 수는 없다. 하지만 현실의 대세는 결국 VM 위에서 돌아가는 언어이니 지원 안할 수도 없다. 그런데, 이런 저런 방법들을 고민해 봤지만 지원하고자 하는 수많은 언어들을 한번에 지원하는 것도 힘들다. 결국 가상머신이라도 써야 하나 헐퀴 이러고 있었는데, 오늘 생각해 보니 왜 아마존 EC2 를 쓸 생각을 안하고 있었나 싶더라.

아마존 EC2 는 가상화 서비스들 중에서도 모든 것이 클라우드 위에 올라가 있다는 점에서 특이한데, 이 말인즉 실행중인 서버 인스턴스들이 특정 서버에 할당되지 않고 클라우드 위에서 시뮬레이션 된다는 뜻이다. (대개의 가상화 솔루션들 - 각종 vps 서비스들, 랙스페이스 클라우드 등은 특정 서버 위에서 돌아간다.) 반대로, 이 인스턴스들에 마운트된 디스크들은 인스턴스가 종료되면 사라져 버린다. 대개는 이런 non-persistence 가 굉장히 귀찮은 요소가 되지만, 우리 용도로는 오히려 매우 적당하다.

chroot jail 등의 최소한의 샌드박싱만을 추가해서 프로그램을 실행하고, 메모리 사용량 모니터링과 실행 시간 모니터링을 예전처럼 한다. 만약 프로그램도 종료하지 않고 샌드박스도 종료하지 않고, CPU 사용량 또한 감소하지 않는다면, 간단하게 VM 자체를 죽여 버리고 리스토어하면 된다. EBS 에 디스크 이미지 저장해 놨다가 여기에서 부트하면 리부팅하는 데도 시간이 별로 걸리지 않는다. (사실 이 기능이 12월에 추가된 걸 보고 이생각을 했따. ㅡㅡ;) 이미지는 오직 이 용도로만 사용할 테니, 악의적인 프로그램이 시스템을 장악한다고 하더라도 잃을 것도 없다. 더더욱이, 아무도 한 시간 동안 서브밋을 하지 않는다면 인스턴스를 죽여둬서 운영비를 절감할 수 있다는 장점까지 있다....

음.. 내가 이걸 왜 쓰냐면, 이렇게 포스팅 해두면 다음주엔 코딩 좀 하겠지 싶어서 써둔다. 후

Ninja Assassin

얼마만에 영화관에서 보는 영화인지. 보은이랑 벤옹이랑 넷이서 벤옹의 스폰싱으로 (!) 보고 왔다. 나는 진짜 아무 기대도 안하고 갔는데 의외로 재밌더군. 판타지였다. -_-

ACM ICPC 2009 Asia Wuhan Regional

요즘 #icpc 채널의 밤을 불태우고 있는 1주1셋운동의 첫번째 세트. 헤헷 난 멋있게 A번부터 풀어야지 하다가 A번 일주일 동안 못풀고, 마지막 날에 몇개 풀고 말았다. -_- 그런데 꽤나 못푼 것의 답을 들으니 배운 점이 많아서 정리해서 포스팅.

배운 점:

• solve by hand: 안 풀리면 일단 작은 예제를 손으로 풀어본다. 문제에 있는 예제도 풀어본다.
• decompose: 복잡한 조건을 분해해서 간단한 조건들의 집합으로 만들 수 있는지 본다.
• avoid premature optimization.

(more)

Malcolm Gladwell - Outliers, 그리고 내 기회들에 관한 이야기

아이폰용 킨들로 처음 읽은 책. 지난 토요일에 수열이랑 쇼핑하면서 뭐 기다리다가 심심해서 킨들 다운받고 샘플 다운받았는데 볼만하길래 샀다. 다른건 다 차치하고, 심심할 때 처음 꺼내드는 것이 핸드폰이다 보니 일 주일만에 다 읽었다. 뭐 분량이 많은 책은 아니지만.. (산지 한달째 방치되어 있는 New Ideas From Dead Economist 재개정판이 울고 있다.)

이 책의 요지는 한 마디로 말하자면 '성공한 사람들을 만드는 데는 그 자신의 재능과 태도도 중요하지만, 주어지는 기회와 문화적 환경이 큰 역할을 한다' 인 것 같다. 별다른 노력을 하지 않고도 이렇게 한 마디로 책을 정리할 수 있을 만큼 책 내용이 얕다. -_- 덕분에 뒷부분은 지루해져서 (뒤로 갈수록 일관성도 떨어지는 것 같고..) 휘휘 넘기면서 봤다. Dominic 이 'his argument doesn't have much substance' 라고 했는데 맞는 말인 듯도 하고. 큰 주장을 하나 갖고 온 다음에 여기에 어울리는 예들을 모아서 붙여 놓으면 이 책이 되는 셈이다.

그래도 초반은 볼만했는데, 한국의 PDI (Power-Distance Index) 와 대한항공의 사고들을 연관짓는 부분부터는 좀 신뢰성이 떨어지는 느낌. 그래도 그래.. 그시절에 항공사면 다 군인 출신들일 테니 완전 군대 분위기겠지.. 라고 생각하면서 봤는데, 여기 나오는 '한국의 subtle 한 대화의 예' 가 가관이다. 번역하자면:

과장: 어, 춥다, 출출하네.
[해석: 먹을 거나 마실거라도 좀 사지?]
김씨: 쏘주라도 한잔 할까요?
[해석: 제가 사드리겠습니다.]
과장: 아 괜찮아 신경쓰지 마.
[해석: 한번 더 사준다고 하면 먹을게.]
김씨: 배고프실텐데요, 한잔 하시죠.
[해석: 제가 꼭 사드리겠습니다.]
과장: 그럴까?
[해석: 그래, 그럼 내가 얻어먹지.]

.... Seriously, WTF? 여기에 과장도 KWACANG 이라고 써놨다. -__- 이 사람이 과연 무엇을 제대로 이해하고 이걸 써놓은 것인지에 대한.. 심각한.. 회의가.. 든다. ;; (80년대, 아니 90년대의 한국이 그랬을까? 아니 최소한 그래도 과장이 윗사람인데 사야 하는 것 아냐?;;;)

하여간 이 책의 신뢰도는 여기에서 이미 바닥났지만 놀랍게도 이 책이 포스팅까지 올라오게 된 이유는 (made it into the postings...) 그래도 이 주장 자체가 나한테도 꽤나 적용되기 때문이다. 얼마 전에 방명록에 후연이가 달아놓은 '공돌이는 공돌이 학교를 가야 하나 봐요' 라는 댓글에 '근데 내가 대전이나 포항을 갔으면 어떻게 됐을지 상상이 안돼' 라는 리플을 달다가 문득 내가 연대에 갔다는 것이 내 삶을 얼마나 바꿔놓았는 지를 다시금 생각하게 되었는데, 참, 생각하면 생각할수록 놀랍다.

고등학교 때까지 나는 컴퓨터를 하겠다는 의지는 투철하지만 제대로 혼자 공부하는 방법을 한번도 안 적이 없었다. 학원을 다닌 것도 아니고, 인터넷이랑 책을 혼자 보는 게 전부였다. USACO 도 모르고 uva 도 모르고, 1년에 프로그램을 짜서 채점받는 일이 대회 때가 유일하니 하드디스크엔 예제만 돌아가는 소스코드가 수북.. 이건 뭐 잘할 수가 없다. 그래서 고등학교 때의 수상 성적은 유진이형 말대로 표현하자면 JB 이다. -_-

근데 놀랍게도 내가 연대에 붙은것이다. -_-; 알고 보니 놀랍고도 놀랍게도 평소에는 한 많아야 여섯 일곱명 정도 뽑던 연대 수시가 02학번에는 스무명을 뽑았다. -_-; 다음 학번부터는 다시 다섯명 정도로 돌아갔고, 나보다 수상 성적 안좋은 친구들이 별로 없었으니 이건 진짜 앞사람 등 꾹꾹 눌러서 집어넣고 나도 들어간 다음에 문닫은 케이스라고 할 수 있다. 3등급이 미달나서 의대가는 느낌이 이럴까? -_-

여기까지만 해도 난 이미 죽도록 운좋은 케이스다. 그런데 입학해 보니까 여기는 당시 학교 중에서 거의 유일하게 컴퓨터 특기자 모임과 ACM ICPC 준비 모임이 활성화되어 있다. 24시간 열려있는 정보특기자용 동아리방에는 개인이 할당받아 관리하고 쓸 수 있는 컴퓨터들이 득시글거리고, 난 집에서 마을 버스 한번 타면 학교에 올 수 있다. 일 주일에 한번씩 모여서 단체로 문제를 풀고 토론을 한다. (나 이런거 태어나서 첨해봤다.) 그러니 죽도록 밤새면서 코딩했다. 1학년 여름에 무슨 문제 하나 맞겠다고 동건이랑 컴실에서 밤새던 기억이 생생하다. 문제 풀다가 밤 열한시에 아침나무 가서 저녁먹고.. 헐.

그러고 나니 성적이 잘 나와서 어찌어찌 대표팀이 되었다. 이 때까지는 (아직 벤처 붐의 기운이 남아 있어서인지) 학교가 외국 대회 진출에 드는 비용까지 지원해 줬다. 그것도 두 팀이나! 덕분에 필리핀 대회도 다녀올 수 있었다. (지금은 우리학교를 포함한 많은 학교들이 일부/전부 자비로 원정을 다녀온다. 학교에서 다 지원해 주는 곳은 숭실대 정도?)

음.. 우리 팀의 당시 전력은 성훈이형 50% 유진이형 30% 나 20% 정도.. 라고 생각된다. -_-; 하여간 다년간 ACM 준비를 해 온 성훈이형의 경험이 있었기에 월파 진출을 어느정도 바라볼 수 있는 상황. 그런데 대전 대회에서 마지막 DP 문제 테스트 케이스가 틀린 점이 있어서 모든 팀들이 돌돌돌 말렸다. 그런데 우리는 당시 max flow 로 풀어야 했던 모 문제를 그리디로 당당하게 30분만에 맞아버린 -_-; 페널티가 있어서 월드파이널에 올라갈 수 있었다. 덕분에, 그 겨울을 하루에 12시간씩 코딩하며 보내게 된다. 이것만 쳐도 세달 가까이 12시간씩 했으니 1000시간이 가뿐히 넘는다. 사실 이 때 월파에 못 갔다면? 겨울에 죽도록 공부하지 않았을 테고, 그럼 성훈이 형이 은퇴한 뒤인 다음 해에도 월파를 못 갔을 테고, 그럼 그 다음 해에도 못 가고, 결국 병특을 갔겠지. -_-; 생각해 보면 죽도록 운이 좋았다.

물론 월파에서 좋은 성적을 올린 것은 아니지만, 월파에 다녀온 다음의 나는 모티베이션에 활활 불타고 있었다. 1년이고 2년이고 희생해서 탑에서 싸우고 싶다!!!! 이런 욕망에 사로잡혀 있달까. 덕분에 2학년도 송두리째 공부하는 데 보냈다. 해외 원정도 가지 않았지만, 안정적으로 서울 대회에서도 적당히 좋은 성적을 올려서 월파 티켓도 획득했다. 그리고 또 한번의 1000시간이 지나가고. 2년이 지난 후의 나는 예전과 전혀 달랐다. Problem solver 로도, 프로그래머로도 mediocre 했던 과거와 달리 자신감도, 경험도 생겼다. 여기에서 시작된 성장의 길은 비교적 그럭저럭 어느정도 (...) 계속되었고, 앞으로도 계속될 거라고 생각한다.

이 수많은 일들이 어디까지나 적절한 타이밍과 기회들로 인해 생겨났다는 것을 생각하면 참 놀랍다. 내가 만약 고등학교때 좀 더 잘해서 S모 던전이나 K모 던전에 갔다면, 득시글거리는 괴물들에게 겁을 먹고 레벨업을 할 시도조차 하지 못했을 거다. 만약 내가 1학년 때 월드파이널에 가지 못했다면, 더 공부하는 데 필요한 자신감과 의욕을 얻지 못했을 거다. 만약 정보특기자 컴퓨터실이 없었다면, 만약 선배들이 없었다면, 만약 nhn 에서 다른 팀에 떨어졌다면... 리스트는 끝도 없다.

내게 주어진 수많은 기회들에 대해 감사하고 싶단 생각이 들어서, 이 포스팅을 한다. 고맙습니다.

Windows 7 Upgrade

지금 쓰는 데스크탑에는 윈도우 비스타가 깔려 왔고, 윈도 7 이 나오면 무료 업그레이드를 해준다고 해서 샀다. 근데 업그레이드를 신청한지 2주일이 지나도 오기는 커녕 배송 소식도 없고, 메일을 보내니 "we will get back to you in 10 business days" 랜다. 이런 미친... -_-;

오늘의 삽질 정리

• jailkit 으로 chroot jail 을 적절히 만든다.
• sandbox 에서 적절한 시점에 해당 jail 안으로 chroot. 이 때 chroot 관련 일들을 하려면 root permission 이 필요하니, fakechroot 를 쓴다.
• 파일 액세스는 막지 않는다.
• 실행이 끝날때마다 mirrordir 같은 유틸리티로 jail 안을 완전히 정리한다.

.. 이런 걸 하고 있다가 plash 를 발견. 우워워워워어어어어어!!

BoA - Bump Bump

아 오피셜 보아 빠 ㅠ 근데 정지영상 프리뷰 완전 굴욕 ㅋㅋ

SRM438 연습

이전에 fail fail fail 한 패망의 매치. 돌아보았는데 여전히 틀림 [....] 나는 갈길이 멀었단 것을 깨달았다. -_-; IntelliJ 에서 각종 오버라이딩 코드나 constructor 를 자동으로 짜 주니까 코드를 좀 오버엔지니어링 하게 되는 감이 있는데.. 좀 잘 밸런스를 맞춰봐야 할 듯.. ㅠㅠ

(more)

정수론 공부하기

정수론은 솔직히 내가 살면서 탑코더 외에서 쓸 일이 없어서 공부를 잘 안하게 된다. [....] 사실 그래서 만인의 상식이어야 할 extended Euclid 따위도 필요할 때 찾아보지 않으면 모르고.. 그런 김에 위키피디아에서 의미있을 만한 정리를 긁어모아보려고 하는데 뭐가 있을까요? (제대로 공부하려면 concrete mathematics 라도 봐야하겠지만 아엉)

아래는 생각나는 대로.

• Euler's Theorem: a 와 n 이 coprime 일 때, a^phi(n) = 1 (mod n). phi() 는 Euler's totient function.
• Chinese Remainder Theorem: pairwise coprime 인 정수들의 벡터 n_i 와, a_j < n_j for all j 인 nonnegative 정수 벡터 a_i 가 있을 때, x_j % n_j = a_j 인 a_j 를 찾는다.
• Extended Euclidean Algorithm
• Lucas' Theorem: p 가 소수일 때, 이항계수 (m,n) 을 매우 큰 m,n 에 대해 빠르게 찾기.

다른 것 추천 좀 해주세요~ ㅠ

SRM439 연습

역주행중. 옛날에 2등했던 셋. 역시 하드는 못풀음 ... ㅠ 아이디어는 생각해 보면 단순한데. 일단 leave 들을 몽땅 지울 수 있다고 생각한 것이 문제였다. -.-; medium 은 당시에 c&p 신공 레코드였는데.. 그냥 짜봤는데 점수가 비교적 잘 나왔다. 호홍! hashCode() 랑 equals() 짜주는거 대단히 편하다. 'ㅅ'

(more)