09-02. 정렬

Q. 저희 서비스는 매일 수십 기가바이트(GB)의 사용자 행동 로그를 생성합니다. 이 로그 데이터는 타임스탬프, 사용자 ID, 행동 유형 등 다양한 정보로 구성되어 있어요. 이제 이 로그 데이터를 타임스탬프 기준으로 정렬해야하는 요구사항이 생겼습니다. 어떤 정렬 알고리즘을 사용하시겠으며, 그 이유는 무엇인가요?

수십 GB의 대용량 로그 데이터를 처리해야 하므로, 메모리에 모든 데이터를 한 번에 올리기 어렵다는 점을 먼저 고려해야 합니다. 따라서 외부 정렬(External Sort)방식이 필요할 것 같습니다. 외부 정렬의 대표적인 예로는 병합 정렬(Merge Sort) 이 적합하다고 생각합니다.

병합 정렬은 데이터를 작은 청크로 나누어 메모리에 올리고 정렬한 후, 이 정렬된 청크들을 디스크에 저장하고 최종적으로 다시 병합하는 방식으로 동작하기 때문에 대용량 데이터 처리에 유리합니다. 또한, 병합 정렬은 O(NlogN)의 시간 복잡도를 항상 보장하며, 안정적인 정렬(Stable Sort)이라는 장점도 있습니다.

Q. 병합정렬을 어떤식으로 적용할지 구체적으로 말씀해주시겠어요?

먼저, 파일을 메모리 크기에 맞춰 여러 '작은 청크'로 나눕니다. 예를 들어, 1GB 메모리가 있다면 1GB씩 끊어서 읽는 식이죠. 각 청크를 메모리에 올린 다음, 퀵 정렬이나 힙 정렬 같은 인메모리 정렬 알고리즘으로 빠르게 정렬합니다. 이렇게 정렬된 청크들은 임시 파일로 디스크에 저장하고요. 이때 파일 시스템의 캐시나 버퍼를 잘 활용해서 디스크 I/O를 최소화해야 합니다.

다음 단계는 '다단계 병합'입니다. 디스크에 저장된 정렬된 임시 파일들을 한 번에 K개씩 읽어와 메모리에서 병합하고, 다시 새로운 임시 파일로 저장하는 과정을 반복합니다. 이때 우선순위 큐를 사용하면 각 파일에서 다음으로 읽을 데이터를 효율적으로 관리하며 병합 성능을 높일 수 있습니다. 이 과정을 계속 반복해서 최종적으로 모든 임시 파일이 하나의 정렬된 파일로 합쳐지게 됩니다.

이러한 과정에서 가장 큰 병목은 디스크 I/O에서 발생할 수 있습니다. 초기 분할 단계에서 데이터를 디스크에 쓰고, 다단계 병합 과정에서 여러 임시 파일들을 계속해서 읽고 쓰는 작업이 반복되기 때문입니다. 아무리 빠른 SSD를 사용하고 버퍼링을 최적화하더라도, CPU 연산 속도에 비하면 디스크 접근 속도는 훨씬 느려서 I/O가 전체 처리 시간의 대부분을 차지하게 될 가능성이 큽니다.

Q. 그렇다면 만약 이 요구사항이 실시간으로 들어오는 로그 스트림을 정렬해야 하는 상황으로 바뀐다면, 여전히 병합 정렬이 최선의 선택일까요? 아니라면 어떤 다른 데이터 구조나 알고리즘을 고려할 수 있을까요?

실시간으로 끊임없이 데이터가 들어오는 상황에서는 병합 정렬은 일반적으로 최선의 선택이 아닙니다. 병합 정렬은 데이터를 모아서 한 번에 처리하는 배치(Batch) 방식에 가깝기 때문에, 실시간으로 항상 정렬된 상태를 유지해야 하는 요구사항에는 잘 맞지 않습니다.

이런 실시간 스트림 처리 상황에서는 몇 가지 다른 접근 방식을 고려할 수 있어요.

첫 번째로, 우선순위 큐(Priority Queue)나 힙(Heap) 을 활용하는 방법입니다. 데이터가 들어올 때마다 우선순위 큐에 넣고, 필요할 때 가장 우선순위가 높은(예를 들어, 가장 오래된 타임스탬프) 데이터를 효율적으로 뽑아낼 수 있습니다. 이건 전체 스트림을 정렬하는 건 아니지만, 특정 시간 범위 내에서 가장 중요한 데이터를 빠르게 관리해야 할 때 유용하죠.

두 번째는 데이터베이스 색인(Indexing)를 활용하는 겁니다. 실시간으로 들어오는 로그를 데이터베이스에 쌓고, 타임스탬프 필드에 인덱스를 생성하는 거죠. 데이터베이스는 내부적으로 B-tree 같은 인덱스 구조를 사용해서 특정 기준으로 데이터를 아주 빠르게 조회하고 정렬된 결과를 줄 수 있습니다. Elasticsearch 같은 검색 엔진도 로그 분석이나 실시간 질의에 굉장히 강력한 도구가 될 수 있고요. 이 방법은 데이터를 '정렬된 상태로 계속 유지'하기보다는, '정렬된 결과를 빠르게 조회'하는 데 초점이 맞춰져 있습니다.