Concurrency Control

Concurrency Control은 DBMS에서 특정 데이터에 대한 동시 접근을 제어하는 것을 의미합니다. Concurrency Control은 Multi-version Concurrency Control (MVCC), Strict Two-phase Locking (S2PL), Optimistic Concurrency Control (OCC) 등 여러 방식으로 이루어집니다. PostgreSQL은 MVCC 방식을 활용하여 Concurrency Control을 수행하고 있습니다.

MVCC는 각 데이터를 각 시점에 따라 여러 버전으로 관리하는 방식입니다. 따라서, 사용자에게 보여지는 데이터는 1개로 보여지지만 실제로 해당 데이터는 여러 버전의 데이터(레코드)로 관리되고 있습니다.

이번 장에서는 PostgreSQL에서 MVCC를 구현하는 방법을 설명하고 이를 기반으로 Isolation Level, Lost Update 등 DBMS에서 정의하는 Concurrency 이슈들이 실제로 어떻게 다루어지고 있는지 확인해볼 것입니다.

Reference. Bernstein, Philip A., and Nathan Goodman. “Concurrency control in distributed database systems.” ACM Computing Surveys (CSUR) 13.2 (1981): 185-221.

Transaction ID

대다수의 데이터베이스는 트랜잭션을 관리하고 있고 이를 위하여 트랜잭션 아이디라는 개념을 사용하고 있습니다. PostgreSQL도 예외 없이 트랜잭션 아이디를 사용하고 있습니다. 본 문단에서는 PostgreSQL에서 트랜잭션 아이디를 관리하는 구조에 대하여 설명하겠습니다.

PostgreSQL은 32-bit unsigned integer(1 ~ 2^32 -1)로 표현되어 약 42억 개의 트랜잭션 아이디를 가질 수 있고 1부터 시작하여 새로운 트랜잭션이 시작될 때 증가합니다(0은 invalid tx_id로 예약되어 있습니다). PostgreSQL은 이를 원형(Circular) 형태로 관리하고 있습니다.

눈치가 빠르다면 이 구조에서 다음과 같은 의문점을 가질 수 있습니다. “트랜잭션 아이디를 다 쓰고 한바퀴 돌면 어떡하지?” 이 개념은 Vacuum에서 설명할 것 입니다. 그때까지 이 의문을 마음에 품고 있길 바랍니다.

Tuple

관계형 데이터베이스를 최초로 고안한 에드거 F. 커드는 Relation은 튜플(Tuple)들의 집합이라고 정의하였습니다. 일반적인 데이터베이스에서는 주로 Relation은 테이블(Table), 튜플은 행(Row)의 형태로 표현됩니다. 그리고 파일 시스템의 관점에서는 Relation은 파일, 튜플은 그 안에 기록된 레코드(Record)들에 대응합니다.

후술할 내용을 원활하게 이해하기 위해서는 우리가 원론적인 정의를 하는 이유에 대해 이해하고 넘어갈 필요가 있습니다. 왜냐하면 우리가 다룰 Concurrency Control은 우리가 익숙한 개념인 테이블과 행과 같은 데이터베이스 관점이 아닌 파일 시스템의 관점에서 이루어지기 때문입니다. (위 개념은 필수적으로 이해야하는 후술할 내용들의 기본 전제입니다. 이 문장이 이해되지 않는다면 Concurrency Control 항목을 다시 한번 읽는 것을 추천합니다.)

Reference. Codd, Edgar F. “A relational model of data for large shared data banks.” Communications of the ACM 13.6 (1970): 377-387.

PostgreSQL에서는 Relation은 테이블, 인덱스, 시퀀스 등을 포함하는 개념으로 정의합니다. 따라서, 튜플 역시 해당 튜플이 포함된 Relation에 따라 Heap Tuple, Index Tuple 등으로 나뉘어집니다. PostgreSQL에서 튜플은 데이터의 레코드를 의미하며, 데이터에 변경(INSERT, UPDATE, DELETE)이 발생할 때 새로 생성되거나 내용이 변경됩니다.

Reference. https://www.postgresql.org/docs/current/catalog-pg-class.html

본문에서는 테이블을 기준으로 Concurrency Control에 대한 설명을 진행할 것이며, 이에 따라 힙 튜플을 기준으로 설명을 진행하겠습니다.

PostgreSQL 힙 튜플을 표현하는 구조체인 HeapTupleData는 다음과 같이 정의되어 있습니다. 이번 장에서는 후술할 내용을 이해하는데 필요한 값에 대해서만 세부적인 설명을 진행하겠습니다.

• HeapTupleData Struct
  • t_len
  • t_self
  • t_tableOid
  • t_data
    • t_heap
      • t_xmin: 튜플이 INSERT 될 때의 트랜잭션 아이디
      • t_xmax: 튜플이 DELETE 되거나 LOCKING 될때의 트랜잭션 아이디
      • t_cid: 튜플의 INSERT, DELETE에 대한 트랜잭션 내 COMMAND ID (0부터 증가합니다.)
      • t_xvac
    • t_datum
      • datum_len_
      • datum_typmod
      • datum_typeid
    • t_ctid: 현재 튜플(자기 자신)의 트랜잭션 아이디 혹은 새로운 튜플(다음 레코드)의 트랜잭션 아이디
    • t_infomask2
    • t_infomask
    • t_hoff
    • t_bits

이중 우리는 다음 4가지 값을 사용하여 Concurrency Control을 설명할 것입니다.

• t_xmin: 튜플이 INSERT 될 때의 트랜잭션 아이디
• t_xmax: 튜플이 DELETE 되거나 LOCKING 될때의 트랜잭션 아이디
• t_cid: 튜플의 INSERT, DELETE에 대한 트랜잭션 내 COMMAND ID (0부터 증가합니다.)
• t_ctid: 현재 튜플(자기 자신)의 트랜잭션 아이디 혹은 새로운 튜플(다음 레코드)의 트랜잭션 아이디

Reference. https://github.com/postgres/postgres/blob/master/src/include/access/htup.h https://github.com/postgres/postgres/blob/master/src/include/access/htup_details.h https://www.postgresql.org/docs/current/ddl-system-columns.html

Operation

본 문단에서는 각 쿼리가 수행될 때 튜플이 어떻게 추가되고 바뀌는지에 대한 설명을 진행하겠습니다. 일단 쿼리의 INSERT, UPDATE, DELETE와 튜플에 대한 INSERT, DELETE를 구분해서 이해해야 합니다. 본 문단에서는 이를 위해 튜플에 대한 INSERT, DELETE를 각각 T_INSERT, T_DELETE로 명시하겠습니다.

쿼리에 의해 INSERT, UPDATE, DELETE가 발생하였을 때, 튜플에 대한 동작은 다음과 같이 정리할 수 있습니다.

• INSERT: 새로운 데이터에 대한 T_INSERT를 수행합니다.
• UPDATE: 갱신된 데이터에 대한 T_INSERT를 수행하고 기존 튜플에 대한 T_DELETE를 수행합니다.
• DELETE: T_DELETE를 수행합니다.

T_INSERT 동작의 특징은 t_xmax = 0으로 설정된다는것 입니다.

T_DELETE 동작은 t_xmax 값을 0에서 현재 트랜잭션 아이디로 변경함으로서 수행됩니다(실제로 튜플을 삭제하지 않는다는 사실에 유의합시다). T_DELETE 동작은 UPDATE, DELETE에 따라 동작이 구분되는데 UPDATE가 발생했을 경우에는 다음 버전의 튜플(레코드)가 생겼다는 의미이므로 t_ctid가 자기 자신이 아닌 다음 레코드에 해당하는 튜플을 가리키게 됩니다. DELETE의 경우에는 다음 버전의 튜플이 존재하지 않으므로 t_ctid가 자기 자신을 가리키게 됩니다.

Insert

다음 코드와 표는 각각 하나의 INSERT를 포함하는 트랜잭션과 해당 트랜잭션이 완료된 후의 튜플의 상태입니다.

# txid = 100
BEGIN;
INSERT INTO example_table VALUES(‘A’); — COMMAND 0
COMMIT;

1	100	0	0	(0, 1)	‘A’

COMMAND 0은 트랜잭션 아이디가 100일 때 수행되어 1번 튜플이 T_INSERT 되었으므로 t_xmin = 100입니다.

위 시나리오에서 1번 튜플은 T_DELETE 되지 않았으므로 t_xmax = 0 입니다.

해당 트랜잭션에서 1번 튜플은 첫번째 COMMAND이다. Command ID는 0부터 시작하므로 t_cid = 0입니다.

해당 트랜잭션에서 새로 생성된 ‘A’를 담고 있는 ROW는 위 시나리오에서 변경된 적이 없으므로 1번 튜플의 t_ctid는 자기 자신을 지칭하게 됩니다. (0, 1)의 의미는 0번 페이지의 Offset = 1에 해당 튜플이 위치한다는 의미입니다.

Update

# txid = 105
BEGIN;
UPDATE example_table SET data = ‘B’ WHERE …; — COMMAND 0
UPDATE example_table SET data = ‘C’ WHERE …; — COMMAND 1
COMMIT;

다음 표는 COMMAND 0이 수행된 이후의 튜플의 상태입니다.

no	t_xmin	t_xmax	t_cid	t_ctid	data
1	100	105	0	(0, 2)	‘A’
2	105	0	0	(0, 2)	‘B’

no	t_xmin	t_xmax	t_cid	t_ctid	data
1	100	105	0	(0, 2)	‘A’
2	105	105	0	(1, 1)	‘B’
3	105	0	1	(1, 1)	‘C’

Delete

# txid = 111
BEGIN;
DELETE FROM example_table WHERE …; — COMMAND 0
COMMIT;

no	t_xmin	t_xmax	t_cid	t_ctid	data
1	100	105	0	(0, 2)	‘A’
2	105	105	0	(1, 1)	‘B’
3	105	111	1	(1, 1)	‘C’

Commit Log

PostgreSQL은 각 트랜잭션의 상태를 Commit Log에 기록합니다. Clog는 트랜잭션 수행 중, 공유 메모리에 할당되어 사용됩니다.

PostgreSQL에서는 트랜잭션의 상태를 IN_PROGRESS, COMMITTED, ABORTED, SUB_COMMITTED로 구분합니다. 본 문서에서는 Sub-Transaction의 상태를 나타내는 SUB_COMMITTED 상태에 대해서는 설명하지 않겠습니다.

IN_PROGRESS는 현재 수행중인 트랜잭션입니다. 여기서 생성된 튜플은 자기 자신에게는 보이지만 다른 트랜잭션에는 보이지 않아야합니다. COMMITTED는 커밋이 완료된 트랜잭션입니다. 해당 트랜잭션은 이미 종료되었고 여기서 생성된 튜플은 다른 트랜잭션에도 보여야 합니다. ABORTED는 중단된 트랜잭션이다. 해당 트랜잭션은 종료되었으나, 중단되었으므로 다른 트랜잭션에 보여서는 안됩니다.

Transaction Snapshot

트랜잭션 스냅샷은 특정 시점의 각 트랜잭션에 대한 Active 여부를 기록한다. PostgreSQL에서는 트랜잭션이 IN_PROGRESS 상태이거나 아직 시작하지 않은 트랜잭션을 Active라고 정의합니다.

트랜잭션 스냅샷은 txid_current_snapshot()을 통해 조회할 수 있습니다. 트랜잭션 스냅샷은 다음과 같이 표현됩니다.

SELECT txid_current_snapshot();
— xmin:xmax:xip_list
— 100:108:100,101,106

트랜잭션 스냅샷의 구성 요소는 다음과 같습니다.

• xmin: 활성 상태인 트랜잭션 중 가장 오래된(트랜잭션 아이디가 낮은) 트랜잭션의 아이디
• xmax: 아직 할당되지 않은 트랜잭션 중 가장 오래된(첫번째) 트랜잭션의 아이디
• xip_list: 스냅샷 시점의 활성된 트랜잭션의 아이디의 리스트

Reference. https://www.postgresql.org/docs/current/functions-info.html

Visibility

PostgreSQL는 트랜잭션 격리(Isolation)를 위해 특정 트랜잭션 수행 시, 어떤 튜플이 보여지고 안 보여질지를 결정해야합니다. 이는 Visibility(가시성)라는 개념으로 구현됩니다. Visibility는 각 트랜잭션에서 특정 튜플의 가시성을 의미하며 Visibility Rule에 의해 결정됩니다. 내부적으로는 수 많은 규칙이 존재하지만 본 문서에서는 보편적인 다음 11가지 규칙에 대해서만 설명하겠습니다.

그냥 봅시다.

Rule #	status (t_xmin)	status (t_xmax)	value (t_xmin)	value (t_xmax)	snapshot (t_xmin)	snapshot (t_xmax)	visibility
1	ABORTED						X
2	IN_PROGRESS		CURRENT	ZERO			O
3	IN_PROGRESS		CURRENT	NON-ZERO			X
4	IN_PROGRESS		OTHER				X
5	COMMITTED				ACTIVE		X
6	COMMITTED	ABORTED					O
7	COMMITTED			ZERO			O
8	COMMITTED	IN_PROGRESS		CURRENT			X
9	COMMITTED	IN_PROGRESS		NON-ZERO			O
10	COMMITTED	COMMITTED				ACTIVE	O
11	COMMITTED	COMMITTED				IN-ACTIVE	X

숲을 봅시다.

• Rule 1 : 튜플을 생성한(T_INSERT) 트랜잭션(t_xmin)은 ABORTED되었습니다. 해당 트랜잭션 자체가 중단되었다는 의미이므로 All or Nothing의 Nothing입니다. 따라서, 해당 튜플은 보여지지 않습니다.
• Rule 2,3,4 : 튜플을 생성한 트랜잭션이 아직 IN_PROGRESS 상태입니다. 해당 트랜잭션이 커밋되지 않았다는 의미이므로 해당 튜플을 생성한 트랜잭션에서만 보여집니다. 또한 해당 튜플이 UPDATE, DELETE에 의해 T_DELETE 되었을 때에는 같은 트랜잭션에서도 보여지지 않습니다.
• Rule 5,6,7,8,9,10,11 : 튜플을 생성한 트랜잭션이 COMMITTED 상태입니다. 즉, 해당 트랜잭션이 커밋 된 이후에 생성된 트랜잭션에서는 해당 튜플이 보여져야합니다. 단, 위와 마찬가지로 또한 해당 튜플이 UPDATE, DELETE에 의해 T_DELETE 되었을 때에는 보여지지 않습니다.

나무를 봅시다.

• Rule 1은 “Status(t_xmin) = ABORTED” 입니다. 즉, 해당 튜플을 생성한 트랜잭션이 중단되었다는 의미입니다. 트랜잭션은 원자성에 의해 All or Nothing입니다. 중단된 트랜잭션의 튜플은 반영되지 않아야하므로 현재 트랜잭션에서 해당 튜플은 볼 수 없어야합니다. 즉, Invisible 입니다.
• Rule 2는 “Status(t_xmin) = IN_PROGRESS”. 해당 튜플을 생성한 트랜잭션이 아직 수행 중이라는 의미입니다. 즉, 아직 커밋되지도 않았습니다. 따라서, 해당 튜플을 생성한 트랜잭션에서만 볼 수 있어야합니다. “t_xmin = current_txid” 즉, 해당 튜플은 현재 트랜잭션에서 생성되었다는 의미입니다. 마지막으로 T_DELETE되었는지만 살펴보겠습니다. t_xmax = 0 입니다. 우리는 상술한 Operation 문단에서 t_xmax가 0일 경우에는 T_DELETE되지 않았다는 사실을 언급 하였습니다. 따라서, Rule 2에 해당하는 튜플은 Visible입니다.
• Rule 3는 Rule 2와 달리 t_xmax ≠ 0 이므로 해당 튜플은 이미 T_DELETE 되었음을 알 수 있습니다. UPDATE로 인해 다음 버전의 튜플이 존재하거나 삭제되었다는 것을 의미합니다. 따라서, Rule 3에 해당하는 튜플은 Invisible입니다.
• Rule 4에 해당하는 튜플은 아직 IN_PROGRESS 상태이니 커밋되지 않았습니다. 즉, 다른 트랜잭션에서는 보여지지 않아야합니다. “t_xmin ≠ current_txid”에 의해 해당 튜플은 현재 트랜잭션과 다른 트랜잭션에서 생성되었습니다. 따라서, Rule 4에 해당하는 튜플은 Invisible입니다.
• Rule 5는 조금 이상합니다. 위에서 분명 IN_PROGRESS 이거나 할당되지 않은 트랜잭션이 Active라고 했는데, Rule 5는 COMMITTED 상태임에도 Active라고 하고 있습니다. 이는 간략하게 설명하자면 다른 Isolation Level(후술하겠습니다)을 가진 세션에서 대상 튜플을 생성한 트랜잭션이 커밋되지 않은 상태에서 스냅샷 생성하여 발생한 일입니다. 결론적으로 PostgreSQL은 Active를 우선으로 하여 해당 트랜잭션을 IN_PROGRESS로 간주합니다. 따라서, Rule 5에 해당하는 튜플은 Invisible입니다.
• Rule 6에 해당하는 튜플을 생성한 트랜잭션은 “If Status(t_xmin) = COMMITTED” 즉, 커밋되었습니다. 그리고, “Status(t_xmax) = ABORTED” 해제하면 T_DELETE를 수행한 트랜잭션이 Abort 되었습니다. 즉, 해당 튜플은 생성 이후 T_DELETE를 했지만 해당 동작이 취소되었습니다. 따라서, Rule 6에 해당하는 튜플은 Visible입니다.
• Rule 7에 해당하는 튜플을 생성한 트랜잭션은 “If Status(t_xmin) = COMMITTED” 즉, 커밋되었습니다. 그리고, t_xmax가 0이므로 생성 이후 T_DELETE 되지 않았습니다. 즉, 해당 튜플은 생성 이후 T_DELETE하지 않았습니다. 따라서, Rule 7에 해당하는 튜플은 Visible입니다.
• Rule 8에 해당하는 튜플은 “If Status(t_xmin) = COMMITTED ∧ Status(t_xmax) = IN_PROGRESS” 즉, 해당 튜플을 생성한 트랜잭션은 커밋되었고, 해당 튜플을 UPDATE 또는 DELETE를 통해 T_DELETE한 트랜잭션은 아직 커밋되지 않았습니다. 따라서, 해당 튜플은T_DELETE를 수행한 트랜잭션에서만 보여지지 않고(아직 T_DELETE가 COMMIT이 안되었으므로), 다른 트랜잭션에서는 보여져야합니다(해당 튜플을 생성한 T_INSERT는 COMMIT되었으므로). Rule 7은 “t_xmax = current_txid”, 즉 현재 트랜잭션이 T_DELETE를 수행하였습니다. 따라서, Rule 7에 해당하는 튜플은 Invisible입니다.
• Rule 9에 해당하는 튜플은 Rule 7과 달리 “t_xmax ≠ current_txid AND t_xmax ≠ 0” 즉, T_DELETE를 수행한 트랜잭션이 아닙니다. 따라서, Rule 8에 해당하는 튜플을 Visible입니다.
• Rule 10에 해당하는 튜플은 “If Status(t_xmin) = COMMITTED” 즉, 생성한 트랜잭션은 커밋되었습니다. 그리고, “Status(t_xmax) = COMMITTED ∧ Snapshot(t_xmax) = active” 해당 튜플을 T_DELETE한 트랜잭션은 커밋되었으나 아직 Active입니다. 우리는 Rule 5에서 조금 이상한 상황에 대해 이미 설명하였습니다. Active 상태가 우선되므로 IN_PROGRESS로 간주하므로 아직 T_DELETE가 반영되지 않았습니다. 따라서, Rule 9에 해당하는 튜플은 Visible 입니다.
• Rule 11에 해당하는 튜플은 Rule 9와 달리 “Snapshot(t_xmax) ≠ active” 입니다. 따라서, T_DELETE가 반영되었습니다. 따라서, Rule 10에 해당하는 튜플은 Invisible 입니다.

Isolation Level

Isolation Level은 트랜잭션의 격리 수준으로 ANSI SQL-92에서 발생하는 현상에 따라 정의한 개념입니다.

ANSI SQL-92 MS, ANSI] defines Isolation Levels in terms of phenomena.

Reference. Berenson, Hal, et al. “A critique of ANSI SQL isolation levels.” ACM SIGMOD Record  24.2 (1995): 1-10.

SQL-92에서는 다음 3가지 현상을 기반으로 트랜잭션 격리 수준을 정의하였습니다.

• Dirty Read

1. 트랜잭션 T1이 특정 데이터 A를 B로 수정
2. 트랜잭션 T2가 변경된 데이터 B를 조회
3. 트랜잭션 T1이 롤백(Rollback)을 수행 ⇒ 롤백이 수행되어 커밋된 적이 없어 존재한 적이 없는 데이터 B를 T2가 조회

• Non-repeatable Read

1. 트랜잭션 T1이 특정 데이터 A를 조회
2. 트랜잭션 T2가 데이터 A를 B로 수정(또는 삭제)하고 커밋
3. 트랜잭션 T1이 해당 데이터를 다시 조회하면 **B(또는 해당 데이터가 없다는 결과)**을 조회 ⇒ 같은 트랜잭션 T1에서 같은 데이터에 대해 다른 결과를 조회

• Phantom Read

1. 트랜잭션 T1이 특정 쿼리로 READ하여 SET1을 결과로 조회
2. 트랜잭션 T2가 해당 쿼리 조건을 만족하는 데이터 A를 추가
3. 트랜잭션 T1이 해당 쿼리로 다시 READ하여 A가 포함된 SET2를 결과 조회 ⇒ 같은 트랜잭션 T1에서 같은 쿼리로 조회한 결과인 SET1과 SET2가 불일치

SQL-92에서는 위에서 언급한 3가지 현상의 발생 여부를 기준으로 4단계의 트랜잭션 격리 수준을 정의하였습니다. 각 단계는 다음과 같습니다.

Isolation Level	Dirty Read	Non-repeatable Read	Phantom Read
Read uncommitted	Possible	Possible	Possible
Read committed	Not possible	Possible	Possible
Repeatable read	Not possible	Not possible	Possible
Serializable	Not possible	Not possible	Not possible

PostgreSQL에서 정의하는 트랜잭션 격리 수준은 다음 표와 같습니다.

Isolation Level	Dirty Read	Non-repeatable Read	Phantom Read	Serialization Anomaly
Read uncommitted	Allowed, but not in PG	Possible	Possible	Possible
Read committed	Not possible	Possible	Possible	Possible
Repeatable read	Not possible	Not possible	Allowed, but not in PG	Possible
Serializable	Not possible	Not possible	Not possible	Not possible

Lost Update (Write-Write Conflict)

Lost Update 현상은 두 개의 트랜잭션에서 동시에 UPDATE를 수행할 경우 첫번째 트랜잭션의 UPDATE가 누락되는 현상으로 위에서 인용했던 “A critique of ANSI SQL isolation levels”에서 언급하고 있습니다.

Reference. Berenson, Hal, et al. “A critique of ANSI SQL isolation levels.” ACM SIGMOD Record  24.2 (1995): 1-10.

PostgreSQL에서는 Repeatable Read와 Serializable 수준에서 Lost Update 현상을 방지하기 위해 다음과 같이 동작합니다.

• 트랜잭션 T2에서 UPDATE 할 대상 데이터가 트랜잭션 T1에 의해 UPDATE가 진행 중이면 T1이 종료될 때까지 기다립니다.
• 만약 해당 트랜잭션이 커밋되었다면,
  • REPEATABLE READ, SERIALIZABLE이면 T2를 Abort 합니다.
  • READ COMMITTED이면 UPDATE를 수행합니다.

Repeatable Read, Serializable 수준에서는 두번째 트랜잭션을 아예 Abort 해버리기 때문에 첫번째 트랜잭션의 UPDATE가 누락되는 현상이 발생하지 않습니다.

지금까지 PostgreSQL의 Concurrency Control에 관해 알아보았습니다

‘PostgreSQL의 Vacuum’를 바로 이어서 확인해보세요!