[시스템 디자인] top k 문제

---

수천만 트래픽에서 실시간 인기 순위(Top K)를 구하는 방법

참고: https://www.youtube.com/watch?v=kx-XDoPjoHw&t=937s

유튜브의 실시간 인기 급상승 동영상, 트위터의 실시간 트렌드, 이커머스의 가장 많이 검색된 상품. 우리가 매일 사용하는 서비스들에는 무수히 쏟아지는 데이터 속에서 가장 많이 발생한 항목 K개를 뽑아내는 ‘Top K’ 기능이 존재합니다.

데이터가 적을 때는 DB에서 그룹화하고 정렬해서 상위 몇 개만 가져오면 끝나는 단순한 문제입니다. 하지만 초당 수십만 건의 이벤트가 발생하고 고유한 상품의 개수가 수천만 개에 달하는 스트림 데이터 환경이라면 이야기가 다릅니다.

무한한 데이터와 유한한 서버 자원 사이에서 어떻게 아키텍처를 진화시켜야 할지, 하나씩 단계별로 사고를 확장해 봅시다.

1. 만약 한 대의 서버에서 구현해야 한다면 어떻게 할 수 있을까요?

자료구조를 떠올려 봅시다. 이건 아마 알고리즘 문제로 치자면 Easy 정도의 난이도일 겁니다.

가장 직관적인 방법은 해시맵(HashMap)을 사용해 각 상품 ID를 키로, 등장 횟수를 값으로 카운트하는 것입니다. 그리고 크기가 K인 최소 힙(Min-Heap)을 메모리에 함께 띄워둡니다.

# 단일 서버에서의 Top K 구현 개념도
frequency_map = {}  # 상품별 빈도수를 저장할 해시맵
top_k_heap = []     # 상위 K개를 유지할 최소 힙

def process_event(item_id):
# 1. 해시맵 카운트 증가
frequency_map[item_id] = frequency_map.get(item_id, 0) + 1

    # 2. 최소 힙 업데이트 (상위 K개만 유지)
    update_min_heap(top_k_heap, item_id, frequency_map[item_id])

해시맵의 카운트가 업데이트될 때마다 힙의 최솟값과 비교하여, 더 큰 빈도수를 가진 상품이 등장하면 힙의 원소를 교체하면 됩니다.

하지만 이 방법은 트래픽이 기하급수적으로 늘어나면 곧바로 한계에 부딪힙니다. 들어오는 데이터의 종류(유니크 키)가 수백만, 수천만 개를 넘어가면 해시맵이 서버의 메모리 용량을 초과해 결국 서버가 죽게 됩니다(OOM). 게다가 쏟아지는 트래픽을 한 대의 CPU가 순차적으로 처리하다 보니 연산 속도 자체가 병목이 됩니다.

2. 데이터가 너무 많아 한 대로는 무리입니다. 스케일아웃을 할 수는 없을까요?

서버 한 대가 버티지 못한다면 여러 대로 나누면 됩니다. 이벤트를 여러 서버로 분산시켜 병렬 처리를 하는 방식입니다.

그런데 여기서 데이터를 어떻게 나눌 것인지가 중요해집니다. 라운드 로빈 방식으로 데이터를 아무 서버나 순서대로 던져주면 안 됩니다. 상품 A에 대한 클릭 데이터가 1번 서버와 2번 서버로 제각각 흩어지면, 나중에 빈도를 합산하기가 매우 까다로워지기 때문입니다.

이를 해결하기 위해 카프카(Kafka) 같은 메시지 큐를 활용해 상품 ID를 기준으로 해싱(Hashing) 라우팅을 합니다.

[ 유저 클릭 이벤트 스트림 ]
│
▼
[ Kafka (상품 ID 기반 해시 라우팅) ]
/     │     \
▼      ▼      ▼
[서버 A]  [서버 B]  [서버 C]
(ID: 1)  (ID: 2)  (ID: 3)

상품 ID에 해시 함수를 적용해 무조건 특정 파티션(서버)으로만 데이터가 흘러가도록 만드는 겁니다. 이렇게 하면 1번 서버는 자신에게 할당된 상품 데이터들만 독립적으로 카운트하면 됩니다. 여러 서버가 동시에 일을 처리하니 처리 속도 문제는 깔끔하게 해결됩니다.

3. 속도는 해결했는데, 특정 서버에 할당된 유니크 상품의 종류가 여전히 수천만 개라면요?

맞습니다. 트래픽은 분산시켰지만, 근본적으로 모든 유니크 키를 메모리에 저장해서 세어야 한다는 해시맵의 한계는 그대로입니다. 메모리 크기를 아예 ‘고정’시켜버릴 방법은 없을까요?

이 지점에서 시스템 디자인의 묘미인 트레이드오프가 등장합니다. 정확도를 아주 조금 포기하는 대신, 메모리 사용량을 확정적으로 고정시키는 Count-Min Sketch라는 확률적 자료구조를 사용하는 겁니다.

원리는 이렇습니다. 고정된 가로, 세로 크기의 2차원 배열을 만듭니다. 데이터가 들어오면 서로 다른 해시 함수들을 돌려 배열의 여러 칸 값을 1씩 증가시킵니다.

# 특정 상품(ID: X)이 들어왔을 때 카운트 방식
해시 함수 1 (h1) -> [ 0 | 2 | 0 | 5 | 1 ]  -> 인덱스 3의 값 증가
해시 함수 2 (h2) -> [ 1 | 0 | 4 | 0 | 2 ]  -> 인덱스 2의 값 증가
해시 함수 3 (h3) -> [ 0 | 3 | 1 | 0 | 0 ]  -> 인덱스 1의 값 증가

* 상품 X의 최종 빈도수 = Min(5, 4, 3) = 3

나중에 특정 상품의 빈도수를 알고 싶을 때는, 그 상품이 가리키는 배열 칸들의 값 중 가장 작은 값(Min)을 읽어오면 됩니다.

물론 한계도 있습니다. 해시 충돌 때문에 내 상품의 카운트가 다른 상품의 카운트와 겹쳐서 실제보다 높게 예측될 가능성이 있습니다. 하지만 최솟값을 취함으로써 이 오차를 크게 줄일 수 있고, 데이터가 수백억 건이 들어와도 메모리 사용량은 배열 크기만큼만 딱 고정되므로 서버 메모리가 터질 일은 절대 없습니다.

4. 정확도와 실시간성, 이 두 마리 토끼를 다 잡을 수는 없나요?

비즈니스 요구사항은 보통 까다롭습니다. 당장 눈에 보이는 실시간 트렌드도 중요하지만, 하루가 지나고 정산을 할 때는 해시 충돌 오차조차 없는 100% 정확한 데이터가 필요합니다.

이 딜레마를 해결하기 위해 대규모 데이터 처리에서는 람다 아키텍처(Lambda Architecture)라는 투트랙 전략을 주로 사용합니다.

                  ┌──> [ Fast Path ] ───────> 실시간 근사치 Top K
                  │    (Count-Min Sketch)
[ 원본 데이터 ] ──┤
│
└──> [ Slow Path ] ───────> 주기적/정확한 Top K (오차 덮어쓰기)
(Hadoop / Spark)

당장 서비스에 보여줄 실시간 데이터는 우리가 방금까지 설계한 빠른 경로(Fast Path)를 태웁니다. Count-Min Sketch를 활용해 초 단위, 분 단위로 근사치를 계산해 사용자에게 제공합니다. 약간의 오차가 있어도 트렌드를 파악하는 데는 무리가 없습니다.

동시에, 백그라운드에서는 원본 로그 데이터를 빠짐없이 하둡이나 S3 같은 분산 파일 시스템에 쌓아둡니다. 이 느린 경로(Slow Path)에서는 주기적으로 스파크(Spark)나 맵리듀스를 돌려 전체 데이터를 무식하지만 정확하게 정렬하고 계산합니다.

그리고 1시간이나 1일 단위로, 이 100% 정확한 배치 처리 결과로 실시간 쪽의 근사치 데이터를 덮어써서 오차를 보정해 줍니다.

Top K 문제는 쿼리를 어떻게 최적화할 것인가에 대한 고민이 아닙니다. 트래픽과 데이터의 규모가 커짐에 따라 메모리와 속도의 한계를 어떻게 극복할 것인지, 그리고 정확도와 실시간성 사이의 아슬아슬한 줄타기를 어떻게 해낼 것인지를 묻는 시스템 설계의 핵심입니다.