스트리밍 알고리즘으로 빈도·고유 수·시간 구간을 근사 집계하는 법

정확한 테이블이 감당하지 못하는 스트림

대규모 실시간 데이터 흐름에서는 모든 값을 정확히 저장하고 계산하는 방식이 지연과 비용을 키운다. 스트리밍 알고리즘은 단일 패스 또는 소수 패스로 입력을 처리하면서 서브선형(sublinear) 메모리를 사용하고, 근사값과 확률적 오차 보장을 제공한다.

설계 목표는 업데이트를 O(1)에 가깝게 유지하고, 여러 파티션의 결과를 합칠 수 있으며, 분산 처리에 자연스럽게 연결하는 데 있다. 빈도는 Count-Min Sketch(CMS), 고유 수는 HyperLogLog(HLL), 최근 시간 범위는 Sliding Window가 맡는 구성이 대표적이다.

빈도·고유 수·시간 범위를 나누어 다루기

Count-Min Sketch로 빈도 추정하기

CMS는 d개의 독립 해시함수와 w폭의 2차원 카운터 배열로 구성한다. 이벤트가 들어오면 각 해시가 가리키는 카운터를 +1 하고, 키를 조회할 때는 해당 카운터 중 최솟값을 반환한다.

추정 오차는 P≥1−δ에서 f̂(x) ≤ f(x) + εN이며, 파라미터는 w=⌈e/ε⌉, d=⌈ln(1/δ)⌉로 정한다. 해시 충돌 탓에 결과는 항상 과대 추정된다. Conservative Update와 Count-Min-Mean은 이 바이어스를 줄이는 데 쓰이며, CMS는 빈도 상위 항목 탐지에 맞는다. 반대로 감소 이벤트는 오차를 키우므로 삭제를 지원하지 않는다.

HyperLogLog로 고유 수 추정하기

HLL은 m=2^p개의 레지스터에 해시값의 선행 0(leading zeros) 길이 ρ를 기록한다. 각 레지스터의 최대값과 조화 평균 보정을 이용해 기수(cardinality)를 추정한다.

상대오차는 ≈ 1.04/√m이며, p=14(m=16384)일 때 약 0.81% 오차다. 여러 HLL은 같은 위치의 레지스터에서 최댓값을 취해 O(m)으로 합칠 수 있다. 따라서 중복 제거가 핵심인 고유 사용자 집계에 적합하다. 작은 범위에서는 HLL++ 보정이 필요하고, 해시의 균일성도 전제된다.

Sliding Window로 최근 구간을 유지하기

Sliding Window는 최근 T 구간의 집계만 보관한다. 창은 서로 겹치는 Sliding, 겹치지 않는 Tumbling, 활동을 기준으로 닫히는 Session 방식으로 나뉜다.

구현은 시간 또는 카운트 기준의 고정 버킷 순환 배열, 지수 감쇠(Exponential Decay), 워터마크 기반 지연 이벤트 처리로 구성할 수 있다. CMS나 HLL을 버킷마다 따로 두면 시간 구간별 빈도와 기수를 추정할 수 있고, 버킷이 만료될 때 메모리 상한도 고정된다. 병렬 파티션을 합치는 구조에도 잘 맞는다.

파라미터와 병합 정책이 정확도를 좌우한다

CMS는 ε와 δ가 메모리 w×d를 결정한다. 카운터 폭은 4B를 권장하며, Conservative Update와 Count-Min-Mean은 heavy hitter에서 과대 추정을 줄이는 데 효과가 있다.

HLL은 p와 레지스터 비트폭(5~6bit)으로 정확도와 메모리의 균형을 조절한다. 레지스터별 max 병합은 분산 샤딩과 오프라인 리듀스에 적합하다.

윈도우는 T/Δ개 버킷의 순환 배열로 구성하고, 만료·스냅샷·백프레셔를 함께 처리해야 한다. 지연 또는 역행 이벤트를 다루려면 워터마크와 허용 지연(Lateness), 보정 규칙이 필요하다.

해시는 64-bit 이상 비편향 함수인 XXH3 또는 Murmur3를 사용하고, seed를 고정해 재현성을 확보한다. 키 스페이스 스큐를 줄이려면 d개 해시의 독립성도 확보해야 한다. 파티션 키로 샤딩한 뒤 로컬 스케치를 유지하고 주기적으로 병합하며, 배치 크기와 주기를 조절해 정확도와 지연을 맞춘다. 병합은 멱등성도 고려해야 한다.

입력부터 알람까지의 집계 경로

⤢✕

선택 기준과 운영 제약

알고리즘	성능(업데이트)	확장성/병합	일관성(오차 모델)	안정성(충돌/바이어스)	운영 편의
Count-Min Sketch	O(d) 상수 시간, 매우 빠름	카운터 합산으로 선형 병합	f̂ ≤ f + εN (1−δ)	과대 추정, 해시 충돌 민감	파라미터 설계 직관적(ε, δ), 삭제 비지원
HyperLogLog	O(1) 상수 시간	레지스터wise max로 선형 병합	상대오차 ≈ 1.04/√m	소범위 바이어스, 해시 균일성 요구	메모리 예측 용이, 고유 수 추정 특화
Sliding Window	버킷 O(1), 만료 O(1)	파티션 윈도우 병합	창 내 근사 일관성	지연/역행 이벤트 민감	워터마크/만료 정책 필요

API 트래픽 이상 탐지에서는 API 키나 엔드포인트를 키로 CMS를 구성하고, 1분 Sliding Window에서 빈도를 추정해 임계치 초과를 알린다. Conservative Update를 적용하고 워터마크 10초로 지연을 허용하는 방식이다.

DAU/MAU나 캠페인 고유 사용자 집계는 사용자 ID를 해시해 HLL에 넣고, 일·주 단위 HLL을 병합한다. p=14(≈12KB/HLL)로 서비스와 지역을 샤딩한 뒤 일일 배치에서 union-by-max를 수행한다.

Top-N 키워드나 상품은 CMS로 빈도를 추정하고 미니힙으로 후보군을 유지한 후, 백그라운드 정확 집계로 재검증한다. CMS 상위 후보에는 샘플링과 정확 카운트의 교차검증을 적용한다.

레이트 리밋과 QoS에서는 사용자별 Sliding Window 카운트로 요청률을 추정하고, 임계치를 넘으면 제한한다. 분산 환경에서는 키 고정 샤딩으로 파티션 일관성을 지키고 clock skew를 모니터링한다.

파이썬 최소 구현

전제조건은 다음과 같다.

• Python 3.10+
• 해시: mmh3 또는 내장 hash (PYTHONHASHSEED 고정 권장)
• HLL 라이브러리: hyperloglog

설치:

• pip install mmh3 hyperloglog

# Python 3.10+
# pip install mmh3 hyperloglog
import time
import collections
import mmh3
import hyperloglog

class CountMinSketch:
    def __init__(self, eps=1e-3, delta=1e-5, seed=42, counter_bytes=4):
        import math, array
        self.w = int(math.ceil(math.e / eps))
        self.d = int(math.ceil(math.log(1/delta)))
        self.seed = seed
        typecode = 'I' if counter_bytes == 4 else 'H'
        self.table = [array.array(typecode, [0]*self.w) for _ in range(self.d)]
        self.c = 0  # total count

    def _hash(self, key, i):
        return mmh3.hash64(str(key), self.seed + i)[0] % self.w

    def add(self, key, cnt=1):
        self.c += cnt
        for i in range(self.d):
            j = self._hash(key, i)
            self.table[i][j] = min(self.table[i][j] + cnt, 0xFFFFFFFF)

    def query(self, key):
        return min(self.table[i][self._hash(key, i)] for i in range(self.d))

# Sliding window by fixed buckets (Δ seconds)
class SlidingWindowCounter:
    def __init__(self, window_sec=60, granularity=1):
        self.window_sec = window_sec
        self.granularity = granularity
        self.buckets = collections.deque(maxlen=window_sec // granularity)
        self.start_ts = None

    def _roll(self, now):
        if self.start_ts is None:
            self.start_ts = now
            for _ in range(self.buckets.maxlen):
                self.buckets.append(0)
        steps = int((now - self.start_ts) // self.granularity)
        for _ in range(min(steps, self.buckets.maxlen or 0)):
            self.buckets.append(0)
            self.start_ts += self.granularity

    def add(self, cnt=1, now=None):
        now = now or int(time.time())
        self._roll(now)
        if self.buckets:
            self.buckets[-1] += cnt

    def sum(self):
        return sum(self.buckets)

# HLL for unique count
hll = hyperloglog.HyperLogLog(p=14)  # ≈0.81% error, ~12KB

cms = CountMinSketch(eps=1e-3, delta=1e-5)
win = SlidingWindowCounter(window_sec=300, granularity=1)

# Stream simulation
for i in range(100000):
    key = f"user_{i % 5000}"  # duplicates
    cms.add(key)
    hll.add(key)
    win.add()

print("CMS est freq(user_42):", cms.query("user_42"))
print("HLL unique users:", int(len(hll)))
print("Requests in last 5m:", win.sum())

CMS를 ε=0.001, δ=1e-5로 설정하면 메모리는 ≈ w(≈2719)×d(≈12)×4B ≈ 127.5KB/스케치다. 키 스페이스별로 인스턴스를 분리하는 방식을 권장한다.

HLL은 p=14에서 ~0.81% 오차/12KB, p=16에서 ~0.26%/48KB다. 워크로드별 비용과 정확도의 최적점을 찾아야 한다. 분산 노드의 시계는 NTP로 동기화하고, 워터마크는 P99 지연을 기준으로 보수적으로 설정한다.

메모리와 지연을 바꾸는 효과

HLL은 p=14, 12KB로 최대 수천만 고유값을 근사할 수 있으며, 정확 집계 대비 수백~수천 배 메모리를 절감한다. CMS는 ε=0.1% 목표에서 스케치당 약 128KB를 사용하고, 정확 카운트 테이블의 O(|keys|) 메모리를 O(w×d) 상한으로 고정한다.

업데이트는 O(1) 수준으로 코어당 수백만 이벤트/초 처리가 가능하며, 언어와 해시 구현에 따라 달라진다. 병합은 O(m) 또는 O(w×d)로 수행해 배치 윈도 병합 지연을 최소화할 수 있다.

HLL의 상대오차는 ≈ 1.04/√m이고 CMS는 f̂ ≤ f + εN(1−δ)의 빈도 상한을 보장한다. 지연과 역행 이벤트를 관리하면 윈도우 일관성을 유지하고 알람 오탐률을 줄일 수 있다.

빈도에는 CMS, 고유 수에는 HLL, 시간 제약에는 Sliding Window를 선택한다. 대규모 트래픽 모니터링, 고유 사용자 집계, 레이트 리밋, 이상 탐지에서 이 조합을 우선 적용할 수 있다.