木鸟杂记

分布式系统,数据库,存储

本文主要“编译”自书籍《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

阅读全文 »

IMG_8879.JPG

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 来讲这个事情。核心思想就是,利用开源组件,像攒台式机一样攒出一个数据库

阅读全文 »

这一年来,由于各种原因,需要不断地学新东西。于是如何高效地学习,就成了一个随之而来的问题。最近看了一些书和公开课,包括 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 道工序,将装备时间由平均二十分钟降到五分钟,效率提升四倍 ,下图图源

T-model-car.png

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

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

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

阅读全文 »