123 lines
7.0 KiB
Markdown
123 lines
7.0 KiB
Markdown
# Bonus
|
||
|
||
括号里的分值为最高得分（分数为期末总分），最终得分由 code review 确定。另请注意，总分值不能超过 1 分。
|
||
|
||
## B+ 树相关
|
||
|
||
### 缓存 *(0.2%)*
|
||
|
||
如果将一些常用数据存在内存中，可以省去大量从外存上读取的时间，这就是缓存的意义。
|
||
|
||
此 bonus 根据实现难度和工作量给分。推荐使用 [LRU 算法](https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU))。
|
||
|
||
关于正确性，你需要用开启缓存的程序通过 OJ 测试。
|
||
|
||
**注意:** 不允许把全部数据储存在内存中。
|
||
|
||
### 空间回收 *(0.1%)*
|
||
|
||
在删除 B+ 树中某些数据后，可能会产生一些空间碎片。此 bonus 要求实现空间回收功能，使得删除数据后，B+ 树可以在下次需要空间时利用这些空间。
|
||
|
||
关于正确性，你需要用开启空间回收的程序通过 OJ 测试。
|
||
|
||
### 并发 *(1%)*
|
||
|
||
对于一个强大的数据库系统来说，并发功能是非常重要的。在本任务中，你需要实现 B+ 树的并发功能。
|
||
|
||
从 Wikipedia 上可以找到对于并发的定义：
|
||
|
||
> In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the final outcome.
|
||
|
||
此 bonus 仅是对于 B+ 树的要求，如果感兴趣，你也可以让你的主体支持高并发操作。此 bonus 无需通过 OJ 测试，但会在 code review 时检查正确性。
|
||
|
||
**注意:** 准备尝试此任务的同学请务必与助教联系并讨论自己的实现思路。
|
||
|
||
### 快照 *(0.8%)*
|
||
|
||
对于一个强大的数据库系统来说，支持快照与恢复功能是非常重要的。在本任务中，你需要实现一个快照系统，实现任意快照间的切换。
|
||
|
||
一个快照几乎不会占用额外存储空间：
|
||
|
||
- 在一个状态上创建一个快照，应该只会占用很小的额外存储来记录这个快照本身的信息，不会将快照的内容完全复制一遍；
|
||
- 在同样的内容上创建 100 个快照，应该只会占用很小的额外存储，不会使磁盘占用增加 100 倍；
|
||
- 在创建快照之后改动一小部分内容，再创建一个快照，也应该只会占用很小的额外存储，不会使磁盘占用增加一倍。
|
||
|
||
要做到这点，可以利用 [Copy-on-write](https://en.wikipedia.org/wiki/Copy-on-write) 的做法。简单来说，就是令所有块都是不可变的，在试图修改一个块的时候，对这个块做复制，然后在复制出的新块上做修改。但是如果在不快照的时候也对这些块做 copy-on-write 的话，每修改一次数据，就会增加一个新块，这是不可接受的。因此，你需要只在快照的时候做 copy-on-write。
|
||
|
||
你需要实现以下接口：（以下内容中 `SnapshotID` 为快照 ID，是一个最大长度为 16 的字符串，字符只包含大小写英文字母和数字）
|
||
|
||
- **创建快照** (create)
|
||
- 在当前状态上创建一个快照，名称为 `SnapshotID`。
|
||
- 如果 `SnapshotID` 已经存在，则不做任何事并抛出异常。
|
||
- **还原快照** (restore)
|
||
- 还原到名称为 `SnapshotID` 的快照状态。
|
||
- 如果 `SnapshotID` 不存在，则不做任何事并抛出异常。
|
||
- 还原快照并不会影响任何快照的状态。它不会使被还原到的快照失效，也不会使其他快照失效。
|
||
- **删除快照** (delete)
|
||
- 删除名称为 `SnapshotID` 的快照状态，不改变当前状态。
|
||
- 其占用的存储空间也需一并释放；
|
||
- 如果 `SnapshotID` 不存在，则不做任何事并抛出异常。
|
||
|
||
**注意:** 准备尝试此任务的同学请务必与助教联系并讨论自己的实现思路。
|
||
|
||
### 容错 *(1%)*
|
||
|
||
程序执行时，我们可能会遇到突然断电等意外情况，导致操作中断。如果此时恰好在对磁盘进行读写操作，那么原本的文件系统就会被破坏，从而造成数据损坏的情况。
|
||
|
||
在 Unix 中常用的文件系统中，删除一个文件可以分为 3 步：
|
||
|
||
1. 删除访问的 entry 指针
|
||
2. 释放对应的 index node
|
||
3. 归还对应的磁盘空间
|
||
|
||
如果操作发生中断，一个常见的恢复方式是从第一条输入指令开始，重新执行一整轮操作，但是时间成本显然难以接受。
|
||
|
||
因此，我们可以实现一个 journaling file system，利用日志来恢复文件，保证文件的数据不被损坏。
|
||
|
||
我们可以考虑把一个指令分为多个 **原子操作** (atomic operation)，在 journal 中保存每个原子操作。当程序中断时，我们就可以知道保存了哪些原子操作，进而进行文件恢复。
|
||
|
||
**Hint**：请思考一下在不同步骤发生中断时，应该如何选取合适的原子操作，并通过原子操作来恢复文件。 [reference link](https://en.wikipedia.org/wiki/Journaling_file_system)
|
||
|
||
## 管理系统
|
||
|
||
### GUI 前端 *(0.9%)*
|
||
|
||
提供一个用户友好的图形化前端（Qt、Gtk、Web、Tcl/Tk 等均可）。基本要求为：
|
||
|
||
- 前后端分离，即前端代码不过度侵入主体逻辑；
|
||
- 用户能通过用户友好的图形化界面完成**所有**操作；
|
||
- 提供完整的《系统安装手册》；
|
||
- （可选）提供更方便的操作，如查询后提供一键订票等。
|
||
|
||
**注意:** 准备尝试此任务的同学请务必与助教联系并讨论自己的实现思路。
|
||
|
||
关于用户友好，这里有一些具体的要求：
|
||
- 查询车票后可以直接点击购票；
|
||
- 尽可能减少用户需要输入的内容；
|
||
- 除了对于普通用户友好，对于工作人员也要有友好的操作界面；
|
||
|
||
|
||
对于使用 Web 方式完成的前端（包括使用Vue、React、Bootstrap、Electron 等框架），需要满足以下要求：
|
||
|
||
- 在不同电脑上应该可以同时运行多个前端（网页）并连接到同一后端（服务器），不会相互干扰，模拟现实情况下多用户场景；
|
||
- Web服务崩溃不能影响后端数据服务的正常运行；
|
||
- 设计合理的方式来关闭或重启Web前端服务器或后端数据服务器，而不是手动 kill 进程或者 Ctrl+C，并保证处理完成已接收到的指令，完成数据的保存。可以参考 `nginx -s restart`。
|
||
- ~~不得使用 TesutoHime 作为模板~~
|
||
|
||
### 守护进程 *(0.1%)*
|
||
|
||
完成此任务需要先完成前置任务 GUI前端。
|
||
|
||
对于服务器来说，保证服务的稳定性是非常重要的。
|
||
|
||
在现代的linux系统中，可以很容易地使用 systemd 等工具来管理服务，完成开机自动启动、崩溃自动重启、定时执行等任务。
|
||
|
||
在本任务中，你需要通过两个途径实现下面的几个功能：
|
||
- 在同一个数据目录下，能且仅能运行一个程序实例；
|
||
- 当程序崩溃时，能自动重启；
|
||
- 接受信号，如 `SIGTERM` 时，能够优雅关闭当前的程序实例。
|
||
|
||
途径分别是：
|
||
1. 在现代的linux中，已经有一些工具（发行版相关）为我们提供了相关功能，如 systemd。为你的程序编写 systemd service 文件，完成上面的功能。你也可以考虑使用其他的工具。
|
||
2. 手动实现一个简单的守护进程。参考 `fork` 等系统调用。
|