可用资料这篇文章主要学习于:张凯的协程浅谈我的博客旅程也是在阅读了这位大神的博客开始的,我觉得这是一个很好的旅程,我逐渐开始学习整理,开源,回顾。之前的我主要是在知乎发已经写完的内容,自己的学习主要是 git + obsidian 的形式进行记录的,在阅读到这位大神的文章后,我搭建了自己的博客,然后开始学习更多的内容,实现文章归档、查询。他的文章里谈论了协程、协程的思想、协程分类,然后是原理剖析,协程实现,协程测试。整体比较的详尽,这里我的文章主要是进行一次对比,把腾讯的fiber库和代码随想录的coroutine进行对比然后学习。
协程是什么在软件开发中,我们常说进程、线程、协程,进程是操作系统分配资源的基本单位,线程是任务调度和执行的基本单位,而线程可以说是用户态下的线程,由程序员手动控制控制,同时,协程和用户态线程非常接近,用户态线程之间的切换不需要陷入内核,但部分操作系统中用户态线程的切换需要内核态线程的辅助。
概念
定义与本质
资源开销
调度方式
通信方式
适用场景
进程
操作系统资源分配的基本单位,拥有独立的内存空间。
高(独立内存、创建/销毁慢)
操 ...
CPP学习
未读关于分布式系统的知识分布式论文对分布式CA特性与CAP的讨论一个分布式的纵览博客
简单来说,分布式系统常用 CAP、BASE、PACELC 等理论描述可用性、一致性和延迟之间的取舍。在需要多个节点就同一结果达成一致时,会使用分布式共识算法;经典代表包括 Paxos、Raft,以及 ZooKeeper 使用的 ZAB 协议。此外,一致性哈希常用于数据分片和请求路由,以降低节点增减带来的数据迁移成本。
一致性理论主要用于描述/规定客户端能观察到什么,例如强一致性(常用线性一致性)、顺序一致性、最终一致性。
CAP理论CAP理论:一个分布式系统最多只能同时满足 一致性(Consistency)、可用性(Availability)和分区容错性(Partition tolerance) 这三项中的两项。CAP 定理的核心在于,在网络分区的情况下,我们需要对 C 和 A 做出相应的妥协,我们不可能完全满足 CA,但是我们可以合理控制 C 和 A 之间的比例让我们的应用/中间件正常提供服务,同时也尽量提升基础设施的稳定性来保障 P。
CAP 到底是什么CAP 定理表达了一个分 ...
CPP学习
未读整体阅读这份笔记,简单了解分布式以及一些架构,关于论文阅读部分没有整理,只作为架构知识点去看。关于论文的总结、阅读可以看这篇博客
Lecture 1为什么需要 分布式系统
利用分布式,获得更高的计算性能(并行运算、CPU、内存、磁盘)
提供容错,如果一台出现问题,可以切换到另一台服务器接手项目。
一些问题天然在空间上是分布的。例如银行转账,我们假设银行A在纽约有一台服务器,银行B在伦敦有一台服务器,这就需要一种两者之间协调的方法。
构建分布式系统来达成一些安全的目标。比如有一些代码并不被信任,但是又需要和它进行交互,因此可以通过一些特定的网络协议通信,从而限制了出错域。
分布式系统的挑战
并发问题:整体系统内存在多个部分,这些部分有在并发执行,因此会遇到并发编程和各种交互带来的复杂问题,以及时间依赖问题(同步、异步)。
局部错误:分布式系统有多个组成部分,再加上计算机网络,你会遇到一些意想不到的故障。如果你只有一台计算机,那么它通常要么是工作,要么是故障或者没电,总的来说,要么是在工作,要么是没有工作。而由多台计算机组成的分布式系统,可能会有一部分组件在工作,而另一部分组件停止运行, ...
p4项目记录在写数据库的页面置换、底层B+树结构、SQL的执行器优化器,我们终于到了数据库的最外层,也就是并发控制,实现MVOCC来为 BusTub 添加事务支持。
主要内容就是:
Timestamps (时间戳)
Storage Format (存储格式) + Sequential Scan / Tuple Retrieval (顺序扫描 / 元组检索)
MVCC Executors (MVCC 执行器)
Primary Key Index (主键索引)
终于要写完了啊…满打满算快写了两个月,马上就要写毕设了都…
Task #1 - Timestamps1.1 Timestamp Allocation这里主要是实现一个事务快照的效果,确保每个事务看到的快照是统一的。
例如:
1234事务1 (ts=1): 创建了 A1, B1, C1事务2 (ts=2): 修改了 A→A2, C→C2事务3 (ts=3): 修改了 A→A3, B→B3, 创建了 D→D3事务4 (ts=4): 修改了 A→A4, B→B4, C→C4
当**read_ts = 3,即事务3 ...
P3的源码真是太多了,看的我头晕,理解起来也比较困难,因为我不是科班生,我按照以下两位博主的专栏去整理、学习了一些内容。前两位做的都是2024Fall的project,第三位对p3做了详细的解析,第四位则是p3的开发者。
https://zhuanlan.zhihu.com/p/690034893
https://zhuanlan.zhihu.com/p/674080359
https://zhuanlan.zhihu.com/p/587566135 (p3的解决方案)
https://zhuanlan.zhihu.com/p/570917775 (在这个项目开始前,推荐阅读p3开发者迟先生的博客)
从project3开始,我们就要逐渐搭建一个数据库的架构了,p1、p2的B+树、缓冲池的内容是数据库的底层内容,而p3要实现的就是SQL查询的算子执行器,以及优化器。
可以参考CMU官网给出的这张流程图:
通过阅读源码 BusTubInstance::ExecuteSqlTxn ,可以看到整体的查询逻辑是:
Parser采用了 libpg_query 库将 sql 语句 pars ...
Task1 B+树的页面类你必须实现以下三个 Page 类来存储 B+ 树的数据。
B+Tree Page (B+树基础页面)
B+Tree Internal Page (B+树内部页面)
B+Tree Leaf Page (B+树叶子页面)
基本按照项目brief去写就行,同时2025Fall加入了墓碑缓存的机制。
墓碑缓存用来记录近期删除的缓冲区,存储LEAF_PAGE_TOMB_CNT个,当超出时,删除缓冲区最后一个元素
同时这里保存的是被”预约”删除的键的索引,直到这个索引在墓碑缓存中被删除,才会真正从叶子节点中移除。
在写Task1的时候我一直在想墓碑缓存什么时候触发,在B+树结构变化的时候墓碑缓存该做出什么操作,什么时候刷新,需不需要实现内部函数,这些都会在Task2实现。
需要注意的是:BPlusTreePage::GetMinSize()这个函数,ceil()与floor()的实现都是可以的,但是这个函数是给B+树提供分裂标准的,可以注意到采用ceil()与floor()会在后续产生不一样的效果,B+树的分裂合并的次数会不同。
二编:在跑Task2的数据时,如果叶子 ...
Task1 ARC算法实现这里需要实现五个函数:
Size() -> size_t:返回当前可被淘汰的 frame 数量。
SetEvictable(frame_id_t frame_id, bool set_evictable):设置某个 frame 是否可淘汰,并同步维护替换器大小。通常当某页的 pin count 变为 0 时,对应 frame 应标记为可淘汰。
RecordAccess(frame_id_t frame_id, page_id_t page_id):记录某个 page 在某个 frame 中被访问。Buffer Pool Manager 在页面被 pin 到 frame 后应调用它。
Evict() -> std::optional<frame_id_t>:按 ARC 规则选择一个 frame 淘汰。如果没有可淘汰 frame,返回 std::nullopt。
Remove(frame_id_t frame_id):如果 frame 存在且可淘汰,则从替换器中移除。Buffer Pool Manager 删除页面时会用到。其中最 ...








