~/blog/redis-listpack/ko.mdx

Redis listpack: 512번째 필드와 513번째 필드 사이

Redis 7에서 작은 hash, set, zset은 listpack 하나에 통째로 들어갑니다. 임계값 한 칸 차이로 메모리가 세 배 뛰고, 한번 바뀐 인코딩은 돌아오지 않으며, 임계값을 올리면 조회가 선형 탐색이 됩니다. Redis 7.2에서 직접 쟀습니다.

Redis의 hash는 작을 때 해시 테이블이 아닙니다. 필드와 값을 연속된 바이트 배열 하나에 차례로 적어 두고, 조회할 때 처음부터 훑습니다. Redis 7.0부터 이 배열의 형식이 ziplist에서 listpack으로 바뀌었습니다. 설정 이름도 hash-max-ziplist-entries에서 hash-max-listpack-entries로 바뀌었고, 옛 이름은 별칭으로 남았습니다.

이 글에서는 왜 형식을 바꿨는지, 그리고 임계값 근처에서 메모리와 지연이 실제로 어떻게 움직이는지 봅니다. 측정은 Redis 7.2.16 공식 Docker 이미지에서 했고, 메모리는 MEMORY USAGE, 서버 쪽 실행 시간은 INFO commandstats의 usec_per_call입니다. 환경은 Apple Silicon 노트북입니다.

ziplist가 바뀐 이유

ziplist의 각 항목은 앞 항목의 길이(prevlen)를 맨 앞에 적습니다. 뒤에서 앞으로 걸어갈 수 있게 하기 위해서입니다. prevlen은 앞 항목이 254바이트 미만이면 1바이트, 이상이면 5바이트입니다.

ziplist: 항목마다 앞 항목의 길이 listpack: 항목마다 자기 길이 새 항목 300B prevlen 1→5B길이 250→254B prevlen 1→5B길이 250→254B prevlen 1→5B ... 새 항목 300Bbacklen 2B 변화 없음 변화 없음

250바이트짜리 항목이 줄지어 있을 때 앞에 큰 항목 하나가 들어가면 문제가 생깁니다. 바로 뒤 항목의 prevlen이 1바이트에서 5바이트로 늘고, 그 항목이 254바이트가 되면서 다음 항목의 prevlen도 늘어나야 합니다. 이것이 끝까지 이어지는 연쇄 갱신(cascading update)입니다. 드물지만 최악의 경우 삽입 한 번이 리스트 전체를 다시 씁니다.

listpack은 앞 항목이 아니라 자기 길이(backlen)를 항목 끝에 적습니다. 뒤에서 걸어갈 때는 바로 앞 항목의 끝에서 그 길이를 읽으면 됩니다. 한 항목의 크기가 바뀌어도 이웃 항목은 그대로이니 연쇄가 생길 구조가 없습니다. Redis 7.0은 hash, zset, 그리고 list(quicklist의 각 노드)에서 ziplist를 모두 listpack으로 바꿨습니다.

퀴즈길이 저장 방식을 확인합니다

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

1문제 중 0개 맞힘

  1. listpack 앞부분에 큰 항목을 넣었습니다. ziplist의 prevlen 연쇄 갱신이 같은 방식으로 생깁니까?

기본 임계값

listpack은 작을 때만 씁니다. Redis 7.2.16의 기본값은 다음과 같습니다.

설정기본값
hash-max-listpack-entries512
hash-max-listpack-value64
zset-max-listpack-entries128
zset-max-listpack-value64
set-max-listpack-entries128
set-max-intset-entries512

필드 수나 값 길이 중 하나만 넘어도 해시 테이블(zset은 skiplist)로 바뀝니다. set은 7.2에서 listpack 인코딩이 새로 생겼고, 원소가 모두 정수면 그보다 앞서 intset을 씁니다.

513번째 필드

값 v12345인 필드를 하나씩 늘리며 MEMORY USAGE를 쟀습니다.

필드 수인코딩바이트필드당
1listpack72
16listpack36823
64listpack1,32821
128listpack2,60820
256listpack5,16820
512listpack10,28820
513hashtable32,92064
1,024hashtable57,44856
"16" "64" "128" "256" "512" "513" "1024" 0 10000 20000 30000 40000 50000 60000 bytes hash 메모리 (바이트), 값 v12345

필드 하나를 더 넣었더니 메모리가 3.2배가 됐습니다. listpack에서는 field:123과 v12345가 길이 헤더와 backlen 몇 바이트만 붙어 나란히 놓이므로 필드당 20바이트 남짓입니다. 해시 테이블에서는 필드와 값이 각각 별도로 할당된 문자열이 되고, 엔트리 구조체와 버킷 배열이 붙어 필드당 60바이트 안팎이 됩니다.

값 길이 쪽 경계도 같은 모양입니다. 필드 100개 hash에서 값 길이만 바꿨습니다.

값 길이인코딩바이트
8listpack1,840
32listpack4,144
63listpack7,216
64listpack8,240
65hashtable12,840
128hashtable20,840

64바이트까지는 listpack이고 65바이트부터 해시 테이블입니다. 경계는 “64 이하”입니다.

set도 같습니다.

원소개수인코딩바이트
문자열128listpack816
문자열129hashtable6,280
정수512intset1,328
정수513hashtable24,712

정수 set은 intset에서 해시 테이블로 바뀔 때 18.6배가 됩니다. intset은 정렬된 정수 배열이라 원소당 2~8바이트밖에 쓰지 않기 때문입니다.

돌아오지 않는 변환

변환은 한 방향입니다. 필드 100개, 1,072바이트인 hash에 65바이트 값을 하나 넣은 뒤 그 필드를 지웠습니다.

단계인코딩바이트
처음listpack1,072
65바이트 값 HSEThashtable5,240
그 필드 HDELhashtable5,128

원인이 사라져도 해시 테이블로 남습니다. Redis는 축소 방향의 변환을 하지 않습니다. 키가 수백만 개인 인스턴스에서 잠깐 긴 값이 들어갔다 나가는 패턴이 있으면 메모리가 계단식으로만 오릅니다. 되돌리려면 키를 다시 써야 합니다. 같은 상태의 키를 DUMP 후 지우고 RESTORE하니 listpack으로 돌아왔습니다. RDB에서 키를 읽어 들일 때 현재 크기를 기준으로 인코딩을 다시 고르기 때문입니다.

임계값을 올리면

메모리가 아까우니 hash-max-listpack-entries를 크게 올리자는 생각이 들 수 있습니다. listpack 조회는 처음부터 훑는 선형 탐색이라 대가가 있습니다. HGET을 첫 필드와 마지막 필드에 대해 각각 5만 번 보내고 서버 쪽 usec_per_call을 봤습니다.

rlp3.sh (발췌)
for f in 1 $n; do
redis-cli config resetstat >/dev/null
redis-benchmark -n 50000 -c 4 -P 16 -q hget h field:$f >/dev/null 2>&1
redis-cli info commandstats | grep cmdstat_hget
done
필드 수인코딩첫 필드 (µs)마지막 필드 (µs)
128listpack0.080.53
512listpack0.082.12
4,096hashtable0.070.07
16,384hashtable0.070.07
4,096listpack (임계값 100000)0.0815.97
16,384listpack (임계값 100000)0.0850.74

기본값 512에서도 마지막 필드는 첫 필드보다 26배 느리지만 절대값은 2µs입니다. 임계값을 올려 16,384개를 listpack에 넣으면 마지막 필드 조회가 50µs가 됩니다. Redis는 명령을 한 스레드에서 처리하므로 이 50µs 동안 다른 클라이언트도 모두 기다립니다. 초당 2만 번 이런 조회가 들어오면 그것만으로 CPU 한 개가 찹니다.

클라이언트에서 잰 초당 요청 수로는 이 차이가 거의 보이지 않았습니다. 로컬 루프백에서도 네트워크 왕복이 0.07µs와 2µs의 차이를 덮기 때문입니다. 서버 쪽 숫자를 봐야 합니다.

임계값은 메모리와 최악 조회 시간을 맞바꾸는 손잡이입니다. 필드를 끝에서 자주 읽는 hash라면 올린 만큼 그대로 느려집니다.

정리

  • ziplist의 연쇄 갱신은 각 항목이 앞 항목의 길이를 적어서 생겼고, listpack은 자기 길이를 적어 구조적으로 없앴습니다.
  • 임계값 한 칸 차이로 hash는 3.2배, 정수 set은 18.6배 커집니다.
  • 해시 테이블로 바뀐 키는 작아져도 돌아오지 않습니다.
  • 임계값을 올리면 메모리를 아끼는 대신 끝쪽 필드 조회가 필드 수에 비례해 느려집니다. 16,384 필드에서 50µs였습니다.

키 하나에 필드가 512개 근처에서 왔다 갔다 한다면 키를 쪼개 512개 아래로 유지하는 쪽이 임계값을 올리는 것보다 안전합니다.

퀴즈작은 hash의 메모리가 뛰었다면

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

3문제 중 0개 맞힘

  1. 기본 설정에서 listpack hash에 짧은 필드와 값을 넣습니다. 필드 수가 512에서 513이 될 때 메모리가 급증하는 이유는 무엇입니까?

  2. 본문 실험처럼 긴 값을 넣어 hash가 해시 테이블이 된 뒤 그 필드를 지웠습니다. 남은 키가 작아지면 자동으로 listpack으로 돌아갑니까?

  3. 메모리를 줄이려고 listpack 필드 수 임계값을 올렸습니다. 끝쪽 필드를 자주 읽는 서비스에서는 무엇을 함께 확인해야 합니까?

~/blog/redis-listpack/en.mdx

Redis listpack: between field 512 and field 513

In Redis 7, small hashes, sets and zsets live in a single listpack. One step past the threshold triples memory, a converted encoding never comes back, and raising the threshold turns lookups into a linear scan. Measured on Redis 7.2.

A small Redis hash is not a hash table. Fields and values are written one after another into a single contiguous byte array, and a lookup scans it from the start. In Redis 7.0 the format of that array changed from ziplist to listpack. The setting hash-max-ziplist-entries became hash-max-listpack-entries, with the old name kept as an alias.

This post covers why the format changed and how memory and latency actually move around the thresholds. Measurements use the official Redis 7.2.16 Docker image: memory from MEMORY USAGE, server-side execution time from usec_per_call in INFO commandstats. The machine is an Apple Silicon laptop.

Why ziplist was replaced

Every ziplist entry starts with the length of the previous entry (prevlen), so the list can be walked backwards. prevlen takes 1 byte if the previous entry is under 254 bytes and 5 bytes otherwise.

ziplist: each entry stores the previous length listpack: each entry stores its own length new entry 300B prevlen 1→5Bsize 250→254B prevlen 1→5Bsize 250→254B prevlen 1→5B ... new entry 300Bbacklen 2B unchanged unchanged

Take a row of 250-byte entries and insert a large one in front. The next entry’s prevlen grows from 1 to 5 bytes, making it 254 bytes, so the entry after it needs a bigger prevlen too. That chain running to the end is the cascading update. It is rare, but in the worst case one insert rewrites the whole list.

listpack stores an entry’s own length (backlen) at its end, not the previous entry’s. Walking backwards reads that length from the end of the preceding entry. Changing one entry’s size leaves its neighbours untouched, so there is nothing to cascade. Redis 7.0 replaced ziplist with listpack for hashes, zsets, and lists (each quicklist node).

QuizCheckpoint: storing entry lengths

Choose an answer to see the explanation.

0 of 1 right

  1. A large entry is inserted near the front of a listpack. Does it trigger the same prevlen cascade as a ziplist?

Default thresholds

listpack is only used while small. The Redis 7.2.16 defaults:

SettingDefault
hash-max-listpack-entries512
hash-max-listpack-value64
zset-max-listpack-entries128
zset-max-listpack-value64
set-max-listpack-entries128
set-max-intset-entries512

Exceeding either the entry count or the value length converts to a hash table (a skiplist for zsets). Sets gained a listpack encoding in 7.2, and if every member is an integer, intset is used before that.

Field 513

I added fields with value v12345 one at a time and measured MEMORY USAGE.

FieldsEncodingBytesPer field
1listpack72
16listpack36823
64listpack1,32821
128listpack2,60820
256listpack5,16820
512listpack10,28820
513hashtable32,92064
1,024hashtable57,44856
"16" "64" "128" "256" "512" "513" "1024" 0 10000 20000 30000 40000 50000 60000 bytes hash memory (bytes), value v12345

One more field made memory 3.2 times larger. In a listpack, field:123 and v12345 sit side by side with only a length header and a few backlen bytes, a little over 20 bytes per field. In a hash table, field and value each become separately allocated strings, plus an entry struct and the bucket array, around 60 bytes per field.

The value-length boundary has the same shape. A 100-field hash with only the value length changed:

Value lengthEncodingBytes
8listpack1,840
32listpack4,144
63listpack7,216
64listpack8,240
65hashtable12,840
128hashtable20,840

Up to 64 bytes it stays listpack; from 65 it is a hash table. The boundary is “64 or less”.

Sets behave the same way.

MembersCountEncodingBytes
strings128listpack816
strings129hashtable6,280
integers512intset1,328
integers513hashtable24,712

An integer set grows 18.6 times going from intset to hash table. An intset is a sorted integer array using only 2–8 bytes per member.

A conversion that does not come back

Conversion only goes one way. I took a 100-field hash of 1,072 bytes, set one 65-byte value, then deleted that field.

StepEncodingBytes
Startlistpack1,072
HSET a 65-byte valuehashtable5,240
HDEL that fieldhashtable5,128

The cause is gone and the key stays a hash table. Redis never converts in the shrinking direction. On an instance with millions of keys, a pattern where long values come and go makes memory climb in steps only. Reverting means rewriting the key. When I ran DUMP on a key in this state, deleted it and RESTOREd it, it came back as listpack, because loading a key from RDB picks the encoding from its current size.

Raising the threshold

Saving memory by raising hash-max-listpack-entries is tempting. A listpack lookup is a linear scan from the start, so there is a cost. I sent 50,000 HGETs each for the first and the last field and read the server-side usec_per_call.

rlp3.sh (excerpt)
for f in 1 $n; do
redis-cli config resetstat >/dev/null
redis-benchmark -n 50000 -c 4 -P 16 -q hget h field:$f >/dev/null 2>&1
redis-cli info commandstats | grep cmdstat_hget
done
FieldsEncodingFirst field (µs)Last field (µs)
128listpack0.080.53
512listpack0.082.12
4,096hashtable0.070.07
16,384hashtable0.070.07
4,096listpack (threshold 100000)0.0815.97
16,384listpack (threshold 100000)0.0850.74

Even at the default of 512, the last field is 26 times slower than the first, but only 2µs in absolute terms. With the threshold raised and 16,384 fields in a listpack, looking up the last field takes 50µs. Redis executes commands on one thread, so every other client waits through those 50µs. At 20,000 such lookups per second, that alone fills a CPU core.

Requests per second measured on the client barely showed this. Even over local loopback, the network round trip hides the gap between 0.07µs and 2µs. You have to look at the server-side numbers.

The threshold is a dial that trades memory against worst-case lookup time. For a hash whose tail fields are read often, raising it slows lookups by exactly as much.

Summary

  • ziplist’s cascading update came from each entry storing the previous entry’s length; listpack stores its own length and removes the problem structurally.
  • One step past the threshold, a hash grows 3.2× and an integer set 18.6×.
  • A key converted to a hash table does not return even after shrinking.
  • Raising the threshold saves memory, but tail-field lookups slow down in proportion to the field count: 50µs at 16,384 fields.

If a key hovers around 512 fields, splitting it to stay below 512 is safer than raising the threshold.

QuizWhen a small hash suddenly grows

Choose an answer to see the explanation.

0 of 3 right

  1. With default settings and short fields and values, why does a listpack hash's memory jump between 512 and 513 fields?

  2. As in the experiment, a long value converts a hash to a hash table, then that field is deleted. Does the smaller surviving key automatically return to listpack?

  3. You raise the listpack field-count threshold to save memory. What should you also check when the service often reads tail fields?

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