[MySQL] Rollback Pointer 기반의 MVCC 이해하기 - 코드 중심으로

DB의 concurrency control 분야를 연구하면서, innodb의 mvcc 로직을 코드 수준으로 이해할 필요가 있다고 생각하여 공부한 내용을 블로그에 작성해보려 합니다.

아래 내용은 제가 직접 찾아보면서 나름의 이해를 바탕으로 쓴 글입니다.

저는 일개 학부연구생으로 전문가가 아닙니다. 그냥 워낙 innodb 관련된 글이 없으므로(특히 한국어는) 조금이라도 도움이 되었으면 해서 블로그로 남기는 것이니 참고만 하시는 게 좋을 것 같습니다.

 

코드 기준은 MySQL-5.7.24 입니다.
아래 모든 코드는 실제 코드를 쉽게 이해하기 위해 임의로 작성한 수도코드입니다. Flow만 참고하면 됩니다.

 

 

---

 

 

0. 관련 용어 정리

 

0.1. Clustered Index와 Secondary Index 개념

- https://jie0025.tistory.com/107 참고

- 정리: 클러스터는 PK용, 세컨더리는 추가 보조 인덱스 정도로 이해하면 될 것 같다.

 

- Docs: https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.html

-  정리: Accessing a row through the clustered index is fast because the index search leads directly to the page that contains the row data.

 

0.2. InnoDB 인메모리 구조

- https://dev.mysql.com/doc/refman/8.0/en/innodb-in-memory-structures.html 참고

- Buffer Pool: 일반적인 버퍼, LRU 알고리즘 사용

- Change Buffer
: 클러스터는 가지지만 보조인덱스는 그렇지 않음
: secondary의 변경 사항을 캐싱해두는 곳 -> 나중에 다시 접근할 때 버퍼와 주기적으로 병합
: 보조 인덱스를 최신 상태로 유지하려면 IO가 많이 소요되므로 캐싱해두면 이득을 볼 수 있다

- Adaptive Hash Index
: 관찰된 쿼리 패턴을 바탕으로 인덱스의 접두사를 활용해 해시 인덱스 구축(ex 자주 인덱스 되는 페이지)
: 테이블이 대부분 메모리에 올라와 있을 경우, 해시 인덱스에서 모든 요소를 조회하고 포인터처럼 사용할 수 있어 쿼리 속도를 높일 수 있다

- Log Buffer: 로그 파일에 기록될 데이터 저장하는 영역

 

0.3. Prebuilt Structure
- https://dev.mysql.com/doc/dev/mysql-server/latest/structrow__prebuilt__t.html#details
- row_prebuilt_t: A struct for (sometimes lazily) prebuilt structures in an Innobase table handle used within MySQL; these are used to save CPU time.

 

0.4. 읽기 모드
- https://blog.naver.com/seuis398/220434402234
- read view: 트랜잭션이 시작한 시점의 스냅샷 정도로 이해
- Committed Read(최근 commit 기준) vs Repeatable Read(내가 read 발생한 시점 기준, 내가 시작한 이후 commit을 읽지 않으려고)
- Consistent Mode: read view의 데이터를 읽음
- Current Mode(Locking Reads): 최근 commit 데이터를 읽음, Lock이 필요한 select 시 사용(explicit lock이 필요한 경우)

 

0.5. Multi Versioning with Rollback Pointer
- https://blog.naver.com/seuis398/70117922756
- 동일 레코드를 다른 Trx가 업데이트 하려 할 때
- 자신의 각 버전을 undo space에 log 작성 -> rollback pointer로 가리킨다
- Ex) Committed Read: 커밋되지 않은 업데이트 읽으려고 시도 -> rollback pointer를 따라 undo log를 찾아 그 row를 읽는다
- Ex) Repeatable Read: 310 trx commit 후 300 trx가 read 시도 -> xid는 300<310이지만 커밋했으니까 310의 변경 내용을 읽는다 / commit 전 read -> rollback pointer를 따라가 이전 값을 읽는다

 

0.6. ICP (Index Condition Pushdown Optimization)
- https://dev.mysql.com/doc/refman/8.0/en/index-condition-pushdown-optimization.html
- 기본: index search -> row 발견 -> where에 반환
- ICP: index 조건 만족하는 경우에만 테이블에서 행을 읽는다 (전체 행 읽기 수를 줄여서 IO를 줄임)
- 엔진-테이블 접근 횟수, 서버-엔진 접근 횟수를 줄일 수 있음
- 클러스터 인덱스는 이미 버퍼에 읽혀져 있어서 이점이 없음
- virtual row의 보조 인덱스에서는 사용 불가능
- 순서: 해당 row의 index tuple 가져옴 -> index로만 where 판단 가능한지 -> 가능하면 index로 전체 테이블 찾아 읽기

 

0.7. Infimum record, Supremum record
- Infimum: 인덱스의 smallest value와의 gap을 나타내는 수도 레코드(locking 용 record)
- 내가 smallest value 포함한 쿼리로(ex. where < 10) 접근하고 있을 때, 다른 trx가 더 작은 value 추가 못하게
- Supremum: largest valude와의 gap

 

1. row_search_mvcc()

- cursor를 이용해 row search 하는 함수, 접근하고자 하는 row를 재구축(새 버전)

 

0) PHASE 0

- adaptive hash index latch에서 (있다면) S-Latch 해제(누가 기다릴 수도 있으니까)
- new record lock info 초기화

 

1) PHASE 1

- prefetch cache에서 row 가져오기
- non-delete-marked locking 시도 -> LOCK_REC_NOT_GAP 표시
- 보조 인덱스는 삭제 표시 다른 버전 있을 수도 있음 -> 그래서 보조 인덱스+locking delted-marked records 사용 시, next-key lock 사용해야 함

 

mtr_start(&mtr);

 

2) PHASE 2

- adaptive hash table 사용 가능한지 확인

// consistent read, read view 이미 할당
// LOCK_NONE: used to note consistent read
if((select_lock_type == LOCK_NONE) 
	&& (!READ_UNCOMMITTED) 
    	&& (readview) 
    	&& (mysql_n_tables_locked == 0)) //insert, create 용 select 아닐 때
{
	
    //hash index 사용 가능
    
    S_LOCK(index);
    
    switch(shortcut 탐색) //shortcut: clustered idx로 fetch
    {
    	case SEL_FOUND: //page latch -> mtr commit 시 해제
        	if(ICP) { row_search_idx_cond_check(); }
            
            //convert row format: Innobase -> MySQL
            row_sel_store_mysql_rec(buf, prebuilt,
						rec, NULL, FALSE, index,
						offsets, false);
                        
            mtr_commit(&mtr);
            err = DB_SUCCESS;
            UNLOCK_S_LOCK(index);
            goto func_exit;
        
        mtr_commit(&mtr);
		mtr_start(&mtr);
  }

 

3) PHASE 3

- cursor position open/restore

release_search_latch(trx);

if((REPEATABLE_READ)||(TRX_ISO_SERIALIZABLE)&&(plain lock SELECT)) { gap_locks = FALSE; }

thr = que_fork_get_first_thr(prebuilt->sel_graph);
thr->state = QUE_THR_RUNNING; //que_thr_move_to_run_state_for_mysql(thr, trx);
clust_index = dict_table_get_first_index(index->table);

if(consistent_read) { trx_assign_read_view(trx); }
else 
{
	// trx->rw_mode(read only trx 제외)
    // compatible 확인 -> lock_table_enqueue_waiting() or lock_table_create()
    // 여기서는 lock mutex 획득X (trx만 table lock을 얻을 수 있으므로)
	err = lock_table();
    if (err != DB_SUCCESS) { table_lock_waited = TRUE; goto lock_table_wait; }
}

if (gap lock) { err = sel_set_rec_lock(); }

 

4) PHASE 4

- loop 돌면서 record 탐색

if(infimum(rec)) { prev_rec = NULL; goto next_rec; //infimum은 result 반환 불가능 -> skip)
if(supremum(rec)
{
	if(row in mysql_rec is out of range) { err = DB_RECORD_NOT_FOUND; goto normal_return; }
	
    // lock on index record
    if((REPEATABLE_READ)||(TRX_ISO_SERIALIZABLE) { err = sel_set_rec_lock(); }
    
    prev_rec = NULL; goto next_rec;
}

offsets = rec_get_offsets();
prev_rec = rec;

if (prebuilt->select_lock_type != LOCK_NONE)
{
	// next-key locking X
	if((READ_UNCOMMITTED)|| (READ_COMMITTED)) { goto no_gap_lock;
    
    // 존재하는 PK 기준으로 range search -> phantom 생길 일 없음 -> gap lock X
    if() { no_gap_lock: lock_type = LOCK_REC_NOT_GAP;}
    
    err = sel_set_rec_lock();
    
    switch (err)
	{
    case DB_LOCK_WAIT:
    	// Never unlock rows that were part of a conflict
        if(unique_search) { goto lock_wait_or_error; }
        
        // deadlock 아니면 wait
        err = lock_trx_handle_wait(trx);
        switch (err)
		{
        case DB_SUCCESS: goto locks_ok; // normal locking read, 가장 최근 commit 버전 읽기
        case DB_DEADLOCK:
			goto lock_wait_or_error;
        case DB_LOCK_WAIT: err = DB_SUCCESS; break;
    }
        
    if (old_vers == NULL) { goto next_rec; } //row is not committed
}

next_rec:
	prev_vrow = vrow; end_loop++;

 

5) PHASE 5

- next index record로 cursor 이동

- moves_up = FALSE: b-tree page 바꿀 때마다 mtr commit&restart
- TRUE: 한 mtr에서 전체 secondary index tree 스캔

if (moves_up)
{
	move = btr_pcur_move_to_next(pcur, &mtr);
    if (!move) { goto normal_return; }
}
goto rec_loop;
    
lock_wait_or_error:
lock_table_wait:
	mtr_commit(&mtr); mtr_has_extra_clust_latch = FALSE;
    que_thr_stop_for_mysql(thr); thr->lock_state = QUE_THR_LOCK_ROW;
    
    if (row_mysql_handle_errors())
	{
    	// lock wait end
        thr->lock_state = QUE_THR_LOCK_NOLOCK; mtr_start(&mtr);
        
        // 다시 lock 시도
        if (table_lock_waited) { goto wait_table_again; }
        
        goto rec_loop;
  	}
thr->lock_state = QUE_THR_LOCK_NOLOCK; goto func_exit;

normal_return:
que_thr_stop_for_mysql_no_error(thr, trx);

// block 한 trx들 rollback 시키기
if (!trx->hit_list.empty()) { trx_kill_blocking(trx); }

func_exit: DBUG_RETURN(err);

 

 

 

---

 

2. trx_undo_report_row_operation()

- insert, update, delete의 undo log를 작성하는 함수이다.
- clustered index record에 대해서만 undo log를 작성한다.
- 이때 작성된 undo log는 rollback이나 consistent read에서 사용된다.

- Temporary table일 때: 수정사항을 기록하지 않음

- Read-Only transaction일 때: temporary table만 수정할 수 있으므로 temporary rseg만 할당한다

- object가 temporary일 때: restore 시 복구되면 안 되므로 redo log를 비활성화 한다

- Insert 일 때:

err = trx_undo_assign_undo(trx, undo_ptr, TRX_UNDO_INSERT);
undo = undo_ptr->insert_undo;

 

- Update/Delete 일 때:

undo = undo_ptr->update_undo;
if (undo == NULL) {
	err = trx_undo_assign_undo(trx, undo_ptr, TRX_UNDO_UPDATE);
    	undo = undo_ptr->update_undo;
}

 

- 마지막으로 rollback pointer를 설정하고 마무리한다.

undo_block = buf_page_get_gen();
*roll_ptr = trx_undo_build_roll_ptr();
return(DB_SUCCESS);

 

 

 

---

 

 

3. code level의 mvcc in innodb: Read-Write

- innodb의 multi version은 undo log로써 관리가 된다. rollback pointer + xid로 자신의 read view를 찾아가는 방식

- 즉, 내가 읽고 있는 레코드를 다른 트랜잭션이 수정/커밋했을 때 다시 읽으면 수정한 값이 아닌, 나의 read view의 값을 읽는다는 것이다.

- 한 번 tpc-c의 데이터로 다음과 같은 시나리오를 진행했을 때 어떤 방식으로 진행되는지 확인해보겠다.
- 기본 isolation level인 Repeatable read mode 이다.
- tpc-c의 warehouse 테이블을 사용하였다.

Trx 1	result	Trx 2
	TO
begin; select w_state from warehouse where w_id = 5;	TO
	(1)	begin; update warehouse set w_state = "00" where w_id = 5; commit;
select w_state from warehouse where w_id = 5; commit;	(2)  TO

 

 

3.1. (1) 코드 진행

- row_search_mvcc(): 우선 w_id가 PK, 즉 clustered index 이므로 PHASE 4의 sel_set_rec_lock() 함수를 이용해 lock을 걸고 record를 읽어온다.

err = sel_set_rec_lock(pcur,
	rec, index, offsets,
    	prebuilt->select_lock_type, 
    	lock_type, thr, &mtr);

- compatible한 lock이므로 정상적으로 lock을 생성한다.

- update를 진행하는데 btr_cur_update_in_place() 함수를 확인해보면
btr_cur_upd_lock_and_undo(): undo log 작성
row_upd_rec_in_place(): 실제 buffer record 수정
를 하고 있는 것을 확인할 수 있다.

 

3.2. (2) 코드 진행

- row_search_mvcc(): PHASE 4에서 old_vars를 읽어온다. (아래 주석 부분)

/* This is a non-locking consistent read: if necessary, fetch
		a previous version of the record */
        
/* Fetch a previous version of the row if the current
			one is not visible in the snapshot; if we have a very
			high force recovery level set, we try to avoid crashes
			by skipping this lookup */

- row_set_build_prev_vers_for_mysql() -> row_wars_build_for_consistent_read()

- row_wars_build_for_consistent_read():

trx_id = row_get_rec_trx_id(rec, index, *offsets);
if (view->changes_visible(trx_id, index->table->name)) {
	// old version 존재
    	*old_vers = rec_copy(buf, prev_version, *offsets);
    	rec_offs_make_valid(*old_vers, index, *offsets);
}

 

 

---