Codyssey B5-1: 정보를 엄청 빠르게 찾아주는 작은 저장소 만들기

프로젝트 개요

Redis의 핵심 기능(String 키-값 저장, LRU 기반 메모리 관리, TTL 만료)을 직접 구현한 CLI 기반 Mini Redis다. dict/set/collections 없이 해시맵·이중 연결 리스트·최소 힙 같은 기본 자료구조부터 밑바닥부터 만들고, 이 셋을 조합해 O(1) LRU 추적과 힙 기반 TTL 만료 관리를 구현하는 것이 이 과제의 핵심이다.

미션 원문의 보너스 5개(동적 배열, 스택/큐/덱 문서화, 이진 트리, 이진 탐색 트리, Pub/Sub)도 함께 구현했다.

---

개발 환경

항목	값
OS	macOS 26.6.2
Python	3.14.7
에디터	VSCode (Ruff 확장 사용)

---

실행 방법

python main.py

mini-redis> 프롬프트에서 명령어를 입력하면 즉시 실행 결과를 확인할 수 있다. EXIT 또는 QUIT(대소문자 무관)으로 종료.

---

파일 구조

.
├── main.py                # 진입점 - REPL 루프 (입력 → tokenize → execute → 출력)
├── commands.py            # 명령어 파싱/디스패치, Redis 스타일 출력 포맷팅
├── store.py               # String 키-값 저장소 (SET/GET/DEL/TTL/메모리 관리)
├── pub_sub.py             # [보너스] 채널 기반 Pub/Sub
│
├── hashmap.py             # 체이닝 방식 해시맵 (직접 구현)
├── doubly_linked_list.py  # 센티넬 기반 이중 연결 리스트 (직접 구현)
├── min_heap.py            # 배열 기반 최소 힙 (직접 구현)
├── dynamic_array.py       # [보너스] 2배 확장 동적 배열
├── binary_tree.py         # [보너스] 완전 이진 트리 (전위/중위/후위/레벨 순회)
├── binary_search_tree.py  # [보너스] 이진 탐색 트리
├── STACK_QUEUE_DEQUE.md   # [보너스] 스택/큐/덱 개념 및 언어별 구현 비교 문서
│
├── ruff.toml
├── .gitignore
└── README.md

---

기능 목록

String 타입 명령어

명령어	설명	출력 예시
SET key value	값 저장. 기존 키를 덮어쓰면 TTL은 초기화(삭제)	OK
GET key	값 조회 (없거나 만료 시 nil, 성공 시에만 LRU 갱신)	"value" / (nil)
DEL key	삭제. 데이터/LRU/TTL 구조에서 함께 제거	(integer) 1
EXISTS key	존재 여부 확인	(integer) 1
DBSIZE	전체 키 개수	(integer) N
KEYS	전체 키 목록 (순서 미보장)	1. "user:2"

메모리 관리

명령어	설명
CONFIG SET maxmemory bytes	최대 메모리 제한(바이트) 설정. 0은 무제한
INFO memory	used_memory/maxmemory/evicted_keys 3줄 출력

maxmemory 초과 시 used_memory ≤ maxmemory가 될 때까지 LRU(가장 오래 안 쓰인 키)부터 제거하고 evicted_keys에 누적한다. 단일 엔트리(키+값) 자체가 maxmemory를 초과하면 저장하지 않고 OOM 에러를 낸다. used_memory는 Σ(len(utf8(key)) + len(utf8(value)))로 계산(자료구조 오버헤드 제외).

TTL 관리

명령어	설명	출력 예시
EXPIRE key seconds	만료 시간 설정. seconds ≤ 0이면 즉시 삭제	(integer) 1
TTL key	남은 만료 시간 (없는 키: -2, 무제한: -1)	(integer) N

에러 처리

(error) ERR unknown command 'HELLO'
(error) ERR wrong number of arguments for 'GET' command
(error) ERR value is not an integer or out of range
(error) OOM command not allowed when used_memory > 'maxmemory'

값에 공백이 있으면 큰따옴표로 감싸서 입력한다 (SET user:1 "Alice Kim").

보너스

• 동적 배열 (dynamic_array.py) — 고정 길이 리스트를 버퍼로 두고 꽉 차면 2배 확장, append가 상환(amortized) O(1). get/set/remove는 파이썬 list와 동일하게 범위를 벗어나면 IndexError.
• 스택/큐/덱 (STACK_QUEUE_DEQUE.md) — 개념, LIFO/FIFO/양방향 규칙과 언어별(Python/Java/C++) 표준 구현체·시간복잡도 비교.
• 이진 트리 (binary_tree.py) — 레벨 순서로 채워 넣는 완전 이진 트리. 전위/중위/후위/레벨 순회 지원.
• 이진 탐색 트리 (binary_search_tree.py) — 삽입/탐색/삭제(자식 2개 노드는 오른쪽 서브트리 최솟값으로 대체)와 중위 순회 기반 정렬 결과 조회.
• Pub/Sub (pub_sub.py) — SUBSCRIBE/PUBLISH 명령어. 채널명과 메시지 큐(DoublyLinkedList)를 매핑하는 HashMap 기반 채널 레지스트리로 구현. 네트워킹·멀티스레딩이 없는 단일 세션 동기 REPL이라 서로 다른 클라이언트 간 진짜 비동기 브로드캐스트는 구조적으로 불가능하며, 대신 미션이 실제로 의도하는 "채널 개념 + 큐 재활용" 연습에 초점을 맞췄다 — PUBLISH는 메시지를 큐에 적재한 뒤 같은 호출 안에서 즉시 FIFO로 꺼내 전달 결과를 반환한다.

---

출력 예시

세션 1 — 기본 String 명령어

mini-redis> KEYS
(empty array)

mini-redis> SET user:1 "Alice"
OK

mini-redis> GET user:1
"Alice"

mini-redis> EXISTS user:1
(integer) 1

mini-redis> DBSIZE
(integer) 1

mini-redis> SET user:2 "Bob"
OK

mini-redis> KEYS
1. "user:1"
2. "user:2"

mini-redis> DEL user:1
(integer) 1

mini-redis> GET user:1
(nil)

mini-redis> DBSIZE
(integer) 1

세션 2 — 메모리 관리 + LRU 자동 제거

mini-redis> CONFIG SET maxmemory 15
OK

mini-redis> SET a "12345"
OK

mini-redis> SET b "12345"
OK

mini-redis> GET a
"12345"

mini-redis> SET c "12345"
OK

mini-redis> INFO memory
used_memory:12
maxmemory:15
evicted_keys:1

mini-redis> KEYS
1. "a"
2. "c"

mini-redis> CONFIG SET maxmemory 5
OK

mini-redis> SET toolong "abcdefgh"
(error) OOM command not allowed when used_memory > 'maxmemory'

세션 3 — TTL 관리

mini-redis> EXPIRE nope 10
(integer) 0

mini-redis> SET session:1 "token-abc"
OK

mini-redis> EXPIRE session:1 3
(integer) 1

mini-redis> TTL session:1
(integer) 0

# (3초 경과 후)

mini-redis> GET session:1
(nil)

mini-redis> TTL session:1
(integer) -2

세션 4 — Pub/Sub

mini-redis> SUBSCRIBE alerts
OK

mini-redis> PUBLISH alerts "server down"
(integer) 1
[alerts] server down

mini-redis> PUBLISH nobody "no one listening"
(integer) 0

세션 5 — 에러 처리

mini-redis> GET
(error) ERR wrong number of arguments for 'GET' command

mini-redis> HELLO
(error) ERR unknown command 'HELLO'

mini-redis> CONFIG SET maxmemory abc
(error) ERR value is not an integer or out of range

---