华子的博客
文章 标签 分类
华子的博客

Contents

Cmu15445 Extendible Hash Index

 included in CMU
   5804 words   12 minutes 

Extendible Hash Index

在此编程项目中，将使用可扩展哈希的变体作为哈希方案，在数据库系统中实现磁盘支持的哈希索引。

下图显示了一个可扩展哈希表，其中header页最大深度为 2，directory页最大深度为 2，存储bucket页最多包含两个条目。值被省略，并且键的哈希值显示在bucket页面中，而不是键本身。

./pics/structure.jpg#pic_center

该索引提供快速数据检索，无需搜索数据库表中的每一行，从而实现快速随机查找。实现应该支持线程安全的搜索、插入和删除（包括增长/收缩目录和拆分/合并桶）。

Read/Write Page Guards

在Buffer Pool Manager中， FetchPage和NewPage函数返回指向已固定页面的指针。固定机制确保页面不会被逐出，直到页面上不再有任何读写操作。为了表明内存中不再需要该页，程序员必须手动调用UnpinPage。

另一方面，如果程序员忘记调用UnpinPage ，该页将永远不会被从缓冲池中逐出。由于缓冲池实际上以较少数量的帧运行，因此将有更多的页面进出磁盘的交换。不仅性能受到影响，而且错误也很难被发现。

所以第一个任务将实现BasicPageGuard ，它存储指向BufferPoolManager和Page对象的指针。页面防护确保一旦超出范围，就会在相应的Page对象上调用UnpinPage 。请注意，它仍然应该公开一个方法，供程序员手动取消固定页面。

由于BasicPageGuard隐藏了底层Page指针，因此它还可以提供只读/写入数据 API，这些 API 提供编译时检查，以确保为每个用例正确设置is_dirty标志。

在Page类中，有用于多线程保护的latch方法。与取消固定页面类似，程序员可能会忘记在使用页面后解锁页面。为了缓解这个问题，您将实现ReadPageGuard和WritePageGuard一旦页面超出范围，它们就会自动解锁页面。

需要为所有BasicPageGuard 、 ReadPageGuard和WritePageGuard实现以下函数。

PageGuard(PageGuard &&that)

移动构造函数。拷贝构造函数和拷贝赋值的目的是将一个对象复制到另一个对象，而移动构造函数和移动赋值的目的是将资源的所有权从一个对象转移到另一个对象(这通常比复制成本低得多)。实现拷贝语义时需要使用const类型的左值引用作为形参，而实现移动语义时，需要使用非const的右值形参。

  1. 转移资源所有权（之后释放原来对象对资源的管理）。
1
2
3
4
5
6

BasicPageGuard::BasicPageGuard(BasicPageGuard &&that) noexcept
    : bpm_(that.bpm_), page_(that.page_), is_dirty_(that.is_dirty_) {
  that.page_ = nullptr;
  that.bpm_ = nullptr;
  that.is_dirty_ = false;
}

operator=(PageGuard &&that)

移动赋值运算符。

  1. 自我赋值检查。
  2. 释放被赋值对象当前持有的资源。
  3. 转移资源所有权。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

auto BasicPageGuard::operator=(BasicPageGuard &&that) noexcept -> BasicPageGuard & {
  if (&that == this) {
    return *this;
  }
  Drop();

  bpm_ = that.bpm_;
  page_ = that.page_;
  is_dirty_ = that.is_dirty_;

  that.page_ = nullptr;
  that.bpm_ = nullptr;
  that.is_dirty_ = false;
  return *this;
}

Drop()

Unpin and/or unlatch.

  1. 如果bpm_和page_不为nullptr，执行bpm_->UnpinPage。
  2. bpm_和page_置为nullptr。

~PageGuard()

析构函数。

  1. 调用Drop()。

还需要为BasicPageGuard实现以下升级功能。这些函数需要保证受保护的页面在升级过程中不会被从缓冲池中逐出。

UpgradeRead()

升级到ReadPageGuard。

  1. 如果page_不等于nullptr，上读锁RLatch()。
  2. 当前资源所有权转移给ReadPageGuard，将它返回。

UpgradeWrite()

升级到WritePageGuard。

  1. 如果page_不等于nullptr，上写锁WLatch()。
  2. 当前资源所有权转移给WritePageGuard，将它返回。

使用新的页面防护，在BufferPoolManager中实现以下包装器。

FetchPageBasic(page_id_t page_id)

  1. 调用FetchPage获取page，用this和page构造BasicPageGuard返回。

FetchPageRead(page_id_t page_id)

  1. 调用FetchPage获取page，若不为nullptr则上读锁RLatch()。
  2. 用this和page构造ReadPageGuard返回。

FetchPageWrite(page_id_t page_id)

  1. 调用FetchPage获取page，若不为nullptr则上写锁WLatch()。
  2. 用this和page构造WritePageGuard返回。

NewPageGuarded(page_id_t *page_id)

  1. 调用NewPage获取page，用this和page构造BasicPageGuard返回。

Extendible Hash Table Pages

每个可扩展哈希表头/目录/桶页对应于缓冲池取出的内存页的内容（即data_部分）。每次读取或写入页面时，必须首先从缓冲池中获取页面（使用其唯一的page_id ），重新解释将其转换为相应的类型，并在读取或写入页面后取消固定该页面。也就是利用任务1的PageGuard API来实现这个目标。

Header Page

标头页位于基于磁盘的可扩展哈希表的第一级，并且哈希表只有一个标头页。它存储指向目录页面的逻辑子指针。你可以把它想象成一个静态的一级目录页面。它有两个字段：

  • directory_page_ids_：目录页面 id 的数组
  • bucket_size_：标题页可以处理的最大深度，也就是最开始图中的header(2)。

需要实现：

  1. Init(uint32_t max_depth)：赋值max_depth_，directory_page_ids_数组中的值都置为INVALID_PAGE_ID。

  2. HashToDirectoryIndex(uint32_t hash)：把hash右移32-max_depth_位，保留最高max_depth_位返回。

  3. GetDirectoryPageId(uint32_t directory_idx)

  4. SetDirectoryPageId(uint32_t directory_idx, page_id_t directory_page_id)

  5. MaxSize()：左移max_depth_位，2的max_depth次方。

Directory Page

目录页位于基于磁盘的可扩展哈希表的第二层。它们中的每一个都存储指向桶页面的逻辑子指针，以及用于处理桶映射和动态目录增长和收缩的元数据。目录页面有以下字段：

  • max_depth_：标题页可以处理的最大深度，对应图中directory(2/2)。
  • global_depth_：当前目录全局深度，对应图中directory(2/2)。
  • local_depths_：桶页面局部深度的数组，对应图中directory下面表格的第二列，表示最后几位相同就在同一个桶。例如，图中00和10对应的局部深度为1，他俩最后一位相同，所以在同一个桶，但01和11的局部深度为2，他俩就不在同一个桶。
  • bucket_page_ids_：桶页面id的数组

部分需要实现的：

  1. Init(uint32_t max_depth)：赋值max_depth_，local_depths_数组中的值都值为0，bucket_page_ids_数组中的值都置为INVALID_PAGE_ID。
  2. HashToBucketIndex(uint32_t hash)：用与运算取hash最后global_depth_位。
  3. GetSplitImageIndex(uint32_t bucket_idx)：可以理解为计算兄弟桶的id，将该bucket_id的最高位反转得到的值返回。
1

return bucket_idx + (1 << (global_depth_ - 1));
  1. IncrGlobalDepth()：首先如果已经等于max_depth_，直接return。将目录增大小扩大一倍，操作相当于把现在的内容复制一遍给新增的那部分：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void ExtendibleHTableDirectoryPage::IncrGlobalDepth() {
  if (global_depth_ >= max_depth_) {
    return;
  }
  // double the size of the directory
  for (int i = 0; i < 1 << global_depth_; i++) {
    bucket_page_ids_[(1 << global_depth_) + i] = bucket_page_ids_[i];
    local_depths_[(1 << global_depth_) + i] = local_depths_[i];
  }
  global_depth_++;
}
  1. DecrGlobalDepth()：若已经等于0，直接return。否则减一。
  2. CanShrink()：GD等于零返回false。检查所有LD < GD。
  3. IncrLocalDepth和DecrLocalDepth：检查大小后直接增或减。

Bucket Page

桶页面位于基于磁盘的可扩展哈希表的第三层。它们是实际存储键值对的。有以下字段：

  • size_：桶中保存的键值对的数量。
  • max_size_：桶可以处理的最大键值对数量。
  • array_：大小为桶页面局部深度的数组，存储键值对数据。

部分需要实现的：

  1. Lookup(const K &key, V &value, const KC &cmp)：查找key，如果找到了把key(array[i],first)对应的值(array[i].second)赋给value，返回true。
  2. Insert(const K &key, const V &value, const KC &cmp)：查找key，如果已经存在，返回false。如果key不存在，则插入到数组最后，size增加，返回true。
  3. Remove(const K &key, const KC &cmp)：查找key，找到了就array_中后面的元素往前移一位，size减少，返回true。没找到返回false。

Extendible Hashing Implementation

实现对插入、搜索和删除的支持。要求要实现桶拆分/合并和目录增长/收缩。先了解一下实现关键点：

  • Empty Table：第一次创建一个空哈希表时，它应该只有一个唯一的Header Page，Directory pages 和 bucket pages按需创建。

  • Header Indexing：通过前面的部分应该已经明白了，使用最高有效位来索引标题页中的directory_page_ids_数组。

  • Directory Indexing：使用最低有效位来索引目录页中的bucket_page_ids_数组。

  • Bucket Splitting：如果没有空间插入，则必须分裂桶。

  • Bucket Merging：当桶变空的时候必须尝试合并。有一些方法可以通过检查桶及其分割映像的占用情况来更积极地进行合并，但这些昂贵的检查和额外的合并可能会增加抖动。这里为了使事情相对简单，用以下规则：

    1. 只能合并空桶。
    2. 仅当其分割图像具有相同的局部深度时，桶才能与其分割图像合并。
    3. 如果合并桶的新分割镜像为空，则应继续递归合并。

  • Directory Growing：意思就是目录会不断增长。

  • Directory Shrinking：仅当每个桶的局部深度严格小于目录的全局深度时才收缩目录。

DiskExtendibleHashTable

构造函数

  1. 主要是把传入的参数都赋值，然后用NewPageGuarded创建一个page guard，再用模版函数转换为ExtendibleHTableHeaderPage，执行init。
1
2
3

  auto header_guard = bpm->NewPageGuarded(&header_page_id_);
  auto header_page = header_guard.template AsMut<ExtendibleHTableHeaderPage>();
  header_page->Init(header_max_depth_);

GetValue

auto DiskExtendibleHashTable<K, V, KC>::GetValue(const K &key, std::vector *result, Transaction *transaction) const -> bool

  1. 从标头页开始搜索：利用FetchPageRead获取header_guard，同样的方式转换为header_page，用Hash函数处理key得到hash值，然后用HashToDirectoryIndex处理得到dir_index，即可找到目录页。这里就可以Drop掉header_guard了。
  2. 若得到的目录页的PageId为INVALID_PAGE_ID，则返回false。否则获取该目录页，HashToBucketIndex得到桶的索引。接着等到成功获取到桶页面切不为INVALID_PAGE_ID的时候再Drop掉dir_guard。
  3. 最后就可以在桶里找了，用桶的LookUp函数搜索，找到了就push_back到result中，Drop掉bucket_guard，返回true。没找到就返回false。

SplitBucket

auto DiskExtendibleHashTable<K, V, KC>::SplitBucket(ExtendibleHTableDirectoryPage *directory, ExtendibleHTableBucketPage<K, V, KC> *bucket, uint32_t bucket_idx) -> bool

  1. New一个新的页面作为新的桶页，并升级为WritePageGuard，如果得到的PageId为INVALID_PAGE_ID，说明分配失败，直接return false。
1

WritePageGuard split_bucket_guard = bpm_->NewPageGuarded(&split_page_id).UpgradeWrite();
  1. 得到分裂的新桶page，执行Init，因为它就是传入的那个bucket（执行分裂前该桶已经增加过LD了）的兄弟，所以它在目录中的索引就是GetSplitImageIndex(bucket_idx)，LD也与之相同，所以目录需要对新桶执行SetBucketPageId和SetLocalDepth。
  2. 由于桶的分裂，LD增加，使得之前存放的第一个桶里的内容需要拿出来重新分配到这两个桶里。用一个vector记录下第一个桶里的所有键值对，然后清空该桶，再根据每个键的最低有效位来选择放到哪个桶里。

Insert

auto DiskExtendibleHashTable<K, V, KC>::Insert(const K &key, const V &value, Transaction *transaction) -> bool

  1. 先执行GetValue(key, &v, transaction)，若找到了，说明键已存在，直接返回false。
  2. 同样从标头页开始找，区别就是这里用的是FetchPageWrite，因为涉及到写。通过hash_key在标头页中得到dir_page_id。
  3. 如果dir_page_id等于INVALID_PAGE_ID，说明目录页不存在，需要新分配目录页，并初始化，我们另起一个函数InsertToNewDirectory来处理，在下面给出。否则，Drop掉header_guard，获取目录页，根据目录页和hash_key得到桶的bucket_page_id。因为目录页之后会写，不着急Drop。
  4. 同理，如果bucket_page_id等于INVALID_PAGE_ID，另起一个函数InsertToNewBucket来处理。否则，拿到桶页，用桶页的Insert函数插入，如果成功就返回true。
  5. 如果失败说明桶已满，需要分裂桶。先检查LD已经等于GD，如果是，再检查GD是否大于等于MD，如果不是，可以IncrGlobalDepth，如果也是，说明满满的了，分不了，返回false。然后就可以增加这个桶的LD了，同时增加它兄弟的LD(例如最开始图中的00和10，要加一起加)。
  6. 执行到这里，就可以开始分裂了SplitBucket，分裂失败就返回false，否则Drop掉bucket_guard和dir_guard，然后递归return Insert(..)。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//  这里两个函数其实主要是在新建有效页，让对应的索引指向有效页面，最后还是要调用Insert来重新插入。 
template <typename K, typename V, typename KC>
auto DiskExtendibleHashTable<K, V, KC>::InsertToNewDirectory(ExtendibleHTableHeaderPage *header, uint32_t directory_idx,
                                                             uint32_t hash, const K &key, const V &value) -> bool {
  page_id_t dir_page_id = INVALID_PAGE_ID;
  // allocate a new directory page
  WritePageGuard dir_guard = bpm_->NewPageGuarded(&dir_page_id).UpgradeWrite();
  auto dir_page = dir_guard.AsMut<ExtendibleHTableDirectoryPage>();
  dir_page->Init(directory_max_depth_);
  header->SetDirectoryPageId(directory_idx, dir_page_id);
  auto bucket_idx = dir_page->HashToBucketIndex(hash);
  return InsertToNewBucket(dir_page, bucket_idx, key, value);
}

template <typename K, typename V, typename KC>
auto DiskExtendibleHashTable<K, V, KC>::InsertToNewBucket(ExtendibleHTableDirectoryPage *directory, uint32_t bucket_idx,
                                                          const K &key, const V &value) -> bool {
  page_id_t bucket_page_id = INVALID_PAGE_ID;
  // allocate a new bucket page
  WritePageGuard bucket_guard = bpm_->NewPageGuarded(&bucket_page_id).UpgradeWrite();
  auto bucket_page = bucket_guard.AsMut<ExtendibleHTableBucketPage<K, V, KC>>();
  bucket_page->Init(bucket_max_size_);
  directory->SetBucketPageId(bucket_idx, bucket_page_id);
  return bucket_page->Insert(key, value, cmp_);
}

Remove

auto DiskExtendibleHashTable<K, V, KC>::Remove(const K &key, Transaction *transaction) -> bool

  1. 同样用FetchPageWrite获取标头页，然后根据hash_key得到目录页的dir_page_id，Drop掉header_guard。如果得到的是INVALID_PAGE_ID，说明目录页不存在，直接return false。
  2. 一样的操作得到桶页，如果桶页PageId为INVALID_PAGE_ID，直接return false。否则用桶页执行Remove，此时Drop掉bucket_guard。如果Remove失败，返回false。
  3. 如果Remove成功，开始检测是否需要合并。一个大循环while(LD > 0)，内部先获取该桶的兄弟桶，然后判断如果俩兄弟LD不一样 or 两个都不是空桶，直接break出来。否则，这轮循环需要合并：bpm_->DeletePage掉那个空桶，LD减1，更新目录。
  4. 上一个循环结束后，合并完成。这里再一个循环，判断是否CanShrink()，如果可以就直接目录DecrGlobalDepth()，直到不能缩为止。Drop掉dir_guard。返回true。

Concurrency Control

多线程并发控制。注意实现过程中Fetch和Drop的时机。

./pics/cmu_project2.jpg

Updated on 2024-12-01
Read Markdown
 Database
Back | Home