从头实现数据库0-简介

数据库的三个原则

整个系列包含了一个最小的持久数据库实现的练习。整个过程是持续的，先从一个B-Tree开始，然后是一个简单的KV存储，最后是一个迷你关系数据库。

重要的思想，而不是实现细节。现实世界中数据库是复杂的，更难掌握。但是可以从精简版的数据库中更快、更容易地学习其原理。

整个系列篇幅很短，实现程度也很低，但是涵盖了三个重要的主题：

持久化如何在崩溃后不丢失或损坏数据

数据结构 数据结构（B 树或 LSM 树）。用于高效的查询和更新

存储引擎 构建在 KV 之上的 SQL

如何阅读

该系列采取循序渐进的方法，每一步都建立在上一步的基础上，并增加一个新的概念。使用Golang作为示例代码，但主题与语言无关，建议编写代码，而不仅仅是阅读文本。

持久化

持久化是需要数据库而不仅仅是文件的第一大原因，假设进程在写一个文件的中途崩溃或者掉电了，此时文件的状态是什么样的？

文件会丢失最后一次写入吗？

或者是存在只写了一半的文件？

或者该文件是否存在？

任何结果都有可能，当简单的写入文件时，不能保证数据在磁盘上持久化。这是数据库关心的问题。数据库在意外关闭后启动时将恢复到可用状态。

有一个办法可以在不使用数据库的情况下实现持久化：

把更新后的数据集写入到新的文件

对新的文件调用 fsync

将新文件重命名为旧文件来覆盖旧文件，保证文件系统的原子性

这仅适用于不频繁更新微小数据的情况，并且除了效率低之外，它还有其他问题。

关于fsync ：

写入文件不是一个同步过程；有多个级别的缓存（操作系统页面缓存和设备上缓存）。 fsync 系统调用请求立即刷新所有写入的数据，并将阻塞直到完成。

索引数据结构

索引主要用于提高查询效率

有两种不同类型的数据库查询：分析（OLAP）和事务（OLTP）

分析（OLAP）查询通常涉及大量数据，具有聚合、分组或联接操作

事务（OLTP）查询通常只涉及少量索引数据。最常见的查询类型是索引点查询和索引范围查询

请注意，“事务性”一词与常见的数据库事务无关，这里只关注OLTP技术。

虽然许多应用程序不是实时系统，但大多数面向用户的软件应该使用合理数量的资源（内存、IO）在合理（少量）时间内做出响应，这属于 OLTP 类别。即使数据集很大，如何快速找到数据？这就是为什么我们需要索引数据结构。

内存数据结构与磁盘数据结构

快速查找数据是一个数据结构问题。但数据库索引可能比内存大，并且将数据结构持久保存到磁盘还有其他挑战。

就地更新数据结构是有问题的，因为您必须在崩溃后处理损坏的状态。您不能只将磁盘视为慢速内存。

另一件需要注意的事情是，即使使用 SSD，随机访问也要慢得多，因此像二叉树这样的数据结构是不可行的。

索引数据结构有一些要求：

基于磁盘

安全增量更新

最大限度地减少随机访问

用于索引的常见数据结构包括 B 树和 LSM 树。这里将编写一个具有简单并发事务的写时复制 B+ 树。

KV之上的关系型DB

两级数据库接口： SQL和KV

SQL：数据库接口

kv：获取、设置和删除单个键，最重要的是，按排序顺序列出一系列键

KV 比 SQL 简单，因为它低一级，关系数据库构建在称为存储引擎的类似 KV 的接口之上。

查询语言

最后的挑战是为您自己的数据库创建类似 SQL 的查询语言。为此，我们首先需要将语言解析为结构并将它们映射到数据库操作。这称为解析器和解释器。

备注：

linux 同步IO: sync、fsync与fdatasync

传统的UNIX实现在内核中设有缓冲区高速缓存或页面高速缓存，大多数磁盘I/O都通过缓冲进行。当将数据写入文件时，内核通常先将该数据复制到其中一个缓冲区中，如果该缓冲区尚未写满，则并不将其排入输出队列，而是等待其写满或者当内核需要重用该缓冲区以便存放其他磁盘块数据时，再将该缓冲排入输出队列，然后待其到达队首时，才进行实际的I/O操作。这种输出方式被称为延迟写（delayed write）。

延迟写减少了磁盘读写次数，但是却降低了文件内容的更新速度，使得欲写到文件中的数据在一段时间内并没有写到磁盘上。当系统发生故障时，这种延迟可能造成文件更新内容的丢失。为了保证磁盘上实际文件系统与缓冲区高速缓存中内容的一致性，UNIX系统提供了sync、fsync和fdatasync三个函数。

sync函数只是将所有修改过的块缓冲区排入写队列，然后就返回，它并不等待实际写磁盘操作结束。通常称为update的系统守护进程会周期性地（一般每隔30秒）调用sync函数。这就保证了定期冲洗内核的块缓冲区。命令sync(1)也调用sync函数。

fsync函数只对由文件描述符对应的文件起作用，并且等待写磁盘操作结束，然后返回。确保将修改过的块立即写到磁盘上。除数据外，fsync还会同步更新文件的属性。

fdatasync函数类似于fsync，但它只影响文件的数据部分。而除数据外，fsync还还会更新元数据——文件的属性，但fdatasync仅更新数据。所以fsync有两次IO操作，而fdatasync只有一次。

一般情况下，对硬盘（或者其他持久存储设备）文件的write操作，更新的只是内存中的页缓存（page cache），而脏页面不会立即更新到硬盘中，而是由操作系统统一调度，如由专门的flusher内核线程在满足一定条件时（如一定时间间隔、内存中的脏页达到一定比例）内将脏页面同步到硬盘上（放入设备的IO请求队列）。 write调用不会等到硬盘IO完成之后才返回，如果OS在write调用之后、硬盘同步之前崩溃，则数据可能丢失。

fsync确保文件fd所有已修改的内容已经正确同步到硬盘上，该调用会阻塞等待直到设备报告IO完成。

fsync 与fdatasync 性能对比： fsync不但同步文件的修改内容（脏页），还会同步文件的描述信息（metadata，包括size、访问时间st_atime & st_mtime等等），因为文件的数据和metadata通常存在硬盘的不同地方，因此fsync至少需要两次IO写操作。

硬盘驱动的平均寻道时间大约是3~15ms， 7200RPM硬盘的平均旋转延迟大约为4ms，因此一次IO操作的耗时大约为10ms左右。

文件的尺寸（st_size）如果变化，是需要立即同步的，否则OS一旦崩溃，即使文件的数据部分已同步，由于metadata没有同步，依然读不到修改的内容。而最后访问时间(atime)/修改时间(mtime)是不需要每次都同步的，只要应用程序对这两个时间戳没有苛刻的要求，基本无伤大雅。