대기열 시스템 설계

[junha-ahn]

Description

예약 동시성 이슈와 갑자기 뛰어오르는 트래픽에 대응하기 위해 대기열 시스템을 설계하고자 합니다.

#33 를 참고해 대기열 시스템을 설계해주세요

To do

• (상시) 관련 자료 요약/기록

  • 자료에 대한 간단한 정리를 댓글에 첨부 (언급된 요약을 통해 follow-up 예정)
  • "link: 글에서는 a와 b의 형식을 사용하여 설계..."

• 1. 시스템 설계도, 흐름도 등 전반적인 Diagram 설계

  • 러프한 손 다이어그램부터 프로그램을 사용한 다이어그램

• 2. 단계별 설계

  • 가장 간단한 설계 => 문제상황 => 확장(해결방법) => 새로운 문제 상황 => 새로운 확장(해결방법) => ...

• 3. 구현 가능한 설계 깊이

  • 각 시스템간 API Request Flow 다이어그램 작성
  • 어떤 데이터를 주고 받아서, 대기열 기능을 가능하게 하는지, 실제 요청 전문(body) 설계
  • 프론트엔드 고려 (이벤트 상세 페이지 : 예약 버튼 => 날짜/시간선택 페이지 => 좌석 선택 페이지 => 최종 정보 입력 후 완료 버튼 => 예약 완료
    • 위 페이지 중 정확히 ‘어디에’ 대기열 기능이 존재하는지 (각 예약 페이지별로 대기열이 있어야 하는지, 처음 예약버튼 클릭시에만 존재하는지, 아니면 최종 ‘완료버튼‘에만 대기열이 존재할 것인지 )
    • 각 페이지마다 API 요청이 존재해야하는지, 마지막 완료버튼클릭시 한번만 Reservation 요청을 Backend로 전송할지 고려
    • 마지막 예약시 좌석 중복으로 인해 튕기는 등의 행위를 방지할려면 어떻게 할 수 있는지
    • 물런 위 작업에 많은 리소스가 소모된다면 구현하지 않을 수 있습니다.

Test Checklist

• 1. 서버가 현재 가진 처리량보다 수십배 높은 요청이 왔을때 문제 해결
• 2. 같은 이벤트에 대해 동시 예약을 했을때 동시성 문제 해결

[junha-ahn]

Reference

각 글에 출처에 대한 학습도 추천드립니다

Github

• 각 레포별로 어떻게 대기열을 구현했는지 '다이어그램'을 통한 정리 부탁드립니다.

대기열 및 MSA, k8s 기반으로 안정적인 콘서트 예매 사이트

• Java 실제 우리가 구현하고자 하는 목표를 완벽하게 구현
• 해당 프로젝트는 다이어그램 등으로 설명 부탁드립니다

기프티콘 선착순 이벤트 (N명 화면에 남은 대기열 표출)

Flab 대기열 프로젝트

System-design-questiosn

• Design Airline Check-in
• Design Synchronized Queue Consumers
• Design Flash Sale

https://github.com/donnemartin/system-design-primer#asynchronism

발표 자료 (영상)

[NDC] 실버바인 대기열 서버 설계 리뷰

• 질문 글

[우아한테크토크] 선착순 이벤트 서버 생존기! 47만 RPM에서 살아남다?!

키워드

• 선착순 이벤트 시스템

• 선착순 쿠폰 시스템

• queueing system

• multiple user queueing

• 이하 유튜브 중심 (위 한국어 키워드처럼, '대기열'에만 집중하는 키워드를 못찾은 상태. 좋은 키워드 있으면 공유 부탁드립니다)

  • concurrency system design
  • concurrency queue
  • concurrency control patterns
  • Online Gaming Server Queues system design
  • Ticketing Queue system design (Booking, Movie, Seat... etc)
  • flash sale queue system design

[ParkJeongseop]

https://minjun3021.notion.site/f057d86591a2435da995740d4fe17c04

[junha-ahn]

@ParkJeongseop 대기열 시스템 메인 이슈 내용을 참고해 더욱 구체화 부탁드립니다.

[junha-ahn]

고려사항

• 하나의 자원(=Event)에 대한 각 유저의 Wait time을 어떻게 개선할 수 있을까?
• 왜 대기열을 도입해야할까?
• 왜 API 서버로 Non-blocking을 논할까?
• 대기열 데이터는 어떻게 구성할까?
• 왜 Redis를 사용할까?
• 왜 Kafka를 사용할까?

참고

• 지마켓 대기열 시스템 파헤치기
• 프로모션을 대비한 대기열 시스템 구성하기
• [우아한테크토크] 선착순 이벤트 서버 생존기! 47만 RPM에서 살아남다?!
• 대기열 설계 - @minjun3021
• Redis를 활용한 트래픽 감당기

하나의 자원(=Event)에 대한 각 유저의 Total Wait time을 어떻게 개선할 수 있을까?

Average Lock Wait Time 등

동시성 문제(=갱신누락)에 대한 어떤 해결 방법이 있을까?

• Auto-commit : 자원이 몇개 더 생성될 수 있다.
• Raw Lock
• Queue or Pub/Sub (Redis)

현재 Raw Lock 사용에서 (크게) 개선할 수 없다.

• 낙관적 락이나 Auto Commit을 사용하면 Latency 개선 가능하지만 갱신 누락이 발생함으로 현재 상황에 맞는 해결법이 아니다. (좋아요 Count 같은 경우는 갱신누락이 발생해도 문제없겠지만, 티켓은 한개 더 발생하는 경우가 생겨서는 안된다)

물런 엄청나게 멋진 DB를 쓰면 어느 순간까지는 대응이 가능할것이다.

왜 대기열 시스템이 필요할까?

그렇다면 각 유저의 Total Wait Time을 개선할 수 없는데, 왜 대기열을 구현해야할까?

• "장애가 일어나지 않는 수준의 트래픽에 대해" 대기열을 사용한다면 POST /reservation 요청자체의 latency는 엄청난 개선이 발생한다
• 하지만 사용자가 대기열에 진입하는 순간부터를 생각해본다면 엄청난 성능 증가라고 말하기는 힘들 것이다 (평소 온라인 대기열을 생각해보자)

지연이 아니라, 정상 응답 조차 감당할 수 없을 정도로 트래픽이 늘어나면 어떠한 문제점이 발생할까?

• tomcat이 처리할 수 있는 요청량을 벗어나 request timeout
• hikari pool connection 고갈
• 즉 한마디로 이쯤되면 지연이 문제가 아니라, 장애가 발생한다.
• 이때 기준의 성능을 놓고 비교한다면 엄청난 개선이 발생한다 (동일한 트래픽에 대해 대기열은 장애가 발생하지 않을 가능성이 높으니)

2000 VU로 설정하여 요청이 증가하자, http_req_failed이 크게 증가함을 알 수 있다.

대기열 시스템은 트래픽의 안정적 순차 처리에 중점을 둔다.

• 먼저 한번에 모든 요청을 DB까지 직접 전달해 처리할 필요가 없었다. 가장 중요한건 선입선출로 Ticket 구매를 보장하는 것이다.
• API서버, DB 등에서 처리 가능한 트래픽만 FIFO 방식으로 전달함에 따라 서버, DB 등 성능을 안정적으로 유지 가능하며, 장애 전파(Circuit Breaker)를 막는다.
• Non-blocking API와 대기열 시스템을 통해 "대용량 트래픽"을 보다 안정적으로 처리한다.
• 자원의 Scale Out 시간보다 짧은 순간의 증가되는 트래픽을 제어 가능하다
• 또한 프론트 대기열 화면 구현을 통해 대기시간을 고지할 수 있다. (Lock은 사용자가 인터렉션했을때 반응이 존재하지 않지만, 대기열은 반응이 존재)
• 성능 저하 포인트를 막아 성능을 개선한다.

그렇다면 Peak 트래픽에 대기열 큐가 터지는건 어떻게 방어할 수 있을까? 오토스케일로는 감당 불가능할것으로 추측된다. 충분한 성능 준비, Pre-warming, 재해복구 등의 키워드가 필요할 것 같다.

왜 API 서버로 Non-blocking을 논할까?

사례

Gmarket: "높은 퍼포먼스를 가지고 있는 Redis를 충분히 활용하기 위해 API 서비스는 Non-Blocking 처리가 편리한 Node.js으로 작성"

배민 : "WebFlux + Netty 논블록킹 서버"

서블릿 컨테이너는 thread-per-request 모델을 따른다

즉 한 쓰레드당 한개의 요청 밖에 처리하지못한다. 그렇게 되면 I/O 작업이 일어날때 쓰레드는 실질적으로 하고있는것이 없지만 다른요청을 처리하지못한다. 그렇게 되면 자원이 부족한 서버(thread를 많이 만들 수 없는)에서 처리할 수 있는 동시 처리량은 매우 제한적일 것이다. 쓰레드를 많이 만든다하더라도 컨텍스트 스위칭 문제가 생겨서 성능에 많은 부담을 주게된다.

특히 이벤트루프기반 비동기 + 논블록킹 Node.js를 사용하면 트래픽을 효율적으로 처리 가능할 것이다

• Node.js API는 Redis에 빠르게 전달 후 특정 스레드를 할당해 응답을 기다리지 않는다. (= 응답을 기다리는데 특정 스레드나 자원을 할당하지 않는다) 따라서 높은 TPS를 유지할 수 있다.

대기열 데이터는 어떻게 구성할까?

https://github.com/wlwlsus/allback-with-k8s

대기열(Watting)과 참가열(Running)을 주로 구분하는것을 확인 가능하다 (또는 Status값을 통해...)

또 다른 구조는 어떤게 있을까?

또한 Batch를 통해 인입률을 제어한다 (대기열에서 동작열로 이동)

왜 레디스를 사용할까?

주로 Redis를 사용하는 이유는 Redis는 싱글 스레드로 돌아가기때문에 대기열 등록에대한 동시성 문제에서도 안전

왜 카프카를 사용할까?

출처

• https://upcurvewave.tistory.com/482

Redis의 문제점

• 장애에 대한 복구 정책을 수립해야 한다. (Kafka로 더 높은 가용성 달성)

[junha-ahn]

구현을 최대한 간단하게 해봅시다

• 최소 API Endpoint를 사용(2~5개)
• Redis 등 외부 Database 사용 X
• Nodejs In-memory Database 사용 (향후 테스트 중 문제점을 발견한다면 그때 개선)

[junha-ahn]

Redis 등 외부 DB 사용 X

라고는 했지만 일단 설계 당시에는 Redis 자료 구조를 사용했습니다 (굉장히 편리하네요)

고려사항

Gmarket의 경우 Traffic 정보를 Redis에 저장해서 특정 임계치 이상일때 대기열을 상품별로 구성합니다.
저희는 일단 Traffic에 따른 대기열 구성 여부를 고려하지 않고, 모든 이벤트에 대해 Redis에 Wating Ticket을 생성하도록 했습니다.

그리고 어떤 트래픽을 대기열을 통해 관리할것인지에 대한 문제는 /reservation Endpoint에 대해서만 대기열로 처리합니다.

또한 아래 두 가지 방식중 1번을 사용했습니다. (2번의 장점으로는 불필요한 추가 요청이 줄어들지만, 일단 구현 간단함을 위해)

1. 필요한 Endpoint에서 Spring API가 대기열 API 서버에 해당 ticket이 허용됬는지 직접 요청
2. 대기열 API 서버가 Proxy 역할을 한다 (wating-server/reservation으로 요청시 체크 후 spring-backend/reservation으로 Redirect)