• 2개의 프로젝트로 구성되어 있습니다.

Project Summary

Project 1. Zariyo

“대기열 중심 콘서트 예약 시스템 개인프로젝트”

전체 시스템 플로우

대기열 시스템 아키텍처

• Dual Redis 분리 이유
  • 대기열 관리(List 위주의 Burst Write)와 토큰 검증(Set/Get 위주)은 워크로드 특성이 다르기 때문에 장애 및 지연을 격리하기 위해 Redis 인스턴스를 분리
  • 분리를 통해 한쪽의 과부하가 다른 쪽의 성능에 영향을 주지 않도록 보장

대기열 핵심 아이디어

O(log N)을 O(1)로 만들 수 있을까?

많은 대기열 구현 방식에서 Redis ZSET(Sorted Set)을 사용합니다. ZSET은 시간복잡도는 O(log N)으로 구성되어 있고 내부 자료구조를 통해 정렬과 순번 조회를 쉽게 할 수 있도로 도와줍니다. 구현 복잡도와 O(log N)에 시간복잡도를 고려했을때 충분히 대기열로 문제 없을거라 판단해 ZSET으로 초기 구현은 했지만,

저는 여기서 의문이 생겼습니다. Redis의 가장 큰 강점은 빠른 속도입니다. 그렇다면 O(1)의 성능으로 대기열을 구현할 수는 없을까? 그래서 이 프로젝트에 ZSET이 아닌 LIST를 사용해 대기열을 구현하고 성능테스트를 통헤 비교를 진행했습니다.

Step 1. LIST 구조의 한계

• 문제

  저는 ZSET이 아닌 진입/퇴장/조회 연산을 O(1)로 구현하기 위해 LIST를 채택했습니다.

  연산	ZSET	LIST
  진입	ZADD - O(log N)	RPUSH - O(1)
  퇴장	ZPOPMIN - O(log N)	LPOP - O(1)
  순번 조회	ZRANK - O(log N)	LPOS - O(N)

  LIST의 RPUSH와 LPOP은 O(1)으로 대기열의 핵심인 넣고 빼는 행위는 매우 빠릅니다. 하지만 치명적인 문제가 있었습니다. 특정 사용자의 순번을 조회하려면 LPOS로 LIST 전체를 순회해야 합니다.

  실시간 순번조회가 많은 특성 상 조회가 빈번하기 때문에 이 부분에 다른 방법을 떠올려야 했습니다.

Step 2. 발상의 전환 - 순번을 LIST에서 찾지 않고 계산하기