Redis ‐ Redis 자료구조 - thought-corner/Backend-PlayGround GitHub Wiki

Redis ‐ Redis 자료구조

Redis 개요

  • Redis(Remote Dictionary Server)
    • 고성능의 키-값 저장소로 거대한 맵 데이터 저장소 형태를 가지고 데이터를 메모리에 저장해 빠른 읽기와 쓰기를 지원한다.
    • 주로 캐싱, 인증 관리, DB 동시성 제어 등에서 다양한 목적으로 사용
  • Redis 주요 특징
    • key-value로 구성된 단순화된 데이터 구조로 SQL 쿼리 사용 불필요
    • 인메모리 NoSQL 데이터베이스로서 빠른 성능을 자랑
    • RDB는 기본적으로 디스크에 저장하고 필요시에 메모리를 캐싱하는 것이므로 RDB보다 훨씬 빠른 성능
    • Redis의 메모리 상의 데이터는 주기적으로 스냅샷 디스크에 저장된다.
  • key-value는 구조적으로 해시 테이블을 사용함으로서 매우 빠른 속도(=O(1))로 데이터 검색이 가능
  • Single Thread 구조이기 때문에 동시성 이슈가 발생하지 않는다.
  • 윈도우 서버에서는 지원X, Linux 서버 및 MAC OS등에서 사용 가능

Redis 자료구조

  • Redis는 0~15번까지의 데이터베이스로 구성(default는 0번 DB)
select DB 번호

String 자료구조

  • 데이터를 String 형태의 value로 저장
  • 가장 일반적인 "key - value" 구조 형태
  • 바이너리 세이프(Binary Safe) : 텍스트 저장, 숫자 저장, 이진 데이터 저장, 직렬화된 객체 형태
  • 최대 512MB 크기 제한 : 작은 값을 권장, 메모리 효율성 고려
  • 각 타입에 맞는 3가지 인코딩 방식을 제공 → 효율적인 영속화를 위해서
    • int : Redis 객체 헤더(16바이트) + 정수값(8바이트) = 약 24바이트
    • embstr : Redis 객체와 SDS를 합쳐서 약 20바이트 + 문자열 길이
    • raw : Redis 객체(16바이트) + SDS 헤더(8바이트) + 문자열 길이 + 여유 공긴
  • 다음과 같이 GET, SET을 사용하며 GET은 읽기, SET은 쓰기를 위한 명령어이다.
  • INCR, DECR, INCRBY, DECRBY의 명령어에서 만약 키가 존재하지 않는 경우 카운터 초기화와 증감 연산을 모두 처리해준다.
  • Redis는 기본적으로 싱글 쓰레드(Single-Thread) 모델 위에서 동작한다. 즉, 여러 클라이언트가 동시에 INCR 요청을 보내더라도 Redis 서버 내부에서는 이 요청들이 순차적으로 하나씩 처리된다.
  • 한 번에 하나의 명령어만 처리하기 때문에 한 명령어가 수행되는 동안 다른 명령어가 끼어들어 데이터(값)를 수정할 수 없다.
  • 일반적인 멀티 쓰레드 환경에서 [값 읽기 → 1 더하기 → 값 저장하기] 이 3단계 과정을 수행하는 과정에서 다른 쓰레드가 개입하면 Race Condition이 발생한다.
  • Redis의 경우 위의 3단계 과정을 하나의 덩어리로 묶어서 원자적으로 처리한다. 싱글 쓰레드가 이 덩어리를 통째로 처리하고 다음 요청으로 넘어가기 때문에 별도의 복잡한 잠금 메커니즘없이도 동시성 이슈를 자연스럽게 해결할 수 있다.
  • 엄밀히 말하자면 메인 루프가 명령어를 처리하는 동안 블로킹 상태가 되는 것이 맞다고 볼 수 있다.
  • 하지만 Redis는 모든 데이터를 메모리 위에서 처리하기 때문에 개별 명령어의 실행 속도가 매우 빠르고 사용자 입장에서 거의 블로킹을 느끼지 못해 매우 높은 처리량(Throughput)을 보여준다.

❗이 때, KEYS *와 같이 처리 시간이 오래 걸리는 명령어를 실행하게 되면 메인 쓰레드가 점유되어 뒤에 대기 중인 다른 명령어들이 정말로 블로킹되면서 서비스 장애가 발생할 수 있으니 KEYS 명령어는 운영 환경에서 절대로 사용하면 안 된다.

  • Redis 자체의 처리 시간은 짧으나 네트워크 왕복 시간은 Redis가 제어를 할 수 없는 영역이다.
  • RTT(Round Trip Time) 자체를 줄이기 위해 여러 값을 읽고 넣을 수 있는 MSET, MGET을 제공한다.
  • 메모리는 제한적이기 때문에 만료일자를 지정해두고 사용해서 오래된 데이터를 제거해주어야 한다.
  • SETEX, SETNX는 TTL을 부여해서 키의 생명주기를 직접 조절할 수 있다.

List 자료구조

  • Redis의 List 자료구조는 기본적으로 LinkedList 형태로 구성되어 있다.
  • 어느 지점을 건드리는지에 따라 성능이 극명히 갈린다.
작업 유형 명령어 예시 시간 복잡도 설명
양 끝 삽입/삭제 LPUSH, RPUSH, LPOP, RPOP O(1) 양방향 포인터를 가지고 있어 즉시 접근이 가능하다.
인덱스 조회 LINDEX O(N) 인덱스만큼 노드를 타고 이동해야 한다.
중간 삽입/삭제 LINSERT, LREM O(N) 특정 위치나 값을 찾기 위한 탐색 과정(O(N))이 필요하다.
범위 조회 LRANGE O(S + N) 시작 지점까지의 거리(S)와 가져올 개수(N)만큼에 비례한다.
  • 단순히 Linked List만 쓰자니 포인터가 차지하는 메모리가 너무 비효율적이고 데이터가 파편화되어 CPU 캐시 효율이 떨어지는 문제를 해결하기 위해 quicklist가 등장했다.
  • 여러 개의 Listpack(ziplist)을 Doubly Linked List 형태로 연결한 구조가 quicklist이다.
    • 메모리 절약 : 노드 간의 포인터 개수를 획기적으로 줄인다.
    • 성능 향상 : 연속된 메모리 공간(Listpack(ziplist))에 데이터를 모아두어 CPU 캐시 적중률을 높인다.
  • LPUSH : 가장 앞은 단 한 번에 찾을 수 있기 때문에 시간 복잡도는 O(1)이다.
  • RPUSH : Redis의 Linked List는 양방향 연결 리스트 구조이다. 즉, 마지막 노드를 찾기 위해 전체를 순회할 필요가 없다. 그렇기 때문에 시간 복잡도는 O(1)이다.
  • LPOP : LPUSH와 마찬가지로 O(1)이다.
  • RPOP : RPUSH와 마찬가지로 O(1)이다.
  • LRANGE는 리스트의 start 인덱스부터 stop 인덱스까지의 모든 요소를 가져온다.
    • 양수 인덱스(0부터 시작)
    • 음수 인덱스(-1부터 시작)
  • Redis는 연결 리스트 기반이기 때문에 특정 위치를 찾으려면 포인터를 타고 이동해야 한다.
  • S(start offset) : 시작 지점까지 찾아가는 거리
  • N(number of elements) : 시작 지점부터 가져올 요소의 개수
  • 즉, 리스트의 아주 깊숙한 지점부터 데이터를 가져오라고 한다면 데이터 양에 비례하기 때문에 시간 복잡도를 따진다면 O(N)이 된다.
  • LLEN
    • Redis는 List 객체를 생성할 때, 내부에 len이라는 필드를 두고 요소가 추가되거나 삭제될 때마다 이 값을 읽어서 실시간으로 업데이트한다.
    • 그렇기 때문에 LLEN 명령이 들어오면 리스트를 훑는 것이 아니라 메모리에 저장된 숫자 하나를 그냥 읽어서 반환한다.
  • LINDEX
    • 반면, 특정 위치의 데이터를 가져오는 LINDEX는 연결 리스트의 태생적 한계를 그대로 가진다.
    • 인덱스 번호가 커질수록 그에 비례해서 탐색 시간에 들어가는 비용이 증가하기 때문에 시간 복잡도는 O(N)이다.
    • 그나마 다행인 점은 Redis가 양방향(Doubly) 구조이기 때문에 무조건 앞에서부터 가는 것이 아니라 뒤쪽에서 접근하는 것이 효율적이라면 Head 혹은 Tail이든 선택해서 탐색을 한다.
  • 각 명령어의 시간 복잡도와 저장 형태에 맞춰서 잘 사용하는 것이 중요하다.

Set 자료구조

1. 중복 없는 컬렉션

  • Redis Set은 수학의 '집합'과 동일하게 중복된 데이터를 허용하지 않는다.
  • 만약 이미 Set에 존재하는 값을 다시 추가하려고 하면 무시된다. 따라서 데이터의 고유성을 보장해야 할 때 매우 유용하다.

2. 순서 없음(Unordered)

  • 데이터가 입력된 순서를 기억하는 List와 달리, Set은 데이터의 순서를 유지하지 않는다.
  • 데이터를 조회할 때 입력했던 순서대로 반환된다는 보장이 없으므로 순서가 중요한 데이터에는 적합하지 않다.

3. 매우 빠른 검색

  • 특정 데이터가 Set 안에 포함되어 있는지(존재 여부)를 확인하는 속도가 데이터의 양과 관계없이 항상 일정하고 매우 빠르다.
  • 해시 테이블 구조를 사용하기 때문에 엄청난 양의 데이터 속에서도 즉시 검색이 가능하다.

4. 집합 연산 지원

  • 다수의 Set 간에 수학적인 집합 연산을 데이터베이스 레벨에서 강력하고 빠르게 지원한다.

1. SADD(Set ADD) - 요소 추가

  • SADD는 Set에 새로운 데이터를 집어넣을 때 사용하는 명령어이다.
  • 중복 무시, 유일성 보장 : 여러 개의 데이터를 한 번에 추가하려고 시도하더라도, 이미 Set 내부에 존재하는 값이라면 무시하고 넘어간다.
  • 추가된 개수 반환: 명령을 실행한 후, Redis는 실제로 새롭게 추가된 데이터의 개수를 숫자로 반환한다.

2. SREM(Set REMove) - 요소 제거

  • SREM은 Set에서 특정 데이터를 삭제할 때 사용하는 명령어이다.
  • 존재하는 요소만 제거 : 지우고자 하는 데이터를 지정했을 때, 해당 데이터가 Set 안에 실제로 존재할 때만 삭제 작업을 수행한다. 만약 Set에 없는 엉뚱한 데이터를 지우라고 명령하더라도, 시스템 오류를 발생시키지 않고 조용히 무시하고 넘어간다.
  • 제거된 개수 반환: SADD와 마찬가지로, 명령 실행 후 실제로 삭제에 성공한 데이터의 개수를 반환한다.

1. SMEMBERS - 모든 요소 조회

  • 특정 Set 안에 들어있는 모든 데이터를 한 번에 가져오고 싶을 때 사용하는 명령어이다.
  • 전체 요소 배열 반환 : Set 내부에 저장된 모든 고유한 값들을 모아 하나의 배열(Array) 형태로 반환한다.
  • 시간 복잡도 O(N) : 이 명령어는 Set에 들어있는 데이터의 총 개수(N)에 비례하여 처리 시간이 늘어난다. 수십만~수백만 개의 데이터가 쌓인 Set에서 이 명령어를 실행하면 Redis 서버 전체에 심각한 성능 저하를 유발할 수 있으므로 주의해서 사용해야 한다.

2. SISMEMBER - 존재 확인

  • 찾고자 하는 특정 값이 이 Set 안에 포함되어 있는지(멤버가 맞는지) 질문할 때 사용하는 명령어이다.
  • 전체 데이터를 가져오는 것이 아니라, 오직 논리적인 참/거짓 결과만 숫자로 반환한다.
  • 시간 복잡도 O(1) : Set 내부의 데이터가 10개이든 1,000만 개이든 전혀 상관없이, 항상 즉시(일정한 시간 내에) 결과를 반환한다.

Hash 자료구조

1. Field-Value 쌍 저장

  • Redis Hash는 하나의 거대한 Key 안에 또 다시 여러 개의 필드(Field)와 값(Value)이 짝을 지어 저장되는 구조이다.

2. 객체 표현에 최적화

  • 관계형 데이터베이스(RDBMS)의 '행(Row)'이나 프로그래밍의 '객체(Object)' 데이터를 표현하는 데 유용하다.

3. 메모리 효율적(압축 인코딩 지원)

  • 객체 데이터를 각각 개별적인 일반 Key-Value로 저장하는 것보다, 하나의 Hash 안에 여러 Field로 모아서 저장하는 것이 메모리 사용량 측면에서 훨씬 효율적이다.
  • Redis는 Hash 내부의 필드 개수가 적고 값의 길이가 짧을 때, 내부적으로 특별한 압축 인코딩 방식(Ziplist 등)을 사용하여 메모리 공간을 극적으로 절약해준다.

4. 부분 업데이트 가능(필드별 개별 접근)

  • 하나의 거대한 텍스트나 JSON 형태로 전체 데이터를 저장하면 데이터 일부만 바꾸고 싶을 때도 전체를 다 불러와서 수정한 뒤 다시 덮어써야 한다.
  • Hash를 사용하면 원하는 특정 필드에만 직접 접근하여 값을 읽거나 수정할 수 있다.

1. HSET(Hash SET) - 필드 설정

  • HSET은 Hash 구조(Key) 안에 특정 필드(Field)와 그에 해당하는 값(Value)을 저장하거나 수정할 때 사용하는 명령어이다.
  • 단일/다중 필드 설정 : 과거에는 하나의 필드만 설정하는 HSET과 여러 필드를 동시에 설정하는 HMSET이 구분되어 있었으나, 최신 Redis 버전부터는 HSET 명령어 하나로 통합되었다.

2. HGET(Hash GET) - 필드 조회

  • HGET은 Hash 구조 안에 저장된 여러 정보 중 내가 딱 원하는 특정 필드의 값만 읽어올 때 사용하는 명령어이다.
  • 단일 필드 값 반환 : 불필요한 데이터를 네트워크로 전송하지 않아도 되므로 트래픽을 아끼고 속도를 높일 수 있다.

3. 시간 복잡도: O(1) per field

  • Hash 안에 필드가 10개가 있든 10만 개가 있든, 특정 필드 하나를 콕 집어서 값을 읽거나 쓰는 데 걸리는 시간은 데이터 양과 무관하게 항상 O(1)으로 일정하다.
  • per field(필드 당) : 전체 데이터의 크기가 아니라 내가 한 번의 명령어로 조작하려는 필드의 개수에만 비례하여 정직하게 시간이 걸린다.

1. HMSET(Hash Multiple SET) - 여러 필드 설정

  • HMSET은 한 번의 명령으로 Hash 안에 여러 개의 필드와 값을 동시에 집어넣을 때 사용하던 명령어이다.
  • HSET으로 대체 : 최신 버전의 Redis(4.0 이후)에서는 기존의 단일 필드용 명령어였던 HSET이 여러 필드를 동시에 설정할 수 있도록 기능이 변경되었다. 따라서 굳이 HMSET을 쓸 이유가 없다.
  • 하위 호환성 유지 : 과거에 HMSET을 사용해서 만들어진 수많은 기존 프로그램들이 갑자기 작동을 멈추면 안 되기 때문에, Redis 측에서 명령어 자체는 계속 정상적으로 동작하도록 하위 호환성을 보장해 주고 있다.

2. HMGET(Hash Multiple GET) - 여러 필드 조회

  • HMGET은 Hash 안에 있는 수많은 정보 중, 내가 딱 필요한 '여러 개'의 필드 값만 쏙쏙 골라서 한 번에 가져오고 싶을 때 사용하는 매우 유용한 명령어이다.
  • 배열로 값 반환 : 요청한 여러 필드에 해당하는 값들을 모아서 하나의 배열(Array) 리스트 형태로 묶어서 반환해준다.
  • 필드 순서 보존 : 반환되는 배열 안의 데이터 순서는 내가 명령어를 입력할 때 요청한 필드의 순서와 정확히 일치한다.

1. HINCRBY - 정수 증가

  • HINCRBY는 필드에 저장된 값이 정수(Integer)일 때, 지정한 숫자만큼 값을 더해주는 명령어이다.
  • 64비트 정수 범위 : 내부적으로 64비트 크기의 부호 있는 정수(Signed Integer)를 지원한다. 약 -900경에서 +900경 사이의 매우 거대한 숫자도 처리할 수 있어, 오버플로우 걱정 없이 안전하게 다룰 수 있다.
  • 증감 모두 가능 : 증가시킬 값으로 양수를 넣으면 값이 올라가고, 음수(예: -1)를 입력하면 더하기의 역연산으로 결과적으로 값을 감소시킨다.

2. HINCRBYFLOAT - 실수 증가

  • HINCRBYFLOAT는 필드에 저장된 값이 실수(소수점이 있는 숫자)일 때, 지정한 수치만큼 더해주는 명령어이다.
  • 배정밀도 부동소수점(Double-precision floating-point) : 컴퓨터가 소수를 표현하는 정교한 방식으로, 소수점 아래 계산 시 발생할 수 있는 미세한 오차를 최소화한다.

3. 원자적 연산(Atomic Operation)

  • 데이터 일관성 완벽 보장 : Redis는 이 명령들을 절대 쪼개거나 섞지 않고 한 번에 하나씩 온전하게(=원자적으로) 처리해낸다.
  • 동시성 문제(Race Condition) 원천 차단 : 해당 명령어들을 사용하면 누락이나 충돌 없이 정확하게 세는 것을 100% 보장한다.

1. HEXISTS - 필드 존재 확인

  • HEXISTS는 특정 Hash 안에 내가 찾고자 하는 필드가 실제로 존재하는지 여부만 빠르게 검사할 때 사용한다.
  • O(1) 시간복잡도 및 빠른 체크 : 값을 굳이 네트워크로 가져올 필요 없이 로직상 '유무'만 판단해야 할 때 시스템 자원을 아끼며 아주 빠르게 사용할 수 있다.

2. HKEYS - 모든 필드명 조회

  • HKEYS는 특정 Hash 안에 저장된 모든 필드(Field)의 이름들만 쏙쏙 뽑아서 배열 형태로 반환한다.

3. HVALS - 모든 값 조회

  • HVALS는 Hash 안에 저장된 모든 값(Value)들만 모아서 배열로 반환한다.

Sorted Set 자료구조

1. 중복 없는 요소 (Set의 유일성)

  • 이미 존재하는 Member를 다시 삽입하려고 하면, 새로운 Member가 추가되는 것이 아니라 기존 Member의 Score 값만 새로운 값으로 업데이트되며, 그에 맞게 정렬 위치가 재조정된다.

2. 내부 자료구조: Skip List + Hash Table

  • Hash Table
  • Skip List(스킵 리스트)
    • 일반적인 연결 리스트와 달리, 중간 노드들을 건너뛸 수 있는(Skip) 여러 계층의 포인터를 가진다.
    • 이로 인해 이진 탐색 트리(Balanced Tree)와 유사하게 검색, 삽입, 삭제 시 시간 복잡도 O(log N)을 가진다.
    • 트리 구조에 비해 구현이 단순하고, 범위 탐색(Range Query) 시 노드를 순차적으로 따라가기만 하면 되므로 성능상 훨씬 유리하다.

3. 범위 조회 지원

  • 정렬된 상태를 유지하므로, 특정 구간에 대한 조회가 매우 빠르다.
  • 시간 복잡도는 O(log N + M)(N은 전체 요소 수, M은 반환되는 요소 수)으로 대규모 트래픽에서도 안정적으로 동작한다.

1. 요소 존재 여부 확인(추가 또는 업데이트 분기)

  • Redis는 내부적으로 유지하고 있는 Hash Table을 활용하여 데이터가 이미 존재하는지 O(1)의 속도로 빠르게 확인한다.
    • 새 요소 삽입 : Hash Table에 데이터가 없다면 완전히 새로운 데이터로 간주하고 Skip List에 새로운 노드를 생성하여 배치한다.
    • 기존 요소 변경 : Hash Table에 데이터가 있다면 기존 데이터를 지우고 새로 쓰는 것이 아니라 새로운 값으로 덮어쓴다.

2. 시간 복잡도 O(log N) 보장

  • 새로운 요소를 삽입할 위치를 찾거나 변경된 기존 요소를 새로운 위치로 옮길 때 Redis는 전체 데이터를 순차 탐색하지 않는다.
  • 다층 연결 리스트 구조인 Skip List를 타며 탐색하기 때문에 이진 탐색 트리와 동일한 O(log N)의 시간 복잡도로 빠르게 정렬 위치를 찾아낸다.

3. 자동 정렬 위치 조정

  • 적절한 위치를 찾았다면 노드들의 포인터를 수정하여 데이터를 끼워 넣거나 이동시킨다.
  • 이 과정이 끝나면 데이터는 오름차순으로 완벽하게 정렬된 상태를 유지하게 된다.
  • ZRANGE(오름차순 조회)
  • ZREVRANGE(내림차순 조회)
  • Redis Sorted Set에서는 O(log N + M)의 시간 복잡도가 나오게 된다. 이 때, 전체 요소의 수는 N, 반환할 요소의 수를 M이라고 한다.
    • 시작점 찾기 : O(log N), Skip List 구조를 통해 이진 탐색 수준의 속도를 가지게 된다.
    • 순차적 탐색 : O(M), 그 노드부터 메모리 상에 연결된 포인터를 따라 지정한 개수만큼 옆으로 이동하며 데이터를 쭉 읽어오기만 하면 된다.
  • ZRANK(오름차순 순위)
  • ZREVRANK(내림차순 순위)
  • Skip List는, 노드와 노드를 연결하는 포인터에 단순히 다음 노드의 주소만 저장하는 것이 아니라 몇 개의 노드를 건너뛰고 있는지에 대한 숫자 정보도 함께 저장한다.
  • Redis는 Skip List의 최상단부터 해당 요소를 찾아 내려가면서 거쳐온 경로의 Span 값들을 단순히 더하기만 한다.
  • 데이터를 일일이 세지 않고 건너뛴 덩어리의 개수만 합산하여 타겟에 도달하기 때문에, 탐색 시간만으로 정확한 전체 순위를 계산할 수 있게 된다.
  • ZINCRBY(점수 증감 명령어)
  • 양수/음수 모두 가능(증가 및 감소) : 덧셈, 뺄셈과 같은 기본 연산이 가능하며 만약 키나 요소가 존재하지 않는다면 초기값을 0으로 간주하고 입력한 값으로 새롭게 요소를 생성한 뒤 정렬 위치를 맞춘다.
  • ZREM(요소 삭제 명령어)
  • 지정 요소 삭제 및 다중 삭제(Multiple Deletion) : 특정 요소 1개만 지울 수도 있지만, 여러 개의 요소를 한 번의 명령어로 동시에 지울 수도 있다.
  • 시간 복잡도 O(M log N) : 현재 Sorted Set에 존재하는 전체 요소의 개수를 N, 이번 명령어로 삭제하려고 요청한 요소의 개수를 M이라고 할 때, Skip List를 타며 이진 탐색 수준인 O(log N)이 걸리고 여러 개를 지우라고 명령을 내리게 되면 O(log N)의 탐색 및 삭제 과정을 M번 반복하므로 최종적으로 O(M log N)이 된다.
  • 삭제된 개수 반환(멱등성 보장) : 실제로 지워진 요소의 개수를 정수형(Integer)으로 반환한다.