阅读论文 Frangipani，参考 FAQ，note。

概述

Frangipani 是一个分布式文件系统，由 Petal 分布式存储服务和多个 Frangipani 服务器组成，Frangipani 服务器共享 Petal 提供的单个虚拟磁盘抽象，同时使用分布式锁保证缓存一致性。

实现

预写日志

每个 Frangipani 服务器都会使用预写日志记录系统元数据的变化（不记录文件数据），只有当日志持久化到 Petal 之后，才能修改系统的元数据。日志首先会按顺序存放在服务器内存的循环缓冲区中，然后定期刷新到 Petal。使用日志记录元数据的变化，可以避免服务器故障时元数据的部分更新导致文件系统结构被破坏（产生不一致），从而可以避免运行 fsck 一致性检查程序，实现快速恢复。

日志由若干大小为 512 字节的日志块组成，每个日志块都有一个单调递增的序列号。论文表示序列号作用是在故障恢复时检测日志的末尾，即使磁盘乱序写入数据。元数据由若干大小为 512 字节的元数据块组成，每个元数据块都有一个单调递增的版本号。日志块也会包含其所修改元数据块的版本号，只有日志块中的版本号大于元数据块的版本号时，才能应用日志。从而可以避免服务器故障恢复时，旧日志覆盖新版本的元数据，以及重复应用已经应用的日志。512 字节的日志块和元数据块实际上对应一个扇区，扇区的读写保证是原子的。

PS：论文提到元数据块被释放然后重用于文件数据导致版本号消失的问题，然后说明限制释放的元数据块仅被新的元数据块重用可以解决该问题。此处所说的元数据块应该是指扇区，所有才会释放和重用，也就是说版本号实际上是和元数据块所在的扇区绑定，而和元数据是什么无关。而且，之所以版本号消失会有问题，是因为日志块记录的是所修改元数据块的扇区位置。这种设计有点奇怪，日志块以及版本号不和修改的元数据关联，而是和扇区关联。

分布式锁

锁服务使用 Paxos 进行容错，为文件系统提供读写锁。当锁服务检测到冲突的锁请求时，会要求当前锁的持有者释放或降级锁，以消除冲突。读写锁允许 Frangipani 服务器从磁盘获取数据并将其缓存。在释放读写锁前，服务器会使缓存无效，从而保证缓存一致性。在释放或降级写锁前，服务器必须将脏数据写入磁盘（包括文件数据）。磁盘被划分为若干逻辑段，每个段都有一个锁，每个日志、文件、目录和符号链接都是一个段。每个文件使用一个锁，适合很少并发写的工作负载，其他负载可能需要使用更细粒度的锁。

锁具有粘性，也就是说 Frangipani 服务器获取锁之后不会主动释放，除非锁服务要求其释放。当挂载 Frangipani 文件系统时，Frangipani 服务器会调用 clerk 模块，该模块会连接到锁服务，获取租约并且在本地打开一个锁表。当文件系统被卸载时，clerk 会关闭锁表。clerk 和锁服务使用异步消息进行通信，有四种消息类型：request、grant、revoke 和 release。

故障处理

当 Frangipani 服务器的租约由于没有续约而过期时，锁服务会认为该服务器故障，此时需要一种机制来释放故障服务器持有的锁。锁服务会在另一个 Frangipani 服务器上启动恢复进程，新服务器会获取租约和故障服务器日志的锁，然后按顺序应用未执行的日志，最后释放（release）所有锁以及释放（free）日志。如果是由于网络分区故障而没有续约，租约过期的 Frangipani 服务器会主动丢弃其所有锁和缓存数据。如果缓存中存在脏数据，则服务器会向用户程序报告错误，将问题交给用户处理。

如果租约在服务器向 Petal 发送写入请求之后到达之前过期，则会产生问题，因为此时锁可能已经被授予故障恢复服务器。论文提到可以为每个写入请求添加过期时间戳，如果请求到达 Petal 的时间戳大于请求中的时间戳，则拒绝该请求。或者将锁服务和 Petal 集成，服务器为写入请求添加租约标识符，然后 Petal 可以判断租约是否过期。

问题

Q：日志序列号的作用有点奇怪，为什么磁盘要乱序写入数据？

Q：日志只会记录元数据，那么有可能只执行元数据更改，而丢失文件数据？

A：该语义符合标准的本地 Unix 文件系统，崩溃之前的写入可能会丢失。应用程序可以使用 fsync 系统调用，强制将数据立即刷新到磁盘。

总结

预写日志存储在 Petal 提供的共享虚拟磁盘上，使得任何服务器都可以使用故障服务器的日志进行恢复。多个日志使得恢复过程变得复杂，需要使用版本号机制避免异常。分布式锁保证服务器之间的缓存一致性。Frangipani 服务器运行在用户侧，负责和共享磁盘通信，该设计要求用户是可信的。该系统使用粗粒度的锁定，一个文件对应一个锁，所以不适用于经常并发写入相同文件的负载。论文的性能测试我没有太多时间看，总结时也忽略了一些我认为不是很重要的细节。

Rectangle Cutting

题目

输入两个整数 \(a\) 和 \(b\)，表示矩形 \(a\times b\)，判断是否能将矩形切割一次再拼接得到不同的矩形，切割线要求平行于某条边且得到的矩形边长为整数。

数据范围：\(1\leq a,b\leq 10^{9}\)。

思路

以下讨论总是假设 \(a\leq b\)：

• 首先我们总是应该对半切，如果不对半切，并且想要拼接得到矩形，那么只能切割更长的边 \(b\)，得到 \(a\times a\) 和 \(a\times(b-a)\)，但是不论怎么拼接都和原矩形相同。
• 如果 \(a\) 是偶数，可以总是对半切 \(a\)，然后拼接得到不同的矩形 \(\frac{a}{2}\times 2b\)。
• 如果 \(a\) 是奇数，\(b\) 必须是偶数，否则无法对半切。此时只能对半切 \(b\)，拼接得到矩形 \(2a\times\frac{b}{2}\)，当 \(a\neq\frac{b}{2}\) 时，得到的矩形和原矩形不同。

代码

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

public static void solve() {
    int a = io.nextInt(), b = io.nextInt();
    if (a > b) {
        int t = a;
        a = b;
        b = t;
    }
    if (a % 2 == 0 || b % 2 == 0 && b != 2 * a) {
        io.println("Yes");
    } else {
        io.println("No");
    }
}

Equalize

题目

输入长度为 \(n\) 的数组 \(a\)，可以选择一个 \([1,n]\) 的任意排列 \(p\)，执行 \(a_{i}=a_{i}+p_{i}\) 操作。输出执行操作之后，能够得到的数组 \(a\) 中相同元素最大出现次数的最大值。

数据范围：\(1\leq n\leq 2\cdot 10^{5}\)，\(1\leq a_{i}\leq 10^{9}\)。

思路

将数组加上任意排列，肯定是更小的数对应更大的数，才能使相同元素的最大出现次数最大化。我们可以将数组 \(a\) 排序同时去重，之所以去重是因为相同元素加上排列之后必定不相同，然后将排列看作固定的递减数组。只要数组 \(a\) 中的两个数的差值小于 \(n\)，那么这两个数之间的元素必定可以在操作之后变成相同的元素。问题就转化为求区间的最大长度，同时最大值和最小值的差值小于 \(n\)，可以使用滑动窗口求解。

代码

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

public static void solve() {
    int n = io.nextInt();
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < n; i++) {
        set.add(io.nextInt());
    }

    int m = set.size(), idx = 0;
    int[] a = new int[m];
    for (var x : set) {
        a[idx++] = x;
    }

    int ans = 1;
    for (int i = 0, j = 1; j < m; j++) {
        while (a[j] - a[i] >= n) {
            i++;
        }
        ans = Math.max(ans, j - i + 1);
    }
    io.println(ans);
}

Physical Education Lesson

题目

输入两个整数 \(n\) 和 \(x\)，求 \(k\) 的个数，使得对于编号为 \(1\) 到 \(k\) 的位置，满足第 \(n\) 个位置的编号为 \(x\)。第 \(n\) 个位置是按往返来计算的，例如 \(1,2,\dots,k-1,k,k-1,\dots,2,1\)，第 \(1\) 和 \(1+2k-2\) 个位置的编号都为 \(1\)。当 \(k>1\) 时，编号循环的周期就是 \(2k-2\)。题目限制 \(k>1\)。

数据范围：\(1\leq x<n\leq 10^{9}\)。

思路

\(k\) 必须满足 \(k\geq x\)，同时 \((2k-2)\cdot t+x=n\) 或 \((2k-2)\cdot t+k+k-x=n\)，变形得到 \(n-x=2\cdot(k-1)\cdot t\) 或 \(n+x-2=2\cdot(k-1)\cdot(t+1)\)。求 \(k\) 的个数，可以首先求出 \(\frac{n-x}{2}\) 和 \(\frac{n+x-2}{2}\) 的约数，约数加一就是满足等式的 \(k\) 值，最后限制 \(k\geq x\)，得到答案。其实也可以不使用集合去重，只需要特判 \(x=1\) 和 \(k=x\) 的情况。

代码

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

public static void solve() {
    int n = io.nextInt(), x = io.nextInt();
    Set<Integer> set = new HashSet<>();
    calc(n - x, x, set);
    calc(n + x - 2, x, set);
    io.println(set.size());
}

private static void calc(int x, int y, Set<Integer> set) {
    if (x % 2 != 0) {
        return;
    }
    x /= 2;
    for (int i = 1; i <= x / i; i++) {
        if (x % i == 0) {
            if (i + 1 >= y) {
                set.add(i + 1);
            }
            if (x / i != i && x / i + 1 >= y) {
                set.add(x / i + 1);
            }
        }
    }
}

Lonely Mountain Dungeons

题目

输入三个整数 \(n,b,x\)，以及长度为 \(n\) 的数组 \(c\)。有 \(n\) 种生物，每种生物的数量为 \(c_{i}\)。你需要将所有生物分为 \(k\) 组，位于不同组的每对同种生物会使总分增加 \(b\)，同时总分会减少 \((k-1)\cdot x\)。输出能够得到的最大分数。

数据范围：\(1\leq n\leq 2\cdot 10^{5}\)，\(1\leq b\leq 10^{6}\)，\(0\leq x\leq 10^{9}\)，\(1\leq c_{i}\leq 2\cdot 10^{5}\)，\(\sum_{i=1}^{n}c_{i}\leq 2\cdot 10^{5}\)。

思路

首先需要知道，对于某种生物 \(i\) 和固定的 \(k\)，将 \(c_{i}\) 尽量平均分配是最优的，不过我也不知道该怎么证明。当 \(k>c_{i}\) 时，得分总是为 \(C_{c_{i}}^{2}\cdot y^{2}\)。当 \(k\leq c_{i}\) 时，就需要将 \(c_{i}\) 分为，\(c_{i}\bmod k\) 组包含 \(y=\lceil\frac{c_{i}}{k}\rceil\) 个该种生物，\(k-c_{i}\bmod k\) 组包含 \(y^{\prime}=\lfloor\frac{c_{i}}{k}\rfloor\) 个该种生物。得分为：

根据以上讨论，很容想到暴力枚举组数 \(k\)，然后内层循环计算该组数下的最大得分，总时间复杂度为 \(O(\max(c_{i})\cdot n)\)。由于题目限制 \(\sum_{i=1}^{n}c_{i}\leq 2\cdot 10^{5}\)，我们可以预处理得到所有 \(c_{i}\) 在组数为 \([1,c_{i}]\) 下的最大得分之和，从而可以将暴力枚举的内循环优化为 \(O(1)\) 时间复杂度。

代码

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

public static void solve() {
    int n = io.nextInt(), b = io.nextInt(), x = io.nextInt();

    int m = 0;
    int[] c = new int[n];
    for (int i = 0; i < n; i++) {
        c[i] = io.nextInt();
        m = Math.max(m, c[i]);
    }

    long[] f = new long[m + 1];
    long[] g = new long[m + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= c[i]; j++) {
            f[j] += calc(c[i], j);
        }
        g[c[i]] += calc(c[i], c[i]);
    }

    long ans = 0L;
    for (int i = 1; i <= m; i++) {
        ans = Math.max(ans, (f[i] + g[i - 1]) * b - (long) (i - 1) * x);
        g[i] += g[i - 1];
    }
    io.println(ans);
}

private static long calc(int n, int k) {
    int a = n / k, b = n % k;
    long res = (long) (k - b) * (k - b - 1) / 2 * a * a;
    res += (long) b * (b - 1) / 2 * (a + 1) * (a + 1);
    res += (long) (k - b) * b * a * (a + 1);
    return res;
}

阅读论文 Chain Replication，参考 note。

概述

链式复制是一种容错复制方式，可以保证高性能、高可用和强一致性（可线性化）。客户端的请求都以原子的方式执行，查询请求直接发送到 tail，更新请求发送到 head，然后沿着链传递到 tail。在没有故障的情况下，可线性化保证源于以下两点：只有 tail 会响应客户端的请求，以及更新操作只会在 head 计算一次，从而可以避免冗余计算和非确定性操作带来的一致性问题。

实现

基本概念

对象由 \(objID\) 唯一标识，\(Hist_{objID}\) 表示该对象上已执行的请求，\(Pending_{objID}\) 表示该对象上待执行的请求。对于链式复制来说，客户端视图中的 \(Hist_{objID}\) 被定义为 tail 存储的 \(Hist_{objID}\)，\(Pending_{objID}\) 被定义为任何服务器接收到的、没有被 tail 执行的客户端请求。注意，这两个状态都是对象的客户端视图，而不是实际存储在服务器中的数据。此外，论文只是为方便论证才将对象状态描述为 \(Hist_{objID}\)，实际的状态应该是对象的当前值。

故障检测和恢复

链式复制使用额外的服务来检测故障，重新配置链，通知客户端链头和链尾对应的服务器。论文称该服务为 master，使用复制进行容错，使用 Paxos 维持多个 master 副本之间的一致性。可以将其视为类似 ZooKeeper 的协调服务。虽然论文没有提及，不过检测故障通常是使用定时心跳。

链头故障

master 直接将 head 的下一个节点作为新的 head，然后通知客户端。所有旧 head 接收而未转发给后继的请求最终都会超时，然后客户端会重试。该过程相当于执行 T2 转移。

链尾故障

master 直接将 tail 的上一个节点作为新的 tail，然后通知客户端。因为更新是从前往后传播的，所以上一个节点的视图至少和旧 tail 的视图一样新，不会影响一致性。该过程相当于执行 T3 转移。

中间故障

master 会修改故障节点的前驱和后继的指针，从而将故障节点从链中删除。但是，如果前驱转发更新请求到故障节点，而故障节点没有将其转发至后继，那么前驱需要一种机制识别这部分请求，然后重新将其转发至后继。

每个服务器维护一个更新请求的已转发列表 \(Sent\)，当服务器将请求转发到后继时，会将该请求添加到列表中。当更新请求 \(r\) 转发到尾节点，并被尾节点处理时，尾节点会向前驱发送确认信息 \(ack( r)\)。收到 \(ack( r)\) 的服务器会将 \(r\) 从 \(Sent\) 列表中删除，同时将 \(ack( r)\) 转发到前驱。

当中间节点 \(S\) 故障，master 向后继 \(S^{+}\) 发送其新的前驱 \(S^{-}\)，\(S^{+}\) 会响应 master 确认消息，其中包含 \(S^{+}\) 收到的最后一个更新请求的序列号。然后 master 向前驱 \(S^{-}\) 发送其新的后继 \(S^{+}\) 和序列号，\(S^{-}\) 会将在 \(Sent_{S^{-}}\) 中且在序列号之后的请求转发到 \(S+\)，这部分请求就是故障节点 \(S\) 未转发至 \(S^{+}\) 的请求。该机制的关键在于保留已发送请求的列表，\(ack\) 的作用只是回收空间。

恢复冗余

发生故障的服务器会从链中删除，需要恢复冗余以保证容错。理论上，可以将新服务器添加到链中的任意位置。实践中，添加到链尾比较简单。master 会要求当前链尾 \(T\) 转发对象已执行的请求队列 \(Hist_{objID}^{T}\) 到新的链尾 \(T^{+}\)，在转发完成之前，依然是当前链尾 \(T\) 执行查询请求和前驱传来的更新请求，以及响应客户端。该过程中执行的更新请求同时会被添加到 \(Sent_{T}\)，该操作与 \(Sent_{T}\) 的定义不一致，之后会处理。当 \(Hist_{objID}^{T}=Hist_{objID}^{T^{+}}\oplus Sent_{T}\) 成立时，也就是转发开始时的 \(Hist_{objID}^{T}\) 都转发到 \(T^{+}\) 时，\(T^{+}\) 可以成为链尾。

过程如下：如果 master 收到上述不变式成立的通知，master 会通知 \(T\) 其不是链尾，之后 \(T\) 会将收到的查询请求转发到 \(T^{+}\)。然后 \(Sent_{T}\) 中的更新请求也会被转发到 \(T^{+}\)，转发完成之后，就符合 \(Sent_{T}\) 的定义，\(T\) 会通知 master 将 \(T^{+}\) 作为新的链尾。然后，master 会通知客户端新的链尾。PS：注意，此时 \(Sent^{T}\) 中的请求已经响应客户端。

对比主从复制

链式复制可以视为特殊的主从复制，头节点和尾节点共同充当主节点，其他节点作为从节点。相比传统的主从复制（指的是强一致性的主从复制）：

• 链式复制的查询，由链尾的服务器处理，不会被链中其他服务器的活动延迟。而主从复制的查询，主节点需要等待之前的更新被从节点确认，才能执行查询。PS：个人理解，指的应该是多客户端之间的更新和查询，单客户端是同步的，只有接收到上一个请求的响应才会发送下一个请求，否则链式复制是无法保证客户端的 FIFO 执行顺序。
• 链式复制串行传播更新，主从复制并行传播更新，所以链式复制的更新延迟更高，而且和链的长度成正比。

测试

根据论文中的模拟实验可以发现，链式复制比主从复制具有更高的读取性能，但是强一致性保证使得读写性能不能随着机器的数量线性扩展，不像 ZooKeeper。比较令人惊讶的是，在更新请求至少占总请求数的 15% 时，弱一致性保证的读取方案反而会降低系统的总吞吐量，因为在头节点的查询和更新会产生竞争。主从复制的吞吐量不会受复制因子的影响，而链式复制的更新是串行传播的，似乎吞吐量会随着链的长度增加而减少。但是，只要有足够多的更新请求，那么通过一个预热时间启动流水线，吞吐量可以恢复正常水平。

问题

Q：更新请求不是幂等的，如果响应丢失，客户端重试更新请求怎么办？

A：目前讨论的系统：GFS 的 primary chunkserver 重试会导致重复追加，我猜客户端重试大致也是如此；VM-FT 请求是否幂等取决于虚拟机中的应用程序；Raft 要求请求包含唯一标识，在状态机层去重；尽管 ZooKeeper 的事务是幂等的，但是请求不是幂等的，没有讨论如何处理；链式复制论文提到可以在重试之前，进行查询判断更新是否已经执行。总的来说，是否要求幂等是根据系统的实际使用场景而定的，课程中也提到，ZooKeeper 和链式复制也可以使用和 Raft 类似的方法去重，从而实现幂等。

Q：更新请求的延迟和链的长度成正比，那么超时时间会更长，如果请求丢失似乎需要更多等待？

Q：如果链头 \(S\) 和 master 发生网络分区故障，那么 \(S^{+}\) 会成为新链头，而此时 \(S^{+}\) 依然会收到旧链头 \(S\) 的转发。节点必然需要一种机制判断是否应该忽略请求，这可以通过简单的判断请求的来源是否是其前驱来实现。

Q：客户端在连接到服务器时，以及链头或链尾被改变时，master 需要通知客户端，如果客户端很多会有什么问题？

总结

课程提到，复制状态机有两种主要的实现方式，一种是使用共识算法复制所有操作，另一种是使用配置服务 + 主从复制，配置服务中的共识算法仅复制元数据，其他操作不需要使用共识算法复制。链式复制使用的是第二种方式，它需要利用额外的配置服务进行故障恢复，同时避免脑裂。链式复制概念简单，只有中间故障和恢复冗余稍微复杂一点。和共识算法不同，只要有一个服务器故障，就可能会导致读请求或写请求的短暂中断。论文在模拟实验中提到多链和对象放置策略，我认为论文的描述很模糊，所以没介绍。