실시간 트렌딩과 Top-K 집계

문제

트렌딩(trending) 은 「일정 시간 창 안에서 언급이 가장 많은 상위 N개」다. 「지금 뜨는 것」에는 늘 「최근 5분」, 「오늘」 같은 창이 붙는다. 그래서 단순 누적 카운트가 아니라 창이 밀리면서 오래된 수는 빠지는 카운트가 필요하고, 입력은 초당 수십만 건의 끝없는 스트림이다.

슬라이딩 창 카운터

창을 슬롯 m개로 나누고 슬롯 하나가 N분이면 창은 N × m분이다. N = 1, m = 5면 「최근 5분 합」을 1분마다 낸다.

구성	하는 일
슬롯 카운터	`Map<키, long[m]>`. 키마다 슬롯 배열을 둔다. 가장 흔한 연산이 「한 키의 모든 슬롯 합」이라 한 키의 값을 붙여 두는 배열이 지역성에 유리하다
창 전진	시간을 직접 보지 않는 링 버퍼다. 「합을 내고 한 칸 전진」을 부를 때마다 가장 오래된 슬롯을 비우고 그 자리에 새 수를 센다
순위	고정 크기 상위 N 목록. 갱신할 때 N위 밖은 버린다

자료구조를 스트림 엔진과 분리해 두면 단위 테스트가 쉽다. 「증가」와 「합산 후 전진」을 한 스레드가 정해진 순서로만 부르게 하면 락 없이도 동시성 문제가 사라진다. 백그라운드 스레드가 시계를 보고 창을 밀던 구현은 카운트가 손상되는 경쟁 조건이 있었고, 엔진이 주기적으로 넣어 주는 틱(tick) 메시지로 시간을 주입하자 사라졌다. 틱은 일반 메시지 뒤에 줄을 서므로 주기는 최선 노력이다.

3단 분산 집계

입력(병렬) → 키별 카운트 → 부분 순위 → 전역 순위(인스턴스 1개)
            키 기준 파티션   키 기준 파티션   전부 한곳으로

키별 카운트: 같은 단어는 늘 같은 인스턴스로 보낸다(키 기준 그루핑). 인스턴스마다 자기 카운터만 만지므로 동시성 코드가 필요 없다.
부분 순위: 각 인스턴스가 받은 키들의 상위 N만 추려 보낸다. MapReduce의 컴바이너처럼 마지막 단계로 가는 양을 줄인다.
전역 순위: 단일 인스턴스가 부분 순위들을 합쳐 최종 상위 N을 낸다.

예시는 Storm 토폴로지(스파우트 → 롤링 카운트 볼트 → 중간 순위 볼트 → 전체 순위 볼트)지만, 지금은 Flink·Kafka Streams·Spark Structured Streaming의 윈도 집계로 같은 일을 한다. 텀블링·슬라이딩·세션 창을 기본 제공하고, 처리 시각 대신 이벤트 시각으로 창을 나누며 늦게 온 이벤트는 워터마크로 다룬다.

「평소 일정 + 가끔 점프」 같은 모형을 정해 점프 크기를 추정하는 모수 방법은, 실제 전조가 작은 점프 뒤 큰 점프, 점진 상승처럼 제각각이라 모형 선택 자체가 어렵다.
비모수 방법은 과거에 트렌드가 된 주제와 안 된 주제의 활동 시계열을 예시로 두고, 새 주제의 최근 구간과 각 예시의 거리로 투표한다. 가중치는 exp(−γ · 거리), 「트렌드」 표의 합 ÷ 「비트렌드」 표의 합이 1보다 크면 트렌드로 판정한다. 가중 k-최근접 이웃과 같다. 소셜 네트워크의 행동은 복잡도가 낮아 전조 패턴이 몇 가지로 뭉친다는 것이 근거다.
평가에서 트렌드의 79%를 Twitter 판정보다 평균 1.43시간 먼저 잡았고, 참양성률 95%, 거짓양성률 4%였다. γ와 관측 길이로 「빠르지만 오탐이 많은」 쪽과 「정확하지만 늦은」 쪽 사이를 고른다.
시계열로 검증할 때는 미래 데이터를 엿보지 않게 시간순으로 나눈다.

정리

트렌딩 = 슬라이딩 창 카운트 + 상위 N. 슬롯 링 버퍼로 창을 밀고, 오래된 슬롯은 비운다.
분산 집계는 키별 카운트 → 부분 순위 → 전역 순위의 3단으로, 마지막 단계로 가는 양을 줄인다.
시간은 엔진이 주는 틱이나 이벤트 시각 워터마크로 주입하고, 직접 시계를 보는 스레드를 두지 않는다.
키가 너무 많으면 근사 카운트로, 창 재계산이 문제면 최소 후보 집합으로 비용을 줄인다.
결론: Top-K 문제의 핵심은 「무엇을 버려도 되는가」를 정확히 아는 것이다.

버그 제보

실시간 트렌딩과 Top-K 집계

문제

슬라이딩 창 카운터

3단 분산 집계

창이 밀릴 때 다시 계산하지 않기: MinTopk

키가 너무 많을 때: 근사 Top-K

트렌드를 일찍 잡기

정리

댓글