Redis 내부 인코딩 — ziplist, listpack, skiplist의 동작 원리

# 인코딩 확인 명령어
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"  ← 값이 크므로 범용 인코딩

┌──────┬──────┬─────────┬─────────┬─────────┬────┐
│ zlbytes│ zltail│ zllen   │ entry1  │ entry2  │ zlend│
│ 4bytes │ 4bytes│ 2bytes  │ ...     │ ...     │ 1byte│
└──────┴──────┴─────────┴─────────┴─────────┴────┘

┌──────────┬──────────┬──────┐
│ prevlen  │ encoding │ data │
│ 1 or 5B  │ 1-5B     │ ...  │
└──────────┴──────────┴──────┘

[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!

ziplist entry:  [prevlen | encoding | data]
listpack entry: [encoding | data | backlen]

┌──────────┬─────────┬─────────┬─────────┬───────┐
│ tot-bytes│ entry1  │ entry2  │ entry3  │ LP_EOF│
│ 4bytes   │ ...     │ ...     │ ...     │ 0xFF  │
└──────────┴─────────┴─────────┴─────────┴───────┘

entry 구조:
┌──────────┬──────┬─────────┐
│ encoding │ data │ backlen │
└──────────┴──────┴─────────┘

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

LPUSH/RPUSH: O(1) — 양쪽 끝의 listpack에 삽입
LINDEX n:    O(N) — listpack 노드를 순회
LRANGE:      O(S+N) — S: 시작점까지, N: 범위 크기

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;
}

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

# 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

# Hash에 129개 필드를 추가하면 hashtable로 전환
# 이후 필드를 삭제해서 10개만 남아도 hashtable 유지

# 인코딩 확인
OBJECT ENCODING key

# 참조 카운트 (내부 객체 공유)
OBJECT REFCOUNT key

# 마지막 접근 이후 유휴 시간 (초)
OBJECT IDLETIME key

# 접근 빈도 (LFU 정책 사용 시)
OBJECT FREQ key

# OBJECT HELP로 사용 가능한 서브커맨드 확인
OBJECT HELP