본문 바로가기
FrostK
테마 색상
로그인

읽는 데 6분Cat

적게 세지 않는다던 Count-min sketch가 상한에 닿았어요

IT 개발원리 데이터
적게 세지 않는다던 Count-min sketch가 상한에 닿았어요

같은 키를 4,294,967,296번 추가한 것으로 넣었는데, 돌아온 값은 4,294,967,295였어요. 다른 키와의 충돌도 없는 입력이었죠. “실제 횟수보다 작게 추정하지 않는다”는 Count-min sketch 설명에, 구현의 숫자 상한이 끼어든 순간이에요.

Anton Zhiyanov의 확률적 자료구조 소개에 나오는 Go 라이브러리 unsure를 시험했어요. Linux, Go 1.27.3에서 같은 프로그램을 64비트 대상인 amd64와 32비트 대상인 386으로 실행하니, 32비트 실행의 반환값은 그보다 더 일찍 멈췄어요. 카운터 상한은 패키지 주석에도 명시된 동작이에요. 알고리즘의 오차 설명과 API가 표현할 수 있는 횟수를 함께 읽어야 하는 사례예요.

충돌은 더 크게, 포화는 더 작게 만들어요

Count-min sketch는 키마다 별도의 횟수를 저장하는 대신, 여러 행의 작은 카운터 배열을 공유해요. 키를 해시해 각 행에서 카운터를 하나씩 고르고, 조회할 때 그중 최솟값을 돌려줘요. 다른 키가 같은 칸을 사용하면 값이 섞여 실제보다 크게 보일 수 있어요.

unsure는 추가할 때 현재 최솟값을 기준으로 필요한 카운터만 올리는 conservative update를 써요. 카운터는 uint32예요. 숫자가 상한을 넘으면 처음으로 되돌아가는 대신, 상한에 머무르게 만들어요. 이걸 포화라고 해요.

조회 경로에는 제한이 하나 더 있어요. 저장된 최솟값을 그대로 반환하지 않고, Go의 int에 들어가는 범위로 한 번 더 제한해요. int의 범위는 실행 아키텍처에 따라 달라져요.

같은 키가 각 행의 카운터로 매핑되고 최솟값을 조회한 뒤 int 범위로 제한되는 흐름
저장 공간의 상한에 닿기 전에도 반환형의 상한에 먼저 닿을 수 있어요.

키 하나로 두 경계를 넘겨 봤어요

시험에는 countmin.New(0.001, 0.01)과 같은 키 하나만 사용했어요. AddN은 같은 키의 횟수를 한 번에 더하는 API라, 수십억 번 반복문을 돌릴 필요는 없어요. 실제로 넣은 횟수는 별도의 uint64 변수에 누적해 정답으로 삼았어요.

정답 누적 횟수 amd64의 Count 386의 Count
100 100 100
2,147,483,647 2,147,483,647 2,147,483,647
2,147,483,648 2,147,483,648 2,147,483,647
4,294,967,295 4,294,967,295 2,147,483,647
4,294,967,296 4,294,967,295 2,147,483,647

32비트 실행에서는 int의 상한이 먼저 보여요. 내부 카운터에 더 큰 값이 들어갈 수 있어도 Count가 그 값을 반환하지 못해요. 64비트 실행에서는 uint32 카운터가 꽉 찬 뒤부터 정답보다 작아져요.

Total()에도 차이가 있었어요. 마지막 입력에서 amd64는 정답 누적 횟수인 4,294,967,296을 돌려줬지만, 386은 2,147,483,647에 멈췄어요. 총합도 반환할 때 int 범위로 제한하기 때문이에요.

아래는 시험에 쓴 핵심 입력이에요. unsure 커밋 a00a96d303c1f457c9e043260531daa1c89800ac 기준이며, 각 증가량은 32비트 int에도 들어가도록 나눴어요.

s := countmin.New(0.001, 0.01)
key := []byte("one-key-control")
var truth uint64
for _, n := range []int{100, 2147483547, 1, 2147483647, 1} {
    s.AddN(key, n)
    truth += uint64(n)
    fmt.Println(truth, s.Count(key), s.Total())
}

오차 설정으로 해결할 문제는 아니에요

원문의 epsilon은 전체 추가 횟수를 기준으로 한 초과 오차 폭, delta는 그 폭을 넘을 확률을 정하는 값이에요. 이번 입력은 서로 다른 키의 충돌을 살펴보는 시험이 아니에요. 정확도 설정을 더 엄격하게 해도 숫자형 자체의 범위가 넓어지지는 않아요.

빈도 추정으로 캐시에 남길 키를 고르거나 경보 임계값을 판단한다면, 원문의 통계적 보장 외에 운영 중 누적 범위도 함께 보세요. 내가 필요한 횟수가 이 구현의 반환 범위에 들어가는지부터 판단할 수 있어요. 다른 라이브러리를 고를 때도 카운터 폭과 공개 API의 반환형을 따로 비교할 이유가 생겨요.

확인한 범위

  • 기준일: 2026-11-15
  • 직접 한 것: Linux, Go 1.27.3에서 unsure의 같은 커밋에 동일한 단일 키 입력을 넣어 amd64와 386의 Count 및 Total을 비교했어요. 결과를 고정 커밋의 포화 처리와 반환형 제한 코드에 대조했어요.
  • 읽은 것: Anton Zhiyanov의 소개, unsure의 Count-min sketch 구현과 패키지 주석.
  • 확인하지 못한 것: 여러 키의 충돌 확률과 성능, 다른 구현의 경계 동작. 이번 숫자는 실제 트래픽 처리량 측정이 아니라 AddN으로 넣은 횟수의 결과예요.

출처

Probabilistic data structures in Go
Bloom filter, count-min sketch, HyperLogLog, t-digest, and top-k sketch.
unsure/countmin/countmin.go at a00a96d303c1f457c9e043260531daa1c89800ac · nalgeon/unsure
Probabilistic data structures in Go. Contribute to nalgeon/unsure development by creating an account on GitHub.