- 확률적 자료구조는 포함 여부, 빈도, 고유 항목 수, 분위수 등에 근삿값을 제공하는 대신 메모리 사용량을 수십 배에서 수천 배까지 줄일 수 있음
- Bloom filter는 항목이 없다는 사실을 확실히 판별해 불필요한 I/O를 줄이고, Count-min sketch는 실제 빈도보다 작지 않은 추정치를 제공함
- HyperLogLog는 고유 항목 100만 개를 약 0.8% 오차와 16KB 메모리로 집계하며, 여러 스케치를 병합해도 공통 항목을 중복 집계하지 않음
- T-digest는 숫자 스트림의 분위수와 누적분포를, Top-k sketch는 자주 등장하는 항목과 빈도를 추정함. 각각 순위 오차와 데이터의 빈도 분포를 고려해야 함
- Go 패키지 unsure는 이 다섯 자료구조를 표준 라이브러리 외 의존성 없이 구현함. 공개된 비교 벤치마크에서 대체로 더 빠르지만, 구조와 데이터 조건에 따라 메모리 및 정확도에 절충이 있음
- 확률적 자료구조는 집합이나 빈도 테이블처럼 정확한 답을 보장하지는 않지만, 허용 가능한 불확실성으로 메모리를 크게 절약함
- unsure는 다섯 자료구조를 Go로 구현하며, 각 구조의 핵심 로직은 100~300줄이고 표준 라이브러리 외 의존성이 없음
- 구조마다 답할 수 있는 질문과 보장하는 오차가 다르므로, 포함 여부 / 빈도 / 고유 항목 수 / 분위수 / 상위 빈도 항목 중 필요한 기능에 맞춰 선택해야 함
- Bloom filter는 실제 항목을 저장하지 않고, “확실히 없음” 또는 “있을 가능성이 있음”을 반환함
- 양성 결과에는 거짓 양성이 있을 수 있으므로 실제 조회가 필요함
- 음성 결과라면 디스크 읽기나 네트워크 호출 같은 비싼 조회를 건너뛸 수 있음
- 서로 다른 8바이트 문자열 100만 개를 저장하는 일반 집합은 약 64MB, 거짓 양성률 1%의 필터는 1.24MB로 약 50배 차이가 남
- 항목당 약 10비트이며, 필터 크기는 항목의 바이트 크기에 의존하지 않아 긴 문자열일수록 절약 폭이 커짐
- 예상 항목 수와 거짓 양성률에 맞춰 크기를 정하며, 예상보다 많이 추가하면 거짓 양성률이 높아짐
- 추가와 포함 여부 확인은 가능하지만 삭제, 항목 수 집계, 항목 순회는 불가능함
- 기본 Bloom filter는 0으로 초기화한 m비트 배열에서 항목의 k개 해시가 가리키는 비트를 1로 설정함
- 조회할 때 하나라도 0이면 추가되지 않은 항목임
- 모두 1이어도 다른 항목이 해당 비트를 설정했을 수 있음
- 비트가 배열 전체에 흩어져 있어 필터가 CPU 캐시보다 크면 한 번의 조회에서 최대 k번 메모리를 기다릴 수 있음
- unsure는 블록형 Bloom filter를 사용해 배열을 CPU 캐시 라인 크기와 같은 512비트 블록으로 나눔
- 한 번 계산한 해시의 상위 32비트로 블록을, 하위 32비트와 솔트로 블록 내 비트 위치를 정함
- 추가와 조회마다 캐시 라인 하나만 접근함
- 블록별 항목 수 불균형 때문에 같은 거짓 양성률을 유지하려면 일반 필터보다 메모리가 더 필요함. 추가 사용량은 거짓 양성률 1%에서 약 3%, 0.1%에서 8%, 0.01%에서 15%임
- 해시는 자체 wyhash 구현을 사용함. xxh3와 대략 비슷한 성능이면서 SIMD나 어셈블리 없이 더 단순하게 구현함
- 비교 벤치마크에서 unsure는 일반 필터인 bits-and-blooms/bloom보다 약 4배, 블록형인 jcalabro/gloom보다 약 2배 빠름
- 메모리는 bits-and-blooms보다 1~8% 많고 gloom보다 4~10% 적게 사용함
- 항목 5,000만 개에서 추가 시간은 unsure / bits-and-blooms / gloom 순으로 38 / 170 / 63ns이며, 적중 조회는 34 / 129 / 60ns임
- Count-min sketch는 실제 항목을 저장하지 않는 근사 빈도 테이블로, 추정치가 실제 횟수보다 작아지지는 않지만 커질 수 있음
- 대규모 이벤트 스트림의 IP별 요청 제한, 오류 횟수에 따른 알림, 요청 빈도에 따른 캐시 보관 판단에 활용할 수 있음
- 카운터 증가와 빈도 조회는 가능하지만 감소나 항목 순회는 지원하지 않음
- 서로 다른 8바이트 문자열 100만 개의 빈도를 저장하는 일반 맵은 약 64MB임. 총횟수의 0.01% 이내 오차를 99% 확률로 만족하는 스케치는 0.55MB로 약 116배 작음
- 크기는 고유 항목 수나 항목 크기가 아니라 선택한 정확도에 따라 결정됨
- 오차 설정은 ε와 δ 두 가지임. 실제 빈도가 X, 전체 누적 횟수가 N이면 최소 1−δ의 확률로 추정치는 X부터 X+ε·N 사이에 있음
- ε=0.001, δ=0.01, N=100만이면 최소 99% 확률로 과대 추정이 1,000 이하이며, 이를 넘을 확률은 최대 1%임
- 오차는 개별 항목 빈도가 아닌 전체 누적 횟수에 비례하므로, 드문 항목은 상대적으로 부정확함
- 기본 Count-min sketch는 d개 행과 w개 열의 카운터 테이블을 사용함
- 행마다 다른 해시로 선택한 카운터를 증가시키고, 조회 시 해당 카운터들의 최솟값을 반환함
- 충돌은 카운터를 높이기만 하므로, 최솟값이 충돌 영향을 가장 적게 받은 추정치임
- w=e/ε이면 각 카운터의 오차가 ε·N 이하일 확률이 최소 1−1/e이며, d=ln(1/δ)이면 모든 카운터가 이 오차를 초과할 확률은 최대 δ임
- unsure는 보수적 갱신(conservative update) 으로 현재 최솟값 E를 구한 뒤, n을 추가할 때 E+n보다 작은 카운터만 그 값까지 올림
- 기존 정확도 보장을 유지하면서 실제 오차를 약 절반으로 줄이지만 카운터를 감소시킬 수 없음
- 일반적인 64비트 대신 32비트 카운터로 메모리를 절반으로 줄임
- wyhash로 한 번 해시한 뒤 행별 무작위 상수를 곱해 각 행의 위치를 정함
- 비교 벤치마크에서 64비트 카운터를 쓰는 BoomFilters보다 추가는 약 1.5배, 조회는 약 4배 빠름
- 메모리는 절반, 오차는 약 2~2.7분의 1 수준임
- ε=0.0001, 고유 항목 100만 개에 총 1,000만 회 추가한 균등 분포에서 평균 과대 추정은 139 대 302이며, 메모리는 536KB 대 1,080KB임
- Zipf 분포에서도 평균 과대 추정이 더 작았음
- HyperLogLog는 각 항목의 등장 횟수와 무관하게 서로 다른 항목 수를 추정함
- 웹사이트 고유 방문자, 일별 고유 검색어, 데이터베이스 열의 서로 다른 값 집계에 적합함
- 추가, 추정 집계, 병합은 가능하지만 특정 항목의 포함 여부 확인, 삭제, 목록 조회는 불가능함
- 8바이트 문자열 100만 개를 담는 일반 집합은 약 64MB지만, 약 0.8% 오차의 스케치는 16KB로 거의 4,000배 작음
- 크기는 데이터 수나 크기가 아니라 정밀도에 따라 결정되며, 16KB 스케치로 1,000개와 10억 개를 같은 상대 표준오차로 집계할 수 있음
- 머신이나 시간 / 페이지 / 지역별 스케치를 병합하면 공통 항목을 중복 집계하지 않는 전체 고유 항목 수를 얻음
- 정밀도 p의 상대 표준오차는 1.04/√(2^p)이며, 일반적인 기본값 p=14에서는 약 0.81% 임
- 고유 항목 100만 개라면 약 68%의 경우 오차가 0.81%, 약 95%는 1.6%, 약 99.7%는 2.4% 이내임
- HyperLogLog의 원리는 무작위 해시에서 앞부분의 연속된 0이 길게 나올수록 더 많은 고유 항목을 봤을 가능성이 높다는 점에 기반함
- 해시의 약 절반은 1, 4분의 1은 01, 8분의 1은 001로 시작하며, 앞에 0이 k개인 해시의 관측은 약 2^(k+1)개의 고유 항목을 시사함
- 첫 p비트로 2^p개 레지스터 중 하나를 고르고, 나머지 비트의 선행 0 개수에 1을 더한 순위의 최댓값을 보관함
- 중복 항목은 같은 해시를 만들므로 결과에 영향을 주지 않음
- 기본 추정은 2^레지스터값의 조화평균을 이용하고, 병합은 대응하는 레지스터의 최댓값을 취함
- 원래 추정기는 작은 집계에서 편향이 있어 선형 계수법(linear counting) 으로 전환하며, 이 경계에서 오차가 급변함
- HyperLogLog++ 같은 구현은 실제 데이터 기반의 큰 편향 보정 테이블을 사용함
- unsure는 Otmar Ertl의 개선된 추정기를 사용해 레지스터 값별 개수를 담은 히스토그램으로 집계함
- 0개부터 수십억 개까지 별도의 소규모 집계 공식이나 보정 테이블 없이 추정함
- 레지스터 변경 시 히스토그램도 갱신하며, 대부분의 추가는 레지스터를 바꾸지 않아 추가 비용이 거의 없음
- 집계 시간은 스케치 크기와 무관하게 일정함. 비교 대상 구현은 집계할 때마다 모든 레지스터를 순회함
- 레지스터는 각각 1바이트, 히스토그램은 4바이트 카운터 64개로 256바이트임. 64비트 wyhash 결과를 레지스터 인덱스와 순위로 나눔
- 비교 벤치마크에서 LogLog-Beta 추정기와 희소 모드를 사용하는 axiomhq/hyperloglog와 추가 속도는 비슷하고, 집계는 270~83,000배, 병합은 2.3~2.9배 빠름
- p=14의 집계 시간은 62ns 대 350,000ns임
- 항목 수가 레지스터 수보다 많으면 정확도와 메모리는 비슷함
- 항목이 적으면 axiom의 희소 모드가 더 정확하고 작음. 항목 1,000개에서 상대 RMSE는 0.63% 대 0.02%, 메모리는 16KB 대 4.2KB임
- T-digest는 숫자 스트림을 요약해 중앙값이나 99번째 백분위수 같은 분위수와, 특정 값보다 작은 데이터의 비율인 누적분포함수(CDF) 를 추정함
- 서비스 지연시간, 요청 크기나 가격 분포, 센서 데이터의 이상치 임계값 계산에 활용할 수 있음
- 추가, 분위수 및 CDF 조회, 병합은 가능하지만 값 삭제나 전체 목록 조회는 불가능함
- 64비트 부동소수점 값 100만 개를 모두 보관하면 8MB지만, T-digest는 약 8KB로 99번째 백분위수를 순위 오차 약 0.03% 이내에서 추정할 수 있음
- 이는 반환값이 실제 98.97번째와 99.03번째 백분위수 사이에 있다는 뜻이며, 값 자체의 상대 오차가 아님
- 크기는 데이터 개수가 아니라 정확도 설정에 의존하며, 8KB로 100만 개와 10억 개를 같은 수준으로 요약할 수 있음
- 여러 머신이나 시간 / 엔드포인트 / 지역별 다이제스트를 병합할 수 있지만 개별 다이제스트보다 정확도가 낮아짐
- 압축 설정 δ 는 중심점(centroid) 수를 δ+2개로 제한함. 일반적인 기본값 δ=100은 약 8KB이며, 값을 높이면 메모리가 늘고 오차가 줄어듦
- 꼬리 부분인 q=0.99, q=0.999의 추정은 중앙값 q=0.5보다 정확함
- T-digest는 평균과 가중치, 즉 대표하는 값의 수를 가진 중심점들을 정렬해 보관하고, 요청한 순위 주변 중심점의 평균을 보간함
- 척도 함수 k(q)는 분위수를 −δ/4부터 δ/4로 매핑하며, 각 중심점은 k(q₂)−k(q₁)≤1을 만족해야 함
- 아크사인 함수 k(q)=δ/(2π)·asin(2q−1)는 양 끝에서 가파르고 중앙에서 평평해, 중앙에는 큰 중심점을, 꼬리에는 작은 중심점을 만듦
- 값 100만 개와 δ=100에서 중심점당 값의 수는 중앙 부근 약 27,000개, 99번째 백분위수 부근 약 5,000개, 가장 바깥쪽 약 500개임
- unsure는 Dunning과 Ertl 논문의 병합형 T-digest를 구현함
- 새 값을 5·δ개 버퍼에 모은 뒤 정렬하고, 기존의 정렬된 중심점과 한 번의 순회로 병합함
- 매번 병합 방향을 좌우로 번갈아 바꿔 한쪽 꼬리의 중심점만 더 차는 현상을 피함
- Quantile, CDF, Merge는 먼저 버퍼를 비움
- 중심점용 고정 배열 두 개와 누적 가중치를 유지하며, 분위수와 CDF 조회에 이진 탐색을 사용함
- 가중치가 1인 중심점은 정확한 값으로 취급하고 양 끝에는 실제 최솟값과 최댓값을 사용함
- 데이터가 적은 다이제스트는 정확한 결과를 내며, Quantile(0)과 Quantile(1)은 항상 정확함
- 비교 벤치마크에서 같은 척도 함수를 쓰는 influxdata/tdigest보다 추가는 약 1.8배, 병합은 7~9배 빠르고 조회 속도와 정확도는 대체로 비슷함
- δ=100에서 메모리는 8.5KB 대 14.4KB로 약 40% 적음
- 정규분포 값 100만 개의 단일 다이제스트에서 99번째 백분위수 평균 순위 오차는 0.018% 대 0.016%, 병합 후에는 0.023% 대 0.021%임
- Top-k sketch는 스트림에서 가장 빈번한 k개 항목과 근사 빈도를 찾음
- 가장 많이 요청되는 URL, 가장 활동적인 사용자, 흔한 검색어를 찾는 데 유용함
- Count-min sketch와 달리 실제 항목을 보관해 목록을 반환할 수 있음
- 정확한 집계를 위해 수백만 고유 항목의 빈도를 모두 저장하면 수십~수백 MB가 필요하지만, 상위 1,000개용 스케치는 약 360KB이며 보통 상위 항목을 모두 찾아냄
- Top은 최대 k개 항목을 빈도 내림차순으로 반환함
- 가장 빈번한 항목의 횟수는 보통 정확하지만 덜 빈번한 항목은 실제보다 조금 작게 추정할 수 있음
- 소수 항목에 빈도가 집중된 편향된 스트림에서 가장 잘 작동하며, 빈도가 고르면 뚜렷한 상위 항목이 없어 정확도가 낮아짐
- 횟수를 감소시키거나 상위 k개 밖의 항목을 조회할 수 없음
- 기반 알고리듬인 HeavyKeeper는 d행, w열의 버킷에 항목 지문과 카운터를 저장함
- 각 항목은 행마다 한 버킷에 대응하며, 비어 있거나 같은 항목의 버킷이면 카운터를 증가시킴
- 다른 항목이 차지한 버킷이면 b^count, b<1의 확률로 카운터를 1 감소시킴. 0이 되면 새 항목이 카운터 1로 차지함
- 항목의 추정 빈도는 해당 버킷들 중 최댓값임
- 빈번한 항목은 카운터가 커져 감쇠 확률이 작아지고, 드문 항목끼리는 서로 교체됨. 스트림 후반에 빈번해진 항목도 기존 항목을 밀어낼 수 있음
- 테이블 옆의 최소 힙에는 추정 빈도가 가장 큰 k개 항목을 유지함
- 새 추정치가 힙의 최솟값보다 크면 그 항목을 넣고 최솟값 항목을 제거함
- 이미 힙에 있는 항목이면 횟수를 증가시킴
- unsure는 2개 행, 행마다 max(16k, 256)개 버킷, 감쇠 밑 b=0.8을 사용함
- b^count를 64비트 임계값으로 미리 계산해 난수 비교로 감쇠를 처리함
- 원래 HeavyKeeper는 b≈0.93과 더 많은 행을 사용함
- 작은 b는 빈번한 항목이 버킷을 빨리 확보하게 해 평탄한 스트림의 정확도를 높이지만, 0.5처럼 너무 작으면 초기 항목이 버킷을 사실상 독점해 뒤늦게 빈번해진 항목을 놓침
- b=0.8은 정확도를 대부분 유지하면서 후반에 빈번해지는 항목도 대부분 포착함. 두 행으로 한 행의 충돌을 보완할 수 있고, 추가 행은 속도를 낮춤
- 해시와 저장 구조도 비용을 줄이도록 구성함
- 한 번 계산한 wyhash에 행별 무작위 상수를 곱해 버킷 위치를 정하고, 상위 32비트를 지문으로 사용함
- 힙은 실제 바이트 비교 대신 64비트 해시로 항목을 식별하며, 난수 생성에는 wyrand를 사용함
- 버킷은 32비트 지문과 32비트 카운터로 8바이트임. 행당 16k개 버킷일 때 테이블은 256·k바이트이며, 힙은 항목당 약 100바이트에 실제 항목 크기가 더해짐
- 비교 벤치마크는 b=0.9, d=ln k인 keilerkonzept/topk와 Filtered Space-Saving을 구현한 dgryski/go-topk를 비교함
- Zipf s=0.8에서 unsure의 추가는 2~4배, 상위 목록 조회는 1.8~4배 빠름
- 평탄한 Zipf s=0.6에서 반환한 항목 중 실제 상위 항목의 비율은 unsure 90~97%, keiler 38~70%, dgryski 19~52%임
- 같은 조건의 평균 상대 카운트 오차는 unsure 2.4~14%, keiler 62~94%이며, dgryski는 빈도를 18배 이상 크게 추정함
- 편향이 큰 s=1.0에서는 세 구현의 정확도가 대체로 비슷함
- k=100에서는 keiler가 27KB로 unsure의 39KB보다 작지만, k=1,000에서는 unsure가 364KB로 keiler 414KB와 dgryski 453KB보다 작음
- 허용 가능한 불확실성이 있다면, 모든 원본 항목이나 값을 저장하지 않고도 필요한 질문에 답하면서 메모리를 수십~수천 배 절약할 수 있음
- Go에서는 nalgeon/unsure로 포함 가능성, 빈도, 고유 항목 수, 분위수, 상위 빈도 항목을 다루는 다섯 구조를 사용할 수 있음