CATS: MySQL은 락 점유 순서를 어떻게 결정할까?

'페스타고' 서비스에서 선착순 티켓팅 기능을 개발하며 궁금증이 생겼다.

 

X-lock은 요청 순서대로 부여될까?

즉, 트랜잭션 A, B, C가 동일한 자원에 대해 순차적으로 락을 대기하면, 그 순서대로 락을 획득할까?

 

선착순 티켓팅이 제대로 작동하려면, 먼저 대기열에 등록된 트랜잭션이 먼저 락을 획득하는 것이 보장되어야 한다.

이를 확인하기 위해 MySQL의 '트랜잭션 스케줄링 기법'에 대해 알아보았다.

 

트랜잭션 스케줄링 기법이란?

트랜잭션 스케줄링은 데이터베이스 시스템에서 여러 트랜잭션이 동시에 실행될 때 이들의 실행 순서를 결정하는 방법이다.

 

여러 트랜잭션이 동일한 자원에 대한 락을 대기하는 경우, 어떤 트랜잭션이 먼저 락을 할당받아야 할까?

 

바로 트랜잭션 스케줄링이 트랜잭션이 어떤 순서로 데이터에 접근하고 락을 획득할 것인지, 그리고 어떤 트랜잭션이 우선권을 갖게 될 것인지를 결정한다.

MySQL에서 트랜잭션 스케줄링 기법으로 과거에는 어떤 방식이 사용되었고, 현재는 어떻게 개선되었는지 알아보도록 하자.

 

과거 - FIFO 방식

MySQL 8.0 이전의 InnoDB 스토리지 엔진에서 트랜잭션 스케줄링 기법으로 선입선출(FIFO) 방식이 기본적으로 사용되었다.

이 방법식은 대기열에 먼저 등록된 트랜잭션이 먼저 락을 획득한다.

 

데드락의 위험성

FIFO 방식은 데드락의 위험을 내포하고 있다. 예를 들어, 트랜잭션 A가 S-lock을 보유하고 있고, 트랜잭션 B와 트랜잭션 A가 동일한 자원에 대한 X-lock을 대기하면, 서로가 서로를 기다리는 교착 상태(데드락)에 빠질 수 있다.

tx A	tx B
🔐 S-lock 점유 (id = 1) SELECT * FROM t WHERE id =1 FOR SHARE;
	X-lock 대기 (id = 1) SELECT * FROM t WHERE id =1 FOR UPDATE;
X-lock 대기 (id = 1) SELECT * FROM t WHERE id =1 FOR UPDATE;

 

아래는 (id = 1)인 레코드에 대한 락 점유 대기열이다.

tx A	tx B	tx A
S-lock	X-lock	X-lock
점유	대기	대기

 

A가 S-lock을 점유한 상태에서, B는 X-lock을 얻으려 대기하고, A도 X-lock을 얻으려 대기한다. 하지만 A는 자신이 X-lock을 획득할 때까지 S-lock을 해제하지 않는다. 즉, B는 A가 락을 풀기를 기다리고, A는 B의 작업이 끝나길 기다린다. 즉, 데드락 문제가 발생한다.

 

트랜잭션 간 우선순위가 존재한다면?

만약  FIFO 방식을 대신, A에게  B보다 먼저 X-lock을 할당한다면 데드락 문제는 발생하지 않는다.

([A] S-lock → [A] X-lock → [B] X-lock 순으로 이루어진다.)

이와 같이 가중치가 높은 트랜잭션에게 먼저 락을 할당한다면, 데드락 문제를 회피할 수 있다.

 

이렇게 트랜잭션별 우선순위에 따라 락을 할당하는 방식을 CATS라 한다.

단, 이 방법도 모든 상황에서 데드락을 막을 수 있는 건 아니다. 예를 들어 두 트랜잭션이 동시에 S-lock을 가진 상태에서 X-lock을 요청하면 여전히 데드락 문제가 발생한다.

 

현재 - CATS 알고리즘

MySQL 8.0부터는 CATS(Contention-Aware Transaction Scheduling) 알고리즘을 도입하여 트랜잭션 스케줄링을 개선했다.

CATS는 대기 중인 트랜잭션이 차단하고 있는 다른 트랜잭션의 수를 기반으로 가중치를 계산하고, 이 가중치에 따라 락을 할당한다.

 

대기 중인 트랜잭션이 해당 리소스를 대기하기 전 이미 많은 리소스에 대한 락을 점유하여, 다른 트랜잭션들이 해당 트랜잭션이 락을 해제할 때까지 기다려야 하는 경우 가중치가 높아진다.

즉, 더 많은 트랜잭션을 차단하고 있는 트랜잭션일수록 먼저 락을 점유하게 된다.

(각 트랜잭션의 가중치는 INFORMATION_SCHEMA.INNODB_TRX 테이블의 trx_schedule_weight 컬럼을 통해 확인할 수 있다.)

위 그림에서 t1은 4개의 트랜잭션을 차단하고 있고, t2는 3개의 트랜잭션을 차단하고 있으므로 t1에게 먼저 O1에 대한 락을 할당한다.

S-lock의 경우 CATS는 가능한 한 많은 트랜잭션에게 락을 할당하는 방법을 채택한다.

자원에 대한 새로운 락 요청이 들어오면, MySQL의 CATS 스케쥴러는 각 트랜잭션의 가중치를 갱신한다.

 

이러한 방법으로 더 많은 트랜잭션이 빨리 진행될 수 있도록 한다.

 

예시 상황

아래 상황에서 A가 작업을 마치면, 대기 중인 B와 C 중 누가 락을 먼저 얻을까?

tx A	tx B	tx C	tx D
(id=1) X-lock 점유
	(id=2) S-lock 점유
		(id=1) X-lock 대기
			(id=2) X-lock 대기
	(id=1) X-lock 대기

 

B는 D를 차단하고 있으므로 가중치(trx_schedule_weight)가 2로 더 높다.

C는 다른 트랜잭션에 영향을 주지 않으므로 가중치가 1이다.

따라서 C가 락 점유 대기열에 먼저 등록이 되었음에도 불구하고, 가중치가 높은 B가 먼저 (id =1)에 대한 X-lock을 획득한다.

(동일한 가중치를 가진 트랜잭션 사이에서는 먼저 등록된 트랜잭션이 먼저 락을 획득한다.)

 

CATS 성능

CATS의 도입으로 지연 시간을 획기적으로 줄이고 처리량을 증가시킬 수 있었다.

트랜잭션이 최대한 서로를 차단하지 않고 효율적으로 진행될 수 있게 하여, 높은 동시성과 복잡한 락 경합이 있는 환경에서 더 좋은 성능을 보인다.

 

아래 그래프는 시스템 경합이 있을 때 FIFO 방식보다 CATS 방식이 TPS, 평균 레이턴시, 95p 레이턴시에서 좋은 성능을 보인다는 것을 보여준다.

 

선착순 기능에서의 X-lock

선착순 티켓팅 시스템을 구현할 때, MySQL의 X-lock을 사용하여 각 사용자의 요청 순서를 보장하는 것이 가능할까?

 

만약 모든 트랜잭션이 동일한 가중치를 가지고 있다면, 대기열에 먼저 들어온 트랜잭션이 해당 자원에 대한 락을 먼저 획득하게 된다.

즉, 트랜잭션 도중에 다른 락을 먼저 획득하지 않았다면, 선착순이 보장된다고 할 수 있다.

 

그러나 때때로, 데이터베이스 내의 외래 키 제약조건이나 데이터를 삽입/갱신/삭제하는 과정에서 예상치 못한 락이 발생할 수 있으므로 주의해야 한다. 이러한 락은 트랜잭션의 순서를 예기치 않게 변경할 수 있기 때문에, 선착순 로직에 영향을 줄 수 있다.

 

따라서 만약 MySQL에서 X-lock을 통해 완벽한 선착순을 보장하는 것이 어렵다면, 메시지 큐와 같은 다른 기술을 통해 요청을 순차적으로 처리하는 것이 좋다. (메시지 큐는 각 요청을 순서대로 저장하고 처리함으로써 선착순을 보장할 수 있게 도와준다.)

 

---

참고 자료

MySQL Docs: 15.7.6 Transaction Scheduling

MySQL Blog: InnoDB Data Locking - Part 4 "Scheduling"

MySQL Blog: Contention-Aware Transaction Scheduling Arriving in InnoDB to Boost Performance

당근 테크 블로그: MySQL CATS (Contention-Aware Transaction Scheduling)