Catalog 关系型数据库存储在 bind、optimism 的时候需要知道相关的系统元信息，这些 metadata 被存储在 Catalog 中。RisingLight 相关代码在 src/catalog 中。由于 RisingLight 比较简单，所以 Catalog 中没有存储太多的东西，只存储了 Column、Table、Scheme 之间的关系。 RisingLight 中 Catalog 的视图如下所示： 123456789101112131415 +------+ | Root | +------+ / \+---------+ +---------+| Scheme1 | ... | Schemen |+---------+ +---------+ / \ +--------+ +--------+ ...

RisingLight 是一个教育用的 OLAP 数据库，它采用列式存储，利用 merge-tree 结构，将多个列组合在一起，可以实现关系模型。对 RisingLight 的相关描述可以在这里查看。 为什么要学习 RisingLight，有以下几个(个人)原因 RisingLight 是一个教育用的 OLAP 数据库，因此不会太复杂。而且该有的功能(比如parse,bind,optimizer,execute)都有，而且与一些知名的系统有许多共同点，很适合学习 代码量不是很大，使用了很多第三方库，但是还是能从中了解到相关的过程，阅读时不会过度陷入细节中 使用 Rust 编写，在阅读过程中可以学习 Rust 文档齐全 Architecture Overview SQL 是一种声明式语言，也就是说它只说明了它要执行什么操作，但是没有说明要怎么执行。所以，为了执行 SQL 语句，我们需要对其进行解析，才能知道该如何执行。RisingLight 的文档描述了它的 architecture SQL 经过 Parser 解析器解析，生成抽象语法树 AST。RisingLight 中使用 s ...

system call 三个主要目的： 为硬件提供一层抽象，比如为读写不同类型的文件、磁盘、设备提供统一的接口 确保系统的安全性和稳定性，方便控制根据用户和权限控制资源的访问 允许用户空间进程使用 virtualized system，比如使用 virtual memory 和 multitasking 而无需关心 kernel 的实现 我们可以使用 strace 来跟踪系统调用，一个使用例子如下所示 1234567891011121314strace -o tmp echo "hello"tail -n 5 tmpopenat(AT_FDCWD, "/usr/lib/locale/C.UTF-8/LC_CTYPE", O_RDONLY|O_CLOEXEC) = 3fstat(3, {st_mode=S_IFREG|0644, st_size=201272, ...}) = 0mmap(NULL, 201272, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7ff1992de000close(3) ...

process scheduler(简称 scheduler) 决定运行哪个 Process，什么时候运行以运行多长时间。其主要 idea 就是最大化地利用 processor time 多任务(Multitasking) OS 有两种： cooperative multitasking，除非进程主动放弃，不然会一直运行。调度器无法决定一个进程能够运行多长时间，因此进程可以独占处理器 preemptive multitasking，一个运行中的进程可以被抢占。Linux 采用这种方式 Scheduler 将 CPU 时间划分为时间片(timeslice)，scheduler 的工作就是管理这些时间片。在现代 OS 中，时间片通常是根据进程的行为和系统配置动态计算的。 O(1) scheduler 可以轻松支持数十甚至上百个处理器，但是对调度 latency-sensitive applications 有些问题，这些 applications 被称为 interactive processes(包括所有与用户交互的应用) Rotaing Staircase Deadline sch ...

Process Management process 是运行中的程序以及其相关资源，它是程序代码运行的结果 thread 是 objects 在进程内的活动，是内核调度的基本单位。每个 thread 包含独自地程序计数器、栈、寄存器等资源，thread 共享进程的资源，比如虚拟内存。对 Linux 来说，并不区分线程与进程，线程只是一种特殊的进程，可以与其他进程共享资源 对其它系统来说，线程相当于轻量级的进程，相比于进程消耗更小，并且可以快速执行 进程提供了两种虚拟化： virtualized processor，让进程认为自己独占系统 virtual memory，让进程认为自己独占整个内存 进程 API exit，退出进程并释放资源 wait，父进程等待子进程退出，可以利用 wait 获取子进程的退出状态。子进程退出后，父进程调用 wait 前处于 zombie state Process Descriptor 进程相关信息被封装到 task_struct 中，并通过进程描述符(process descriptor)。进程描述符通过引用双向链表进行连接，被称为 task ...

已有缓存策略的优缺点： LRU：可以很快适应访问模式的改变(热点数据的改变)，但是对热点数据的命中率不如 LFU LFU：需要维护频次；对于热点数据命中率更高，难以应对突发的稀疏流量，旧数据长期不淘汰，会影响某些场景下的命中率(如外卖)，需要额外消耗来记录和更新访问频率 TinyLFU 淘汰时策略挑选一个 victim，由 TinyLFU 决定是否使用 new item 替换 victim。 TinyLFU 维护了 Item 最近的统计信息，为了减少消耗，TinyLFU 只使用 sketching 技术进行估算。 两个挑战： 刷新机制，只需要最新的历史，需要移除旧 events 如何减少内存消耗负载 Approximate Counting Minimal Increment CBF 是一种计数的 Bloom Filter。支持两个方法： Estimate：对 key 计算 k 个不同的 hash 值，找到 counter 中相应位置的计数值，返回最小的一个 Add：对 key 计算 k 个不同的 hash 值，找到 counte 中相应的位置，只增加最小的计数值 co ...

Large-scale Incremental Processing Using Distributed Transactions and Notifications Percolator Motivation MapReduce 无法单独处理增量数据更新，更新延迟与整体的数据量成正比 DBMS 可以利用事务进行增量更新，但是无法处理 Google web index 这个数量级的数据 已有的分布式存储系统（比如 Bigtable）可以处理这个量级的数据，但是无法保证并发更新时数据的不变性 Percolator 的目标是并发处理增量更新的同时，保证数据的不变性(事务)，并且可以跟踪那些更新已经被处理了(Observe 机制) Design Percolator 是在 Bigtable 的基础上构建的。Bigtable 可以看做是一个多维的 map (row, column, timestamp)，提供了在 row 上查找并保证 row 事务的能力。但是 Bigtable 不支持跨行事务。因此 Percolator 的一个目标就是利用 Bigtable 实现跨行、跨表事务。 Perc ...

Raft extended: In Search of an Understandable Consensus Algorithm Raft 博士论文: Consensus: Bridging Theory and Practice 共识算法的目的通常是为了保持复制状态机的一致性，为了保持复制状态机的一致性，通常采用复制日志的方法，即将保持复制状态机的一致性转换为保持日志的一致性。 Raft 保证的属性： Election Safety: 一个 term 最多只能有一个 Leader Leader Append-Only: Leader 从来都不会修改或删除 entries，只会向后添加 entry Log Matching: 如果两个 log 中的 entry 有相同的 index 和 term，那么该 entry 及之前的所有的 entries 都是等价的 Leader Completeness：如果一个 entry 被提交了，那么这个 entry 在以后得 term 中也会一直存在 State Machine Safety: 如果一个 entry 被 apply 了，那么 ...

学习资料 英文版 中文版(注意：中文版本有部分翻译使用的还是老版本 Rust，可以对照看一下) Install rustup 一个命令行工具，可以用来管理版本，并集成了相关工具 1curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh 123456# 更新rustup update# 卸载rustup self uninstall# 本地文档rustup doc 代码风格： 文件名采用 “_” 连接 函数名与 “{” 在同一行，且中间加一个空格 代码采用 4 个空格的缩进方式 使用 rustfmt 可以格式化代码 Cargo Cargo 可以帮助管理 Rust 项目，同时还可以 build code、管理 libraries 12345678cargo new projectcargo new --vcs=git # 使用 git 管理 默认cargo build # 在 target/debug/project 可执行文件，默认以 debug 模式 --rele ...

VersionEdit VersionEdit 对应一次修改，修改指的是 LSM 结构发生变化，比如将内存数据写入 SSTable、compaction 删除和写入新文件。 12345678910111213class VersionEdit { typedef std::set<std::pair<int, uint64_t>> DeletedFileSet; std::string comparator_; uint64_t log_number_; // 当前 log 文件的文件序号 uint64_t prev_log_number_ uint64_t next_file_number_; // 下一个 log 文件的文件序号，可以用于创建新的文件 SequenceNumber last_sequence_; // 保存过得最大的时间戳序号 // ...... std::vector<std::pair<int, InternalKey>> co ...