대기열 서비스 구현(+Redis)

제가 콘서트 예약시스템에서 구현한 대기열에 대한 설계에 대해서 얘기해보겠습니다.

 

대기열이란?

대기열 시스템은 많은 사용자들이 동시에 접근하는 상황에서, 시스템의 안정성과 성능을 보장하기 위해 필수적인 요소입니다. 특히, 티켓 예매, 상품 구매, 서비스 예약 등과 같은 상황에서 대기열 시스템이 중요한 역할을 합니다.

만약 1000명의 유저가 동시에 좌석 예약을 위해 요청을 보낸다면, 정해진 선착순 100명만 예약이 가능하게 하고, 나머지는 대기열에서 대기하게 됩니다.

이렇게 하면 트레픽의 유량을 제어할 수 있기 때문에 서버의 부하를 줄일 수 있습니다. 대기열에 있는 유저는 일정 시간이 지나면 좌석 예약이 가능하게 되어 콘서트 좌석을 예약할 수 있습니다.

 

대기열 구현 방법

전통적으로? 대기열을 구현하는 방식에는 크게 2가지가 있습니다.

 

1. 은행 창구 방식 + DB를 이용한 대기열 구현

https://www.databyteindia.com/products/queue-token-management-system-banks

 

은행 창구 방식이란?

은행 창구에서 은행원이 고객을 1명씩 응대하듯이, 고객 1명의 업무가 종료되면 다음 고객이 기회를 갖게 되는 방식을 말한다.

 

장점

딱 우리가 설정한 사용자수만 예약이 가능한 상태가 됨. 그래서 서버의 부하를 일정 수준 이하로 유지할 수 있음

 

단점

대기열에 있는 사용자는 기약없이 기다려야 함. 예약이 완료될 때마다 대기열에 있는 사용자들이 1명씩 예약 가능한 상태로 변경, 그렇다보니 대기 중인 사용자는 언제까지 대기할지 모름. 그래서 대기열에서 이탈하는 고객이 발생할 가능성이 높다.

물론 대기 시간을 예측하여 대기번호와 함께 줄 수 있겠지만, 우리의 예측시간과 실제 대기시간과 다를 수도 있음

토큰 발급 및 대기 순서 반환 워크플로우는 다음과 같다.

 

 

위 워크플로우를 참고하여 아래와 같이 서비스를 구현하였다.

 

@Service
@RequiredArgsConstructor
public class WaitingQueueService {

    private final JwtUtils jwtUtils;
    private final WaitingQueueRepository waitingQueueRepository;
    private final WaitingQueueValidator waitingQueueValidator;

    /**
     * 토큰 발급을 요청하면 토큰 정보를 반환한다.
     *
     * @param userId userId 정보
     * @return WaitingQueueTokenResponse 토큰 정보를 반환한다.
     */
    public String issueToken(Long userId) {
        //토큰 발급
        return jwtUtils.createToken(userId);
    }

    /**
     * 대기열에 진입을 요청하면 대기열 정보를 반환한다.
     *
     * @param (user,token) user, token 정보
     * @return WaitingQueueResponse 대기열 정보를 반환한다.
     */
    @Transactional
    @DistributedLock(key = "'waitingQueueLock'")
    public WaitingQueue enterQueue(User user, String token) {
        // 현재 활성 유저 수 확인
        long activeTokenCnt = waitingQueueRepository.getActiveCnt();
        // 이미 유저의 활성화 된 토큰이 있다면 expired 시킴
        expiredIfExist(user.getUserId(), activeTokenCnt);
        // 활성화 시킬 수 있는 수 계산
        long availableActiveTokenCnt = WaitingQueue.calculateActiveCnt(activeTokenCnt);
        // 토큰 정보 저장
        WaitingQueue waitingToken = WaitingQueue.toDomain(availableActiveTokenCnt, user, token);

        Optional<WaitingQueue> savedWaitingToken = waitingQueueRepository.saveQueue(waitingToken);
        WaitingQueue waitingTokenInfo = waitingQueueValidator.checkSavedQueue(savedWaitingToken);

        // 만약 활성화 된 토큰이 아니라면 대기열 정보 생성
        if (waitingTokenInfo.getStatus() == WaitingQueue.WaitingQueueStatus.WAIT) {
            long waitingCnt = waitingQueueRepository.getWaitingCnt();
            waitingTokenInfo.addWaitingInfo(waitingCnt, Duration.ofMinutes(waitingCnt).toSeconds());
        }

        return waitingTokenInfo;
    }

    /**
     * 대기열 확인을 요청하면 대기열 정보를 반환한다.
     *
     * @param (userId,token) userId, token 정보
     * @return WaitingQueueResponse 대기열 정보를 반환한다.
     */
    @Transactional(readOnly = true)
    public WaitingQueue checkQueue(Long userId, String token) {

        // 1. 토큰 정보 확인
        Optional<WaitingQueue> tokenInfo = waitingQueueRepository.getToken(userId, token);

        if (tokenInfo.isEmpty()) {
            throw new CustomException(TOKEN_IS_NOT_FOUND,
                    "토큰 정보를 찾을 수 없습니다");
        }
        // 2. 토큰이 활성화 상태인지 확인
        tokenInfo.get().isActive();

        // 3. 활성화 되지 않은 토큰이면 대기 정보 반환
        long waitingCnt = waitingQueueRepository.getWaitingCnt(tokenInfo.get().getRequestTime());
        tokenInfo.get().addWaitingInfo(waitingCnt, Duration.ofMinutes(waitingCnt).toSeconds());

        return tokenInfo.get();
    }

 

여기서 중요한 점은 “일정 시간 주기로 사용자(토큰)을 활성화 상태로 전환” 해주어야 한다. 예약이 완료된 유저는 토큰이 만료될 것이고, 대기열에서 대기 순서가 제일 앞선 유저의 토큰 상태를 활성화 시켜줘야 한다. 이러한 기능을 수행하기 위해서 Spring Scheduler를 활용하여 구현해주자.

 

@Component
@RequiredArgsConstructor
@Slf4j
public class WaitingQueueScheduler { // 대기열 관련 스케줄러

    private final WaitingQueueFacade waitingQueueFacade;

    @Scheduled(fixedRate = 5000) // 매 5초마다 스케줄러 실행
    /**
     * token을 active 하는 스케줄러 5초마다 실행
     */
    @Scheduled(fixedRate = 5000)
    public void activeToken() {
        log.info("token을 active하는 스케줄러 실행");
        waitingQueueFacade.active();
    }

    /**
     * token을 expired 하는 스케줄러 5초마다 실행
     */
    @Scheduled(fixedRate = 5000)
    public void expireToken() {
        waitingQueueFacade.expire();
    }
}

 

각 토큰의 상태는 *WAIT*, *ACTIVE*, *EXPIRED* 가 있다. 스케줄러는 정해진 주기마다 토큰을 active 와 expired 시키는 아래의 메서드를 실행한다.

 

@Service
@RequiredArgsConstructor
public class WaitingQueueService {

...

    /**
   * 대기열에 있는 토큰을 순차적으로 active 시킨다.
   */
  @Transactional
  public void activeToken(Long activeTokenCnt) {
      // 1. 활성 유저 수 확인
      if (activeTokenCnt == null) activeTokenCnt = waitingQueueRepository.getActiveCnt();

      long availableActiveTokenCnt = WaitingQueue.calculateActiveCnt(activeTokenCnt);

      if (availableActiveTokenCnt == 0) throw new CustomException(TOKEN_ACTIVE_IS_NOT_EXIST, "활성화 시킬 토큰이 존재하지 않습니다.");
      // 2-1 대기열에 있는 유저 토큰 조회
      List<WaitingQueue> waitingTokens = waitingQueueRepository.getWaitingTokens();
      // 2-2 활성화 할 수 있는 만큼 활성화 진행
      waitingTokens.stream()
              .limit(availableActiveTokenCnt)
              .forEach(waitingQueue -> {
                  waitingQueue.active();
                  waitingQueueRepository.saveQueue(waitingQueue);
              });
    }

    /**
     * 시간이 만료된 active token 을 expired 시킨다.
     */
    @Transactional
    public void expireToken() {

        // active 된지 10분이 지난 토큰 조회
        List<WaitingQueue> tokens = waitingQueueRepository.getActiveOver10min();

        tokens.forEach(waitingQueue -> {
            waitingQueue.expireOver10min();
            waitingQueueRepository.saveQueue(waitingQueue);
        });
    }

 ...   
}

스케줄러를 이용하여 대기열을 관리하는 이유는?

 

사실 스케줄러를 사용하면 한가지 문제가 있습니다. 만약 스케줄러의 주기 중간에 자리가 났을 경우라도, 다음 스케줄러가 실행될 때까지 대기를 해야합니다. 스케줄러의 주기가 길어질수록, 자리가 났음에도 대기하는 시간이 더 길어집니다. 그럼에도 스케줄러를 이용하여 구현한 이유는 다음과 같습니다.

• 스케줄러를 통해서 한번에 토큰 상태를 WAIT -> ACTIVE **로 상태 변경
• 스케줄러를 통해서 ACTIVE 된지 10분이 지난 토큰을 만료시킴

이렇게 2가지 역할을 자동으로 주기적으로 처리를 해주며, 구현 난이도도 어렵지 않아 스케줄러를 이용하여 대기열을 관리하게 되었습니다.

 

더 좋은 방법은 없을까?

 

지금 방식도 나쁘지는 않지만, 이벤트 리스너 방식이나 pub/sub 방식을 이용한다면 스케줄러를 이용할 때 보다 더 효율적일 수도 있다고 생각합니다. 토큰의 활성화열에 빈자리가 생겼을 때 이벤트 리스너가 토큰의 상태를 WAIT -> ACTIVE 로 변경하면 되기 때문입니다.

여기서 주의할 점이라면 AFTER_COMMIT 으로 받아야 토큰이 만료된 후에 이벤트를 받을 수 있습니다.

 

2. 놀이동산 방식 + Redis를 이용한 대기열 구현

 

https://easydrawingguides.com/how-to-draw-a-ferris-wheel/

 

놀이동산 방식이란?

대관람차를 생각하면 쉬운데, 일정주기마다 N명씩 놀이동산에 입장시키는 것처럼, 일정 주기가 되면 대기열에 있던 사용자들을 N명씩 순차적으로 들여보내는 방식이다.

 

장점

은행 창구 방식과는 다르게 대기시간이 정해여 있다.

예를 들어 10초마다 500명씩 예약 가능 상태로 변경 가능 하다면, 3000번째 사용자는 약 1분 뒤에 예약이 가능해 진다.

 

단점

예약이 완료되어 나가는 사람보다 예약하기 위해 진입하는 사람이 더 많아진다면 서버에 부하가 생기게 된다.

Redis를 사용한 이유?

DB → Redis로 대기열을 이관한 이유는 다음과 같다.

• DB의 부하를 줄여준다.
  • DB는 비용이 비싼 리소스다. 그리고 disk를 사용하기 때문에 인메모리를 사용하는 Redis보다 속도가 느리다.
  • Redis를 활용한다면 DB의 병목현상을 줄여주고, 더 빠르게 대용량 트래픽을 감당할 수 있다.
• 대기열의 진입을 순차적으로 관리 가능
  • Redis의 자료구조 중 Sorted Set 을 이용한다면 Score 값을 활용하여, 사용자가 들어온 순서대로 우선순위를 결정할 수 있다.
  • 대기열의 첫번째부터 활성화 상태로 변경해주면 되기 때문에 관리가 용이하다.

 

Redis를 이용해도 마찬가지로 토큰을 관리해주는 스케줄러가 필요하다.

다만, DB로 구현했을 때와는 다르게 TTL값을 주어 자동으로 정해진 시간이 되면 만료가 되기 설정을 할것이기 때문에 토큰 활성화에 대한 스케줄러만 있으면 된다.

 

@Component
@RequiredArgsConstructor
@Slf4j
public class WaitingQueueScheduler { // 대기열 관련 스케줄러

    private final WaitingQueueFacade waitingQueueFacade;

    /**
     * token을 active 하는 스케줄러 10초마다 실행
     */
    @Scheduled(fixedRate = 1000 * 10)
    public void activeToken() {
        waitingQueueFacade.active();
    }

}

 

구현 코드는 아래와 같다.

 

@Service
@RequiredArgsConstructor
public class WaitingQueueService {

    private final JwtUtils jwtUtils;
    private final WaitingQueueRepository waitingQueueRepository;

    /**
     * 토큰의 활성화 여부를 체크하여 토큰 대기열 정보를 반환한다.
     *
     * @param user  user 정보
     * @param token token 정보
     * @return WaitingQueue 대기열 정보
     */
    @Transactional
    @DistributedLock(key = "'waitingQueueLock'")
    public WaitingQueue checkWaiting(User user, String token) {
        // 1. 토큰을 발급한다.
        if (token == null) token = jwtUtils.createToken(user.getUserId());
        // 2. 현재 활성 유저 수 확인
        long activeTokenCnt = waitingQueueRepository.getActiveCnt();
        // 3. 활성화 시킬 수 있는 수 계산
        long availableActiveTokenCnt = WaitingQueue.calculateActiveCnt(activeTokenCnt);

        if (availableActiveTokenCnt > 0) {
            return getInActive(user, token); // 활성화 정보 반환
        }
        return getInWaiting(user, token); // 대기열 정보 반환
    }

    private WaitingQueue getInActive(User user, String token) {
        // 1. 활성 유저열에 추가
        waitingQueueRepository.saveActiveQueue(user, token);
        // 2. ttl 설정
        waitingQueueRepository.setTimeout(token, AUTO_EXPIRED_TIME, TimeUnit.MILLISECONDS);
        // 3. 대기열에서 토큰 정보 제거
        waitingQueueRepository.deleteWaitingQueue(user, token);
        // 4. 활성화 정보 반환
        return WaitingQueue.builder()
                .token(token)
                .user(user)
                .status(ACTIVE)
                .build();
    }

    private WaitingQueue getInWaiting(User user, String token) {
        Long myWaitingNum = waitingQueueRepository.getMyWaitingNum(user, token);
        if (myWaitingNum == null) { // 대기순번이 없다면 대기열에 없는 유저
            // 대기열에 추가
            waitingQueueRepository.saveWaitingQueue(user, token);
            // 내 대기순번 반환
            myWaitingNum = waitingQueueRepository.getMyWaitingNum(user, token);
        }
        // 대기 잔여 시간 계산 (10초당 활성 전환 수)
        long waitTimeInSeconds = (long) Math.ceil((double) (myWaitingNum - 1) / ENTER_10_SECONDS) * 10;

        return WaitingQueue.builder()
                .token(token)
                .user(user)
                .status(WAIT)
                .waitingNum(myWaitingNum)
                .waitTimeInSeconds(waitTimeInSeconds)
                .build();
    }

    /**
     * N초당 M 명씩 active token 으로 전환한다.
     */
    public void activeTokens() {
        // 대기열에서 순서대로 정해진 유저만큼 가져오기
        Set<String> waitingTokens = waitingQueueRepository.getWaitingTokens();
        // 대기열에서 가져온만큼 삭제
        waitingQueueRepository.deleteWaitingTokens();
        // 활성화 열로 유저 변경
        waitingQueueRepository.saveActiveQueues(waitingTokens);
    }

    /**
     * 강제로 active token 을 만료시킨다.
     *
     * @param token token 정보
     */
    public void forceExpireToken(String token) {
        waitingQueueRepository.deleteExpiredToken(token);
    }
}

 

 

@Repository
@RequiredArgsConstructor
public class WaitingQueueRepositoryImpl implements WaitingQueueRepository {

    private final WaitingQueueJpaRepository waitingQueueJpaRepository;
    private final RedisRepository redisRepository;

    @Override
    public Optional<WaitingQueue> saveQueue(WaitingQueue queue) {
        WaitingQueueEntity queueEntity = waitingQueueJpaRepository.save(WaitingQueueEntity.toEntity(queue));

        return Optional.of(queueEntity.toDomain());
    }

    @Override
    public long getActiveCnt() {
        return redisRepository.countActiveTokens();
    }

    @Override
    public void saveActiveQueue(User user, String token) {
        redisRepository.setAdd(ACTIVE_KEY + ":" + token, String.valueOf(user.getUserId()));
    }

    @Override
    public void setTimeout(String key, long timeout, TimeUnit unit) {
        redisRepository.setTtl(ACTIVE_KEY + ":" + key, timeout, unit);
    }

    @Override
    public void deleteWaitingQueue(User user, String token) {
        redisRepository.zSetRemove(WAIT_KEY, token + ":" + user.getUserId());
    }

    @Override
    public Long getMyWaitingNum(User user, String token) {
        return redisRepository.zSetRank(WAIT_KEY, token + ":" + user.getUserId());
    }

    @Override
    public void saveWaitingQueue(User user, String token) {
        redisRepository.zSetAdd(WAIT_KEY, token + ":" + user.getUserId(), System.currentTimeMillis());
    }

    @Override
    public Set<String> getWaitingTokens() {
        return redisRepository.zSetGetRange(WAIT_KEY, 0, ENTER_10_SECONDS - 1);
    }

    @Override
    public void deleteWaitingTokens() {
        redisRepository.zSetRemoveRange(WAIT_KEY, 0, ENTER_10_SECONDS - 1);
    }

    @Override
    public void saveActiveQueues(Set<String> tokens) {
        redisRepository.setAddRangeWithTtl(ACTIVE_KEY, tokens, AUTO_EXPIRED_TIME, TimeUnit.MILLISECONDS);
    }

    @Override
    public void deleteExpiredToken(String token) {
        redisRepository.deleteKey(ACTIVE_KEY + ":" + token);
    }

}

 

 

@Repository
@RequiredArgsConstructor
public class RedisRepository {

    private final RedisTemplate<String, String> redisTemplate;
    private static final String REDIS_NAMESPACE = "hhplus:";
    private static final String ACTIVE_COUNT_KEY = "hhplus:waiting:active:*";

    // sorted_set 추가
    public Boolean zSetAdd(String key, String value, double score) {
        return redisTemplate.opsForZSet().addIfAbsent(REDIS_NAMESPACE + key, value, score);
    }

    // sorted_set 삭제
    public void zSetRemove(String key, String value) {
        redisTemplate.opsForZSet().remove(REDIS_NAMESPACE + key, value);
    }

    //sorted_set 순서 구하기
    public Long zSetRank(String key, String token) {
        return redisTemplate.opsForZSet().rank(REDIS_NAMESPACE + key, token);
    }

    public Set<String> zSetGetRange(String key, long start, long end) {
        return redisTemplate.opsForZSet().range(REDIS_NAMESPACE + key, start, end);
    }

    public void zSetRemoveRange(String key, int start, int end) {
        redisTemplate.opsForZSet().removeRange(REDIS_NAMESPACE + key, start, end);
    }

    //set 사용
    public Long setAdd(String key, String value) {
        return redisTemplate.opsForSet().add(REDIS_NAMESPACE + key, value);
    }

    public void setAddRangeWithTtl(String key, Set<String> value, long timeout, TimeUnit unit) {
        value.forEach(token -> {
            String[] tokenInfo = token.split(":");
            redisTemplate.opsForSet().add(REDIS_NAMESPACE + key + ":" + tokenInfo[0], tokenInfo[1]);
            setTtl(key + ":" + tokenInfo[0], timeout, unit);
        });
    }

    public Boolean setIsMember(String key, String value) {

        return redisTemplate.opsForSet().isMember(REDIS_NAMESPACE + key, value);
    }

    public void setTtl(String key, Long timeout, TimeUnit timeUnit) {
        redisTemplate.expire(REDIS_NAMESPACE + key, timeout, timeUnit);
    }

    public void clearCurrentDatabase() {
        RedisConnection connection = null;
        try {
            connection = RedisConnectionUtils.getConnection(Objects.requireNonNull(redisTemplate.getConnectionFactory()));
            connection.serverCommands().flushDb();  // Execute FLUSHDB command
        } finally {
            if (connection != null) {
                RedisConnectionUtils.releaseConnection(connection, redisTemplate.getConnectionFactory());
            }
        }
    }

    public Long countActiveTokens() {

        String luaScript = "local count = 0 " +
                "for _, key in ipairs(redis.call('keys', ARGV[1])) do " +
                "count = count + 1 " +
                "end " +
                "return count";

        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
        redisScript.setScriptText(luaScript);
        redisScript.setResultType(Long.class);

        return redisTemplate.execute(redisScript, Collections.emptyList(), ACTIVE_COUNT_KEY);
    }

    public void deleteKey(String key) {
        redisTemplate.delete(REDIS_NAMESPACE + key);
    }

}

 

RDB로 빈 주입해주던 것을 Redis로만 변경하여 DIP를 잘지켜주었다.

자세한 코드는

https://github.com/smileboy0014/hhplus-concert/pull/7 여기를 확인해보면 될 것 같다.

 

10초당 600명을 대기열에서 활성화열로 전환해주는 이유?

 

• 한 유저가 예약조회부터 결제까지 걸리는 시간: 평균 1분
• DB에 동시에 접근할 수 있는 트래픽의 최대치
  • 약 1,000 TPS(초당 트랜잭션 수) ⇒ 1분당 60,000
• 1분동안 유저가 호출하는 API 수
  • 5(콘서트 조회, 콘서트 가능 날짜 조회, 콘서트 예약 좌석 조회, 좌석 예약, 결제) * 2( 동시성 이슈에 의해 예약에 실패하는 케이스를 위한 재시도 계수(보정치)) = 10
• 분당 처리할 수 있는 동시접속자 수 = (60,000/ 60) * 10 = 10,000명

→ 결론: 10초마다 600명의 유저를 예약 가능한 상태로 전환

 

놀이동산 방식의 한계?

 

놀이동산 방식을 이용하면 빠르게 대용량 트레픽을 다루며, DB에 대한 병목 현상을 줄일 수 있지만, 서비스를 이용하는 유저의 수를 보장할 수 없다.

즉, 예약 가능한 유저들의 수가 계속 증가하여 결국에는 서버의 부하가 커질 것이다.

이런 경우에는 서버의 스케일 아웃이나 주기적으로 활성화 유저의 수를 확인하며 Redis의 확정도 고려해 볼 수 있을 것 같다.