카운트-민 스케치

카운트-민 스케치 (Count-min sketch)

카운트-민 스케치(Count-Min Sketch)는 데이터 스트림에서 특정 요소의 **빈도(frequency)**를 추정하는 확률적 데이터 구조예요. 메모리를 아주 조금 쓰면서 대략적인 개수를 세는 데 특화되어 있죠. 이번 페이지에서는 원리부터 크기 설정, 실제 예제까지 차근차근 살펴볼게요.

출처: Redis 공식 문서 — Count-min sketch

카운트-민 스케치란?

Redis Open Source의 Count-Min Sketch는 데이터 스트림에서 이벤트/요소의 빈도를 추정하는 확률적 데이터 구조예요.

충돌(collision) 때문에 일부 이벤트를 과대 계수(over-count)하는 대신, 준선형(sub-linear) 공간만 사용해요. 이벤트/요소의 스트림을 소비하면서 각각의 빈도에 대한 추정 카운터를 유지하죠.

여기서 꼭 알아야 할 점이 있어요. Count-Min sketch에서 특정 임계값(threshold, error_rate에 의해 결정)보다 낮은 결과는 무시해야 하고, 보통 0으로 근사해서 처리해야 해요. 즉 Count-Min sketch는 스트림 요소의 빈도를 세는 데이터 구조이지만, 높은 카운트에만 유용해요. 아주 낮은 카운트는 노이즈로 무시해야 한다는 거죠.

사용 사례 (Use cases)

제품 판매량 집계 (Products, retail, online shops)

이런 질문에 답하는 용도예요: "어떤 제품의 (특정 날짜의) 판매량은 얼마였나요?"

  • 기간(하루)마다 Count-Min sketch 하나를 만들어요.
  • 모든 제품 판매가 CMS에 들어가요.
  • CMS는 판매에 가장 많이 기여한 제품에 대해 합리적으로 정확한 결과를 줘요.
  • 전체 판매에서 차지하는 비중이 낮은 제품은 무시돼요.

예제 (Examples)

오차율 0.1%(0.001)와 확실성 99.8%(0.998)를 선택한다고 가정해볼게요. 이는 오류 확률이 0.2%(0.002)라는 뜻이에요.

  • 스케치는 추가한 전체 요소 수의 0.1% 이내로 오차를 유지하려고 해요.
  • 오차가 이 값을 초과할 확률이 0.2% 있어요. 예를 들어 임계값 아래에 있는 요소가 위에 있는 요소와 겹칠 때 그렇죠.

CMS에 몇 개 아이템을 추가하고 빈도를 평가할 때, 다른 확률적 데이터 구조와 마찬가지로 이렇게 작은 표본에서는 충돌이 드물다는 점을 기억해야 해요.

카운트-민 스케치의 주요 연산은 다음과 같아요. CMS.INITBYPROB로 스케치를 만들고, CMS.INCRBY로 요소 카운트를 증가시키며, CMS.QUERY로 빈도를 추정하고, CMS.INFO로 스케치 속성을 확인합니다. 데이터 스트림에서 요소 빈도를 추정할 때 쓰는 명령들이죠.

res1 = r.cms().initbyprob("bikes:profit", 0.001, 0.002)  # key, error, probability
print(res1)  # >>> True
res2 = r.cms().incrby("bikes:profit", ["Smoky Mountain Striker"], [100])
print(res2)  # >>> [100]
res3 = r.cms().incrby("bikes:profit", ["Rocky Mountain Racer", "Cloudy City Cruiser"], [200, 150])
print(res3)  # >>> [200, 150]
res4 = r.cms().query("bikes:profit", "Smoky Mountain Striker")
print(res4)  # >>> [100]
res5 = r.cms().info("bikes:profit")
print(res5.width, res5.depth, res5.count)  # >>> 2000 9 450

CLI로는 이렇게 실행해요.

> CMS.INITBYPROB bikes:profit 0.001 0.002
OK
> CMS.INCRBY bikes:profit "Smoky Mountain Striker" 100
1) (integer) 100
> CMS.INCRBY bikes:profit "Rocky Mountain Racer" 200 "Cloudy City Cruiser" 150
1) (integer) 200
2) (integer) 150
> CMS.QUERY bikes:profit "Smoky Mountain Striker"
1) (integer) 100
> CMS.INFO bikes:profit
 1) width
 2) (integer) 2000
 3) depth
 4) (integer) 9
 5) count
 6) (integer) 450

CMS.INITBYPROB의 인자는 key, error, probability 순서예요. 위 예제에서는 오차율 0.001, 오류 확률 0.002를 지정했어요. 각 언어별 클라이언트(redis-py, node-redis, Jedis, go-redis, NRedisStack, Predis 등)에서도 동일한 연산을 제공해요.

예제 1 (Example 1)

1000개의 요소가 균등 분포(uniform distribution)를 이루고, 각각의 카운트가 약 500이라면 임계값은 500이 돼요.

threshold = error * total_count = 0.001 * (1000*500) = 500

이건 균등하게 분포된 스트림의 빈도를 세는 데 CMS가 최선의 구조는 아닐 수 있음을 보여줘요. 오차를 0.01%로 낮춰보면:

threshold = error * total_count = 0.0001 * (1000*500) = 100

이 임계값은 훨씬 수용 가능해 보여요. 하지만 스케치의 폭 w = 2/error = 20 000이 필요하게 되어 더 많은 메모리를 쓰게 됩니다.

예제 2 (Example 2)

다른 예제로, 정규(가우시안) 분포를 가정해볼게요. 1000개의 요소 중 800개는 합산 카운트 400K(평균 카운트 500), 나머지 200개는 합산 카운트 1.6M(평균 카운트 8000)이라서 이 200개가 heavy hitter(코끼리 흐름, elephant flow)가 되는 상황이에요.

모든 1000개 요소로 스케치를 "채운" 뒤의 임계값은:

threshold = error * total_count = 0.001 * 2M = 2000

이 임계값은 두 평균 카운트(500과 8000) 사이에 잘 자리 잡고 있어요. 그래서 처음 선택한 오차율이 이 경우에는 잘 동작할 거예요.

크기 설정 (Sizing)

Count-Min sketch는 여러 면에서 Bloom filter와 비슷하지만, 크기 설정은 훨씬 복잡해요. 초기화 명령은 두 개의 크기 파라미터만 받지만, 쓸만한 스케치를 만들려면 이들을 제대로 이해해야 해요.

CMS.INITBYPROB key error probability

1. 오차 (Error)

error 파라미터가 스케치의 폭 w를 결정하고, 확률(probability)이 해시 함수 개수(깊이 d)를 결정해요. 우리가 고른 오차율이 이 값 위에서는 결과를 믿을 수 있는 임계값을 결정하죠. 관계는 다음과 같아요.

threshold = error * total_count

또는

error = threshold/total_count

여기서 total_count는 CMS.INFO 명령 결과의 count 키에서 얻을 수 있는, 스케치 안 모든 요소 카운트의 합이에요. 당연히 스케치에 새 증분이 생길 때마다 변하는 동적인 값이죠. 생성 시점에는 total_count 비율을, 스케치에서 기대하는 평균 카운트와 요소 수의 곱으로 근사할 수 있어요.

임계값이 필터의 총 카운트에 비례하기 때문에, 카운트가 커질수록 임계값도 함께 커진다는 점이 중요해요. 하지만 총 카운트를 알면 임계값은 언제든 동적으로 계산할 수 있고, 결과가 그 아래면 버리면 됩니다.

2. 확률 (Probability)

이 데이터 구조에서 probability는 임계값보다 낮은 카운트를 가진 요소가, 임계값보다 높은 카운트를 가진 요소와 모든 스케치/깊이에서 충돌할 확률을 나타내요. 그렇게 되면 자주 나타나는 요소의 최소 카운트를 대신 반환하게 되는 거죠.

성능 (Performance)

CMS에서 요소를 추가(adding), 갱신(updating), 조회(querying)하는 시간 복잡도는 모두 O(1) 이에요.

학술 자료 (Academic sources)

더 알아보기 (Learn more)