M9: Key-value Database (libkvdb)

⏰Soft Deadline: 同 Hard Deadline (期末后；无奖励加分)

请遵守实验须知中的 AIGC Policy；在命令行中 git pull origin M9 下载框架代码。

⚖️M9 - libkvdb

请输入 Token 登录。

1. 背景

现代操作系统和应用程序广泛依赖于高效、可靠的持久化存储。无论是配置管理、缓存、元数据存储还是日志系统，Key-Value 数据库 (KVDB) 都是最常见的底层组件之一。相比传统的关系型数据库，KVDB 结构简单、易于嵌入、性能优越，广泛应用于嵌入式系统、浏览器、移动设备等场景。

数据库为我们提供了 ACID (Atomicity, Consistency, Isolation, Durability) 的保证。其中，崩溃一致性 (crash consistency) 是持久化存储系统设计中的一大挑战。系统在任意时刻可能因断电、内核 panic、kill -9 等原因崩溃，重启后必须保证数据不会损坏、不会丢失已提交的操作，也不会出现 “部分写入” 导致的不可恢复状态。为此，操作系统和数据库系统采用了多种技术 (如 write-ahead logging、copy-on-write、原子重命名等) 来保证崩溃一致性。

在这个实验中，你将会实现一个具备崩溃一致性的嵌入式 Key-Value 数据库库 (libkvdb)，并借此机会理解 “persistence” 这一操作系统领域的核心问题。

2. 实验描述

🗒️实验要求：实现带崩溃一致性的 Key-Value 数据库库 (libkvdb)

你需要实现一个简单的 Key-Value 数据库库 (libkvdb)，支持基本的 put、get 操作，并保证在任意时刻崩溃后，数据库能够恢复到一致的状态。性能不是本实验的重点，正确性和 crash consistency 优先。

2.1 总览

你需要实现如下接口 (C 语言，伪代码)：

struct kvdb_t;  // 在 kvdb.h 中定义

int kvdb_open(struct kvdb_t *db, const char *path);
int kvdb_put(struct kvdb_t *db, const char *key, const char *value);
int kvdb_get(struct kvdb_t *db, const char *key, char *buf, size_t length);
int kvdb_close(struct kvdb_t *db);

2.2 API Specification

int kvdb_open(struct kvdb_t *db, const char *path);
- 功能：初始化数据库，将数据库文件与 db 结构体关联。path 为数据库文件路径。如果路径不存在，则创建一个空数据库。
- 返回值：成功返回 0，失败返回 -1。
int kvdb_put(struct kvdb_t *db, const char *key, const char *value);
- 功能：将 key 对应的值设置为 value。如果 key 已存在，则覆盖原有值。
- 返回值：成功返回 0，失败返回 -1。
int kvdb_get(struct kvdb_t *db, const char *key, char *buf, size_t length);
- 功能：查找 key 对应的值，并将其拷贝到 buf，最多拷贝 length-1 字节，并以 \0 结尾。
- 返回值：找到则返回实际拷贝的字节数（不含结尾的 \0），未找到返回 -1。
int kvdb_close(struct kvdb_t *db);
- 功能：关闭数据库，释放相关资源。
- 返回值：成功返回 0，失败返回 -1。

你可以自行设计数据库文件的格式和实现细节，但满足以下两方面的安全性：

所有接口需保证进程安全、线程安全。允许多个进程中的多个线程同时打开同一个 Key-value database，并在很长的一段时间内并发访问。一个进程 (线程) 写入的 key 可以被另外的进程 (线程) 读到。
写操作保证崩溃一致性：write 系统调用不能保证数据的完整性 (写入的数据可能只有部分落盘)。

⚠️管理数据库文件

kvdb_open 时会指定一个 regular file 作为数据库文件，所有的 key-value 数据都存储在这个文件中，你可以将 kvdb_open 时打开文件的文件描述符保存在传入的 struct kvdb_t 中。你可以自由选择文件的格式和系统调用，例如 read/write/lseek/fsync/fdatasync，或是 mmap/msync。

3. 正确性标准

假设我们能够 “观察到” 系统内所有进程和线程对同一个 kvdb 的访问，则所有操作应满足可序列化（serializable）要求：即所有 put 和 get 操作可以排列为某个全局顺序 $O$ ，满足以下条件：

最近写可见性：对每一个 key 的 get 操作，总是返回在全局顺序 $O$ 中该 get 之前最近一次 put 所写入的值；如果不存在对应的 put，应返回 -1。
顺序一致性：对于具有 happens-before 关系的任意两次操作（如同一线程内，操作 $a$ 发生在操作 $b$ 之前），它们在全局顺序 $O$ 中也必须保持 $a$ 在 $b$ 之前。
并发一致性：对于没有 happens-before 关系的两次并发操作（例如并发地对同一 key 的两次 put），所有发生在这两次操作之后的 get 操作，必须返回相同的值（即，系统需表现为选定其中一个 put 的效果为最终结果）。

我们将在测试时，通过并发执行 kvdb_put/kvdb_get 操作、随机杀死与重启进程，以及反复打开数据库文件等方式，检查上述一致性与正确性要求能否被严格满足。此外，我们还会模拟系统的崩溃，此时，在同步 (fsync 等) 系列系统调用之后的 write 操作可能会只有部分的数据被正确保存到磁盘。

本实验对性能没有要求：使用 “一把大锁” 即可通过所有测试用例；但需要实现严格的互斥和崩溃一致性。

4. 实验指南

4.1 实现互斥

在课堂中，我们已经介绍过多种共享内存中实现的互斥/同步机制，从自旋锁、mutex lock 到信号量/条件变量。它们的应用范围是共享内存的线程，底层的实现是 futex 系统调用，系统调用的参数中需要传递一个内存地址。而我们知道，Linux 中进程的地址空间是默认隔离的，也就是当两个独立创建的进程同时打开数据库时，我们是无法为它们创建互斥锁的。

当然，只要应用程序有合理的需求，操作系统一定能实现它。Linux 为我们提供了 flock (file lock) 系统调用，可实现进程间的互斥。它通过对文件加锁，确保同一时刻只有一个进程可以进入临界区执行，基本用法步骤如下：

打开文件：使用 open 获取文件描述符。
加锁：调用 flock(fd, LOCK_EX) 获得排他锁。如果已有其他进程持有锁，则阻塞，直到锁可用。
临界区操作：安全地访问共享资源。
解锁：调用 flock(fd, LOCK_UN) 释放锁。
关闭文件：使用 close 关闭文件描述符。

没错，就和我们的 pthread_mutex_lock 一样。我们既可以创建一个专门的锁文件 (例如 a.db.lock)，也可以直接使用数据库文件本身上锁：

int fd = open("lock.file", O_CREAT | O_RDWR, 0666);
flock(fd, LOCK_EX);
// 临界区
flock(fd, LOCK_UN);
close(fd);

flock 一个很有趣的应用是 gityuan 的 TIM 后台保活，实现在进程被杀死后 “立即唤醒” 另一个进程。

4.2 实现崩溃一致性

虽然我们实现的是磁盘上的数据库，但用共享内存里的数据结构来理解，就容易得多了。我们不妨假设已经正确实现了互斥，一把大锁保证了安全。但是，我们对内存的写入，如果不执行特定的 flush 操作，就有悄悄 “丢失” 的可能，例如：

void list_append(list_t *node, list_t *new_node) {
    new_node->next = node->next;
    new_node->prev = node;
    node->next->prev = new_node;
    node->next = new_node;
}

所有对数据结构的操作，我们都希望是 “all or nothing” 的，丢失任何一个指针的赋值对数据结构的一致性都是灾难性的。实现崩溃一致性一种简单且可靠的方法是 write-head logging：在实际写入数据前，先将本次操作的内容 (key, value) 作为一条日志追加写入日志区 (通常你可以在数据库文件中专门开辟一段空间作为日志)，只有日志被持久化 (使用 fsync 或 fdatasync 写入磁盘) 后，才继续下一步，将该操作实际写入数据区，对应更新数据结构，成功后，可以选择将该条日志标记为已完成或清理。这样在每次打开数据库时，我们都增加额外的一致性检查，需遍历日志，将所有已记录但尚未应用的操作重新执行一遍，确保数据库达到一致状态。

⚠️不要使用 sync

sync 系统调用实现 “操作系统” 级的数据同步，这意味着会同步系统中所有挂载的设备——你可以试想一下，如果计算机系统挂载了上百块磁盘，每个磁盘都有大量的待写入数据；而你仅仅为了在 usb drive 上保存一个小文件调用 sync，会带来多大的性能开销和延迟。

4.3 高性能的 key-value 存储

如果我们在内存中实现 key-value (C++ unordered_map, Python dict, ...)，通常我们会使用 hash table 数据结构，利用内存 $O(1)$ “random access” 的特性，通过合理的 hash function 在近乎常数时间内完成 key $\to$ value 的检索。但是在按块为单位访问的存储设备中，这样会引起巨大的写放大效应：如果连续执行多次 put 操作，这些操作会均匀地被分配到 hash table 的各个 bucket 中，导致每次 put 操作都会写入一个完整的块。

为了解决这个问题，现代 key-value store 的核心数据结构是 “Log Structured-Merge Tree” (LSM Tree)。对于存储设备 (尤其是 SSD) 来说，顺序写入的性能会比随机写入高得多，因此不如把连续的写入缓存下来，打包成一个小数据结构，积攒到一定数量以后再一次性写入磁盘。而这个想法不仅能很好地支持高并发，又恰好又对应了 key-value store 在真实应用场景中 “最近写入的数据使用更频繁” 的特性，我们可以通过不断合并小数据结构形成中等大小的数据结构、更大的数据结构……用于存储相对 “冷” 的数据，而保持 “热” 的数据在树的顶层，实现性能与存储空间的平衡。

有兴趣的同学可以参考 LevelDB 的实现，是一个非常适合作为入门的项目，也是 Jeff Dean 的 “大作”。而 RocksDB 这样的高性能的嵌入式键值存储引擎 (同样基于 LSM Tree 实现)，则广泛被用于分布式数据库、消息队列等系统的底层数据存储。