应届生如何半年找到一份数据库内核开发的工作
匆匆忙忙的春招告一段落了,自己最后也找到了数据库内核方向的工作,希望以后能在数据库领域有一番建树。 在这篇文章中我将我的学习路径贴出来,帮助对这方面有兴趣的人提供一点指南,当然也只是仅供参考。 其实如果按照我的路径学习,我个人觉得可以找的工作不光仅限于数据库这块,像分布式存储,分布式xx,基础架构等都是可以的(不含操作系统)。 个人背景 在开始 g…
Raft 成员变更的相关问题
之前一直没有深入了解过 Raft 的成员变更,实现也就是在 TinyKV 中搞了一个单步成员变更,以至于在面试的时候,甚至想当然以为成员变更一定要被 apply 后才生效,结果就被挂了。故这里重新梳理一遍,内容是到处扒来的,不一定正确。 直接成员变更存在的问题 如果我们把成员变更当做和普通日志一样,在 apply 时直接应用,可能会使得整个集群产生…
分布式原子提交协议大全
在单机上实现原子提交没啥好说了,可以通过 logging 来保证,但是在分布式系统中,情况就不简单。很多人会把 2PC/3PC 这类算法叫做分布式一致性算法,但是我个人觉得它们叫原子提交协议更合适(atomic commitment protocol ),因为它们只是把多个操作融合为一个原子操作,要么全部成功,要么全部失败。具体可以看 https:…
2021 CMU 15-445 实验笔记
陆陆续续终于把 CMU 15-445 刷完了(中间插了个 TinyKV),这也算是自己数据库的启蒙之课。编码耗时共计 98 小时 43 分钟。 我个人给整个项目难度评级:Project 1 < Project 4 < Project 3 << Project 2。其中 Project 2 难度最大,主要没啥参考资料,今年的是…
数据库并发控制原理
数据库的事务 transaction (txn)很有搞头,特此特别记下这篇笔记,方便自己的回顾,如有错误,请指正。 Transaction 数据库事务以 Begin() 开始,以 Commit() 或 Abort() 结束。事务需要满足 ACID。 ACID Atomicity A:Atomicity 原子性,即多个操作合并在一起,如一个原子一样不…
数据库查询实现原理
这一篇文章主要参照 CMU 15-445 Project 3 的 Query Execution 章节,特此记录。 本文所有的 Cost 均为 IO Cost。 数据库操作主要包含如下三大类: Access:Sequential ScanModifications: Insert, Update, DeleteMiscellaneous:Neste…
Talent Plan TinyKV 白皮书
前言 最近参加了 PingCAP 的 2021 Talent Plan KV 学习营,大概就是在不到两个月的时间里完成 TinyKV。之前做完了 MIT 6.824 就被人安利过,不过那时候看了一眼 README 就被劝退了,太复杂了。好在项目最后是完成了,就是拿了个低分,挺抑郁的。 正确性:4 个项目的正确性接近了 100%,意料之中,自己是跑了…
Extendible Hash Table 算法实现
Extendible Hash Table 属于动态哈希的一种,网上有很多关于它的介绍,但是真的在实现它的时候,或多或少有着很多问题。网上很多教程光讲怎么扩容,不讲收缩,而且网上很多都是概念性的东西,不讲代码实操。因 CMU 15-445 的课程需要,自己捣鼓了一下算法流程,这里分享一下。 在看之前请自行了解 Extendible Hash Tab…
2021 CS144 实验笔记
计算机网络一直是自己的薄弱项,因为感觉知识都是死记硬背,背完就忘。那就索性学一下 CS144,顺带梳理一下整个的网络流程。这篇笔记不光记录实验过程,也会记录相关的网络笔记。 整个项目编码耗时 51 小时 21 分钟。 整个实验的的顺序是自顶向下,正好对应《计算机网络 自顶向下》这本书。 如果要答案源码,直接私信或发邮件。 网络分层 按照五层网络模型…
2021 MIT 6.824 札记
满打满算花了 25 天完成了 2021 MIT 6.824 的 4 个 lab,这里记录下自己遇到的坑和设计思路,为后续者参考。 这里个人给的难度评级是 Lab 2 > Lab 4 >> Lab 3 = Lab 1。 这里我就简单的记录下自己的设计思路和遇到的坑。 如果大家想要参考更加具体的代码实现,可以看看 https://gi…