InnoDB와 PostgreSQL의 MVCC

• https://www.enterprisedb.com/ko/blog/well-known-databases-use-different-approaches-mvcc 게시물의 번역본 입니다. 모든 사진 자료들은 원 게시물에서 가져왔습니다. (All contents are from original article)
• 부가설명이나 제 견해는 주석과 이탤릭체로 달아두었습니다.

들어가기 전에

• scalability는 DBMS가 달성해야하는 가장 중요한 목표이고, 그러려면 contention(혹은 locking)을 가능한 한 최소화해야 한다.

여기서 scalability란, 현재 잘 사용하고 있는 DBMS가 과연 multi-core 환경에서도 동시성을 보장하면서 잘 작동할 수 있는가에 대한 이슈 입니다.

• READ, WRITE, UPDATE, DELETE 같은 빈번한 DML operation (select는 read lock 잡을 경우 DML)들은 블락 당하지 않고 동시성을 보장 받아야 한다.
• Multi-Version Concurrency Control은 contention을 가장 효과적으로 낮출 수 있는 기법이므로 대부분의 DBMS들이 채택하고 있다.

MVCC는 무엇인가

• MVCC란 하나의 logical object에 대해서 여러개의 physical한 version이 존재하는 기법.

MVCC에 대해서는 따로 포스팅으로 정리해 두었습니다.

• 기본 가정은 READ와 WRITE는 충돌하지 않는 것.
• WRITE: UPDATE와 DELETE를 의미한다. (INSERT는 isolation level에 따라서 snapshot을 읽어오냐 마냐에 따라 알아서 필터링. 여기 읽어보기)
• 각 write는 오브젝트의 새로운 버전을 만들어낸다.
• READ: 각 read는 isolation level에 따라서 다른 버전을 읽어온다.

→ read랑 write가 각각 다른 버전에 대해서 작동하기 때문에, lock을 잡을 필요가 없어지고, 동시성을 보장할 수 있다. 다만, 같은 레코드에 대한 write-write 충돌은 발생할 수 있다.

• 여러 DBMS들이 MVCC를 채택하고 있고, 각 구현 방식의 차이점은 버전의 생성과 관리 방법에만 있다. 대표적인 분류가 아래 두 가지 이다.
• PostgreSQL와 Firebird/Interbase
• InnoDB와 Oracle

PostgreSQL의 MVCC

• postgreSQL에서는 버전 단위에 대한 용어가 Tuple. 각 tuple에 대해 추가적인 field를 운용한다.
• xmin - TID는 튜플을 insert하거나 update한 트랜잭션의 ID. UPDATE의 경우 튜플의 새로운 버전은 xmin을 TID로 할당한다.
• xmax - TID는 튜플을 delete하거나 update한 트랜잭션의 ID. UPDATE의 경우 기존 버전의 xmax을 TID로 할당한다. 새로 만들어진 튜플의 경우 xmax는 null이 기본 값.

형태만 다를 뿐, 이전 포스팅에서 정리한 MVCC의 메타 데이터인 begin-ts, end-ts와 동일한 개념이다.

• PostgreSQL은 모든 데이터를 HEAP이라는 하나의 공간에 저장 (page 크기는 8KB가 디폴트).
• 새로운 버전이 만들어지면 older version → new version의 링크가 생긴다.
• older version은 롤백시 튜플을 다시 만들 때 사용되거나, read 동작 시 isolation level에 따라 예전 버전을 읽어올 때 사용될 수 있다.
• 즉, 옛날 버전이나 최근 버전이나 같은 공간에 저장됨! 이게 InnoDB에서의 MVCC와 가장 큰 차이점이 될 수 있다.

PostgreSQL MVCC 예시

• 두 개의 튜플이 있다고 가정.
• T1 (value 1)
• T2 (value 2)

Step 1

• 튜플 T1, T2가 존재하고, 각각 column value는 1과 2.

From Original Article

Step 2 (T2 update)

• 같은 저장 공간에서 뒤에 append된다.
• T2' (older version)의 xmax, T2n(new version)의 xmin을 TID로 할당하고, older version이 new version을 가리키게 된다. (화살표가 좀 이상한데, 두번째가 세번째를 가리키는거)

From Original Article

Step 3 (T1 delete)

• row T1은 virtually 삭제됨. 즉, xmax 값을 TID로 할당한다.

• 다음으로는 INSERT, UPDATE, DELETE에서 어떤식으로 버전 관리가 되는지를 살펴봄.
• 모든 예시는 READ COMMITTED isolation level에서 진행됨.

INSERT

• 레코드를 insert 할 때마다, 새로운 tuple을 만들 것이고, 이건 해당 table에 대응되는 페이지들 중 하나에 추가될 것임.

<시나리오>

1. Session-A 시작. TID 495.
2. Session-B 시작. TID 496.
3. Session-A insert. (HEAP에 저장)
4. xmin = 495인 새로운 튜플 추가.
5. 다만, 커밋되지 않았기 때문에 Session-B에서는 visible하지 않음.
6. Session-A 커밋
7. 두 세션 모두에서 볼 수 있다.

UPDATE

• PostgreSQL에서의 update는 'in-place' update가 아님. 즉, 기존의 내용을 바꾸는게 아니라, INSERT 처럼 새로운 버전을 만들어낸다.
• UPDATE를 진행하는 과정

1. 현재 버전 delete로 표시 (virtually deleted)
2. 새로운 버전 추가하기
3. old 버전을 새로운 버전으로 redirect.

• 따라서, UPDATE가 일어날 때 레코드의 수는 그대로 유지되지만, HEAP에는 계속해서 공간을 차지하게 된다.

<시나리오>

1. Session-A 시작. TID 497.
2. Session-B 시작. TID 498.
3. Session-A가 기존의 레코드 update.

• 기존 버전의 xmax는 497이 된다.

4. Session-A는 update된 버전을 볼 수 있지만, Session-B의 경우는 xmax = 497인 옛날 버전 밖에 볼 수 없다. 두 버전 모두 HEAP에 저장 된다. (같은 페이지일지는 상황에 따라 다름)

5. Session-A 커밋. 옛날 버전은 만료된다.

6. 이제 두 세션 모두 같은 버전을 보고 있음.

DELETE

• 새로운 버전을 추가하지 않는것 외에는 UPDATE랑 비슷함.
• InnoDB에서와 비슷하게, 현재 버전을 DELETED 표시함.

<시나리오>

1. Session-A 시작. TID 499.
2. Session-B 시작. TID 500.
3. Session-A가 기존의 레코드 delete.

• 기존 버전의 xmax는 499가 된다.

4. Session-A는 아무것도 못보고, Session-B는 xmax가 499인 버전을 보게 된다. (아직 커밋하기 전이므로 delete mark된 버전을 보게 됨)

5. Session-A 커밋. 옛날 버전은 만료된다.

6. 이제 두 세션 모두 지워진 버전을 못 보게 된다.

정리

• 그 어떤 쿼리도 바로 레코드를 지우지는 않고, 필요할 경우 새로운 버전을 추가하기는 한다.

나중에 Garbage Collection시, 필요없는 버전은 수거해간다.

• 그럼 SELECT 쿼리의 경우 multiple 버전이 있는 튜플에서 어떻게 작동할까?
• SELECT는 isolation level에 따라 읽을 수 있는 버전을 찾을 때까지 모든 버전을 봐야함.
• 예를 들어 튜플 T1이 있고, 업데이트해서 새로운 버전인 T1'을 만들고, T2"를 마지막으로 update해서 만들었다고 치자.

1. SELECT는 일단 해당 테이블의 heap 공간으로 가서 T1을 본다. xmax가 committed인 경우, 이 튜플의 다음 버전으로 이동한다.
2. T1'의 xmax 역시 committed면, 다음 버전으로 또 이동한다.
3. 마지막으로 xmax가 uncommitted (null)이고, 현재 트랜잭션의 isolation level에서 xmin이 visible한 T1" 버전을 찾게 되면, 읽어온다.

• visible한 버전을 찾기 위해서 세 버전 (T1, T1', T1")모두 한번씩 둘러봐야함.
• 물론, garbage collector가 만료된 튜플을 없애면 (VACUUM) 안봐도 되겠지만, 그 전까지는 다 둘러봐야함.

InnoDB의 MVCC

• PostgreSQL이 xmin과 xmax를 가지고 있듯이, InnoDB도 multi verison을 관리하기 위해서 각 row마다 추가적인 field를 가지고 있다.
• DB_TRX_ID: 해당 row를 insert 하거나 update한 트랜잭션 ID

이전 포스팅에서 정리한, Exclusive Lock을 나타내는 txn-id 필드

• DB_ROLL_PTR: roll pointer로, 롤백 세그먼트에 쓰여진 undo log record를 가리킨다.

추후 MVCC Deep Internal 분석에서 다룰 내용이다. InnoDB는 내부적으로 따로 undo tablespace를 운용하고 있으며, 이전 버전을 여기에 저장하고, 최신 버전이 pointer로 가리키고 있는 방식이다.

• PostgreSQL처럼 한 row에 여러 버전을 만드는건 같은데, old version을 담고 있는 저장 공간은 살짝 다르다.
• InnoDB에선, 변경된 row의 옛날 버전은 분리된 tablespace/storage에 저장된다. (언두 세그먼트)
• PostgreSQL이랑은 다르게, InnoDB는 row의 가장 최근 버전만 main storage에 저장하고, old version은 undo segment에 저장 해둔다.
• Undo segment의 row version들은 rollback 발생 시 undo 수행 때 사용되기도 하고, READ문 수행 시 isolation level에 따라서 옛날 버전을 읽어올 때 사용되기도 한다. (visible한 버전을 찾으러 돌아 다녀야 하기 때문)

예시

• 두 row, T1(1), T2(2)가 있다 치면, 새로운 row 생성은 아래 과정을 거친다.

Step 1

• 처음에 두 row(value 1이랑 2)가 존재한다. 물론 main storage에 있음!

Step 2

• T2 값을 3으로 업데이트. 새로운 버전이 만들어지고, 옛날 버전은 undo segment로 옮겨진다. (기본적으로 undo, rollback은 동의어라고 보면 된다. 짜피 하는일은 같으니까)
• 앞서 언급했던 roll pointer는 새로운 버전에서 rollback segment에 있는 옛날 버전을 가리킨다. * 이거 또 그림 이상한데, T2가 T2U를 가리키는거.
• 따라서, InnoDB에서의 UPDATE는 "IN-PLACE"임.

Step 3

• 비슷하게, main storage에서 T1을 delete한다고 생각. 동일하게 virturally deleted된다 (delete bit만 mark하는거)
• 대응되는 새 버전이 undo segment에 추가되고, roll pointer는 이를 가리키게 된다.

→ PostgreSQL과 InnoDB는 외부에서 봤을때 작동방식은 모두 같음. 다만, storage를 어떤식으로 관리하는지에 대한 내부적인 방법만 다름.

MVCC: PostgreSQL vs InnoDB

• 지금까지는 undo storage의 유무에 대해서 살펴 봤는데, 이제는 MVCC 구현에서의 가장 큰 차이점에 대해 알아보기.

1. older version의 크기

PostgreSQL

• old version의 xmax값만 바꾸기 때문에, 모든 옛날 버전들과 새로 삽입된 레코드의 크기는 동일함.

InnoDB

• Undo 세그먼트에 저장되는 old version들은 변경된 ‘값’만 저장해두기 때문에, 삽입된 레코드에 비해 상대적으로 크기가 작다.

2. INSERT 작동

PostgreSQL

• UPDATE의 경우에만 새로운 버전을 만든다.

InnoDB

• INSERT의 경우에도 언두 세그먼트에 추가적인 레코드를 새로 넣어야함.

3. rollback에 대비하여 older version을 저장 해두는 경우

PostgreSQL

• PostgreSQL does not need to anything specific in order to restore an older version in case of rollback. Remember the older version has xmax equal to the transaction which updated this tuple. So, till this transaction id gets committed, it is considered to be alive tuple for a concurrent snapshot. Once the transaction is rollbacked, the corresponding transaction will be automatically considered alive for all transaction as it will be an aborted transaction. (이해 불가)

InnoDB

• rollback 발생 시 옛날 버전을 다시 만들어 내야함.

4. older version이 차지하고 있는 공간을 수거하기

PostgreSQL

• 옛날 버전을 읽으려는 병렬적이 snapshot이 있지 않은 이상, old version이 차지하고 있는 공간은 죽은 공간이다.
• ‘죽었다’는 것은, VACUUM 수행이 old version들이 차지하고 있는 공간을 회수하는 것.
• 옛날에 정리했듯이, VACUUM은 manually 작동시킬 수도 있고, 백그라운드로 돌릴 수도 있다.

InnoDB

• UNDO log 공간은 INSERT와 UPDATE UNDO로 나눌 수 있다.
• INSERT UNDO
• 대응되는 트랜잭션이 커밋하면 바로 discard.
• UPDATE UNDO
• 다른 스냅샷이 보고 있으면 계속해서 가지고 있어야함.
• InnoDB에는 explicit한 VACUUM 동작은 없지만, 비슷한 의미에서 백그라운드에서 돌아가는 비동기식 PURGE 동작이 존재한다.

5. vacuum이 지연 되었을 때의 여파

PostgreSQL

• VACUUM이 지연될 경우 엄청난 여파가 존재함.
• 옛날 버전을 최신 버전과 같은 main storage에 한꺼번에 저장하기 때문에, 지속적으로 지운다고 해도 vacuum이 안되면 저장 공간이 계속해서 증가하거나 테이블이 넘치게 된다.

6. bloated table에서의 seqeuntial scan

PostgreSQL

• PostgreSQL의 sequential scan은 모든old version들을 다 훑어봐야한다. (죽었다고 판단 되어도, vacuum이 안되어있으면 봐야함)
• 이게 PostgreSQL에서 가장 많이 제기되는 문제점임.

InnoDB

• 굳이 필요하지 않으면 Undo 레코드를 읽을 필요는 없다.
• 만약에 undo 레코드들이 죽었으면, 그냥 최신 버전들만 읽어도 충분하다.

7. Index

PostgreSQL

• index를 분리된 공간에 저장하고, HEAP의 실제 데이터에 연결하는 하나의 링크만 유지한다.
• 그래서, INDEX자체에는 변경이 없어도, data에 변경이 생기면 INDEX 부분을 업데이트 해야한다. (추후 이 문제는 HOT — Heap Only Tuple 구현으로 해결되는 함)

InnoDB

• InnoDB는 clustered index를 사용하기 때문에 그런 문제는 없다.

결론

• PostgreSQL의 MVCC는사용하는 워크로드에 UPDATE,DELETE가 빈번하게 발생하면 bloated table 관련해서 여러 단점이 존재함.
• 제대로 수거가 안되면 old version을 다 훑어봐야함.
• 최근에는 이 VACUUM 문제를 인식하고, UNDO 기반의 MVCC 접근 방식에 대해 연구중 (ZHEAP)