文章
Build Your Own Database from Scratch - 1
从文件到数据库
# From File To Databases
## 📝 Updating files in-place(原地更新文件)
当我们要存储一些数据到磁盘上时，我们会这么做：
```go
func SaveData1(filename string, data []byte) error {
// Implementation to save data to a file
fp, err := os.OpenFile(filename, 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()
}
```
这段代码是：如果一个文件不存在会创建一个文件，或者在文件中写入新的内容之前会清空原来的内容，最重要的是，文件不会持久化在文件里，除非你调用fsync(fp.Sync())在Go语言中。
这种做法有很大的局限性：
1. 它会更新全部分数据，只适用很小的数据。这也是为什么你不把Excel当作数据库的原因。
2. 如果你需要更新老的文件，你必须将数据读取到内存中修改，然后再覆写到老的文件中，如果应用在你覆写的过程中挂了将会发生什么？
3. 如果应用需要并发访问数据，你如何防止读者获取混合数据，以及防止写入者发生冲突操作？这就是为什么大多数数据库采用客户端-服务器架构——你需要一个服务器来协调并发的客户端。（如果没有服务器，并发会更复杂，参见 SQLite。）
## 📝 Atomic renaming(原子重命名)
### Replacing data atomically by renaming files
不原地更新文件可以解决很多问题，你可以写一个新文件，然后删除老的文件。
不更新老文件的数据的意思是：
1. 如果更新被中断，你可以从旧文件中恢复，因为它仍然保持完整。
2. 并发读取者不会获取半写入的数据。
问题在于读者如何找到新文件。一个常见的做法是将新文件重命名为旧文件的路径。
```go
func SaveData2(filename string, data []byte) error {
tmp := fmt.Sprintf("%s.tmp.%d", filename, rand.Int())
fp, err := os.OpenFile(tmp, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 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()
if err != nil {
return err
}
return os.Rename(tmp, filename)
}
```
重命名一个一个已经存在的文件去替换它是原子性的；删除老的文件是不需要的，也是不正确的。
注意术语的含义，每当你看到“X 是原子的”时，你应该问：“X 相对于什么是原子的？” 在这种情况下：
- 重命名相对于(***w.r.t.***)并发读取者是原子的；读取者要么打开旧文件，要么打开新文件。
- 重命名相对于(***w.r.t.***)电源丧失不是原子的；它甚至不是持久的。你需要对父目录执行额外的 `fsync` 操作，这将在后面讨论。
### Why does renaming work? 文件系统保持从文件名到文件数据的映射，因此通过重命名替换文件时，只需将文件名指向新数据，而不触及旧数据。这就是文件系统中原子重命名可能实现的原因。并且该操作的成本与数据大小无关，是恒定的。 在 Linux 中，如果旧文件仍被某个读取者打开，它可能仍然存在；只不过无法通过文件名访问它。读取者可以安全地操作它所获得的任何版本的数据，而写入者不会被读取者阻塞。然而，必须有一种方法来防止并发写入者。并发的级别是多读取者-单写入者，这是我们将要实现的模式。 ## 📝 Append-only logs(只追加日志) ### Safe incremental updates with logs 一种实现增量更新的方法是将更新直接追加到文件中。这种方式被称为“日志”，因为它是只追加的。它比就地更新更安全，因为没有数据被覆盖；在崩溃后，你总是可以恢复旧数据。 使用日志的读取者必须考虑所有的日志条目, 例如，下面是一个基于日志的键值存储（KV）系统，包含 4 个条目： - **Entry 1**: `Put(key1, value1)` - **Entry 2**: `Put(key2, value2)` - **Entry 3**: `Delete(key1)` - **Entry 4**: `Put(key1, value3)` 在这种日志结构中，所有更新都会被追加到文件中。为了获得正确的最终数据，读取者必须按顺序读取和处理所有的条目。例如，`key1` 的值会在第 1 条和第 4 条日志条目之间发生变化。因此，最终的 `key1` 的值是 `value3`，即使在日志中它被先设置为 `value1`，然后被删除，最后再被更新为 `value3`。 日志是许多数据库中不可或缺的组件。然而，日志仅仅是每个更新的描述，这意味着： - 它不是一个索引数据结构；读取者必须读取所有条目。 - 它没有回收已删除数据的空间的机制。 因此，仅依靠日志不足以构建数据库，必须与其他索引数据结构结合使用。 ### Atomic log updates with checksums 尽管日志不会损坏旧数据，但在崩溃后，如果最后一条日志条目被损坏，仍然需要处理这些情况。可能出现的情况有： 1. 最后一条追加操作根本没有发生；日志仍然有效。 2. 最后一条日志条目半写入。 3. 日志大小增加，但最后一条日志条目缺失。 处理这些情况的一种方法是为每条日志条目添加校验和。如果校验和不匹配，则说明更新未发生，从而使得日志更新在**原子性**方面（相对于读取者和持久性）得到保证。这个场景涉及的是**不完整写入**（在数据库术语中称为“撕裂写入”），即在成功执行 `fsync` 之前发生的写入错误。 校验和还可以检测 `fsync` 之后的其他形式的损坏，但这不是数据库能够恢复的内容。因为一旦数据被写入磁盘并且 `fsync` 完成，数据库就无法从物理损坏中恢复。 总结来说，通过为日志条目添加校验和，数据库能够确保在写入过程中即使出现崩溃或不完整写入，仍能保持数据的一致性和原子性。 ## 📝 \`fsync\` gotchas(fsync的易错点) 在重命名文件或创建新文件后，**必须对父目录调用 ****`fsync`****（强制写入磁盘）**。目录本质上是文件名到实际文件的映射，和普通文件数据一样，除非显式调用**`fsync`**，否则其元数据变更可能未被持久化到磁盘。参考此[例\[1\]](https://www.usenix.org/sites/default/files/conference/protected-files/osdi14_slides_pillai.pdf#page=31) 中对目录的`fsync`操作。`fsync`的另一个挑战是**错误处理**。如果`fsync`失败，数据库更新会宣告失败，但若此时尝试读取文件，仍可能获取到新数据（因为操作系统page cache尚未刷新）！这种行为[高度依赖具体文件系统的实现\[2\]](https://www.usenix.org/conference/atc20/presentation/rebello)。 # 🤗 Summary ### What we have learned: - **就地更新的问题** - 通过**重命名文件**避免就地更新。 - 通过\*\*日志（log）\*\*避免就地更新。 - **仅追加日志（Append-only logs）** - 支持**增量更新**。 - 但不是完整的解决方案：**缺乏索引**，无法**回收空间**。 - **`fsync`**** 的使用** ### What remains a question: - **索引数据结构及如何更新它们** - 如何设计和管理索引数据结构，以支持快速的数据查询、插入和删除？ - 当数据更新时，如何保持索引的高效更新和一致性？ - **从仅追加文件中回收空间** - 如何处理文件中的已删除或过期数据并回收空间？ - 是否可以通过合并日志条目或定期清理日志文件来管理磁盘空间？ - **将日志与索引数据结构结合** - 如何将增量更新的日志与索引结构结合使用，以便在提供高效检索的同时确保数据的一致性和恢复能力？ - 这两者如何协同工作以确保数据库性能和可靠性？ - **并发问题** - 如何处理并发访问问题，确保多个读取者和写入者之间不会发生冲突？ - 如何在多用户环境中保证数据的原子性和一致性，特别是在没有服务器的情况下，如何处理并发写入？ # 📎 参考文章 - 《Build your own databases from scratch Second Edition》 - [www.usenix.org](https://www.usenix.org/sites/default/files/conference/protected-files/osdi14_slides_pillai.pdf#page=31) - [Can Applications Recover from fsync Failures? \| USENIX](https://www.usenix.org/conference/atc20/presentation/rebello)
### Why does renaming work? 文件系统保持从文件名到文件数据的映射，因此通过重命名替换文件时，只需将文件名指向新数据，而不触及旧数据。这就是文件系统中原子重命名可能实现的原因。并且该操作的成本与数据大小无关，是恒定的。 在 Linux 中，如果旧文件仍被某个读取者打开，它可能仍然存在；只不过无法通过文件名访问它。读取者可以安全地操作它所获得的任何版本的数据，而写入者不会被读取者阻塞。然而，必须有一种方法来防止并发写入者。并发的级别是多读取者-单写入者，这是我们将要实现的模式。 ## 📝 Append-only logs(只追加日志) ### Safe incremental updates with logs 一种实现增量更新的方法是将更新直接追加到文件中。这种方式被称为“日志”，因为它是只追加的。它比就地更新更安全，因为没有数据被覆盖；在崩溃后，你总是可以恢复旧数据。 使用日志的读取者必须考虑所有的日志条目, 例如，下面是一个基于日志的键值存储（KV）系统，包含 4 个条目： - **Entry 1**: `Put(key1, value1)` - **Entry 2**: `Put(key2, value2)` - **Entry 3**: `Delete(key1)` - **Entry 4**: `Put(key1, value3)` 在这种日志结构中，所有更新都会被追加到文件中。为了获得正确的最终数据，读取者必须按顺序读取和处理所有的条目。例如，`key1` 的值会在第 1 条和第 4 条日志条目之间发生变化。因此，最终的 `key1` 的值是 `value3`，即使在日志中它被先设置为 `value1`，然后被删除，最后再被更新为 `value3`。 日志是许多数据库中不可或缺的组件。然而，日志仅仅是每个更新的描述，这意味着： - 它不是一个索引数据结构；读取者必须读取所有条目。 - 它没有回收已删除数据的空间的机制。 因此，仅依靠日志不足以构建数据库，必须与其他索引数据结构结合使用。 ### Atomic log updates with checksums 尽管日志不会损坏旧数据，但在崩溃后，如果最后一条日志条目被损坏，仍然需要处理这些情况。可能出现的情况有： 1. 最后一条追加操作根本没有发生；日志仍然有效。 2. 最后一条日志条目半写入。 3. 日志大小增加，但最后一条日志条目缺失。 处理这些情况的一种方法是为每条日志条目添加校验和。如果校验和不匹配，则说明更新未发生，从而使得日志更新在**原子性**方面（相对于读取者和持久性）得到保证。这个场景涉及的是**不完整写入**（在数据库术语中称为“撕裂写入”），即在成功执行 `fsync` 之前发生的写入错误。 校验和还可以检测 `fsync` 之后的其他形式的损坏，但这不是数据库能够恢复的内容。因为一旦数据被写入磁盘并且 `fsync` 完成，数据库就无法从物理损坏中恢复。 总结来说，通过为日志条目添加校验和，数据库能够确保在写入过程中即使出现崩溃或不完整写入，仍能保持数据的一致性和原子性。 ## 📝 \`fsync\` gotchas(fsync的易错点) 在重命名文件或创建新文件后，**必须对父目录调用 ****`fsync`****（强制写入磁盘）**。目录本质上是文件名到实际文件的映射，和普通文件数据一样，除非显式调用**`fsync`**，否则其元数据变更可能未被持久化到磁盘。参考此[例\[1\]](https://www.usenix.org/sites/default/files/conference/protected-files/osdi14_slides_pillai.pdf#page=31) 中对目录的`fsync`操作。`fsync`的另一个挑战是**错误处理**。如果`fsync`失败，数据库更新会宣告失败，但若此时尝试读取文件，仍可能获取到新数据（因为操作系统page cache尚未刷新）！这种行为[高度依赖具体文件系统的实现\[2\]](https://www.usenix.org/conference/atc20/presentation/rebello)。 # 🤗 Summary ### What we have learned: - **就地更新的问题** - 通过**重命名文件**避免就地更新。 - 通过\*\*日志（log）\*\*避免就地更新。 - **仅追加日志（Append-only logs）** - 支持**增量更新**。 - 但不是完整的解决方案：**缺乏索引**，无法**回收空间**。 - **`fsync`**** 的使用** ### What remains a question: - **索引数据结构及如何更新它们** - 如何设计和管理索引数据结构，以支持快速的数据查询、插入和删除？ - 当数据更新时，如何保持索引的高效更新和一致性？ - **从仅追加文件中回收空间** - 如何处理文件中的已删除或过期数据并回收空间？ - 是否可以通过合并日志条目或定期清理日志文件来管理磁盘空间？ - **将日志与索引数据结构结合** - 如何将增量更新的日志与索引结构结合使用，以便在提供高效检索的同时确保数据的一致性和恢复能力？ - 这两者如何协同工作以确保数据库性能和可靠性？ - **并发问题** - 如何处理并发访问问题，确保多个读取者和写入者之间不会发生冲突？ - 如何在多用户环境中保证数据的原子性和一致性，特别是在没有服务器的情况下，如何处理并发写入？ # 📎 参考文章 - 《Build your own databases from scratch Second Edition》 - [www.usenix.org](https://www.usenix.org/sites/default/files/conference/protected-files/osdi14_slides_pillai.pdf#page=31) - [Can Applications Recover from fsync Failures? \| USENIX](https://www.usenix.org/conference/atc20/presentation/rebello)