引子

在某些工作负载中，随着时间的推移，内存的使用会逐渐增长，直到 OOM。后面发现是内存碎片问题，而将系统默认的内存分配器（glibc malloc）换成 jemalloc ，能有效控制内存的增长上界。

为了解其背后原理，便找来 jemalloc 最初的论文：A Scalable Concurrent malloc(3) Implementation for FreeBSD 来一探究竟。当然，相比 2006 年论文发表时，当前的 jemalloc 可能已经发生了很大改变，因此本文只对当时论文内容负责。更多 jemalloc 机制，大家可以去其 github 仓库查看文档和源码。

背景

在探讨论文的主要思路之前，我们先简单回顾下内存分配器（memory allocator）的作用和边界。简言之：

1. 对下，向操作系统申请大块内存（使用 sbrk、mmap 等系统调用）
2. 对上，处理应用层的各种尺寸的内存申请请求（malloc(size)），并在应用层“表示”不用（free）后进行释放

往小了说，分配器的功能非常简单：分配和释放（malloc 和 free）。想象中，实现也应该很简单，只需利用一个表来记录所有已使用内存和未分配内存（ a bit of bookkeeping），然后：

1. malloc 请求来了，先去空闲表中找，不够的话就问操作系统要
2. free 请求来了，还回空闲表中，如果空的多了，就还给操作系统

Snowflake 由甲骨文的两位员工在 2012 年出来创办，一开始就瞄准云原生数仓，因此架构设计（在当时看来）非常“激进”。超前的视野带来超额的回报，Snowflake 在 2020 年正式上市，市值一度高达 700 亿美金，创造了史上规模最大的软件 IPO 记录。

本文我们综合两篇论文：The Snowflake Elastic Data Warehouse 和 Building An Elastic Query Engine on Disaggregated Storage 来大致聊聊其架构设计。

本文来自我的专栏《系统日知录》，如果你觉得文章还不错，欢迎订阅支持我。

这篇文章我早就想写了，但上次在看论文时卡住了——论文信息太多，地毯式的阅读，很快就淹没在细节中，当时也只看了三分之二，就搁置了。上周（20240707）在文章 Spark：如何在云上做缩容时提到了存算分离的 snowflake ，有读者要求写下，于是便重新捡起来。

相比上次 push 的方式，本次采用 pull 的方式：即不是被动的读论文，而是先思考，如果让我设计这么一个云原生数仓，我要怎么设计，会有哪些问题等等。带着这些问题，我再去从论文中找答案，发现效率一下高了很多，也便让这篇文章没有再次难产。

缘于某个播客提了一嘴，便找来书在通勤时听了。这版是傅雷翻在 1939 年译的版本，有一股淡淡的老式白话风。小书不长，几天便听完。我喜欢在走路的时候听东西，所听入耳、所观入眼，哲人的凝言练语、街头的风物百态，总能在心里发生奇妙的化学反应，偶在三伏天都一激灵。

最近心绪颇为起伏，在上下班踱步听这本书时，数次给我宽慰平和，书中指出的快乐和不快乐之因，都命中了我的某些缺点和特点，因此听完觉得还是要写点东西。

罗素《幸福之路》

人类从狩猎时代进入农耕时代后，虽获得了生活的相对安稳，却也失掉了向外的探索和冒险。到工业时代，城市化加剧，进一步脱离了自然的“蓝领白领”亦是如此。只有少数的企业家才仍然保持着丛林式的生活方式。

选择安稳意味着有大量的“烦闷”（Boredom）需要排遣。但多数人过度的将注意力集中在自己的身上，比如畏罪狂（纠结于行为不符合少时的成见或社会的规训）、自溺狂（过度期待外界称许的虚荣）、自大狂（过度的权力欲望），则使得这种烦闷愈加在幻想中野蛮式的生长，直至占满人们的内心。

ray.data 是基于 ray core 的一层封装。依赖 ray.data，用户用简单的代码，就可以实现数据大规模的异构处理（主要指同时使用 CPU 和 GPU）。一句话总结：很简单好用，同时也有很多坑。
在 上一篇中，我们从用户接口出发，浅浅地梳理了一下 ray.data 的主要接口。本篇，我们从宏观的角度，大概串一下 ray.data 的基本原理。之后，我们再用几篇，结合代码细节和使用经验，探讨下比较重要的几块内容：执行调度、数据格式和避坑指南。
本文来自我的专栏《系统日知录》，如果你觉得文章还不错，欢迎订阅支持我。

概述

从高层来理解，ray.data 的一次数据处理任务大致可以分成前后相继的三阶段：

1. 数据加载：将数据从系统外部读到 ray 的 Object Store 中 （如 read_parquet）
2. 数据变换：利用各种算子在 Object Store 中对数据进行变换（如 map/filter/repartition）
3. 数据写回：将 Object Store 中的数据写回外部存储（如 write_parquet）

由于对各种矩阵运算物理意义的理解总是跟不上，因此尽管多年多次尝试入门机器学习，却总是被拒之门外。偶然间同事推荐了 MIT 那门经典的线性代数公开课，听了几节，煞是过瘾，之前紧闭的大门竟有打开一丝的感觉。

因此，本系列会在每篇文章分享一些课程中有意思的点。为了避免晦涩，每章会尽可能去上下文、保持简短，请放心食用。也因此，本系列会牺牲一些精确性，且并无体系化，仅仅旨在唤起你一丢丢兴趣。注：例子都由 KimiChat 生成。

这是我在很早之前遇到的一个题，很有意思，所以到现在仍然记得。题意借用了 TCP 的上下文，要求实现 TCP 中一个“顺序组装”的关键逻辑：

1. 对于 TCP 层来说，IP 层的 packet 是乱序的收到。
2. 对于应用层来说，TCP 层交付的是顺序的数据。

这个题有意思的点在于，借用了 TCP 的上下文之后，就可以先和候选人讨论一些 TCP 的基础知识，然后话锋一转，引出这道题。这样既可以考察一些基础知识，也可以考察工程代码能力。

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

struct Packet {
    size_t offset;
    size_t length;
    uint8_t *data;
};

// 实现一个“顺序交付”语义
class TCP {
  // 应用层调用：按顺序读取不超过 count 的字节数到 buf 中，并返回实际读到的字节数
  size_t read(void *buf, size_t count);
  // TCP 层回调：得到一些随机顺序的 IP 层封包
  void receive(Packet* p);
  // TCP 层回调：数据发完，连接关闭
  void finish();
};

说的就是我的大规模数据系统专栏《系统日知录》—— 有人问，在读了你的专栏文章后，可能很久之后才可能会用到都不会用到，那为啥要买呢？何况，雨伞在雨天可是刚需，这专栏在面试的时候可不是。所以这实在不是一门好“生意”——受众狭窄、场景低频，两者乘数，便是我这惨淡销量了。

这也是为什么成功的专栏动辄上万次购买，而我只卖了个二百五，也敢把经历拿出来说一说了。万一你有类似的危险想法，也可以参考一二。

本文主要“编译”自书籍《Operating Systems: Three Easy Pieces》第 40 章，这是一本非常深入浅出的书，推荐给所有对操作系统感到迷茫的同学。本文件系统基于一个非常小的硬盘空间，以数据结构和读写流程为主线，从零到一的推导出各个基本环节，可以帮你快速建立起对文件系统的直觉。

文件系统基本都是构建于块存储之上的。但当然，现在的一些分布式文件系统，如 JuiceFS，底层是基于对象存储的。但无论块存储还是对象存储，其本质都是按 “数据块” 进行寻址和数据交换的。

我们首先会探讨一个完整的文件系统在硬盘上的数据结构，也即布局；然后再通过打开关闭、读写流程将各个子模块串起来，从而完成对一个文件系统要点的覆盖。

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 算法中海量的细节。