数据库查询实现原理
这一篇文章主要参照 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…
理解 FLP-Impossibility 论文
FLP 这篇论文在分布式领域有着重要的作用,当然,这篇文章也写得晦涩难懂。这是第一篇我死扣每个字读下来的分布式论文,十分吃力,在此记录下,并且竟可能写的简单,希望能够帮助初入分布式计算的新人们够更加容易理解 FLP 论文。当然再怎么简单,数学的符号是跑不了的,但是不要害怕,一个一个字看下来即可。 论文原文的名字叫:Impossibility of …
理解 TCP
此文章仅为笔记,不推荐大家观看。 TCP Header 上面每一个方格代表 8 位,所以序列号有 4x8 = 32 位 源端口,目标端口:TCP 里面不包含 IP 地址,因为那是网络层(IPv4)应该干的事情。TCP 通过源 IP,端口,目标 IP,端口 4 个特征标识一个 TCP 连接。本地向远程80端口发起请求时,本地的端口是随机申请的。序列号…
操作系统并发
Terms Critical section: piece of code that accesses a shared resource.Race condition: 多个线程同时进去 critical section。Indeterminate:指程序在多线程情况下,程序结果不唯一。Mutual exclusion:排他。 Locks Eva…
CPU Scheduling Policies 调度算法
本文只写给自己,所以比较粗糙。 调度衡量指标 Turnaround time Turnaround time = 任务完成时间-任务到达时间$$T_{turnaround} = T_{completion} - T_{arrival}$$ Response time 如果通过 turnaround time 来衡量调度的算法,STCF 算法是最好的…
用 Java 实现一个可用的布隆过滤器(Bloom Filter)
布隆过滤器可以使用极少的空间来判断一个元素是否存在某一个集合中,本文不具体讨论布隆过滤器的原理,而是探讨如何实现一个可用的布隆过滤器。  GitHubSmith-Cruise/java-bloom-filter   本文代码提取自 Apache ORC 项目。 基本概念 这里附带一些链接,适合不了解布隆过滤器的人阅读。 https://zhuanl…