raft节点如何自动compact自己的entries日志对于一个长期运行的服务器来说，永远记住完整的Raft日志是不现实的。相反，服务器会检查Raft日志的数量，并不时地丢弃超过阈值的日志。一般来说，Snapshot 只是一个像 AppendEntries 一样的 Raft 消息，用来复制数据给 Follower，不同的是它的大小，Snapshot 包含了某个时间点的整个状态机数据，一次性建立和

Percolator事务模型原理TinyKV中的Percolator实现需要PD模块提供两个时间戳，一个是事务刚开始的时候需要一个时间戳在data列和lock列进行写入，还有一个时间戳是事物的提交时间戳。比如如果我们想实现一个客户端，我们首先需要联系PD模块获取region信息和一个开始时间戳，然后根据region对需要进行修改的KV进行分组，向每一个region所在的leader发送一个PreW

TinyKV中的Percolator代码实现

Query Execution从这一个实验开始，我们就正式进入了Bustub数据库的底层实现部分。这个实验完成后，我们利用我们实现的算子，可以在本机进行SQL语句的查询。 SQL语句的执行Parser 一条 sql 语句，首先经过 Parser 生成一棵抽象语法树 AST。Bustub 中采用了 libpg_query 库将 sql 语句 parse 为 AST。这个地方主要运用的是编译原理的内容

OverviewP4需要完成以下任务： Lock Manager：锁管理器，利用 2PL 实现并发控制。支持 REPEATABLE_READ、READ_COMMITTED 和 READ_UNCOMMITTED 三种隔离级别，支持 SHARED、EXCLUSIVE、INTENTION_SHARED、INTENTION_EXCLUSIVE 和 SHARED_INTENTION_EXCLUSIVE 五

Overview第一部分是设计好遍历B+树的迭代器，第二部分是实现B+树的并发。 B+树中的并发控制我们会使用一种特殊的加锁方式，叫做 latch crabbing。顾名思义，就像螃蟹一样，移动一只脚，放下，移动另一只脚，再放下。基本思想是： 1. 先锁住 parent page， 2. 再锁住 child page， 3. 假设 child page 是安全的，则释放 parent page 的

Overview写这篇文章的目的主要用于B+树实现过程中的一些总结，不会太多涉及代码的实现，主要介绍思路和结构。个人感觉这是整个课程实验中最难的一个实验了。早就听说数据库中常用B+树来做索引，现在终于有机会直观地了解这一部分了。 这篇文章主要介绍CheckPoint1的内容。下一篇文章介绍B+树中的并发。 B+树的结构B+树中有两种节点，一种是InternalPage，另一种是LeafPage。这

Extendible Hash Table我们先来了解一下什么是Extendible Hash Table。Extendible Hashing 有两个主要的部分 目录(Directories): 即我们的哈希数组,目录的一个slot(即一个元素,下标)存储一个指向叶的地址的指针。还有一个id被分配给每个目录项,当目录扩张的时候,id就会发生改变。 叶(bucket): 桶用来存储散列后的数据(

前置知识书到用时方恨少，这个Project虽说前缀树我在之前就学过，但C++的基础知识还是很不牢固，所以先把一些需要用的知识点要在这里再记一下。 左值引用和右值引用 左值是可以放在赋值号左边的，左值必须要在内存中有实体。 右值出现在赋值号右边；右值可以在寄存器也可以在内存中。 123int num = 10;int &b = num;int &c = 10; // 错误 上面。n