1. cmu 15-445 Project 0 (2023 Spring)

1.1 Task 1 Copy-On-Write Trie

1. 注意: Trie中根节点为const智能指针,其指向的内容是无法改变的,因此在实现Put和Remove时,在从上到下遍历时,需要不断调用Clone函数来对遍历到的结点进行复制.(从trie.h也能明显看出,复制的结点不需要加const,因此可以对其子树进行修改)
2. key有可能出现为空字符串的情况,需要考虑此边界条件. 新的头结点,可能需要由TrieNode类型变为TrieNodeWithValue
3. 实现Put时,需要注意,新插入的结点不一定是叶子节点,有可能是中间结点,因此需要把其原本的TrieNode类型变为TrieNodeWithValue,直接调用Clone是无法实现此目的.

// 需要保留原本的孩子结点
std::make_shared<TrieNodeWithValue<T>>(iter->second->children_, var_ptr); //TrieNode转换为TrieNodeWithValue
 cur = std::make_shared<TrieNode>(cur->children_);  // TrieNodeWithValue转换为TrieNode

4. Remove实现思路:先对Trie进行遍历,只有发现了满足key的TrieNodeWithValue类型的结点才会执行删除操作,否则返回原本Trie.(也就是说遍历时不对结点进行复制)
   只有确定其中包含需要找到结点后,才开始执行删除操作.这一步通过递归函数实现.

1.2 Task 2 并发

目标是能够并发的实现多读和单写,这里只是加锁,调用上述实现的函数即可.
获取根结点时注意要加锁
在调用Put和Remove时,并不需要加root_lock_,这样代表着调用这两个函数是仍能进行读的操作,这两个操作都是通过复制实现,因此在修改时,不会改变原先根结点的内容,所有可以处理读的操作,当修改完成后,再更新根结点.(只需要在获取根结点或更新时需要root_lock_)

调用函数, 其中value类型为T
new_root.Put(key, value);
出现如下错误:
error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = unsigned int; _Dp = std::default_delete<unsigned int>]’
这里错误的原因是:
T可能为unique_ptr,因此需要改为
new_root.Put(key, std::move(value));

2. Project 1

这块内容不难（如果只是加大锁的话），但优化有难度，需要进行细致的调试及更改代码结构。
最好找一找测试原文件，否则真的很难调出来。

2.1 LRU-k

1. LRU-k想法是利用哈希表实现快速查找,链表实现不满足$k$次,红黑树实现满足$k$次的访问

• 刚开始理解错了题意(之前理解为最新的一次访问), 其实这里的$k$是指,往前数第$k$次访问; 不满足$k$的,以第一次访问为准.
  之前方案为: 利用哈希表和双向链表实现, 历史的时间戳,使用queue存放,当然使用list存放也可以
  (1) 如果自己实现双向链表,那么需要自己维护堆上的变量(即自己调用new).最好还是使用智能指针来进行维护,这样析构时就不用进行额外的操作.也可能使用智能指针来实现双向链表(为避免循环引用问题,next使用shared_ptr,而pre使用weak_ptr)
  (2) 如果自己不实现双向链表使用STL中的list,那么哈希表中保持的指针就无法获取其在list中的位置(无法获取相应迭代器),由于list的迭代器在插入删除时都不会失效,那么是否可以在LRUKNode中保存其插入时的迭代器那?
• 修改后的方案为:
  (1) 新建结点时,统一放入list头部中(使用list存放不满足$k$次访问的),并在LRUKNode保存其对应迭代器,方便删除时使用.
  满足$k$次访问的用map存储(key为向前数第$k$次的时间戳).这样Evict遍历时,可以先从后往前遍历list,如果没有找到,则从前往后遍历map.
  如果只使用一个unordered_map则每次Evict都需要遍历一遍.

2. 线程安全的LRU
   主要的查询结构为unordered_map,必须保证对其的写访问是单独的,可以并发读(并发写肯定会引发冲突,一读一写也可能会导致冲突,因为在写入时很可能会导致unordered_map重新分配空间).此处只是加一些大锁实现

2.2 Buffer Pool Manager

此部分比较简单,按照要求来就行.也不需要添加额外的结构
线程安全部分:还是大锁来的简单.(后面的HardTest基本都是并发测试)

2.3 Read/Write Page Guards

在实现Buffer Pool Manager时,不要使用page的读写锁,其读写锁是Page Guards中维护的,否则在BPMTest中会出现问题.这个测试利用多线程尝试对同一个page调用两次FetchPageWrite,如果FetchPage中有WLatch()的话,会一直阻塞
(1) 原先在Buffer Pool Manager中的所有函数的逻辑为: 先加大锁latch_, 然后对page元数据或内容的改变都加WLatch()
这样就会造成问题,在第一个线程中调用FetchPageWrite,可以正常执行.而第二个线程中的FetchPageWrite会卡在FetchPage的中间,因为其持有latch_锁,无法获取WLatch锁,又会导致第一个线程无法调用BMP中的其他函数(如UnpinPage),从而无法释放WLatch锁,造成死锁

上述的实现可以让QPS 可以达到3000左右

2.4 优化

1. 并发IO优化
   对涉及到磁盘IO的部分,都改为如下形式,但这种方式无法通过HardTest2(有时能过,有时过不了),原因排查比较困难

     latch_.unlock();
     pages_[frame_id].WLatch();
     disk_manager_->ReadPage(page_id, tmp_data);
     pages_[frame_id].WUnlatch();
     latch_.lock()

（1） 保证执行的顺序,当驱逐块时(即进行WritePage时),确保先在page_table释放该page_id,这样其他程序就不会访问到这个正在被删除的块了
如果没有先在page_table删除,那么驱逐时,释放锁,可能有一个并发的FetchPage到来,其仍能从page_table发现该page_id,从而返回其地址（2）原先代码基本框架如下，这种写法比较紧凑，单线程或者加大锁下没有问题，但对多线程不同友好。
因为是在最后才建立新的映射，想象一下，假设page_id = 0不存在缓存池中，有两个线程同时调用FetchPage(0)，第一个线程释放锁，执行WritePage时，第二个线程开始执行，在page_table中仍未找到page_id = 0，又开始调用Evict，并创建page_id = 0的块。这样就造成了重复，并且后一个会覆盖原先的page_table，此时pin_count仍为1，而非2，这就引发错误。

 if (free_list_.empty()) {
     bool flag = replacer_->Evict(&evit_frame_id);
     if (flag) {
       if (pages_[evit_frame_id].is_dirty_) {
       		latch_.unlock();
         	disk_manager_->WritePage(original_pid, tmp_data);
         	latch_.lock()
       }
     }
   }
   if (!free_list_.empty()) {
     new_frame_id = free_list_.front();
     free_list_.pop_front();
     disk_manager_->ReadPage(page_id, tmp_data);
     page_table_[page_id] = new_frame_id;		// 建立新的映射
   }

因此，需要把page_table_[page_id] = new_frame_id放到latch_.unlock()之前，这样第一个线程执行到这步时，其他的线程也能通过page_table_.find()找到该page_id，而不会重新创建，只需要改变pin_count即可，而若想保证在改变pin_count时，该page的元数据被正确设置，那么就需要加锁来实现，并且各page都持有自身的锁。为了不影响后续测试，需要额外添加锁（如果简单的使用page的读写锁的话，调用一个FetchPageRead会一直持有读锁，从而无法在bpm内获得写锁），最简单的方法是在page.h文件中添加一个互斥锁，但这样无法通过在线的测试，因此需要在buffer_pool_manager中实现一个锁数组。

（3）锁数组的实现

• 本来想用vector<mutex>及其emplace_back方法实现，这会调用其复制构造函数，但mutex是没有复制构造和赋值函数的。如果实在要用，可以采用如下方法实现：

std::vector<std::mutex> mutexes;
...
size_t count = 4;
std::vector<std::mutex> list(count);
mutexes.swap(list);

此处参考stackoverflow上的讨论
链接: link

• 这里我是直接通过使用类包装实现的

  struct MyMutex {
    std::mutex latch_;
  };
  MyMutex *mutex_arr_ = new MyMutex[pool_size_];  // 使用方式
  

  （4）加锁的顺序问题避免死锁
  始终保持下述加锁顺序

latch_.lock();
mutex_arr_[i].latch_.lock();

（5）结果
实现并发IO后，分数可以达到5w多

与没有加入并发IO相比，本地测试没有延迟的结果，即--latency 0表明都在内存中，并发IO的性能其实是有些下降，但在Leaderboard上没有体现。
（6）这一步没有测试出来，是自己想出来的
FlushAllPages采用下面的实现，这仍然是单线程的思维，因为把latch_释放后，page_table_可能发生改变，这样就会造成迭代器失效（范围for本质上是使用迭代器遍历实现）

latch_.lock();
for (auto &it : page_table_) {
  page_id_t tmp_p = it.first;
  frame_id_t tmp_f = it.second;
  char *tmp_data = pages_[tmp_f].data_;
  mutex_arr_[tmp_f].latch_.lock();
  latch_.unlock();
  disk_manager_->WritePage(tmp_p, tmp_data);
  pages_[tmp_f].is_dirty_ = false;
  mutex_arr_[tmp_f].latch_.unlock();
  latch_.lock();
}
latch_.unlock();

改进思路就是使用临时数据先将page_table_中的数据保存下来，再释放锁，如下所示：

std::vector<MyPageMeta> frame_arr;
latch_.lock();
for (auto &it : page_table_) {
  page_id_t tmp_p = it.first;
  frame_id_t tmp_f = it.second;
  char *tmp_data = pages_[tmp_f].data_;
  frame_arr.emplace_back(MyPageMeta{tmp_p, tmp_f, tmp_data});
}
for (auto &it : frame_arr) {
  mutex_arr_[it.f_].latch_.lock();
  latch_.unlock();
  disk_manager_->WritePage(it.p_, it.d_);
  pages_[it.f_].is_dirty_ = false;
  mutex_arr_[it.f_].latch_.unlock();
  latch_.lock();
}
latch_.unlock();

（7）这一步的问题是参考码呆茶大佬的实验记录，提前获取了这一步的坑
即将脏页写回磁盘时虽然持有 frame 的锁，但并未持有 bpm 锁，此时如果刚好有另一个线程读取刚刚被淘汰的 page，由于已被驱逐，bpm 会从free_list_获取可用的 frame 空间，并从磁盘上读取该刚刚被淘汰的 page。锁数组中是关于每个frame都有自身的锁，而非关于每个page_id都有自己的锁。
这里的问题就是：正在读取正在写入的页。有两个不同的frame被锁，但其操作的是同一个page_id，一个正在读，一个正在写，就会引发冲突。
我想到的解决措施：其实这个问题应该在底层维护锁数据。但在这一级也能进行，我的想法是额外创建一个读写锁，当向磁盘写入时获取读锁，而当从磁盘读取时获取写锁。这样就会使得读写不能同步发生，只能并发写入，不能并发读取。
知乎链接: CMU 15-445 Project 1 (Spring 2023) | 缓冲池并发 I/O 优化

（8）精细化调整锁范围时出现的未知bug

这个bug只在QPS.1中出现。

UnpinPage函数实现如下所示，即使其他函数全程加latch_.lock，改变page元数据时需要获得锁数组中相应的锁，也会出现上述bug。这表明调用其他函数时，不可能再调用UnpinPage。要么是并发调用了UnpinPage，要么是先调用了UnpinPage，再调用其他函数。

 latch_.lock();
 auto it = page_table_.find(page_id);
 if (it != page_table_.end()) {
   frame_id_t tmp_f = it->second;
   mutex_arr_[tmp_f].latch_.lock();
   latch_.unlock();
   if (pages_[tmp_f].pin_count_ > 0) {
     --pages_[tmp_f].pin_count_;
     if (is_dirty) {
       pages_[tmp_f].is_dirty_ = true;
     }
     if (pages_[tmp_f].pin_count_ == 0) {
       replacer_->SetEvictable(tmp_f, true);
     }
     flag = true;
   }
   mutex_arr_[tmp_f].latch_.unlock();
 }
 else {       // ****
   latch_.unlock();
 }

导致的问题猜测是，无法正确保证设置frame是可弹出的，造成了buffer缓存页满后，没有页面可以被替换出去，从而出现错误。将 replacer_->SetEvictable调整下位置，如下所示，就不会出现这个问题了。（replacer_都是通过加大锁来实现的，逻辑上感觉没问题）

原因猜测是：

1. FetchPage中的很好理解；假设FetchPage(page_id1)中的replacer_->SetEvictable(tmp_f, false)没有加 latch_锁，并且之前执行过UnpinPage(page_id1)，当执行到thread1执行到释放掉 latch_锁，没有执行SetEvictable语句之前。另一个线程执行FetchPage(page_id2)时，那么此时有可能buffer已满，而page_id1是可被驱逐的，恰好驱逐出page_id1，就会出现错误，因此必须加锁，保证其不会被驱逐。

2. 类似对比；假设在UnpinPage中的replacer_->SetEvictable(tmp_f, true)没有加 latch_锁，那么如果多个线程执行到当UnpinPage释放掉 latch_锁，还没有执行replacer_->SetEvictable(tmp_f, true)语句时，额外的get thread线程调用FetchPage，发现没有frame可被驱逐。（这个感觉有点牵强）

上述两条的根本原因是：在 UnpinPage及FetchPage中可以在page_table中找到page_id的情况下，此时操作的frame是被多个线程共享的，而非某个线程独占(对比的是，如果 page 不在缓冲池，则会选择一个可驱逐的 frame 写入，对应 page 一定不会被其他线程持有)，因此需要更加小心。

// FetchPage函数
 latch_.lock();
 auto it = page_table_.find(page_id);
 if (it != page_table_.end()) {
   frame_id_t tmp_f = it->second;
   replacer_->RecordAccess(tmp_f);			// 如果这两句不加 latch_锁，也会出现上述问题，但这两个函数明明是线程安全的
   replacer_->SetEvictable(tmp_f, false);  	// ****此处顺序
   mutex_arr_[tmp_f].latch_.lock();
   ++pages_[tmp_f].pin_count_;
   mutex_arr_[tmp_f].latch_.unlock();
   latch_.unlock();
}
// UnpinPage函数
 bool flag = false;
 latch_.lock();
 auto it = page_table_.find(page_id);
 if (it != page_table_.end()) {
   frame_id_t tmp_f = it->second;
   mutex_arr_[tmp_f].latch_.lock();
   if (pages_[tmp_f].pin_count_ == 1) {					// 如果这两句没加latch_锁，则出现上述错误
       replacer_->SetEvictable(tmp_f, true);
   }
   latch_.unlock();
   if (pages_[tmp_f].pin_count_ > 0) {
     --pages_[tmp_f].pin_count_;
     if (is_dirty) {
       pages_[tmp_f].is_dirty_ = true;
     }
     flag = true;
   }
   mutex_arr_[tmp_f].latch_.unlock();
 }
 else {       // ****
   latch_.unlock();
 }