이 글은 solved.ac 개발기 1: 학회에서 사용할 서비스 만들기에서 이어집니다.
학회에서 사용할 수 있을 만한 서비스가 드디어 완성되었습니다. 하지만 안타깝게도 서강대학교에는 PS를 잘하는 사람이 그렇게 많지 않습니다.
Theorem 1. 서강대학교 구성원만으로 BOJ 문제들에 난이도를 일관되게 많이 달기는 힘들다.
Lemma 1. 서강대학교에는 PS를 잘하는 사람이 그렇게 많지 않다.
Proof of lemma. 애초에 시프트부터가 PS를 못한다. ∎
Proof of theorem. By Lemma 1, it’s trivial. ∎
집단지성으로 난이도를 붙이려는 시도는 이렇게 무너지고 마나요? 아니죠, 집단이 충분히 커지면 괜찮아요.
기존에 짜여 있었던 갱신 로직은 단체 랭킹 페이지를 긁어와서 갱신하기 쉽도록 되어 있었고, 더구나 전체 유저를 스크레이핑할 경우 서비스 자체가 차단될 수도 있겠다고 생각했기에, 일단은 랭킹 페이지가 있는 단체들에 제공하면 좋겠다고 생각했습니다. 다른 많은 학교들과 함께 기여해 나가면 됩니다.
다만, 학회에서 쓸 거라고 생각했기에 신경쓰지 않은 부분이 많았습니다. 일단 전 포스트에서 언급했듯이 푼 문제 정보를 업데이트하는 속도가 초당 150문제밖에 되지 않았습니다.
오늘 기준으로 서강대학교 학생들이 맞은 문제 수를 전부 합히면 80,989문제입니다. 초당 150문제라면, 9분만에 처리할 수 있는 수준입니다. 갱신 주기가 1시간이라면 봐줄 수 있는 갱신 시간이죠.
하지만 여기에 맞은 문제 132,249개의 서울대학교가 추가된다면 어떨까요? 거기에 더해 다른 학교가 열 곳, 스무 곳 이상씩 추가된다면? 아마 업데이트 시간으로 1시간은 턱없이 부족할 겁니다. 분명히 갱신 시간을 더 줄일 수 있을 텐데, 줄일 구석은 어디에 있을까요?
갱신 시간
갱신 작업은 여러 개의 작은 작업들로 나눌 수 있습니다.
문제 리스트 스크레이핑해서 문제 목록 받아오기
→ 단체 랭킹 리스트 스크레이핑해서 유저 목록 받아오기
→ 유저 페이지 스크레이핑해서 맞은 문제 목록 받아오기
→ 맞은 문제 정보를 토대로 경험치 계산
→ 맞은 문제 정보를 solved.ac 서버로 전송
줄일 구간이 어떤 게 있을까 하고 각각 단계별로 걸리는 시간을 계산해봤습니다.
- 스크레이핑은 단체 랭킹이나 유저 페이지나, 1페이지당 1초를 넘기지 않았습니다(300ms~700ms). 다만 한 단체를 400명이라고 했을 때 단체 내의 모든 유저 페이지를 스크레이핑하는 건 약 3.6분 가량이 걸렸습니다.
- 특히 문제 목록 스크레이핑은 전체 문제 페이지가 160페이지 가량이다 보니, 전부 스크레이핑하는 데 약 1~2분 정도가 걸렸습니다.
- 경험치 계산도 오래 걸리지 않았습니다. 전체 문제 목록을 스크레이핑할 때 문제 난이도 정보도 solved.ac에서 가져왔기 때문입니다. 전체 문제 m개의 목록과 유저가 맞은 문제 n개의 목록은 모두 정렬된 상태였기 때문에, O(n + m)만에, 그리고 n이 충분히 작다면 O(n log m)만에 경험치를 계산할 수 있습니다. 2,000문제 가량을 맞은 제 유저 페이지를 기준으로, 경험치를 계산하는 데 겨우 13ms 가량이 걸렸습니다.
- 맞은 문제 정보 갱신은 생각보다 오래 걸렸습니다. 위에서 언급했듯이 초당 150문제를 처리할 수 있는데, 제 페이지의 경우 1350ms 가량이 걸렸습니다.
결국 한 번 업데이트하는 데 맞은 문제 정보 갱신과 유저 페이지 스크레이핑, 그리고 문제 목록 스크레이핑 순서로 많은 시간을 쓰고 있음을 알 수 있었습니다. 경험치를 계산하는 로직에서는 더 줄일 수 있는 게 딱히 보이지 않았습니다. 이걸 어떻게 줄일 수 있을까요?
문제 목록 스크레이핑
‘이건 줄일 수 있겠다!’고 생각한 것 중 가장 먼저 생각난 것은 문제 목록 스크레이핑이었습니다. BOJ에는 1만 6천개 가량으로 많은 문제들이 있지만, 그렇다고 해도 문제가 1시간 단위로 추가되거나 하지는 않기 때문이죠.
그래서 다소 시간이 걸리는 문제 스크레이핑은 사용자 수가 가장 적을 매일 오전 6시에만 하도록 했습니다.
이를 통해 일단 2분 가량을 아낄 수 있었습니다.
유저 페이지 스크레이핑
지난 1시간 동안 푼 문제가 없는데도 업데이트를 해야 할까요? 푼 문제가 없다면 업데이트하지 않아도 되지 않을까요?
유저 페이지 스크레이핑 시간을 줄이려면 유저 페이지 자체를 들어가지 않아야 합니다. 다행히도 유저 페이지를 들어가지 않고도 푼 문제 수가 변했는지 확인할 수 있습니다. 애초에 랭킹 페이지를 스크레이핑해 오기 때문인데요,
랭킹 페이지에는 다행히도 맞은 문제 수와 제출 수가 있습니다. 이를 서버에 캐싱해 두고, 변동이 있을 경우에만 유저 페이지에 직접 들어가서 스크레이핑합니다. 참고로 재채점 등으로 인해 맞은 문제 수가 줄어들 수도 있으므로 맞은 문제 수와 제출 수를 동시에 확인해야 해요.
BOJ가 가장 활성화되는 시간인 오후 12시~1시 사이에도, 서강대학교에서는 8% 이하의 유저만이 맞은 문제 수 또는 제출 수에 변화가 있었습니다. 이런 식으로 모든 유저가 항상 BOJ를 붙들고(?) 있진 않기 때문에, 이 방법을 적용하고 스크레이핑 시간을 현저히 줄일 수 있었습니다. 학교 당 12배 정도였습니다. 게다가 BOJ 서버에 전송하는 리퀘스트 수도 획기적으로 줄이는 효과를 누렸습니다.
맞은 문제 정보 갱신
가장 많은 시간이 걸렸던 맞은 문제 정보 갱신 로직도 시간을 줄일 수 있었습니다. DB에 수많은 레코드들을 업데이트하는 건 시간이 꽤 걸리므로, solved.ac에 저장된 맞은 문제 정보와 스크레이핑해온 맞은 문제 정보를 가져와서, 차이가 있는 것들만 DB에 넣어주도록 바꿨습니다.
유저 정보를 처음 가져올 때는 여전히 많은 시간이 걸렸지만, 한 명이 한 시간에 몇백 개의 문제를 풀 리가 없으므로 (과연?) 처음 유저 정보를 가져온 이후에는 푼 문제 수에 비해 엄청나게 적은 레코드를 업데이트하게 되어 갱신 시간이 상당히 줄어들게 되었습니다.
이 세 가지 방법을 적용했더니, 결과적으로 390명을 9분만에 처리하는 수준에서 8,000명을 평균적으로 5분만에 처리하는 수준까지 개선할 수 있었습니다. 처리 속도가 약 37배 빨라진 셈입니다. 이 방법을 적용하고 나서, 홍익대학교, 서울대학교, KAIST 등의 순서로 차례차례 학교를 등록해 나갔고 지금 현재 37개의 단체가 별 무리없이 갱신되고 있습니다.
하지만 현재 업데이트되는 사용자 규모는 10,000명 정도에 불과하고, BOJ 전체 유저는 16만 명 정도이므로 전체 사용자를 대상으로 갱신한다면 아마 이걸로도 부족할 것입니다. BOJ에 리퀘스트를 날리면서, 동시에 맞은 문제 차이를 계산하고, 동시에 solved.ac 서버에 업데이트하도록 백엔드를 파이프라인화시키는 것도 고려하고 있으나 애초에 서버의 vCPU 수가 2개밖에 안 되는지라 효과적일지는 모르겠네요..
여담으로, solved.ac 한 달 광고 수익은 제가 2,500원짜리 학식 라면을 꼭 5번 먹을 수 있을 정도에 불과해요. 저도 중학생 때 캐놓은 비트코인 같은 거라도 있었더라면 좋았겠네요 ㅠ
고려하지 못했던 것
그렇게 많은 학교를 추가하고 한동안 여러 기능들을 추가하면서 평화롭게(?) 지냈습니다. 모든 기능이 문제없이 잘 돌아가고 있었습니다. 근데 원래 모든 게 잘 돌아가면 어딘가 불안해집니다. 저만 그런가요?
아무튼 그렇게 매일 새벽까지 개발하고 늦잠 자고 아침강의도 없겠다 늦게 일어나고 하는 평화로운 나날을 보내고 있었습니다. 이런 메시지를 받기 전까지는요.
아니 대체 왜?
갑자기 로그인이 안 될 이유가 딱히 없는데 로그인이 안 된다고 합니다. 음 뭐지?
No space left on device라고 합니다. df 명령어로 남은 공간을 확인해봤는데 공간은 아직 많이 남아 있습니다. 진짜 뭐지??
구글링 끝에 알게 되었습니다. ext4 파일시스템에는 파일의 메타데이터를 저장하는 inode가 있는데, 이 수에 제한이 있다고 합니다. df -hi로 inode 사용량을 분석할 수 있습니다.
역시 inode 사용량이 가득 찼던 거였습니다. Inode가 가득 찼다는 건 파일을 엄청 많이 만들었다는 뜻이 될 거 같은데, 파일을 그렇게 많이 만든 적이 없었던 거 같은데 대체 어느 부분에서 이렇게 되었을까요?
바로 세션 정보들이었습니다. 세로로 긴 이미지 하나 보고 갑시다.
세션 파일이 몇백만 개나 있었습니다. 이 세션 파일들이 inode 개수를 다 잡아먹고 있었습니다.
불행 중 다행으로 PHP는 세션 핸들러를 직접 만드는 게 가능했습니다. 기존 세션 파일들을 전부 삭제하고, MySQL을 사용하는 세션 핸들러를 만들어 교체해 줬더니 세션들이 전부 DB에 저장되었고, inode 폭발 현상이 다시 일어나는 일은 없었습니다.
다음에 한가할 때는 프론트엔드를 짜면서 했던 고민들에 대해 이야기해 보고자 합니다. 최근 solved.ac에 제출된 난이도 의견 수가 12,000건을 넘겼습니다. 학회에서만 사용하려고 했는데 어쩌다 보니 여기까지 올 수 있게 되었습니다. 사이트에 관심 가져 주셔서 정말로 감사하고, 알고리즘 문제해결을 공부하는 사람들의 길잡이가 될 수 있는 좋은 커뮤니티 프로젝트가 되도록 노력을 아끼지 않겠습니다.
감사합니다!