Mingyu Kim

데이터 구조의 기저 원리 파악

Redis는 하나의 Key에 다양한 형태의 ‘객체(Object)’를 매핑하는 구조다. 단순히 값을 저장하는 게 아니라, 각 자료구조가 메모리를 효율적으로 쓰고 속도를 극대화하기 위해 상황에 따라 내부 인코딩을 스스로 바꾼다는 점이 핵심이다.

1. 기본 구조: redisObject

SET key “value”를 입력하면, 아래와 같은 메타데이터를 포함한 객체를 만든다.

• Type: 외부에서 보이는 자료구조 (String, List 등)
• Encoding: 내부적으로 데이터를 저장하는 방식 (Raw, Int, ZipList 등)
• LRU/LFU: 메모리 교체 알고리즘을 위한 시간 정보
• Refcount: 참조 횟수 (메모리 관리용)

2. 주요 자료구조별 심층 분석

String

단순 텍스트뿐만 아니라 숫자, 바이너리 데이터(이미지 등)도 저장한다.

• 내부 구현: SDS (Simple Dynamic String)라는 구조를 사용한다. C언어의 기본 문자열과 달리 문자열의 길이를 미리 저장해두어, 길이를 구하는 연산이 O(1)이다.
• 특징: 버퍼 오버플로우를 방지하고, 메모리 재할당을 최소화하기 위해 여유 공간을 미리 할당(Pre-allocation)한다.

Lists(연결 리스트)

데이터의 순서를 유지한다.

• 내부 구현: 과거에는 ZipList와 LinkedList를 섞어 썼지만, 최신 버전에서는 두 장점을 합친 QuickList를 사용한다.
• QuickList: 여러 개의 ZipList를 양방향 연결 리스트로 이은 형태로 메모리 효율과 포인터 오버헤드 사이의 균형을 잡은 구조

Sorted Sets

값(Member)과 점수(Score)를 함께 저장하며, 점수순으로 정렬된다.

• 내부 구현: SkipList와 Hash Table을 동시에 사용한다.
• SkipList: 이진 탐색 트리와 유사한 성능(O(log N))을 내면서도 구현이 훨씬 단순하고 병렬 처리에 유리하다. 데이터를 층(Layer)으로 쌓아 “건너뛰며” 검색하는 방식이다.

3. 왜 이렇게 복잡하게 구현했을까?

레디스의 설계 철학은 “메모리는 비싸고 귀하다”이다. 예를 들어, 데이터 개수가 적을 때는 데이터를 압축해서 저장하는 ZipList를 쓰다가, 일정 개수를 넘어가면 검색 속도가 빠른 자료구조로 자동 변환(Conversion)한다.

자료구조	적은 데이터 (Memory Saving)	많은 데이터 (Performance)
Hash	ZipList (선형 탐색)	Hash Table (상수 시간)
Set	IntSet (정수 배열)	Hash Table
Sorted Set	ZipList	SkipList + Hash Table