Memgraph 是一个内存型图数据库，使用 OpenCypher 作为查询语言，主打小数据量、低延迟的图场景。由于 Memgraph 是开源的（repo 在这，使用 C++ 实现）我们可以一窥其实现。根据这行注释，我们可以看出，其内存结构实现灵感主要来自论文：Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems。

本系列主要分为两大部分，论文解读和代码串讲，每一部分会根据情况拆成几篇。本篇，是论文解读（一），主要讲论文概述以及如何使用链表巧妙的存储了多版本、控制了可见性。论文解析（二）和（三），会讲如何实现可串行化以及回收多版本数据。

概述

从论文题目可以看出，本论文旨在实现一种针对内存型数据库的、基于多版本（MVCC）实现的、支持可串行化隔离级别的高性能数据结构。其基本思想是：

1. 使用列存
2. 复用 Undo Buffer 数据结构
3. 使用双向链表来串起数据的多版本
4. 巧妙设计时间戳来实现数据的可见性
5. 通过谓词树（PT）来判事务读集合（Read Set）是否被更改

与一般的多版本不同的是，本论文会在原地更新数据，然后将旧版本数据“压”到链表中去，使用 “压”是因为链表采用头插法：表头一侧数据较新、表尾一侧数据较旧。所有数据的链表头由一个叫 VersionVector 的数据结构维护，如果某一行没有旧数据，对应的位置就是 null。

2023 年倏忽而过，事后来看，要用一个词来形容的话，就是——穷则思变。

穷倒并非是物理上穷的吃不下饭，而是更接近穷则独善其身”中困顿的穷。思想上原先很多赖以生存的观念维持不下去了，因此经历了一个痛苦地重塑过程。这倒并非坏事，只不过其间被动的思想拉扯，现在想来仍然倍感折磨。当然，正是这些逆境逼迫我们跳出“群体思维”进行求索（think different），纵一时痛苦，却能有所得——每个人毕竟要走出属于自己的路。

那这一年到底发生了哪些改变呢？

Y Combinator（YC）是一家知名的美国创业加速器，自2005年成立以来致力于推动初创企业成功。作为初创企业界的领军人物，YC 的特点是，不仅提供资金，还提供指导、资源和网络，以帮助初创企业在竞争激烈的市场中脱颖而出。YC 的成功案例包括 Airbnb、Dropbox 和 Reddit 等，这些公司现在都是各自领域的巨头。
YC 发布的“创业公司征集请求”（RFS）是其基于对市场趋势、技术进步和全球挑战的深入理解，对全球创业社区的发出的一种前瞻性呼吁，相信能够对创业者和想选择创业公司的小伙伴们有诸多启发。2024 年的 RFS 一共有 20 个方向，这是上篇，包括前十个。如果看的人多，我再继续翻译后面 10 条。以下是正文。

引言

虽然，我们投资过的最棒创业 idea，往往并不是一开始我们想找的，反而是那些无心插柳的。

但仍然，我们对几类创业公司非常期待。以下是我们最新的 2024 版本的创业公司征集请求（Requests for Startups，RFS），简述了下我们关注一些创业方向。

但并非说创业只有选择这些方向，才能够申请 Y Combinator。其实我们的多数投资仍然集中在过于一直关注的互联网和移动端。所以如果在阅读本文前，你已经有相关方向的创业想法，请继续做下去。
同样的，也不是说我们列了这些方向，你就要据此创立一家公司。RFS 的目的在于，如果你正好已经有一个类似的想法，那欢迎向我们申请。
另外，如果你想知道我们在寻求投资哪些类型的非盈利组织，可以看这篇文章。

相比 Paxos，Raft 的一大特色就是算法拆成了相对正交的几个部分——领导者选举、日志同步、状态持久化、日志压缩和配置变更。你如果对课程照目录看下就能看出来，除却最后一部分，这些模块就是我们课程 PartA ~ PartD 要分别实现的内容。将算法正交化拆分的好处是，让每个模块相对内聚，使得整体更易理解和实现——这也是 Raft 算法设计的初衷。

下面我不打算采用精确的方式来讲解每个模块——那是论文正文和代码实现要做的事情。相反，本章我将带领大家在感性上建立一个对 Raft 基本概念（任期、选举）和两大流程（领导选举、日志同步）的认识。带着这个感性认识，大家可以再去仔细研读论文，想必能事半功倍地梳理出 Raft 算法中海量的细节。

本文来自 Amazon S3 VP Andy Warfield 在 FAST 23 上的主旨演讲的文字稿，总结了他们在构架和维护如此量级的对象存储 —— S3 的一些经验。我们知道，Amazon S3 是云时代最重要的存储基础设施之一，现在各家云厂商的对象存储基本都兼容 S3 接口，所有云原生的基础设施，比如云原生数据库，其最终存储都要落到对象存储上。

假如你是一个初创公司的 CTO，想迅速推出一款面向 AP 市场可用的数据库产品，还得有差异化的功能（不然谁会用一个新产品），你会怎么做呢？

Firebolt 在 2022 年专门发了一篇论文：Assembling a Query Engine From Spare Parts 来讲这个事情。核心思想就是，利用开源组件，像攒台式机一样攒出一个数据库。

这是使用 Procreate 画图之余，心血来潮开的一个面试基础系列，力求图文并茂、代码视频兼顾，做成最好看的面试系列。欢迎喜欢的小伙伴点赞、转发和打赏，如果支持的同学多，我就继续更下去。

这一年来，由于各种原因，需要不断地学新东西。于是如何高效地学习，就成了一个随之而来的问题。最近看了一些书和公开课，包括 Scott H Young 的 Learn More, Study Less（以下简称 LMSL），和 Coursera 上的公开课学会如何学习（Learning How to Learn，以下简称 LHL），发现了一些有意思的观点，趁着热乎（虽然都还没看完），记下来梳理一下，也希望能对大家有所启发。

这两个资源在进行讲解时，都使用了类比（analogy）。

LMSL 中提出了整体学习法（Holistic learning），其基本思想是：你不可能孤立地学会一个概念，而只能将其融入已有的概念体系中，从不同角度对其进行刻画来弄懂其内涵和外延。

数据库面试的几个常见误区

由于业务的需要，最近面试了很多数据库候选人。发现很多候选人在面试准备时会有一些普遍的误区，借此机会展开聊聊我作为面试官的一些建议。这次主要讲四个误区：代码基础差、工程素养弱、沟通思维无、知识框架碎。

我们在工程实践中，有些构建代码的小技巧，其背后所体现的思想，生活中也常常可见。本系列便是这样一组跨越生活和工程的奇怪联想。这是第一篇：多轮次拆解，也即，很多我们习惯一遍完成的事情，有时候拆成多个轮次完成，会简单、高效很多。

我在进行 code review 时，常看到一些新手同学在一个 for 循环中干太多事情。常会引起多层嵌套，或者 for 循环内容巨大无比。此时，如果不损失太多性能，我通常建议同学将要干的事情拆成多少个步骤，每个步骤一个 for 循环。甚至，可以每个步骤一个函数。

当然，这些全是从维护角度着眼的。因为人一下总是记不了太多事情，一步步来，而不是揉在一块来，会让每个步骤逻辑清晰很多。后者，我通常称之为”摊大饼“式代码，这种代码的特点是写时很自然，但是维护起来很费劲——细节揉在一起总会让复杂度爆炸。软件工程中的最小可用原型，也是类似的理念。

“工业流水线”的鼻祖，福特 T 型汽车的电机装配，将组装过程拆成 29 道工序，将装备时间由平均二十分钟降到五分钟，效率提升四倍 ，下图图源。

这种流水线的思想在数据处理过程中也随处可见。其核心概念是：

1. 标准化的数据集合：对应待组装对象，是对数据处理中各个环节输入输出的一种一致性抽象。所谓一致，就是一个任意处理环节的输出，都可以作为任意处理环节的输入。
2. 可组合的数据变换：对应单道组装工序，定义了对数据进行变换的一个原子操作。通过组合各种原子操作，可以具有强大的表达力。

则，数据处理的本质是：针对不同需求，读取并标准化数据集后，施加不同的变换组合。

最近翻 DuckDB 的执行引擎相关的 PPT(Push-Based-Execution) 时，发现了这篇论文：Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age。印象中在执行引擎相关的文章中看到他好几次；且 NUMA 架构对于现代数据库架构设计非常重要，但我对此了解尚浅，因此便找来读一读。

从题目中也可以看到，论文最主要关键词有两个：

1. NUMA-Aware
2. Morsel-Driven

据此，大致总结下论文的中心思想：

1. 多核时代，由于部分 CPU 和部分内存的绑定关系，CPU 访问内存是不均匀（NUMA）的。也即，对于某一个 CPU 核来说，本机上一部分内存访问延迟较低，另一部分内存延迟要高。
2. 传统火山模型，使用 Exchange 算子来进行并发。其他算子并不感知多线程，因此也就没办法就近内存调度计算（硬件亲和性）。也即，非 NUMA-local。
3. 为了解决此问题，论文在数据维度：对数据集进行水平分片，一个 NUMA-node 处理一个数据分片；对每个分片进行垂直分段（Morsel），在 Morsel 粒度上进行并发调度和抢占执行。
4. 在计算维度：为每个 CPU 预分配一个线程，在调度时，每个线程只接受数据块（Morsel）分配到本 NUMA-node 上的任务；当线程间子任务的执行进度不均衡时，快线程会”窃取“本应调度到其他线程的任务，从而保证一个 Query 的多个子任务大约同时完成，而不会出现”长尾“分片。