확률적 자료 구조에서 카운터를 설계할 때 가장 중요하게 고려해야 할 두 가지 요소는 바로 카운터의 크기와 오버플로 발생 가능성입니다. 이 글에서는 포아송 근사(Poisson approximation)를 기반으로 적절한 카운터 크기를 산정하는 방법과, 오버플로가 시스템에 미치는 영향을 살펴봅니다.
카운터 크기(Counter Size)
오버플로를 방지하기 위해서는 각 카운터가 저장할 수 있는 값의 범위가 충분히 커야 합니다. 카운터가 너무 작으면 값이 상한에 도달하는 순간 더 이상 정확한 정보를 담을 수 없게 되기 때문입니다.
- 포아송 근사 분석에 따르면 카운터당 4비트가 권장됩니다.
- k = (ln 2)m/n개의 카운터를 구현할 때 평균 부하(load)는 ln 2로 계산됩니다.
- 특정 카운터의 부하가 최소 16 이상일 확률은 다음과 같이 근사됩니다.
e-ln2(ln 2)16/16! ≈ 6.78E-17
즉, 약 1016분의 1 수준으로 극히 낮습니다. - 이러한 분석 결과를 바탕으로, 성능 비교 실험에서도 카운터당 4비트 기준을 채택하여 평가합니다.
요컨대, 평균 부하가 ln 2에 불과한 상황에서 하나의 카운터가 16까지 차오를 확률은 사실상 무시할 수 있을 만큼 작으므로, 4비트만으로도 실질적인 오버플로 위험 없이 운영할 수 있습니다.
카운터 오버플로(Counter Overflow)
카운터가 오버플로되면 해당 값은 표현 가능한 최댓값에 고정되어 버립니다. 문제는 이후 카운터 값이 감소하는 과정에서 발생할 수 있습니다.
- 오버플로된 카운터는 최댓값에 도달한 상태로 유지될 수 있습니다.
- 이로 인한 false negative(거짓 음성)는 카운터가 감소 과정을 거쳐 0이 되었지만, 실제로는 0이 아닌 값을 유지했어야 하는 경우에만 발생합니다.
- 이런 상황이 발생하기까지의 기대 시간(expected time)은 매우 길지만, false negative를 허용하지 않는 애플리케이션이라면 반드시 염두에 두어야 합니다.
- 오버플로를 방지하려면 카운터 크기를 충분히 크게 설정해야 하며, 연구 결과에 따르면 카운터당 4비트면 충분한 것으로 확인되었습니다.
결론적으로, 대부분의 응용 환경에서 카운터당 4비트는 메모리 효율과 정확성 사이의 균형점을 제공합니다. 다만 결함이 용납되지 않는 시스템이라면 오버플로로 인한 false negative 가능성과 그 발생 주기를 함께 검토하는 것이 안전합니다.