Bitly-Dongwoo

1. 문서의 기본 정보 (Title and People)

제목: Url 리다이렉션을 빠르게 처리하기
작성자: 이동우
최종 업데이트 날짜: [2025-09-13]

2. 개요 (Overview)

대규모 URL 단축 서비스인 Bitly의 시스템 중 URL 단축, 리다이렉션을 간단하게 구현해보고 조회 성능을 개선하는 프로젝트 입니다.
세 단계에 걸쳐 시스템을 최적화하여, 리다이렉션 요청을 안정적으로 처리할 수 있는 아키텍처를 구축하는 것을 목표로 합니다.

3. 배경 및 문제 정의 (Context)

• 문제 설명: 현재 시스템은 모든 URL 데이터를 단일 데이터베이스에 저장하고 있으며, 리다이렉션 요청시 단축 코드를 찾는 과정에서 전체 테이블 스캔이 발생합니다. URL 수가 증가하면서 탐색 시간이 기하급수적으로 늘어나고 있습니다.
• 필요성: 리다이렉션 속도는 사용자 경험과 서비스 안정에 직결되는 핵심 지표입니다. 트래픽이 집중되는 피크 타임에서 발생하는 지연 시간은 사용자 이탈을 야기할 수 있으므로, 대규모 트래픽을 효율적으로 처리할 수 있어야 합니다.

4. 목표와 비목표 (Goals and Non-Goals)

목표 (Goals):

• 사용자 중심의 영향: 사용자가 단축 URL 클릭 시 1초 미만의 지연 시간으로 즉시 리다이렉션될 수 있도록 합니다.
• 성공 측정 지표(KPI):
  • 평균 리다이렉션 응답 시간을 200ms 미만으로 단축
  • 최대 트래픽 발생 시에도 99.9%의 요청 성공률 유지

비목표 (Non-Goals):

• URL 생성 기능의 성능 최적화는 포함되지 않습니다.
• 통계 분석 및 사용자 대시보드와 같은 부가 기능을 다루지 않습니다.

5. 마일스톤 및 일정 (Milestones)

• 1단계(기초 구현): DB 풀스캔 구현
• 2단계(Good Solution): DB 인덱싱
• 3단계(Great Solution): In-Memory(Redis) 도입

5.1. 성능 테스트 결과

각 개선 단계가 실제로 어느 정도의 성능 향상을 가져왔는지, 부하 테스트를 통해 검증했습니다. 모든 테스트의 상세 비교 결과는 아래 링크에서 확인할 수 있습니다.

• 1단계: DB 풀 스캔 vs. 인덱싱

  • O(N)의 복잡도를 가진 풀 스캔 방식과 O(log N)의 인덱싱 방식이 실제 어느 정도의 성능 차이를 보이는지 비교했습니다. 100만 건의 데이터 환경에서 인덱싱이 약 332배 빠른 p95 응답 속도를 기록하며 압도적인 성능을 보였습니다.
  • DB 인덱싱 vs. 풀 스캔 상세 비교 결과 보기

• 2단계: 캐시 정책(LRU vs. LFU) 비교

  • 인기 있는 URL이 반복적으로 요청되는 '핫스팟' 데이터 환경을 가정하여, LRU(Least Recently Used)와 LFU(Least Frequently Used) 캐시 정책의 효율을 비교했습니다. 정상 부하(5,000 TPS) 환경에서 LFU가 LRU보다 약 14배 빠른 p95 응답 속도를 보여주며, Skewed 워크로드에 더 적합함을 입증했습니다.
  • 캐시 정책(LRU vs. LFU) 상세 비교 결과 보기

6. 기존 솔루션 (Existing Solution)

• 현 시스템 설명: 현재 시스템은 MySQL과 같은 관계형 데이터베이스를 사용하여 모든 단축 URL과 원본 URL 정보를 저장합니다. 리다이렉션 요청이 들어오면, 애플리케이션 서버가 데이터베이스에 단축 코드를 쿼리하여 원본 URL을 찾습니다. 인덱스가 최적화되지 않아, 데이터베이스는 전체 테이블을 순차적으로 탐색하며 값을 찾습니다.
• 사용자 시나리오: 사용자가 단축 URL을 클릭하면, 서버는 데이터베이스 전체를 스캔하는 느린 쿼리를 실행하고, 이로 인해 사용자는 리다이렉트되기까지 상당한 시간을 기다려야 합니다.

7. 제안 솔루션 (Proposed Solution)

• Tier 1 (인메모리 캐시): Redis를 도입하여 데이터베이스 부하를 최소화하고, 대부분의 요청에 대해 200ms 미만의 응답 시간을 보장합니다.
• Tier 2 (관계형 데이터베이스): 최종적인 데이터의 영구 저장소입니다. short_code를 Primary Key로 지정하고 B-tree 인덱싱을 적용하여 캐시 미스 시에도 효율적인 탐색이 가능하도록 합니다.

8. 대안 솔루션 (Alternative Solutions)

• 대안 1: 기초 구현 (DB 인덱싱)

  • 설명: 단일 관계형 데이터베이스를 사용하되, short_code 컬럼에 인덱스를 적용하여 탐색 성능을 O(log n)으로 개선합니다.
  • 장단점:
    • 장점: 구현이 간단하고, 인덱스만으로도 상당한 성능 향상을 얻을 수 있습니다.
    • 단점: 디스크 기반 탐색이므로 메모리 접근보다 느리고, 피크 트래픽 발생 시 단일 DB 인스턴스가 병목 현상을 일으킬 수 있습니다.

• 대안 2: Great Solution (인메모리 캐시 도입)

  • 설명: 기초 구현에 Redis와 같은 인메모리 캐시를 추가하여 데이터베이스 부하를 줄입니다.
  • 장단점:
    • 장점: 캐시 히트율이 높을 경우 O(1)에 가까운 빠른 응답 속도를 제공합니다. DB 부하를 크게 감소시킵니다.
    • 단점: 캐시 미스 시에는 여전히 DB 접근이 필요하며, 사용자와 서버 간의 물리적 거리가 멀 경우 발생하는 지연 시간 문제는 해결하지 못합니다.

9. 테스트, 모니터링 및 알림 (Testability, Monitoring and Alerting)

• 테스트 계획:
  • 부하 테스트: JMeter를 사용하여 초당 5000 건 이상의 리다이렉션 요청을 시뮬레이션하고, 응답 시간과 성공률을 측정합니다.
• 모니터링 전략:
  • 지표: Redis 캐시 히트율, DB 쿼리 응답 시간, 서버 CPU 및 메모리 사용량, 에러율(5xx).
  • 도구: Prometheus와 Grafana를 활용하여 실시간 모니터링 대시보드를 구축합니다.

10. 미결 질문 (Open Questions)

• 미정 사항:
  • 컴퓨터 리소스
  • 엣지 캐싱 전략: 모든 URL을 캐싱할지, 아니면 인기 있는 URL만 선별적으로 캐싱할지에 대한 결정이 필요합니다.
  • 캐시 무효화: URL이 삭제되거나 변경될 경우, 캐시를 어떻게 무효화할지에 대한 구체적인 정책 수립이 필요합니다.
• 향후 작업:
  • URL 생성 기능의 성능 최적화.
  • 리다이렉션 통계 데이터 수집을 위한 데이터 파이프라인(Kafka) 구축.

12. 세부 범위 및 타임라인 (Detailed Scoping and Timeline)

• 0단계 - 초기 세팅 및 초기 구현(3일 이내)
• 1단계 - DB 인덱싱 (1주차 이내)
  • short_code 컬럼에 인덱스 생성 및 Primary Key로 지정: 1일
  • 부하 테스트 및 성능 측정: 2일
• 2단계 - 인메모리 캐시 도입 (2주차 이내)
  • Redis 인스턴스 설정 및 연동: 1일
  • 캐시 로직(Cache Aside) 구현 및 테스트: 2일