05_Lock & Transaction Design
struct lock_t {
int trx_id;
int lock_mode;
int is_waiting;
int undo;
lock_table_entry * sentinel;
lock_t * prev;
lock_t * next;
lock_t * trx_prev;
lock_t * trx_next;
pthread_cond_t cond;
};struct lock_table_entry {
int table_id;
int64_t key;
lock_t * head;
lock_t * tail;
};
0 is shared lock
shared lock means that lock can be accessed by other S lock objects.
1 is exclusive lock
exclusive lock mean that lock can not be accessed by any other lock objects.
lock_acquire(table_id, key, trx_id, lock_mode)
lock_acquire(2, 5, 7, 1) means that transaction 7 is trying to get a lock of table 2's key 5 with exclusive lock mode.
Initialize hash table entry and new lock object.
Add new lock object to lock list.
In this case, condition variable is not initialized. Because, new lock object does not wait to acquire the entry.
In this case, we only care about whether new lock object's Trx exists in working lock list.
new lock object's Trx can not be in waiting lock list. It's impossible to occur !!!
So, new lock object's Trx exists in lock list means that it exists in working lock list.
Case 2 - 1 : new lock object's Trx exists in lock list
-
Working lock is X lock
Trx can acquire lock thank to Lock 1.
new lock object's lock mode doesn't matter, because Lock 1 is X mode.
-
Working lock is S lock
-
new lock object is S lock
Whatever waiting lock exist or not, new lock object can acquire lock.
-
new lock object is X lock
-
Direct
Trx can acquire lock by upgrading S working lock to X working lock.
-
Wait
If Deadlock is detected, abort.
Else, new lock object must wait until Trx2 releases its lock.
-
-
Case 2 - 2 : trx_id lock does not exist in lock list
-
Tail lock is working lock
-
Tail lock is S lock
-
new lock object is S lock
No Deadlock in this case.
-
new lock object is X lock
If Deadlock is detected, abort.
Else, add new lock object to lock list and make it sleep.
-
-
Tail lock is X lock
If Deadlock is detected, abort.
Else, add new lock object to lock list and make it sleep.
-
-
Tail lock is waiting lock
If Deadlock is detected, abort.
Else, add new lock object to lock list and make it sleep.
lock_release(lock_obj)
Case 1 - 1 : lock_obj is the only lock of lock list
Delete lock_obj from lock list and update links.
Free lock_obj.
Case 1 - 2 : lock_obj is not the only lock of lock list
-
lock_obj's next lock is working lock
Change head and free lock_obj.
-
lock_obj's next lock is waiting lock, send signal
-
lock_obj's next lock is S waiting lock
Send signal to every possible locks.
Free lock_obj.
-
lock_obj's next lock is X waiting lock
Send signal to only Lock 2, because Lock 2 is X mode.
Free lock_obj.
-
Case 2 - 1 : release by abort
when release(lock_obj) is called by abort situation, be careful about below case.
By releasing Lock 3, Lock 4 & Lock 5 can work. So send a signal to them.
Without upper case, 'lock_obj is not a head of lock list' means that there is still working lock except lock_obj, so lock_obj can not send a signal.
Just update lock list.
Condition 1 - One working lock is left
Condition 2 - First waiting lock's trx is same with one left working lock's trx
After release lock_obj, if lock list satisfies Condition 1 & 2, it is fig 2.
fig 2 means that although Trx1 has S lock, Trx1 was waiting to acquire X lock.
So, change the Trx1's lock mode to X like fig 3 to acquire a lock.
struct trx_t {
int trx_id;
lock_t * next;
lock_t * tail;
unordered_map< int, unordered_map< int, undoLog > > undo_log_map;
};struct undoLog {
int table_id;
int64_t key;
char old_value[120];
};
Deadlock detection occurs at lock_acquire(table_id, key, trx_id, lock_mode).
Deadlock can be detected only below 4 cases.
Although transaction has S lock, it waits to acquire X lock.
Tail is S mode working lock & new lock object is X mode.
Tail is X mode working lock & new lock object is S/X mode.
Tail is S/X mode waiting lock & new lock object is S/X mode.
To detect deadlock, lock manager calls get_wait_for_list(lock_obj, is_visit) at transaction manager.
get_wait_for_list(lock_obj, is_visit) returns the list of trx_id which new lock object is waiting for.
If the returned list has new lock object's trx_id, it means a cycle in dependency graph.
Else, there is no deadlock
In transaction manager, trx_abort(trx_id) conducts abort operation.
Release locks of transaction list.
If lock had been updated record, rollback the value of record by using undo log.
When do the update, log the old value by trx_logging(lock_obj, old_value) function.
2 cases
If the record's log is not exist, log it.
Log is not exist means that record's value is the one which should be rollback when abort happens.
Do not log.
Because, log already has the value which should be rollback when abort happens.