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),支持基本的 putget 操作,并保证在任意时刻崩溃后,数据库能够恢复到一致的状态。性能不是本实验的重点,正确性和 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. 正确性标准

(TBD)