파일 전체 메모리 적재 한계와 외부 병합 정렬
100GB 파일을 1GB 메모리로 정렬하려면 전체를 배열로 읽을 수 없습니다. 메모리에 맞는 묶음을 읽어 정렬한 임시 파일을 만들고, 각 파일이 이미 정렬돼 있다는 성질을 이용해 병합할 수 있습니다. 정렬된 연속 입력 묶음을 run이라고 부릅니다.
예산 1GB를 모두 레코드에 쓰면 안 됩니다. 정렬 도구의 보조 공간·디코딩 객체·입력 및 출력 버퍼·메타데이터도 포함해야 합니다. 실제 run 크기는 그만큼 작아질 수 있습니다. 큰 레코드 하나가 예산을 넘는 경우의 거절·별도 처리도 정합니다.
파일 전체를 메모리에 넣을 수 없는 정렬에서는 메모리 예산이 곧 알고리즘의 경계가 됩니다. 이 경계에서 run과 병합 후보가 어떤 순서로 이동하는지, 그리고 결과 파일을 언제 완성본으로 인정할지를 한 번에 추적해야 성능 수치와 복구 설계를 함께 판단할 수 있습니다.
작은 예를 실제 버퍼 상태로 따라가면 경계가 선명해집니다. 메모리 예산이 레코드 세 개이고 입력이 [7,2,5,1,8,3,6,4]라면 먼저 R0=[2,5,7]을 완성한 뒤에야 다음 묶음을 읽을 수 있습니다. 병합에서 힙이 (1,R1),(2,R0),(4,R2)인 상태라면 1을 출력한 직후 R1만 읽어 (2,R0),(3,R1),(4,R2)로 바뀝니다. 이 trace를 계측할 때는 run 생성 peak bytes, 열린 입력 수, 단계별 read/write bytes, 중단 시 마지막 완료 run을 함께 기록합니다. 연습으로 출력 중간에 R1 읽기를 실패시키면 최종 이름의 파일은 생성하지 않고, 임시 출력과 입력 run을 보존한 채 재개 가능한 상태로 남아야 합니다.
메모리 적재 단위와 정렬 run 생성
메모리에 레코드 세 개만 올린다는 예에서 입력은 [7,2,5,1,8,3,6,4]입니다.
| 원본 묶음 | 정렬해서 저장한 run |
|---|---|
| 7,2,5 | R0=[2,5,7] |
| 1,8,3 | R1=[1,3,8] |
| 6,4 | R2=[4,6] |
이제 세 파일을 합쳐야 합니다. 각 파일에서 맨 앞 값만 읽으면 후보는 R0의 2, R1의 1, R2의 4입니다. 이 중 가장 작은 1을 결과에 씁니다. 다음에는 1을 꺼낸 R1에서만 다음 값 3을 읽습니다. 후보는 2, 3, 4로 바뀝니다.
이번에는 2를 출력하고 R0에서 5를 읽습니다. 후보는 5, 3, 4가 됩니다. 이 일을 반복하면 1부터 8까지 차례대로 출력할 수 있습니다. 후보의 최솟값을 매번 빠르게 고르기 위해 최소 힙을 사용합니다.
파일마다 앞 값 하나만 보아도 되는 이유는 이미 정렬해 두었기 때문입니다. R0의 첫 값이 2라면 그 뒤에는 2보다 작은 값이 없습니다. 다른 파일도 마찬가지입니다. 따라서 전체에서 가장 작은 남은 값은 반드시 어느 파일인가의 맨 앞에 있습니다.
그림을 글로 읽기
- R0 · R1 · R2: [2,5,7] · [1,3,8] · [4,6]
- 후보 최소 힙: 처음: (1,R1),(2,R0),(4,R2)
- 순차 출력 버퍼: 1 → 2 → 3 → …
- R0 · R1 · R2 → 후보 최소 힙: 각 앞 레코드
- 후보 최소 힙 → 순차 출력 버퍼: 최소 후보 출력
다중 병합의 슈도코드
mergeRuns(runs, temporaryOutput):
heap = empty min-heap
for run in runs:
record = bufferedReadNext(run)
if record exists:
heap.push((record.key, record.originalSequence, run.id, record))
while heap not empty:
key, sequence, runId, record = heap.pop_min()
bufferedWrite(temporaryOutput, record)
next = bufferedReadNext(runId)
if next exists:
heap.push((next.key, next.originalSequence, runId, next))
flush_and_validate_output()
mark_run_complete()
원래 입력의 순번을 보조 키로 저장하면 동점의 원래 순서를 run 경계를 넘어 보존하기 쉽습니다. 안정적으로 생성한 연속 run과 안정 병합 규칙을 일관되게 쓰는 다른 방법도 가능하지만, 임의 run 번호만 붙였다고 언제나 안정성이 생기지는 않습니다.
run k개를 병합하는 비교 비용은 N개 레코드에 대해 O(N log k)입니다. 실제 비용은 레코드 크기와 파일 읽기·쓰기에 크게 좌우됩니다. 힙 후보 하나에도 긴 문자열 키나 디코딩 메모리가 있을 수 있으므로 O(k)개라는 개수만으로 메모리 예산을 다 설명하지 못합니다.
fan-in 규모와 병합 단계·버퍼 예산
한 번에 병합할 입력 파일 수를 fan-in이라고 합니다. 임시 파일이 100개일 때 10개씩 합치면 첫 단계에서 10개가 남고, 다음 단계에서 최종 파일 하나가 됩니다. 4개씩 합치면 100→25→7→2→1로 네 단계가 필요합니다.
단계가 늘어나면 같은 데이터를 디스크에서 다시 읽고 다시 써야 합니다. 전체 데이터가 S바이트이고 각 단계에서 모두 읽고 쓴다면, 한 단계의 I/O는 약 2S바이트입니다. 100GB라면 병합 두 단계에 약 400GB, 네 단계에 약 800GB의 읽기와 쓰기가 발생하는 셈입니다. 처음 원본을 읽어 정렬된 임시 파일을 만드는 비용도 여기에 별도로 더해야 합니다.
그렇다고 100개를 무조건 한 번에 열면 좋을까요? 각 입력 파일에 읽기 버퍼가 필요하고, 출력 버퍼와 힙도 메모리를 사용합니다. 한 번에 합칠 파일 수는 다음 예산 안에서 정해야 합니다.
k * inputBufferBytes + outputBufferBytes
+ heapAndDecodedRecords + runtimeOverhead <= memoryBudget
k를 늘리면 입력 버퍼가 작아지거나 메모리·열린 파일 수가 늘어납니다. 작은 버퍼는 시스템 호출과 잘게 나뉜 I/O 비용을 키울 수 있습니다. 최종 출력을 바로 소비하는 경우 마지막 쓰기 비용이 달라질 수 있으므로 파이프라인 경계를 명시합니다.
| 확인 자원 | 놓치기 쉬운 항목 |
|---|---|
| 메모리 | 정렬 보조 공간, 각 run 후보, 문자열 디코딩 |
| 파일 핸들 | 입력 run k개 외 출력·로그·다른 앱 파일 |
| 디스크 | 기존 run과 새 출력의 동시 보유, 원본 보존 |
| I/O | 모든 병합 단계의 전체 읽기·쓰기 |
이미 정렬된 구간과 간접 정렬의 대가
입력에 긴 오름차순 run이 있으면 그대로 활용해 초기 정렬과 병합 단계를 줄일 수 있습니다. 그러나 무작위·교차 패턴에는 작은 run이 많아 탐지·관리 비용이 남습니다. 내림차순 run을 뒤집을 때 같은 키까지 함께 뒤집으면 안정성이 깨질 수 있습니다. 엄격한 감소 구간만 뒤집거나 원본 순번으로 동점을 보존합니다.
레코드가 매우 크면 (key, originalSequence, fileOffset)만 정렬할 수도 있습니다. 중간 데이터 이동은 줄지만 최종 순서대로 원본 레코드를 읽을 때 랜덤 I/O가 커질 수 있습니다. 원본 파일이 바뀌면 offset이 다른 내용을 가리키므로 파일 버전과 수명을 고정해야 합니다. 최종 재구성까지 포함한 총비용으로 비교합니다.
중단 출력과 완료 파일 공개 경계
새 run은 임시 이름으로 쓰고 레코드 수·정렬 기준 버전·체크섬·완료 상태를 기록합니다. 병합 출력이 완성되고 필요한 내구성 확인을 마치기 전에는 입력 run을 지우지 않습니다. 병합 중 프로세스가 멈추면 출력 파일 일부만 남을 수 있는데, 그 파일을 최종 이름으로 공개하면 독자가 완성된 결과와 중단된 결과를 구별할 수 없습니다.
원자 rename은 독자가 반쪽 파일을 보지 않게 하는 데 도움이 되지만 전원 장애 뒤에도 완료 상태가 남는다는 뜻은 아닙니다. 파일·디렉터리 fsync와 파일시스템 계약을 별도로 확인하고, 원본을 보존할지 어느 완료 run부터 재개할지 임시 파일을 언제 정리할지 정해야 합니다.
따라서 빈 파일·동점·큰 레코드·디스크 부족·쓰기 중단·완료 표시 전 중단을 넣어 봅니다. 결과가 정렬됐는지만 보지 말고 입력 다중집합과 동점 원본 순서도 대조해야 합니다. 파일 하나가 생겼다는 사실보다 검증된 완료 파일을 안전하게 공개했는지가 성공 기준입니다.