笔记本上没事，到了 Pod 就被杀

목표

큰 파일을 메모리에 올리지 않고 다루는 도구 stream.py 를 만들고, 메모리 상한을 걸어 그것이 정말로 스트리밍인지 종료 코드로 증명한다. 집계·상위 N·고유값 세기·외부 정렬·검증을 모두 손에 쥐는 것의 개수로 설계한다.

왜 중요한가

파일을 통째로 읽는 코드는 작은 파일에서 더 짧고 더 빠르다. 그래서 처음 쓸 때는 의심할 이유가 없고, 파일이 커지는 것은 우리가 아니라 고객이 결정한다. 컨테이너가 메모리 한도를 넘으면 커널이 프로세스를 죽이는데, 그 죽음은 파이썬 예외로 잡히지 않고 표준출력에도 아무것도 남지 않는다. 설계의 기준은 파일 크기가 아니라 어느 시점에도 손에 쥐고 있는 것의 개수다. 집계는 한 줄, 상위 N 건은 N 개면 된다. 그런데 고유값 세기는 스트리밍이어도 메모리가 값의 가짓수에 비례한다 — 이 차이를 모르면 "스트리밍으로 짰는데 왜 죽죠" 가 된다. 그리고 "돌려 봤더니 되던데요" 는 증명이 아니다. 그때 그 파일에서 됐다는 뜻일 뿐이다. 상한을 걸고 통과해야 증명이고, 그 결과는 문장이 아니라 종료 코드로 남아야 다음 사람이 다시 묻지 않는다. 채점기는 여러분의 문구를 믿지 않는다. 임시 디렉터리에 채점기가 만든 로그를 차려 놓고 여러분의 도구를 메모리 상한 아래에서 실제로 실행해 답을 대조한다. 건수와 금액은 실행마다 바뀐다.

단계

1. /root/stream/gen_events.py 를 만들어 실행해 /root/stream/data/events.csv 를 만드세요. 30만 줄입니다.
2. /root/stream/stream.py 에 agg <파일> 을 만들어 한 줄씩 읽어 건수·합계·평균·최소·최대를 내게 하세요.
3. top <파일> <N> 을 더해 힙으로 상위 N 건만 유지하게 하세요.
4. distinct <파일> <칼럼> 을 더해 고유값을 세고 그때의 최대 메모리를 함께 내게 한 뒤, 가짓수가 적은 칼럼과 많은 칼럼을 비교해 /root/stream/distinct.json 에 적으세요.
5. /root/stream/cap.py 와 /root/stream/slurp.py 를 만들어 메모리 상한 64MiB 아래에서 두 판을 나란히 돌리고 결과를 /root/stream/limit.json 에 적으세요.
6. sortmerge <파일> <칼럼> <청크행수> 를 더해 분할·정렬·병합으로 외부 정렬하게 하세요.
7. verify <파일> <칼럼> 을 더해 정렬 여부와 순서에 무관한 지문을 내게 하고, 원본과 정렬본을 대조해 /root/stream/verify.json 에 적으세요.
8. 전체를 한 장으로 정리해 /root/stream/stream_report.json 과 /root/stream/stream_report.md 를 만드세요.

참고

• 실행 계약: python3 /root/stream/stream.py <명령> <파일> [인자]. 명령은 agg·top·distinct·sortmerge·verify 다섯입니다. 성공하면 종료 코드 0, 파일이 없으면 3, 명령이나 인자 수가 틀리면 2 입니다.
• agg 응답: rows·sum_amount·mean_amount·min_amount·max_amount·peak_kib. 평균은 소수 둘째 자리에서 반올림합니다.
• peak_kib 는 그 프로세스가 쓴 최대 메모리이고 resource.getrusage(resource.RUSAGE_SELF).ru_maxrss 로 얻습니다. 리눅스에서 단위는 KiB 입니다.
• top 응답: {"n": 정수, "rows": [[event_id, amount], ...], "peak_kib": 정수}. 금액 내림차순이고, 금액이 같으면 event_id 가 큰 쪽이 위입니다.
• distinct 응답: column·rows·exact·peak_kib. sortmerge 응답: rows·chunks·chunk_rows·output·peak_kib. 청크는 입력 파일이 있는 디렉터리의 chunks/ 에 쓰고, 결과는 같은 디렉터리의 sorted.csv 에 머리글과 함께 씁니다.
• verify 응답: rows·ordered·sum_amount·digest·peak_kib. digest 는 머리글을 뺀 줄마다 sha256(줄 전체 바이트) 의 앞 8바이트를 정수로 읽어 전부 더한 값을 2의 64제곱으로 나눈 나머지이고, 16자리 소문자 16진수로 냅니다. 순서가 달라도 같은 값이 나와야 합니다.
• 정렬 키는 값이 정수 모양이면 (정수, 원래 문자열), 아니면 (0, 원래 문자열) 로 봅니다. 이 규칙은 이 실습의 가정입니다.
• python3 /root/stream/cap.py <MiB> <명령> [인자...] 는 그 명령을 주소 공간 상한 아래에서 돌리고 {"limit_mib": 정수, "argv": [...], "exit_code": 정수, "ok": true|false} 를 냅니다. cap.py 자신은 자식이 죽어도 0 으로 끝납니다.
• python3 /root/stream/slurp.py <파일> 은 파일을 통째로 읽어 리스트에 담는 판이고, 상한 아래에서 떨어지라고 만드는 대조군입니다.
• 공식 문서: heapq · resource · hashlib · POSIX sort
• 흔한 실수: read() 나 readlines() 로 시작하기, 전체를 정렬한 뒤 앞을 자르기, 검증하려고 원본과 결과를 둘 다 리스트에 올리기, 청크 파일을 안 지우기.
• 파드 자원은 CPU 2코어·메모리 2Gi·임시 디스크 6Gi 입니다. 더 큰 파일을 만들지 마세요.

한 번에 못 읽는 파일 만들기

/root/stream/gen_events.py 를 만들어 실행해 /root/stream/data/events.csv 를 만드세요. 머리글은 event_id,shop_id,kind,amount,ts 이고 30만 줄입니다.

만들 때도 리스트에 모으지 말고 한 줄씩 파일에 쓰세요. shop_id 는 가짓수가 적게, event_id 는 줄마다 다르게 만들어야 나중에 고유값 세기의 메모리 차이를 볼 수 있습니다.

한 줄씩 읽어 집계하기

/root/stream/stream.py 에 agg <파일> 을 만들어 rows·sum_amount·mean_amount·min_amount·max_amount·peak_kib 를 내게 하세요.

파일 객체를 그대로 for 문에 넣으면 한 줄씩 읽힙니다. read() 나 readlines() 를 부르는 순간 그 성질이 사라집니다. 최소·최대는 방금 읽은 값과 견주기만 하면 되고, 평균은 합계와 건수로 마지막에 냅니다.

상위 N 건만 손에 쥐기

top <파일> <N> 을 더해 금액 상위 N 건을 [[event_id, amount], ...] 로 내게 하세요. 금액 내림차순이고 금액이 같으면 event_id 가 큰 쪽이 위입니다.

전체를 정렬해 앞을 자르면 전체가 메모리에 올라갑니다. 크기 N 의 최소 힙을 두고, 힙이 N 개가 되면 새 값이 맨 밑보다 클 때만 밀어 넣으세요. heapq 의 heappushpop 이 한 번에 해 줍니다. 힙에 넣을 값은 (금액, event_id) 짝으로 두면 동점 처리까지 함께 됩니다.

고유값 세기의 메모리는 어디에 비례하나

distinct <파일> <칼럼> 을 더해 column·rows·exact·peak_kib 를 내게 하세요. 그리고 shop_id 와 event_id 두 칼럼의 결과를 /root/stream/distinct.json 에 rows·low·high 로 적으세요.

한 줄씩 읽어도 이미 본 값을 기억해야 하므로 메모리가 값의 가짓수에 비례합니다. 가짓수가 적은 칼럼과 줄마다 다른 칼럼을 각각 재어 보면 그 차이가 숫자로 보입니다. low 에는 가짓수가 적은 쪽, high 에는 많은 쪽 결과를 담으세요.

상한을 걸어 증명하기

/root/stream/cap.py 와 /root/stream/slurp.py 를 만들고, 상한 64MiB 아래에서 stream.py agg 와 slurp.py 를 각각 돌려 /root/stream/limit.json 에 limit_mib·file_bytes·rows·stream_exit·slurp_exit 를 적으세요.

리눅스에는 프로세스가 잡을 수 있는 주소 공간의 상한이 있고, 파이썬에서는 resource 모듈로 걸 수 있습니다. subprocess 로 자식을 띄울 때 자식 쪽에서 상한을 걸어야 부모가 함께 죽지 않습니다. cap.py 자신은 자식이 죽어도 0 으로 끝나고, 자식의 종료 코드를 JSON 으로 알려 주기만 합니다.

분할·정렬·병합으로 외부 정렬하기

sortmerge <파일> <칼럼> <청크행수> 를 더해 청크마다 정렬해 chunks/ 에 쓰고, 합쳐서 같은 디렉터리의 sorted.csv 에 머리글과 함께 쓰게 하세요. 응답은 rows·chunks·chunk_rows·output·peak_kib 입니다.

청크 행수만큼 모아 정렬해 파일로 내보내고 버퍼를 비우기를 반복합니다. 병합할 때는 청크 파일을 전부 열어 두되 각 파일에서 한 줄씩만 꺼내면 되고, heapq.merge 가 정렬 키를 받아 그 일을 해 줍니다. 이전에 만든 청크 파일은 시작할 때 지우세요 — 안 지우면 다음 실행에서 결과가 섞입니다.

중간 산출물 없이 검증하기

verify <파일> <칼럼> 을 더해 rows·ordered·sum_amount·digest·peak_kib 를 내게 하고, 원본과 정렬본을 대조해 /root/stream/verify.json 에 column·source·sorted·same_multiset 을 적으세요.

원본과 결과를 둘 다 리스트에 올려 비교하면 스트리밍으로 정렬한 보람이 사라집니다. 줄마다 해시를 내어 전부 더하면 순서가 달라도 같은 값이 나오고, 줄이 하나라도 빠지거나 겹치면 달라집니다. 정렬 여부는 직전 줄의 키만 기억하면 알 수 있습니다.

증명을 한 장으로 남기기

/root/stream/stream_report.json 에 file_bytes·rows·sum_amount·chunks·limit_mib·stream_exit·slurp_exit·digest_match 를 적고, /root/stream/stream_report.md 에 ## 무엇을 받았나 ## 어떻게 처리했나 ## 정말로 스트리밍인가 ## 남은 한계 네 절로 쓰세요.

앞 단계에서 남긴 limit.json 과 verify.json 과 distinct.json 을 읽어 합치면 됩니다. 보고서에는 상한 값과 두 종료 코드를 숫자로 적으세요 — 그것이 증명이고, 남은 한계 절에는 고유값 세기의 메모리가 가짓수에 비례한다는 사실을 적으세요.