~/blog/redis-hyperloglog/ko.mdx

Redis HyperLogLog: 100만 명을 14KB로 세기

고유 방문자를 SET으로 세면 100만 명에 48MB, HyperLogLog로 세면 14KB입니다. 어떻게 세는지 따라가 보고, 오차가 얼마인지 직접 재 봤습니다.

하루 고유 방문자 수처럼, 누가 왔는지는 필요 없고 몇 명인지만 알면 되는 질문이 있습니다. 이 글의 숫자는 모두 Docker의 Redis 7.2.4(공식 이미지, jemalloc)에 user:0부터 user:999999까지 넣어 잰 값입니다.

정확히 세면

SET에 넣으면 정확한 개수가 나옵니다. 대신 원소를 전부 들고 있어야 합니다.

Terminal window
$ redis-cli SCARD visitors:set
(integer) 1000000
$ redis-cli MEMORY USAGE visitors:set SAMPLES 0
(integer) 48388640

100만 명에 48,388,640바이트, 약 48MB입니다. 하루치가 이 크기이고, 날마다 따로 보관하면 그만큼 쌓입니다.

HyperLogLog가 세는 방법

HyperLogLog는 원소를 저장하지 않고 해시값의 모양만 기억합니다. Redis 소스의 hyperloglog.c를 따라가면 이렇습니다.

원소 64비트 해시 하위 14비트 남은 50비트 레지스터 16384개 PFCOUNT 추정

원소를 MurmurHash64A로 64비트 해시값으로 바꿉니다. 같은 원소는 언제나 같은 해시가 됩니다.

하위 14비트로 레지스터 하나를 고릅니다. 2의 14제곱, 16,384개입니다.

남은 비트를 아래쪽부터 보면서 처음 1이 나올 때까지의 0의 개수에 1을 더합니다. 레지스터는 지금까지 본 가장 큰 값만 남깁니다. 0이 길게 이어지는 해시는 드물기 때문에, 큰 값이 보였다는 것은 그만큼 많은 원소를 봤다는 뜻입니다.

PFCOUNT는 레지스터 값들의 분포로 개수를 추정합니다. Redis는 Otmar Ertl의 추정식을 씁니다.1

해시의 하위 비트와 나머지 비트를 직접 바꿔 보면 두 역할이 구분됩니다. “같은 후보 값, 다른 번호”를 누르면 후보 값은 그대로인데 레지스터 번호만 바뀝니다. 기존 값보다 작은 후보는 저장하지 않습니다.

이 해시는 어느 레지스터를 바꿀까요?

하위 14비트: 레지스터남은 50비트: 연속된 0의 수 + 1

14번 비트에서 63번 방향으로 읽습니다.

레지스터 번호
42
후보 값
5
max(기존 값, 후보 값)
5

후보 값 5는 기존 값 5와 같습니다. 레지스터는 바뀌지 않습니다.

실제 사용자 ID의 해시가 아닌 구성한 예시입니다. 0번이 최하위 비트입니다. Redis 7.2.4 hllPatLen의 비트 선택 규칙을 적용하며 PFCOUNT를 실행하지 않습니다.

남은 비트가 모두 0인 경우도 있습니다. hllPatLen(Redis 7.2.4)의 규칙은 검사할 비트 뒤에 종료용 1을 붙여 후보 값이 51에서 멈추도록 합니다. 위 “모든 비트가 0” 예시에서는 남은 50비트를 전부 검사하고 이 종료용 비트에서 멈춥니다. 이 후보 값 자체가 방문자 수는 아닙니다.

레지스터 하나는 6비트이므로 16,384 × 6비트 = 12,288바이트이고, 16바이트 헤더가 붙어 12,304바이트입니다. 잰 값도 같습니다.

퀴즈레지스터 갱신을 확인합니다

답을 고르면 해설이 나옵니다.

1문제 중 0개 맞힘

  1. 한 사용자가 같은 날 여러 번 방문합니다. 같은 ID를 PFADD할 때마다 추정치가 늘어납니까?

Terminal window
$ redis-cli STRLEN visitors:hll
(integer) 12304
$ redis-cli MEMORY USAGE visitors:hll SAMPLES 0
(integer) 14392

같은 100만 명을 SET보다 약 3,400분의 1 크기로 셉니다.

오차는 얼마나

표준 오차는 레지스터 수 mm으로 정해집니다.

σ≈1.04m=1.0416384=1.04128≈0.81%\sigma \approx \frac{1.04}{\sqrt{m}} = \frac{1.04}{\sqrt{16384}} = \frac{1.04}{128} \approx 0.81\%

원소 수를 바꿔 가며 잰 결과입니다.

원소 수PFCOUNT오차문자열MEMORY USAGE
1001000.00%283 B440 B
1,0001,007+0.70%1,910 B2,616 B
10,00010,089+0.89%12,304 B14,392 B
100,00099,471−0.53%12,304 B14,392 B
1,000,000999,674−0.03%12,304 B14,392 B
100 1천 1만 10만 100만 0 0.2 0.4 0.6 0.8 1 % PFCOUNT 오차의 크기 (%)
측정한 오차표준 오차 0.81%

1만 개에서는 0.89%로 표준 오차 0.81%(선)보다 컸습니다. 표준 오차는 상한이 아니라 오차가 흔히 그 정도라는 뜻이어서, 한 번 잰 값은 넘어설 수 있습니다. 100만 개에서는 0.03%였습니다.

작을 때는 더 작게

원소가 적을 때 Redis는 레지스터 16,384개를 다 펼치지 않는 희소(sparse) 표현을 씁니다. 100개일 때 283바이트, 1,000개일 때 1,910바이트였고, 1만 개에서는 12,304바이트의 밀집(dense) 표현으로 바뀌어 있었습니다. 바뀌는 기준은 hll-sparse-max-bytes입니다.2

코드에서 쓰기

방문할 때마다 그날의 키에 넣고, 셀 때는 날짜 키를 여러 개 함께 넘깁니다. 예시는 Go와 go-redis v9입니다.

visitors.go
func Visit(ctx context.Context, rdb *redis.Client, day, user string) error {
return rdb.PFAdd(ctx, "visitors:"+day, user).Err()
}
func Unique(ctx context.Context, rdb *redis.Client, days ...string) (int64, error) {
keys := make([]string, len(days))
for i, d := range days {
keys[i] = "visitors:" + d
}
return rdb.PFCount(ctx, keys...).Result()
}

방문마다 그날 키에 PFADD합니다. 같은 사용자가 여러 번 와도 개수는 늘지 않습니다.

PFCOUNT에 키를 여러 개 넘기면 합집합의 크기를 추정합니다. 일주일의 고유 방문자는 날짜 키 일곱 개로 셉니다. 합친 결과를 계속 쓸 거라면 PFMERGE로 새 키에 저장해 둘 수 있습니다.

정확한 수가 꼭 필요한 곳, 예를 들어 과금이라면 SET이나 데이터베이스로 세야 합니다. 위 측정에서는 오차가 모두 1% 안쪽이었지만, 표준 오차 0.81%도 실제 오차의 상한은 아닙니다. 대시보드처럼 근사 집계를 받아들이는 곳에서는 HyperLogLog로 메모리를 아낄 수 있습니다. 오차가 반드시 1% 이하여야 하는 요구사항을 HLL만으로 보장하면 안 됩니다.

퀴즈방문자 집계를 설계한다면

답을 고르면 해설이 나옵니다.

3문제 중 0개 맞힘

  1. 날짜별 HLL로 일주일의 고유 방문자를 셉니다. 여러 날 방문한 사용자를 중복해서 세지 않으려면 어떻게 합니다?

  2. 측정 표에서 오차가 0.89%로 나왔습니다. 표준 오차 0.81%보다 크다는 이유만으로 구현 버그라고 판단할 수 있습니까?

  3. 과금용으로 정확한 고유 사용자 수와 사용자 목록이 필요합니다. HLL만 저장해도 됩니까?

각주

  1. Otmar Ertl, “New cardinality estimation algorithms for HyperLogLog sketches”, arXiv:1702.01284. Redis 소스의 hllSigma 함수 주석이 이 논문을 가리킵니다. ↩

  2. 이 글을 잰 환경에서 CONFIG GET hll-sparse-max-bytes는 3000을 돌려줬습니다. ↩

~/blog/redis-hyperloglog/en.mdx

Redis HyperLogLog: counting a million users in 14 KB

Counting unique visitors with a SET takes 48 MB for a million; HyperLogLog takes 14 KB. How it counts, and how far off it is, measured.

Some questions only need how many, not who: unique visitors in a day, for one. Every number in this post was measured on Redis 7.2.4 in Docker (official image, jemalloc) loaded with user:0 through user:999999.

Counting exactly

A SET gives the exact count. In exchange it has to hold every member.

Terminal window
$ redis-cli SCARD visitors:set
(integer) 1000000
$ redis-cli MEMORY USAGE visitors:set SAMPLES 0
(integer) 48388640

A million members take 48,388,640 bytes, about 48 MB. That is one day; keep a set per day and it adds up.

How HyperLogLog counts

HyperLogLog stores no members, only the shape of their hashes. Following hyperloglog.c in the Redis source:

member 64-bit hash low 14 bits remaining 50 bits 16384 registers PFCOUNT estimate

Each member is hashed to 64 bits with MurmurHash64A. The same member always gets the same hash.

The low 14 bits pick one register: 2 to the 14th, 16,384 of them.

The remaining bits are read from the bottom up, counting the zeros before the first 1, plus one. A register keeps only the largest value it has seen. Long runs of zeros are rare, so seeing a large value means many members have gone past.

PFCOUNT estimates the count from how the register values are spread. Redis uses Otmar Ertl’s estimator.1

Changing the low bits and the remaining bits makes their roles visible. Choose “Same rank, another register”: the candidate rank stays the same while the register index changes. A candidate smaller than the stored value is not written.

Which register does this hash change?

Low 14 bits: registerRemaining 50 bits: zero run + 1

Read from bit 14 toward bit 63.

Register index
42
Candidate rank
5
After max(previous, rank)
5

Rank 5 equals the stored 5. The register does not change.

Constructed hashes, not hashes of real user IDs. Bit 0 is the least significant bit. This applies the bit-selection rule in Redis 7.2.4 hllPatLen; it does not run PFCOUNT.

The remaining bits can also all be zero. hllPatLen in Redis 7.2.4 appends a sentinel 1 beyond the scanned bits, capping the rank at 51. The “All zero bits” example scans all 50 remaining bits before reaching that sentinel. This candidate rank is not a visitor count.

A register is 6 bits, so 16,384 × 6 bits is 12,288 bytes, and a 16-byte header makes 12,304. The measurement agrees.

QuizCheckpoint: updating a register

Choose an answer to see the explanation.

0 of 1 right

  1. A user visits several times in one day. Does each PFADD of the same ID increase the estimate?

Terminal window
$ redis-cli STRLEN visitors:hll
(integer) 12304
$ redis-cli MEMORY USAGE visitors:hll SAMPLES 0
(integer) 14392

The same million members, counted in about 1/3,400 of the space the SET takes.

How far off it is

The standard error is set by the number of registers mm:

σ≈1.04m=1.0416384=1.04128≈0.81%\sigma \approx \frac{1.04}{\sqrt{m}} = \frac{1.04}{\sqrt{16384}} = \frac{1.04}{128} \approx 0.81\%

Measured at several sizes:

MembersPFCOUNTErrorStringMEMORY USAGE
1001000.00%283 B440 B
1,0001,007+0.70%1,910 B2,616 B
10,00010,089+0.89%12,304 B14,392 B
100,00099,471−0.53%12,304 B14,392 B
1,000,000999,674−0.03%12,304 B14,392 B
100 1k 10k 100k 1M 0 0.2 0.4 0.6 0.8 1 % Size of the PFCOUNT error (%)
measured errorstandard error, 0.81%

At 10,000 members the error was 0.89%, above the 0.81% standard error (the line). A standard error is the typical size of the error, not a ceiling, so a single measurement can go past it. At a million it was 0.03%.

Smaller when small

With few members, Redis uses a sparse representation that does not lay out all 16,384 registers. It was 283 bytes at 100 members and 1,910 bytes at 1,000; by 10,000 it had switched to the 12,304-byte dense representation. The switch is set by hll-sparse-max-bytes.2

Using it from code

Add each visit to that day’s key; to count, pass several day keys at once. The example is Go with go-redis v9.

visitors.go
func Visit(ctx context.Context, rdb *redis.Client, day, user string) error {
return rdb.PFAdd(ctx, "visitors:"+day, user).Err()
}
func Unique(ctx context.Context, rdb *redis.Client, days ...string) (int64, error) {
keys := make([]string, len(days))
for i, d := range days {
keys[i] = "visitors:" + d
}
return rdb.PFCount(ctx, keys...).Result()
}

Every visit is a PFADD to that day’s key. The same user visiting twice does not raise the count.

Given several keys, PFCOUNT estimates the size of their union. A week’s unique visitors are seven day keys. If the union will be read again and again, PFMERGE can store it under a new key.

Where the exact number matters, billing for example, count with a SET or a database. All the measurements above had errors under 1%, but neither those observations nor the 0.81% standard error bound future errors. HyperLogLog saves memory for dashboards that accept estimates. It does not guarantee a requirement that error must always stay within 1%.

QuizDesigning a visitor counter

Choose an answer to see the explanation.

0 of 3 right

  1. You keep one HLL per day. How do you estimate weekly unique visitors without counting repeat visitors once per day?

  2. The measurement table reports 0.89% error. Does exceeding the 0.81% standard error alone prove an implementation bug?

  3. Billing requires both an exact unique-user count and the user list. Can you store only an HLL?

Notes

  1. Otmar Ertl, “New cardinality estimation algorithms for HyperLogLog sketches”, arXiv:1702.01284. The comment on hllSigma in the Redis source points to it. ↩

  2. On the machine these numbers come from, CONFIG GET hll-sparse-max-bytes returned 3000. ↩

ko.mdx

단축키Keyboard

/ ⌘K
글 검색Search posts
t
밝은/어두운 테마Light or dark theme
l
한국어/영어, 읽던 자리 유지Korean or English, keeping your place
[ ]
이전/다음 절Previous or next section
?
이 목록This list

↑↓ 이동move↵ 열기openesc 닫기close