Redis 리드·아키텍트 코딩·알고리즘 면접
새 면접Q. Redis를 이용한 분산 락 구현 시 Redlock 알고리즘의 핵심 동작 원리와 안전성을 보장하기 위한 알고리즘적 요구사항을 설명하고, 시간 복잡도와 네트워크 복잡도를 분석해주세요.
과반수 노드에서의 락 획득과 타임스탬프 기반 유효성 검증이 핵심입니다.
Redlock은 N개의 독립적인 Redis 인스턴스(보통 5개)에서 과반수 이상의 락을 획득해야 성공으로 간주하는 알고리즘입니다. 각 노드에 SET NX PX 명령으로 락을 시도하며, 전체 소요 시간이 TTL보다 충분히 짧아야 유효성을 인정합니다. 시간 복잡도는 O(N)이며 N은 Redis 노드 수로, 각 노드에 순차적으로 락을 요청합니다. 네트워크 복잡도는 최악의 경우 2N번의 왕복(락 획득 N번, 해제 N번)이 발생합니다. 클록 드리프트를 고려하여 유효 시간을 계산할 때 안전 마진을 두어야 하며, 락 획득 실패 시 획득한 모든 락을 즉시 해제하는 롤백 로직이 필수입니다. 재시도 시에는 랜덤 지연을 적용하여 thundering herd 문제를 방지해야 합니다.
- • 과반수(quorum) 기반 락 획득으로 안전성 보장
- • 시간 복잡도 O(N), 네트워크 왕복 2N회
- • 클록 드리프트 고려 및 유효 시간 검증 필수
- • 실패 시 롤백과 재시도 백오프 전략 구현
MSA 환경에서 여러 서비스 인스턴스가 동시에 배치 작업을 수행할 때 중복 실행을 방지하는 분산 락 시스템 설계
Redlock의 안전성에 대한 Martin Kleppmann의 비판과 fencing token 방식의 차이점을 설명해주세요.
Q. Redis HyperLogLog의 카디널리티 추정 알고리즘 원리를 설명하고, 공간 복잡도와 시간 복잡도, 그리고 오차율을 수학적으로 분석해주세요. 대용량 UV 카운팅 시나리오에서 정확한 Set 대비 트레이드오프를 설명하세요.
해시 함수의 leading zero 패턴을 이용한 확률적 카운팅이 핵심입니다.
HyperLogLog는 입력값을 해시한 후 바이너리 표현에서 leading zero의 최대 개수를 추적하여 카디널리티를 추정합니다. m개의 버킷(Redis는 16384개)을 사용하며, 각 버킷은 6비트로 최대 leading zero 수를 저장합니다. 공간 복잡도는 O(m) = 12KB로 고정되며, 입력 크기와 무관합니다. PFADD, PFCOUNT의 시간 복잡도는 O(1)이고, PFMERGE는 O(N)입니다(N은 병합할 HLL 개수). 표준 오차는 0.81%로, 1억 개의 고유값을 12KB로 추정할 수 있습니다. 정확한 Set 방식은 O(n) 메모리가 필요하지만 100% 정확하고, HyperLogLog는 O(1) 고정 메모리로 99.19% 정확도를 제공하는 트레이드오프입니다. 실시간 대용량 UV 카운팅에서는 메모리 효율성이 정확도보다 중요하므로 HyperLogLog가 적합합니다.
- • 확률적 카운팅으로 공간 복잡도 O(1) 고정(12KB)
- • 시간 복잡도 PFADD/PFCOUNT O(1), 표준 오차 0.81%
- • Set 방식 대비 메모리 효율 vs 정확도 트레이드오프
- • 대용량 UV 추정에서 실용적 선택
대규모 광고 플랫폼에서 수억 개의 광고 노출에 대한 실시간 순 사용자 수(unique visitor) 집계
1억 DAU 서비스에서 시간대별 UV를 추적할 때 HyperLogLog를 어떻게 파티셔닝하고 병합할 것인지 설계해주세요.
Q. Redis Sorted Set의 내부 자료구조인 Skip List와 Hash Table의 조합 방식을 설명하고, ZADD, ZRANGE, ZRANK 연산의 시간 복잡도를 분석해주세요. 대용량 실시간 리더보드 구현 시 고려해야 할 알고리즘적 최적화 방안도 제시하세요.
Skip List의 계층적 구조가 범위 검색과 순위 계산을 효율적으로 만듭니다.
Sorted Set은 Skip List와 Hash Table을 동시에 유지합니다. Skip List는 score 기반 정렬된 순서를 O(log N) 탐색으로 제공하고, Hash Table은 member로 score를 O(1)에 조회합니다. ZADD는 평균 O(log N)으로 Skip List 삽입 위치를 찾고 Hash Table에도 추가합니다. ZRANGE는 O(log N + M)으로 시작 위치를 찾고 M개 요소를 순회하며, ZRANK는 O(log N)으로 Skip List를 탐색하여 순위를 계산합니다. 대용량 리더보드에서는 전체 랭킹 대신 상위 N개만 유지하거나, 시간 윈도우별로 파티셔닝하여 각각의 크기를 제한해야 합니다. ZREMRANGEBYRANK로 주기적으로 하위 순위를 제거하고, 사용자별 정확한 순위가 필요 없다면 근사 순위를 제공하는 방식으로 최적화할 수 있습니다. 읽기가 많은 경우 ZREVRANGE 결과를 별도 캐싱하는 전략도 유효합니다.
- • Skip List + Hash Table 이중 구조로 O(log N) 정렬 탐색과 O(1) 조회 제공
- • ZADD O(log N), ZRANGE O(log N + M), ZRANK O(log N)
- • 대용량 리더보드는 파티셔닝과 상위 N개 제한으로 최적화
- • 주기적 정리와 근사 순위 전략 적용
게임 서비스에서 1억 명의 사용자 점수를 실시간으로 정렬하고 특정 사용자의 순위를 조회하는 글로벌 리더보드 시스템
Skip List 대신 B-Tree나 Red-Black Tree를 사용하지 않는 이유와 Redis의 설계 철학을 설명해주세요.
Q. Redis Geospatial 인덱스의 내부 구현인 Geohash 알고리즘의 동작 원리를 설명하고, GEORADIUS 연산의 시간 복잡도와 정확도를 분석해주세요. 대규모 위치 기반 검색에서 성능 최적화 방법도 제시하세요.
Geohash는 2차원 좌표를 1차원 문자열로 변환하여 Sorted Set에 저장합니다.
Geohash는 위도/경도를 번갈아가며 비트로 인코딩하여 52비트 정수로 변환하고, 이를 Sorted Set의 score로 저장합니다. Z-order curve(공간 채움 곡선)를 이용해 2차원 공간을 1차원으로 매핑하므로, 인접한 위치는 비슷한 해시값을 가집니다. GEORADIUS는 중심점의 Geohash를 계산하고 반경에 해당하는 Geohash 범위를 ZRANGE로 조회한 후, 각 결과의 정확한 거리를 계산하여 필터링합니다. 시간 복잡도는 O(N + log M)으로 N은 반환 결과 수, M은 전체 요소 수입니다. Geohash 경계에서 false negative가 발생할 수 있어 약간 넓은 범위를 조회 후 필터링합니다. 대규모 검색 최적화를 위해서는 도시/지역별로 키를 분리하거나, 검색 반경에 따라 다른 Geohash 정밀도를 사용하고, 결과 수 제한(COUNT 옵션)을 적용해야 합니다.
- • Geohash로 2D 좌표를 1D 정수로 변환하여 Sorted Set 활용
- • GEORADIUS 시간 복잡도 O(N + log M), 경계 오차 존재
- • Z-order curve 기반 공간 인접성 보존
- • 지역별 파티셔닝과 결과 수 제한으로 최적화
배달 앱에서 사용자 위치 기준 반경 3km 내의 수만 개 음식점을 실시간으로 검색하는 시스템
Geohash 대신 R-Tree나 Quadtree를 사용할 때의 장단점과 Redis에서 Geohash를 선택한 이유를 설명해주세요.
Q. Redis Stream의 Consumer Group 기반 메시지 처리 알고리즘을 설명하고, XREADGROUP의 동작 원리와 시간 복잡도를 분석해주세요. Pending Entries List(PEL) 관리 전략과 메시지 재처리 알고리즘도 설계하세요.
Consumer Group은 각 소비자의 처리 상태를 추적하여 정확히 한 번(at-least-once) 처리를 보장합니다.
Consumer Group은 각 소비자에게 메시지를 분배하고, 처리 완료 전까지 PEL에 보관하여 장애 시 재처리를 가능하게 합니다. XREADGROUP은 그룹의 last_delivered_id 이후 메시지를 조회하며, 시간 복잡도는 O(N)으로 N은 반환할 메시지 수입니다. 각 메시지는 특정 소비자에게 할당되고 PEL에 추가되며, XACK로 확인 응답 시 PEL에서 제거됩니다. PEL 관리를 위해 XPENDING으로 미처리 메시지를 모니터링하고, idle time이 임계값을 초과하면 XCLAIM으로 다른 소비자에게 재할당합니다. 재처리 알고리즘은 exponential backoff를 적용하여 재시도 간격을 늘리고, 최대 재시도 횟수 초과 시 Dead Letter Queue로 이동시킵니다. 메시지 ID는 타임스탬프 기반이므로 시간순 처리가 보장되며, MAXLEN으로 스트림 크기를 제한하여 메모리를 관리합니다.
- • Consumer Group과 PEL로 at-least-once 처리 보장
- • XREADGROUP O(N), XPENDING으로 미처리 메시지 추적
- • XCLAIM 기반 재할당과 exponential backoff 재시도
- • 타임스탬프 기반 메시지 ID로 순서 보장
실시간 주문 처리 시스템에서 여러 워커가 주문 이벤트를 분산 처리하고, 실패한 주문은 자동으로 재처리하는 파이프라인
Kafka와 비교했을 때 Redis Stream의 처리량과 내구성 측면에서의 트레이드오프를 분석해주세요.
Q. Redis Bitmap을 이용한 대용량 사용자 활동 추적 시스템을 설계할 때, BITCOUNT와 BITOP 연산의 시간 복잡도를 분석하고, 메모리 효율성을 극대화하는 알고리즘적 접근을 설명해주세요.
Bitmap은 각 비트를 boolean 값으로 사용하여 공간 효율적인 집합 연산을 제공합니다.
Bitmap은 문자열 타입에 비트 단위 연산을 제공하며, 각 사용자 ID를 비트 오프셋으로 매핑하여 O(1) 공간으로 존재 여부를 표현합니다. BITCOUNT는 O(N)으로 N은 바이트 수이며, Redis는 population counting 알고리즘을 사용해 최적화합니다. BITOP(AND, OR, XOR)는 O(N)으로 여러 Bitmap을 병합하여 교집합/합집합을 계산합니다. 1억 사용자의 일일 활동을 추적하면 12.5MB만 필요하므로, 365일 데이터도 4.5GB로 저장 가능합니다. 메모리 최적화를 위해 sparse bitmap은 Hash로 대체하고(비트가 적게 설정된 경우), dense bitmap은 그대로 사용하는 하이브리드 전략을 적용합니다. 날짜별 키 파티셔닝과 TTL 설정으로 오래된 데이터를 자동 삭제하며, BITPOS로 첫 번째 활성 사용자를 O(N)에 찾을 수 있습니다.
- • 비트 단위 매핑으로 극도의 공간 효율성(1억 사용자 = 12.5MB)
- • BITCOUNT O(N), BITOP O(N)으로 집합 연산
- • Sparse는 Hash, Dense는 Bitmap 하이브리드 전략
- • 날짜별 파티셔닝과 TTL로 메모리 관리
1억 사용자 서비스에서 일일 활성 사용자(DAU), 주간 활성 사용자(WAU) 등의 지표를 실시간으로 계산하는 분석 시스템
MAU(월간 활성 사용자) 계산 시 30일치 Bitmap을 효율적으로 병합하는 알고리즘을 설계하고, 메모리와 CPU 트레이드오프를 분석해주세요.
Q. Redis Bloom Filter의 확률적 자료구조 원리를 설명하고, false positive rate를 제어하기 위한 해시 함수 개수(k)와 비트 배열 크기(m)의 최적 값을 계산하는 알고리즘을 유도하세요. 대규모 중복 검사 시나리오에서 Set 대비 공간/시간 복잡도 트레이드오프를 분석하세요.
여러 해시 함수로 비트를 설정하고, 모든 비트가 1이면 존재 가능성이 있다고 판단합니다.
Bloom Filter는 k개의 해시 함수로 입력을 m비트 배열의 k개 위치에 매핑하고, 조회 시 모든 비트가 1이면 존재 가능으로 판단합니다. False positive는 발생하지만 false negative는 없습니다. 최적 해시 함수 개수는 k = (m/n) * ln(2)이며, n은 예상 요소 수입니다. False positive rate p = (1 - e^(-kn/m))^k로, 목표 p와 n이 주어지면 m = -n*ln(p) / (ln(2))^2로 계산합니다. 공간 복잡도는 O(m)으로 Set의 O(n*size(element))보다 훨씬 작으며, 시간 복잡도는 삽입/조회 모두 O(k)로 Set의 O(1) 해시 조회와 유사하지만 k는 상수입니다. 1억 개 요소를 1% FPR로 저장 시 약 120MB만 필요하며, Set은 수GB가 필요합니다. 중복 URL 필터링, 캐시 존재 여부 사전 확인 등에서 메모리 절약이 정확도보다 중요할 때 적합합니다.
- • k개 해시 함수로 false positive만 허용하는 확률적 자료구조
- • 최적 k = (m/n)*ln(2), m = -n*ln(p)/(ln(2))^2
- • 공간 복잡도 O(m)으로 Set 대비 90% 이상 절약
- • 시간 복잡도 O(k) 삽입/조회, 정확도 vs 메모리 트레이드오프
크롤러 시스템에서 수억 개의 URL 중복 방문을 방지하기 위해 이미 크롤링한 URL을 빠르게 확인하는 필터
Counting Bloom Filter와 일반 Bloom Filter의 차이점을 설명하고, 삭제 연산이 필요한 시나리오에서의 알고리즘 설계를 제시하세요.
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!