[Lock] X-Lock은 순서를 보장할까?(Transaction Scheduling : CATS)

[문제 시나리오 설명]

선착순 구매 프로젝트를 진행하고 있다.

특가 상품을 한정된 수량만 판매하기 때문에 갑작스럽게 이벤트 트래픽이 발생하는 상황을 가정한다.

 

가장 먼저 고민한 내용은 동시성 이슈이다.

    * 동시성 이슈란? 하나의 공유 자원을 여러 실행 단위가 변경함으로써 자원의 정합성이 맞지 않는 문제

프로젝트에서 동시성 이슈가 발생할 수 있는 자원은 상품 재고이다.

상품 구매가 일어나면, (상품 재고 확인 -> 재고가 남아 있으면 재고 차감) 의 로직을 수행하는데, 

로직의 원자성을 보장하기 위해 X-Lock을 사용했다.

    * X-Lock에 대해 자세하게 알고 싶으면 링크를 참조해주세요. https://mergeman.tistory.com/10

 

동시성 이슈는 해결 되었지만, 순서도 보장 되었을까?

 

5명의 사용자가 동시에 재고 차감을 요청한 경우를 생각해보자.

서버 시간에 따른 요청 순서는 A, B, C, D, E이다.

유저 A가 X-Lock을 획득했고, 유저 B, C, D, E는 락 대기 상태가 되었다.

이 때 5명의 유저 F, G, H, I, J의 요청이 추가로 들어왔다.

A가 여전히 락을 해제하지 않았으므로 새로운 유저 5명의 트랜잭션도 락 대기 상태가 되었다.

A가 락을 해제했을 때 B ~ J의 요청은 순서대로 실행될까?

정답은 보장 할 수도 있고, 아닐 수도 있다.

---

 

[InnoDB의 트랜잭션 스케줄링 전략]

CATS(Contention-Aware Transaction Scheduling)

락 역시 공유자원이기 때문에 동시에 락을 획득하려는 경쟁이 발생한다.

경쟁에서 실패한 트랜잭션은 락 대기 상태에 들어간다.

 

MySQL InnoDB는 트랜잭션 범위 안에서 X-Lock을 실행할 수 있으며, 락 경쟁이 발생하면 InnoDB의 CATS(Contention-Aware Transaction Scheduling) 알고리즘에 의해 우선순위가 스케줄링 된다.

    * MySQL 8.0.20 이전에는 FIFO(First In First Out)와 CATS를 함께 사용했으나 8.0.20 이후로는 CATS에 의해서만 결정된다.

 

CATS 알고리즘은 아래의 조건에 따라 트랜잭션 우선순위를 결정한다.

1. 해당 트랜잭션이 차단하고 있는 트랜잭션 수에 따라 스케줄링 가중치를 할당해 대기 우선 순위를 지정한다.
2. 가중치가 동일하면 가장 오래 대기중인 트랜잭션이 우선이다.

 

이 조건들을 바탕으로 락 대기 상태를 요청 순서에 따라 보장하는 상태와 보장하지 않는 상태로 나누어 검증해보자.

---

 

검증을 위한 사전 준비

- 준비물 : MySQL, SpringBoot(스프링 부트와 DB 접근을 위한 환경 구축)

 

- 상품 테이블을 생성

CREATE TABLE products (
    id INT AUTO_INCREMENT,
    title VARCHAR(30),
    stock INT,
    purchased_stock INT,
    PRIMARY KEY(id)
)engine=InnoDB;

 

- 상품 엔티티 혹은 도메인 클래스 생성

public class Product {   
    private int id;
    private String title;
    private int stock;
    private int purchasedStock;
}

 

- 상품 영속성 클래스 생성

@Mapper
public interface ProductMapper {

    @Select("SELECT * FROM products WHERE id = #{id} FOR UPDATE")
    public Product findByIdForUpdate(final int id);

    @Update("UPDATE products SET purchased_stock = #{updatedStock} WHERE id = #{id}")
    public int updateStock(final int id, final int updatedStock);
}

 

- 상품 서비스 클래스 생성

@Service
@RequiredArgsConstructor
public class ProductService {

    private final ProductMapper productMapper;

    @Transactional
    public void deductStock(final int id, final int requestQuantity) {
        Product product = productMapper.findByIdForUpdate(id);

        if (product.getPurchasedStock() + requestQuantity > product.getStock()) {
            throw new RuntimeException("Total Stock Exceeded");
        }
        
        productMapper.updateStock(id, product.getPurchasedStock() + requestQuantity);
    }
}

 

[InnoDB가 락 대기 상태를 요청 순서대로 보장하는 상태]

- 가설

InnoDB가 트랜잭션 간 입력 순서대로 순서를 보장하려면 동일한 가중치를 트랜잭션 순서대로 누적하는 것이다.

예를들어 A <- B <- C <- D 의 순서로 입력되며 모두 X-Lock을 걸었다고 가정해보자.

A는 블로킹 되지 않았으므로 실행 되지만, B, C, D는 차례대로 블로킹되어 순서를 기다릴 것이다.

CATS 알고리즘에 의하면 대기중인 트랜잭션 중 B가 가장 많은 트랜잭션을 블로킹 중이다.(2개 : C, D)

따라서 다음 락의 우선 순위는 B에게 주어진다.

 

- 검증

검증 방법

1. 수동으로 상품에 X-Lock을 건다.
2. 논블로킹하게 재고 차감 로직(재고 확인 -> 재고가 남아있으면 차감)을 시도한다.
   (멀티 스레드로 실행하는 코드는 순서를 주기 위해 약간의 지연을 둔다.)
3. 락 대기 상태와 트랜잭션의 가중치를 확인한다.
   (이미 락이 걸려있기 때문에 코드로 실행한 재고 차감 로직은 락 대기 상태에서 확인할 수 있다.)
4. 수동으로 COMMIT 후 코드에서 실행 순서를 확인한다.
   

실습 방법

먼저, 터미널을 통해 MySQL에 직접 X-Lock을 건다.

START TRANSACTION;

SELECT * FROM products WHERE id = 1 FOR UPDATE;

 

 

ExecutorService를 통해 3개의 스레드를 동시에 실행한다.

실행 순서를 확인하기 위해 AtomicInteger와 DB에 순서대로 접근하기 위해 약간의 지연을 두었다.

@Test
public void XLockTest() throws InterruptedException {
    int numberOfThread = 3;

    ExecutorService executorService = Executors.newFixedThreadPool(numberOfThread);
    CountDownLatch latch = new CountDownLatch(numberOfThread);
    AtomicInteger counter = new AtomicInteger(0);

    for (int i = 0; i < numberOfThread; i++) {
        int order = counter.incrementAndGet();
        executorService.submit(() -> {
            try {
                productService.deductStock(1, 1, order);
            } finally {
                 latch.countDown();
            }
        });
        Thread.sleep(500);
    }
    latch.await();
}

 

실행 순서를 확인하기 위해 deductStock 메서드 파라미터에 order을 추가하자.

@Transactional
public void deductStock(final int id, final int requestQuantity, final int order) {
    Product product = productRepository.findByIdForUpdate(id);

    if (product.getPurchasedStock() + requestQuantity > product.getStock()) {
        throw new RuntimeException("Total Stock Exceeded");
    }

    productRepository.updateStock(id, product.getPurchasedStock() + requestQuantity);
    log.info("Finish Order : " + order);   
}

 

터미널에서 새로운 세션을 연 뒤, MySQL에서 락 대기 상태를 확인해보자.

SELECT
  waiting_trx_id,
  waiting_pid,
  waiting_query,
  blocking_trx_id,
  blocking_pid,
  blocking_query
FROM sys.innodb_lock_waits;

 

MySQL에 X-Lock을 건 세션으로 돌아가 커밋을 하자.

COMMIT;

 

 

- 검증 결과

InnoDB의 락 대기 상태를 확인하면 아래와 같다.

각 컬럼은 아래의 내용을 의미한다.

• waiting_trx_id : 대기중인 트랜잭션
• waiting_query : 대기 중인 쿼리
• blocking_trx_id : 같은 row의 waiting_trx_id를 막고 있는 트랜잭션
• blocking_query : waiting_trx_id를 막고 있는 쿼리

 

결과를 정리하면 아래와 같다.

• trx 304225 : 락 점유 중
• trx 304226 :
  • trx 304225가 product 1에 X-Lock을 점유해 trx 304226이 블로킹 되었다.
• trx 30227 :
  • trx 304225가 product 1에 X-Lock을 점유해 trx 304227이 블로킹 되었다.
  • trx 304226가 product 1에 X-Lock을 걸기 위해 대기 중이며 trx 304227이 블로킹 되었다.
• trx 30228 :
  • trx 304225가 product 1에 X-Lock을 점유해 trx 304228이 블로킹 되었다.
  • trx 304226가 product 1에 X-Lock을 걸기 위해 대기 중이며 trx 304228이 블로킹 되었다.
  • trx 304227가 product 1에 X-Lock을 걸기 위해 대기 중이며 trx 304228이 블로킹 되었다.

 

결과를 그림으로 나타내면 아래와 같은 관계를 가진다.

trx 226이 가장 많은 트랜잭션을 블로킹 하고 있으므로 가장 우선 순위를 가진다.

trx 225의 락을 해제하는 순간 226부터 순서대로 다음 락을 점유할 것이며, 228이 가장 마지막에 종료 됨을 예측할 수 있다.

 

재고 차감 결과는 아래와 같다.

모두 락 대기 상태에 들어갔지만, 실행 순서대로 종료 되었다.
(1 -> 2 -> 3)

 

 

하지만 여기서 의심이 들 수 있다.

과연, CATS 알고리즘에 의해 가중치를 받은건지? 혹은 FIFO로 실행된 것인지?

다음 검증을 통해 입력 순서를 무시하고 가중치로 실행되는 결과를 확인해보자.

---

 

[InnoDB가 락 대기 상태를 요청 순서대로 보장하지 않는 상태]

- 가설

이전 검증과 동일하게 수동으로 락을 점유하고 논블로킹하게 재고 차감 요청을 해 락 대기 상태로 만들 것 이다.

대신 두 그룹으로 나눌건데, A 그룹은 product 1에 대한 락 점유만 시도할 것이고,

B 그룹은 product 2에 먼저 X-Lock을 건 후 product 1에 락 점유를 시도할 것이다.

A 그룹은 2개의 스레드를 사용, B 그룹은 5개의 스레드를 사용한다.

 

CATS 알고리즘에 따르면 블로킹 하고 있는 트랜잭션이 많으면 가중치를 받는다.

B 그룹에서 가장 먼저 요청을 한 (실행 순서대로) trx 4가 블로킹 한 트랜잭션이 가장 많으므로 우선 순위를 가질 것이다.

 

- 검증

검증 방법

1. 수동으로 상품에 X-Lock을 건다.
2. 논블로킹하게 A 그룹(스레드 2개)의 재고 차감 로직(재고 확인 -> 재고가 남아있으면 차감)을 시도한다.
   (멀티 스레드로 실행하는 코드는 순서를 주기 위해 약간의 지연을 둔다.)
3. 논블로킹하게 B 그룹(스레드 5개)의 다른 락을 먼저 점유한 상태에서 재고 차감 로직(재고 확인 -> 재고가 남아있으면 차감)을 시도한다.
   (멀티 스레드로 실행하는 코드는 순서를 주기 위해 약간의 지연을 둔다.)
4. 락 대기 상태와 트랜잭션의 가중치를 확인한다.
   (이미 락이 걸려있기 때문에 코드로 실행한 재고 차감 로직은 락 대기 상태에서 확인할 수 있다.)
5. 수동으로 COMMIT 후 코드에서 실행 순서를 확인한다.

실습 방법

먼저, 터미널을 통해 MySQL에 직접 X-Lock을 건다.

START TRANSACTION;

SELECT * FROM products WHERE id = 1 FOR UPDATE;

 

B 그룹이 실행할 메서드를 ProductService에 추가한다.

@Transactional
public void deductStockWithAnotherLock(final int id, final int requestQuantity, final int order) {
    Product prefixLock = productRepository.findByIdForUpdate(2);

    Product product = productRepository.findByIdForUpdate(id);

    if (product.getPurchasedStock() + requestQuantity >= product.getStock()) {
        throw new RuntimeException("Total Stock Exceeded");
    }

    productRepository.updateStock(id, product.getPurchasedStock() + requestQuantity);
    log.info("Finish Order : " + order);
}

 

ExecutorService를 통해 A 그룹(스레드 2개), B 그룹(스레드 5개)를 실행한다.

그룹 간은 순차적으로, 그룹 내에서는 논블로킹하게 실행해야 한다.

실행 순서를 확인하기 위해 AtomicInteger와 DB에 순서대로 접근하기 위해 약간의 지연을 두었다.

@Test
public void XLockTestWithAnotherLock() throws InterruptedException {
    int firstGroupThread = 2;
    int secondGroupThread = 5;

    ExecutorService executorService = Executors.newFixedThreadPool(firstGroupThread + secondGroupThread);
    CountDownLatch firstGroupLatch = new CountDownLatch(firstGroupThread);
    CountDownLatch secondGroupLatch = new CountDownLatch(secondGroupThread);
    AtomicInteger counter = new AtomicInteger(0);

    for (int i = 0; i < firstGroupThread; i++) {
        int order = counter.incrementAndGet();
        executorService.submit(() -> {
            try {
                productService.deductStock(1, 1, order);
            } finally {
                firstGroupLatch.countDown();
            }
        });
        Thread.sleep(500);
    }

    for (int i = 0; i < secondGroupThread; i++) {
        int order = counter.incrementAndGet();
        executorService.submit(() -> {
            try {
                productService.deductStockWithAnotherLock(1, 1, order);
            } finally {
                secondGroupLatch.countDown();
            }
        });
        Thread.sleep(500);
    }

    firstGroupLatch.await();
    secondGroupLatch.await();
}

 

 

터미널에서 새로운 세션을 연 뒤, MySQL에서 락 대기 상태를 확인해보자.

SELECT
  waiting_trx_id,
  waiting_pid,
  waiting_query,
  blocking_trx_id,
  blocking_pid,
  blocking_query
FROM sys.innodb_lock_waits;

 

MySQL에 X-Lock을 건 세션으로 돌아가 커밋을 하자.

COMMIT;

 

- 검증 결과

락 대기 상태를 확인해보자.

 

여기서 눈여겨 볼만한 점은 trx 262가 product 2의 락은 획득했지만, product 1의 락을 획득하기 위해 대기중이다.

CATS 알고리즘이 동작한다면 FIFO 가 아니라 가장 많은 트랜잭션을 블로킹 하고 있는 trx 262(순서 상 세 번째 락 점유 요청, 그룹 B의 첫 번째)가 가장 먼저 실행되어야 한다.

 

trx 236 ~ 266 까지는  trx 262가 product 1의 락을 점유한 후 product 1, 2의 락을 해제해야 순서대로 product 2의 락 점유 시도를 할 것이다.

 

애플리케이션에서 실행 결과를 확인해보자.

(3 -> 1 -> 4 -> 2 -> 5 -> 6 -> 7)

 

예상한대로 Order3 (trx 262)이 먼저 실행되었다.

CATS 알고리즘대로 작동했다는 것이다!

 

하지만 그 다음으로 Order1 (trx 260)이 실행되었다.

CATS 알고리즘대로라면 블로킹한 트랜잭션이 많은 트랜잭션인 Order4 (trx 263)가 실행되어야 하는게 아닌가 하는 의문이 있을 수 있다.

• 이는 그룹 B는 product 2에 먼저 락 점유를 시도하기 때문에 Order4 (trx 263)는 product 2에 락 점유를 시도한다.
  그 때 Order1 (trx 260)이 product 1에 락 점유를 시도한다.
  따라서 Order1 (trx 260)이 락을 해제해야 Order4 (trx 263)가 비로소 product 1에 대한 락을 점유할 수 있다.

 

이후 과정은 아래 그림처럼 되어 이전 과정을 반복한다.

(Order 4가 CATS 알고리즘에 따라 가장 우선 순위를 부여 받는다.)

 

 

[결론]

• InnoDB는 CATS 알고리즘에 의해 트랜잭션 우선순위를 스케줄링 하기 때문에 개발자의 의도대로 조절 하기 어렵다.
  실제 서비스 환경은 예시 시나리오보다 훨씬 복잡한 데이터 관계를 가지고 있다.
  우선 순위를 하나하나 예측하고 검증하기에는 비용이 너무 크다.
• InnoDB에 트랜잭션의 락 관계는 체이닝 형태로 저장되고 있다.
  A <- B <- C 관계를 저장하기 위해 n(n - 1) / 2 개수의 row를 저장한다.
  또한 스케줄링 또한 InnoDB에 의해 이루어지므로 DB에 가중되는 부하가 크다.