CMU15-445 Project2

CMU15-445 Project2

Part I PAGE LAYOUTS

整个Hash Table分为directory和bucket。我们选择把directory和bucket都放在page里面。

设计逻辑

directory和bucket存的是不同的信息，但都是page。因为是page，所以对空间的要求比较高。需要计算好每个成员变量会占用的空间大小！不要动态分配内存。如果动态分配了内存，我们是把内存分在了堆上，那么当我们要将一个page写回到磁盘上时，并不会将堆上的信息写回，而是只写回这个page类中的成员信息。因此如果要把数据保存在page中，就要保存数据的实体，用一个定长数组。空闲需要提前计算好。

对于所有的操作，用最暴力的方法来实现，因为一个page也就4kb，直接枚举花不了多少时间。

Directory Page

Variable Name Size Description
page_id_ 4 bytes Self Page Id
lsn_ 4 bytes Log sequence number (Used in Project 4)
global_depth_ 4 bytes Global depth of the directory
local_depths_ 512 bytes Array of local depths for each bucket (uint8)
bucket_page_ids_ 2048 bytes Array of bucket page_id_t

一些小功能实现起来非常简单。

Bucket Page

这个类因为要存数据，而且要存的数据类型是未知的，所以定义成员变量要格外小心。一个occupied_数组用来标注每一位有没有被占用，一个readable_数组用来标注每一位的值能不能被读取。array数组存实际的数据。因为一个page中的空间非常重要，因此这里的readable和occupied数组都用char类型，即一个字节可以表示8位的数据，用位运算就可以得到第i位的值。

需要注意的是这里的array千万不能用动态分配内存扩容的方式，因为动态内存不会被写到磁盘上。这里用了一个trick：我们将array数组定义为0长度的，将这个成员变量放在类的最后面，就表示这个成员使用的空间一直到类的空间的末尾。除此之外，千万不能定义其他的成员变量！不然就会和前面的计算结果冲突。

函数设计

GetValue
1
2
3
4
5
6
7
8
9
10
11
12
template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::GetValue(KeyType key, KeyComparator cmp, std::vector<ValueType> *result) -> bool {
  bool flag = false;
  int size = ((BUCKET_ARRAY_SIZE - 1) / 8 + 1) * 8;
  for (int i = 0; i < size; ++i) {
    if (IsReadable(i) && cmp(key, array_[i].first) == 0) {
      result->push_back(array_[i].second);
      flag = true;
    }
  }
  return flag;
}
Insert
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::Insert(KeyType key, ValueType value, KeyComparator cmp) -> bool {
  // 如果找到了完全相同的，就返回false
  int size = ((BUCKET_ARRAY_SIZE - 1) / 8 + 1) * 8;
  int lastpos = -1;
  for (int i = 0; i < size; ++i) {
    if (IsReadable(i) && cmp(key, array_[i].first) == 0 && value == array_[i].second) {
      return false;
    }
    if (IsOccupied(i)) {
      lastpos = i;
    }
  }
  lastpos++;
  std::pair<KeyType, ValueType> temp = std::make_pair(key, value);
  array_[lastpos] = temp;
  SetOccupied(lastpos);
  SetReadable(lastpos);
  return true;
}

如果是要插入一个pair，最好是先用make_pair这个函数来初始化一个！

Remove
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_BUCKET_TYPE::Remove(KeyType key, ValueType value, KeyComparator cmp) -> bool {
  int pos = -1;
  int size = ((BUCKET_ARRAY_SIZE - 1) / 8 + 1) * 8;
  for (int i = 0; i < size; ++i) {
    if (IsReadable(i) && cmp(key, array_[i].first) == 0 && value == array_[i].second) {
      pos = i;
      break;
    }
  }
  if (pos == -1) {
    return false;
  }
  RemoveReadable(pos);
  return true;
}

如果删除了一个元素，为了不移动整个hash table，我们直接在这个位置上设一个墓碑。这个位置以后不能写入，也不能读出来了。不用真的把元素给删掉。

Part II Hash Table Implementation

设计逻辑

先把单线程的版本写好，再来加锁，最后优化锁（尽量让锁细一点）。

这里就涉及到和低层的交互了，会用到BufferPool来获取page。在写每个函数之前都先确认一遍和低层的交互是否有问题。比如这里我们创建了一个Page，必须先用reinterpret_cast来进行类型转换，转换为我们实现的page类型，不管是NewPage还是FetchPage最后都必须要UnpinPage，而且在DeletePage之前也必须要先UnpinPage。

在写每个函数前，先列个清单，想好这个函数的每一步要做什么。如果设计到helper function，就要先写好helper function。

搞清楚bucket_index和bucket_id的区别。索引和id的区别！

函数设计

构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename KeyType, typename ValueType, typename KeyComparator>
HASH_TABLE_TYPE::ExtendibleHashTable(const std::string &name, BufferPoolManager *buffer_pool_manager,
                                     const KeyComparator &comparator, HashFunction<KeyType> hash_fn)
    : buffer_pool_manager_(buffer_pool_manager), comparator_(comparator), hash_fn_(std::move(hash_fn)) {
  auto directory_page = reinterpret_cast<HashTableDirectoryPage *>(
      buffer_pool_manager_->NewPage(&directory_page_id_, nullptr)->GetData());
  directory_page->IncrGlobalDepth();
  page_id_t bucket_page_id_1 = INVALID_PAGE_ID;
  page_id_t bucket_page_id_2 = INVALID_PAGE_ID;
  buffer_pool_manager_->NewPage(&bucket_page_id_1, nullptr);
  buffer_pool_manager_->NewPage(&bucket_page_id_2, nullptr);
  directory_page->SetLocalDepth(0, 1);
  directory_page->SetLocalDepth(1, 1);
  directory_page->SetBucketPageId(0, bucket_page_id_1);
  directory_page->SetBucketPageId(1, bucket_page_id_2);
  buffer_pool_manager_->UnpinPage(bucket_page_id_1, true);
  buffer_pool_manager_->UnpinPage(bucket_page_id_2, true);
  buffer_pool_manager_->UnpinPage(directory_page_id_, true);
}

这里要注意的点就是这3个page一定要Unpin掉。

GetValue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_TYPE::GetValue(Transaction *transaction, const KeyType &key, std::vector<ValueType> *result) -> bool {
  table_latch_.RLock();
  auto directory_page = FetchDirectoryPage();
  auto bucket_page_id = KeyToPageId(key, directory_page);
  auto bucket_page = FetchBucketPage(bucket_page_id);
  AddBucketLatch(bucket_page, 'R');
  bool flag = bucket_page->GetValue(key, comparator_, result);
  buffer_pool_manager_->UnpinPage(directory_page_id_, false);
  buffer_pool_manager_->UnpinPage(bucket_page_id, false);
  table_latch_.RUnlock();
  RemoveBucketLatch(bucket_page, 'R');

  return flag;
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_TYPE::Insert(Transaction *transaction, const KeyType &key, const ValueType &value) -> bool {
  table_latch_.WLock();
  auto directory_page = FetchDirectoryPage();
  AddDirectoryLatch(directory_page, 'R');
  auto bucket_page_id = KeyToPageId(key, directory_page);
  auto bucket_page = FetchBucketPage(bucket_page_id);
  RemoveDirectoryLatch(directory_page, 'R');
  // 如果要插入的bucketpage中已经有完全相同的key-value了，不插入
  AddBucketLatch(bucket_page, 'R');
  if (bucket_page->FindElement(key, value, comparator_)) {
    RemoveBucketLatch(bucket_page, 'R');
    buffer_pool_manager_->UnpinPage(directory_page_id_, false);
    buffer_pool_manager_->UnpinPage(bucket_page_id, false);
    table_latch_.WUnlock();
    return false;
  }
  RemoveBucketLatch(bucket_page, 'R');
  AddDirectoryLatch(directory_page, 'W');
  AddBucketLatch(bucket_page, 'W');
  auto directory_index = KeyToDirectoryIndex(key, directory_page);
  auto limit_size = (1 << ((directory_page->GetLocalDepth(directory_index)) - 1));
  if (limit_size == static_cast<int>(bucket_page->GetSize())) {
    // 如果满了，要进行分裂
    auto last_local_depth = directory_page->GetLocalDepth(directory_index);
    auto new_bucket_page_id =
        SplitBucketPage(bucket_page, directory_page, bucket_page_id, KeyToDirectoryIndex(key, directory_page));
    if (directory_page->GetGlobalDepth() == last_local_depth) {
      directory_page->IncrGlobalDepth();
      UpdateDirectoryPage(directory_page, bucket_page_id, new_bucket_page_id);
    } else {
      UpdateLittleDirectoryPage(directory_page, bucket_page_id, new_bucket_page_id, last_local_depth + 1);
    }
    auto another_bucket_page_id = KeyToPageId(key, directory_page);
    if (another_bucket_page_id != bucket_page_id) {
      auto another_bucket_page = FetchBucketPage(another_bucket_page_id);
      AddBucketLatch(another_bucket_page, 'W');
      another_bucket_page->Insert(key, value, comparator_);
      buffer_pool_manager_->UnpinPage(another_bucket_page_id, true);
      RemoveBucketLatch(another_bucket_page, 'W');
    } else {
      bucket_page->Insert(key, value, comparator_);
    }
    buffer_pool_manager_->UnpinPage(directory_page_id_, true);
    buffer_pool_manager_->UnpinPage(bucket_page_id, true);
  } else {
    bucket_page->Insert(key, value, comparator_);
    buffer_pool_manager_->UnpinPage(directory_page_id_, false);
    buffer_pool_manager_->UnpinPage(bucket_page_id, true);
  }
  RemoveBucketLatch(bucket_page, 'W');
  RemoveDirectoryLatch(directory_page, 'W');
  table_latch_.WUnlock();

  return true;
}

先把一开始的框架写好，即取directory_page和bucket_page，把必要的信息都用变量给保存起来。然后就是一些常规操作，比如是否要分裂，分裂后目录的改变：先复制原来一半的指针，然后更新要指向新的bucket_page的指针。

Remove
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
template <typename KeyType, typename ValueType, typename KeyComparator>
auto HASH_TABLE_TYPE::Remove(Transaction *transaction, const KeyType &key, const ValueType &value) -> bool {
  table_latch_.WLock();
  auto directory_page = FetchDirectoryPage();
  AddDirectoryLatch(directory_page, 'W');
  auto bucket_page_id = KeyToPageId(key, directory_page);
  auto bucket_page = FetchBucketPage(bucket_page_id);
  auto directory_index = KeyToDirectoryIndex(key, directory_page);
  auto local_depth = directory_page->GetLocalDepth(directory_index);
  page_id_t another_bucket_page_id = 0;
  AddBucketLatch(bucket_page, 'W');
  if (!bucket_page->FindElement(key, value, comparator_) &&
      (!bucket_page->IsEmpty() || !CheckMerge(directory_page, directory_index, local_depth, &another_bucket_page_id))) {
    buffer_pool_manager_->UnpinPage(directory_page_id_, false);
    buffer_pool_manager_->UnpinPage(bucket_page_id, false);
    table_latch_.WUnlock();
    RemoveDirectoryLatch(directory_page, 'W');
    RemoveBucketLatch(bucket_page, 'W');
    return false;
  }
  bucket_page->Remove(key, value, comparator_);
  if (!bucket_page->IsEmpty() || !CheckMerge(directory_page, directory_index, local_depth, &another_bucket_page_id)) {
    buffer_pool_manager_->UnpinPage(directory_page_id_, false);
    buffer_pool_manager_->UnpinPage(bucket_page_id, true);
    table_latch_.WUnlock();
    RemoveDirectoryLatch(directory_page, 'W');
    RemoveBucketLatch(bucket_page, 'W');
    return true;
  }
  // try to merge
  Merge(nullptr, directory_page, bucket_page_id, another_bucket_page_id);
  if (CheckUpdateGlobalDepth(directory_page)) {
    // update global depth
    directory_page->DecrGlobalDepth();
  }
  buffer_pool_manager_->UnpinPage(directory_page_id_, true);
  buffer_pool_manager_->UnpinPage(bucket_page_id, true);
  table_latch_.WUnlock();
  RemoveDirectoryLatch(directory_page, 'W');
  RemoveBucketLatch(bucket_page, 'W');

  return true;
}

这里要注意合并的几个条件。合并其实也就是改指针。

UpdateDirectoryPage
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename KeyType, typename ValueType, typename KeyComparator>
void ExtendibleHashTable<KeyType, ValueType, KeyComparator>::UpdateDirectoryPage(HashTableDirectoryPage *directory_page,
                                                                                 page_id_t id0, page_id_t id1) {
  auto offset = (1 << (directory_page->GetGlobalDepth() - 1));
  auto global_depth = directory_page->GetGlobalDepth();
  // 先复制指针
  for (auto i = 0; i < offset; i++) {
    directory_page->SetBucketPageId(i + offset, directory_page->GetBucketPageId(i));
    directory_page->SetLocalDepth(i + offset, directory_page->GetLocalDepth(i));
  }
  offset <<= 1;
  for (auto i = 0; i < offset; i++) {
    if (directory_page->GetBucketPageId(i) == id0) {
      auto maxbit = ((i >> (global_depth - 1)) & 1);
      if (maxbit != 0) {
        directory_page->SetBucketPageId(i, id1);
      }
      directory_page->SetLocalDepth(i, global_depth);
    }
  }
}
SplitBucketPage
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
26
27
28
29
template <typename KeyType, typename ValueType, typename KeyComparator>
auto ExtendibleHashTable<KeyType, ValueType, KeyComparator>::SplitBucketPage(
    HashTableBucketPage<KeyType, ValueType, KeyComparator> *bucket_page, HashTableDirectoryPage *directory_page,
    page_id_t bucket_page_id, uint32_t bucket_index) -> page_id_t {
  auto local_depth = directory_page->GetLocalDepth(bucket_index);
  local_depth++;
  page_id_t new_bucket_page_id = INVALID_PAGE_ID;
  auto new_bucket_page = reinterpret_cast<HashTableBucketPage<KeyType, ValueType, KeyComparator> *>(
      buffer_pool_manager_->NewPage(&new_bucket_page_id, nullptr)->GetData());
  AddBucketLatch(new_bucket_page, 'W');
  new_bucket_page->Clear();
  std::vector<MappingType> elements;
  bucket_page->GetAllPairs(&elements);
  bucket_page->Clear();
  auto maskbits = (1 << local_depth) - 1;
  for (auto it : elements) {
    auto hash_val = (Hash(it.first) & maskbits);
    auto check_bit = ((hash_val >> (local_depth - 1)) & 1);
    if (check_bit) {
      new_bucket_page->Insert(it.first, it.second, comparator_);
    } else {
      bucket_page->Insert(it.first, it.second, comparator_);
    }
  }
  buffer_pool_manager_->UnpinPage(new_bucket_page_id, true);
  RemoveBucketLatch(new_bucket_page, 'W');

  return new_bucket_page_id;
}
CheckMerge
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <typename KeyType, typename ValueType, typename KeyComparator>
bool ExtendibleHashTable<KeyType, ValueType, KeyComparator>::CheckMerge(HashTableDirectoryPage *directory_page,
                                                                        uint32_t pid, uint32_t local_depth,
                                                                        page_id_t *pInt) {
  auto global_depth = directory_page->GetGlobalDepth();
  auto maxbit = (1 << (global_depth - 1));
  auto npid = (pid ^ maxbit);
  if (local_depth <= 1 || directory_page->GetLocalDepth(npid) != local_depth) {
    return false;
  }
  auto bucket_page_id = directory_page->GetBucketPageId(npid);
  if (bucket_page_id == directory_page->GetBucketPageId(pid)) {
    return false;
  }
  *pInt = bucket_page_id;
  auto bucket_page = FetchBucketPage(bucket_page_id);
  AddBucketLatch(bucket_page, 'R');
  bool flag = bucket_page->IsEmpty();
  buffer_pool_manager_->UnpinPage(bucket_page_id, false);
  RemoveBucketLatch(bucket_page, 'R');

  return flag;
}
Merge
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename KeyType, typename ValueType, typename KeyComparator>
void ExtendibleHashTable<KeyType, ValueType, KeyComparator>::Merge(Transaction *transaction,
                                                                   HashTableDirectoryPage *directory_page,
                                                                   page_id_t id0, page_id_t id1) {
  auto global_mask = directory_page->GetGlobalDepthMask();
  for (int i = 0; i <= static_cast<int>(global_mask); ++i) {
    auto bucket_page_id = directory_page->GetBucketPageId(i);
    if (bucket_page_id == id0) {
      directory_page->DecrLocalDepth(i);
    } else if (bucket_page_id == id1) {
      directory_page->DecrLocalDepth(i);
      directory_page->SetBucketPageId(i, id0);
    }
  }
  buffer_pool_manager_->UnpinPage(id1, true);
  buffer_pool_manager_->DeletePage(id1);
}

这里一定要先unpin掉page然后才能delete。

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家