Post

Why is Redis So Fast

Posted Updated
By junsu
18 min read
Why is Redis So Fast

RAM based

RAM based 이미지

Redis가 빠른 가장 근본적인 이유는 데이터를 디스크가 아닌 RAM에 저장하기 때문이다. 메모리 계층 구조를 보면 RAM 접근 속도는 약 120ns인 반면, SSD는 50~150us, HDD는 1~10ms가 걸린다. 즉 RAM은 SSD보다 약 1,000배, HDD보다는 최대 100,000배 가까이 빠르다.

MySQL 같은 디스크 기반 RDBMS는 데이터를 읽고 쓸 때마다 디스크 I/O가 발생하고, 이 과정에서 디스크 탐색(seek) 시간과 회전 지연(HDD의 경우) 또는 페이지 캐시 미스로 인한 지연이 병목이 된다. 반면 Redis는 모든 데이터를 메모리에 올려두기 때문에 이러한 디스크 I/O 병목 자체가 없고, 요청이 들어오면 RAM에서 바로 값을 읽거나 써서 응답할 수 있다.

이런 구조 덕분에 Redis는 단일 인스턴스에서도 초당 약 10만~100만 건(100K~1M ops/sec) 수준의 처리량을 낼 수 있다. 단순 GET/SET 같은 명령은 초당 10만 건 이상 처리가 가능하며, 파이프라이닝(pipelining)을 활용해 여러 명령을 한 번에 묶어 보내면 네트워크 왕복(RTT) 오버헤드가 줄어들어 초당 100만 건 이상까지도 처리량을 끌어올릴 수 있다.

Redis는 기본적으로 요청-응답(request-response) 방식으로 동작한다. 클라이언트가 명령어를 보내고 서버의 응답을 받아야 다음 명령어를 보낼 수 있기 때문에, 명령어를 N개 실행하면 네트워크 왕복(RTT)도 N번 발생한다. Redis 자체의 명령어 처리 시간은 수십~수백 ns에 불과하지만, RTT는 로컬 네트워크에서도 수백 us~수 ms가 걸릴 수 있어 실제 지연의 대부분은 RTT에서 발생한다. 파이프라이닝은 응답을 기다리지 않고 여러 명령어를 연속으로 보낸 뒤 응답들을 한꺼번에 받아오는 방식으로, RTT 횟수를 N번에서 사실상 1번으로 줄여 처리량을 크게 끌어올린다.

IO multiplexing & Single-threaded READ/WRITE

IO multiplexing & Single-threaded READ/WRITE 이미지

Redis에는 수많은 클라이언트가 각자의 소켓(Socket1, Socket2, Socket3, …)으로 동시에 연결된다. 만약 Redis가 소켓 하나마다 스레드를 하나씩 할당해서 처리한다면(thread-per-connection 방식), 연결 수가 늘어날수록 스레드 컨텍스트 스위칭 비용과 락(lock) 경합이 커져서 오히려 성능이 떨어진다.

이를 피하기 위해 Redis는 I/O 멀티플렉싱(I/O Multiplexing)을 사용한다. OS가 제공하는 epoll(Linux), kqueue(BSD/macOS) 같은 메커니즘을 통해, 하나의 주체가 여러 소켓을 동시에 감시(watch)하면서 어떤 소켓에 읽을 데이터가 들어왔는지 혹은 쓰기가 가능한 상태인지를 논블로킹(non-blocking)으로 확인한다. 각 소켓을 개별적으로 blocking read 하는 대신, “준비된(ready) 소켓들”만 골라내는 것이다. 이 감시 작업 자체는 필요에 따라 멀티스레드로 처리될 수 있다(그림의 IO Multiplex 박스 하단에 표시된 multi-threaded 부분).

이렇게 준비된 이벤트들은 이벤트 루프(Event Loop)로 전달된다. 이벤트 루프는 단일 스레드(single-threaded)로 동작하며, 준비된 이벤트를 하나씩 꺼내 Task Queue에 쌓고, Event Dispatcher가 이를 Event Processor로 넘겨 실제 GET/SET 같은 명령어를 순서대로 처리한다.

명령어 실행 자체를 단일 스레드로 처리하는 이유는 다음과 같다.

  • 락(lock)이 필요 없다: 하나의 스레드만 메모리의 자료구조에 접근하므로 뮤텍스나 락을 걸 필요가 없고, 그만큼 락 획득/해제 오버헤드와 경쟁(contention)이 사라진다.
  • 컨텍스트 스위칭 비용이 없다: 여러 스레드가 번갈아 CPU를 점유하며 발생하는 컨텍스트 스위칭 비용이 없다.
  • 원자성이 보장된다: 한 번에 하나의 명령어만 실행되므로 별도의 동시성 제어 없이도 명령어 단위의 원자적 실행이 자연스럽게 보장된다.

즉, I/O(네트워크 송수신 대기)는 멀티플렉싱으로 효율적으로 처리하고, 실제 연산(명령어 실행)은 단일 스레드로 처리함으로써 락 오버헤드 없이 빠르고 예측 가능한 성능을 낼 수 있는 것이다. (참고로 Redis 6.0부터는 소켓의 읽기/쓰기 자체를 여러 스레드로 병렬화하는 I/O 스레딩이 추가되었지만, 명령어 실행 로직은 여전히 단일 스레드로 동작한다.)

Efficient Data Structure

Efficient Data Structure 이미지

Redis는 사용자에게 보이는 자료형(String, List, Hash, Set, Sorted Set)마다 내부적으로 최적화된 인코딩을 사용한다. 데이터 크기가 작을 때는 메모리를 아낄 수 있는 압축된 구조를, 데이터가 커지면 조회 성능이 좋은 구조로 자동 전환한다.

자료형내부 구조
StringSDS (Simple Dynamic String)
ListLinkedList (quicklist)
HashZipList → HashTable
SetIntSet / ZipList → HashTable
Sorted SetZipList → SkipList

SDS (Simple Dynamic String)

String 타입은 C의 기본 문자열이 아니라 Redis가 직접 구현한 SDS를 사용한다.

1
2
3
4
5

struct sdshdr {
    int len;     // 현재 문자열 길이 (buf에서 사용 중인 바이트 수)
    int free;    // 할당됐지만 아직 쓰이지 않은 여유 공간
    char buf[];  // 실제 문자열 데이터 + 널 종료 문자
};

예를 들어 “Redis”를 저장하면 length: 5, buffer: "Redis\0" 형태가 된다. 일반 C 문자열과 비교했을 때 SDS는 다음과 같은 이점이 있다.

  • O(1) 길이 조회: C 문자열은 길이를 알기 위해 \0까지 순회(O(N))해야 하지만, SDS는 len 필드를 바로 읽으면 되므로 O(1)이다.
  • 미리 할당된 공간 재사용: 문자열을 늘릴 때마다 매번 realloc 하지 않고, free에 기록된 여유 공간을 먼저 사용한다. 공간이 부족할 때만 필요한 것보다 더 크게 미리 할당해 다음 확장에 대비한다.
  • 버퍼 오버플로우 방지: 길이 정보를 자체적으로 관리하기 때문에 strcat 같은 연산에서 발생하는 오버플로우 문제로부터 안전하다.

ZipList

List, Hash, Sorted Set은 원소 개수가 적을 때 ZipList를 사용한다. 노드마다 포인터를 갖는 LinkedList와 달리, 메모리에 연속된 하나의 블록으로 데이터를 꽉꽉 채워 넣는 구조다.

1

[zlbytes][zltail][zllen][entry1][entry2] ... [entryN][zlend]
  • zlbytes: 전체 ZipList의 바이트 크기
  • zltail: 마지막 entry의 위치(오프셋) — 뒤에서부터 접근할 때 사용
  • zllen: entry(원소) 개수
  • entry: prevlen(바로 이전 entry의 길이, 역방향 탐색용) + encoding(데이터 타입/길이 정보) + 실제 데이터
  • zlend: 끝을 알리는 종료 마커(0xFF)

노드마다 prev/next 포인터를 따로 두는 LinkedList는 64비트 환경 기준 노드당 16바이트 이상의 포인터 오버헤드가 붙지만, ZipList는 데이터를 그냥 나란히 붙여서 저장하므로 그런 오버헤드가 없다. 대신 원소를 찾으려면 처음부터 순서대로 읽어야 해서 조회는 O(N)이다. 그래서 원소 수가 적을 때(기본 128개 이하 등 설정값 기준)는 ZipList로 메모리를 아끼다가, 개수나 데이터 크기가 임계값을 넘으면 HashTable/SkipList 같은 범용 구조로 자동 전환된다.

IntSet

Set의 원소가 전부 정수일 때만 사용하는 구조로, 정수를 크기순으로 정렬해 담아둔 배열이다.

1
2
3
4
5

struct intset {
    uint32_t encoding;  // 원소 타입 (INT16 / INT32 / INT64)
    uint32_t length;    // 원소 개수
    int8_t contents[];  // 정렬된 상태로 저장된 실제 정수 값들
};

데이터가 정렬된 배열이기 때문에 이진 탐색(O(log N))으로 값을 찾을 수 있다. 처음엔 가장 작은 타입(int16)으로 시작하다가, 그보다 큰 정수가 들어오면 배열 전체를 더 큰 타입(int32 → int64)으로 업그레이드한다. HashTable처럼 버킷이나 포인터 체인을 쓰지 않고 정수를 그대로 붙여서 저장하기 때문에, 정수 집합에 한해서는 메모리 효율이 매우 좋다.

즉 ZipList와 IntSet 모두 “데이터가 작고 단순할 때는 포인터·해시 오버헤드 없는 연속 메모리 구조로 압축해서 저장하고, 커지면 범용 구조(HashTable/SkipList)로 갈아탄다”는 Redis의 공통 전략을 보여준다.

SkipList

Sorted Set은 각 원소가 score 기준으로 정렬되어 있어야 하는데, 이를 위해 여러 층(level)의 인덱스를 갖는 SkipList를 사용한다.

1
2
3
4
5
6
7
8
9
10

typedef struct zskiplistNode {
    sds ele;                          // 저장된 값(멤버)
    double score;                     // 정렬 기준이 되는 점수
    struct zskiplistNode *backward;   // 이전 노드 포인터

    struct zskiplistLevel {
        struct zskiplistNode *forward; // 해당 레벨에서 다음 노드 포인터
        unsigned long span;            // 다음 노드까지 건너뛴 원소 수
    } level[];                          // 노드마다 랜덤하게 결정되는 레벨 배열
} zskiplistNode;

이미지의 예시처럼 가장 아래층은 모든 원소(1, 2, 4, 6, 9, 13, 18, 25, 31)를 순서대로 연결한 일반 연결 리스트고, 위로 갈수록 일부 원소만 골라 건너뛰는 상위 인덱스(1 → 9 → 31 등)가 쌓인다. 특정 값을 찾을 때는 최상위 레벨에서 시작해서, 다음 노드의 score가 목표값보다 작거나 같으면 오른쪽으로 이동하고, 넘어서면 한 층 아래로 내려가는 식으로 탐색한다.

이렇게 여러 층을 오가며 필요 없는 노드를 건너뛰기 때문에, 전체를 순회하는 LinkedList의 O(N) 탐색과 달리 SkipList는 평균 O(log N)의 시간 복잡도로 검색·삽입·삭제가 가능하다. 앞서 본 ZipList와 마찬가지로, Sorted Set 역시 원소 개수가 적을 때는 ZipList를 쓰다가 개수나 크기가 임계값을 넘으면 SkipList로 자동 전환된다.

Simple Commands

자료구조가 효율적인 것과 별개로, Redis가 지원하는 명령어 자체가 단순하고 예측 가능한 연산이라는 점도 속도에 큰 영향을 준다.

  • 명령어가 자료구조 연산에 1:1로 매핑된다: GET/SET은 SDS 조회·할당, LPUSH는 quicklist 헤드에 삽입, HSET은 HashTable에 키-값 삽입, ZADD는 SkipList 삽입처럼, 명령어 하나가 곧바로 해당 자료구조의 기본 연산으로 이어진다. RDBMS처럼 쿼리를 분석해서 최적의 실행 계획을 찾는 옵티마이저(query planner) 같은 중간 단계가 없다.
  • 모든 명령어의 시간복잡도가 정해져 있고 대부분 O(1)~O(log N)이다: 공식 문서에 명령어마다 Big-O 복잡도가 명시되어 있을 정도로 실행 비용이 예측 가능하다. KEYS *처럼 O(N)인 명령어는 오히려 “위험한 명령어”로 별도 취급될 정도로, 나머지 대부분은 상수 시간이나 로그 시간에 끝난다.
  • 프로토콜(RESP)이 단순하다: 클라이언트-서버 간 통신에 쓰는 RESP(REdis Serialization Protocol)는 텍스트 기반이지만 파싱 규칙이 매우 단순해서, SQL 파싱처럼 복잡한 문법 분석이 필요 없다.

정리하면 Redis가 빠른 이유는 한 가지가 아니라, RAM 기반이라 접근 자체가 빠르고, 락 없는 단일 스레드 이벤트 루프로 오버헤드가 없고, 자료구조가 데이터 크기에 맞게 효율적으로 선택되며, 명령어 자체도 조인·옵티마이저 없이 자료구조 연산에 바로 대응되는 단순한 구조라는 여러 요인이 함께 작용한 결과다.

System
시스템
This post is licensed under CC BY 4.0 by the author.

Trending Tags

시스템 기술 도서