Leyland Number

模拟。

1
2
3
4
5
6
7
8
9
10
11
12

public static void solve() {
    int a = io.nextInt(), b = io.nextInt();
    int x = 1;
    for (int i = 0; i < b; i++) {
        x *= a;
    }
    int y = 1;
    for (int i = 0; i < a; i++) {
        y *= b;
    }
    io.println(x + y);
}

Longest Palindrome

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static void solve() {
    String s = io.next();
    int n = s.length();
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            String a = s.substring(i, j + 1);
            String b = new StringBuilder(a).reverse().toString();
            if (a.equals(b)) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    io.println(ans);
}

Slot Strategy 2 (Easy)

暴力枚举每个转盘的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static void solve() {
    int n = 3, m = io.nextInt();
    int ans = Integer.MAX_VALUE;
    String[] s = new String[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.next();
    }
    for (int i = 0; i < n * m; i++) {
        char a = s[0].charAt(i % m);
        for (int j = 0; j < n * m; j++) {
            if (i == j) continue;
            char b = s[1].charAt(j % m);
            for (int k = 0; k < n * m; k++) {
                if (i == k || j == k) continue;
                char c = s[2].charAt(k % m);
                if (a == b && b == c) {
                    ans = Math.min(ans, Math.max(i, Math.max(j, k)));
                }
            }
        }
    }
    io.println(ans == Integer.MAX_VALUE ? -1 : ans);
}

Relative Position

DFS 模拟，需要注意给的不是一棵树，所以在 DFS 时要使用访问数组，而不能用父结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int a = io.nextInt() - 1, b = io.nextInt() - 1, x = io.nextInt(), y = io.nextInt();
        g[a].add(new int[]{b, x, y});
        g[b].add(new int[]{a, -x, -y});
    }
    long[] X = new long[n];
    long[] Y = new long[n];
    Arrays.fill(X, Long.MAX_VALUE);
    Arrays.fill(Y, Long.MAX_VALUE);
    boolean[] vis = new boolean[n];
    dfs(0, vis, g, 0, 0, X, Y);
    for (int i = 0; i < n; i++) {
        if (X[i] != Long.MAX_VALUE && Y[i] != Long.MAX_VALUE) {
            io.println(X[i] + " " + Y[i]);
        } else {
            io.println("undecidable");
        }
    }
}

private static void dfs(int i, boolean[] vis, List<int[]>[] g, long x, long y, long[] X, long[] Y) {
    X[i] = x;
    Y[i] = y;
    vis[i] = true;
    for (int[] t : g[i]) {
        int j = t[0];
        if (vis[j]) continue;
        long nx = t[1] + x, ny = t[2] + y;
        dfs(j, vis, g, nx, ny, X, Y);
    }
}

Somen Nagashi

还是模拟，可以一边输入一边处理，减少代码量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    long[] ans = new long[n], re = new long[n];
    PriorityQueue<Integer> q = new PriorityQueue<>();
    PriorityQueue<Integer> p = new PriorityQueue<>((a, b) -> Long.compare(re[a], re[b]));
    for (int i = 0; i < n; i++) {
        q.offer(i);
    }
    while (m-- != 0) {
        int t = io.nextInt(), w = io.nextInt(), s = io.nextInt();
        while (!p.isEmpty() && re[p.peek()] <= t) q.offer(p.poll());
        if (q.isEmpty()) continue;
        int x = q.peek();
        ans[x] += w;
        re[x] = t + s;
        p.offer(q.poll());
    }
    for (int i = 0; i < n; i++) {
        io.println(ans[i]);
    }
}

green_gold_dog, array and permutation

让最小值减去最大值，就一定可以得到 $n$ 个不同的差值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    var aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> a[i] - a[j]);
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        int t = aux[i];
        ans[t] = n - i;
    }
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

XOR Palindromes

算是简单的分类讨论，比赛时写的稀烂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static void solve() {
    int n = io.nextInt(), cnt = 0;
    char[] s = io.next().toCharArray();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            cnt++;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i <= n; i++) {
        if (i < cnt || i > n - cnt || (i - cnt) % 2 == 1 && n % 2 == 0) {
            sb.append('0');
        } else {
            sb.append('1');
        }
    }
    io.println(sb);
}

Salyg1n and the MEX Game

比赛调试一小时，疯狂超时，结果是限制太强的原因。（浪费时间。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public static void solve() {
    int n = io.nextInt();
    int[] s = new int[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.nextInt();
    }
    Arrays.sort(s);
    int x = n;
    for (int i = 0; i < n ; i++) {
        if (s[i] != i) {
            x = i;
            break;
        }
    }
    while (x != -1) {
        io.println(x);
        io.flush();
        x = io.nextInt();
    }
}

Cyclic Operations

做了一个多小时 AC，有点像之前做的内向基环树，该题每个点都有个出边，所以至少有一个环。首先要特判 $k=1$ 的情况，该情况每个位置都必须自成一个环，即 $a_{i}=i$；其他情况所有环的长度都必须为 $k$，这样可以保证答案存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt() - 1;
    }

    int[] in = new int[n];
    for (int i = 0; i < n; i++) {
        in[b[i]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            q.offer(i);
        }
    }
    while (!q.isEmpty()) {
        int x = q.poll();
        if (--in[b[x]] == 0) {
            q.offer(b[x]);
        }
    }

    int cnt = 0;
    boolean[] vis = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (in[i] == 0 || vis[i]) continue;
        int len = 0;
        for ( ; !vis[i]; i = b[i]) {
            vis[i] = true;
            len++;
        }
        if (len != k) {
            io.println("NO");
            return;
        }
        cnt++;
    }
    if (k == 1 && cnt != n) {
        io.println("NO");
    } else {
        io.println("YES");
    }
}

Salyg1n and Array (simple version)

注意，$n$ 和 $k$ 都是偶数！手推的话可能可以做出来吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    int ans = 0, i;
    for (i = 1; i + k - 1 <= n; i += k) {
        io.println("? " + i);
        io.flush();
        ans ^= io.nextInt();
    }
    for (; i <= n; i++) {
        io.println("? " + (i - k + 1));
        io.flush();
        ans ^= io.nextInt();
    }
    io.println("! " + ans);
    io.flush();
}

Salyg1n and Array (hard version)

技巧性有点强，真想不到。就是如果多出一部分，可以通过两次异或算出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    int ans = 0, i;
    for (i = 1; i + k - 1 <= n; i += k) {
        io.println("? " + i);
        io.flush();
        ans ^= io.nextInt();
    }
    int t = n - i + 1;
    io.println("? " + (n - k + 1 - t / 2));
    io.flush();
    ans ^= io.nextInt();
    io.println("? " + (n - k + 1));
    io.flush();
    ans ^= io.nextInt();
    io.println("! " + ans);
    io.flush();
}

项目准备

项目地址：Project #1 - Buffer Pool

准备工作：阅读 Chapter 12.1-12.4 13.2-13.3 24.2，学习 Lecture #03 #04，以及阅读课堂笔记。

项目结构

buffer_pool_manager

pages_ 数组相当于缓冲池，frame_id 是该数组的下标，也就唯一标识一个 Page，即标识一个缓冲页面。一个 Page 可以存储不同的物理页面，Page 的数据成员 page_id_ 唯一标识一个物理页面。因为不管是 FetchPage，还是 DeletePage 等函数，我们都是针对实际的物理页面做操作，所以 buffer_pool_manager 中的函数的形参都是提供 page_id。

lru_k_replacer

该类提供缓冲页面的淘汰策略，即淘汰某个 fram_id 对应的缓冲页面。一个缓冲页面会有一个对应的 LRUKNode，它负责记录该缓冲页面的访问历史。

page_guard

主要有三个类：BasicPageGuard，ReadPageGuard 和 WritePageGuard。BasicPageGuard 的作用是保证缓冲页面在使用完后会进行 UnpinPage 操作。而 ReadPageGuard 和 WritePageGuard，它们和 BasicPageGuard 是组合关系，它们的作用在 BasicPageGuard 的基础上保证页面在使用完后会解除读写锁。

Task #1 - LRU-K Replacement Policy

实现

① 一开始以为 current_timestamp_ 自动就是当前时间戳，调试时发现一直是 $0$，我真笨。可以直接从 $0$ 开始手动模拟时间戳，调用 RecordAccess 时，让当前时间戳加 $1$ 即可。

② 在 Evict 的注释中有：If multiple frames have inf backward k-distance, then evict frame with earliest timestamp* based on LRU。我以为淘汰的是最后一次访问时间最早的 frame，结果淘汰的是第一次访问时间最早的 frame。

③ 在 ListNode 中使 history_ 的长度不超过 k_，如果超过就调用 pop_front()，这样每次获取之前第 k_ 个访问记录只需要调用 front() 函数。

④ 在 RecordAccess 的注释中有：If frame id is invalid (ie. larger than replacer_size_), throw an exception。但其实应该是大于等于吧，因为 BufferPoolManager 构造函数的实现如下：

1
2
3
4
5
6
7
8

// we allocate a consecutive memory space for the buffer pool
pages_ = new Page[pool_size_];
replacer_ = std::make_unique<LRUKReplacer>(pool_size, replacer_k);

// Initially, every page is in the free list.
for (size_t i = 0; i < pool_size_; ++i) {
    free_list_.emplace_back(static_cast<int>(i));
}

上述代码说明 frame_id 是小于 pool_size 的，所以大于等于 pool_size 的 fram_id 都应该抛出异常。（或许小于零的也应该抛出异常）

补充

① 测试时将 DISABLED_SampleTest 改为 SampleTest。

② 忘记 C++ 的 = 是拷贝，传引用加上 &：

1

auto node = node_store_.at(frame_id); // 错误：拷贝

③ LRU 的中文翻译是“最近最少使用”，实在让人很无语，我以后就将其称为“最久未被使用”吧。

Task #2 - Buffer Pool Manager

实现

① NewPage 和 FetchPage 有很多逻辑相同的部分，可以加个辅助函数来获取 frame_id。

② 注意，在 FetchPage 时，如果页面在内存中并且 pin_count_ = 0，则需要将其设置为不可淘汰的。

③ 在 UnpinPage 中，更新 is_dirty 属性时使用或运算，因为可能某个线程修改了页面数据，而其他线程没有修改。

④ 在 FlushPage 中，注释表示 REGARDLESS of the dirty flag，应该说的是函数调用者，我们在实现时可以根据 is_dirty 来判断是否实际刷盘。

补充

① 提交 GradeScope 报错时，下面会显示一堆 LeakSanitizer: detected memory leaks。但是没有关系，这应该是由于测试程序提前终止引发的，直接解决上面的错误就行。

② 实现 FetchPage 时，有个情况我忘记调用 RecordAccess，竟然通过所有线上测试了，后来检查代码才发现，修改后 QPS 快了一些。

Task #3 - Read/Write Page Guards

实现

① 使用移动构造和移动赋值后，需要清除 that 的元数据。

② 移动赋值的调用者，也就是 this，如果其 page_ != nullptr，那么需要先将其 Drop，再进行赋值操作。

③ 实现读写页面守卫的移动构造函数，可以直接赋值 std::move(that.guard_)，相当于调用之前实现的 BasicPageGuard 的移动赋值运算符。

④ 实现读写页面守卫的 Drop 时，需要注意在调用 guard_.Drop() 之后再解锁页面，所以在 Drop 之前需要保存一下指向页面的指针。

⑤ 在实现 BufferPoolManager 中的 FetchPageRead 和 FetchPageWrite 时，为页面加读写锁。

⑥ 和 PageGuard 有关的 FetchPage 函数会返回一个 PageGuard 对象，但是如果所有缓存页已经被 pin，那么该返回什么。一开始我是直接拿 nullptr 构造 PageGuard，但是发现不对，因为 PageGuard 对象并没有检查 page_ == nullptr 的函数，所以页面必须被 Fetch 到。要不就一直自旋，要不就使用条件变量，但是使用条件变量又要加个锁，防止通知丢失，那样锁竞争会很激烈啊。（不是很想改，BufferPoolManager 和 B+Tree 的线上测试都能过，暂时不管）

Leaderboard Task (Optional)

准备

性能分析

看到CMU 15-445 2023 P1 优化攻略中使用火焰图做性能分析，之前从来没听说过，打算学习一下。以下是几个不错的网站，奈何感觉很复杂啊。一开始我是用 perf 做分析，然后使用 speedscope 进行可视化，但是捣鼓半天还没弄明白，遇到很多问题，有空再搞吧。

• Brendan Gregg’s Homepage
• How to use flamegraphs for performance profiling
• profiling 与性能优化总结
• speedscope

LRU-K（对优化似乎没有帮助）

关于 LRU-K 的论文：The LRU-K Page Replacement Algorithm For Database Disk Buffering。

LRU 存在的问题：仅根据页面的最后一次访问时间进行淘汰，它不知道页面是否经常访问，从而可能将不经常访问的页面长时间保留在缓冲区中。（论文中对此有两个场景分析）

解决方案：① 页面池调优，缺点是需要人工操作，并且不能适应移动热点；② 查询执行计划分析，缺点是在多用户的场景下，查询优化器可能会以复杂的方式重叠；③ LRU-K，自适应的。（有点不是很懂）

LRU-K 和 LFU 的区别：LRU-K 有一个“老化”的概念，即只考虑对页面的最后 K 次引用，而 LFU 无法区分最近和过去的引用频率，因此无法应对不断变化的访问模式。

LRU-K 存在的问题：① Early Page Replacement，新加入缓冲池的页面因为访问次数不足 K（$K\geq 2$），所以相对于有 K 次访问历史的页面更容易被淘汰，但是该页面之后可能会有相关访问（原文是称作 Correlated References，并介绍了事务内、事务重试、进程内、进程间的相关访问）；② Page Reference Retained Information Problem，当页面被淘汰时，它的访问历史需要保留一段时间，如果超时再进行删除操作。

实现

更新：以下内容存在一些错误，将会在下一节纠正。

① 初次提交，所有函数开头一把大锁。提交相同的代码，排名波动挺大的，可能是因为没优化的代码跑分都差不多，QPS 大概四五千左右。

② 并行 IO 优化，尝试在进行 IO 操作时将大锁切换为单独的页锁（针对 frame_id，即缓冲池页面的锁），简单来说就是在 IO 之前拿到页锁，然后释放大锁。一定需要注意加锁和解锁的顺序，如果有部分代码先加大锁再加页锁，另一部分代码先加页锁再加大锁，那么就会产生死锁。优化半天，遇到不少 BUG，但是没遇到死锁，QPS 提升至五万多。（注意，我们优化的是磁盘页面读写，而不是缓存页面读写，不要混淆，说的就是我）

③ 死锁警告，调试最久的一次，线上提交五十多次（当时不知道本地有 bpm-bench 测试），结果发现是我理解有问题。尝试使用读写锁在 BufferPoolManager 内部锁定页面，但是读写锁是依赖于访问类型的，因为有 Unknown 类型的存在，实际上根本无法执行该优化，并且该优化并不会提高 IO 的并行量。PS：仔细想想后发现甚至根本就不可能这样做，因为 FetchPage 时需要修改共享变量肯定不能用读写锁。并且根本就不可能有什么性能提升，因为优化的部分不涉及 IO 等耗时操作，所以瞎折腾半天后放弃。

④ 参考CMU 15-445 2023 P1 优化攻略，似乎用的是写时复制的思想，刷盘的时候复制一份数据在新线程刷，这样就可以让当前线程做 ResetMemory 操作而不会产生冲突，具体的优化思路见文章。单纯的写时复制优化我觉得还行，刷盘之后就会释放复制页面占用的内存空间，读取的时候也可以重复利用。但是如果像文中那样固定为每个页面都保存缓存，那就相当于变相增加了缓冲池的容量，那还不如用下面的方法简单粗暴，并且时间和空间都应该是更优的。

⑤ 有个无耻的优化方式，把所有页面全部存到内存缓存中，读盘的时候读缓存，刷盘的时候刷缓存，最后析构的时候再进行实际的物理刷盘。具体实现的时候，不能在析构的时候刷盘，因为线上测试会在析构 BufferPoolManager 之前析构 DiskManager，但是这样也是可以通过线上测试的，QPS 两百多万（其实大部分测试结果只有一百多万）。然而，这已经不能算优化了，磁盘数据库不可能这么操作的，因为内存不太可能存下所有页面。

⑥ 本来想优化 LRU-K 的，但是想不到怎么根据访问类型来优化，怎么利用 zipfian 分布，暂时搁置。突然想到优化方法了，因为 Scan 线程是进行全表扫描，所以只被 Scan 线程访问过的页面就可以直接淘汰掉。我们可以在 LRUKNode 中维护一个布尔值，表示当前页面是否只被 Scan 线程访问，如果是就可以在 Evict 中直接淘汰，并且优先淘汰此类页面。回归正轨，基于 ② 优化提升大概三万 QPS，排名 12。（这优化完全是针对基准测试做的，没有什么适用性）

重做

实现纠错

在做 B+Tree 时发现上面第 ② 个实现有个 Bug，如果我新建一个缓存页面，然后它被淘汰刷盘，在刷盘之前，我会拿到该缓存页面的锁，然后释放缓冲池的独占锁，这会存在问题。为了避免死锁，加锁解锁的顺序是固定的，所以我释放缓冲池的独占锁后，不会再去尝试对它加锁。那么我就需要释放独占锁之前，修改完所有和缓冲池有关的共享变量（例如 page_table_），但是，如果在刷盘过程中，有另一个线程读取该页面，它在 page_table_ 中找不到该页面，所以它会去读取磁盘，这时页面还没有写入磁盘中，就会出现 “page not exist” 错误，错误在 disk_manager_memory.h 中被检测：

1
2
3
4

if (page_id >= static_cast<int>(data_.size()) || page_id < 0) {
    LOG_WARN("page not exist");
    return;
}

所以第 ② 种优化方式是不完善的。可以额外搞个哈希表存正在进行刷盘的 page_id 和 frame_id，然后加个锁，在刷盘的时候加到该表里，刷完的时候删除（注意在添加到表时持有 page_table_ 的锁，以确保在其他线程 FetchPage 时，表中已有该 page_id）。这时如果有其他线程 Fetch 该 page_id，不会直接从磁盘读，而是读这个表拿到之前的 frame_id，然后拷贝到当前缓存页。（之所以另开哈希表，而不是保留在原来的表里，是因为如果这样会导致混乱，当有其他线程 FetchPage 该 page_id 时，会发生已淘汰又被 pin 的情况，还会发生其他很复杂的情况）

如何优化

既然 B+Tree 把我打回来修复 Bug，那么我就想，有没有更好的优化方案。自己独自优化总觉得找不到方向，并且可能设计就是错的，而且优化方式很幼稚。在网上搜也搜不到具体的优化方案，我就想尝试看一看开源数据库都是怎么做的，最后在 PostgreSQL 项目中发现一份超级详细的 README（MySQL 为什么没有），省去我看源码的时间，以下是对它的简单概述（使用我们项目中的变量来解释）：

① 缓存页面的访问规则

• 读写页面时必须 pin 页面，并拿到相应的读写锁。（文中要求必须在上锁之前 pin）
• 在读页面时，可以释放页面的读锁，因为已经拿到页面的 pin。
• 在写页面时，必须拿到 pin 和写锁，并且需要检查 pincount_ == 1，如果不相等，则释放写锁并返回或者使用条件变量等待唤醒。（因为在读页面时会提前释放读锁，但没有 unpin，所以拿到写锁时，还需要等待）当进行写操作时，有可能页面会被 pin，但是没有关系，因为当前线程拿到写锁，其他线程 pin 之后还需要拿锁才能读写页面。

我们的项目和上面的描述不一样，但是无伤大雅，基本上 PageGuard 和 FetchPage 等函数已经提供了这些功能。

② 缓冲池管理器的内部锁定

• 访问 page_table_ 前需要拿到 page_table 的读写锁（文中称作 BufMappingLock）。如果是读页面，则在释放锁之前，需要拿到缓存页面的 pin。在修改 page_table_，或者修改缓存页面头部字段（应该是指 Page 的除 data_ 以外的成员变量，在本项目中就是 page_id_、pin_count_ 和 is_dirty_），或者从磁盘读物理页面到缓存页面时，需要拿到 page_table_ 的写锁。
• 可以将 BufMappingLock 拆分为 NUM_BUFFER_PARTITIONS 个锁，每个锁负责映射的一部分。每个 page_id_ 属于哪个分区，由 page_id_ 的哈希值的低比特位决定（其实就是有多个 page_table_，每个 page_id 会根据哈希函数来确定存放在哪个 page_table_ 中）。如果要同时锁定多个分区，则需要按照分区编号顺序锁定，以避免死锁。
• 为空闲列表和页面替换提供独占的自旋锁 buffer_strategy_lock ，当拿到该锁时，不应该去获取任何其他锁。
• 每个缓存页面都有一个自旋锁，在读写缓存页面头部字段时使用（疑问，如果有这个锁，在修改头部字段时似乎就不需要持有 BufMappingLock 锁）。
• BM_IO_IN_PROGRESS 标志是一种锁，用来等待缓存页面的 IO。在从磁盘读物理页面到缓存页面，或者将缓存页面刷到磁盘的过程中，会将该标志置位，操作完成后清除标志位。等待标志位被清除的线程会使用条件变量休眠（疑问，如果有这个标志，那么在从磁盘读物理页面到缓存页面时，就不需要持有 BufMappingLock 锁吧）。

缓冲池管理器的优化就靠这部分内容，但是有些描述还是不太清晰（是不是我理解错误，并且文中涉及日志相关的内容，不是很好懂），实现的时候再想吧。然后文中还提出了如何对线性扫描做优化，但是我认为单纯在缓冲池管理器里面做不了这个优化，因为没办法识别当前操作是否是线性扫描，而且优化需要另开一个小缓冲池，这应该是查询优化器的任务。

③ 后台线程刷盘

• 按照淘汰顺序扫描页面，选择 is_dirty_ == true && pin_count_ == 0 的页面，然后 pin 该页面并刷盘，最后回收到空闲列表。
• 还有一些优化方式，没看懂就不翻译了。

总结一下，该文件中提到的优化，有一些可能跟它的页面替换算法相关（PostgreSQL 使用的是时钟扫描算法），或者和该数据库的其它特性相关（提示位之类的），看得云里雾里的，我们能够做的优化大概就是上面提到的这些，具体怎么实现还是走一步看一步吧。

尝试实现

重构代码，轻松通过本地测试，哭死。惊了，线上就一个测试没过。

① FetchPage 在判断 page_id 是否在 page_table_ 时，需要使用 page_table_ 的独占锁。并且如果页面不在 page_table_ 中，则在函数返回 nullptr 或修改 page_table_ 之前不能释放该锁，以防止多次 FetchPage 同一个 page_id 时，多次从 free_list_ 中获取页面或者多次淘汰页面。

② 因为在 FetchPage 将淘汰页面刷盘时，我会释放所有锁，这时页面是可以被 pin 的，所以之后设置 pin_count_ 时，不能直接设置为 1，而是进行 ++ 操作。

第一次重构没有拆分 BufMappingLock，没有使用自旋锁，其他的锁基本都加了。QPS 和之前的第 ② 个优化差不多，其实也可以想到，毕竟只是加了一些锁保证正确性，基本上没有提高并行性。本来想使用自旋锁的，但是因为需要条件等待，而条件变量只能用 unique_lock 作为参数，并且 atomic_flag 的原子等待只有在 C++ 20 才有，不好实现，遂放弃挣扎（而且估计不会有什么提升）。不搞了，像个小丑，没意思。

调试

① 优化的时候一步一步优化，然后进行测试，要不然调试半天，都不知道 BUG 在代码的哪个位置。

② 优化时容易出问题的点就是 NewPage 和 FetchPage，以及 UnpinPage。像是 FlushPage、FlushAllPage 以及 DeletePage 都可以暂时不管（可以直接 return），这样比较方便调试。

补充

① 在 C++ 20 之前，结构化绑定不能被 lambda 表达式捕获。

② 遇到 Reference to non-static member function must be called 问题，解决方案在此。

③ MySQL Buffer Pool 的实现 15.5.1 Buffer Pool。

④ Linus Torvalds 发表的一篇评论：do not use spinlocks in user space, unless you actually know what you’re doing。

⑤ 条件变量如果使用不当，可能会导致唤醒丢失，必须利用锁保证不会在等待前执行唤醒操作。

⑥ 发现一个感觉不错的博客：MC++。

测试结果

测试通过！本地的测试数据比较弱，而且没有并发测试。如果线上测试遇到问题，可以通过添加打印语句，线上看输出来调试。基本上没遇到什么大问题，都是细节问题，很容易漏判断一些条件。另外，加锁优化是可选的，暴力加锁就可以通过测试。

优化任务让我的提交记录暴涨，特别是在尝试第 ③ 个优化方案时。一般等 4 分钟才能出结果，有时候评测机还会出问题，算下来等结果的时间都有 8 小时，离谱。

每次本地测试都需要输入很多命令，提交线上又要格式化，如果手动输入太麻烦了，可以写个 shell 脚本来执行：

1
2
3
4
5
6
7
8
9

#!/bin/bash
make lru_k_replacer_test buffer_pool_manager_test page_guard_test -j$(nproc)
./test/lru_k_replacer_test
./test/buffer_pool_manager_test
./test/page_guard_test
make format
make check-lint
make check-clang-tidy-p1
make submit-p1

项目小结

① 在做项目的时候，总是会想某个地方是不是有更优的写法，但是当时对整个项目结构不太清楚，以及代码实现是否正确也不清楚，所以基本上都是浪费时间。据此，我的收获就是先让代码跑起来，其他的之后再说。

② 虽然做的时候很艰辛，但是做完之后发现，好像也没有什么工作量，bpm 优化也就是简单减少锁的粒度，lru 的优化也完全是针对基准测试做的，感觉我的优化方式很烂，有没有更牛逼的优化方式啊。

③ 我好菜啊！！！前三个任务花了两天，优化花了好几天。

更新：发现 Lecture #06 就是讲 BufferPool 优化的（课堂笔记），不知道能不能在这用上，等做完所有 Project 再来试试。