[MySQL]Undo Log of InnoDB

김규림·2025년 7월 20일

InnoDB란?
: MySQL의 기본 스토리지 엔진 중 하나로, 안정성, 동시성, 트랙잭션 지원 등에서 매우 중요한 역할을 함.
즉 MySQL이 데이터를 어떻게 저장하고 관리할지를 결정하는 방식 중 하나라고 할 수 있음.

Undo Log란?

InnoDB의 중요한 구성요소로 동시성 제어(concurrency control), 장애 복구(Crash recovery)에 많은 영향을 줌.
InnoDB에서의 Undo log 구현은 로그이면서 데이터의 성격을 가짐.
다음 글은 MySQL 8.0을 기반으로 작성함.

1. Undo Log의 역할

Undo log는 각 변경 전에 기록된 이전 값을 저장함. 이는 Redo Log와 함께 장애 복구에 사용됨.

1) transaction rollback

데이터베이스 설계 시 언제든지 시스템이 갑자기 중단(crash)될 수 있음.
커밋되지 않은 트랜잭션이라도 일부 데이터가 디스크에 기록되었을 수 있는데, 이 경우 트랜잭션의 원자성 보장이 깨질 수 있음. 데이터베이스는 하나의 트랜잭션 변경이 전부 반영되거나 전혀 반영되지 않아야 함.

이 문제를 해결하는 직관적인 방식은
'트랜잭션이 커밋될 때 까지 어떤 변경도 디스크에 반영하지 않는' 것.
이를 No-steal 전략이라 함.
그러나 이 전략은 한편으로는 메모리 공간 부족, 커밋 시점의 무작위 I/O로 인한 성능저하를 야기할 수 있음.

이를 보완하여 다음 방식을 채택함:

트랜잭션이 진행되는 도중 Undo log를 함께 기록하여 수정 전의 데이터를 보관.
장애 발생 시, 이 Undo log를 이용해 커밋되지 않은 트랜잭션의 변경 사항을 되돌릴 수 있음.

Undo log는 이러한 crash recovery 뿐만 아니라, 데드락 처리나 사용자가 직접 요청하는 트랜잭션 롤백 등 정상적인 운영 중의 롤백에도 활용됨.

2) MVCC(Multi-version concurrency control)

거의 모든 주요 DBMS는 MVCC 방식을 사용하여 읽기 전용 트랜잭션과 쓰기 트랜잭션 간 충돌을 방지하고 쓰기 작업이 읽기 작업을 기다리지 않도록 처리함.
DB는 각 레코드의 여러 버전(이전 값들)을 저장하고,
읽기 트랜잭션은 필요한 시점의 버전을 참조하며,
쓰기 작업은 단순히 새로운 버전을 추가하면 되므로 충돌이 최소화됨.

InnoDB는 Undo log에 저장된 과거 버전의 데이터를 재사용하여 MVCC를 구현함.

2. 어떤 종류의 Undo Log인가?

페이지 기반 Redo Log는 동시적인 Redo 적용(concurrent Redo application)을 가능하게 하여 데이터베이스의 장애 복구 시간을 줄이는 데 도움을 줌.

InnoDB는 MVCC를 구현하기 위해 Undo log를 사용하며 데이터베이스가 운영 중일 때도 버전 히스토리 데이터를 유지할 수 있게 함.
그렇기 때문에 장애 복구 중 발생하는 Undo log 기반의 트랜잭션 롤백은 일반적인 트랜잭션처럼 백그라운드에서 비동기적으로 처리할 수 있음.
즉, 데이터베이스는 롤백이 끝나기 전에 먼저 서비스를 재개할 수 있음.

Undo log - Redo log 는 설계 원리가 다름.
Undo log는 다음과 같은 점을 중시함:

트랜잭션 간의 동시성
멀티 버전 데이터의 효율적인 관리
데이터베이스의 물리적 저장 구조가 변경되어도 리플레이(복구) 논리가 영향을 받지 않도록 설계

따라서 InnoDB의 Undo log는 트랜잭션 기반의 논리 로그 방식을 채택하고 있음.
또한 InnoDB는 Undo log를 일종의 Data로 관리하며 다른 일반적인 데이터와 마찬가지로 Undo log 역시 Redo log를 통해 그 변경사항이 기록되고 원자성이 보장됨.

3. Content in Undo Log

InnoDB에서 레코드가 수정될 필요가 있을 때마다, 그 이전 상태(히스토리 버전)가 Undo log에 기록됨. 이때 생성되는 Undo 레코드는 update 타입.
새로운 레코드가 삽입될 경우에는 과거 버전이 존재하지 않지만, Insert 타입의 Undo 레코드가 기록됨. 이는 트랜잭션 롤백 시 삽입된 레코드를 삭제할 수 있게 하기 위함임.

1) Insert 타입의 Undo record

이 undo 레코드는 코드 상에서 TRX_UNDO_INSERT_REC 타입(InnoDB에서 트랜잭션 도중 새로운 레코드가 삽입되었을 때 기록되는 Undo 레코드 타입)에 해당함.
Update 타입과 달리 insert 타입의 레코드는 이전 데이터가 아닌 새로운 데이터 이므로 MVCC 기능과는 무관함.
오직 트랜잭션이 롤백될 경우를 대비하여 준비되는 것.

따라서 이 경우에는 롤백 시 어떤 레코드를 찾아 삭제할지 알아내기 위해 해당 레코드의 key만 기록하면 충분함.

Undo Number는 각 Undo 레코드에 부여되는 증가형 숫자임.
Table ID는 어떤 테이블이 수정되었는지 식별하는 데 사용됨.
그 다음에 나오는 Key 필드 집합의 길이는 가변적임. 왜냐하면 기본 키(primary key)는 여러 필드로 구성될 수 있기 때문. 따라서 이 Undo 레코드에는 해당 레코드의 완전한 기본 키 정보가 저장되어야 함.
트랜잭션 롤백 시 이 기본 키 정보를 사용해 인덱스에서 해당 레코드의 위치를 찾을 수 있음.

또한 각 Undo 레코드의 시작과 끝에는 2바이트 공간이 추가되어 있음.
이는 앞선 Undo 레코드와 다음 Undo 레코드의 위치를 기록하기 위한 공간임.
즉, Undo 레코드들은 서로 연결된 구조(연결 리스트 형태)를 가짐.

2) Update 타입의 Undo 레코드

MVCC는 레코드의 여러 과거 버전(히스토리 버전)을 보존해야 하므로 이 과거 버전이 아직 사용 중일 경우에는 삭제할 수 없음. 이런 경우에는 실제 삭제하지 않고, 단순히 해당 레코드의 Delete Mark만 수정함.

그리고 만약 이 시점에 동일한 레코드가 다시 삽입된다면 사실상 이는 새로운 레코드를 추가하는 것이 아니라 Delete Mark만 다시 해제하는 것.

즉, 삭제와 삽입을 Update로 변환하여 처리하게 됨.
이처럼 일반적인 레코드 수정 작업과 더불어, InnoDB에서는 Update 타입 Undo 레코드를 다음 3가지 유형으로 구분함:

TRX_UNDO_UPD_EXIST_REC:기존 레코드의 값 수정 (정상적인 Update)
TRX_UNDO_DEL_MARK_REC:Delete Mark를 세우는 삭제 처리
TRX_UNDO_UPD_DEL_REC:Delete Mark 해제를 포함한 삽입 처리 (삭제 후 재삽입)
이 세 유형은 저장 구조상 공통점이 많음.
Insert 타입 Undo 레코드를 동일하게 헤더, 테일 정보와 기본 키 정보(Key Fields)를 포함하며 여기에 다음과 같은 정보가 추가됨:
💡Transaction ID
해당 Undo 레코드를 생성한 트랜잭션 ID
MVCC에서 버전 가시성 판단(visibillity check) 시 사용됨.
💡Rollptr(Roll Pointer)
이전 버전 Undo 레코드의 위치를 가리키는 포인터
포함 정보: space ID, page number, offset
이 포인터를 따라가면 해당 레코드의 모든 과거 버전을 추적할 수 있음.
💡Update Fields
현재 Undo 레코드가 담고 있는 변경된 필드들의 델타 정보(차이값)
포함 정보: 변경된 필드의 개수/각 필드의 길이/각 필드의 과거 값

4. The Organization Mode of Undo Record

1) 논리적 조작 방식 - Undo Log

하나의 트랜잭션은 여러 개의 레코드를 수정할 수 있으며, 이로 인해 여러 개의 Undo 레코드가 생성됨.
이 Undo 레코드들은 서로 연결되어 하나의 Undo Log를 구성함.
이 Undo Log의 맨 앞에는 Undo Log Header가 추가되어 제어에 필요한 다양한 정보를 담음.

📍Undo Log Header 구조

Trx ID: 해당 Undo Log를 생성한 트랜잭션 ID
Trx No: 트랜잭션의 커밋 순서 번호. 후에 Purge(정리) 가능 여부 판단에 사용함.
Delete Mark: Undo Log에 TRX_UNDO_DEL_MARK_REC 타입이 존재하는지 표시. 불필요한 스캔 회피 목적
Log Start Offset: 헤더 확장을 고려한 호환성 확보를 위해 헤더의 끝 위치 저장
Undo Log/Prev Undo Log: 이전/다음 Undo Log 포인터
History List Node: Purge 작업을 위한 히스토리 리스트에 이 Undo Log를 연결하기 위한 정보

📍Rollptr에 의한 다중 버전 구성

서로 다른 트랜잭션이 동일 레코드(같은 인덱스 키)를 수정하면 각각의 트랜잭션 Undo Log에 해당 레코드의 과거 버전이 저장됨.
이때의 Rollptr(롤백 포인터)를 따라가면 레코드의 모든 히스토리 버전을 연결된 리스트처럼 추적할 수 있게됨.

2) 물리적 조직 방식 - Undo Segment

앞서 논리적 구조를 설명했지만 실제로는 모든 Undo Log가 디스크에 기록되어야 함. 하지만 트랜잭션마다 생성되는 Undo Log의 크기는 제각각임. 반면 InnoDB는 디스크에 16KB 고정 크기 블록 단위로 기록함.

📍InnoDB의 설계 아이디어

짧은 Undo Log: 하나의 Undo Page(16KB) 안에 여러 개를 압축 저장
긴 Undo Log: 여러 Undo Page를 연결해서 저장

📍Undo Segment란?

트랜잭션이 시작될 때 Undo segment가 할당됨
Undo Segment는 하나 이상의 Undo Page를 포함
FSP Segment가 이 Undo Segment의 Page 할당/해제를 관리함. 이는 인덱스에서 사용하는 Leaf/Non-Leaf segment 관리와 동일한 구조

📍Undo Page 구조

38~56바이트: Undo Page Header
페이지 타입, 마지막 Undo Record 위치, 다음 Undo Record를 쓸 위치 등
56~86바이트: Undo Segment Header(첫 페이지 한정)
이 segment의 상태(TRX_UNDO_CACHED 등), 할당된 페이지 리스트 등
그 외: Undo 레코드 저장 공간(Undo Log들)

짧은 Undo Log들은 하나의 페이지에 여러 개 저장
긴 Undo Log는 다수의 페이지에 나눠 저장됨
단, 페이지 재사용은 첫 번째 페이지에서만 가능

3) 파일 조작 방식 - Undo Tablespace

하나의 Undo Segment는 항상 하나의 트랜잭션에만 속함.
모든 쓰기 트랜잭션은 적어도 하나의 Undo Segment을 사용함. 따라서 여러 쓰기 트랜잭션이 동시에 실행될 경우, Undo Segment가 다수 필요함.

📍Rollback Segment 구조

InnoDB의 Undo 파일은 Undo Segment를 위한 슬롯을 다수 준비해둠.
1,024개의 슬롯이 모이면 하나의 Rollback Segment를 구성함.
하나의 Undo Tablespace에는 최대 128개의 Rollback Segment가 들어감.
Undo Tablespace 파일 내 3번째 페이지는 항상 이 Rollback Segment들의 디렉토리(Rollback Segment Array Header)로 사용되며 이곳에는 128개의 포인터가 있어 각각의 Rollback Segment Header가 위치한 페이지를 가리킴.
Rollback Segment Header는 필요 시 할당되며, 각 슬롯은 4바이트임. 하나의 Undo Segment의 첫 페이지를 가리킴.
또, 커밋된 트랜잭션의 히스토리 리스트도 여기에 기록됨. 이후 Purge 프로세스는 이 리스트로부터 정리 작업을 시작함.

📍Rollback Segment 수의 의미

Rollback Segment 수는 InnoDB가 지원하는 최대 병렬 트랜잭션 수에 영향을 미침.
MySQL 8.0은 최대 127개의 독립적인 Undo Tablespace를 지원함. 이는 ibdata1 파일의 과도한 확장을 피하고 Undo 공간 회수(정리)를 용이하게 함. 동시에 Rollback Segment의 개수도 증가시켜 병렬성 향상에 기여함.

4) 메모리 조직 구조

지금까지는 디스크 상의 Undo 구조를 설명함.
실제로는 Undo 로그를 효율적으로 관리하기 위해 메모리 내에도 해당 구조체가 유지됨.

디스크의 각 Undo Tablespace에 대응하여 메모리에도 하나의 Undo::Tablespace 구조체가 존재함.
그 핵심은 여러 개의 trx_rseg_t임. 앞서 설명한 Rollback Segment Header에 해당함.

📍trx_rseg_t 내부 구조

Update List: 현재 Update 타입 Undo 레코드를 기록 중인 Undo Segment
Update Cache List: 아직 사용되지 않았으나 공간이 남아 재사용 가능한 Update segment
Insert List: 현재 Insert 타입 Undo 레코드를 기록 중인 Segment
Insert Cache List: 공간이 남아 재사용 가능한 Insert Segment

각 Undo Segment는 trx_undo_t 구조체로 관리되며 위 네 리스트 중 하나에 포함됨.

5. Undo 로그 쓰기(Undo Writing)

트랜잭션이 시작되면, trx_assing_rseg_durable()을 호출하여 Rollback Segment를 할당함. 이때 트랜잭션 구조체 trx_t는 해당 Rollback Segment를 가리키는 trx_rseg_t 구조체를 연결함.
할당 전략으로는 현재 활성 상태인 Rollback Segment를 순차적으로 시도함.
첫 수정 작업 시 trx_undo_assing_undo()가 호출되어 Undo Segment를 요청함. 먼저 trx_rseg_t의 Cached List에 있는 미사용 Undo Segment를 재사용 시도함. 없다면 trx_undo_create()를 호출하여 새로 생성
현재 Rollback Segment 내 slot을 순회하며 사용 가능한 슬롯(FIL_NUL 값)을 선택. 새로운 Undo Page를 할당하고 Undo Page Header, Undo Segment Header를 초기화함.
메모리 구조체 trx_undo_t를 생성하여 trx_rseg_t의 리스트에 추가
Undo 레코드 기록으로는,
트랜잭션은 할당받은 Undo Segment에 자신만의 Undo Log Header를 초기화하고, trx_undo_report_row_operation() 시퀀스를 통해 Undo 레코드를 기록함.

insert의 경우: trx_undo_page_report_insert()
update의 경우: trx_undo_page_report_modify()
insert 타입 레코드는 기본 키만 기록
update 타입 레코드는 기본 키 + 변경된 필드의 Delta 정보 포함. Undo Record의 위치를 가리키는 Rollptr가 인덱스 레코드에 저장됨.

Undo Page가 가득차면 trx_undo_add_page()를 호출하여 새 페이지 추가
⚠️ 하나의 Undo 레코드는 페이지를 넘지 않음. 현재 페이지에 다 들어가지 않으면 다음 페이지에 전체 Undo 레코드를 기록
트랜잭션 종료 후 처리로는,

Undo page가 1개만 있고 75% 미만 사용 - Undo Segment를 보존하고 Cached List에 추가
Insert 타입 segment - 즉시 재사용을 위해 반환
Update 타입 segment - Purge 완료 후 반환
Undo Segment Header의 상태는 다음 중 하나로 변경됨:
trx_undo_active
trx_undo_to_free
trx_undo_to_purge
trx_undo_cached
이 상태 변화는 트랜잭션 종료의 신호이며, Redo 로그만 디스크에 기록되면 커밋/롤백은 완료된 것으로 처리되어 crash recovery 시 Undo 복구를 다시 수행하지 않음

6. Undo를 통한 롤백 처리

💡 롤백이 발생하는 경우

사용자 명령을 롤백 수행
데드락 발생 시 자동 롤백
crash 후 미완료 트랜잭션 롤백
➡️ 모두 Undo 로그를 기반으로 동일한 방식으로 처리

💡 롤백 처리 절차
1. row_undo() 함수가 진입점
2. trx_roll_pop_rec_of_trx() 호출 ➡️ 가장 마지막 Undo 레코드 pop
3. 레코드가 여러 페이지에 걸쳐 있을 경우:

Undo Segment Header에 기록된 page list로 마지막 Undo page 찾기
page Header의 Free space offset으로 마지막 레코드 위치 확인
prev record offset 포인터를 따라가며 이전 레코드 추적
➡️ 모든 페이지의 레코드를 역순으로 하나씩 롤백 처리

💡 레코드 유형별 롤백 처리
✔ TRX_UNDO_INSERT_REC
함수: row_undo_ins()
처리: 기본 키를 이용해 인덱스에서 위치 탐색

row_undo_ins_remove_sec_rec()
row_undo_ins_remove_clust_rec()

✔ Update 계열 (TRX_UNDO_UPD_EXIST_REC, TRX_UNDO_DEL_MARK_REC, TRX_UNDO_UPD_DEL_REC)
함수: row_undo_mod()
처리:

row_undo_mod_del_unmark_sec_and_undo_update() 호출: 모든 보조 인덱스에서의 영향 롤백
row_undo_mod_clust() 호출: 클러스터 인덱스(기본 인덱스)에서 원래 값으로 복원
➡️ update vector의 delta 정보(diff)를 기반으로 원상복구

💡 롤백 후 공간 회수

trx_roll_try_truncate() 호출: 불필요한 페이지 회수
trx_undo_free_last_page()로 Undo page 반환: 이는 trx_undo_add_page()의 반대 작업

7. MVCC를 위한 Undo

MVCC의 목적은 쓰기 트랜잭션과 읽기 트랜잭션이 서로 기다리지 않도록 하는 것.
각 읽기 트랜잭션은 레코드에 lock을 걸지 않고도 자신이 읽어야 하는 적절한 과거 버전(히스토리 버전)을 찾아야 함.
이를 위해 InnoDB는 읽기 전용 트랜잭션이 시작될 때 전체 DB의 스냅샷을 본 것처럼 작동시켜야 하지만, 실제로 모든 트랜잭션의 스냅샷을 저장하는 것은 시간과 공간 비용이 너무 큼.

💡 InnoDB의 접근법: ReadView

읽기 트랜잭션이 처음 실행될 때 ReadView를 획득하고, 트랜잭션이 끝날 때까지 유지함.
ReadView에는 현재 활성화된 모든 쓰기 트랜잭션의 ID가 기록됨.
InnoDB의 트랜잭션 ID는 자동 증가하므로 어떤 트랜잭션이 커밋되었고 어떤 트랜잭션이 아직 실행 중인지 readview를 통해 판단할 수 있음.

📍 읽기 일관성 규칙(read commited 기준)

커밋되지 않은 트랜잭션의 수정 내용은 볼 수 없음
커밋된 트랜잭션의 수정 내용은 볼 수 있음

💡 Undo 로그를 통한 버전 조회

Undo 로그에는 레코드의 과거 버전 정보가 저장되어 있으며 trx_id 값(수정한 트랜잭션 ID)을 통해 가시성 판단이 가능함.
기본 인덱스에도 trx_id가 함께 저장됨.

💡 Undo 로그에서 과거 버전 복원

Undo는 두 버전 간의 차이(diff)만 저장하므로, Rollptr을 따라가며 Undo 레코드의 delta 정보를 이용해 전체 레코드 내용을 복원해야 함
이 과정은 row_search_mvcc() 함수에서 실행되며 다음 흐름을 따름:

trx_undo_prev_version_build()를 호출해 현재 Rollptr로 Undo 레코드 위치 탐색
만약 해당 Undo 레코드가 Insert 타입이거나 Purge된 상태이면 탐색 종료
or trx_id, Rollptr, 기본 키, update vector(diff) 복원/row_upd_rec_in_place()로 레코드 복원/changes_visible() 함수로 ReadView 기준 가시성 판단. 가시성 있으면 사용자에게 반환

8. Undo for Crash Recovery

장애 복구에에서는 커밋되지 않은 트랜잭션의 모든 변경 사항을 되돌려야 데이터베이스의 원자성을 보장할 수 있음.
Undo는 InnoDB에서 일반 데이터처럼 처리되며, Redo 로그를 통해 내구성(Durability)이 보장됨.

💡 Undo 관련 Redo 타입

mlog_undo_init:Undo page 초기화 시 기록
mlog_undo_hdr_reuse/mlog_undo_hdr_create: Undo log header 재사용/생성 시 기록
mlog_undo_erase_end: Undo page를 넘을 때 불완전한 Undo 레코드 지우기

💡 장애 복구 절차 (ARIES st.)
1. Redo 로그 재생
: 앞서 언급한 Redo 타입들을 통해 Undo 구조 전체 복원
2. trx_sys_init_at_db_start 함수에서:

디스크 상 모든 Rollback Segment/Undo segment를 스캔
각 Undo Segment Header의 상태를 읽어 trx_undo_active면 복구가 필요하므로 롤백 진행/그렇지 않으면 종료된 트랜잭션이므로 정리 가능하다고 판단.

메모리 구조 복원

trx_t: 트랜잭션 구조
trx_rseg_t: Rollback Segment
trx_undo_t: Undo Segment(insert/update 리스트 포함)

💡 비동기 롤백 처리
▶️ 비동기 처리는 어떤 작업을 요청한 후 그 작업이 끝날 때까지 기다리지 않고 다른 작업을 계속 수행할 수 있도록 하는 처리 방식.

srv_dict_recover_on_restart() 에서 비동기 롤백 스레드 trx_recovery_rollback_thread 실행
trx_rollback_active()를 통해 crash 이전의 활성 트랜잭션을 롤백. 이는 일반 롤백 처리와 동일한 방식

9. Undo Cleanup

Undo는 MVCC를 위해 여러 버전 정보를 유지하지만 더 이상 어떤 트랜잭션에서도 읽히지 않을 과거 버전은 제거해야 함.

💡 불필요한 Undo 판단 기준

각 트랜잭션 커밋 시 커밋 순서 번호 trx_no를 부여
각 읽기 트랜잭션은 최초 시작 시점에 본 최대 trx_no를 Readview에 m_low_limit_no로 저장
따라서 어떤 트랜잭션의 trx_no가 모든 활성 ReadView의 m_low_limit_no보다 작다면 해당 트랜잭션은 모든 읽기보다 이전에 커밋됨. 그러면 Undo를 더 이상 사용할 필요가 없으므로 정리 가능함.

💡Purge 작업 흐름

백그라운드 스레드 srv_purge_coordinator_thread가 주도
워커 스레드 srv_worker_thread들이 분산 처리

1) scan a Batch of Undo Records to be cleaned up

트랜잭션 종료 시, Purge가 필요한 update 타입 Undo 로그는 해당 Rollback Segment Header의 History List에 커밋 순서(trx_no)대로 추가됨.
Undo 로그의 정리(purge) 기본 원칙은 작은 trx_no 부터 큰 순서로 Undo 로그 전체를 순차적으로 순회하며 정리하는 것.

❔Rollback Segment가 여러 개일 경우?

InnoDB는 여러 Rollback Segment를 사용할 수 있으며 이 경우 각각 독립적인 History List를 가짐.
각 리스트 내부의 트랜잭션들은 순서가 있지만, 전체적으로 trx_no 기준으로 정렬된 전역 순서를 구성하려면 조정이 필요함.
➡️ 이를 해결하기 위해 purge_queue 도입

💡 purge queue
purge_queue는 힙 자료구조로서 모든 history list로부터 가장 작은 trx_no를 가진 트랜잭션을 우선적으로 처리할 수 있게 해줌.
▶️ Purge 절차
1. purge_queue에 모든 Rollback Segment의 최상위 Undo Log 추가
2. trx_purge_choose_next_log(): purge_queue에서 trx_no가 가장 작은 Undo log를 꺼냄
3. trx_purge_get_next_rec(): 해당 Undo Log의 Undo 레코드를 위에서 아래 방향으로 순회하며 처리. (일반적인 롤백은 아래-위 방향)
4. 처리 후에는 trx_purge_rseg_get_next_history_log() 호출. 현재 Rollback Segment의 다음 Undo Log를 Purge_queue에 추가하고 이후 반복함.

💡 Undo Log가 여러 페이지에 걸쳐 있는 경우
ex) 하나의 Undo Log가 2개의 Undo Page에 걸쳐 존재하는 경우
Undo Log Header의 Log start offset 값을 이용해 첫 Undo 레코드의 위치 탐색
Next Record offset을 따라 다음 레코드로 이동
page가 끝나면 page list node를 통해 다음 페이지로 이동
모든 레코드가 처리될 때까지 이 과정을 반복함.

💡 인덱스 정리와 연동되는 처리
어떤 Undo 레코드는 인덱스 데이터에 영향을 주므로, purge 전에 특별한 처리가 필요함
ex) trx_undo_del_mark_rec 타입: 이는 단순히 레코드를 삭제하는 것이 아닌 delete mark를 세운 상태로 유지한 것
정리 시 해야 할 일로는,
1. Undo purge: trx_undo_del_mark_rec undo 레코드에 대응하는 실제 인덱스 레코드 삭제
2. Undo Truncate: Undo 레코드 자체를 오래된 순서부터 새 레코드까지 삭제(데이터 자체가 아닌 Undo 로그 공간을 제거하는 의미)

💡 Undo Tablespace Truncate
InnoDB에서 독립 Undo Tablespace 수가 2개 이상으로 설정된 경우, Undo Tablespace가 설정된 크기를 초과하면 자동으로 축소(Rebuild) 가능
이 공간 정리 작업을 Undo Tablespace Truncate라고 함.

2) Undo Purge

이 단계는 주로 trx_undo_del_mark_rec 타입의 Undo 레코드를 대상으로 함. 해당 레코드는 인덱스에서 Delete mark가 지정된 레코드를 실제로 삭제하는 데 사용됨.

💡 처리 절차
1. row_purge_parse_undo_rec 함수를 사용해 Undo 레코드에서 Undo type/table_id/Rollptr/기본 키 정보/update vector(변경 정보)를 추출함.
2. Undo 타입이 trx_undo_del_mark_rec인 경우

row_purge_remove_sec_if_poss() 호출: 보조 인덱스에서 삭제
row_purge_remove_clust_if_poss() 호출: 기본 인덱스에서 삭제

Undo 타입이 trx_undo_upd_exist_rec인 경우 기본 인덱스는 삭제되지 않지만 보조 인덱스에서의 삭제가 필요할 수 있음. 이 역시 위 과정과 함께 처리됨.

3) Undo Truncate

Undo purge 후에는 사용되지 않는 Undo 로그 자체를 정리하는 작업이 수행됨.
코디네이터 스레드는 워커 스레드들이 Undo purge를 완료할 때까지 기다리고, 이후 더 이상 필요하지 않은 Undo 로그를 제거하려 시도함.

💡 처리 함수 및 조건
1. trx_purge_truncate() 함수 호출 - 모든 Rollback Segment Undo Segment 순회
2. 각 Undo Segment 상태 확인. 상태가 trx_undo_to_purge이면 trx_purge_free_segment() 호출 - 디스크 공간 해제, 히스토리 리스트에서 제거
상태가 trx_undo_cached 등 다른 상태라면, 단순히 trx_purge_remove_log_hd()를 통해 리스트에서만 제거

⚠️ Undo Truncate는 매번 실행되지 않음. 설정값 innodb_rseg_truncate_frequency에 따라 N번째 Purge 배치마다 한 번 수행
즉, 각 purge 배치는 innodb_purge_batch_size 개의 Undo 레코드를 처리하고 그 결과 show engine innodb status에서 보이는 Undo History List 길이는 간헐적으로 감소(hopping)함

4) Undo Tablespace Truncate

동작 조건으로는 설정값 innodb_trx_purge_truncate가 활성화되어 있어야 함. 이 경우 trx_purge_truncate() 함수는 Undo tablespace 축소도 시도함

💡 처리 흐름
1. Undo Truncate 이후, trx_purge_mark_undo_for_truncate() 함수에서 모든 Undo tablespace의 파일 크기 확인
2. 파일 크기가 innodb_max_undo_log_size를 초과하는 tablespace는 비활성화로 표시됨. 한 번에 최대 하나의 Undo tablespace만 비활성 상태로 유지. 비활성 tablespace의 Rollback Segment는 더 이상 새로운 할당에 참여하지 않음.
3. 해당 tablespace에 있는 모든 트랜잭션이 종료되고, 해당 Undo 로그가 Purge 완료되면 trx_purge_initiate_truncate() 함수 호출. Undo table space의 파일 및 메모리 구조를 재구성(rebuild). 다시 활성화 상태로 전환되어 이후 새로운 트랜잭션에서 재사용 가능.

Reference
https://www.alibabacloud.com/blog/an-in-depth-analysis-of-undo-logs-in-innodb_598966