Skip to content

Latest commit

 

History

History
222 lines (155 loc) · 12 KB

bonus.md

File metadata and controls

222 lines (155 loc) · 12 KB

Bonus

括号里的分值为最高得分，最终得分由 code review 确定。另请注意，总分值不能超过 10 分。

缓存 (1.5 pts)

如果将一些常用数据存在内存中，可以省去大量从外存上读取的时间，这就是缓存的意义。

此 bonus 根据实现难度和工作量给分。

注： 若选择实现并发功能，则此 bonus 分不再计入总分。

中文输入验证 (1.5 pts)

在实际使用中，书名、作者名等只支持 ASCII 显然是不够的；我们有很多中文的书名。但是，为了贯彻落实文化自信，我们也不允许书名中出现不是汉字的文字。

我们把图书相关信息做扩展定义如下：（其他定义不变）

  • [BookName], [Author]：图书名字，图书作者名字；
    • 合法字符集：除不可见字符和英文双引号以外 ASCII 字符，以及汉字和允许的特殊符号；
    • 最大长度：60，一个汉字或特殊符号算作一个字符。
  • [Keyword]：图书关键词；
    • 合法字符集：除不可见字符和英文双引号以外 ASCII 字符，以及汉字和允许的特殊符号；
    • 最大长度：60，一个汉字或特殊符号算作一个字符。

其中，汉字的定义是：最新 Unicode 标准（Unicode 15.0.0）中指定的 Han Ideographs（汉字）区块内的字。网上能查到的大部分匹配方式都不符合这个要求。例如，它们都不能匹配「𰻝」字（音 biáng，U+30EDD，位于 CJK 扩展 G 区）。所以你需要自行查阅相关文档来找出具体的字汇。

允许的特殊符号有：

  • 间隔号「·」，U+00B7
  • Em Dash「—」，U+2014
  • 括号「（」「）」，U+FF08 U+FF09
  • 冒号「：」，U+FF1A

你需要自己了解并手写解析 UTF-8 编码的代码。使用 C++ 标准库解析 UTF-8 不能得分。

完成本 bonus 需通过 OJ 评测（暂未上线）。

Validator (1.5 pts)

本任务的主要目的是练习一些 C++ 语法的使用。

在写 Bookstore 的时候，你一定会写到很多参数的验证：指令需要验证，帐户信息需要验证，图书信息也需要验证。这个任务提供了一个参数验证方法。例如，如果想验证 quantity 在 1 到 10 之间且不是 4，就可以写：

expect(quantity).ge(1).And.le(10).And.Not().toBe(4);

就相当于写：

if (!(quantity >= 1 && quantity <= 10 && quantity != 4)) {
  throw std::exception();
}

本任务要求你实现一个这样的 expect 函数（写 bookstore 主体的时候这个函数也能用上），若验证不通过则 throw 任意值。它只有一个输入参数，其他参数以链式调用 (method chaining) 的方式传入。expect 函数是多态的。你需要实现以下接口：

struct T {};
struct U : T {};
T x, y, z;
U u;
T &ref = u;

// T 的 == 需要有定义，验证是否有 x == y
expect(x).toBe(y);

// 验证 ref 是否为 U 的实例。
// **注意，此处如果 U 根本不是 T 的子类，则需要编译报错。**
expect(ref).toBe<U>();

// T 的 == 需要有定义，接收任意多个（至少一个）参数，验证 x 是否与参数列表中的至少一个值相等
expect(x).toBeOneOf(x, y, z, ...);

// T 的 <= 或 >= 需要有定义，验证是否有 x <= y 或 x >= y
expect(x).le(y);
expect(x).ge(y);

// Not() 将后面跟的所有条件取反
// 意为 x 不能为 1 或 2
expect(x).Not().toBe(1).Or.toBe(2);

如果传入的 x 是 std::basic_string<CharT>（注意不一定是 std::string，点击链接跳转到 C++ Reference），则还需实现以下函数：

std::basic_string<CharT> str1, str2;

// 验证 str1 中的所有字符都包含于 str2 中
// 例如 expect(std::string("1024.00")).toBeConsistedOf("42.01")
// 提示：std::basic_string<CharT>::find()
expect(str1).consistedOf(str2);

// 验证 str1 符合 str2 这个正则表达式
// 提示：可以使用 std::basic_regex<CharT> 实现
expect(str1).toMatch(str2);

这些方法需要能够任意连接：（中间的 And, Or 和 but 为无意义连词，直接令其为 *this 即可）：

// 意为 x 需要在 10 到 100 之间，且不是 2 3 5 7 11 中的任意一个
expect(x)
  .ge(10)
  .And.le(100)
  .but.Not().toBeOneOf(2, 3, 5, 7)
  .Or.toBe(11);

完成本 bonus 需通过 OJ 评测（暂未上线）。

并发 (10 pts)

对于一个强大的数据库系统来说，并发功能是非常重要的。在本任务中，你需要实现块链的并发功能。

从 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.

如果想要进一步了解 C++ 中如何实现一个并发的块状链表，你需要：

以上提供的资料仅用于初步了解并发，如果想要实现一个并发的块状链表，你可能还需要搜索、参看更多资料。

Hint: 简单来说，块状链表应该能够同时处理多个块，主要需要考虑如何分块、并块。如果不同线程同时处理的块恰为同一个块，如何让其中一个线程知道这个块正在被占用？将块正在被占用的信息写回外存显然在时间上是不可接受的。

此 bonus 仅是对于块状链表的要求，如果感兴趣，你也可以让你的主体支持高并发操作。此 bonus 无需通过 OJ 测试，但需要通过评测程序，可从 SJTU jBox（暂未上线） 下载。

注意: 准备尝试此任务的同学请务必与助教联系并讨论自己的实现思路。

快照 (10 pts)

对于一个强大的数据库系统来说，支持快照与恢复功能是非常重要的。在本任务中，你需要实现一个快照系统，实现任意快照间的切换。

一个快照几乎不会占用额外存储空间：

  • 在一个状态上创建一个快照，应该只会占用很小的额外存储来记录这个快照本身的信息，不会将快照的内容完全复制一遍；
  • 在同样的内容上创建 100 个快照，应该只会占用很小的额外存储，不会使磁盘占用增加 100 倍；
  • 在创建快照之后改动一小部分内容，再创建一个快照，也应该只会占用很小的额外存储，不会使磁盘占用增加一倍。

要做到这点，可以利用 Copy-on-write 的做法。简单来说，就是令所有块都是不可变的，在试图修改一个块的时候，对这个块做复制，然后在复制出的新块上做修改。但是如果在不快照的时候也对这些块做 copy-on-write 的话，每修改一次数据，就会增加一个新块，这是不可接受的。因此，你需要只在快照的时候做 copy-on-write。

本任务引入了一条新的指令 snapshot，需要权限等级为 7：

  • [SnapshotID]
    • 合法字符集：大小写英文字母和数字；
    • 最大长度：16；
    • 测试数据保证所有 SnapshotID 均合法。
  • 创建快照
    • {7} snapshot create [SnapshotID]
    • 在当前状态上创建一个快照，名称为 SnapshotID。
      • 测试数据保证 SnapshotID 不会重复。
  • 还原快照
    • {7} snapshot restore [SnapshotID]
    • 还原到名称为 SnapshotID 的快照状态，并清空登录栈。
      • 清空登录栈是为了避免书籍信息被修改所带来的不必要的麻烦；
      • 测试数据保证 SnapshotID 是存在的。
  • 删除快照
    • {7} snapshot delete [SnapshotID]
    • 删除名称为 SnapshotID 的快照状态，不改变当前状态。
      • 其占用的存储空间也需一并释放（下文中说明的情况除外）；
      • 测试数据保证 SnapshotID 是存在的。
  • 合并快照（仅 A 班需要实现）
    • {7} snapshot merge [SnapshotID]
    • 将名称为 SnapshotID 的快照状态合并到当前状态（不一定是一个快照）中，并清空登录栈；
      • 只改变当前状态，快照状态不变；
      • 清空登录栈是为了避免书籍信息被修改所带来的不必要的麻烦；
      • 测试数据保证 SnapshotID 是存在的。
    • 「合并」的定义是：
      • 日志系统不做合并，保留当前日志；
      • 首先，每个快照都需要记录一个「父节点」的信息，表示这个快照之前的快照；
        • 对于第一个快照来说，其父节点是空状态。
      • 找出当前状态与需要合并的快照状态的最小公共祖先；
        • 即使 LCA 状态所对应的快照被删除了，它的状态也需要被保留。
      • 将当前状态和需要合并的快照中，每个对象（一本书、一个帐户）的状态分别与 LCA 中的状态作合并。
        • 如果存在两侧都修改（不包括删除）了同一个对象的情况，则输出 Invalid\n 并不做任何合并；
        • 如果存在两侧都新增了同一个对象的情况（用户以 UserID 为准，书籍以 ISBN 为准），则输出 Invalid\n 并不做任何合并；
        • 如果其中至少一侧删除了一个对象（包括两侧删除了同一个对象），则删除这个对象；
        • 如果其中恰有一侧修改了一个对象，则保留修改过的对象；
        • 如果其中恰有一侧新增了一个对象，则保留新增的对象；
        • 数据保证 ISBN 不会被修改。
    • 你可以暂时把所有数据加载到内存，但是合并结束之后需要将这些数据写回文件，并从内存中删除；
    • 实现中不需要考虑时间复杂度。

为了减轻同学们实现的负担，此部分测试点中输入数据保证合法，无需做校验。

数据点可从 SJTU jBox（暂未上线） 下载。完成本 bonus 需通过 OJ 评测（暂未上线）。

注意: 准备尝试此任务的同学请务必与助教联系并讨论自己的实现思路。

容错 (10 pts)

程序执行时，我们可能会遇到突然断电等意外情况，导致操作中断。如果此时恰好在对磁盘进行读写操作，那么原本的文件系统就会被破坏，从而造成数据损坏的情况。

在 Unix 中常用的文件系统中，删除一个文件可以分为 3 步：

  1. 删除访问的 entry 指针
  2. 释放对应的 index node
  3. 归还对应的磁盘空间

如果操作发生中断，一个常见的恢复方式是从第一条输入指令开始，重新执行一整轮操作，但是时间成本显然难以接受。

因此，我们可以实现一个 journaling file system，利用日志来恢复文件，保证文件的数据不被损坏。

我们可以考虑把一个指令分为多个 原子操作 (atomic operation)，在 journal 中保存每个原子操作。当程序中断时，我们就可以知道保存了哪些原子操作，进而进行文件恢复。

Hint：请思考一下在不同步骤发生中断时，应该如何选取合适的原子操作，并通过原子操作来恢复文件。 reference link

注意: 准备尝试此任务的同学请务必与助教联系并讨论自己的实现思路。

GUI 前端 (8.5 pts)

提供一个用户友好的图形化前端（Qt、Gtk、Web、Tcl/Tk 等均可）。基本要求为：

  • 前后端分离，即前端代码不过度侵入主体逻辑；
  • 用户能通过用户友好的图形化界面完成所有操作；
  • 提供完整的《系统安装手册》《用户手册》。

注意: 准备尝试此任务的同学请务必与助教联系并讨论自己的实现思路。