4. Transaction Layer Design

Transaction Layout

1. Transaction

struct trx_t {
	int trx_id;                    // Transaction id
	lock_t* next;                  // Points the next lock object
	lock_t* tail;                  // Points the last lock object
	vector<undoLog> undo_log_list; // Logs for undo operation (Abort)
	pthread_mutex_t trx_latch;     // Mutex 
};

2. Undo Log

struct undoLog {
	int table_id;        // Table id of record
	int64_t key;         // Key of record
	char old_value[120]; // Old value of record

	int64_t lsn;         // (For Recovery) Last sequence number
	int64_t pagenum;     // (For Recovery) Page number of record
	int key_index;       // (For Recovery) Index of record in page
	char new_value[120]; // (For Recovery) New value of record
};

Transaction Lock List

Transaction Lock List는 트랜잭션마다 존재하는 Linked List입니다. 먼저 얻은 Lock Object일수록 Transaction Lock List의 앞쪽에 위치합니다.

Transaction Lock List의 역할은 아래 두 가지 입니다.

1. Deadlock Detection
2. Lock Release

Deadlock Detection

Deadlock Detection 과정

1. Lock Hash Table에 추가되어야 하는 New Lock Object가 도착합니다. (Lock 7, TRX 4, X Mode)
2. Lock 7은 Lock 3를 직접적으로 기다리고 있습니다. Lock 3의 트랜잭션 TRX 3을 Wait-for List에 추가합니다.
3. TRX 3 Lock List를 순회하며 Wait-for List를 생성합니다.
4. Lock 3는 Working Lock이기 때문에 기다리고 있는 Lock이 없습니다. Skip.
5. Lock 4는 Lock 1을 직접적으로 기다리고 있습니다. Lock 1의 트랜잭션 TRX 1을 Wait-for List에 추가합니다.
6. TRX 1 Lock List를 순회하며 Wait-for List를 생성합니다.
7. Lock 1은 Working Lock이기 때문에 기다리고 있는 Lock이 없습니다. Skip.
8. Lock 6는 Lock 5를 직접적으로 기다리고 있습니다. Lock 5의 트랜잭션 TRX 4를 Wait-for List에 추가합니다.
9. Wait-for List에 New Lock Object의 트랜잭션인 TRX 4가 추가되었기 때문에 탐색을 종료합니다.
10. DEADLOCK

위의 Deadlock Detection 과정에 따른 Wait-for List

1. Wait-for List = { }
2. Wait-for List = { TRX3 }
3. Wait-for List = { TRX3 }
4. Wait-for List = { TRX3 }
5. Wait-for List = { TRX3, TRX1 }
6. Wait-for List = { TRX3, TRX1 }
7. Wait-for List = { TRX3, TRX1 }
8. Wait-for List = { TRX3, TRX1, TRX4 }
9. Wait-for List = { TRX3, TRX1, TRX4 }
10. Wait-for List = { TRX3, TRX1, TRX4 } → DEADLOCK

Pseudo Code

// Pseudo Code

List wait_for_list;
int new_lock_obj_trx_id;

bool make_wait_for_list(target_trx_id) {
	for (LOCK in TRX_LOCK_LIST[target_trx_id]) {
		if (LOCK is waiting) {
			if (check_lock_hash_table(LOCK))
				return true;
		}
	}
	return false;
}

bool check_lock_hash_table(target_lock) {
	for (LOCK in LOCK_HASH_TABLE) {
		if (LOCK is WAIT_FOR_LOCK of target_lock) {
			trx_id = WAIT_FOR_LOCK.get_trx_id();
			wait_for_list.add(trx_id);
			
			if (wait_for_list.find(new_lock_obj_trx_id) == true)
				return true;

			make_wait_for_list(trx_id);
		}
	}
	return false;
}

int main() {
	new_lock_obj_trx_id = new_lock_object.get_trx_id();

	bool result = check_lock_hash_table(new_lock_object);
	
	if (result) DEADLOCK;
	else NO_DEADLOCK;
}

New Lock Object가 기다려야 하는 모든 Lock을 확인하여 Wait-for List를 구성합니다. 만약 Wait-for List에 New Lock Object의 트랜잭션이 추가된다면, 자기 자신을 기다리는 Cycle이 생성되기 때문에 Deadlock 입니다.

Wait-for List를 통해 데드락을 확인하는 방법은 다음과 같습니다.

1. 같은 Lock Hash Table에서 자신이 직접적으로 기다고 있는 Lock의 트랜잭션을 Wait-for List에 추가한다.
2. 1번에서 Wait-for List에 값이 추가되는 즉시, Lock Hash Table에서 자신이 직접적으로 기다고 있는 Lock이 남아 있더라도, 추가된 트랜잭션의 Transaction Lock List를 순회하며 1번 과정을 반복한다.
3. 2번이 종료되면, 1번에서 아직 확인하지 못한 Lock을 계속 확인한다. (즉 다시 1번으로 회귀한다.)
4. 만약 1, 2, 3번 과정을 통해 모든 Lock을 확인했는데 Wait-for List에 New Lock Object의 트랜잭션이 존재하지 않는 경우는 데드락이 아니고, 존재하는 경우는 데드락이다.