Mini Redis

redis-cli처럼 프롬프트에 명령을 치면 Redis와 같은 형식으로 답하는 인메모리 키-값 저장소. 서버와 클라이언트가 한 프로세스에 들어 있고, 명령어 10개와 LRU eviction · TTL 만료가 동작한다. 내부의 해시맵 · 이중 연결 리스트 · 최소 힙은 dict · set · collections 없이 직접 구현했다.

Redis란

Redis(REmote DIctionary Server)는 메모리에 사는 키-값 저장소다. 디스크가 아니라 RAM에 데이터를 두고, 클라이언트가 보낸 명령에 답한다.

왜 빠른가

빠른 이유로 "메모리에 있으니까"를 먼저 떠올리게 된다. 하지만, 메모리에 올려놓고도 키를 하나씩 훑으면 여전히 느리다. 이 문제를 자료구조를 통해 해결한다.

• 키를 찾는 일은 해시 테이블이 맡는다. 데이터가 백만 개여도 여는 칸은 하나다.
• 무엇을 버릴지는 이중 연결 리스트가 안다. 가장 오래 안 쓴 키가 늘 꼬리에 있다.
• 언제 만료할지는 힙이 답한다. 가장 임박한 만료가 늘 맨 앞에 놓인다.

실행

python3 -m mini_redis      # 종료: exit, quit, Ctrl-D, Ctrl-C

테스트

pip install -r requirements.txt
python3 -m pytest tests/ -v      # 171개

---

명령어

명령어	인자	반환	비고
SET	key value	OK	한도 초과 시 LRU eviction. 값 하나가 한도보다 크면 OOM
GET	key	"value"	없으면 (nil)
DEL	key	(integer) 1	없으면 0
EXISTS	key	(integer) 1	없으면 0
DBSIZE	—	(integer) n	만료된 키 제외
KEYS	—	1. "key" 목록	비었으면 (empty array)
EXPIRE	key seconds	(integer) 1	없으면 0, seconds <= 0이면 즉시 삭제
TTL	key	(integer) 남은 초	TTL 없음 -1, 키 없음 -2
CONFIG SET	maxmemory <bytes>	OK	0은 무제한
INFO	memory	used_memory / maxmemory / evicted_keys	섹션 생략 가능

설계

	구현	담당	핵심 성질
HashMap	체이닝 (버킷마다 독립 DLL)	key → Entry, 명령어 디스패치	평균 O(1) 조회
DoublyLinkedList	센티넬 head/tail	버킷 충돌 체인, LRU 순서	노드 참조만 있으면 삭제 O(1)
MinHeap	배열 기반 완전 이진 힙	TTL 만료 순서	최솟값 peek O(1)

---

LRU와 메모리

정책	기준	필요한 자료구조	갱신 비용
LRU (채택)	가장 오래 안 쓰인 것	HashMap + DLL	O(1)
LFU	가장 덜 쓰인 것	+ 빈도 카운터, 빈도별 버킷	O(1)이지만 구조가 두 배
Random	무작위	없음	O(1)
TTL 임박순	만료가 가까운 것	이미 있는 MinHeap 재사용	O(log n)

메모리

엔트리 크기는 len(key.encode("utf-8")) + len(value.encode("utf-8"))

⚠️ 이 값은 오버헤드를 제외한 순수 데이터 크기다. 실제로 한 엔트리를 저장하려면 그 밖에도 다음이 딸려온다.

오버헤드	정체
Entry 객체	value · expire_at · version · lru_node 4개 필드
버킷 체인 노드	[key, value] 리스트를 담는 Node
LRU 노드	key를 담는 Node (엔트리마다 노드가 총 2개)
버킷 테이블	로드 팩터 0.75 → 항상 25% 이상이 빈 칸
힙 레코드	TTL이 걸린 키마다, stale 항목까지 포함

---

TTL

힙 top 상태	처리
Entry가 없거나 version 불일치	stale — pop 후 버림 (시각과 무관)
version 일치, 아직 만료 전	뒤는 전부 미래이므로 중단
version 일치, 만료됨	pop 후 삭제

---

복잡도

연산	평균	최악	근거
GET SET DEL EXISTS	O(1)	O(n)	체인 길이에 비례. 해시가 나쁘면 최악에 근접
LRU 갱신 (move_to_front)	O(1)	O(1)	Entry.lru_node 역참조로 탐색 없음
eviction 대상 선정	O(1)	O(1)	DLL 꼬리 peek
EXPIRE (힙 push)	O(log n)	O(log n)	_up_heap 깊이 = 트리 높이
만료 정리 1건	O(log n)	O(log n)	힙 pop
_resize	—	O(n)	로드 팩터 0.75 초과 시. 상각 O(1)
KEYS	O(n)	O(n)	전 버킷 순회
DBSIZE	O(1)	O(1)	카운터

⚠️ 표에서 정리 비용은 제외함. 모든 public 명령이 진입할 때 _cleanup_expired()를 먼저 돌리므로, 그 호출에서 힙 레코드 k개를 처리했다면 +O(k log n)이 얹힌다. SET은 >evict한 키 m개에 +O(m)이, 확장이 일어난 회차에는 +O(n)이 더 붙는다.

---

해시 함수

1. 정보를 버리지 않는다.
2. 남은 정보를 균등하게 흩뿌린다

DJB2 다항식 해시 사용 (h = h*33 + byte)

	순서 반영	출력 분포	구현
바이트 합 sum(key) % bucket_size	✗ 애너그램 충돌	키 길이에 비례하는 좁은 구간	1줄
DJB2 (h*33 + b)% bucket_size (현재)	✓	32비트 전역	4줄
파이썬 내장 hash()	✓	무작위 시드 포함	직접 구현 과제라 제외

	put	get	사용된 버킷	최장 체인
바이트 합	1290 ms	1146 ms	130 / 65536	1990
DJB2	373 ms	64 ms	24236 / 65536	5