Redis 내부 인코딩 — ziplist, listpack, skiplist의 동작 원리
Redis는 같은 Hash 타입이라도 데이터 크기에 따라 내부 저장 방식이 달라진다는데, 왜 그런 설계를 했을까요?
개념 정의
Redis의 **내부 인코딩(Internal Encoding)**은 논리적 데이터 타입(String, Hash, List 등) 아래에서 실제 데이터를 저장하는 물리적 자료구조입니다. Redis는 데이터 크기에 따라 메모리 효율적인 인코딩과 접근 속도가 빠른 인코딩 사이를 자동으로 전환합니다.
왜 필요한가
모든 데이터를 항상 hashtable이나 skiplist에 저장하면 접근은 빠르지만 메모리를 많이 사용합니다. 반대로 모든 데이터를 압축하면 메모리는 절약되지만 O(N) 탐색이 필요합니다.
Redis의 해법은 원소가 적을 때는 압축 인코딩, 많아지면 범용 인코딩으로 자동 전환하는 것입니다.
# 인코딩 확인 명령어
OBJECT ENCODING mykey
# Hash의 인코딩 변화 관찰
HSET small_hash field1 "short"
OBJECT ENCODING small_hash
# "listpack" ← 원소가 적으므로 압축 인코딩
HSET big_hash field1 "a]very_long_value_that_exceeds_64_bytes..."
OBJECT ENCODING big_hash
# "hashtable" ← 값이 크므로 범용 인코딩
인코딩별 사용 타입 정리
| 논리적 타입 | 소규모 인코딩 | 대규모 인코딩 | 전환 조건 |
|---|---|---|---|
| String | int / embstr | raw | 44바이트 초과 시 |
| List | listpack | quicklist | 128개 또는 64바이트 초과 |
| Hash | listpack | hashtable | 128개 또는 64바이트 초과 |
| Set | intset / listpack | hashtable | 128개 초과 또는 정수가 아닌 원소 |
| Sorted Set | listpack | skiplist + hashtable | 128개 또는 64바이트 초과 |
ziplist — 과거의 압축 리스트
Redis 7.0 이전에 사용된 컴팩트 자료구조입니다. 현재는 listpack으로 대체되었지만, 이해하면 listpack의 개선점을 파악할 수 있습니다.
메모리 레이아웃
┌──────┬──────┬─────────┬─────────┬─────────┬────┐
│ zlbytes│ zltail│ zllen │ entry1 │ entry2 │ zlend│
│ 4bytes │ 4bytes│ 2bytes │ ... │ ... │ 1byte│
└──────┴──────┴─────────┴─────────┴─────────┴────┘
각 entry의 구조입니다.
┌──────────┬──────────┬──────┐
│ prevlen │ encoding │ data │
│ 1 or 5B │ 1-5B │ ... │
└──────────┴──────────┴──────┘
Cascading Update 문제
prevlen 필드는 이전 엔트리의 길이를 저장합니다.
- 이전 엔트리가 254바이트 미만이면
prevlen은 1바이트 - 254바이트 이상이면
prevlen은 5바이트
문제는 한 엔트리가 커지면 다음 엔트리의 prevlen이 1→5바이트로 바뀌고, 그 엔트리가 커지면 또 다음 엔트리의 prevlen이 바뀌는 연쇄 반응이 발생한다는 것입니다.
[entry A: 253B] [entry B: 253B] [entry C: 253B]
↓ entry A가 254B로 커짐
[entry A: 254B] [entry B: prevlen 5B → 258B] [entry C: prevlen 5B → 258B]
↑ cascading! ↑ cascading!
최악의 경우 O(N^2)의 재할당이 발생할 수 있습니다.
listpack — ziplist의 진화 (Redis 7.0+)
listpack은 ziplist의 cascading update 문제를 해결한 자료구조입니다.
핵심 차이: prevlen 제거
ziplist entry: [prevlen | encoding | data]
listpack entry: [encoding | data | backlen]
listpack은 prevlen 대신 **자기 자신의 길이(backlen)**를 뒤에 저장합니다. 역방향 순회 시 현재 엔트리의 backlen을 읽어서 이전 엔트리의 시작 위치를 계산합니다.
이 설계로 한 엔트리의 크기가 변해도 다른 엔트리에 영향을 주지 않습니다.
listpack의 메모리 레이아웃
┌──────────┬─────────┬─────────┬─────────┬───────┐
│ tot-bytes│ entry1 │ entry2 │ entry3 │ LP_EOF│
│ 4bytes │ ... │ ... │ ... │ 0xFF │
└──────────┴─────────┴─────────┴─────────┴───────┘
entry 구조:
┌──────────┬──────┬─────────┐
│ encoding │ data │ backlen │
└──────────┴──────┴─────────┘
성능 특성
- 조회: O(N) — 순차 탐색
- 삽입/삭제: O(N) — 이후 데이터 이동 필요
- 메모리: 매우 효율적 — 포인터 오버헤드 없음
원소가 적을 때(기본 128개 이하)는 O(N)이어도 N이 작으므로 메모리 절약이 더 이득입니다.
quicklist — List의 내부 인코딩
Redis의 List 타입은 quicklist를 사용합니다. quicklist는 listpack 노드들의 이중 연결 리스트입니다.
구조
quicklist
┌─────────────────────────────────────────────────┐
│ head ──→ [listpack] ←→ [listpack] ←→ [listpack] │
│ ← tail │
└─────────────────────────────────────────────────┘
설정
# 각 listpack 노드의 최대 크기
# -1: 4KB, -2: 8KB(기본), -3: 16KB, -4: 32KB, -5: 64KB
list-max-listpack-size -2
# 중간 노드 압축 (양쪽 끝은 압축하지 않음)
# 0: 압축 안 함(기본), 1: 양쪽 1개씩 제외하고 압축, ...
list-compress-depth 0
왜 이런 설계를 했을까?
- 순수 연결 리스트: 노드당 포인터 오버헤드 (prev + next = 16바이트)
- 순수 배열: 중간 삽입/삭제 시 O(N) 이동
- quicklist: listpack의 메모리 효율 + 연결 리스트의 유연성
LPUSH/RPUSH: O(1) — 양쪽 끝의 listpack에 삽입
LINDEX n: O(N) — listpack 노드를 순회
LRANGE: O(S+N) — S: 시작점까지, N: 범위 크기
skiplist — Sorted Set의 내부 인코딩
원소가 많은 Sorted Set은 skiplist + hashtable 조합을 사용합니다.
skiplist의 기본 구조
일반 연결 리스트에 확률적 다단계 인덱스를 추가한 자료구조입니다.
Level 3: HEAD ──────────────────────────────→ 50 ──────────→ NIL
Level 2: HEAD ──────────→ 20 ──────────────→ 50 ──→ 70 ──→ NIL
Level 1: HEAD ──→ 10 ──→ 20 ──→ 30 ──→ 40 → 50 ──→ 70 ──→ NIL
Level 0: HEAD → 5 → 10 → 20 → 25 → 30 → 40 → 50 → 60 → 70 → NIL
확률적 레벨 결정
// Redis 내부 구현 (단순화)
#define ZSKIPLIST_MAXLEVEL 32 // 최대 레벨
#define ZSKIPLIST_P 0.25 // 승격 확률
int randomLevel() {
int level = 1;
while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level++;
return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
레벨 분포 확률입니다.
| 레벨 | 확률 | 기대 노드 비율 |
|---|---|---|
| 1 | 75% | 100% (모든 노드) |
| 2 | 18.75% | 25% |
| 3 | 4.69% | 6.25% |
| 4 | 1.17% | 1.56% |
왜 B-Tree가 아닌 skiplist인가?
Redis 공식 답변에서 제시한 이유입니다.
- 구현이 단순: skiplist는 B-Tree보다 구현과 디버깅이 쉽습니다
- 범위 쿼리 효율:
ZRANGEBYSCORE같은 범위 연산에서 skiplist는 시작점을 찾은 후 연결 리스트를 따라가면 됩니다 - 메모리 효율: 포인터 배열만 추가하므로 B-Tree의 노드 관리보다 가벼울 수 있습니다
- 동시 수정에 유리: CAS 기반 lock-free 구현이 가능합니다 (현재 싱글 스레드이지만 확장성 고려)
skiplist + hashtable 이중 구조
Sorted Set "leaderboard"
├── skiplist: score 기준으로 정렬 (범위 쿼리용)
│ Level 2: ... → (alice, 100) ──────────→ (dave, 400) → ...
│ Level 1: ... → (alice, 100) → (bob, 200) → (dave, 400) → ...
│ Level 0: ... → (alice, 100) → (bob, 200) → (charlie, 300) → (dave, 400) → ...
│
└── hashtable: member → score 매핑 (O(1) 점수 조회용)
alice → 100
bob → 200
charlie→ 300
dave → 400
ZSCORE member: hashtable에서 O(1) 조회ZRANGEBYSCORE min max: skiplist에서 O(log N + M) 범위 탐색ZADD member score: 둘 다 업데이트
인코딩 전환 설정
# Hash: listpack → hashtable 전환 조건
hash-max-listpack-entries 128 # 필드 수 초과 시
hash-max-listpack-value 64 # 필드/값 바이트 초과 시
# Sorted Set: listpack → skiplist 전환 조건
zset-max-listpack-entries 128
zset-max-listpack-value 64
# Set: intset → hashtable 전환 조건
set-max-intset-entries 512 # 정수 원소 수 초과 시
# List: quicklist 내 listpack 크기
list-max-listpack-size -2 # 각 노드 최대 8KB
전환은 단방향
중요한 점은 인코딩 전환은 소규모 → 대규모 방향으로만 발생한다는 것입니다. 한번 hashtable로 전환되면 원소를 줄여도 listpack으로 돌아가지 않습니다.
# Hash에 129개 필드를 추가하면 hashtable로 전환
# 이후 필드를 삭제해서 10개만 남아도 hashtable 유지
OBJECT 명령어로 인코딩 확인
# 인코딩 확인
OBJECT ENCODING key
# 참조 카운트 (내부 객체 공유)
OBJECT REFCOUNT key
# 마지막 접근 이후 유휴 시간 (초)
OBJECT IDLETIME key
# 접근 빈도 (LFU 정책 사용 시)
OBJECT FREQ key
# OBJECT HELP로 사용 가능한 서브커맨드 확인
OBJECT HELP
정리
Redis의 내부 인코딩 시스템은 "적을 때는 절약하고, 많아지면 속도를 우선한다"는 설계 철학을 따릅니다.
- listpack: ziplist의 cascading update 문제를 해결한 컴팩트 구조 (7.0+)
- quicklist: listpack 노드들의 이중 연결 리스트 (List 타입)
- skiplist: 확률적 다단계 인덱스 (Sorted Set의 범위 쿼리용)
- 인코딩 전환은 자동 + 단방향(소규모→대규모)으로 이루어집니다
OBJECT ENCODING으로 현재 인코딩을 확인하고, 설정값을 조정하여 메모리 효율을 최적화할 수 있습니다