请输入 Token 登录。
现代操作系统和应用程序广泛依赖于高效、可靠的持久化存储。无论是配置管理、缓存、元数据存储还是日志系统,Key-Value 数据库 (KVDB) 都是最常见的底层组件之一。相比传统的关系型数据库,KVDB 结构简单、易于嵌入、性能优越,广泛应用于嵌入式系统、浏览器、移动设备等场景。
数据库为我们提供了 ACID (Atomicity, Consistency, Isolation, Durability) 的保证。其中,崩溃一致性 (crash consistency) 是持久化存储系统设计中的一大挑战。系统在任意时刻可能因断电、内核 panic、kill -9 等原因崩溃,重启后必须保证数据不会损坏、不会丢失已提交的操作,也不会出现 “部分写入” 导致的不可恢复状态。为此,操作系统和数据库系统采用了多种技术 (如 write-ahead logging、copy-on-write、原子重命名等) 来保证崩溃一致性。
在这个实验中,你将会实现一个具备崩溃一致性的嵌入式 Key-Value 数据库库 (libkvdb),并借此机会理解 “persistence” 这一操作系统领域的核心问题。
你需要实现一个简单的 Key-Value 数据库库 (libkvdb),支持基本的 put
、get
操作,并保证在任意时刻崩溃后,数据库能够恢复到一致的状态。性能不是本实验的重点,正确性和 crash consistency 优先。
你需要实现如下接口 (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);
int kvdb_open(struct kvdb_t *db, const char *path);
db
结构体关联。path
为数据库文件路径。如果路径不存在,则创建一个空数据库。int kvdb_put(struct kvdb_t *db, const char *key, const char *value);
key
对应的值设置为 value
。如果 key
已存在,则覆盖原有值。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);
你可以自行设计数据库文件的格式和实现细节,但满足以下两方面的安全性:
kvdb_open 时会指定一个 regular file 作为数据库文件,所有的 key-value 数据都存储在这个文件中,你可以将 kvdb_open 时打开文件的文件描述符保存在传入的 struct kvdb_t 中。你可以自由选择文件的格式和系统调用,例如 read/write/lseek/fsync/fdatasync,或是 mmap/msync。
(TBD)