Database Internals

InnoDB 행 잠금의 2원 2규칙에 대해 설명하기에 앞서 개요가 조금 필요할 것 같아 살짝 지루한 이야기를 먼저 해보겠다.

MySQL 서버의 InnoDB 스토리지 엔진에는 아래와 같이 3가지의 행 잠금 알고리즘이 존재한다.

• 레코드 락(Record Lock): 단일 행 레코드에 대한 잠금
• 갭 락(Gap Lock): 간격 잠금(범위를 잠그지만 레코드 자체는 포함하지 않음)
• 넥스트 키 락(Next-Key Lock): 범위를 잠그고 레코드 자체도 잠금

그리고 당연한 이야기처럼 들리겠지만 이 중 넥스트 키 락은 갭 락과 레코드 락이 결합된 형태의 잠금 알고리즘이다. (역사적으로) 데이터베이스 시스템에서는 팬텀 리드(Phantom Read) 문제를 해결하기 위해 키 범위 잠금 기술(key-range locking techniques)을 사용해왔다. 이 기술들 중에는 Next-Key Locking이라는 기술이 포함되어 있는데, 현재 우리가 알고 있는 InnoDB의 넥스트 키 락이 이 Next-Key Locking 메커니즘의 실제 구현체이다.
(현실과 동떨어진 이야기지만) Next-Key Locking의 메커니즘은 간단하다. 키 범위 잠금 요청이 들어오면 현재 키(Current Key)뿐만 아니라 다음 키(Next Key)까지 잠그는 것이다. (여담으로) Current Key와 Previous Key를 잠그는 Previous-Key Locking이라는 메커니즘도 존재한다.

각설하고,
팬텀 문제를 해결하기 위해 InnoDB 스토리지 엔진에 구현된 넥스트 키 락은 아직까지도 많은 사용자들에게 혼란을 주고 있다고 생각한다. DB 관련 종사자에게 넥스트 키 락이 무엇인가요? 라고 물어보면 어느 부분까지 정확하게 대답할 수 있을까?(심지어 이 글을 쓰고 있는 나조차도). 더군다나 기본 격리 수준이 REPEATABLE-READ이기 때문에 초심자는 선택의 여지 없이 넥스트 키 락을 맞닥뜨려야 한다.

기억의 굴레(그게 뭐였더라 라는 기억)에서 벗어나고 싶지만 넥스트 키 락은 정말 많이 접하면서도 매번 헷갈리고 잊어버리게 되는 잠금 방식인 것 같다.

그래서,
이번 내용은 어떻게 하면 넥스트 키 락을 쉽게 이해할 수 있을까. 어떻게 하면 헷갈리지 않을 수 있을까에 대한 고민의 흔적을 적은 것이다. 코드 설명의 개입을 최대한 없애고 추상적인 형태로 이해할 수 있도록 InnoDB 행 잠금을 2원 2규칙으로 정리하였다.
추가로 이 내용은 InnoDB 스토리지 엔진에만 국한되며, REPEATABLE-READ 격리 수준에서만 적용됨을 잊지 않도록 하자. 버전은 MySQL 8.4 기준이다.

1. InnoDB 행 잠금의 2원 2규칙
   1. 1) 동등 조건(=)의 쿼리와 갭 락(Gap Lock)
   2. 2) 세컨더리(Non Unique) 인덱스와 동등 조건(=)의 잠금
   3. 3) 프라이머리 키(Primary Key) 인덱스 범위 잠금
   4. 4) 세컨더리 인덱스(Non Unique) 인덱스 범위 잠금
   5. 5) 중복된 행이 존재하는 동등 조건(=)의 잠금
   6. 6) LIMIT절에 대한 잠금
   7. 7) 갭 락 + 레코드 락
   8. 8) ORDER BY DESC 잠금
   9. Reference

InnoDB 행 잠금의 2원 2규칙

아래는 InnoDB 잠금의 2가지 원칙과 2가지 규칙이다.
원칙은 반드시 지켜야 하는 것이며, 규칙은 경우에 따라 적용될 수도 적용되지 않을 수도 있는 것이다.

• 원칙 1: InnoDB의 기본 잠금 단위는 넥스트 키 락이며, 넥스트 키 락의 잠금 범위는 좌측으로는 개구간, 우측으로는 폐구간이다.
• 원칙 2: 잠금은 쿼리를 수행하는 과정에서 접근한 객체에만 걸린다.
• 규칙 1: 인덱스(고유, 비고유)를 사용하는 동등 조건의 쿼리를 수행할 때 레코드 스캔 방향은 오른쪽이며, 마지막 레코드가 동등 조건을 만족하지 않으면 넥스트 키 락은 갭 락으로 강등된다.
• 규칙 2: 고유 인덱스를 사용하는 동등 조건의 쿼리를 수행할 때, 레코드가 동등 조건을 만족하면 넥스트 키 락은 레코드 락으로 강등된다.

원칙 1은 InnoDB의 기본 잠금이 넥스트 키 락이라는 것을 꼭 기억해야 한다는 의미이다. 갭 락도, 레코드 락도 아니다 (내부적으로는 갭 락과 레코드 락이지만). InnoDB 잠금의 시작은 넥스트 키 락이다. 이후에 갭 락과 레코드 락을 따져보는 것이다. 그리고 넥스트 키 락은 특정 기준점을 중심으로 좌측으로는 열린 구간이며, 우측으로는 닫힌 구간이다. R1부터 R10까지의 레코드 범위에서 좌측에 해당하는 R1에는 잠금이 걸리지 않는다는 의미이며, 우측에 해당하는 R10에는 잠금이 걸린다는 의미이다.
ex) (R1, R10]

원칙 2는 쿼리를 수행할 때는 접근한 객체에만 잠금이 걸리기 때문에 엉뚱한 곳에서 잠금이 걸리지 않는다는 의미이다. 여기서 말하는 객체는 쿼리를 수행하는 과정 중에 스쳐 지나가는 모든 것들을 의미한다고 보면 된다.

규칙 1와 규칙 2는 예제를 통해서 살펴보도록 하겠다.

우선 아래와 같이 t 테이블과 테스트 데이터를 생성한다. 최대한 응용하기 쉽도록 테이블과 데이터를 단순화 하였으니 이해하는데 큰 어려움은 없을 것이다.

mysql> CREATE TABLE t (
  id int NOT NULL,
  a int NULL,
  b int NULL,
  PRIMARY KEY (id),
  KEY ix_a(a)
) ENGINE=InnoDB;

mysql> INSERT INTO t(id, a, b) 
VALUES (0,0,0), (5,5,5), (10,10,10), (15,15,15), (20,20,20), (25,25,25);

mysql> SELECT * FROM t;
+----+------+------+
| id | a    | b    |
+----+------+------+
|  0 |    0 |    0 |
|  5 |    5 |    5 |
| 10 |   10 |   10 |
| 15 |   15 |   15 |
| 20 |   20 |   20 |
| 25 |   25 |   25 |
+----+------+------+

그럼 본격적으로 예제 쿼리를 살펴보도록 하자.

1) 동등 조건(=)의 쿼리와 갭 락(Gap Lock)

첫 번째 예제이다. 위의 표는 세션 1에서 t 테이블에 대해 id=7 조건에 해당하는 레코드를 업데이트 하는 것으로 시작한다. id=7 조건에 해당하는 레코드는 없지만, 앞서 얘기했던 것처럼 원칙 1에 따라 기본 잠금 단위는 넥스트 키 락이기 때문에 좌측 개구간, 우측 폐구간을 적용하여 (5, 10]에 넥스트 키 락이 설정된다. 그리고 동시에 규칙 1에 따라 인덱스를 사용하는 동등 조건(=) 쿼리, 그리고 마지막 레코드 10이 id=7 조건에 만족하지 않기 때문에 넥스트 키 락은 갭 락으로 강등된다.

그래서 최종 잠금 범위는 (5, 10)이다.

최종 잠금 범위가 (5, 10)이기 때문에 세션 2의 INSERT문은 갭 락으로 인해 Block되며, id=10 조건에 해당하는 레코드를 업데이트 하는 세션 3의 SQL문은 성공한다. 이는 넥스트 키 락이 갭 락으로 강등되어 레코드 10에 걸려있던 잠금이 해제되었기 때문이다.

2) 세컨더리(Non Unique) 인덱스와 동등 조건(=)의 잠금

두 번째 예제는 세션 1에서 t 테이블에 대해 a=5 조건에 해당하는 레코드를 FOR SHARE 모드로 조회하는 것으로 시작한다. FOR SHARE는 다른 세션에서 읽기는 가능하지만 쓰기는 불가능한 명시적 공유 잠금이다. 여기서 한 가지 의아하다고 생각이 드는 것은 세션 2일 것이다. 분명 a=5 조건에 해당하는 레코드에 공유 잠금을 걸었는데 업데이트가 성공했다. 왜 그럴까?

먼저 원칙 1에 따라 기본 잠금 단위는 넥스트 키 락이기 때문에 (0, 5]에 넥스트 키 락이 설정된다. 그런데 ix_a 인덱스는 넌유니크한 세컨더리 인덱스이기 때문에 a=5 조건에 해당하는 레코드만 찾아서 바로 종료하는 것이 아니라 오른쪽으로 계속 스캔하여 레코드 10을 찾을 때까지 이동한다. 이 때 원칙 2가 적용되면서 쿼리를 수행하는 과정에 접근한 모든 객체에 잠금을 걸게 되므로 (5, 10]에 넥스트 키 잠금이 설정된다. 그리고 규칙 1에 따라 레코드 10은 a=5 조건을 만족하지 않기 때문에 넥스트 키 락이 갭 락으로 강등되어 (5, 10)으로 잠금 범위가 변경된다.

그래서 최종 잠금 범위는 (0, 5] (5, 10) 이다.

눈치챘겠지만 사실 세션 1의 쿼리는 커버링 인덱스를 사용한다. 프라이머리 키 인덱스에는 어떠한 잠금도 설정하지 않는다 (for share이기 때문에). 그래서 id=5 조건에 해당하는 레코드를 업데이트 하는 세션 2의 SQL문이 정상적으로 실행되는 것이다. 그리고 세션 3의 VALUES(7, 7, 7)은 갭 락이 걸려있는 (5, 10)에 레코드를 삽입하려고 하기 때문에 Block되는 것이다.

여기서 FOR SHARE 대신 FOR UPDATE를 사용하면, MySQL 서버는 이후 데이터를 업데이트할 것으로 간주하기 때문에 a=5 조건에 해당하는 프라이머리 키 인덱스에 레코드 락을 설정한다. 만일 세션 2에 의해 레코드가 업데이트 되는 것을 원치 않으면 SELECT절에 b 컬럼을 포함시키거나, FOR SHARE 대신 FOR UPDATE로 쿼리가 수행되게끔 만들어야 한다.

3) 프라이머리 키(Primary Key) 인덱스 범위 잠금

세 번째 예제에서는 아래 두 쿼리를 비교해볼 것이다. 두 쿼리를 수행하면 조회 결과와 잠금 범위까지 모든 것이 동일해야할 것 같지만, 실은 조회 결과만 동일하고 잠금 범위는 동일하지 않다.

먼저 왼쪽의 쿼리부터 살펴보도록 하자.
세션 1에서 id=10 조건에 해당하는 레코드를 FOR UPDATE로 조회하는 것으로 시작한다. 원칙 1에 따라 넥스트 키 락이기 때문에 (5, 10]에 넥스트 키 락이 설정된다. 그런데 id는 고유 인덱스(Primary Key Index)이기 때문에 id=10 조건에 해당하는 레코드가 존재하므로 규칙 2에 따라 넥스트 키 락은 레코드 락으로 강등된다. (5, 10] 범위의 넥스트 키 락이 id=10에 해당하는 레코드 락으로 강등되었으므로 아래 세션 2와 세션 3의 SQL문은 Block없이 정상적으로 수행된다.

왼쪽 쿼리의 최종 잠금 범위는 10이다.

이번에는 오른쪽의 쿼리를 살펴보도록 하겠다.

먼저 세션 1에서 id>=10 AND id<11 조건에 해당하는 레코드를 찾는 것으로 시작한다. 사실 id>=10 조건에 사용된 부등호는 부등호(>)와 등호(=)로 분리해서 판단해야 한다. 쿼리는 가장 먼저 id=10인 레코드를 찾는 것부터 시작한다. 이 때 원칙 1에 따라 (5, 10]에 넥스트 키 락이 설정되며, 다시 규칙 2에 따라 고유 인덱스를 사용하는 id=10인 레코드가 존재하므로 넥스트 키 락은 레코드 락으로 강등된다. 이제 다시 부등호 조건(>)을 살펴보자. 범위 검색은 조건을 만족하는지 안하는지 다음 첫 번째 레코드까지 접근해야만 알 수 있기 때문에 오른쪽으로 범위 검색을 계속해서 수행한다. 조건을 만족하는 시점은 id=15에 해당하는 레코드를 찾는 시점이다. 이 때에는 고유 인덱스를 사용하는 id=10인 레코드를 이미 찾았으므로 (10, 15)에 갭 락이 설정된다.

오른쪽 쿼리의 최종 잠금 범위는 10, (10, 15) 이다.

두 쿼리의 결과가 같을지라도 잠금 범위는 다를 수 있다는 것을 꼭 명심하자.

4) 세컨더리 인덱스(Non Unique) 인덱스 범위 잠금

이번에는 예제 3과 동일한 형태의 쿼리이지만 넌유니크한 세컨더리 인덱스로 수행했을 때는 어떠한 차이점(잠금에)이 있는지 살펴보도록 하겠다.

세션 1에서 a>=10 AND a<11 조건에 해당하는 레코드를 찾는 것으로 시작한다. 우선 a=10인 레코드를 찾아야 하므로 원칙 1에 따라 (5, 10]에 넥스트 키 락이 설정된다. a=10 조건을 만족하는 레코드가 존재하지만 ix_a 인덱스는 유니크 인덱스가 아니기 때문에 규칙 2를 적용할 수가 없다. 때문에 동등 조건을 만족하지 않는 다음 레코드까지 범위 검색을 수행하며, a=15에 해당하는 레코드를 찾으면 검색이 중단되고 (10, 15]에 넥스트 키 락이 설정된다. 하지만 지금은 범위 검색에 해당되기 때문에 규칙 1을 적용할 수 없으므로 넥스트 키 락은 갭락으로 강등되지 않는다.

최종 잠금 범위는 (5, 10], (10, 15] 이다.

그래서 예제 3과는 다르게 세션 2의 INSERT문이 Block된 것을 확인할 수 있다.

5) 중복된 행이 존재하는 동등 조건(=)의 잠금

이번에는 살짝 복잡하게 아래와 같이 레코드를 1건 추가하여 동등 조건의 잠금을 살펴보도록 하겠다.

mysql> INSERT INTO t(id, a, b) VALUES(30, 10, 30);

mysql> SELECT * FROM t ORDER BY a;
+----+------+------+
| id | a    | b    |
+----+------+------+
|  0 |    0 |    0 |
|  5 |    5 |    5 |
| 10 |   10 |   10 |
| 30 |   10 |   30 |
| 15 |   15 |   15 |
| 20 |   20 |   20 |
| 25 |   25 |   25 |
+----+------+------+

위의 INSERT문까지 수행하면 ix_a 인덱스의 전체 레코드 구성은 아래 그림과 같다. 레코드와 레코드 사이의 빈 공간은 잠금 범위를 쉽게 파악하기 위해 일부러 넣은 것이다. a=10 조건에 해당하는 레코드 건 수가 2건 이상 중복되어 있는 것을 확인할 수 있는데,

이 경우 잠금 범위는 어떻게 설정되는지 살펴보도록 하겠다.

이번 예제는 세션 1에서 a=10 조건에 해당하는 레코드를 FOR UPDATE로 조회하는 것으로 시작한다. 먼저 a=10 조건에 해당하는 레코드를 찾아야 하므로 원칙 1에 따라 넥스트 키 락은 (5, 10]에 설정된다. 정확히는 (a=5, id=5)부터 (a=10, id=10)까지 넥스트 키 락이 설정된다. 그리고 a=10에 해당하는 레코드가 존재하지만 넌유니크한 세컨더리 인덱스이기 때문에 다음 레코드(a=15)를 찾을 때까지 오른쪽으로 검색을 계속 수행한다. 검색 과정에서 (a=10, id=30)인 레코드에 접근하게 되므로 원칙 1과 원칙 2에 따라 (a=10, id=10)부터 (a=10, id=30)까지 넥스트 키 락이 설정된다. 다시 오른쪽으로 검색을 하다가 (a=15, id=15)인 레코드를 만나면 검색 루프는 종료되고, (a=10, id=30)부터 (a=15, id=15)까지 넥스트 키 락이 설정된다. 하지만 검색된 a=15 레코드는 a=10인 조건에 해당되지 않으므로 최종적으로는 규칙 1에 따라 넥스트 키 락이 갭 락으로 강등된다.

최종 잠금 범위는 ((a=5, id=5), (a=10, id=10)], ((a=10, id=10), (a=10, id=30)], ((a=10, id=30), (a=15, id=15)) 이다.

복잡해보이지만 최종 잠금 범위를 그림으로 나타내면 다음과 같다.

6) LIMIT절에 대한 잠금

이번에는 예제 5에 이어 잠금 범위가 LIMIT절의 존재 여부에 따라서 어떻게 바뀌는지 살펴보도록 하겠다.

이전 예제(예제 5)에서 크게 바뀐 것은 없고, 세션 1의 쿼리에 LIMIT 2가 추가되었다. 먼저 a=10 조건에 해당하는 레코드를 찾아야 하므로 원칙 1에 따라 넥스트 키 락은 (a=5, id=5)부터 (a=10, id=10)까지 설정된다. 그리고 다음 레코드(a=15)를 찾을 때까지 오른쪽으로 검색을 계속 수행한다. 검색 과정에서 (a=10, id=30)인 레코드에 접근하게 되므로 원칙 1과 원칙 2에 따라 (a=10, id=10)부터 (a=10, id=30)까지 넥스트 키 락이 설정된다.
이제 여기서부터가 중요한 부분이다. 검색 루프는 (a=10, id=30) 레코드까지 순회하고 나면 LIMIT 2에 대한 조건을 만족했기 때문에, 즉 레코드 2건을 찾았기 때문에 더이상 검색을 진행하지 않고 종료한다.

이에 따라 ix_a 인덱스에 대한 최종 잠금 범위는 ((a=5, id=5), (a=10, id=10)], ((a=10, id=10), (a=10, id=30)] 가 된다.

아래 그림에서 예제 6의 최종 잠금 범위를 보면 예제 5와 비교했을 때 갭 락이 없어진 것을 확인할 수 있다. 추가로 예제 5에서 갭 락 때문에 Block 되었던 세션 2의 INSERT문은 이제 정상적으로 수행되는 것을 확인할 수 있다.

7) 갭 락 + 레코드 락

본 글의 서두에서 “넥스트 키 락은 갭 락과 레코드 락이 결합된 형태의 잠금 알고리즘이다” 라는 내용을 언급했었다. 이번 예제에서는 이렇게 말한 이유에 대해서 설명을 해보려고 한다.

먼저 세션 1에 의해 ix_a 인덱스의 최종 잠금 범위는 이전 예제들에서 보았듯이 (5, 10], (10, 15) 이다. 세션 2에서는 a=10 조건에 해당하는 레코드를 업데이트 해야되므로 ix_a 인덱스의 (5, 10]에 넥스트 키 락이 설정된다. 그리고 a=10 조건에 해당하는 레코드에 이미 잠금이 걸려있기 때문에 세션 2는 대기 상태(block)에 들어간다. 다시 세션 1에서는 트랜잭션을 커밋/롤백하지 않은채 (8, 8, 8)을 삽입하려고 하는데, 이 때는 세션 2의 (5, 10) 갭 락에 의해 block 되어 버린다. 세션 1은 세션 2가 대기하는 a=10에 해당하는 레코드 락을 해제하지 않은채 세션 2가 해제하지 않은 갭 락을 획득하려 하고, 세션 2는 세션 1이 대기하는 갭 락을 해제하지 않은채 세션 1이 해제하지 않은 레코드 락을 획득하려고 하기 때문에 데드락이 발생하면서 세션 2가 롤백된다.

이 내용을 좀 더 이해하기 쉽도록 그림으로 나타내보았다. 여기서 중요한 것은 세션 2는 세션 1의 넥스트 키 락을 기다리는 것이 아니라 레코드 락을 기다린다는 것이다. 세션 1이 레코드 락을 소유하고 있기 때문에 세션 2는 레코드 락을 누군가가 소유하고 있는지 확인 후 소유하고 있다면 갭 락만을 요청하여 잠금을 획득한다.

결국 “넥스트 키 락은 갭 락과 레코드 락이 결합된 형태의 잠금 알고리즘이다”의 의미는 사용자 눈에 보이는 잠금 상태는 넥스트 키 락일지언정 내부적으로는 갭 락과 레코드 락으로 분할(두 단계)되어 진행된다는 의미이다.

8) ORDER BY DESC 잠금

마지막은 재미있는 잠금 예제이다.

먼저 아래 그림을 살펴보도록 하자. 세션 1을 수행했을 때 ix_a 인덱스에 걸리게 되는 잠금 범위이다.

ORDER BY절에 Descending 정렬만 추가했을 뿐인데 왜 이렇게 많은 범위에 걸쳐서 잠금이 발생하는 것일까?

세션 1의 쿼리는 DESC 정렬이기 때문에 쿼리의 시작 지점은 a<=20 부터 시작한다. 먼저 a=20 조건에 따라서 (15, 20]와 (20, 25]에 원칙 1이 적용되며 넥스트 키 락이 설정된다. 레코드 25는 a=20 조건에 해당되지 않기 때문에 규칙 1에 따라 넥스트 키 락이 (20, 25) 갭 락으로 강등된다. 이어서 범위 검색에 따라 왼쪽으로 이동하면서 레코드 15를 찾게 되고, (10, 15]에 넥스트 키 락이 설정된다. 여기서 다시 레코드 10까지 확인해야만 조건을 만족하는지 알 수 있기 때문에 왼쪽으로 이동하면서 레코드 10을 찾게 되고, ((a=5, id=5), (a=10, id=10)]과 ((a=10, id=10), (a=10, id=30)]에 넥스트 키 락이 설정된다.

최종 잠금 범위는 (20, 25), (15, 20], (10, 15], ((a=10, id=10), (a=10, id=30)], ((a=5, id=5), (a=10, id=10)] 이다.

앞으로 잠금이 발생할 때마다 InnoDB 잠금의 2원2규칙으로 분석을 시작해보자.

Reference

• https://patentimages.storage.googleapis.com/84/2e/69/c7cb03f2c94287/US7174331.pdf
• https://github.com/mysql/mysql-server/blob/8.4/storage/innobase/lock/lock0lock.cc