-
Notifications
You must be signed in to change notification settings - Fork 1
Project 5 Milestone 2
- Implement the Implicit Locking: optimization for reducing space overhead for exclusive locks.
- Implement the Lock Compression: optimization for reducing space overhead for shared locks.
The type definition of trx_entry_t is changed to:
struct trx_entry_t{
uint64_t trx_id;
lock_t* lock;
std::set<uint64_t> wait_for;
std::map<std::pair<std::pair<int64_t, pagenum_t>, std::pair<int64_t, int>>, lock_t*> locks;
std::map<std::pair<std::pair<int64_t, pagenum_t>, int64_t>, std::pair<uint16_t, char*>> logs;
};Two new fields locks and logs is added.
-
locks To find the locks which this transaction holds faster than linear searching all locks in the lock list,
std::mapis used. -
logs To record the log entries which this transaction has written. This was originally located in each lock. But since we are trying to implement the Implicit Locking, we need to record the log entries in the transaction itself.
By the commit d17fe43cb04ce04cb0980ac27cdf036f9bf775fd and 7bc7cad8d53d068bbfa16d8888f628f671adc544, the implicit locking is implemented. In the update() function, the procedure of acquiring the lock is changed to:
if(lock_exist(table_id, leaf, i, trx_id)){
int res = acquire_lock(table_id, leaf, i, trx_id, 1);
if(res < 0) return -1;
} else {
int trx_written = slot.get_trx_id();
int res = trx_implicit_to_explicit(table_id, leaf, i, trx_id, trx_written);
if(res){
ctrl_block = buf_read_page(table_id, leaf);
slot.set_trx_id(trx_id);
PageIO::BPT::LeafPage::set_nth_slot(ctrl_block->frame, i, slot);
buf_return_ctrl_block(&ctrl_block, 1);
} else {
res = acquire_lock(table_id, leaf, i, trx_id, 1);
if(res < 0) return -1;
}
}This is basically similar to the one explained in the specification document. First, we have to check whether there exists any lock of that record id. If there exists, we have to acquire the lock the way we used to.
If there does not exist, we have to check whether the other transaction has written the record before. If it has and that transaction is still running, we have to acquire the lock. Otherwise, we don't need to acquire the lock. We can simply use the implicit locking method.
trx_implicit_to_explicit() is a function that is used to change implicit lock to a explicit lock. It returns 0 on success. Meaning that the new lock has to be acquired in a explicit manner.
Otherwise, it has failed to change the implicit lock to explicit lock. In this project, we can assume that this process failed because the other transaction has already committed. In this case, we can do the implicit locking.
db_find()'s lock aquiring procedure has changed too to support implicit locking. But it is not significant so it will not be described in this wiki.
Implementing the lock compression was a bit more complicated. (And failed to implement on time.)
Implementation explained in this wiki may contain some incorrect approach. This implementation fails to pass the tests
First, we need to add change the lock_t object like so:
struct lock_t{
lock_t* next;
lock_t* prev;
hash_table_entry_t* sentinel;
pthread_cond_t lock_table_cond;
int lock_mode;
int record_id;
lock_t* trx_next;
int trx_id;
uint64_t bitmap; // maximum of 62 records in a page so uint64_t is enough
};W
Note that original_value and original_size are no longer used because we implemented the logs in the trx_entry_t.
64 bits of bitmap is enough because we have at most 62 records in a page.
Following function is used to try to acquire the compressed lock.
lock_t* lock_acquire_compressed(int64_t table_id, pagenum_t page_id, int64_t key, int trx_id) {
pthread_mutex_lock(&lock_table_latch);
std::pair<int64_t, int64_t> p(table_id, page_id);
hash_table_entry_t* list = lock_table[p];
if (list == nullptr) {
pthread_mutex_unlock(&lock_table_latch);
return nullptr;
}
lock_t* cur = list->head;
while (cur != nullptr) {
if(cur->lock_mode == 1 && (cur->bitmap & (((uint64_t)1) << key)) != 0){
pthread_mutex_unlock(&lock_table_latch);
return nullptr;
}
cur = cur->next;
}
cur = list->head;
lock_t* me = nullptr;
while (cur != nullptr) {
if (cur->lock_mode == 0 && cur->trx_id == trx_id) {
me = cur;
break;
}
cur = cur->next;
}
if(me != nullptr){
me->bitmap |= (((uint64_t)1) << key);
}
pthread_mutex_unlock(&lock_table_latch);
return me;
}The main logic is that when there is no X locks that conflict with the key trying to insert, we can do the compressed locking. (if and only if there exists a S lock that is not conflicting with any of the locks)
So first, it checks for the presense of the X lock that conflict with the given key in the first while loop. If there are only S locks present, this will take a very long time. In fact, I think this is the main reason why the Stress Test failed.
If it has passed the first while loop, it means that there are only S locks. This means, if there are any lock that is acquired by this transaction, it is assured that this lock is not a sleeping lock. Therefore, we can turn on the bit in the bitmap.
Let's look at the final version of the acquire_lock() function.
int acquire_lock(int64_t table_id, pagenum_t pagenum, int64_t key, int trx_id, int lock_mode){
lock_t* lock = trx_get_lock(table_id, pagenum, key, trx_id, lock_mode);
if (lock == nullptr) {
// Lock compression // This does not work correctly
if(lock_mode == 0){
lock = lock_acquire_compressed(table_id, pagenum, key, trx_id);
if(lock != nullptr){
trx_add_to_locks(trx_id, key, lock);
return 0;
}
}
lock = lock_acquire(table_id, pagenum, key, trx_id, lock_mode);
lock = trx_acquire(trx_id, lock);
if (lock == nullptr)
return -1;
}
return 0;
}Implicit Locking is done outside this function. This functino is dedicated for acquiring the explicit lock.
First, it looks for the existing lock list(actually a std::map) for the possibility of not needing to actually acquire the lock. If the transaction does not have to needed lock, it should acquire a appropriate lock.
It tries the lock cmpression if the lock mode is 0. If it is successful, it adds the lock to the transaction's lock map using trx_add_to_locks() api. Otherwise, it acquires the lock in the original manner.