-
Notifications
You must be signed in to change notification settings - Fork 0
Project5_Milestone1
Yeonguk Go edited this page Oct 8, 2021
·
2 revisions
- 현재 과제에서는 transaction 안에서 db_find와 db_update만 동작하면 된다.
- 하지만 실제 완성된 DBMS에서는 transaction 안에서 insert / delete / find / update는 물론, JOIN과 같은 releational set operator까지 포함된 query 여러 개를 담을 수도 있어야 한다.
- 따라서, transaction과 lock을 관리하는 lock manager는, 특정 layer의 상/하위에 반드시 위치할 필요는 없지만, 모든 layer를 일렬로 세우기 위해 위치를 꼭 정한다면 최상위 layer로 위치해야 할 것이다.
- 하지만, concurrency를 위해 사용하는 latch는 특정 layer에 모두 둘 필요 없이, 각 layer에서 사용하면 된다.
enum trx_state {IDLE, RUNNING, WAITING};
typedef struct trx_t trx_t;
struct trx_t {
int trx_id;
enum trx_state state;
list<lock_t*> trx_locks;
lock_t* wait_lock;
};- 각각의 transaction에 관한 정보를 담기 위한 transaction 구조체이다.
- begin_trx 함수에 의해 할당/초기화되며 거기서 정해진 unique transaction id를 member로 가진다.
- IDLE, RUNNING, WAITING 3가지 상태를 가지는 state를 member로 가진다. 초기화 시 (아직 아무 action이 없으므로) IDLE로 초기화된다.
- 해당 transaction이 잡고 있는 lock들의 list인 trx_locks를 member로 가진다.
- 해당 transaction의 state가 WAITING일 경우 어느 lock을 대기 중인지를 가리키는 lock_t 포인터 wait_lock을 member로 가진다. state가 WAITING이 아닐 경우 NULL로 둔다.
unordered_map<int, trx_t> trx_table;- transaction의 개수는 정해져 있지 않으며, unique한 transaction id 값을 가지므로, transaction 구조체를 담기 위한 transaction table의 container로 unordered_map을 사용하도록 하였다. (전윤성 학생의 제안)
- transaction의 개수가 적을 경우 hash를 사용하는 unordered_map에 비해 tree를 사용하는 map의 탐색속도가 빠를 수 있다. 하지만 DBMS는 많은 transaction이 동시에 수행 중인 상황도 고려해야 하고, transaction의 수가 적을 경우 unordered_map이 map에 비해 상대적으로 느리더라도 절대적으로는 둘 다 매우 빨라서 큰 차이가 나지 않을 것이다. 또한 현재 1부터 차례로 증가하도록 begin_trx에서 구현한 transaction id는, hashing했을 때의 conflict를 최소화할 수 있는, 즉 hash에 매우 적합한 key이므로 unordered_map을 사용하였다.
enum lock_mode {SHARED, EXCLUSIVE};
typedef struct lock_t lock_t;
struct lock_t {
int table_id;
int64_t key;
enum lock_mode mode;
list<trx_t*> current_trxs;
list<trx_t*> waiting_trxs;
};- 각 transaction에서 특정 table의 특정 record에 lock을 걸기 위해 사용되는 구조체이다.
- 해당 table_id와 key(record_id)를 member로 가진다.
- SHARED, EXCLUSIVE 2가지 상태를 가지는 mode를 member로 가진다.
- 현재 해당 record에 lock을 잡고 있는 transaction들에 대한 back pointer list인 current_trxs를 member로 가진다. SHARED mode일 때 해당 record에 대한 여러 transaction의 lock을 각각의 구조체로 두지 말고, 하나의 구조체에서 관리하도록 하기 위해 사용한다.
- 현재 해당 record에 lock을 잡기 위해 wait 중인 transaction들에 대한 list인 waiting_trx를 member로 가진다. 이는 current_trxs들이 end될 때, current_trxs가 더 이상 없으면 waiting_trxs list의 첫 번째부터 wake 시키기 위해 사용한다.
- lock의 개수는 정해져 있지 않으므로 가변적인 container를 써야 할 것이다. buffer에서와 같이 크기를 정하고 가는 것이 아니므로 array 등으로는 어렵고, c++에서 제공하는 unordered_map이나 다른 hash container들을 고려해봐야 한다.
- page id로 access하도록 과제에서 명시하였으니, db_find와 db_update에서는 입력받은 table_id와 key에 해당하는 page id를 확인해본 후 lock hash table을 확인하는 것이 맞는지 고려가 필요하다.
- page id로 lock hash table에 진입 시, page별로 hash bucket을 가지고, 그 안에 record별 slot에 lock 구조체를 가지도록 할 수 있다.
- page id가 아닌 table id와 key를 가지고 lock hash table을 확인할 경우, 2개 값을 어떻게 hash value으로 만들지 고려가 필요하다. buffer에서와 같이 cantor pairing function을 사용할 수 있으나 overflow 발생을 주의해아 한다.
- table id와 key를 가지고 lock hash table에 진입 시, 각각의 lock 구조체가 hash bucket이 될 수 있을 것이다.
int trx_cnt = 1;
pthread_mutex_t trx_latch = PTHREAD_MUTEX_INITIALIZER;
int lock_begin_trx(void) {
int trx_id = 0;
pthread_mutex_lock(&trx_latch);
if(trx_table.size() < __INT_MAX__) {
while(true) {
while(trx_table.find(trx_cnt) != trx_table.end()) {
trx_cnt++;
}
if(trx_cnt < 0) { trx_cnt = 1; }
else { break; }
}
trx_id = trx_cnt;
trx_table.insert({trx_id, trx_t{trx_id, IDLE, list<lock_t*>(0), NULL}});
}
pthread_mutex_unlock(&trx_latch);
return trx_id;
}- API layer의 begin_trx 함수가 wrap할 lock_begin_trx 함수를 lock manager layer에 구현하였다.
- unique한 1 이상의 transaction id를 생성하기 위해, 전역변수 trx_cnt를 lock manager layer에 두었다.
- lock_begin_trx 함수는 trx_cnt 값을 key(transaction id)로 가지는 transaction이 transaction table에 존재하지 않을 때까지 trx_cnt를 1씩 증가시켜가며 탐색한다. (일반적으로, 2147483646개의 추가적인 transaction이 수행될 동안 종료되지 않은 transaction이 존재하지 않는 한, 0~1번의 증가를 수행한다.)
- 탐색한 transaction id를 가지는 transaction 구조체를 초기화하여 transaction table에 삽입한다.
- int 자료형의 최대 크기(4bytes int 기준 2147483647)를 넘어가서 overflow가 발생하여 trx_cnt가 음수가 된 경우에는 trx_cnt를 1로 초기화한다. 따라서, trx_id는 1~ 2147483647, 총 2147483647개를 가질 수 있다.
- 따라서, trx_table의 size가 2147483647보다 작을 때만 해당 과정을 수행하고 새로 시작된 transaction의 id를 반환하며, 2147483647개의 transaction이 이미 모두 존재할 때는 0(실패)를 반환한다.
- 여러 user가 접근 시 trx_cnt 값에 대한 data race를 방지하기 위하여, lock_begin_trx 내부 동작을 pthread_mutex_t로 구현한 latch로 보호한다.
int lock_end_trx(int tid) {
if(trx_table.erase(tid) == 0) {
return 0;
}
return tid;
}- API layer의 end_trx 함수가 wrap할 lock_end_trx 함수를 lock manager layer에 구현하였다.
- transaction table에서 입력받은 transaction id를 가지는 transaction 구조체를 찾아서 삭제하고 해당 tid를 반환한다. 존재하지 않을 시 0(실패)를 반환한다.
- 해당 transaction이 wait중인 lock이 있을 경우 대기하고, 모든 수행이 완료되면 해당 transaction이 잡고 있던 모든 lock을 unlock하는 작업 또한 필요하다. 현재 lock manager를 온전히 구현하지 않았으므로 생략되었으며, 추후 추가될 예정이다.
- 현재 구상에 따르면, 해당 transaction 구조체가 가지는 trx_locks list의 lock을 하나하나 확인한 후 아래 작업을 수행한다. 이 때 lock hash table의 global latch를 잡고 작업하도록 한다.
- 해당 lock을 잡고 있는 다른 transaction과 해당 lock을 wait 중인 다른 transaction이 없을 경우 이를 lock_hash_table에서 erase한다.
- 해당 lock을 잡고 있는 다른 transaction이 있을 경우, current_trxs list에서 현재 transaction을 제거만 한다.
- 해당 lock을 잡고 있는 다른 transaction이 없고, 해당 lock을 wait 중인 다른 transaction이 있을 경우, current_trxs list에서 현재 transaction을 제거한다. 그 다음 waiting_trxs list의 첫 번째 transaction을 WAITING state에서 깨워 작업을 수행하게 해야 하는데, wait이 발생한 시점에 sleep을 시켰다가 wake시키는 것을 구체적으로 어떻게 수행할지 고려가 필요하다.
// 현재 구현
int lock_find(int table_id, int64_t key, char* ret_val);
// 구현 예정
int lock_find(int table_id, int64_t key, char* ret_val, int trx_id);- API layer의 db_find 함수가 wrap할 lock_find 함수를 lock manager layer에 구현한다.
- 현재 lock manager를 온전히 구현하지 않았으므로, transaction 없이 기존 사용하던 find 함수의 wrapper function으로 동작하게 두었다.
- transaction_id를 입력받으면 이를 탐색하여 해당 transaction의 state를 확인하고, RUNNING/WAITING 상태일 경우 IDLE 상태가 될 때까지 대기할 것이다.
- IDLE이 되면 state를 RUNNING으로 변경한 후, 입력받은 table_id와 key를 가지고 lock hash table을 탐색할 것이다. 이 때, 여러 user가 동시에 lock hash table을 수정할 수 없도록 lock hash table의 global latch를 얻고 수행할 것이다.
- 해당 table_id와 key를 가지는 lock이 없으면, lock_mode는 SHARED, current_trxs list에는 현재 trx가 추가된 lock을 생성할 것이다. 이를 lock hash table에 넣고, 이의 포인터를 현재 trx의 trx_locks list에 추가할 것이다. 이후 global latch를 풀어준다.
- 해당 table_id와 key를 가지는 lock이 SHARED mode로 있으면, 해당 lock의 current_trxs list에 현재 trx를 추가하고, 이의 포인터를 현재 trx의 trx_locks list에 추가할 것이다. 이후 global latch를 풀어준다.
- 해당 table_id와 key를 가지는 lock이 EXCLUSIVE mode로 있으면, 해당 lock의 포인터를 transaction의 wait_lock에 담고 transaction의 state를 WAITING으로 변경한다. 해당 lock의 waiting_trxs list에 현재 trx를 추가하고, 이후 global latch를 풀어준 뒤 sleep한다. 기존에 해당 record에 lock을 걸고 있던 trx가 end되어 wake시켜야하는데, 이를 구체적으로 어떻게 구현할지 고려할 필요가 있다.
- 하위 layer의 find 함수를 이용하여 실제 find를 수행하고 그 값을 ret_val에 넣어준 뒤, 결과값을 반환한다.
// 구현 예정
int lock_update(int table_id, int64_t key, char* values, int trx_id);- API layer의 db_update 함수가 wrap할 lock_update 함수를 lock manager layer에 구현한다.
- 추후 여기서 사용할 update 함수를 하위 layer에 구현해야 한다.
- transaction_id를 입력받으면 이를 탐색하여 해당 transaction의 state를 확인하고, RUNNING/WAITING 상태일 경우 IDLE 상태가 될 때까지 대기할 것이다.
- IDLE이 되면 state를 RUNNING으로 변경한 후, 입력받은 table_id와 key를 가지고 lock hash table을 탐색할 것이다. 이 때, 여러 user가 동시에 lock hash table을 수정할 수 없도록 lock hash table의 global latch를 얻고 수행할 것이다.
- 해당 table_id와 key를 가지는 lock이 없으면, lock_mode는 EXCLUSIVE, current_trxs list에는 현재 trx가 추가된 lock을 생성할 것이다. 이를 lock hash table에 넣고, 이의 포인터를 현재 trx의 trx_locks list에 추가할 것이다. 이후 global latch를 풀어준다.
- 해당 table_id와 key를 가지는 lock이 있으면, 해당 lock의 포인터를 transaction의 wait_lock에 담고 transaction의 state를 WAITING으로 변경한다. 해당 lock의 waiting_trxs list에 현재 trx를 추가하고, 이후 global latch를 풀어준 뒤 sleep한다. 기존에 해당 record에 lock을 걸고 있던 trx가 end되어 wake시켜야하는데, 이를 구체적으로 어떻게 구현할지 고려할 필요가 있다.
- 하위 layer에 구현한 update 함수를 이용하여 실제 update를 수행하고 그의 결과값을 반환한다.
- DB item 외의, memory 상에 존재하는 모든 shared data structure를 보호하기 위해 존재한다.
- 현재 구현한 것에는, 다수의 user가 존재할 때 transaction id 생성 중 data race가 발생하지 않도록 lock manager에 구현된 latch가 있다.
- lock hash table에서 특정 lock을 탐색/수정할 때, 중복으로 수행되지 않도록 global latch가 존재해야 한다.
- buffer manager에서도 buffer에서 특정 page block을 탐색할 때, 중복으로 수행되지 않도록 global latch가 존재해야 한다.
- buffer manager에서는 page block별로 실제 read/write가 동시에 일어나지 않도록 page latch가 필요하다.
- buffer manager에서 특정 page에 접근할 시, global latch를 얻은 후 필요한 page를 탐색하고, 해당 page latch를 얻은 다음, global latch를 풀고 실제 read/write를 수행한 후 page latch를 풀어야 한다.
- buffer manager에서는 이 외에도 각 table의 정보를 저장하는 구조체의 배열, LRU list 등의 shared data가 존재한다. 이에 관한 접근도 latch를 이용해 문제가 생기지 않도록 방지해야 한다. db open이나 shutdown도 동시에 진행되지 못하도록 latch를 이용할 필요가 있다.
- 현재 과제에서는 deadlock을 해결하기 위해 prevention이 아닌 detection을 사용한다.
- 이를 위해 waits-for graph가 필요하다.
- 현재 구상 중인 구현에서는, 각각의 transaction 구조체는 어느 lock을 위해 wait 중인지를 저장하고 있고, 해당 lock 구조체는 현재 해당 lock을 잡고 있는 transaction을 저장하고 있기 때문에 이를 이용해서 waits-for graph의 create/maintain이 가능하다.
- 이를 주기적으로 체크하여 cycle이 존재하는지 확인하고 죽여야 할 transaction을 abort 시켜야 한다.
- 언제 어떻게 주기적으로 체크할지를 고려할 필요가 있다.
- 기존에는 각각의 layer의 함수들이 해당 layer를 의미하는 접두사를 가지는 경우(주로 상위 layer에서 사용되는 함수)와 그렇지 않은 경우(주로 해당 layer 안에서 helper function으로 사용되는 함수)가 있었다. 이를 모두 접두사를 가지도록 수정하고, 접두사들을 abbreviation으로 변경하였으며, 일부 함수명/구조체명 등을 좀 더 적절하게 혹은 간단하게 바꾸었다.
- 기존에는 특정 leaf page 삭제 후 right sibling page number를 재연결해 줄 때, 삭제되는 page의 left page를 찾기 위해 table의 leftmost leaf page부터 탐색했다.
- 이는 leaf page가 증가(record가 증가)할수록 그에 비례해 탐색시간이 증가하는 문제점을 가지고 있다. 따라서 개선할 필요가 있다.
- 삭제할 leaf page가 parent page의 leftmost child가 아닌 경우, parent page를 이용해 쉽게 left page를 찾을 수 있다. 따라서 삭제할 page가 leftmost page인 경우의 처리를 위해 2가지 방법을 고려하였다.
- parent page의 left sibling page의 rightmost child page를 탐색한다. parent page도 그의 parent page의 leftmost child일 경우, 더 타고 올라가야 하며, 최악의 경우 root page까지 탐색해 올라가게 되는 상황이 발생할 수 있다. 하지만 그런 경우는 매우 적게 발생하며, 현재 page가 leftmost page가 아닐 경우와 마찬가지로 이렇게 찾은 left page의 right sibling page 값만 바꿔준 후 현재 page를 삭제하면 된다. (전윤성 학생의 제안)
- left page를 탐색하는 것은, 현재 page가 삭제될 예정이므로 left page의 right sibling page number를 현재 page의 right sibling page number로 갱신해주기 위함이다. 따라서 현재 page가 삭제될 상황에서 현재 page를 삭제하지 않으면 left page를 탐색할 필요가 없다. 이렇게 하기 위해, right sibling page의 모든 정보(records, right sibling page number)를 현재 page로 복사한 후, 현재 page 대신 right sibling page를 삭제하도록 한다. (차세현 학생의 제안)
- left page를 탐색하는 추가적인 함수 구현이 필요 없는 2번째 방법을 선택하였다.
- 변경 후, 100만 개 records를 random order로 삭제하는 작업을 수행해본 결과, 기존 2분 30여초 정도 걸리던 것이 50여초 정도로 약 1/3로 줄어든 것을 확인할 수 있었다. 또한 이는 records의 수가 커질수록, 우측의 records를 먼저 삭제할수록 탐색시간이 증가하던 기존의 문제를 해결할 수 있기에, 반드시 필요한 변경 사항이었다.
- 과제에서 제안한 data structure에 사용되는 list, 가변적인 hash table을 사용하기 위한 unordered_map 등 c++에서 지원되는 기능을 사용하기 위하여 모든 파일을 .c에서 .cpp로 변경하였다.
- 기존 c style로 작성한 코드들은 c++에서 모두 호환되므로 따로 변경하지 않고, 추가적으로 사용할 부분만 c++에서 지원되는 기능을 사용하도록 했다.
- 파일들이 변경됨에 따라 makefile도 수정하여 gcc가 아닌 g++로 컴파일하도록 변경하였고, makefile을 전체적으로 단순화하였다.
- main.cpp(기존 main.c) 파일은 libbpt.a를 만드는 데에 사용되는 필수적인 코드가 아닌, 현재 테스트를 위해 사용하고 있는 코드이므로, project5/src/ directory에서 project5/ directory로 위치를 변경하고 makefile도 그에 맞게 수정하였다.