15445 Project 1

Buffer Pool Manager

Task 1

先看官网给出的描述：

在该项目的第一部分中，您将构建一个通用哈希表，使用无序的桶来存储唯一的键/值对。您的哈希表必须支持插入/删除键/值条目的能力，而无需指定表的最大大小。您的表需要根据需要逐步增长，但您不需要将其缩小。也就是说，您不需要实现缩小或压缩哈希表的支持。您还需要支持检查哈希表中是否存在一个键，并返回其相应的值。

我们鼓励您首先手动演示一些拆分和目录增长情况的小例子，然后再开始实现。

您必须在项目源代码中的指定文件中实现您的哈希表。您只允许修改哈希表头文件（src/include/container/hash/extendible_hash_table.h）及其相应的实现文件（src/container/hash/extendible_hash_table.cpp）。您不需要修改任何其他文件。您不得在实现中内部使用另一个内置哈希表。您必须在ExtendibleHashTable类中实现以下函数：

  • Find(K，V)：对于给定的键K，请检查它是否存在于哈希表中。如果存在，则将其相应值的指针存储在V中并返回true。如果键不存在，则返回false。
  • Insert(K，V)：将键/值对插入哈希表中。如果键K已经存在，则用新值V覆盖其值并返回true。如果无法将键/值对插入桶中（因为桶已满且该键不是更新现有对），请在重试之前执行以下步骤： 如果桶的局部深度等于全局深度，则增加全局深度并将目录的大小加倍。增加桶的局部深度。拆分桶并重新分配目录指针和桶中的kv对。某些实现将在插入后如果桶变满就拆分桶。但是对于这个项目，请检测桶是否溢出并在插入之前执行拆分。
  • Remove(K)：对于给定的键K，请从哈希表中删除其相应的键/值对并返回true。如果键K不存在于哈希表中，则返回false。
  • GetGlobalDepth()：返回整个哈希表的当前全局深度。
  • GetLocalDepth(dir_index)：返回给定目录索引指向的桶的当前局部深度。
  • GetNumBuckets()：返回哈希表中分配的桶的总数。

您可以使用提供的IndexOf(K)私有函数来计算给定键散列到的目录索引。此外，我们提供了一个Bucket嵌套类，表示可扩展哈希表中的桶。首先按照代码文档完成Bucket类的TODO，可以更轻松地实现ExtendibleHashTable API。但是您可以随意编写自己的内部类/辅助函数。

您需要确保哈希表中的所有操作都是线程安全的，使用std::mutex。您需要决定如何保护数据结构。

Extendible Hash Table与正常的线性哈希不同，我们采取分裂bucket的方式而不是让bucket线性增长，多个哈希槽位置可以指向同一个桶链。在拆分时重新整理桶中的条目，并增加要检查的位数。具体的来说，Extendible Hash Table的结构中会维护一个global depth来记录哈希表中最长的位数，对每个bucket结构会维护一个local depth，来记录该bucket的寻址位数，当bucket进行分裂时，local depth会增加，如果local depth超过了global depth，那么global depth会同时加一。

我们采取自底向上的方法进行实现，先来介绍Extendible Hash Table中Bucket的实现：

  • Bucket中维护一个(key,value)pair的list来存储数据，size_来记录Bucket中(key,value)pair的最大个数(2^depth_)，depth_来记录上述中记录local depth的大小

  • Find(k,v)：在Bucket中给定key寻找value的方法，该方法实现较简单，对list中的pair进行遍历，如果寻找到相等的key则将对应的value返回并返回true，若没找到则返回false

  • Remove(k)：在Bucket中给定key删除对应的(key,value)pair，与Find类似，直接遍历，若找到相等的key则删除并返回true，否则遍历完成并返回false

  • Insert(k,v)：在Bucket中插入新的(key,value)pair，如果list为空，则直接插入并返回true；否则需要先遍历Bucket寻找是否该key已存在，若已存在更新即可；若不存在则需要判断Bucket是否已满，若未满直接插入并返回true即可；若已满需要返回false来通知上层需要分裂该Bucket

接下来我们介绍Extendible Hash Table的实现：

  • Extendible Hash Table维护一个Bucket的vector，一个控制并发操作的锁latch，一个记录Bucket数量的变量，记录Bucket最大size的变量以及一个global depth
  • IndexOf(key)&IndexOf(key,depth)：这两个函数都是寻找Bucket index的函数，与PPT中的寻址方法相同，直接匹配前depth/global depth的位数来寻址即可
  • GetDepth一类的函数(包括local depth/global depth等)：这类函数获取depth的值，需要注意的是，depth的值是会因为Bucket的分裂而动态变化的，由于我们需要考虑并发操作，所以在访问无论是global depth还是local depth时都需要对latch进行上锁，再进行访问；访问local depth时就到对应的Bucket中读取数据即可
  • Find(k,v)：该函数在哈希表中寻找key对应的value，同样的，由于Bucket中的数据在动态变化，所以在查找前需要对整个哈希表上锁，然后对key进行对应的Bucket编号查找，找到对应的Bucket后调用Bucket的Find函数进行查找即可
  • Remove(key)：与Find(k,v)同理
  • Insert(k,v)：该函数向哈希表中插入一个(key,value)pair，这个函数应该是哈希表中最复杂的一个函数了。首先由于我们需要对表中数据进行修改，所以需要对整个哈希表上锁；在插入之前，我们需要对Bucket是否已满进行判断，若已满则需要进行分裂处理，(需要注意的是，在极端情况下分裂处理是需要递归进行的，因为我们分裂的方法是继续看key的下一位bit的值，而此时有可能Bucket中下一位bit都是相同的，这时候就需要递归进行处理，但这样的递归总有尽头，直到剩余bits的位数小于等于Bucket中个数时，一定会出现不满的Bucket，这时即可进行插入)
    • 不需要分裂(要插入的Bucket非满)：直接调用Bucket的插入进行插入即可
    • 需要分裂(要插入的Bucket已满)：若目标Bucket的深度已经达到global depth，则需要扩展整个哈希表的global depth并扩大Bucket vector；然后建两个新Bucket，把原Bucket中的元素按照key下一位bit的不同分别插入到两个Bucket中，最后把两个Bucket按照索引位的不同放到Bucket vector的相应位置中

Task 2

先看官网给出的描述：

该组件负责跟踪缓冲池中页面的使用情况。您将在src/include/buffer/lru_k_replacer.h中实现一个名为LRUKReplacer的新类，以及其相应的实现文件src/buffer/lru_k_replacer.cpp。请注意，LRUKReplacer是一个独立的类，与其他Replacer类无关。您只需要实现LRU-K替换策略，不需要实现LRU或时钟替换策略，即使有相应的文件也不需要。

  • LRU-K算法会淘汰最长时间未被访问的页框。后向k距离是指当前时间戳与第k次之前访问的时间戳之间的时间差。如果一个页框历史访问次数小于k，则将其后向k距离设为正无穷。当有多个页框的后向k距离都是正无穷时，替换器会淘汰时间戳最早的那个页框。

  • LRUKReplacer的最大大小与缓冲池的大小相同，因为它包含了BufferPoolManager中所有页框的占位符。然而，在任何时刻，替换器中不是所有的页框都被视为可淘汰的。LRUKReplacer的大小由可淘汰的页框数量表示。LRUKReplacer被初始化为不含任何页框。只有当一个页框标记为可淘汰时，替换器的大小才会增加。

您需要实现课堂上讨论的LRU-K策略。您需要实现以下方法：

  • Evict(frame_id_t*)：从替换器中淘汰后向k距离与其他可淘汰的页框中最大的那个页框。将页框的id存储在输出参数中并返回True。如果没有可淘汰的页框，则返回False。

  • RecordAccess(frame_id_t)：记录给定页框id在当前时间戳下被访问。在BufferPoolManager中固定页面后，应调用此方法。

  • Remove(frame_id_t)：清除与页框关联的所有访问历史记录。仅在BufferPoolManager中删除页面时调用此方法。

  • SetEvictable(frame_id_t, bool set_evictable)：此方法控制页框是否可淘汰。它还控制LRUKReplacer的大小。当页的引用计数达到0时，对应的页框被标记为可淘汰，并增加替换器的大小。

  • Size()：此方法返回当前LRUKReplacer中可淘汰的页框数量。

LRU-K算法简介：

LRU-K算法是一种页面替换算法，它通过记录缓存数据被访问的历史来判断哪些数据最有可能被淘汰。在LRU-K算法中，K代表最近使用的次数。与LRU算法不同的是，LRU-K算法将“最近使用过1次”的判断标准扩展为“最近使用过K次”，从而解决了LRU算法中可能出现的“缓存污染”的问题。

LRU-K算法需要维护一个访问历史队列，用于记录缓存数据被访问的历史。当一个数据第一次被访问时，它会被加入到访问历史队列中。如果一个数据在访问历史队列中的访问次数没有达到K次，则按照一定规则（例如FIFO或LRU）淘汰。当一个数据的访问次数达到K次后，它将被移到缓存队列中，并缓存此数据。缓存队列会按照时间排序，以便淘汰最久未使用的数据。

当需要淘汰数据时，LRU-K算法会淘汰缓存队列中排在末尾的数据，即“倒数第K次访问离现在最久”的数据。当一个数据再次被访问时，它会被重新排序，以确保最近使用的数据总是在缓存队列的前面。

总的来说，LRU-K算法是一种比较复杂的页面替换算法，但它能够更准确地判断哪些数据最有可能被淘汰，从而提高了缓存系统的性能。

具体实现方法：

  • LRUKReplacer维护的数据包括：一个记录每个页对应的访问次数的map；上文中提到的一个历史队列、一个缓存队列；缓存队列和历史队列都需要的一个页号对应迭代器的map；一个记录每个页是否可以被换出的map；记录LRU-K的K值；此时包含的页数size；一个保持安全并发操作的锁latch(需要强调的是，LRU-K替换器本身就是一个公共资源，所以在执行任何操作时都需要加锁，下文的操作中不再赘述)；一个replacer_size
  • Evict(frame_id_t*)：该函数换出LRU-K策略选出的页，若无页可选直接返回false；在有页可选的情况下，我们优先从历史队列中挑选可被换出的页，直接从历史队列队尾回溯选择，若可换出则在历史队列中将该项移除，历史队列的map中溢出，记录访问次数设置为0，并设置不可换出并减少当前的size，返回true；若历史队列中无可换出的页，则遍历缓存队列(遍历方向相同)，操作也相同；若均无可换出的页，则返回false
  • RecordAccess(frame_id_t)：若frame_id超过了replacer的size，说明是非法页框号，需要特殊处理，否则开始访问记录，先增加对应frame的访问计数，若访问计数达到k次则需要在缓存队列/map中删除，并添加到历史队列/map中；若访问计数大于k次，则需要将其移到队尾；若访问计数未达到k次，则需要移动到缓存队列的队尾
  • SetEvictable(frame_id_t, bool set_evictable)：该函数设置该frame是否可以被换出，若可换出则set_evictable=true，反之为false，同理，若frame_id超过了replacer的size，说明是非法页框号，需要特殊处理，若访问次数为0，则不需要设置；若此时状态不可换出并设置可换出，则需要增加当前的size；若次数状态可换出且要设置不可换出，则需要减小size；最后设置是否可换出为set_evictable即可
  • Remove(frame_id_t)：若frame_id超过了replacer的size，说明是非法页框号，需要特殊处理，否则开始执行删除，若访问次数为0可直接返回无需删除；若不可换出则直接抛出异常；剩下的工作就是在历史/缓存队列和map中删除对应的项，减小当前size，初始化count和是否可换出即可
  • Size()：由于我们维护了当前的size，所以直接返回即可

Task 3

先看官网给出的描述：

最后，您需要在系统中实现缓冲池管理器（BufferPoolManagerInstance）。BufferPoolManagerInstance负责从DiskManager中获取数据库页面并将其存储在内存中。当需要为新页面腾出空间时，BufferPoolManagerInstance也可以将脏页面写回磁盘，或者在明确指示时进行写回。

为确保您的实现与系统的其余部分正确配合，我们将为您提供一些已填充的函数。您也不需要实现实际读写数据到磁盘的代码（在我们的实现中称为DiskManager），我们将为您提供该功能。

系统中的所有内存页面都由Page对象表示。BufferPoolManagerInstance不需要理解这些页面的内容。但是，作为系统开发人员，了解Page对象只是缓冲池中内存的容器，因此不属于唯一的页面是很重要的。也就是说，每个Page对象包含一块内存块，DiskManager将使用该内存块作为从磁盘读取的物理页面内容的位置。BufferPoolManagerInstance将重用相同的Page对象来存储数据，因为它在磁盘和内存之间来回移动。这意味着同一个Page对象可能在系统的整个生命周期内包含不同的物理页面。Page对象的标识符（page_id）跟踪它包含的物理页；如果Page对象不包含物理页，则必须将其page_id设置为INVALID_PAGE_ID。

每个Page对象还维护一个计数器，用于记录“固定”该页面的线程数。您的BufferPoolManagerInstance不允许释放被固定的Page。每个Page对象还跟踪它是否是脏的。您的任务是在取消固定Page之前记录页面是否已修改。在可以重复使用该对象之前，您的BufferPoolManagerInstance必须将脏Page的内容写回磁盘。

您的BufferPoolManagerInstance实现将使用您在先前步骤中创建的ExtendibleHashTable和LRUKReplacer类。它将使用ExtendibleHashTable来映射page_id到frame_id的表。它还将使用LRUKReplacer来跟踪Page对象的访问时间，以便在必须释放帧以为从磁盘复制新的物理页面时决定哪个页面被淘汰。

您需要在源文件（src/buffer/buffer_pool_manager_instance.cpp）中实现头文件（src/include/buffer/buffer_pool_manager_instance.h）中定义的以下函数：

  • FetchPgImp(page_id)
  • UnpinPgImp(page_id, is_dirty)
  • FlushPgImp(page_id)
  • NewPgImp(page_id)
  • DeletePgImp(page_id)
  • FlushAllPagesImpl()

对于FetchPgImp函数，如果在空闲列表中没有可用页面且所有其他页面当前都被固定，则应返回nullptr。FlushPgImp应该无论页面的固定状态如何都会刷新页面。

对于UnpinPgImp，is_dirty参数跟踪页面在固定期间是否被修改。

AllocatePage私有方法为BufferPoolManager提供一个新的唯一页面标识符，当您想在NewPgImp()中创建新页面时使用。另一方面，DeallocatePage()方法是一个仿真在磁盘上释放页面的无操作，您应该在DeletePgImp()实现中调用此方法。

BufferPoolManager的具体实现方法如下：

  • BufferPoolManager要维护的数据包括：一个常量缓冲池的大小；一个原子页id记录下一个页面id；一个常量记录哈希表的Bucket大小；一个存储页面的数组；一个从物理页号映射到缓冲池帧号的可扩展哈希表；一个LRU-K替换器；一个用来管理并发操作的锁(与Task 2相同，每个操作都在改写公共资源BufferPoolManager的内容，所以几乎每个操作都需要加锁，后面不特殊说明的话就说明该操作是需要上锁的)；一个list记录空闲帧；一个磁盘管理器来负责将数据向磁盘出读入/写回
  • NewPgImp(page_id)：该函数在缓冲池中新建一个page，若空闲帧list非空，则存在空闲帧，可以在空闲帧中存放page，从队尾取出一个空闲帧；若空闲帧list为空，则不存在空闲帧，先判断是否所有页面均已被占用(pin count > 0)，若是则无法新建，返回false，若不是则换出一个未被任何进程pin过的页面(若该页为脏页则需要disk manager将内容写回磁盘)，从页表中删除原page并添加新page并将该页在BufferPoolManager中进行初始化即可，而且需要注意的是，我们需要在此处对该帧进行RecordAccess，因为我们对该帧进行了替换操作(无论之前是否在空闲帧list中)
  • FetchPgImp(page_id)：该函数从磁盘中调入一个页号为page_id的页，若该页未在BufferPool中，需要找到一个帧(优先考虑空闲帧，最大化缓冲池的利用率)，找到可换的帧后将页换出(若该页为脏页则需要disk manager将内容写回磁盘)，重新初始化刚刚选取的帧，调用disk manager将该页换到帧中并设置页表项即可；若该页已在缓冲池中(注：换回页后也同样需要这个操作)，该操作需要记录RecordAccess，设置pin count表明上级调用正在使用该page，并将该page返回即可
  • UnpinPgImp(page_id, is_dirty)：该函数取消页的pin状态，is_dirty参数记录该页是否被修改，首先需要确定该页是否在缓冲池中，若该页不在缓冲池中或pin count <= 0，则无需取消pin状态，直接返回false即可；否则将该页维护的pin count--即可；若pin count变为0，则需要设定可被替换状态；若is_dirty参数为true，则需要改变该页是否为脏页的状态，需要注意的是，如果is_dirty为false则不需要执行任何操作，因为有可能其他进程修改了页面，该进程未进行改变，最后返回true即可
  • FlushPgImp(page_id)：该函数的作用是将给定页号的页写回磁盘，若该页不在缓冲池中，则无需做任何操作，直接返回false即可；若该页对应的帧号不合法也返回false；否则为合法情况，将页写回磁盘并设置is_dirty为false并返回true即可
  • FlushAllPagesImpl()：该函数将所有页写回内存，遍历页数组执行FlushPgImp即可，需要注意的是这个操作无需上锁，因为每个FlushPgImp都会上锁并进行写操作，而且按照并发执行的语义来说，写回后的页就可以为后续进程所用，无需对写回后的page进行阻塞了
  • DeletePgImp(page_id)：该函数删除参数页号对应的页，若不在缓存池中则无需删除，直接返回true即可；若在缓冲池中但仍处于pin状态，则无法删除，返回false；若在缓冲池中但处于unpin状态，则从页表中删除该页，执行初始化并将帧放回空闲帧list即可
database
database 15445

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！