CMU-15-445-Lab2记录

TASK1

实现HashTableDirectoryPage和HashTableBucketPage两个类

实现方法

这两个实现起来没有太多的难点

HashTableDirectoryPage

其中GetLocalHighBit是用来获取 local_depths对应的位的，这个函数主要是用来获取要分裂/合并页的pair页
其他函数就照着函数名来就行

HashTableBucketPage

这个类中，occupied_和readalbe_数组都是位图，所以当想法访问第i位的时候，需要处理为

uint32_t bit_index = bucket_idx / 8;
uint32_t bias = bucket_idx % 8;
return readable_[bit_index] | (1 << bias);

其他的也没有太多好说的，按照提示来就行

TASK2 HASH TABLE IMPLEMNETATION

Task2是要实现一个extendible hasing scheme的hash table，需要支持Insert，点搜索GetValue和删除Remove。在本次task中只需要完成Inset,GetValue,Remove就可以了，不要改动VerifyIntegrity
hash table需要要支持uni que和non-unique key。但是相同的value和key是不允许的。例如(key_0, value_0)与(key_0, value_1)是可以存在一个hash table中，但是(key_0, value_0)与(key_1, value_1)是不行的，如果出现这种情况，Insert需要返回false

实现细节

• Directory Indexing
  当插入到hash table的时候，需要使用lest-significant bits来索引directory。也可以使用most-significant bits，但是前者会简单一些
• Splitting Buckets
  当insert没有空间的时候，需要split一个bucket。比较推荐的方法是当insertion会导致一个page overflow的时候，再分裂。
• Merging Buckets
  当一个bucket空的时候必须进行Merging，为了让merging简化，task提供了一些规则：
  • 只有当buckets空的时候才merge
  • buckets只能和它localdepth相同的合并
  • buckets的depth为0的时候不能合并

实现方法

Insert

Insert是最复杂的函数

• 如果要插入的page没有满，那么就直接调用bucket_page的insert插入即可
• 如果满了且该页的depth和global depth相等，就说明directory 需要expand，expand的具体方法就是遍历directory_page的每个bucket，找出对应的pair bucket，然后让pair bucket指向相同的page id 即可
• 如果depth小于global depth，就不需要扩展
• 接下来是split bucket
• 大概思路是先将即将split的buket的数据放到一个vecotr里面，然后通过buffer_pool_manager_->NewPage获取新的页，最后将vector的数据分别放到这两个页里就行(注意之前的bucket的数据需要清空一下)

Remove

Remove较为简单，先调用bucket_page的Remove函数，然后判断这个page是否为空，如果为空了，就开始合并page
合并page首先将该bucket page的local_depth减一，然后删除掉对应的page，然后获取它的pair page，将pair page的对应page_id赋值给待merge的bucket_page，这样就完成了合并，最后遍历与这俩相关的bucket，将它们的page_id都赋值为刚刚的pair page的page_id

GetValue

直接调用bucket_page的GetValue就行了

TASK3 CONCURRENCY CONTROL

实现并发

Insert

先获取table_latch_的读锁，然后再获取bucket_page的写锁，判断bucket_page是否满，如果满了，释放table_latch_和bucket_page的锁，再获取table_latch_的写锁，和bucket_page的写锁，执行SplitInsert，并且重复执行，直到成功插入，如果执行SplitInset的时候，发现bucket_page未满（因为可能另一个线程删除了数据），直接执行bucket_page的inset就行了。

Remove

这里我的实现直接上了table_latch_的写锁，后续需要改进

GetValue

直接上table_latch_的读锁即可