1. 도입
캐시로 Redis를 쓰다 보면 "이 명령은 O(1)이니까 마음껏 써도 되겠지"라고 막연하게 넘긴 적이 많았다. 그러다 KEYS *나 SMEMBERS 같은 명령이 운영 환경에서 지연을 만든다는 글을 보고, 명령별 시간복잡도를 한 번 제대로 정리해야겠다고 생각했다.
그런데 시간복잡도만 외우는 건 금방 잊어버린다. 결국 각 자료형이 내부적으로 어떤 구조로 저장되는가를 알아야 "왜 이 명령이 O(1)이고 저 명령이 O(N)인지"가 자연스럽게 따라온다. 그래서 이 글은 Redis의 다섯 가지 기본 자료형(String, List, Hash, Set, Sorted Set)이 내부에서 어떤 인코딩으로 저장되는지, 그리고 그 구조에서 주요 명령의 복잡도가 어떻게 결정되는지를 따라가 본 정리다.
내부 인코딩은 Redis 버전마다 조금씩 바뀌었다. 이 글은 Redis 7.x 기준으로 정리했고, 확신이 약한 세부는 공식 docs 인용으로 처리했다.
2. 핵심 개념: "하나의 자료형, 여러 인코딩"
Redis의 자료형(type)과 인코딩(encoding)은 다른 층위다. 사용자가 보는 건 String, List 같은 타입이지만, 내부 저장 방식인 인코딩은 데이터의 크기·내용에 따라 Redis가 자동으로 고른다.
핵심 동기는 메모리 절약이다. 원소가 몇 개 안 되는 작은 컬렉션을 위해 해시테이블이나 스킵리스트 같은 무거운 구조를 쓰면 포인터 오버헤드가 크다. 그래서 Redis는 작을 때는 연속된 메모리 블록(listpack 등)에 빽빽하게 담아두다가, 임계치를 넘으면 조회에 유리한 구조로 자동 전환한다.
이 전환 임계치는 설정값으로 조절된다. 예를 들어 해시는 다음 두 값으로 인코딩이 결정된다고 공식 docs(redis.conf 주석)에 적혀 있다.
hash-max-listpack-entries 128 # 원소 수가 이보다 크면 hashtable로 전환
hash-max-listpack-value 64 # 값 길이가 이보다 길면 hashtable로 전환실제로 어떤 인코딩이 쓰이는지는 OBJECT ENCODING 명령으로 확인할 수 있다.
127.0.0.1:6379> RPUSH mylist a b c
(integer) 3
127.0.0.1:6379> OBJECT ENCODING mylist
"listpack"참고:
ziplist는 예전 인코딩 이름이고, Redis 7.0부터 대부분listpack으로 대체됐다고 알려져 있다. 오래된 자료와 용어가 다를 수 있다.
3. 자료형별 내부 동작과 복잡도
3.1 String — SDS
String은 가장 단순하다. 내부적으로 SDS(Simple Dynamic String)라는 구조를 쓴다. C 문자열과 달리 길이(len)와 여유 공간(alloc)을 헤더에 따로 들고 있어서, 길이 조회가 O(1)이고 APPEND가 매번 전체를 다시 스캔하지 않는다.
GET/SET: O(1)APPEND: 분할 상환(amortized) O(1) — 여유 공간을 미리 잡아두는 전략STRLEN: O(1) — 헤더에 길이가 있으므로GETRANGE: O(N) — N은 반환 구간 길이SETRANGE: O(1)에 가깝지만 메모리 재할당이 일어나면 그만큼 비용
값이 정수로만 이루어졌고 범위 안이면 int 인코딩으로 저장돼 메모리를 더 아낀다.
3.2 List — quicklist
List는 Redis 3.2부터 quicklist를 쓴다. quicklist는 이름 그대로 "listpack(작은 연속 블록)들을 양방향 연결 리스트로 이은" 하이브리드 구조다.
quicklist
┌──────────┐ ┌──────────┐ ┌──────────┐
│ listpack │ ↔ │ listpack │ ↔ │ listpack │
│ [a,b,c] │ │ [d,e,f] │ │ [g,h] │
└──────────┘ └──────────┘ └──────────┘
head node tail node양 끝 노드에 접근하는 건 O(1)이라 큐/스택으로 쓰기 좋다.
LPUSH/RPUSH/LPOP/RPOP: O(1)LINDEX: O(N) — 임의 인덱스 접근은 노드를 순회해야 함LRANGE: O(S+N) — S는 시작 오프셋까지의 거리, N은 반환 개수LINSERT/LREM: O(N)
여기서 자주 헷갈리는 지점: List는 "양 끝은 빠르고 가운데는 느리다"는 것이다. 메시지 큐처럼 끝에서만 넣고 빼면 O(1)이지만, 중간을 인덱스로 헤집으면 O(N)이 된다.
3.3 Hash — listpack ↔ hashtable
Hash는 원소가 적고 값이 짧으면 listpack(연속 메모리에 필드-값을 번갈아 저장), 임계치를 넘으면 hashtable로 전환된다.
HGET/HSET/HDEL: hashtable일 때 평균 O(1)HGETALL: O(N) — N은 필드 수HMGET: O(K) — K는 요청한 필드 수
listpack 상태에서는 사실 필드를 찾을 때 선형 탐색이라 엄밀히는 O(N)에 가깝지만, 원소 수가 임계치(기본 128) 이하로 작아서 상수처럼 취급한다고 이해했다.
3.4 Set — intset / listpack / hashtable
Set은 인코딩이 세 갈래로 나뉘는 점이 재미있다.
| 조건 | 인코딩 | 비고 |
|---|---|---|
| 원소가 전부 정수이고 개수가 작음 | intset | 정렬된 정수 배열, 이진 탐색 |
| 정수가 아니지만 개수가 작음 | listpack | Redis 7.2+에서 추가됐다고 알려짐 |
| 임계치 초과 | hashtable | 값이 키, 값은 NULL |
SADD/SREM/SISMEMBER: hashtable일 때 평균 O(1), intset일 때는 이진 탐색이라 O(log N)SMEMBERS: O(N) — 전체 반환이라 큰 Set에서 위험SINTER/SUNION/SDIFF: 입력 크기 합에 비례 (대략 O(N*M) 또는 O(전체 원소 수))
SMEMBERS로 큰 Set을 통째로 가져오면 단일 명령이 오래 점유해 다른 요청을 막을 수 있다. 공식 docs도 큰 컬렉션 전체 조회 대신SSCAN계열의 점진적 순회를 권한다.
3.5 Sorted Set — listpack ↔ (skiplist + hashtable)
가장 흥미로운 건 Sorted Set이다. 원소가 많아지면 스킵리스트(skip list)와 해시테이블을 동시에 들고 있는 이중 구조가 된다.
hashtable: member -> score 조회 O(1)
skiplist (score로 정렬, 다층 링크):
L2: HEAD ----------------> [50] --------> NULL
L1: HEAD ------> [20] ----> [50] --------> NULL
L0: HEAD -> [10][20][35][50][70] -------> NULL- 해시테이블은 "member로 score를 O(1)에 찾기" 담당 →
ZSCOREO(1) - 스킵리스트는 "score 순 정렬·범위 조회" 담당 → 평균 O(log N) 탐색
복잡도를 정리하면:
ZADD: O(log N)ZSCORE: O(1) — 해시테이블 덕분ZRANGE/ZREVRANGE: O(log N + M) — M은 반환 개수ZRANK: O(log N)
스킵리스트는 균형 트리(B-tree, red-black tree)와 비슷한 O(log N) 성능을 내면서 구현이 단순하다는 이유로 채택됐다고 공식 docs에서 설명한다. 확률적으로 노드의 층 높이를 정하는 구조라, 평균적으로 균형이 잡힌다.
4. 정리한 복잡도 표
자주 쓰는 명령만 한눈에 모았다. (인코딩 전환 후 일반적인 경우 기준)
| 자료형 | 대표 O(1) 명령 | 주의할 O(N)/O(log N) 명령 |
|---|---|---|
| String | GET, SET, STRLEN | GETRANGE(O(N)) |
| List | LPUSH, RPUSH, LPOP, RPOP | LINDEX, LRANGE, LINSERT(O(N)) |
| Hash | HGET, HSET | HGETALL(O(N)) |
| Set | SADD, SISMEMBER | SMEMBERS, SINTER(O(N)) |
| Sorted Set | ZSCORE | ZADD, ZRANGE(O(log N(+M))) |
운영에서 특히 조심할 명령은 KEYS, SMEMBERS, HGETALL, LRANGE 0 -1처럼 컬렉션 전체를 한 번에 훑는 부류다. 데이터가 커지면 단일 명령이 이벤트 루프를 오래 잡아 전체 지연으로 번진다. 공식 docs는 이런 경우 SCAN/SSCAN/HSCAN 같은 커서 기반 순회를 권한다.
5. 정리
Redis의 시간복잡도는 외우는 게 아니라 "이 타입이 지금 어떤 인코딩으로 저장돼 있는가"에서 따라 나온다.
이번에 정리하면서 가장 크게 남은 건 두 가지다. 첫째, 같은 타입이라도 크기에 따라 인코딩이 바뀌고 그에 따라 복잡도 체감이 달라진다는 것. 둘째, Sorted Set이 스킵리스트와 해시테이블을 동시에 들고 있어서 "정렬 조회"와 "단건 score 조회"를 둘 다 빠르게 한다는 구조적 트릭이다.
다음에 더 파고들 주제로는 두 가지를 적어둔다.
- Redis Persistence (RDB vs AOF) — 이 인메모리 구조가 디스크에 어떻게 내려가는가
- listpack의 실제 바이트 레이아웃 — 연속 메모리 인코딩이 메모리를 아끼는 구체적 방식
참고 자료
- Redis 공식 docs — Data types 및 각 명령 페이지의 Time complexity 표 (https://redis.io/docs/latest/develop/data-types/)
redis.conf주석 —*-max-listpack-entries/*-max-listpack-value설정 설명- Redis 공식 docs — Skip list 및 sorted set 구현 관련 설명
