Redis 기본 개념 — 왜 메모리이고, 왜 Sorted Set인가

---

1. Redis란 무엇인가

정의

정의: Redis(Remote Dictionary Server)는 메모리 기반의 키-값(Key-Value) 데이터 저장소다. 모든 데이터를 RAM에 저장하므로 디스크 기반 DB(MySQL, PostgreSQL)보다 읽기/쓰기가 수십~수백 배 빠르다.

핵심 포인트:

• Remote = 네트워크를 통해 접근하는 (로컬 변수가 아니라 서버에 있는)
• Dictionary = Key-Value 쌍으로 저장하는 (Python의 dict, Java의 HashMap과 같은 개념)
• Server = 독립 프로세스로 동작하는 서버
• 이름 자체가 "원격에 있는 딕셔너리 서버"라는 뜻이다

왜 Redis인가? -- 속도

일반적인 DB(MySQL)는 디스크에 데이터를 저장한다. 디스크 I/O는 느리다. 반면 Redis는 RAM에 저장한다.

[속도 비교]

MySQL (디스크)
  SELECT * FROM queue WHERE movie_id = 'topgun' ORDER BY created_at LIMIT 100;
  → 디스크 탐색 + 인덱스 조회 + 정렬 = ~5ms

Redis (메모리)
  ZRANGE sessions:{topgun}:waiting 0 99
  → 메모리 직접 접근 = ~0.1ms

50배 차이다. 10만 명이 동시에 대기열에 등록하는 CGV 티켓팅에서, 5ms와 0.1ms의 차이는 서비스 응답 시간을 결정한다.

비교 항목	MySQL (디스크)	Redis (메모리)
읽기 속도	~5ms	~0.1ms
초당 처리량	~10,000 ops	~100,000+ ops
데이터 저장	디스크 (영구)	메모리 (휘발)
재시작 시	데이터 유지	데이터 소멸 (기본)
데이터 구조	테이블/행/열	Key-Value (다양한 구조)

Redis를 쓰는 대표적인 용도

용도	왜 Redis인가	예시
캐시	DB 조회 결과를 메모리에 저장해두면 반복 조회가 빠름	영화 정보, 상영 시간표
세션 저장소	로그인 상태를 빠르게 확인	사용자 인증 토큰
대기열	순서 보장 + 빠른 삽입/조회	CGV 티켓팅 대기열
실시간 순위	Sorted Set으로 자동 정렬	게임 리더보드, 대기열 순번
분산 락	여러 서버에서 동시 접근 제어	동시 접근 제어 (SET NX)
Pub/Sub	실시간 메시지 브로드캐스트	WebSocket 멀티 Pod 메시지 전달

CGV 프로젝트에서는 이 중 대기열, 실시간 순위, 분산 락, Pub/Sub 4가지를 모두 사용한다.

메모리에만 저장하면 서버 죽으면 데이터 날아가는 거 아닌가?

맞다. 기본적으로 Redis는 메모리에만 저장하므로 서버가 재시작되면 데이터가 사라진다. 하지만 이것이 CGV 대기열에서는 문제가 아니다.

[왜 대기열 데이터는 날아가도 되는가]

대기열 데이터의 수명: 티켓팅 오픈 ~ 매진 (약 3~5분)
→ 영구 저장할 필요 없음
→ 서버 장애 시: 사용자에게 "다시 접속해주세요" + 대기열 재등록
→ 대기열 이후의 데이터(예매 확정 등)는 MySQL에 저장 (영구)

정리:
  - Redis = 대기열 (임시 데이터, 빠른 속도 필요)
  - MySQL = 영구 저장이 필요한 데이터 (정확성 필요)
  - 각각의 강점에 맞는 역할 분담

Redis에는 RDB(스냅샷)와 AOF(로그)라는 영속화 옵션이 있다. 하지만 CGV 대기열 용도에서는 영속화를 켤 필요가 없다. 영속화는 성능을 떨어뜨리고, 대기열 데이터는 어차피 수명이 짧다.

AWS ElastiCache: prod 환경에서는 Redis를 직접 설치하지 않고 AWS ElastiCache를 사용한다. ElastiCache는 AWS가 관리하는 Redis 서비스로, 자동 failover(장애 시 Replica가 승격), Multi-AZ 배치, 백업 등을 제공한다. 우리가 Redis 서버 관리를 신경 쓸 필요 없이 연결 주소만 바꾸면 된다 

Redis 메모리 구조 — 왜 메모리이고, 내부에서 무슨 일이 일어나는가

위에서 "메모리에 저장해서 빠르다"고 했다. 그런데 정확히 왜 메모리가 빠른 것인가? "메모리니까 빠르죠"로는 면접에서 통하지 않는다. 하드웨어 레벨에서 이유를 이해하고, Redis 내부에서 명령어 하나가 어떤 경로를 거치는지 따라가 본다.

왜 메모리인가 — 하드웨어 레벨 이유

컴퓨터의 저장 장치에는 속도 계층이 있다. CPU에 가까울수록 빠르고 비싸다:

┌──────────────┐
│  CPU 레지스터  │  ~0.3ns     ← CPU 안에 있음, 가장 빠름
├──────────────┤
│   L1 캐시     │  ~1ns       ← CPU 안에 있음
│   L2 캐시     │  ~4ns
│   L3 캐시     │  ~10ns
├──────────────┤
│   RAM (메모리) │  ~100ns     ← Redis가 여기서 동작
├──────────────┤
│   SSD (디스크) │  ~100,000ns ← 100μs. RAM의 1,000배 느림
├──────────────┤
│   HDD (디스크) │  ~10,000,000ns ← 10ms. RAM의 100,000배 느림
└──────────────┘

핵심은 이것이다:

RAM 접근: ~100ns. SSD 접근: ~100,000ns. 1,000배 차이.

MySQL이 인덱스를 통해 디스크에서 데이터를 읽을 때, 아무리 최적화해도 디스크 I/O가 1번 이상 발생한다. 한 번의 SSD 랜덤 읽기가 100μs다. 반면 Redis는 데이터가 이미 RAM에 있으므로 디스크를 건드릴 필요가 없다.

 

CGV 대기열에서의 차이를 계산하면:

ZRANK sessions:{topgun}:waiting "req-abc:sess-123"

MySQL 방식 (B-Tree 인덱스 + 디스크):
  1. 인덱스 B-Tree 탐색: 디스크 읽기 2~3회 × 100μs = 200~300μs
  2. 데이터 페이지 읽기: 디스크 읽기 1회 × 100μs = 100μs
  3. ORDER BY + LIMIT로 순위 계산: 추가 CPU 연산
  → 총: ~500μs ~ 5ms (인덱스 상태에 따라)

Redis 방식 (Skip List + RAM):
  1. 해시 테이블 조회: RAM 접근 수회 × 100ns = ~300ns
  2. Skip List 탐색: RAM 포인터 따라감 ~17단계 × 100ns = ~2μs
  → 총: ~3μs

→ Redis가 100~1,000배 빠르다
→ 10만 명이 동시에 ZRANK를 호출하면, 이 차이가 서비스 응답 시간을 결정한다

 

Redis가 빠른 진짜 이유는 3가지다:

1. 메모리 (위에서 설명)
   → 모든 데이터가 RAM에 있으므로 디스크 I/O = 0

2. 싱글 스레드 이벤트 루프
   → 스레드 간 컨텍스트 스위칭 없음, Lock 경합 없음
   → "한 번에 하나"를 처리하므로 오히려 빠르다
   → 10만 ops/sec 이상 처리 가능 (대부분의 명령어가 μs 단위이므로)

3. 최적화된 자료구조
   → 아래에서 설명할 Skip List, Hash Table 등
   → 범용 DB가 아니라 특화된 자료구조를 직접 구현

이 3가지가 합쳐져서 Redis가 초당 10만 건 이상을 처리할 수 있다. 이제 2번과 3번을 뒷받침하는 Redis의 내부 구조를 들여다본다.

---

명령어 하나를 따라가며 내부 구조 이해하기

Redis의 내부를 이해하는 가장 좋은 방법은 실제 명령어 하나가 실행되는 경로를 처음부터 끝까지 따라가는 것이다. LevelDB 시리즈(cgv_deep_dive/3.1.md)에서 Get(key)을 Footer → Index Block → Data Block 순서로 따라간 것처럼, 여기서는 CGV에서 가장 자주 실행되는 명령어 하나를 따라간다.

ZRANK sessions:{topgun}:waiting "req-abc:sess-123"
→ "req-abc:sess-123 사용자가 대기열에서 몇 번째인지 알려줘"
→ 사용자가 대기 화면에서 "나는 지금 몇 번째?" 물어볼 때마다 실행

 

이 명령어가 Redis 내부에서 거치는 경로:

ZRANK sessions:{topgun}:waiting "req-abc:sess-123"
  │
  ├─ Step 1. 이벤트 루프가 명령어를 수신
  │
  ├─ Step 2. 전역 dict(해시 테이블)에서 키를 찾음          ← O(1)
  │          hash("sessions:{topgun}:waiting") → bucket 번호
  │
  ├─ Step 3. bucket에서 redisObject를 꺼냄               ← O(1)
  │          type=ZSET 확인, encoding=skiplist 확인
  │
  ├─ Step 4. redisObject의 ptr이 가리키는 zset 구조체 접근
  │          ├─ Hash Table: member→score 매핑
  │          └─ Skip List: score순 정렬 + rank 계산
  │
  ├─ Step 5. Hash Table에서 score 조회                    ← O(1)
  │          "req-abc:sess-123" → 1707120000000
  │
  ├─ Step 6. Skip List에서 rank 계산                      ← O(log N)
  │          span 합산 → 3421
  │
  └─ Step 7. 결과 반환: (integer) 3421

이 전체 과정이 RAM 안에서 일어난다. 디스크를 한 번도 건드리지 않는다.

각 단계를 하나씩 들여다본다.

---

Step 1. 싱글 스레드 이벤트 루프

Redis는 메인 스레드 하나가 모든 클라이언트의 명령어를 순서대로 처리한다.

[Redis 이벤트 루프 — epoll 기반 I/O 다중화]

클라이언트 10만 개가 동시에 연결되어 있어도:

  while (true) {
      events = epoll_wait(...)          // 준비된 소켓들을 한꺼번에 가져옴
      for (event in events) {
          command = readCommand(event)   // 명령어 읽기
          result = executeCommand(command) // 실행 (여기가 핵심)
          writeResponse(event, result)   // 결과 전송
      }
  }

→ 하나의 명령어를 처리하는 데 ~1μs (ZRANK 기준)
→ 1초에 100만 건 처리 가능 (이론상)
→ 실제: 네트워크 오버헤드 포함 ~10만~30만 ops/sec

싱글 스레드라서 느릴 것 같지만, 명령어 하나가 μs 단위로 끝나므로 초당 10만 건 이상을 처리할 수 있다. Lock이 없으므로 컨텍스트 스위칭 오버헤드도 없다.

CGV에서: 10만 명이 동시에 ZRANK를 호출해도, Redis 자체는 병목이 아니다. 10만 ZRANK × ~3μs = 0.3초면 전부 처리 가능하다. 병목은 네트워크와 Pod→Redis 연결이다.

---

Step 2. 전역 해시 테이블 (dict) — O(1) 키 조회

Redis 프로세스가 시작되면 메모리에 하나의 해시 테이블(dict)을 만든다. Redis에 저장된 모든 키가 이 하나의 dict에 들어간다.

Redis 프로세스 메모리
│
└─ redisDb[0]                        ← 기본 데이터베이스
    │
    └─ dict (해시 테이블)
        │
        ├─ bucket[0] → NULL
        ├─ bucket[1] → "sessions:{topgun}:waiting" → redisObject(Sorted Set)
        ├─ bucket[2] → NULL
        ├─ bucket[3] → "session:sess-abc-123" → redisObject(String)
        ├─ bucket[4] → "lock:resource-1" → redisObject(String)
        ├─ ...
        └─ bucket[N] → "active_movies" → redisObject(Set)

동작 원리는 Java의 HashMap과 동일하다:

ZRANK sessions:{topgun}:waiting "req-abc:sess-123"
       ↑ 이 키를 찾아야 한다

1. 해시 함수에 키를 넣는다:
   hash("sessions:{topgun}:waiting") % bucketCount = 1

2. bucket[1]로 바로 점프한다
   → 거기에 dictEntry가 있다:
   ┌──────────────────────────────────────────┐
   │ *key → SDS("sessions:{topgun}:waiting")  │   ← 키 (SDS 문자열)
   │ *val → redisObject                        │   ← 값 (robj 포인터)
   │ *next → NULL                              │   ← 해시 충돌 시 체이닝
   └──────────────────────────────────────────┘

3. 키가 맞는지 문자열 비교 → 맞으면 val(redisObject)을 반환
   → O(1). 키가 10만 개든 100만 개든 동일하다.

왜 O(1)인가: 해시 함수가 키를 bucket 번호로 직접 변환하므로, 전체 키를 순회할 필요가 없다. MySQL의 SELECT ... WHERE key = ?가 B-Tree 인덱스를 타서 O(log N)인 것과 대비된다.

해시 충돌: 다른 키의 해시가 같은 bucket에 매핑되면, *next 포인터로 연결리스트를 만든다(체이닝). 키가 너무 많아져서 체인이 길어지면 dict가 자동으로 rehash(bucket 배열을 2배로 확장)한다. 이 rehash가 "점진적(incremental)"으로 일어나는 것이 Redis의 특징이다 — 한 번에 전부 옮기면 그 순간 서비스가 멈추므로, 명령어 실행할 때마다 조금씩 옮긴다.

---

Step 3. redisObject — 모든 값의 16바이트 헤더

dict에서 찾은 값은 항상 redisObject라는 16바이트 헤더로 감싸져 있다. 이 헤더가 Redis 타입 시스템의 핵심이다.

// Redis 소스코드 (server.h)
typedef struct redisObject {
    unsigned type:4;         // STRING, LIST, SET, ZSET, HASH (5가지)
    unsigned encoding:4;     // 실제 내부 구현 방식
    unsigned lru:24;         // 마지막 접근 시간 (LRU/LFU 만료용)
    int refcount;            // 참조 카운트
    void *ptr;               // ← 실제 데이터를 가리키는 포인터
} robj;

왜 이 구조가 중요한가:

ZRANK sessions:{topgun}:waiting "req-abc:sess-123"

Step 3에서 redisObject를 꺼내면:
┌──────────────────────┐
│ type     = ZSET (4)  │ ← "이건 Sorted Set이다"
│ encoding = skiplist   │ ← "내부적으로 Skip List + Hash Table이다"
│ lru      = 1707120… │ ← "마지막으로 접근한 시간"
│ refcount = 1         │
│ ptr ─────────────────┼──→ zset 구조체 (Skip List + Hash Table)
└──────────────────────┘

1) type 확인 → ZSET이 맞으므로 ZRANK 실행 가능
   만약 type이 STRING이면? → "(error) WRONGTYPE" 반환
   redis_02에서 WRONGTYPE 에러 방어가 필요한 이유가 바로 이것이다.
   redisTemplate.type(key).name()이 O(1)인 것도 이 헤더 덕분 — ptr을 안 따라가도 type 필드만 읽으면 된다.

2) encoding 확인 → skiplist이므로 Skip List API를 사용
   만약 encoding이 listpack이면? → 다른 API를 사용 (작은 데이터용 최적화)

3) ptr → 실제 자료구조로 이동 (Step 4)

다른 키의 예시도 보자:

"session:sess-abc-123" 키의 redisObject:
┌──────────────────────┐
│ type     = STRING    │
│ encoding = embstr    │ ← 44바이트 이하 문자열 (메모리 최적화)
│ ptr ─────────────────┼──→ "1" (SDS 문자열)
└──────────────────────┘

"sessions:{topgun}:active" 키의 redisObject:
┌──────────────────────┐
│ type     = ZSET      │
│ encoding = skiplist   │ ← 128명 이상이니까 skiplist
│ ptr ─────────────────┼──→ zset 구조체
└──────────────────────┘

---

Step 3.5. encoding 자동 전환

Redis는 데이터 크기에 따라 내부 인코딩을 자동으로 전환한다.

Sorted Set의 인코딩:
  멤버 128개 이하 + 각 64 bytes 이하 → listpack (메모리 절약)
  그 이상 → skiplist + hashtable (성능 우선)

CGV 대기열: 10만 명 → 항상 skiplist
→ 인코딩 전환을 신경 쓸 필요 없다. 항상 skiplist이다.
→ 중요한 것은 skiplist의 O(log N) 성능 특성뿐이다.

---

Step 4~6. ptr이 가리키는 실제 자료구조

redisObject의 ptr을 따라가면 zset 구조체가 나온다:

zset 구조체:
┌──────────────────────────────────┐
│ zset                              │
│ ├─ *dict → Hash Table            │  ← member→score 매핑 (O(1) 조회)
│ └─ *zsl  → Skip List            │  ← score순 정렬, rank 계산 (O(log N))
└──────────────────────────────────┘

이 두 자료구조의 상세 동작은 아래 Sorted Set 내부 구조 섹션에서 CGV 5명의 예시로 하나씩 설명한다.

ZRANK의 나머지 경로만 요약하면:

Step 5. Hash Table에서 score 조회
   "req-abc:sess-123" → 1707120000000  (O(1))

Step 6. Skip List에서 rank 계산
   최상위 레벨에서 탐색 → span 합산 → rank = 3421  (O(log N))

Step 7. 결과 반환
   → (integer) 3421

---

문자열은 어떻게 저장되나 — SDS와 jemalloc

Redis 문자열은 내부적으로 SDS(Simple Dynamic String)로 저장된다. C의 char*와 달리 길이를 O(1)로 조회하고, 바이너리 안전하다.

[SDS가 CGV에서 의미하는 것]

member: "req-abc-123-def:sess-xyz-789-ghi"  → SDS로 저장
  - len 필드: 문자열 길이를 즉시 반환 (strlen 불필요)
  - 바이너리 안전: UUID에 특수문자가 있어도 안전
  - 메모리: SDS 헤더(3~5 bytes) + 문자열 + '\0' = ~70 bytes

→ SDS 내부 구조는 Redis 코어를 수정하지 않는 한 직접 다룰 일이 없다.
  CGV에서 중요한 것은 "멤버 1개 = ~70 bytes"라는 메모리 크기뿐이다.

메모리 할당은 jemalloc이 담당한다. 2의 거듭제곱 크기(8, 16, 32, 64...)로 메모리를 할당하여 단편화를 줄인다. 이 역시 애플리케이션 레벨에서 직접 관여할 부분이 아니므로, "Redis가 메모리를 효율적으로 관리한다"는 것만 이해하면 된다.

---

전체 그림 — ZRANK 한 번의 전체 경로

지금까지 따라온 경로를 하나로 합치면:

QueueProcessor가 2초 주기로 대기열 처리 중, 특정 사용자의 순번 조회
  ↓
백엔드 서버 → Redis 명령어 전송 (결과를 WebSocket으로 사용자에게 푸시)

ZRANK sessions:{topgun}:waiting "req-abc:sess-123"
  │
  ├─ 1. 이벤트 루프 수신 (epoll)                      ← ~1μs
  │
  ├─ 2. dict에서 키 조회                              ← ~0.3μs
  │     hash("sessions:{topgun}:waiting") % N → bucket[1]
  │     bucket[1] → dictEntry → redisObject(ZSET, skiplist)
  │
  ├─ 3. redisObject 확인                              ← ~0.1μs
  │     type=ZSET ✓, encoding=skiplist
  │     ptr → zset 구조체
  │
  ├─ 4. zset.dict (Hash Table)에서 score 조회          ← ~0.3μs
  │     "req-abc:sess-123" → 1707120000000
  │
  ├─ 5. zset.zsl (Skip List)에서 rank 계산            ← ~2μs
  │     최상위 레벨에서 출발 → span 합산 → rank = 3421
  │
  └─ 6. 결과 반환: (integer) 3421                      ← ~0.3μs

총 소요: ~3~4μs (0.003~0.004ms)
  → 디스크 I/O: 0회
  → 시스템 콜: 0회 (epoll_wait 제외)
  → 전부 RAM 위의 포인터 따라가기

이것이 Redis의 모든 명령어가 거치는 경로다: 이벤트 루프 → dict → redisObject → 실제 자료구조. LevelDB의 Get(key)이 Footer → Index Block → Data Block을 거치며 최소 3번의 디스크 I/O가 필요한 것과 대비된다. Redis는 전부 RAM 위에 있으므로 포인터만 따라가면 끝이다.

CGV에서 Redis 메모리를 얼마나 쓰는가

[10만 대기열의 실제 메모리 계산]

1명당 메모리:
  - dictEntry: 24B (key ptr + val ptr + next ptr)
  - SDS 키: ~50B (키 이름 "sessions:{topgun}:waiting"의 참조)
  - Skip List 노드: ~44B (member ptr + score + backward + level[0])
    + 레벨당 16B 추가 (forward ptr + span)
    평균 레벨 1.33 → ~44 + 0.33 × 16 ≈ 49B
  - Hash Table 엔트리: ~24B (member → score 매핑)
  - SDS 멤버: ~60B ("req-abc-123:sess-xyz-789" + SDS 헤더)
  - jemalloc 오버헤드: ~20%

  1명 합계: ~150B (jemalloc 포함)

10만 명:
  100,000 × 150B = 15MB

→ dev: Redis Pod 512Mi 할당 중 15MB만 사용 / prod: ElastiCache ~1 GiB 중 15MB
→ 대기열은 Redis 메모리의 병목이 아니다
→ 나머지: Active Set, 세션 키 + Redis 자체 오버헤드
→ 이 메모리 사용량은 k6 부하테스트 중 Grafana에서 실시간 확인한다 (→ 2.4 참고)

---

2. Redis 데이터 구조

Redis는 단순한 Key-Value 저장소가 아니다. Value에 다양한 데이터 구조를 저장할 수 있다. 이것이 Redis의 핵심 강점이다.

전체 데이터 구조 비교

데이터 구조	설명	비유	CGV에서의 용도
String	단순 값 (문자열, 숫자)	변수 하나	세션 검증, 좌석 선점 (SET NX), 매진 카운터 (INCR)
List	순서 있는 목록	배열, 큐	(사용 안 함)
Set	중복 없는 집합	HashSet	활성 영화 목록, 예매 확정 좌석 (booked)
Hash	필드-값 쌍의 집합	HashMap, 객체	상영관 메타정보 (theater:{movieId}:info)
Sorted Set	점수(score)로 자동 정렬되는 집합	TreeMap	대기열, 활성 세션

String -- 가장 기본

정의: 하나의 Key에 하나의 값을 저장한다. 값은 문자열, 숫자, JSON 등 무엇이든 될 수 있다. 최대 512MB까지 저장 가능하다.

SET name "홍길동"        → OK
GET name                 → "홍길동"

SET counter 0            → OK
INCR counter             → 1
INCR counter             → 2
GET counter              → "2"

SET user:1234 '{"name":"홍길동","age":25}' EX 3600    → OK (1시간 후 자동 삭제)

핵심 포인트:

• SET key value -- 값 저장
• GET key -- 값 조회
• INCR key -- 숫자를 1 증가 (원자적)
• EX seconds -- TTL(Time To Live) 설정. 지정 시간 후 자동 삭제
• NX -- "Not eXists". 키가 없을 때만 저장 (분산 락에 사용)

CGV 적용 -- 세션 검증:

# 사용자 세션 생성 (1시간 TTL)
SET session:sess-abc-123 "1" EX 3600

# 세션 유효한지 확인
EXISTS session:sess-abc-123    → 1 (있다 = 유효)

# 세션 접근할 때마다 TTL 갱신 (슬라이딩 윈도우)
EXPIRE session:sess-abc-123 3600

분산 락 (Distributed Lock) -- SET NX 활용:

SET NX는 CGV 프로젝트에서 좌석 선점에 사용된다. 대기열의 QueueProcessor 중복 실행 방지는 Spring의 @SchedulerLock(ShedLock)이 담당하며, 이것도 내부적으로 Redis를 저장소로 사용하지만 SET NX를 직접 호출하지는 않는다.

SET NX는 분산 환경에서 동시에 하나의 프로세스만 자원에 접근하도록 보장하는 패턴이다. 여러 Pod/서버가 동시에 같은 작업을 수행하려 할 때, 하나만 성공하고 나머지는 실패시키는 "분산 락"에 핵심적으로 쓰인다.

# 분산 락 예시: 여러 서버가 동시에 같은 리소스에 접근 시도
# SET NX: 키가 없을 때만 저장. 이미 있으면 실패.

SET lock:batch-job-001 "server-A" NX EX 30
→ OK (server-A: 락 획득 성공)

SET lock:batch-job-001 "server-B" NX EX 30
→ (nil) (server-B: 실패. 이미 락이 걸려 있음)

SET lock:batch-job-001 "server-C" NX EX 30
→ (nil) (server-C: 실패)

SET NX는 원자적(atomic)이다. "키가 있는지 확인 + 없으면 저장"이 하나의 연산으로 실행된다. 중간에 다른 요청이 끼어들 수 없다. 이것이 DB의 SELECT + INSERT 조합보다 안전한 이유다.

CGV 좌석 선점 예시 (SET NX 실전 활용):

# 사용자 req-001이 용산 IMAX A-10 좌석 선점
SET seat:{korea-series-g5}:{imax-yongsan}:{A-10} "req-001" NX EX 300
→ OK (req-001: 선점 성공. 5분(300초) 동안 이 좌석을 독점)

# 0.3초 뒤, 사용자 req-002가 같은 좌석 A-10 선점 시도
SET seat:{korea-series-g5}:{imax-yongsan}:{A-10} "req-002" NX EX 300
→ (nil) (req-002: 실패. A-10은 이미 req-001이 점유 중)

# 5분 후 TTL 만료 → 키 자동 삭제 → 다른 사용자가 다시 선점 가능
# 또는 req-001이 결제 완료 후 직접 삭제: DEL seat:{...}:{A-10}

결과: 동시에 10명이 같은 좌석을 클릭해도, 정확히 1명만 선점 성공.
→ 좌석 더블 부킹(double booking) 불가능.
→ TTL 300초(5분)로 자동 해제: 사용자가 결제를 포기해도 좌석이 영구 잠금되지 않는다.

ShedLock vs 좌석 선점: QueueProcessor 단일 실행 보장은 @SchedulerLock(ShedLock)이 담당한다. ShedLock은 내부적으로 Redis에 락 키를 생성하지만, Spring이 관리하므로 개발자가 SET NX를 직접 호출하지 않는다. 좌석 선점은 SET NX를 직접 사용하여 "한 사용자만 자원 점유"를 구현한다.

[SET NX vs DB의 차이]

DB 방식 (위험):
  1. SELECT: 락이 있나? → 없음
  --- 여기서 다른 서버도 "없다"고 확인 ---
  2. INSERT: 내가 락을 잡겠다
  → 두 서버가 동시에 INSERT → 충돌

Redis SET NX (안전):
  1. SET lock:resource "server-A" NX → OK (성공)
  2. SET lock:resource "server-B" NX → nil (실패, 이미 있음)
  → 확인과 저장이 하나의 원자적 연산

왜 NX와 EX를 반드시 함께 써야 하는가:

[EX 없이 SET NX만 사용하면 — 데드락]

1. server-A가 락 획득: SET lock:resource "server-A" NX → OK
2. server-A 크래시 (작업 미완료, DEL 호출 안 됨)
3. lock:resource 키가 영원히 남아있음
→ 아무도 해당 리소스에 접근할 수 없는 "데드락"

[SET NX EX 30 — 자동 안전장치]

1. server-A가 락 획득: SET lock:resource "server-A" NX EX 30 → OK
2. server-A 크래시
3. 30초 후 Redis가 키를 자동 삭제
4. 다른 서버가 락 획득 가능
→ TTL이 "서버 크래시/네트워크 단절" 상황의 안전장치

중요: SET key value NX EX 30은 하나의 원자적 명령어다. SET NX를 먼저 하고 별도로 EXPIRE를 호출하면, 그 사이에 서버가 죽을 경우 TTL이 설정되지 않아 똑같이 데드락이 발생한다.

위험: SET lock:resource "server-A" NX → OK → 서버 크래시 → EXPIRE 실행 안 됨 → 데드락
안전: SET lock:resource "server-A" NX EX 30 → 하나의 명령어로 NX + TTL 동시 설정

List

Redis List는 LPUSH/RPOP으로 FIFO 큐를 만들 수 있다. 하지만 CGV 대기열에서는 사용하지 않는다.

왜 List가 아닌 Sorted Set인가:
  List: "내가 몇 번째?"를 알려면 LPOS → O(N) → 10만 명이면 너무 느림
  Sorted Set: ZRANK → O(log N) → 10만 명이어도 ~17단계 = ~0.01ms

→ 대기열 + 순위 조회를 하나의 자료구조로 해결하려면 Sorted Set이 유일한 선택이다.

Set -- 중복 없는 집합

정의: 순서가 없고, 중복을 허용하지 않는 집합이다. 멤버 존재 여부 확인이 O(1)이다.

SADD fruits "apple"      → 1 (추가됨)
SADD fruits "banana"     → 1
SADD fruits "apple"      → 0 (이미 있음, 무시)

SMEMBERS fruits          → {"apple", "banana"}
SISMEMBER fruits "apple" → 1 (있다)
SCARD fruits             → 2 (개수)

핵심 포인트:

• SADD: 멤버 추가 (중복 무시)
• SMEMBERS: 전체 멤버 조회
• SISMEMBER: 멤버 존재 확인 O(1)
• SCARD: 개수

CGV 적용 -- 활성 영화 목록 + 예매 확정 좌석:

우리 시나리오는 인기 영화 1편에 10만 명이 집중하는 구조다. active_movies Set에는 영화 1개가 들어간다.

# 현재 대기열이 열려있는 영화 등록
SADD active_movies "movie-topgun"

# QueueProcessor가 처리할 영화 목록 조회
SMEMBERS active_movies
→ {"movie-topgun"}

# 티켓팅 종료 시 제거
SREM active_movies "movie-topgun"

예매 확정된 좌석도 Set으로 관리한다 (-> redis_02 키 구조 참고):

# 좌석 예매 확정
SADD booked:{topgun}:{imax-yongsan} "A-01" "A-02" "B-05"

Hash -- 필드-값 쌍

정의: 하나의 Key 안에 여러 필드(field)-값(value) 쌍을 저장한다. Python의 dict, Java의 HashMap과 같다.

HSET user:1234 name "홍길동"
HSET user:1234 age 25
HSET user:1234 email "hong@example.com"

HGET user:1234 name      → "홍길동"
HGETALL user:1234         → {"name": "홍길동", "age": "25", "email": "hong@example.com"}

핵심 포인트:

• HSET/HGET: 필드 단위로 읽기/쓰기
• HGETALL: 모든 필드 조회
• String에 JSON을 저장하는 것보다 개별 필드 접근이 효율적

CGV에서는 Hash를 상영관 메타정보에 사용한다. theater:{movieId}:info 키에 capacity, theaterCount 등의 필드를 저장한다 (-> redis_02 키 구조 참고). 사용자 세션 데이터는 단순("1" 마커)하므로 String으로 충분하다.

Sorted Set (ZSet) -- CGV 대기열의 핵심

정의: 각 멤버(member)에 점수(score)가 붙어 있고, 점수 순서로 자동 정렬되는 집합이다. 중복 멤버는 허용하지 않는다.

# 점수(score) = 타임스탬프, 멤버(member) = 사용자 ID
ZADD waiting 1707120000 "user-A"    → 20:00:00에 등록
ZADD waiting 1707120001 "user-B"    → 20:00:01에 등록
ZADD waiting 1707120002 "user-C"    → 20:00:02에 등록

# 자동으로 점수 순서로 정렬됨
ZRANGE waiting 0 -1 WITHSCORES
→ [("user-A", 1707120000), ("user-B", 1707120001), ("user-C", 1707120002)]

핵심 포인트:

• 멤버(member): 저장되는 값. 중복 불가.
• 점수(score): 64비트 부동소수점 숫자. 정렬 기준. 같은 멤버가 ZADD되면 점수만 업데이트.
• 자동 정렬: 삽입 시점에 정렬 위치가 결정됨. 별도의 ORDER BY 없이 항상 정렬 상태.
• 시간복잡도: 삽입 O(log N), 순위 조회 O(log N), 범위 조회 O(log N + M)

왜 이름이 Z로 시작하는가?

Redis 명령어에서 Sorted Set 관련 명령어는 모두 Z로 시작한다: ZADD, ZRANGE, ZRANK, ZREM, ZCARD...

이유: Set 명령어와 충돌을 피하기 위해서다.

Set 명령어:    SADD, SMEMBERS, SCARD, SREM ...     (S = Set)
Sorted Set:    ZADD, ZRANGE, ZCARD, ZREM ...        (Z = ?)

Set이 이미 S를 차지하고 있으므로, Sorted Set은 다른 접두사가 필요했다. Redis 창시자 Salvatore Sanfilippo가 알파벳 끝인 Z를 선택했다. "ZSet"이라는 내부 명칭에서 온 것으로, Z에 특별한 의미는 없다. 단순히 네이밍 충돌 회피다.

[명령어 접두사 규칙]

S → Set         (SADD, SREM, SMEMBERS, SCARD)
H → Hash        (HSET, HGET, HGETALL, HDEL)
L → List        (LPUSH, LPOP, LRANGE, LLEN)
Z → Sorted Set  (ZADD, ZREM, ZRANGE, ZCARD)

String은 접두사 없음: SET, GET, INCR, DEL

 

Sorted Set 내부 구조 -- Skip List + Hash Table

Sorted Set이 O(log N)으로 빠르게 동작하는 이유는 내부적으로 두 가지 자료구조를 동시에 사용하기 때문이다. 두 구조가 각각 무엇이고 왜 필요한지를, CGV 대기열 5명을 처음부터 넣어보면서 설명한다.

Skip List란 무엇인가 — 일반 리스트의 문제에서 시작

대기열에 5명이 score(타임스탬프) 순으로 정렬되어 있다고 하자.

HEAD → 1000(A) → 1500(B) → 2000(C) → 2300(D) → 3000(E) → NIL

"user-D(score: 2300)를 찾아라" 하면, 앞에서부터 하나씩 가야 한다:

HEAD → A → B → C → D  찾았다!
       (1) (2) (3) (4)  → 4번 이동 (포인터 4개 따라감)

5명이면 괜찮지만, 10만 명이면 최악 10만 번 이동해야 한다. O(N). 이걸 해결하는 게 Skip List다.

Skip List 구축 — 노드를 하나씩 넣어보기

핵심 아이디어: 일반 리스트 위에 "급행 레벨"을 쌓는다. 지하철에 완행/급행/특급이 있는 것과 같다.

새 노드를 삽입할 때 동전 던지기로 레벨을 정한다:

• 앞면 → 한 단계 승격. 한 번 더 던진다.
• 뒷면 → 멈춤.

확률적으로 Level 0만: 50%, Level 1까지: 25%, Level 2까지: 12.5%... 위로 갈수록 노드가 적어진다.

※ 아래 예시는 이해를 위해 p=0.5(동전)로 설명한다. Redis는 실제로 p=0.25(4면체 주사위)를 사용하며, 이유와 차이는 "Redis의 실제 Skip List 구현" 섹션에서 다룬다.

5명이 순서대로 등록되는 과정:

user-A (score: 1000) — 동전 결과: Level 0~1까지

Level 1:  HEAD ──→ 1000(A) ──→ NIL
Level 0:  HEAD ──→ 1000(A) ──→ NIL

같은 user-A 노드 하나가 Level 0과 Level 1 양쪽에 포인터로 연결된다. 복사본이 아니라 하나의 노드에 포인터가 2개(Level 0용, Level 1용) 달린 것이다.

[노드의 실제 구조]

┌──────────────────┐
│ member: "user-A"  │
│ score:  1000      │
│ Level 1 → (다음)  │
│ Level 0 → (다음)  │
└──────────────────┘

→ 레벨이 높을수록 포인터가 많다

 

user-B (score: 1500) — 동전 결과: Level 0만

Level 1:  HEAD ──→ 1000(A) ─────────────→ NIL
Level 0:  HEAD ──→ 1000(A) ──→ 1500(B) ──→ NIL

user-B는 Level 0에만 있다. Level 1에서 보면 B는 건너뛰어진다.

 

user-C (score: 2000) — 동전 결과: Level 0~2까지

Level 2:  HEAD ─────────────────────────→ 2000(C) ──→ NIL
Level 1:  HEAD ──→ 1000(A) ────────────→ 2000(C) ──→ NIL
Level 0:  HEAD ──→ 1000(A) ──→ 1500(B) → 2000(C) ──→ NIL

user-C는 Level 2까지 올라갔다. Level 2에서 보면 세상에 C만 보인다.

 

user-D (score: 2300) — 동전 결과: Level 0만

Level 2:  HEAD ─────────────────────────→ 2000(C) ───────────────→ NIL
Level 1:  HEAD ──→ 1000(A) ────────────→ 2000(C) ───────────────→ NIL
Level 0:  HEAD ──→ 1000(A) ──→ 1500(B) → 2000(C) ──→ 2300(D) ──→ NIL

 

user-E (score: 3000) — 동전 결과: Level 0~1까지

Level 2:  HEAD ──────────────────────→ 2000(C) ──────────────────────→ NIL
Level 1:  HEAD ──→ 1000(A) ────────→ 2000(C) ────────→ 3000(E) ───→ NIL
Level 0:  HEAD ──→ 1000(A) → 1500(B) → 2000(C) → 2300(D) → 3000(E) → NIL

최종 구조 정리:

Level 2:  HEAD ───────────→ C ─────────────→ NIL     (C만 보인다)
Level 1:  HEAD ──→ A ────→ C ────→ E ─────→ NIL     (A, C, E만 보인다)
Level 0:  HEAD ──→ A → B → C → D → E ──→ NIL       (전원 보인다)

각 노드의 레벨:
  user-A: Level 1 (포인터 2개)
  user-B: Level 0 (포인터 1개)  ← 급행 안 섬
  user-C: Level 2 (포인터 3개)  ← 특급까지 섬
  user-D: Level 0 (포인터 1개)  ← 급행 안 섬
  user-E: Level 1 (포인터 2개)

B-Tree처럼 리밸런싱(노드 분할/병합)이 필요 없다. 동전 던지기(확률)만으로 위로 갈수록 노드가 적어지는 구조가 자연스럽게 만들어진다. 이것이 Skip List가 구현이 단순한 이유다.

10만 명이면 레벨 수 = log₂(100,000) ≈ 17. 각 레벨에서 2~3번 이동하므로 약 50번이면 10만 명 중 아무나 찾을 수 있다.

Skip List 탐색 — CGV 실전 예시

ZRANK — "user-D는 몇 번째야?"

사용자가 대기 화면에서 "나는 지금 몇 번째?" 물어보는 상황이다. user-D(score: 2300)를 찾는다. 최상위 레벨에서 시작하여 아래로 내려간다:

Step 1) Level 2, HEAD에서 출발
        → 오른쪽: C(2000)
        → 2000 < 2300이니까 C로 이동 ✓
        → 오른쪽: NIL
        → 더 갈 수 없다. 아래로 내려간다 ↓

Step 2) Level 1, C(2000)에서 계속
        → 오른쪽: E(3000)
        → 3000 > 2300이니까 넘어간다! 아래로 ↓

Step 3) Level 0, C(2000)에서 계속
        → 오른쪽: D(2300)
        → 2300 == 2300, 찾았다! ✓

총 3번 이동으로 도착.

 

이동 경로를 그림으로 보면:

Level 2:  HEAD ──[→ C]────────────→ NIL
                   ↓
Level 1:           C ──[→ E는 넘김]
                   ↓
Level 0:           C ──[→ D] 찾았다!

Level 0에서 HEAD부터 갔으면 HEAD → A → B → C → D로 4번 이동이다. 5명에서는 차이가 작지만 10만 명이면 최악 10만 번 vs Skip List 약 50번, 2,000배 차이다.

 

ZRANGE 0 2 — "대기열 앞에서 3명 줘" (QueueProcessor)

Level 0의 맨 앞에서부터 3개를 순서대로 읽으면 끝이다:

Level 0:  HEAD → A(1000) → B(1500) → C(2000) → ...
                  ^1번째     ^2번째     ^3번째

결과: [user-A, user-B, user-C]
→ 이미 score 순으로 정렬되어 있으므로 별도 정렬 불필요

 

ZRANGEBYSCORE 0 1800 — "score 1800 이하 찾기" (타임아웃 감지)

Level 0에서 앞부터 읽으면서 1800 넘으면 멈춘다:
  → A(1000) ✓ → B(1500) ✓ → C(2000) ✗ STOP

결과: [user-A, user-B]

Hash Table은 뭘 하는가

Skip List는 score 순서로 정렬되어 있다. score로는 빠르게 찾지만, member 이름으로는 못 찾는다:

Skip List에서 "user-D"를 이름으로 찾으려면?
→ score를 모르니까 Level 0에서 하나씩 이름 비교해야 함
→ HEAD → A(user-A ≠ user-D) → B → C → D 찾았다!
→ O(N) 전체 탐색. 10만 명이면 최악 10만 번.

 

이걸 해결하는 게 Hash Table이다. member → score 매핑을 별도로 유지한다:

[Hash Table]

┌─────────────┬───────────┐
│   member     │   score   │
├─────────────┼───────────┤
│  "user-A"   │   1000    │
│  "user-B"   │   1500    │
│  "user-C"   │   2000    │
│  "user-D"   │   2300    │
│  "user-E"   │   3000    │
└─────────────┴───────────┘

ZSCORE waiting "user-D"
→ Hash Table에서 "user-D" 조회 → 즉시 2300 반환 → O(1)

두 구조의 전체 그림

┌─────────────────────────────────────────────────────────────┐
│                    Sorted Set (ZSet)                         │
│                                                             │
│  ┌─────────────────────┐     ┌────────────────────────────┐ │
│  │     Hash Table       │     │        Skip List           │ │
│  │                      │     │                            │ │
│  │  "user-A" → 1000    │     │  L2: HEAD ────→ C ───→ NIL │ │
│  │  "user-B" → 1500    │     │  L1: HEAD → A → C → E→NIL │ │
│  │  "user-C" → 2000    │     │  L0: HEAD→A→B→C→D→E→NIL   │ │
│  │  "user-D" → 2300    │     │                            │ │
│  │  "user-E" → 3000    │     │  (score 순서로 정렬)        │ │
│  └─────────────────────┘     └────────────────────────────┘ │
│                                                             │
│  member로 score 찾기: O(1)    score 순서 조회: O(log N)      │
│  → ZSCORE 명령어              → ZRANGE, ZRANK 명령어         │
└─────────────────────────────────────────────────────────────┘

같은 데이터를 두 구조가 포인터로 공유한다. 복사본이 아니다.

CGV 명령어별 어떤 구조를 사용하는가:

ZADD waiting 2300 "user-D"       → Hash Table에 추가 + Skip List에 삽입 (양쪽)
ZSCORE waiting "user-D"          → Hash Table만 사용 → O(1)
ZRANK waiting "user-D"           → Hash Table로 score 조회 → Skip List로 순위 계산
ZRANGE waiting 0 99              → Skip List만 사용 → Level 0 앞에서 순차 읽기
ZRANGEBYSCORE waiting 0 1800     → Skip List만 사용 → score 범위 탐색
ZREM waiting "user-D"            → Hash Table에서 삭제 + Skip List에서 삭제 (양쪽)

왜 두 개가 필요한가

Hash Table만 있으면:
  ZSCORE "user-D" → O(1) ✓
  ZRANK "user-D"  → 순위? 전체를 정렬해야 함 → O(N log N) ✗
  ZRANGE 0 99     → 상위 100명? 전체를 정렬해야 함 → O(N log N) ✗

Skip List만 있으면:
  ZRANGE 0 99     → O(log N + 100) ✓
  ZRANK "user-D"  → score로 찾으면 O(log N) ✓
  ZSCORE "user-D" → member 이름으로? 전체 탐색 O(N) ✗

둘을 합치면:
  모든 연산이 O(1) 또는 O(log N) ✓

왜 B-Tree가 아니라 Skip List인가?

비교	Skip List	B-Tree
구현 복잡도	상대적으로 단순	복잡 (노드 분할/병합)
삽입/삭제	노드 하나만 수정	트리 리밸런싱 필요
범위 조회	Level 0에서 순차 탐색	리프 노드 순회
메모리	포인터 오버헤드 있음	좀 더 효율적
동시성	부분 잠금 가능	전체 리밸런싱 시 잠금

Redis 창시자는 "Skip List가 B-Tree와 성능은 비슷하면서 구현이 훨씬 단순하고, 범위 조회가 자연스럽다"고 선택 이유를 밝혔다.

Skip List + Hash Table의 "Dual Index 패턴"과 LevelDB와의 비교는 4편 LevelDB 비교에서 상세히 다룬다.

Redis의 실제 Skip List 구현

위 예시에서는 이해를 위해 p=0.5(동전)를 사용했다. Redis의 실제 소스코드는 다르다.

노드의 C 소스코드 구조:

// Redis 소스코드 (server.h)
#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25

typedef struct zskiplistNode {
    sds ele;                         // member 문자열 ("req-abc:sess-123")
    double score;                    // score (타임스탬프)
    struct zskiplistNode *backward;  // 뒤로 가기 포인터 (Level 0 전용)
    struct zskiplistLevel {
        struct zskiplistNode *forward;   // 앞으로 가기 포인터
        unsigned long span;              // 이 포인터가 건너뛴 노드 수
    } level[];                       // ← 가변 길이 배열. 레벨 수만큼 생성됨
} zskiplistNode;

핵심:

• level[]은 가변 배열이다. 레벨 1 노드는 level[0] 하나, 레벨 3 노드는 level[0], level[1], level[2] 세 개를 가진다
• "리스트가 여러 층으로 쌓인 것"이 아니라, 노드 하나가 포인터를 레벨 수만큼 배열로 들고 있는 것이다
• span은 해당 포인터가 건너뛴 노드 수를 기록한다. ZRANK 계산 시 경로상의 span을 합산하면 O(log N)으로 순위를 알 수 있다

[노드 구조 비교]

일반 Linked List 노드:
┌────────┬──────┐
│ value  │ next ─┼──→ 다음 노드
└────────┴──────┘
  포인터 1개

Skip List 노드 — 레벨 3:
┌────────────┬──────────────────────────────┐
│            │ level[2].forward ──→ 먼 노드    │
│ member     │ level[2].span = 4  (4개 건너뜀) │
│ "user-C"   │                                │
│            │ level[1].forward ──→ 중간 노드   │
│ score      │ level[1].span = 2              │
│ 2000       │                                │
│            │ level[0].forward ──→ 바로 다음   │
│            │ level[0].span = 1              │
│            │                                │
│            │ backward ──→ 이전 노드           │
└────────────┴──────────────────────────────┘
  포인터 = 레벨 수 + backward 1개

→ 레벨이 높을수록 메모리를 더 쓴다 (포인터가 많으므로)
→ 대부분의 노드는 레벨 1 (포인터 최소)

 

span으로 ZRANK 계산하는 원리:

Level 2:  HEAD ──(span:3)──→ C ──(span:2)──→ NIL
Level 1:  HEAD ──(span:1)──→ A ──(span:2)──→ C ──(span:2)──→ E → NIL
Level 0:  HEAD ──(span:1)──→ A ──(span:1)──→ B ──(span:1)──→ C → D → E → NIL

ZRANK "user-D" (D의 순위를 구하라):
  Level 2: HEAD → C (span 3 누적)         → 3
  Level 1: C에서 E(3000)는 D(2300)보다 큼 → 아래로
  Level 0: C → D (span 1 누적)            → 3 + 1 = 4
  → rank = 4 - 1 = 3 (0-based)

span 합산만으로 순위 계산 완료. 노드를 하나씩 세지 않아도 된다.

 

레벨 결정 — p=0.25 (4면체 주사위):

// Redis 소스코드 (t_zset.c)
int zslRandomLevel(void) {
    int level = 1;
    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))  // 25% 확률
        level++;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

동전(50%)이 아니라 1/4 확률로 레벨업한다:

레벨별 확률 (p=0.25):

레벨 1:  75.00%      ← 3/4 확률로 첫 시도에서 멈춤
레벨 2:  18.75%      ← 1/4 × 3/4
레벨 3:   4.69%      ← (1/4)² × 3/4
레벨 4:   1.17%      ← (1/4)³ × 3/4
레벨 5:   0.29%
...
레벨 32: (1/4)³¹ ≈ 0.000000000000000021%


CGV 10만 명 대기열에서의 예상 분포:

Level 0: 100,000명  ← 전원 (Level 0에는 모든 노드가 있다)
Level 1:  25,000명  ← 25%만 Level 1 이상
Level 2:   6,250명
Level 3:   1,563명
Level 4:     391명
Level 5:      98명
Level 6:      24명
Level 7:       6명
Level 8:       2명   ← 10만 명이면 이 근처가 최고 레벨

왜 p=0.25인가 (p=0.5가 아니라):

p=0.5 (동전):
  노드당 평균 포인터 수 = 1/(1-p) = 1/0.5 = 2개
  10만 명 × 포인터 2개 × 16바이트 = ~3.2 MB

p=0.25 (Redis):
  노드당 평균 포인터 수 = 1/(1-p) = 1/0.75 ≈ 1.33개
  10만 명 × 포인터 1.33개 × 16바이트 = ~2.1 MB

→ 메모리 약 33% 절약
→ 검색 속도: 거의 동일 (레벨이 높아지지만 각 레벨에서 더 많이 건너뜀)

Redis는 메모리 효율을 택했다. 포인터 1개당 16바이트(forward 8B + span 8B)이므로, 모든 연산이 메모리에서 일어나는 Redis 특성상 포인터를 줄이는 것이 유리하다.

 

MAXLEVEL=32인 이유:

4^32 ≈ 18,446,744,073,709,551,616 (약 1,844경)

→ 노드가 1,844경 개가 되어야 레벨 32까지 쓸 일이 생긴다
→ 10만 명 대기열: 레벨 8~9이면 충분
→ 10억 명이라도: 레벨 15이면 충분
→ 32는 사실상 "무한"과 같다

Antirez(Redis 창시자)가 이 값을 정했다. 바꿀 이유가 없는 값이다.

왜 랜덤이 작동하는가 — 큰 수의 법칙:

노드 1개의 레벨은 순수한 랜덤이다. 하지만 노드가 수만 개 이상이면 큰 수의 법칙(Law of Large Numbers)이 작동한다:

동전을 10번 던지면 앞면이 8번 나올 수 있다 (운빨)
동전을 10만 번 던지면 앞면이 거의 정확히 50,000번 나온다 (확률 수렴)

10만 명에서 전부 레벨 1일 확률:
  (0.75)^100,000 ≈ 10^(-12,494)
  → 우주의 원자 수(10^80)보다 작은 확률
  → "일어나지 않는다"와 같다

실제로는 확률 분포에 정확히 수렴:
  ~75,000명이 레벨 1, ~25,000명이 레벨 2, ...
  → 급행 구조가 자동으로 형성

확정적 균형(Red-Black Tree)과 확률적 균형(Skip List)의 트레이드오프:

	Red-Black Tree	Skip List
균형 보장	확정 (회전 연산으로)	확률 (큰 수의 법칙으로)
삽입 후	회전 연산 필요 (여러 노드 수정)	포인터 연결만 (로컬 연산)
동시성	Lock 필요 (회전이 트리를 건드림)	Lock-free 가능
구현	복잡 (회전 케이스 분류)	단순 (동전 던지고 연결)
범위 검색	중위순회 필요	Level 0 따라가면 끝
성능	O(log N) 보장	O(log N) 기대값 (사실상 보장)

Redis가 Skip List를 고른 핵심 이유: "동전 던지기로 균형이 알아서 잡히니까 리밸런싱 코드가 필요 없고, Level 0이 정렬된 Linked List이니까 ZRANGE가 그냥 따라가면 된다."

CGV에서 Sorted Set을 선택한 이유

[대기열 시스템의 요구사항]

1. 순서 보장: 먼저 온 사람이 먼저 입장해야 한다
2. 순번 조회: "나는 지금 몇 번째인가?" 질문에 빠르게 답해야 한다
3. 상위 N명 추출: "빈자리만큼 입장시켜라" 연산이 빈번하다
4. 개별 제거: 사용자가 이탈하면 대기열에서 빠져야 한다
5. 크기 확인: "지금 몇 명이 대기 중인가?" O(1)이어야 한다

요구사항	List	Set	Sorted Set
순서 보장	O (삽입순)	X (순서 없음)	O (score순)
순번 조회	O(N) 느림	X 불가능	O(log N) ZRANK
상위 N명	O(N) 느림	X 불가능	O(log N + M) ZRANGE
개별 제거	O(N) 느림	O(1) 빠름	O(log N) ZREM
크기 확인	O(1) LLEN	O(1) SCARD	O(1) ZCARD

Sorted Set이 5가지 요구사항을 모두 충족하는 유일한 데이터 구조다.

score에 타임스탬프를 넣는 이유:

ZADD sessions:{topgun}:waiting 1707120000000 "req-aaa:sess-111"   → 20:00:00.000
ZADD sessions:{topgun}:waiting 1707120000500 "req-bbb:sess-222"   → 20:00:00.500
ZADD sessions:{topgun}:waiting 1707120001000 "req-ccc:sess-333"   → 20:00:01.000

• score = 밀리초 타임스탬프
• 먼저 등록한 사용자 = score가 작음 = 앞에 위치
• ZRANGE로 앞에서부터 꺼내면 자동으로 선착순 처리

---

3. Redis 명령어 정리

Sorted Set 명령어 (Z 명령어) -- CGV 핵심

CGV 대기열 시스템에서 사용하는 모든 Sorted Set 명령어를 정리한다.

ZADD -- 멤버 추가

ZADD key score member [score member ...]

score와 함께 멤버를 추가한다. 이미 존재하는 멤버면 score만 업데이트한다.

# 대기열에 사용자 추가 (score = 타임스탬프)
ZADD sessions:{topgun}:waiting 1707120000000 "req-abc:sess-123"
→ (integer) 1    (새로 추가됨)

ZADD sessions:{topgun}:waiting 1707120000000 "req-abc:sess-123"
→ (integer) 0    (이미 존재, score만 업데이트)

시간복잡도: O(log N). Skip List에서 정렬 위치를 찾아 삽입하므로.

CGV 적용: 사용자가 대기열에 진입할 때, System.currentTimeMillis()를 score로 사용하여 ZADD한다.

ZCARD -- 전체 멤버 수

ZCARD key

Sorted Set의 전체 멤버 수를 반환한다.

ZCARD sessions:{topgun}:waiting
→ (integer) 45832    (현재 대기열에 45,832명)

시간복잡도: O(1). Redis가 내부적으로 카운트를 별도로 관리하므로 즉시 반환된다.

CGV 적용: KEDA가 Prometheus 메트릭(cgv_queue_waiting_count)으로 대기열 길이를 읽어 스케일링을 판단한다. 이 메트릭의 원본이 ZCARD다. ZCARD의 결과는 Prometheus 메트릭으로 노출되어 KEDA 오토스케일링의 트리거가 된다. 부하테스트 시나리오에서 이 연계를 검증한다 (→ 2.4 참고).

ZRANK -- 순위 조회

ZRANK key member

해당 멤버가 몇 번째인지 반환한다 (0부터 시작).

ZRANK sessions:{topgun}:waiting "req-abc:sess-123"
→ (integer) 3421    (현재 3,422번째 -- 0-based이므로 +1)

시간복잡도: O(log N). Skip List를 탐색하여 위치를 계산한다.

CGV 적용: QueueProcessor가 주기적으로 대기열을 처리하면서 ZRANK로 각 사용자의 순번을 조회하고, WebSocket으로 실시간 순번을 알려준다.

ZRANGE -- 범위 조회 (인덱스 기반)

ZRANGE key start stop [WITHSCORES]

인덱스 범위로 멤버를 조회한다. score가 작은 것부터 (오름차순).

# 앞에서 100명 조회 (0번부터 99번까지)
ZRANGE sessions:{topgun}:waiting 0 99
→ ["req-aaa:sess-111", "req-bbb:sess-222", ..., "req-zzz:sess-999"]

# 전체 조회 (0부터 끝까지)
ZRANGE sessions:{topgun}:waiting 0 -1

# score도 함께 조회
ZRANGE sessions:{topgun}:waiting 0 99 WITHSCORES
→ [("req-aaa:sess-111", 1707120000000), ("req-bbb:sess-222", 1707120000500), ...]

시간복잡도: O(log N + M). N은 전체 멤버 수, M은 반환할 멤버 수.

CGV 적용: QueueProcessor가 2초마다 대기열 앞에서 빈자리(vacantSlots)만큼 꺼내 입장시킨다. BATCH_SIZE=5,000은 상한이며, 실제 이동 수는 min(vacantSlots, waitingCount, BATCH_SIZE)로 결정된다.

ZRANGEBYSCORE -- 범위 조회 (점수 기반)

ZRANGEBYSCORE key min max

score 범위로 멤버를 조회한다.

# 30초 무응답 세션 조회 (타임아웃 감지)
ZRANGEBYSCORE sessions:{topgun}:active 0 1707119970000
→ ["req-old:sess-expired"]   (30초 초과 세션들)

시간복잡도: O(log N + M).

CGV 적용: Active 세션 중 30초 이상 무응답인 세션을 찾아 타임아웃 처리한다. score(입장 시간)가 현재시간 - 30초보다 작은 멤버를 조회한다.

ZREM -- 멤버 제거

ZREM key member [member ...]

지정한 멤버를 제거한다.

# 입장 처리된 사용자를 대기열에서 제거
ZREM sessions:{topgun}:waiting "req-abc:sess-123"
→ (integer) 1    (제거됨)

# 여러 명 동시 제거
ZREM sessions:{topgun}:waiting "req-aaa:sess-111" "req-bbb:sess-222" "req-ccc:sess-333"
→ (integer) 3

시간복잡도: O(M * log N). M은 제거할 멤버 수.

CGV 적용: 대기열에서 Active로 이동할 때, Waiting에서 ZREM + Active에 ZADD. 이 두 연산을 Lua 스크립트로 원자적으로 실행한다.

ZREMRANGEBYSCORE -- 점수 범위로 제거

ZREMRANGEBYSCORE key min max

score 범위에 해당하는 멤버를 모두 제거한다.

# 타임아웃된 세션 일괄 제거 (30초 초과)
ZREMRANGEBYSCORE sessions:{topgun}:active 0 1707119970000
→ (integer) 15    (15명의 타임아웃 세션 제거)

CGV 적용: 주기적으로 Active 세션 중 30초 무응답 세션을 일괄 정리한다.

ZSCORE -- 특정 멤버의 점수 조회

ZSCORE key member

ZSCORE sessions:{topgun}:waiting "req-abc:sess-123"
→ "1707120000000"    (등록 시간)

시간복잡도: O(1). Hash Table에서 직접 조회하므로.

String 명령어 (CGV 관련)

명령어	형식	설명	CGV 용도
SET	SET key value [EX sec] [NX]	값 저장	세션 생성
GET	GET key	값 조회	세션 정보
EXISTS	EXISTS key	키 존재 확인 (0/1)	세션 유효성 검증
EXPIRE	EXPIRE key seconds	TTL 설정/갱신	세션 슬라이딩 TTL
DEL	DEL key [key ...]	키 삭제	세션 삭제
TTL	TTL key	남은 TTL 확인	디버깅
TYPE	TYPE key	키의 데이터 타입 확인	WRONGTYPE 방어

Set 명령어 (CGV 관련)

명령어	형식	설명	CGV 용도
SADD	SADD key member	멤버 추가	활성 영화 등록
SMEMBERS	SMEMBERS key	전체 멤버 조회	QueueProcessor 영화 목록
SCARD	SCARD key	멤버 수	영화 수 확인

CGV에서 사용하는 명령어 전체 맵

[CGV Redis 명령어 전체 맵]

┌─────────────────────────────────────────────────────────┐
│                    대기열 관리                              │
│                                                         │
│  진입: ZADD waiting (score=timestamp)                    │
│  순번: ZRANK waiting → "당신은 3,422번째"                  │
│  크기: ZCARD waiting → "현재 45,832명 대기 중"             │
│  추출: ZRANGE waiting 0 {N-1} → "앞에서 N명" (vacantSlots)  │
│  이동: ZREM waiting + ZADD active (Lua 원자적)            │
│  만료: ZRANGEBYSCORE active 0 {30초전} → 타임아웃 감지     │
│  정리: ZREMRANGEBYSCORE active 0 {30초전} → 일괄 제거      │
│                                                         │
├─────────────────────────────────────────────────────────┤
│                    세션 관리                              │
│                                                         │
│  생성: SET session:{id} "1" EX 3600                      │
│  검증: EXISTS session:{id}                               │
│  갱신: EXPIRE session:{id} 3600                          │
│  삭제: DEL session:{id}                                  │
│                                                         │
├─────────────────────────────────────────────────────────┤
│                    영화 목록                              │
│                                                         │
│  등록: SADD active_movies {movieId}                      │
│  조회: SMEMBERS active_movies                            │
│                                                         │
├─────────────────────────────────────────────────────────┤
│                    Pub/Sub (계획됨 — 멀티 Pod 메시지)       │
│                                                         │
│  발행: PUBLISH queue:notifications {event, ...}           │
│  구독: SUBSCRIBE queue:notifications                     │
│                                                         │
└─────────────────────────────────────────────────────────┘

---