从头开始构建你自己的数据库

数据库有三个核心概念：持久性、索引和 并发性。

持久性：如何避免数据丢失或损坏，并能够从崩溃中恢复；
索引：如何高效查询和处理数据；
并发性：如何通过事务处理多个客户端的请求。

持久性

为什么要使用数据库？直接将数据写入文件不行吗？

事实上，大多数情况下可以直接将数据写入文件，但这种方式在某些极端情况下可能会导致问题。

假设写入文件的过程中发生异常中断（如断电、系统崩溃等），写入的内容可能并未正常保存。一些人可能因为没有定期保存 Word 文档而懊恼，但即使文件保存了，内容也可能会丢失或损坏。原因包括：

文件写入可能仅完成了一部分；
数据可能仍停留在系统内存页中，未及时刷盘。

因此，我们需要数据库来解决这些问题。通过持久化，数据库能够保证即使发生异常，数据也能安全保存。

持久化数据到文件中

写入文件具有一定的局限性，下边有一个列子展示我们如何持久化文件并使用数据库解决，这是一个写入文件的典型操作：

func SaveData1(path string, data []byte) error {
  fp, err := os.OpenFile(path, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0664)
  if err != nil {
    return err
  }
  defer fp.Close()

  _, err := fp.Write(data)
  if err != nil {
    return err
  }
  return fp.Sync() 
}

这个简单的操作有一些缺陷：

它会整体更新内容；仅适用于极小数据量。这就是为什么不能把Excel当数据库用的原因。
如需更新旧文件，必须先在内存中读取修改，再覆盖原文件。若覆盖过程中程序崩溃怎么办？
若需多线程并发访问数据，如何防止读取混杂数据或写入冲突？因此大多数数据库采用客户端-服务器架构——需要服务端协调并发客户端。（无服务端时并发问题更复杂，详见SQLite案例）

我们可以通过写入新文件后替换旧文件的方式解决上述问题，如果更新中断不影响旧数据完整性，并发读取也不会读取到没有更新完的数据。这是一个通用的模式：

func SaveData2(path string, data []byte) error {
  tmp := fmt.Sprintf("%s.tmp.%d", path, randomInt())
  fp, err := os.OpenFile(tmp, os.O_WRONLY|os.O_CREATE|os.O_EXCL, 0664)
  if err != nil {
    return err
  }
  defer func() {
    fp.Close()
    if err != nil {
      os.Remove(tmp)
    }
  }()

  _, err = fp.Write(data)
  if err != nil {
    return err
  }
  err = fp.Sync() // fsync
  if err != nil {
    return err
  }
  return os.Rename(tmp, path)
}

追加日志是一种更安全的写入方式，它不需要更新数据，只需要记录每次操作记录即可。但它有一个缺点是没有数据的索引结构，我们如果想要知道数据的最终结果需要读取并执行所有的操作日志，而且它不能回收已经删除数据的空间。这意味着 Append-only logs 的方案在工程环境下是不能独立存在的，需要结合其他具有索引结构的数据一起使用。

追加日志这种方案还有个问题是他的写入并不具备原子性，我们在写入一个操作日志s时能会有很多情况，比如日志没有刷入存储介质、数据只写入一半、日志大小变大了但是没有记录。这是一种非常典型的场景，即如何在非原子性的情况下确保原子性。使用 checksum 可以检测数据的完整性，即使我们的写入过程不是原子的，通过 checksum 依然可以保证写入的原子性。

总结数据库在保证持久性和原子性的挑战：

就地更新的问题:
通过重命名文件避免就地更新。
使用日志避免就地更新。
仅追加日志:
增量更新。
并非完整解决方案；缺乏索引和空间复用。
fsync的使用。

仍待解决的问题：

从仅追加文件中回收空间。
将日志与索引数据结构相结合。
并发。

索引

数据库的查询分为两种主要类型：分析性查询（OLAP） 和 事务性查询（OLTP）。

分析性查询：对大量数据执行分组、聚合、连接等复杂操作。
事务性查询：处理少量数据（如千万级别），通过索引实现快速查询。

如果我们不考虑数据的持久化需求，仅在内存中存储数据，那么只需要选择合适的数据结构即可快速查询。但为了管理比内存更大的数据量，我们需要：

使用数据结构对数据建立索引；
将数据持久化到硬盘。

常用的索引数据结构包括：

B-Trees
LSM-Trees

并发性

现代应用程序通常并非按顺序执行所有操作，数据库同样如此。
并发性可以分为以下几种情况：

读取操作之间的并发；
读取操作与写入操作之间的并发；
写入操作是否需要独占数据库访问权限。

即使是基于文件的 SQLite 也支持一定程度的并发性，但要实现高效并发，数据库通常以“服务器”的形式运行。
随着并发性的增加，应用程序可能需要以**原子性**方式执行操作（如读取-修改-写入）。这引入了数据库的另一个关键概念：事务。

通过了解持久性、索引和并发性，我们可以从头开始构建一个简单而强大的数据库系统。

从头开始构建你自己的数据库

持久性

持久化数据到文件中

索引

并发性

评论