> ## Content Index
> Fetch the complete content index at: https://blog.frostk.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 적게 세지 않는다던 Count-min sketch가 상한에 닿았어요
- URL: https://blog.frostk.com/countmin-counter-limits/
- Published: 2026-11-15T01:00:00.000Z
- Updated: 2026-11-15T01:00:00.000Z
- Description: Count-min sketch는 실제 횟수보다 작게 추정하지 않는다고 배우지만, 구현의 숫자 범위까지 무한한 건 아니에요. unsure에 같은 키 하나만 넣고 32비트와 64비트로 실행해 봤어요. 저장 카운터의 포화와 반환형 제한이 서로 다른 지점에서 나타났어요.
- Author: Cat
- Tags: IT, 개발원리, 데이터

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

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

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

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

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

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

![같은 키가 각 행의 카운터로 매핑되고 최솟값을 조회한 뒤 int 범위로 제한되는 흐름](https://blog.frostk.com/content/images/2026/11/hf-26909337.png)

저장 공간의 상한에 닿기 전에도 반환형의 상한에 먼저 닿을 수 있어요.

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

시험에는 `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`에도 들어가도록 나눴어요.

```go
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 GoBloom filter, count-min sketch, HyperLogLog, t-digest, and top-k sketch.![](https://blog.frostk.com/content/images/icon/favicon-88387fb3-226d-4164-aaba-b3c32bf65367.png)Anton Zhiyanovantonz.org![](https://blog.frostk.com/content/images/thumbnail/cover-e16aa416-f53a-4ffc-96d8-d153a296a703.png)](https://antonz.org/probabilistic-data-structures/?ref=blog.frostk.com)

[unsure/countmin/countmin.go at a00a96d303c1f457c9e043260531daa1c89800ac · nalgeon/unsureProbabilistic data structures in Go. Contribute to nalgeon/unsure development by creating an account on GitHub.![](https://blog.frostk.com/content/images/icon/favicon-0fe65af8-01dd-45cf-9514-05cd0633664d.png)GitHub![](https://blog.frostk.com/content/images/thumbnail/e7224b4d-0d25-442a-9592-501ce3eab2cf-f8d6eecb-bc53-40cd-8989-919db8a1f919.png)](https://github.com/nalgeon/unsure/blob/a00a96d303c1f457c9e043260531daa1c89800ac/countmin/countmin.go?ref=blog.frostk.com)