Redis & Valkey에 대해 알아보자 - 원자성과 자료구조(Siphash, Skiplist)

💡 공부하며 작성한 내용으로 잘못된 내용이 있을 수 있습니다.
🌀 Valkey는 Redis의 포크 버전으로 기본 개념과 동작방식은 동일하기 때문에 명칭 생략했습니다.

 

💧 Redis의 원자성(Automicity)

• Redis는 모든 명령어가 원자적으로(Atomic) 실행되도록 설계되어 있습니다.
  • 즉, 하나의 명령어는 중간에 끼어들거나 나뉘지 않고, 완전히 실행되거나 아예 실행되지 않습니다.
• 예를 들어 INCR counter 명령어는 다른 클라이언트의 명령어가 중간에 끼어들 수 없이 한 번에 실행되기 때문에, 여러 클라이언트가 동시에 이 명령을 실행해도 값이 정확하게 증가합니다.
  • INCR counter 명령어는 특정 키의 숫자 값을 1 증가시키는 명령어입니다.
• 이러한 동작이 가능한 이유는 Redis가 단일 스레드 기반 아키텍처(single-threaded architecture)를 사용하기 때문입니다.
• Redis는 하나의 명령어를 처리하는 동안 다른 명령어는 대기 상태로 두며, 모든 명령어를 순차적으로 처리합니다.
• 덕분에 개발자는 별도의 락(Lock) 처리 없이도 안전하게 데이터를 다룰 수 있으며, race condition(경쟁 조건)에 대한 고민을 줄일 수 있습니다.
  • Race Condition은 여러 스레드나 프로세스가 동시에 같은 자원에 접근해 순서에 따라 결과가 달라지는 오류 상황을 말합니다.

 

🔧 Redis 클러스터에서도 명령은 Atomic한가?

• Redis 클러스터는 샤딩 방식을 이용해 여러 노드로 데이터를 분산해서 저장합니다.
• 각 노드는 자신의 키 범위(slot)에 대해 책임지며, 여전히 단일 스레드로 명령을 처리합니다.
• 즉, 노드 내부에서는 여전히 모든 명령이 Atomic 하게 실행됩니다.

✅ 예시

• 클러스터 노드 A에 있는 키 user1에 대한 명령 → 여전히 단일 스레드로 처리 → Atomic 보장

 

🚨 만약 여러 키를 동시에 조작하는 연산이 서로 다른 노드에 분산되어 있다면?

• 예를 들어 아래와 같은 명령어를 입력할 때입니다.

MSET user:1:name "손흥민" user:2:name "해리 케인"

• 만약 user:1:name은 노드 A, user:2:name은 노드 B에 있다면?
  • 이 명령은 두 노드에 나뉘어 실행되므로 Atomic하지 않습니다.
• Redis는 이런 경우 "CROSSSLOT" 에러를 발생시켜 실행을 막습니다.

 

😵‍💫 그럼에도 Race Condition 발생할 수 있다?!

여러 클라이언트가 동시에 Redis에서 같은 키를 GET 해서 값을 가져온 뒤 각자 계산한 결과를 SET 하면?

# 애플리케이션 A와 B 둘 다 동시에 실행
GET stock:item → A와 B 모두 1 읽음

# 두 애플리케이션에서 모두 "재고 있음"이라고 판단
# 재고가 있으면 차감하는 조건부 차감 방식이기 때문에 DECRBY(원하는 값만큼 감소)와 같은 단순 차감 명령어로는 해결 불가
# 애플리케이션 내 코드로 분기 처리해야 함(재고 있음, 없음)
# 각각 재고 -1 계산
SET stock:item 0 → A 실행
SET stock:item 0 → B 실행 (B가 A 결과를 덮어씀)

→ 누가 마지막에 쓰느냐에 따라 값이 덮어씌워질 수 있습니다

→ ❌ 실제로는 B는 재고 없음으로 요청이 실패되어야 함

 

 

🤓 해결책

-- 재고가 1 이상이면 1 차감
if tonumber(redis.call("GET", KEYS[1])) >= 1 then
  return redis.call("DECRBY", KEYS[1], 1)
else
  return -1
end

• 클라이언트에서 Lua 스크립트를 활용하여 Redis 내부에서 계산과 저장을 한 번에 실행하는 요청을 보낼 수 있습니다.
• 이를 Redis가 실행함으로써 조건 검사 + 차감을 내부에서 한 번에 처리할 수 있습니다.

 

📦 Redis의 기본 자료구조

Value 자료구조	설명	예시 명령어
String	기본 문자열 또는 숫자	SET, GET, INCR, DECR
List	순서 있는 문자열 리스트	LPUSH, LRANGE
Set	중복 없는 문자열 집합	SADD, SISMEMBER
Hash	필드-값 쌍의 집합 (딕셔너리)	HSET, HGET
Sorted Set	점수 기반 정렬된 집합	ZADD, ZRANGE

• Redis는 Key-Value 구조의 데이터베이스입니다.
• Redis에서 사용하는 모든 Key는 항상 문자열(String) 형태로 저장됩니다.
• 반면 Value는 다양한 자료구조로 저장될 수 있습니다.

 

🔸 String

SET user "Tom"
GET user            → "Tom"
INCR page           → 1, 2, 3, ...

• 가장 기본적인 자료형입니다.
• 문자열, 숫자, JSON 등 단일 값을 저장할 때 사용합니다.
• 숫자일 경우 INCR, DECR, INCRBY, DECRBY와 같이 연산도 가능합니다.
  • INCR, DECR는 숫자를 1 증가시키거나, 감소시키는 명령어입니다.
  • INCRBY, DECRBY는 원하는 숫자만큼 증가시키거나, 감소시키는 명령어입니다.
• 활용: JWT 토큰 저장, 특정 횟수 카운트 등

 

🔸 List

LPUSH queue "task1"
LPUSH queue "task2"
# start: 시작 인덱스(0부터 시작), stop: 끝 인덱스(포함), 음수 인덱스: -1은 리스트의 끝, -2는 끝에서 두번째
LRANGE queue 0 -1         → ["task2", "task1"]

• 순서가 있는 문자열 목록입니다.
• 스택이나 큐 구조로 구현 가능합니다.
• 양쪽 모두 삽입/삭제가 가능합니다.
  • LPUSH, LPOP는 왼쪽으로 데이터를 삽입/ 삭제합니다.
  • RPUSH, RPOP는 오른쪽으로 데이터를 삽입/ 삭제합니다.
  • LRANGE는 특정 범위의 요소들을 가져오는 명령어입니다. 
• 활용: 작업 큐 등

 

🔸 Set

SADD users "user1"
SADD users "user2"
SISMEMBER users "user1"   → 1

• 순서와 중복이 없습니다.
  • 중복이 없는 집합이기 때문에 빠르게 존재 여부를 확인할 수 있습니다.
• SADD는 집합에 요소를 추가하는 명령어입니다.
• SISMEMBER는 집합의 요소가 있는지 없는지 여부를 true(1)/false(0)으로 리턴하는 명령어입니다.
• 활용: 실시간 접속 유저, 태그 목록 등

 

🔸 Hash

HSET user1 name "Tom"
HSET user1 age "30"
HGET user1 name   → "Tom"
HGET user1 age   → "30"

# 내부 저장 방식
Key: user1 (하나의 HASH 자료구조)
Value:
  {
    "name": "Tom",
    "age": "30"
  }

• 하나의 키에 여러 필드-값 쌍을 저장 가능합니다.
• 마치 딕셔너리 또는 JSON 객체처럼 사용 가능합니다.
• 객체 형태로 값을 묶어서 관리하고 싶을 때 사용합니다.
• 활용: 사용자 정보 저장, 설정값 저장 등 

 

🔸 Sorted Set(ZSET) 

ZADD leaderboard 100 "Alice"
ZADD leaderboard 120 "Bob"
ZADD leaderboard 90 "Charlie"

ZRANGE leaderboard 0 -1 WITHSCORES
→ ["Charlie", "90", "Alice", "100", "Bob", "120"]

• Set과 유사하지만 Score(점수)를 기준으로 자동 정렬됩니다.
• 랭킹시스템에 최적화되어 있습니다.
• WITHSCORES는 점수 포함해서 보여줍니다.
• 활용: 게임 랭킹, 인기 상품 정렬 등

 

📚 Redis의 심화 자료구조

🔸 Redis에서의 해시 테이블(dict)

📦 Redis 내부 dict 구조 (해시테이블)
→ 해시함수(SipHash)를 통해 key를 해시하고,
→ 그 해시값 % 테이블 크기 = 버킷 인덱스
→ 해당 인덱스에 key-value 쌍(dictEntry)을 저장

🧱 dict 구조 예시 (테이블 크기 = 8)

[Bucket 0] ──▶ (empty)

[Bucket 1] ──▶ (empty)

[Bucket 2] ──▶ dictEntry(key="user1", val="Tom") 
                └─▶ dictEntry(key="user2", val="Jerry")

[Bucket 3] ──▶ dictEntry(key="product5", val="Shampoo")

[Bucket 4] ──▶ (empty)

[Bucket 5] ──▶ (empty)

[Bucket 6] ──▶ (empty)

[Bucket 7] ──▶ dictEntry(key="config1", val="xxxconfig")

# 예시
"user1" → hash("user1") = 42 → 배열 인덱스 42에 저장

• Redis는 내부적으로 모든 데이터를 해시테이블(dict)에 저장합니다.
• 해시테이블은 각 Key에 해시함수를 적용하여 메모리상에 저장할 인덱스를 계산합니다.
  • 이때 key 해싱은 SipHash를 사용하여 해시값을 생성합니다.
  • 이 계산은 수학적인 연산이므로 매우 빠르고 일정한 시간에 끝납니다.
• 해시테이블은 내부적으로 배열(Array)을 사용하기 때문에 해시값을 기반으로 한 인덱스를 통해 메모리에서 바로 접근이 가능합니다.
  • 데이터를 탐색하는 것이 아니라, 주소를 계산해서 직접 접근하므로 빠릅니다.
• 시간복잡도는 평균적으로 O(1)입니다.

 

🔹 dict

• Redis 소스코드에서 사용하는 C 언어 기반 해시테이블 구조체입니다.
• Redis는 이 구조체를 통해 모든 key - Value 데이터를 저장하고 관리합니다.

구성 요약

구성 요소	설명
ht[0], ht[1]	해시 테이블 두 개: 리해싱 중일 때 사용 (보통은 ht[0]만 사용, 아래에 자세히 설명)
hashFunction	key를 해시할 때 사용하는 함수 (보통 SipHash)
dictEntry	실제로 key와 value가 저장되는 엔트리 구조체
buckets	해시 버킷 배열. 해시값을 기준으로 key가 어떤 버킷에 들어갈지 결정됨
size, used	해시 테이블의 크기 및 실제 저장된 항목 수

 

🔹 SipHash

• 충돌 공격에 강한 해시 함수입니다.
  • 기존 해시 함수(MurmurHash 등)는 속도는 빠르지만, 해시 충돌을 쉽게 유도할 수 있어 공격에 취약합니다.
  • 예를 들어 해시 테이블의 여러 Key가 특정 버킷에 몰리는 해시 충돌을 의도적으로 발생시키는 Dos 공격이 발생할 수 있습니다.
  • 이때 O(1) -> O(n)으로 성능이 급격히 안 좋아집니다.
• SipHash 내부에 비밀키를 사용하여 해시함으로써 의도적인 충돌 유도를 어렵게 합니다.
  • Redis는 서버가 시작될 때 16바이트 크기의 무작위 비밀 키(seed)를 생성합니다.
  • 이 키는 메모리에만 저장되며, 외부에 노출되지 않고 디스크에도 기록되지 않습니다.
  • 모든 key 해싱 연산에 이 비밀 키가 사용되어 보안성을 강화합니다.
• 이 방식은 salt와 유사하지만, salt는 입력값에 추가되는 공개값이고, SipHash는 내부에서 사용하는 비밀 키 기반이라는 점에서 다릅니다.

 

🔸 해시테이블의 해시 충돌(Hash Collision)

• 해시테이블에서 서로 다른 key들이 같은 해시 인덱스를 갖게 되는 현상입니다. 
  • 데이터가 많아질수록 자연스럽게 발생합니다.
• 위에서 언급했듯이 기본적으로 Redis에서 사용하는 해시테이블의 시간복잡도는 O(1)입니다.
• 그러나 해시테이블 크기(size)에 비해 실제 저장된 항목 수(used)가 더 많아지면 특정 버킷에 n 개의 데이터가 체이닝 형태로 저장되게 됩니다.
• 그리고 이 개수에 따라 시간복잡도가 O(1)에서 O(n)이 될 수 있습니다.
  • 해시 충돌을 통해 한 버킷에 여러 개의 서로 다른 데이터가 포함되기 때문입니다.
• Redis에서는 이러한 해시 충돌은 체이닝(chaining)과 리해싱(Rehashing) 방식으로 해결합니다.

🔹 체이닝(Chaining)

[버킷]
[000] → Apple → Orange
[001] → Melon
[010] → (비어 있음)
[011] → Banana → Potato → Kiwi
[100] → (비어 있음)
[101] → (비어 있음)
[110] → (비어 있음)
[111] → (비어 있음)

• 서로 다른 Key들에서 같은 해시값이 나와 인덱스가 겹치게 되면 연결리스트로 이어서 저장합니다.
  • 따라서 이때는 실제 탐색이 O(n)이 걸릴 수가 있습니다. 
  • 이때 n은 해당 인덱스에 연결된 엔트리 수이며, 이 경우 평균 시간복잡도는 O(1)이지만, 충돌이 많이 발생한 버킷에서는 최악의 경우 O(n)이 됩니다.
• 그래도 평균적인 시간복잡도는 O(1)입니다. 해시 함수가 고르게 분포되어 있다면 대부분의 key는 충돌 없이 독립된 슬롯에 저장되기 때문입니다.

 

🔹 리해싱(Rehashing)

• 위에서 보았듯이 데이터가 너무 많아져 해시테이블의 슬롯이 부족해지게 되면 충돌이 증가해 연결리스트의 개수가 증가(Chaining)하고, 이는 점점 성능에 영향을 미치게 됩니다.
• Redis는 점진적 리해싱(Incremental Rehashing) 방법을 통해 이를 해결합니다.

 

점진적 리해싱 예시

/*실제와 다소 다름. 이해하기 위한 예시일 뿐입니다.*/

/*기존 해시 테이블 (크기 = 4, 2비트 인덱스 사용)*/
ht[0] 
[00] → Apple → Orange
[01] → Melon
[10] → Mango
[11] → Banana → Potato → Kiwi

/*새로운 테이블 생성, 크기는 2배로 확장 (크기 = 8, 3비트 인덱스 사용)*/
ht[1] 
[000] (비어 있음)
...
[111] (비어 있음)

• 기본 해시 테이블(ht[0])의 연결리스트 수가 늘어나 성능이 저하됩니다.
• 이때 새로운 테이블(ht[1])을 생성하고 인덱스 크기를 2배로 확장합니다.

 

/*실제와 다소 다름. 이해하기 위한 예시일 뿐입니다.*/

/*기존 해시 테이블*/
ht[0] 
[00] (Apple, Orange 이동으로 비워짐)
[01] → Melon
[10] → Mango
[11] → Banana → Potato → Kiwi

/* 새로 생긴 해시 테이블*/
/*첫번째 버킷만 이동*/
ht[1] 
[000] → Apple(이동)
...
[010] → Orange(이동)
...
[111] (비어 있음)

/*... 위와 같은 방식으로 하나씩 이동*/

/*점진적 리해싱 최종*/
ht[0] -> 삭제
[00] (비어 있음)
[01] (비어 있음)
[10] (비어 있음)
[11] (비어 있음)

ht[1] -> ht[0]으로 변경
[000] → Apple
[001] → Melon
[010] → Orange
[011] → Banana
[100] → Potato
[101] → Kiwi
[110] → Mango
[111] (비어 있음)

• 위와 같이 한 명령마다 기존 해시 테이블에서 새로운 해시 테이블로 내부 값이 이동하게 됩니다.
• 점진적으로 새로운 버킷으로 이전함으로써 전체 성능 저하 없이 해시 확장이 가능합니다.
• 모든 데이터가 옮겨지면 기존 해시테이블은 삭제되고 새로운 해시테이블로 완전 전환됩니다.
• 테이블 간 데이터 이동 중인 상황에서 데이터를 조회할 때는 양쪽 모두 조회하도록 동작합니다.

 

🔸 Redis의 Skiplist

• Sorted Set(ZSET)을 구성하는 핵심 내부 자료구조입니다.
  • ZSET은 score를 기준으로 정렬된 데이터를 저장해야 하기 때문에 O(log n) 수준의 빠른 검색과 삽입 성능을 제공하는 자료구조가 필요합니다.
  • 이를 위해 Redis는 skiplist와 hash table을 함께 사용합니다.
• skiplist는 연결 리스트 기반의 정렬된 자료구조로 균형 잡힌 다단계 구조를 통해 빠른 탐색이 가능합니다.
• 쉽게 말해 일종의 계층형 연결 리스트라고 볼 수 있습니다.
• 하위 레벨일수록 노드 수가 증가합니다.
  • 상위 레벨은 하위 레벨보다 적은 노드 수를 가지고 있어 노드 간의 점프를 하며 이동할 수 있습니다.
  • 상위 레벨은 하위 레벨의 급행열차와 같은 역할을 합니다.
• 이러한 레벨 구조는 균형 트리처럼 강제적인 게 아니라 랜덤으로 배정됩니다.
  • 레벨 1은 반드시 존재하며 그 외 레벨은 랜덤으로 정해집니다.
  • 보통 레벨 1 ~ 32 사이 (Redis에서 maxLevel = 32)
  • 레벨이 높을수록 등장 확률은 기하급수적으로 낮아집니다.
• 덕분에 구조가 자연스럽게 균형을 이루고 탐색/삽입/삭제 모두 평균 O(log n) 시간복잡도를 가집니다.
• 탐색 시에는 상위 레벨부터 시작해 아래로 빠르게 내려가면서 원하는 값을 찾습니다.
  • 상위 레벨에 원하는 값이 없으면 하위레벨로 한 단계 내려가 찾는 방식입니다.
• ZADD, ZRANK, ZRANGE 등의 명령은 내부적으로 skiplist를 통해 효율적으로 처리됩니다.

 

🔹 log n

• log n이라고 하면 로그는 어떤 수를 몇 번 곱해야 n이 되는지를 나타내는 수학적 개념입니다.
• 컴퓨터 공학 알고리즘에서 등장하는 O(log n)의 시간 복잡도는 이진탐색처럼 매 단계마다 탐색 범위를 절반씩 줄이는 구조에서 나타납니다.
  • 예를 들어 이진 탐색은 매번 전체 범위인 n을 2로 나누는 과정을 거치기 때문에 최악의 경우에도 2^x = n을 만족하는 x번의 비교만 하면 됩니다.
• 즉, 실행 횟수는 log₂(n) 번이며, 이를 O(log n)으로 표현합니다.

 

🔹 예제

score 기준 정렬

[3, 7, 9, 12, 19, 21, 25, 30]

 

Skiplist 예시

# 레벨 개수는 랜덤
Level 3:          ──────────▶ 9 ───────────────────────────────▶ 25
                   │                                           │
Level 2:     ─────▶ 7 ─────────────▶ 12 ──────────────────────▶ 25
              │     │               │                          │
Level 1:  3 ─▶ 7 ─▶ 9 ─▶ 12 ─▶ 19 ─▶ 21 ──────────────────────▶ 25 ─▶ 30

 

🕵🏻‍♂️ 검색 예시) 값 21을 찾을 때 경로

1. Level 3
   → 9 → 25 (21보다 작거나 같은 노드 없음) → 아래 레벨로 ↓
2. Level 2
   → 7 → 12 → 25 (21보다 작거나 같은 노드 없음) → 아래로 ↓
3. Level 1
   → 12 → 19 → 21 ✅ 찾음!

→ 총 6번의 포인터 이동으로 탐색 성공
→ 데이터가 8개인데도 log₂(8) = 3~4단계만 거쳐서 도달

 

🤔 의문점, 레밸 내에서 옆으로 얼마나 이동하는지도 비용이 드는 것 아닌가?

• 한 레벨 내에서도 수평 이동은 탐색 비용에 포함되고, 그래서 실제 포인터 이동 횟수는 log n보다 클 수 있습니다.
• 하지만 Skiplist는 확률적으로 잘 설계돼 있어서 전체 평균 포인터 이동 횟수 O(log n)으로 유지됩니다.

 

 

 

참고

2025 오픈소스 컨트리뷰션 아카데미 Git & Redis 수업 자료

ChatGPT