Redis vs LevelDB

1. 시스템 설계 패턴: Dual Index (이중 인덱스)

Redis Sorted Set의 "Skip List + Hash Table" 조합은 시스템 프로그래밍에서 반복적으로 등장하는 설계 패턴이다. 하나의 자료구조로는 두 가지 연산을 동시에 최적화할 수 없기 때문에, 두 인덱스를 결합하는 것이다.

 

패턴의 핵심:

하나의 데이터에 대해 두 가지 접근 경로가 필요할 때
→ 두 자료구조를 결합하고, 같은 노드가 두 곳에 동시에 소속된다

 

Redis Sorted Set이 이 패턴의 대표 사례다:

Redis Sorted Set
├── Hash Table → "이 member의 score가 뭐야?"  → O(1) 포인트 조회
└── Skip List  → "score 순서대로 상위 100명?"  → O(log n) 범위 검색

Hash Table만 있으면: score 범위 검색 시 전체 스캔 O(n)
Skip List만 있으면: 특정 member의 score 조회 시 순회 O(log n)
→ 둘을 결합하면 두 연산 모두 최적화

 

같은 패턴이 적용된 다른 시스템들:

시스템	자료구조 조합	목적
Redis Sorted Set	Hash Table + Skip List	O(1) score 조회 + O(log n) 범위 검색
LevelDB LRU Cache	Hash Table + Doubly-Linked List	O(1) 캐시 조회 + O(1) eviction
Java LinkedHashMap	HashMap + Doubly-Linked List	O(1) 조회 + 삽입 순서 유지
Linux O(1) Scheduler	Hash Table + Bitmap + Linked List	O(1) 태스크 조회 + O(1) 스케줄링

---

2. LevelDB LRU Cache와의 내부 자료구조 비교

LevelDB의 Table Cache와 Block Cache는 모두 Hash Table + Doubly-Linked List 조합의 LRU Cache 구조다.

Redis Sorted Set과 비교하면 Dual Index 패턴의 원리가 선명하게 보인다.

[LevelDB LRU Cache]
┌─────────────────────────────────────────────┐
│              LRUCache                        │
│                                              │
│  ┌──────────────┐  ┌──────────────────────┐ │
│  │  HandleTable  │  │  Doubly-Linked List  │ │
│  │  (Hash Table) │  │                      │ │
│  │               │  │  lru_: eviction 후보 │ │
│  │  key → node   │  │  in_use_: 사용 중    │ │
│  │  O(1) 조회    │  │  O(1) 삽입/삭제      │ │
│  └──────────────┘  └──────────────────────┘ │
└─────────────────────────────────────────────┘

[Redis Sorted Set]
┌─────────────────────────────────────────────┐
│              ZSet (Sorted Set)               │
│                                              │
│  ┌──────────────┐  ┌──────────────────────┐ │
│  │     dict      │  │     Skip List        │ │
│  │  (Hash Table) │  │                      │ │
│  │               │  │  score 순서로 정렬   │ │
│  │  member→score │  │  O(log n) 범위 검색  │ │
│  │  O(1) 조회    │  │  O(log n) 삽입/삭제  │ │
│  └──────────────┘  └──────────────────────┘ │
└─────────────────────────────────────────────┘

공통점 -- 진짜 연결고리:

1. Hash Table의 역할이 동일하다: 둘 다 "특정 key/member를 O(1)에 찾기" 용도
   • LevelDB: table_.Lookup(key, hash) → 캐시에 있는지 판별
   • Redis: dictFind(zs->dict, member) → member의 score 조회
2. 하나의 노드가 두 자료구조에 동시 소속된다:데이터를 복사하지 않고, 같은 데이터를 두 자료구조가 포인터로 공유한다.
3. LevelDB LRUHandle: next_hash → HandleTable 체이닝용 next/prev → Linked List 연결용
4. Redis Sorted Set 엔트리: dict entry → Hash Table 버킷에 연결 skiplist node → level별 forward + backward 포인터
5. 하나의 값이 노드의 위치를 결정한다:
   • LevelDB: refs (참조 카운트) → refs=1이면 lru_(eviction 대상), refs≥2이면 in_use_(보호)
   • Redis: score → score 값에 따라 Skip List 내 정렬 위치 결정

차이점 -- 왜 결합하는 "순서 자료구조"가 다른가:

	LevelDB LRU	Redis Sorted Set
순서 기준	시간 (최근 사용 순)	값 (score 크기 순)
순서 자료구조	Doubly-Linked List	Skip List
접근 패턴	양 끝단만 (맨 앞 제거, 맨 뒤 추가)	임의 위치 (score 기반 삽입, 범위 검색)
시간복잡도	삽입/삭제 O(1)	삽입/삭제 O(log n)

 

LevelDB가 Linked List로 충분한 이유:

Lookup 시: 현재 위치에서 빼서 → 맨 뒤에 붙임 (항상 양 끝단 = O(1))
Eviction 시: 맨 앞(lru_.next)에서 뺌 (항상 맨 앞 = O(1))
→ 임의 위치 접근이 필요 없음 → Linked List면 충분

 

Redis가 Skip List를 써야 하는 이유:

ZADD 시: score에 맞는 정확한 위치에 삽입 (임의 위치 = O(log n))
ZRANGEBYSCORE 시: score 범위로 구간 검색 (범위 조회 = O(log n + k))
ZRANK 시: member가 몇 번째인지 계산 (순위 조회 = O(log n))
→ 임의 위치 접근 + 범위 검색 필요 → Linked List로는 O(n) → Skip List 필요

 

핵심 인사이트:

"어떤 순서 자료구조를 결합할지"는 접근 패턴이 결정한다.

• 양 끝단만 건드린다 → Doubly-Linked List
• 임의 위치 + 범위 검색이 필요하다 → Skip List (또는 Balanced Tree)

두 경우 모두 Hash Table은 항상 함께 쓰인다. "O(1) 포인트 조회"는 거의 모든 시스템에서 필수이기 때문이다.

전제 조건 — 왜 둘 다 포인터 기반 구조인가:

위 비교가 성립하는 근본 이유는 둘 다 메모리에 존재하기 때문이다.

메모리에서 포인터 따라가기: ~수 나노초 (ns)
디스크에서 랜덤 읽기:      ~수 밀리초 (ms)  ← 약 100만 배 느림

Doubly-Linked List와 Skip List는 노드 간 포인터로 연결되는 구조다.

포인터를 따라가는 비용이 나노초 단위로 거의 무시할 수 있으므로 이런 설계가 가능하다.

디스크였다면 포인터 = 랜덤 I/O = 밀리초 단위 지연이므로, B-Tree처럼 블록 단위로 데이터를 묶어서 순차 접근하는 구조를 써야 한다.

메모리 → 포인터 기반 (Linked List, Skip List)  ← LevelDB Cache, Redis
디스크 → 블록 기반 (B-Tree, SSTable)           ← MySQL, LevelDB 저장소

같은 LevelDB 안에서도 이 차이가 드러난다:

• Cache (메모리): Hash Table + Doubly-Linked List (포인터 기반)
• 저장소 (디스크): LSM-Tree + SSTable (블록 기반, 순차 I/O 최적화)

---

3. LevelDB 캐시 아키텍처와 Redis

앞에서는 "내부 자료구조"를 비교했다. 여기서는 한 단계 올라가서, LevelDB의 캐시 시스템(Table Cache, Block Cache)이 Redis와 어떤 개념을 공유하는지 비교한다. LevelDB 캐시를 공부한 사람이 Redis를 볼 때 "아, 같은 원리구나"라고 느낄 수 있는 부분만 정리한다.

비교 1: "느린 저장소 앞에 빠른 메모리를 놓는다"

LevelDB의 Block Cache와 Redis의 역할이 정확히 같은 패턴이다.

[LevelDB 읽기 경로]

MemTable (메모리, 가장 빠름)
  ↓ miss
Block Cache (메모리, 4MB LRU)
  ↓ miss
SSTable on Disk (디스크, 가장 느림)

→ Block Cache 히트: ~29 μs/op
→ Block Cache 미스: ~150 μs/op (5배 느림)


[일반적인 웹 애플리케이션 읽기 경로]

Application 로컬 변수 (메모리, 가장 빠름)
  ↓ miss
Redis (메모리, 네트워크 경유)
  ↓ miss
MySQL / RDS (디스크, 가장 느림)

→ Redis 히트: ~0.1ms
→ Redis 미스 → MySQL 조회: ~5ms (50배 느림)

같은 원리: 느린 저장소(디스크/DB) 앞에 빠른 메모리 계층을 두고, 자주 접근하는 "hot data"를 캐싱해서 느린 접근을 회피한다. 컴퓨터 과학에서 메모리 계층 구조(Memory Hierarchy) 라고 부르는 보편 원리다.

 

CPU Register → L1 Cache → L2 Cache → L3 Cache → RAM → SSD → HDD
                    ↑                              ↑           ↑
              LevelDB Block Cache              Redis        MySQL
              (RAM에 디스크 데이터 캐싱)    (RAM에 DB 데이터 캐싱)

단, CGV 대기열 시스템에서 Redis는 "캐시"가 아니라 "Primary Store"다. 대기열 데이터는 Redis에만 존재하고, 뒤에 MySQL이 없다. 이 비교는 Redis를 캐시로 사용하는 일반적인 웹 아키텍처(게시판 캐싱, 세션 캐싱 등)에 해당한다.

비교 2: capacity 초과 시 LRU Eviction

LevelDB Block Cache와 Redis 모두 "메모리가 꽉 차면 오래된 것부터 버린다" 는 같은 전략을 쓴다.

[LevelDB Block Cache]
capacity: 4MB (기본값)
charge: Data Block의 바이트 크기 (4KB)
초과 시: lru_ 리스트에서 가장 오래된 Block부터 eviction
→ usage_ -= old->charge
→ usage_ ≤ capacity_가 될 때까지 반복

[Redis maxmemory]
maxmemory: ~1 GiB (CGV prod, cache.t3.small 기준)
초과 시: maxmemory-policy에 따라 eviction
→ allkeys-lru: 모든 key 중 가장 오래 안 쓰인 것 삭제
→ volatile-lru: TTL 설정된 key 중 가장 오래 안 쓰인 것 삭제
→ noeviction: 에러 반환 (CGV는 이 정책 사용 — 대기열 데이터 유실 방지)

	LevelDB Block Cache	Redis
용량 한도	capacity (바이트)	maxmemory (바이트)
엔트리 크기	charge (Block 크기)	각 key-value의 메모리 사용량
Eviction 정책	LRU (유일한 옵션)	LRU, LFU, Random, TTL 등 6가지 선택
Eviction 대상	lru_ 리스트의 맨 앞	샘플링 기반 근사 LRU

 

LevelDB는 정확한 LRU, Redis는 근사 LRU라는 차이:

• LevelDB: lru_ 이중 연결 리스트에 모든 엔트리가 정확한 사용 순서로 연결 → 맨 앞이 정확히 가장 오래된 것
• Redis: 10만 개 key를 전부 리스트로 관리하면 오버헤드가 크므로, 랜덤 샘플 5개를 뽑아서 그 중 가장 오래된 것을 삭제하는 근사(approximate) LRU를 사용
• LevelDB는 캐시 엔트리가 최대 수천 개(Block Cache 4MB / Block 4KB ≈ 1000개)라서 정확한 LRU가 가능하지만, Redis는 수백만 개 key를 관리하므로 근사 LRU가 현실적

비교 3: 리소스 핸들 캐싱 -- Table Cache ↔ Connection Pool

이 비교가 가장 직접적으로 겹친다. 둘 다 "비싼 리소스의 핸들을 미리 열어두고 재사용" 하는 것이다.

[LevelDB Table Cache]
캐싱 대상: 열린 파일 핸들 (RandomAccessFile*) + Index Block
왜: SSTable을 열 때마다 open() 시스템 콜 + Footer/Index 읽기 = 최소 3번 Disk I/O
효과: 캐시 히트 시 Disk I/O = 0번 (이미 열려있는 핸들 재사용)
용량: 1,000개 (최대 1,000개 SSTable 핸들 유지)
비용: 파일 핸들(fd)은 OS 자원 → 무한정 열 수 없음

[Redis Connection Pool (CGV application.yml)]
캐싱 대상: 열린 TCP 연결 (Socket)
왜: Redis 연결 시마다 TCP 3-way handshake + AUTH = 네트워크 왕복 2~3회
효과: 풀 히트 시 연결 수립 비용 = 0 (이미 열려있는 연결 재사용)
용량: max-active 8 (local), 50 (prod)
비용: TCP 연결은 Redis 서버 메모리 + OS fd 소모 → 무한정 열 수 없음

	LevelDB Table Cache	Redis Connection Pool
캐싱 대상	파일 핸들 (fd)	TCP 연결 (socket)
열기 비용	open() + 3 Disk I/O	TCP handshake + AUTH
재사용 효과	Disk I/O 0번	네트워크 왕복 0번
용량 제한 이유	OS fd 개수 제한	Redis 서버 메모리/fd 제한
Eviction	LRU (안 쓰는 핸들 닫기)	Idle timeout (유휴 연결 종료)

둘 다 "열기 비용이 비싼 OS 리소스의 핸들을 풀에 유지하고 재사용" 하는 동일한 최적화다. LevelDB Table Cache를 이해했다면, Redis Connection Pool이 왜 존재하고 왜 max-active를 제한하는지가 직관적으로 이해될 것이다.

비교 4: Sharding으로 동시성 확보

LevelDB의 ShardedLRUCache와 Redis Cluster가 같은 아이디어를 다른 스케일에서 적용한다.

[LevelDB ShardedLRUCache]
목적: 단일 머신에서 Lock 경합 감소
방식: hash 상위 4비트 → 16개 샤드 → 각 샤드 독립 Lock
효과: 16개 스레드가 동시에 서로 다른 샤드에 접근 가능

[Redis Cluster]
목적: 여러 머신에서 데이터 분산
방식: CRC16(key) % 16384 → 16384 슬롯 → 노드별 슬롯 범위 할당
효과: 여러 노드가 동시에 서로 다른 슬롯의 요청 처리

[CGV Hash Tag]
key: sessions:{topgun}:waiting
CRC16("{topgun}") → 특정 슬롯 → 같은 영화의 모든 키가 같은 노드
→ Lua 스크립트가 하나의 노드 안에서 원자적으로 실행 가능

우리 프로젝트: ElastiCache Non-Cluster Mode + Multi-AZ Replica 구성이므로 슬롯 분산이 없지만, 키 네이밍 컨벤션으로 {movieId} Hash Tag를 유지한다. Lua 스크립트가 같은 영화의 waiting/active 키를 원자적으로 조작해야 하므로 Hash Tag가 필수이며, 이 때문에 Cluster Mode로 전환해도 분산 이점을 얻을 수 없다

참고: CGV는 현재 Non-Cluster Mode이므로 Hash Tag가 슬롯 분산에 영향을 주지 않는다.
Hash Tag를 유지하는 이유는 (1) 키 구조의 가독성과 (2) 향후 Cluster Mode 전환 시 Lua 스크립트 무변경을 위해서다.

	LevelDB ShardedLRUCache	Redis Cluster
파티셔닝 단위	16개 샤드	16,384개 슬롯
해시 함수	hash >> 28 (상위 4비트)	CRC16(key) % 16384
스케일	단일 머신 (스레드 간 분산)	여러 머신 (노드 간 분산)
해결하는 문제	Lock 경합	메모리/처리량 한계
공통 원리	해시 기반 파티셔닝으로 독립적 처리 영역을 만든다

규모는 다르지만 원리는 같다: "전체를 하나로 관리하면 병목이 생기니, 해시로 쪼개서 독립적으로 처리한다."

---

4. MemTable의 Skip List ↔ Sorted Set의 Skip List

LevelDB를 공부할 때 MemTable이 Skip List라는 걸 배웠다. Redis Sorted Set도 Skip List다. 둘 다 "데이터를 정렬된 상태로 메모리에 유지" 해야 하는 같은 요구사항 때문에 같은 자료구조를 선택한 것이다.

[LevelDB MemTable]
역할: 쓰기 요청을 메모리에서 정렬 상태로 유지
구조: Skip List (key의 바이트 순서로 정렬)
이유: SSTable로 flush할 때 정렬된 순서로 순차 쓰기해야 함
     → 삽입 시점에 정렬을 유지하면 flush가 O(n) 순차 스캔으로 끝남

[Redis Sorted Set]
역할: member를 score 순서로 메모리에서 정렬 상태로 유지
구조: Skip List (score 크기 순으로 정렬)
이유: ZRANGE, ZRANK 같은 순위 조회가 빈번함
     → 삽입 시점에 정렬을 유지하면 조회가 O(log n)으로 끝남

	LevelDB MemTable	Redis Sorted Set
자료구조	Skip List	Skip List
정렬 기준	key (바이트 순서)	score (숫자 크기)
정렬 유지 이유	flush 시 순차 쓰기	순위 조회
B-Tree 안 쓰는 이유	Lock-free 동시성 + 구현 단순	구현 단순 + 범위 조회 자연스러움
삽입	O(log n)	O(log n)
범위 조회	Level 0 순차 탐색	Level 0 순차 탐색

Skip List를 선택한 공통점과 차이점:

• 공통: B-Tree는 노드 분할/병합(리밸런싱)이 필요하고 구현이 복잡. Skip List는 확률적 레벨 할당만으로 균형이 유지된다
• LevelDB: Lock-free(CAS 기반) 동시 삽입이 주된 이유. 멀티 스레드 환경에서 Lock 없이 삽입 가능
• Redis: 구현 단순성 + 범위 조회의 자연스러움이 주된 이유. 싱글 스레드라 Lock-free는 불필요
• 두 시스템이 같은 자료구조를 택했지만, 핵심 선택 이유는 다르다

---

5. WAL ↔ AOF -- 크래시 복구용 순차 로그

LevelDB의 WAL(Write-Ahead Log)과 Redis의 AOF(Append-Only File)는 이름만 다르고 목적이 같다: "메모리 데이터가 날아가도 로그를 재생해서 복구한다."

[LevelDB WAL]
쓰기 흐름: Write 요청 → WAL에 순차 append → MemTable에 반영
크래시 시: WAL을 처음부터 재생(replay) → MemTable 복원
삭제 시점: MemTable이 SSTable로 flush 완료되면 해당 WAL 삭제
파일 형태: 고정 32KB 블록 단위의 바이너리 로그

[Redis AOF]
쓰기 흐름: Write 명령 → 메모리에 반영 → AOF 파일에 순차 append
크래시 시: AOF를 처음부터 재생(replay) → 메모리 상태 복원
정리 시점: AOF Rewrite로 현재 상태만 남기고 과거 로그 압축
파일 형태: Redis 명령어 텍스트 (사람이 읽을 수 있음)

	LevelDB WAL	Redis AOF
기록 시점	메모리 반영 전 (Write-Ahead)	메모리 반영 후 (Append-After)
기록 내용	key-value 바이너리	Redis 명령어 텍스트 (SET key value)
재생 방식	바이너리 파싱 → MemTable Insert	명령어 재실행
로그 정리	MemTable flush 시 WAL 삭제	AOF Rewrite (bgrewriteaof)
fsync 정책	OS에 위임 (기본 sync=false)	everysec / always / no 선택

핵심 차이 — "Ahead" vs "After":

• LevelDB는 WAL에 먼저 쓰고 MemTable에 반영한다 (Write-Ahead Log). 메모리 반영 전에 크래시나도 WAL에 남아있으니 복구 가능
• Redis는 메모리에 먼저 반영하고 AOF에 기록한다. fsync=everysec이면 최대 1초치 데이터를 잃을 수 있음 (fsync=always면 매 명령마다 디스크 동기화하여 유실 없지만 느림)

이 차이는 설계 철학의 차이다:

• LevelDB: 디스크가 주 저장소, 메모리는 캐시 → 데이터 유실 = 치명적 → WAL 먼저
• Redis: 메모리가 주 저장소, 디스크는 백업 → 약간의 유실 허용 가능 → 성능 우선

---

6. 싱글 스레드 쓰기 모델 -- Lua 원자성의 근본 이유

LevelDB는 쓰기를 단일 스레드로 직렬화한다. Redis는 모든 명령을 단일 스레드로 처리한다.

이 설계 선택이 Redis Lua 스크립트의 원자성을 보장하는 근본 이유다.

[LevelDB]
쓰기: 단일 스레드 (Writer Queue에 넣고 순차 처리)
읽기: 여러 스레드 가능 (Lock-free SkipList + 스냅샷 기반 읽기)
이유: 쓰기 직렬화로 WAL/MemTable 동시 접근 문제 제거

[Redis]
모든 명령: 단일 스레드 이벤트 루프 (epoll 기반)
읽기/쓰기 구분 없음: 전부 하나의 스레드가 순차 처리
이유: Lock 없이 모든 자료구조에 안전하게 접근

	LevelDB	Redis
싱글 스레드 범위	쓰기만	모든 명령
읽기 동시성	멀티 스레드 가능	싱글 스레드
이점	WAL 순서 보장	모든 연산 원자적
대가	쓰기 처리량 제한	전체 처리량 제한 (CPU 1코어만 사용)

 

CGV와의 연결 — 왜 Lua 스크립트가 원자적인가:

[Redis 이벤트 루프]

→ 명령 1: SET key1 value1        ← 처리
→ 명령 2: EVAL "lua script..."   ← 처리 시작
    Lua 내부: ZCARD → 비교 → ZADD    ← 이 사이에 다른 명령 끼어들 수 없음
→ 명령 3: GET key2               ← Lua 끝난 후에야 처리

싱글 스레드이므로 Lua 실행 중에는 다른 클라이언트의 명령이 대기
→ ZCARD와 ZADD 사이에 다른 요청이 끼어드는 것이 물리적으로 불가능
→ 이것이 CGV 대기열 진입 Lua의 레이스 컨디션을 해결하는 근본 원리

LevelDB에서 "왜 쓰기를 직렬화하는가"를 이해했다면, Redis의 "왜 모든 걸 직렬화하는가"도 같은 맥락이다. 동시 접근 문제를 Lock이 아니라 직렬화로 해결하는 것. Lock은 복잡하고 데드락 위험이 있지만, 직렬화는 단순하고 안전하다. 대신 처리량을 희생한다.

---