抖音技术能力大揭密!钜惠大礼、深度体验,尽在火山引擎增长沙龙,就等你来! 立即报名>> 了解详情
写点什么

数据库内核杂谈(一):一小时实现一个基本功能的数据库

2019 年 12 月 11 日

数据库内核杂谈(一):一小时实现一个基本功能的数据库

本篇文章选自数据库内核杂谈系列文章。


数据库内核博大精深,很多子系统的设计初看不知所云,但是细读就会发现其已经做到了极致。但是市面上很少有类似的资源或者课程把数据库内容的精髓讲解出来,因此 Facebook 现任 Tech Lead 顾仲贤撰写了《数据库内核杂谈》的系列文章。


开篇词

为啥想写这样一个系列?

最主要的原因肯定是出于兴趣吧,自从接触了数据库内核开发,觉得里面真的是博大精深,很多子系统的设计初看不知所云,细读就发现已经做到了极致。然后特别希望有大牛能够深入浅出地把这些精髓讲解出来。但可惜,一直没有发现类似的资源或者课程(笔者虽然工作多年,但自觉还是比较注重积累,每天都关注科技新闻,技术博客甚至领域内的新的学术文章)。近期也看到有越来越多的付费培训,从算法到系统设计,到大数据,应有尽有,但唯独没有发现非常好的关于数据库内核设计的资源。自己当然没有实力可以去开那样一门课程,但我希望可以通过写 blog 来完善自己的知识储备。也希望读者能有所收获。不过想归想,自己从来没下定决心去做这样一件事,因为总是觉得自己积累还不够,还要准备准备云云。


什么契机让你真正去行动了?

这契机真的是一个非常偶然的故事。上个周末的一天晚上,小葡萄(我最爱且仅爱的老婆大人)正在给我洗脸。感觉闲着也是闲着,加之正好下午刚讨论过 SQL,我就半开玩笑地说,“老婆,你不是对数据库感兴趣吗?我给你讲讲数据库是怎么实现的,数据库是怎么去执行一个 SQL 语句的” 小葡萄:“你说呀,你能说得出来吗?”;“嘿,小看我,你听着哦 。。。” 然后我就 blahblah 地讲了大半个小时,用尽量通俗易懂的语言给老婆描述了数据库最初是怎么起源的;怎么去实现最基本的存储;有了存储,怎么去实现基本的数据读取;有了读取怎么去实现基本的数据操作,等等。听完,小葡萄真的是突然有种对我肃然起敬地感觉(极有可能是我自己的一厢情愿)。也正是小葡萄的支持,我决定,要真正去做这件想了很久却从未开始的事情。就像她说的,与其过多地去 get ready but do nothing, 还不如去实践一个不怎么 ready 的事!


啥背景呀,就敢写数据库内核

说真的,我自己也信心不足呢。说说背景吧(偶尔咱也知乎体一下):咳咳,谢邀。本人上海交通大学软件学院本科毕业,University of California, Davis 计算机博士毕业。现在在脸书做一个老年程序员。自己并不算一个数据库的科班出身,博士学的也不是数据库专业。一个很偶然的机会,我得到了一份数据库公司 Greenplum(Pivotal)的实习的机会,又阴差阳错地毕业后正式加入了 Query Processing 组。在 Pivotal 的两年,非常有幸地参与了 Orca Query Optimizer (已在 Apache 开源) 的开发。在这期间也混了几篇 VLDB,SIGMOD 的 papaer。正是这份工作让我开始对内核有所了解。再后来原 Pivotal 的 director 离开开了个做数据库虚拟化的初创公司就把我一起拉去了。这个初创公司做的也非常有趣,database virtualization:旨在不用改变任何 application code 的前提下(包括不用换 JDBC, 或者 ODBC driver),就让 application code 可以直接运行在另一个数据库上(举个例子,Teradata BTEQ script 可以直接通过我们的中间件,运行在 Pivotal Greenplumn Database 上),当时我们用的最多的简介就是 VMWare in terms of databases。这份工作让我更细致地了解了不同数据库原生接口的不同以及如何 rewrite 不同的 SQL dialect 来使它们之间互相兼容,我觉得也算变相的 query optimization 吧。总的来说,自己对各个部件都有所了解,但知识点比较分散,不够系统,也希望在写 blog 的过程中去学习和完善知识储备。


这个系列会分为哪几个模块?有没有大纲

真心觉得自己还不够格去系统地讲解数据库的各个模块。所以我才把这个系列的名称定义为杂谈。咱们就暂不列什么提纲了,但我会把最核心的部件包括存储,SQL 语言,数据优化器和执行器都 cover 了。 然后我们也能够自由发挥,分享一些我对 NoSQL 以及 NewSQL 的理解。在这个过程中,我也会去查最新的资料,在写的同时也能更好地去巩固和订正知识。


阅读这个系列会有啥收获?

我希望能够深入浅出地去讲解数据库是一个什么样的系统,以及为什么它最后会演化成这样一个系统,为什么我们都用 SQL 来操作数据,而不是 AQL 或 BQL. 希望读者阅读后,对数据库的理解不再单单只是知道简单的 table, row 等的基本概念或者单单会写些 join, select 的 SQL 语句。而是能从源头真正做到知其所以然。 希望能从对数据库系统的认知来进一步提高对 general 系统设计的认知。


虽然没有大纲,但是这篇的题目想好了:一小时实现一个基本数据库。


一小时实现一个基本数据库

今天我们摒弃直接介绍数据库内核各个模块的思路,而是从应用开发者的角度出发,来看实现一个数据库需要哪些基本功能,然后把这些功能细分成最小的模块再手把手一起实现,帮你揭开数据库内核的神秘面纱。希望能够减轻你对学习数据库内核的压力。我们也可以从中体会到,九层之台,起于累土。所有复杂的系统,都是通过模块化的架构和设计,以及工程阶段的精益求精,一步一步累计起来。


对与应用开发者而言,一个数据库需要哪些必要的功能呢?我觉得,下面这些是必不可少的:


1)创建数据库和数据表:create database,schema, table 等


2)存储数据:insert /update 数据,或者从其他方式导入数据(比如 csv 文件)


3)读取查询数据:通过 SQL 语句,对数据进行读取和查询,比如 sort,aggregate,filter 等


根据这三个功能,再回看标题,你可能产生疑问,一个小时就能实现上面这些功能,不会是标题党吧。我承认,有一点小小得标题党了。因为要和数据库交互,最必要的条件是有个客户端程序可以接受用户送来的指令。但要实现一个功能齐全的 Parser 可得花不少精力。既然是内核杂谈,请允许我偷个懒,假设 Parser 已经有实现,从而把精力都关注在数据库系统内部的实现。抛开 Parser,又该从哪开始呢?我的思路是跟着数据的流向,自下而上,依次从存储数据,读取数据和查询数据来看。


创建和存储数据

当用户创建一个新的数据库,并导入数据时,数据库系统就需要存储这些数据。说到存储,第一个想法就是文件系统(其实说到底数据库系统就是一个特殊的文件系统,区别与普通文件系统提供的的读写文件的接口,数据库只是提供了一个面向数据的接口:存储,读取和查询;整个系统为这些接口提供服务)。以下图 student 表作为示例,要怎么把这张表存在文件中呢?



Student 表


1,“Xiaoputao”,3,“Hiking”

2,“Zgu”,3,“Running”

3,“Xiaopang”,2,“Walking”


读取 CSV 文件的逻辑也非常简单: 一行一行读取数据,然后根据";"把每个数据段取出。


除了 CSV 存储,另一种常见的方式就是 json 格式:


[ {"id":1, "name":"Xiaoputao", "class":3, "hobby":"running}, ... ]
复制代码


聊聊 CSV 和 JSON 存储的优缺点。两者都属于文本存储,优点一在于易于人类理解。另一个优点就是直接兼容其他支持 CSV 和 JSON 的数据库。缺点也很明显,存储效率不高,读取效率也会随之降低。另一个问题在于,上述例子中存储的内容只有值,没有 type 和 size(metadata),这些信息在后续操作如校验中是很重要的。当然,我们可以把 metadata 加入到存储中,比如,把 json 的每个 val 变成一个 obj:{“colName”:“id”,“colType”:“int”,“colSize”:4,“colVal”:1}。专业数据库肯定不会选择用 CSV 或 JSON 作为默认存储,但几乎都支持 CSV 和 JSON 数据作为 external table。如果要追求更高的性能,我们可以选择更高效的编码方式把数据以字节流的形式存储在文件中;只要数据库系统自身能够读取这些数据即可。咱们既然时间有限,当然是一切从简,就选择 CSV 或者 JSON 的文件格式来存储我们的数据。


只要有一个文本编辑器,能够创建和编辑 CSV 或者 JSON 文件。这其实这已经完成了创建数据表,输入,修改以及存储数据的功能。


读取数据

基于上述用 CSV 或 JSON 的存储,读取数据非常简单(允许我们调用第三方支持 CSV 或者 JSON 的 API)。重点在于读取完存放在怎样一个数据结构中方便后续对数据进一步的查询操作。根据数据的特性,结果集(RowSet)是由一序列的行数据(Row)组成,每一行又由多个单元(Cell)组成。我们试着根据这个概念设计下面这些类:



Cell, Row, RowSet Class


简单梳理下,每个 Cell 存 type,size,和 value;Row 存一整行 cell;RowSet 存一序列的 Row。具体在实现中还有很多细节需要注意,如 typecheck, 确保每行列数相同,等等,这里也一并从简略过。定义了存储方式和数据结构,具体数据读取代码如下:



读取


csvToRowSet 和 jsonToRowSet 的实现只需要借助第三方 CSV 和 JSON 的类库就能实现,就不赘述代码了。


这一节里,我们定义了 Cell, Row, RowSet 的数据结构来存放从文件(CSV 或 JSON)中读取的数据,并给出了示例代码。


执行查询

有了存储和读取,已经可以把数据从文件中读取到内存,接下来就要支持用户的查询语句了。实现查询就是去实现 SQL 语句中的各个功能模块,比如排序(order by), 聚合(group by),多表联合(join)等等。执行器会对每个功能模块进行实现,甚至针对不同的数据分布,会有多种方式的实现来提高读取速度。现在,我们一起来讨论一些常用的语言功能。


全表读取(SELECT *)

其实,定义了 RowSet 的数据结构和实现了读取文件的接口,我们的数据库就已经支持全表读取的 SQL 语句,示例如下:


SELECT * FROM student;
复制代码


分页语句(LIMIT)

一下子就能想到的分页语句,用来限制输出的数据行数:



Limit Operator


一行代码,不解释了。抬走!


关系映射语句(PROJECTION)

关系映射的本质是对于输入的 RowSet 的每一行(row), 通过各种标量计算,输出一个新的数据行,再由这些行组成新的 RowSet。见下图示例:


SELECT id + 5, LEN(name) FROM student;
复制代码


对从 student 表读取的每一行数据,输出一个新的数据行包含 id + 5 和 LEN(name)的 cells。


Projection 可以非常复杂,但有一条准则就是它不改变原有 RowSet 的基数(cardinality), 即新 RowSet 的行数和原来的相同。因此,无论映射逻辑多复杂,输入一个 Row,输出一个 Row。再复杂的计算,也是一比一步迭代产生。比如上述示例可以分解成下面这些操作来完成:对于每一行 input row, id 值加 5,对 name 取 length,最后去掉 class 和 hobby 两列。归根结底就是将复杂的运算拆分成原子操作然后一步一步地顺序执行。我们可以定义如下两个基本 operator:RowComputeOperator 根据定义的 computeCellVal 对 input row 计算一个新 cell,并把这个 cell 加到原 row 的末尾。SelectionOperator 根据给定的 indexes,生成一个仅包含指定 index 的新 row。Pseudo code 如下:



RowComputeOperator and SelectionOperator


RowComputeOperator 里面有需要定义 computeCellVal,输入是一个 row,输出一个新的 cell。具体实现则根据具体语义来定。定义一个 computeCellVal 需要 2 个参数:1)运算作用在哪些 cell 上,假设限制只能作用在 1 个或 2 个 cell 上(2 个以上可以用多个 Operator 嵌套);2)提供具体计算的操作,比如常见单元操作如 len(), ceiling(), abs()或者常见的二元操作如±*/等等。


有了这两个基本 operator, 实现示例中的 projection,我们定义 3 个 operator 即可:1)compute a new cell using “(id + 5)” 2) compute a new cell using “len(name)” 3) 用 SelectionOperator 选择最后两个新生成的 cell。


实现整个 projection 的 operator 的 pseudo code 如下:



Projection Operator


条件选择语句(WHERE)

有了 Projection,我们就可以实现下面的条件选择语句(WHERE)了:


SELECT * FROM student WHERE class = 3;
复制代码


实现想法很简单,首先用 Projection operator 计算出 filter condition 的值(bool),然后 filter by 这个 cell 即可。



Filter Operator


排序语句(ORDER BY)

这里,我给一个非常低效但很容易理解的实现:创建一个 hashmap 来存<cell, id>,然后对要 sort 的 cell 排序,根据 cell 顺序取出原 row 组成新的 rowSet 输出:



Sort Operator


有读者会问,如果排序语句是一个 expression 而不是单个 column 怎么办?比如下面的示例:


SELECT * FROM student ORDER BY id + 5 ASEC;
复制代码


还记得我们前面实现的 projection 吗?这里把(id + 5)作为一个新的 projection 加入到 Row 中即可。


一起实现了 4 个 Operator,看看有没有什么规律可循?所有定义的操作都是基于一个原则:输入一个 RowSet,然后输出一个 RowSet。并且,是一层一层循序渐进的迭代。对于数据的查询操作,是从最初读取表中的原始数据开始,根据给定的 Operator 序列对数据逐一进行操作;这一个 Operator 的输出就是下一个 operator 的输入。也就是说,给定一个 SQL 查询语句,我们生成一序列 Operator 的 tree,再依次执行,就能得到最终结果。现在来一起优化下代码,把 Operator 的接口抽象出来,然后把刚才实现的 operator 全当成子类来实现。代码如下:



Unary Operator


有读者会有疑问,基类为什么叫 UnaryOperator 呢?先卖个关子。有了基类,我们可以根据 SQL 的语法功能实现相应的 Operator。


聚合操作(AGGREGATION)

接着一起来实现聚合操作。Aggregation 分为两大类,scalar-agg 和 multi-agg。scalar-agg 就是简单的 sum, avg, min, max 等的数据聚合操作,最终返回一个数据行的结果集,实现代码如下:



Scalar-agg


每个 AggOp 接受一序列的 cells,然后输出聚合结果的 cell。常见的 AggOp 如 sum, max,min 实现都很简单,这边就不赘述了。


multi-agg 对应 SQL 中的 GROUP By,如下图示例:


SELECT class_room, COUNT(*) FROM student;
复制代码


比 scalar-agg 复杂的地方就是先要把有相同值的 group by columns(示例中为 class_rom)的 row 合并起来,然后对合并后的 rows 做 Scala-agg 即可。代码我就不贴啦,当留个小作业给大家。


SQL Operator Tree

有了实现基本语义的 Operator,要实现一个完整的查询语句,我们要做的就是把 operator 一层一层的累加起来,形成一个 Operator tree,然后根据这个 operator tree, 依次执行每一个 operator 即可。比如下面这个查询语句:


select class, sum(id + len(name)) as c
from (
select * from student where hobby = 'hiking' limit 10
)
group by class;
复制代码


我们只要建立如下的 Operator tree:



sql operator tree


有没有觉得挺神奇的!即使再复杂的查询 SQL 都能这样用基本的 operator 像搭乐高一样搭建起来。


小结

至此,我们简单的数据库也实现得差不多啦。我看了下自己写的 pseudo code 仅仅 200 多行,一个小时写完也不算条件太苛刻。虽然数据结构冗余,算法低效,但是麻雀虽小,五脏俱全!


来解释前面卖的关子,为什么基类定义为 UnaryOperator?因为我们还有 BinaryOperator。二元的操作是做什么的呢?答案就是为了表与表的联合(join)。有了 Binary Operator,Operator 的叠加就真正变成了一颗树(二叉树),这也是为什么前文我们称之为 operator tree。本文就先不详述如何实现 Join Operator 了,以后会有专门的章节来覆盖。再讲下去,肯定超过一个小时,读者就更觉得我标题党了。


最后给大家总结一下:


1)一个 SQL 的查询语句,即便逻辑再复杂,也可以拆分成一个一个原子 operator 的叠加


2)把这些 operator 组建成一个 operator tree,然后自底向上地依次执行,就能得到最终的查询结果


3)你可能觉得真正的数据库和我们在这捣鼓的很不一样。如果有条件,可以在 Mysql 或者 Postgres 中运行"EXPLAIN SQL_STMT"来打印它们生成的 operator tree,你会发现和我们生成的树挺相似的


4)相信大家都非常熟悉用 SQL 做各种数据查询,但可能从没去想过底层是怎样实现的。希望这篇博客对你有所帮助。正所谓,知其然,知其所以然!


下一篇,咱们深入聊聊存储!


作者介绍:


顾仲贤,现任 Facebook Tech Lead,专注于数据库,分布式系统,数据密集型应用后端架构与开发。拥有多年分布式数据库内核开发经验,发表数十篇数据库顶级期刊并申请获得多项专利,对搜索,即时通讯系统有深刻理解,爱设计爱架构,持续跟进互联网前沿技术。


2008 年毕业于上海交大软件学院,2012 年,获得美国加州大学戴维斯计算机硕士,博士学位;2013-2014 年任 Pivotal 数据库核心研发团队资深工程师,开发开源数据库优化器 Orca;2016 年作为初创员工加入 Datometry,任首席工程师,负责全球首家数据库虚拟化平台开发;2017 年至今就职于 Facebook 任 Tech Lead,领导重构搜索相关后端服务及数据管道, 管理即时通讯软件 WhatsApp 数据平台负责数据收集,整理,并提供后续应用。


2019 年 12 月 11 日 10:3513254

评论 25 条评论

发布
用户头像
有没有去任意篇的传送门
2021 年 08 月 18 日 11:13
回复
作者亲自回复:https://www.infoq.cn/theme/46
2021 年 08 月 21 日 00:22
回复
用户头像
2021 年 07 月 17 日 23:17
回复
用户头像
求问有开源代码么?写的太好了!!
2021 年 04 月 12 日 11:35
回复
额。。没有。实在没空写代码。
2021 年 08 月 21 日 00:23
回复
用户头像
666

2021 年 04 月 02 日 14:44
回复
用户头像
刚加入info不久的老程序员。最近打算总结elasticSearch,感觉是连个方向的数据库,向您学习,还请指点。
2021 年 02 月 20 日 16:58
回复
不敢当,不敢当。一起学习,一起进步。哈哈。
2021 年 02 月 22 日 02:46
回复
用户头像
"区别与普通文件系统提供的的读写文件的接口,数据库只是提供了一个面向数据的接口"---精辟~!
2021 年 02 月 20 日 10:13
回复
用户头像
作者来留个言,一言难尽的2020终于过去了,新年快乐,希望2021对所有人,都充满惊喜。数据库内核杂谈也已经更新到第十四期了,再次感谢各位的关注。如果你是内核杂谈的真粉丝,觉得内核杂谈对你有收获,愿意听我多扯扯,欢迎加入我的知识星球:Dr.ZZZ 聊技术和管理:https://t.zsxq.com/VrZbeAE(由于不知道能输出多少,也不知道有多少粉丝,所以还是先免费吧)
2021 年 01 月 01 日 02:29
回复
用户头像
写的很棒! 给组内分享拉
2020 年 09 月 07 日 15:46
回复
用户头像
更偏实现,现在基本都是DBA方向的文章,这种内核开发方向的经典确实很少,加油
2020 年 08 月 20 日 09:55
回复
用户头像
浅显易懂,必须点赞
2020 年 03 月 03 日 11:17
回复
用户头像
学习了
2020 年 02 月 16 日 10:26
回复
用户头像
哈哈,作者来留言啦。您们好。看到那么多留言,特别激动。谢谢大家阅读。我会再接再厉,保证不断更。
2020 年 01 月 16 日 13:13
回复
用户头像
有木有英文版本?
2020 年 01 月 07 日 01:20
回复
暂时没有。
2020 年 01 月 16 日 10:49
回复
用户头像
你好,这一篇主要是讲解了sql语句对应的operator的简单实现。
哪sql语句是怎么转变成能被代码识别的operator呢?
想听听你讲讲一条sql语句是怎么解析成Operator tree的。
2019 年 12 月 31 日 12:58
回复
你好。关于这个,我在数据库内核杂谈(四):执行模式(https://www.infoq.cn/article/spfiSuFZENC6UtrftSDD)中有描述过。可以去看看。如果还有问题,我们接着讨论。
2020 年 01 月 16 日 13:14
回复
用户头像
学的很好
2019 年 12 月 17 日 21:58
回复
用户头像
通俗易懂,期待后期更新
2019 年 12 月 11 日 16:05
回复
一直在更新,之后做个合集,方便大家查看。
2019 年 12 月 16 日 11:37
回复
用户头像
我就想知道多大了,还需要老婆给洗脸~^_^
2019 年 12 月 11 日 14:33
回复
此洗脸可不是用水撸两把,哈哈
2019 年 12 月 17 日 16:00
回复
用户头像
老同学的文章,专家啊
2019 年 12 月 11 日 11:56
回复
没有更多了
发现更多内容

玩K8S不得不会的HELM

雪雷

k8s Helm

Jenkins部署Python项目实战

雪雷

Python jenkins CI/CD

Linux系统检查脚本

雪雷

Shell 系统检测

Serverless初探

雪雷

Serverless Lambda 无服务器云函数

Flink高可用性设置-4

小知识点

scala 大数据 flink 流计算

Elasticsearch安装

北漂码农有话说

JVM-技术专题-GCViewer调优GC

李浩宇/Alex

JVM

Apache常用配置指北

亻尔可真木奉

Apache 代理 跨域

Guacamole实战

雪雷

guacamole 远程登录 堡垒机

Ceph集群部署

雪雷

分布式存储 Ceph rdb pvc

Gitlab Pipeline+Supervisor 实战Python项目CI/CD

雪雷

gitlab jenkins CI/CD Supervisor

Jenkins 详解

雪雷

jenkins

支付宝蜻蜓刷脸支付

诸葛小猿

支付宝 蜻蜓 刷脸支付

微服务注册发现配置中心-consul

雪雷

Consul 服务注册与发现 配置中心

记一次混合监控的反思

雪雷

监控 zabbix redis监控 监控宝

Linux自定义快捷工具

雪雷

Linux Shell tools scripts

Docker Web管理工具

雪雷

Docker shipyard dockerui

记一次混合云API发布的反思

雪雷

iptables API api发布

Docker+Jenkins+Gitlab+Django应用部署实践

雪雷

DevOps jenkins CI/CD

Kubernetes-学习必备(awesome-kubernetes-notes)

雪雷

学习 k8s入门 k8s文档 k8s知识

Istio微服务治理笔记(一)

雪雷

istio 服务治理 server mesh

RabbitMQ实践

雪雷

RabbitMQ 消息队列

业务容器化改造

雪雷

Docker 容器 微服务 服务化改造

一文带你检查Kubernetes应用是否为最佳实践

雪雷

k8s k8s最佳实践

微服务API网关-Kong详解

雪雷

kong api 网关

SonarQube集成gitlab/jenkins

雪雷

jenkins sonar gitlab ci 代码扫描

Python利用sphinx构建个人博客

雪雷

sphinx Blog

等级三整理之深信服

Lane

微服务链路追踪之Jaeger

雪雷

全链路监控 Jaeger

Prometheus + Grafana详解

雪雷

监控 Grafana Prometheus 告警

API统一管理平台-YApi

雪雷

YAPI API接口管理

Study Go: From Zero to Hero

Study Go: From Zero to Hero

数据库内核杂谈(一):一小时实现一个基本功能的数据库-InfoQ