Nathanaël

纳塔纳埃尔，切莫再想去尝试旧日的清水

0%

CMU 15-445 Project-1（2022秋季）

发表于 更新于

其实我做过去年的lab，但没有写年轻人的第一棵B+树难免是一种遗憾，于是寒假决定写完B+树就收手！

Task #1 - Extendible Hash Table

这一部分是要实现一个可拓展哈希表，作为去年的Project-2，我已经接触过了，所以写起来没啥太难得地方，但还是有个bug卡了一会儿。

Bucket的插入删除查找很简单，不再赘述，主要介绍可拓展哈希的扩容原理。

可拓展哈希有一个目录，目录元素是指针，指针指向一个实际的Bucket

1
std::vector<std::shared_ptr<Bucket>> dir_;

可拓展哈希最大的特点就是多个指针可以指向同一个bucket，这也是为什么目录要存shared_ptr了。

当一个bucket存满了，会触发split操作。

在介绍split操作之前，我们先熟悉一下Extendible Hash的插入流程。

将一个键值对 (K,V) 插入哈希表时，会先用哈希函数计算 K 的哈希值 H(K)，并用此哈希值计算出索引，将 键值对放入索引对应的 bucket 中。

Extendible Hash 计算索引的方式是直接取哈希值 H(K) 的低 n 位。在这里，我们把 n 叫做 global depth。例如，K 对应的 H(K) = 1010 0010b，假设 global depth 为 4，则对应的 index 为 0010，即应将 V 放入 directory 里 index 为 2 的指针指向的 bucket 中。

刚初始化的Extendible Hash有一个directory page和一个bucket page，此时的global depth为0，因此不论H(K)得到什么结果，都会存进这个index为0的bucket。

哈希表的初始化

1
2
3
4
5
template <typename K, typename V>
ExtendibleHashTable<K, V>::ExtendibleHashTable(size_t bucket_size)
    : global_depth_(0), bucket_size_(bucket_size), num_buckets_(1) {
  dir_.emplace_back(std::make_shared<Bucket>(bucket_size, 0));
}

Bucket的初始化，local depth设为0

1
2
3
4
5
template <typename K, typename V>
ExtendibleHashTable<K, V>::Bucket::Bucket(size_t array_size, int depth) 
                        : size_(array_size), depth_(depth) {
  list_.clear();
}

假设bucket 的容量为 2，现在向表中插入 KV 对，仅关注 K。假设 H(K) = K。

首先插入 0 和 1。由于 global depth 为 0，所以 H(K) 计算出的 index 均为 0：

再插入 2。index 仍然为 0。而此时 bucket 已满，无法继续插入 2，则需要进行之前提到的 split 操作。这时的 split 包含如下几个步骤：

  1. 判断bucket的local depth是否等于global depth；如果等于，转到2；否则转到3
  2. local depth++，global depth++，directory 容量翻倍
  3. local depth++
  4. 创建一个新的 bucket
  5. 重新安排指针
  6. 重新分配 KV 对

初始时global depth = local depth = 0，因此global depth需要加1，directory翻倍。

前面提到对于一个bucket，可能有多个指针指向它。假如index为0的指针指向的bucket的local depth为1，global depth为3，如果此时有四个数0、2、4、6需要插入，分别计算得到H(K1) = 000b、H(K2) = 010b、H(K3) = 100b、H(K4) = 110b，因此它们应该分别被插入索引为0、2、4、6的指针指向的bucket，而四个哈希结果的相同点是最低一位都是0，index为0的指针指向的bucket的local depth为1，它只看最低的一位是否为0，000b、010b、100b、110b显然符合要求，因此这四个数都会存入index为0指针指向的bucket：

我们不难发现规律，对于一个bucket，如果其local depth为L，假设当前global depth为G=2，则一共有2^(G - L)个指针指向它。

当这个bucket满了的时候，需要一个更长的哈希值来区分bucket内的元素，比如当前bucket内的元素哈希后低四位都是1010b，为了能将这些元素进一步区分，需要将这些元素划分为1 1010b和01010b两组。

当L < G时，local depth还有增长的空间，只需要新建一个bucket，将其local depth设为L + 1，将这个2^(G - L)个指针分为两组，按要求分别指向原来的bucket或新建的bucket。

当L = G时，只有一个指针指向这个bucket，bucket内的元素的低G位完全相同，因此必须先将global depth加1，使bucket内的这些元素可以按低G+1位哈希值分为两组，插入到新建的bucket或保留在当前这个已满的bucket中。当global depth增加时，目录需要扩大，因为我们计算H(K)然后得到的低G位实际是就是目录下标而已。

因为今年的哈希表不需要考虑缩容，所以只要关注插入就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename K, typename V>
void ExtendibleHashTable<K, V>::Insert(const K &key, const V &value) {
  std::scoped_lock<std::mutex> lock(latch_);
  V v;
  auto ptr = dir_[IndexOf(key)];
  if (ptr->Find(key, v)) {
      ...
  }
  while (dir_[IndexOf(key)]->IsFull()) {
    SplitInsert(key, value);
  }
  dir_[IndexOf(key)]->Insert(key, value);
}

首先记得加锁

在插入前需要查一遍是否已经存在key/value，如果存在，需要先移除再插入，这是跑测试样例才发现的。

随后我们需要判断当前插入的bucket是否已满，如果是满的，需要进行分裂。

注意这里需要while而不能用if，因为有可能当前bucket里的元素在分裂后仍然可能放进同一个bucket里，如果bucket里存放了0010b和1010b两个key，bucket的局部深度为2，看后两位，即使扩容了之后局部深度达到3，看后三位，它们俩还是会分到这个bucket里。

还需要注意的是循环里要用dir_[IndexOf(key)]，而不能在之前用一个变量存IndexOf(key)，然后在循环里使用这个变量

1
2
3
4
5
template <typename K, typename V>
auto ExtendibleHashTable<K, V>::IndexOf(const K &key) -> size_t {
  int mask = (1 << global_depth_) - 1;
  return std::hash<K>()(key) & mask;
}

IndexOf函数的返回值与global_depth相关，而global_depth在分裂的时候是可能改变的，如果全局深度变了，那么计算得到的bucket的位置也就变了，然后导致错误。可以推导一下按0 1 2插入和按0 2 1插入的区别，这也是在跑测试时才发现的，因为多线程的原因，有时会按0 2 1的顺序插入，然后导致bug。

然后就是分裂的过程了

首先判断是否需要扩容

1
2
3
4
5
6
7
8
9
if (split_bucket_local_depth == GetGlobalDepthInternal()) {
  int cur_nums = 1 << global_depth_;
  global_depth_++;
  int origin = 0;
  for (int i = cur_nums; i < cur_nums * 2; i++) {
    dir_.emplace_back(std::shared_ptr<Bucket>(dir_[origin]));
    origin++;
  }
}

如果当前bucket局部深度等于全局深度，需要扩容，将指针数翻倍，然后将后面这部分指针依次赋值，建议将指针元素下标的十进制转换成2进制算一下为什么要像上面这样赋值了。

扩容后增加需要分裂bucket的局部深度

随后我们需要真正的新创建一个bucket，上面的扩容只是shared_ptr的复制，增加的只是引用计数罢了。

1
std::shared_ptr<Bucket> image_bucket = std::make_shared<Bucket>(bucket_size_, split_bucket_local_depth);

然后我们需要找到目录中某个位置的bucket A，A下标的2进制形式和当前bucket B下标的2进制表示，在B的局部深度的长度下只有最高位不同。

假设当前全局深度为4，B的下标表示为 1010b，满了需要分裂，局部深度由2变成3，那么看后三位是010b ，由于B内的元素本来只要看两位的，即10b，现在满了需要区分它们，所以需要将它们分为010b和110b两组，而这个110b就是我们要找的那个bucket A在目录里的位置

1
int image_bucket_index = 1 << (split_bucket_local_depth - 1) ^ split_bucket_index;

随后我们需要将指向A和B的指针重新分配，因为它们在分裂前肯定都是指向B的，现在需要将它们中的一半指向A，一半指向B。

1
2
3
4
5
6
7
8
9
10
int diff = 1 << split_bucket_local_depth;
for (int i = image_bucket_index; i >= 0; i -= diff) {
  dir_[i] = image_bucket;
  if (i < diff) {
    break;
  }
}
for (size_t i = image_bucket_index; i < dir_.size(); i += diff) {
  dir_[i] = image_bucket;
}

剩下的指向B的指针不需要改变指向。

随后将B的元素按哈希值插入两个bucket即可。

Task #2 - LRU-K Replacement Policy

这一部分是实现LRU-K淘汰策略。我的实现是用哈希表维护frame信息

1
std::unordered_map<frame_id_t, FrameInfo> frame_map_;
1
2
3
4
struct FrameInfo {
  std::list<size_t> timestamps_list_;
  bool is_evictable_{false};
};

frameInfo里保存当前frame存放的page的最近k次访问记录，这里隐含的意思就是timestamps_list_的长度最长为k，如果超过k次了，需要将最久远的那一次访问时间戳从队头移除，然后在队尾插入最新的这次时间戳。

然后需要一个is_evictable_来判断当前frame上的page是否可以淘汰，初值需要为false

LRU-K的淘汰策略，简而言之是先看有没有哪个frame的访问次数少于K次的，如果有，则挑出来，然后从它们之中淘汰最早访问时间最久远的，即比较这些frame的frameInfo的队头元素，然后淘汰队头元素最小的。如果每个frame都被访问了至少K次，那么就从所有的frame里淘汰最早访问时间最久远的。

这部分理解了淘汰流程后实现相对简单，但也有一些需要注意的：

  • replacer_size_是淘汰队列的最大长度，基本没有，反正超出了这个大小就抛异常。curr_size_才是真正的淘汰队列的长度。

  • SetEvictable函数，只有操作的frame的is_evictable_为true且set_evictable为false或者这两个正好相反时才需要处理curr_size。

  • Evict函数直接遍历哈希表就行了，我也想不到别的好方法…

Task #3 - Buffer Pool Manager Instance

这一部分没啥好说的，网上博客很多，配合注释很好理解。

对于New和Fetch，都是先从freelist找，没找到就淘汰一个frame（Fetch函数需要先查哈希表看有没有要找的page，有的话就直接返回了），所以可以抽出一个公共的函数以供调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
auto BufferPoolManagerInstance::GetFreeFrame(frame_id_t *frame_id) -> bool {
  if (!free_list_.empty()) {
    *frame_id = free_list_.front();
    free_list_.pop_front();
    return true;
  }
  frame_id_t victim_frame_id = -1;
  if (!replacer_->Evict(&victim_frame_id)) {
    return false;
  }
  Page *page = &pages_[victim_frame_id];
  page->pin_count_ = 0;
  if (page->IsDirty()) {
    disk_manager_->WritePage(page->GetPageId(), page->data_);
  }
  page_table_->Remove(page->GetPageId());
  *frame_id = victim_frame_id;
  return true;
}

还需要注意的一点是只有Fetch和New才需要调用RecordAccess，每次调用RecordAccess还记得调用一下SetEvictable，以防万一。