参考 SRE deep dive into Linux Page Cache，mm/workingset.c，io_uring。

环境准备

安装依赖，下载内核源码，编译、安装 page-types 工具，生成测试数据文件，同步、清空缓存。

1

$ sudo apt install git build-essential golang vmtouch

1
2

$ uname -r
6.2.0-36-generic

1
2
3
4
5
6
7

$ mkdir kernel
$ cd kernel
$ wget https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/snapshot/linux-6.2.tar.gz
$ tar -xzf linux-6.2.tar.gz
$ cd linux-6.2/tools/vm
$ make
$ sudo make install

1

$ dd if=/dev/random of=/var/tmp/file1.db count=128 bs=1M

1

$ sync; echo 3 | sudo tee /proc/sys/vm/drop_caches

基本概念

基本操作

File reads

使用 Python 代码从文件读取 2B 数据，发现实际会读取 16 KB 的数据到缓存，操作系统会预读多个页面。使用 posix_fadvise() 提示内核，文件是随机访问的，此时内核不会使用预读优化。实测使用 mmap 系统调用，将文件映射到进程的虚拟内存，依然读取 2B 数据，此时内核预读 32 页而不是 read 系统调用的 4 页。

1
2

with open("/var/tmp/file1.db", "br") as f:
    print(f.read(2))

1
2
3
4
5
6

$ strace -s0 python3 ./read_2_bytes.py
...
openat(AT_FDCWD, "/var/tmp/file1.db", O_RDONLY|O_CLOEXEC) = 3
...
read(3, ""..., 4096)                    = 4096
...

1
2
3
4
5

$ vmtouch /var/tmp/file1.db
           Files: 1
     Directories: 0
  Resident Pages: 4/32768  16K/128M  0.0122%
         Elapsed: 0.001331 seconds

1
2
3
4
5
6

import os

with open("/var/tmp/file1.db", "br") as f:
    fd = f.fileno()
    os.posix_fadvise(fd, 0, os.fstat(fd).st_size, os.POSIX_FADV_RANDOM)
    print(f.read(2))

1

$ echo 3 | sudo tee /proc/sys/vm/drop_caches && python3 ./read_2_random.py

1
2
3
4
5

$ vmtouch /var/tmp/file1.db
           Files: 1
     Directories: 0
  Resident Pages: 1/32768  4K/128M  0.00305%
         Elapsed: 0.001301 seconds

File writes

更新文件的前 2B，发现内核读取 1 页数据到缓存。如果及时查看当前 cgroup 的脏页大小，会发现有 4KB 的数据还未刷盘。也可以使用 cat /proc/meminfo | grep Dirty 查看整个系统中的脏页大小，但是很难利用该信息。

1
2

with open("/var/tmp/file1.db", "br+") as f:
    print(f.write(b"ab"))

1

$ sync; echo 3 | sudo tee /proc/sys/vm/drop_caches && python3 ./write_2_bytes.py

1
2
3
4
5

$ vmtouch /var/tmp/file1.db
           Files: 1
     Directories: 0
  Resident Pages: 1/32768  4K/128M  0.00305%
         Elapsed: 0.001764 seconds

1
2
3
4

$ cat /proc/self/cgroup
0::/user.slice/user-1000.slice/user@1000.service/app.slice/app-org.gnome.Terminal.slice/vte-spawn-7fe5140d-9b95-4aff-9979-de88b1c42b94.scope
$ grep dirty /sys/fs/cgroup/user.slice/user-1000.slice/user@1000.service/app.slice/app-org.gnome.Terminal.slice/vte-spawn-7fe5140d-9b95-4aff-9979-de88b1c42b94.scope/memory.stat
file_dirty 4096

1
2
3
4
5
6
7
8

$ sudo page-types -f /var/tmp/file1.db -b dirty
/var/tmp/file1.db       Inode: 402310   Size: 134217728 (32768 pages)
Modify: Mon Oct 13 19:35:25 2025 (2 seconds ago)
Access: Mon Oct 13 18:21:11 2025 (4456 seconds ago)

             flags      page-count       MB  symbolic-flags                     long-symbolic-flags
0x0000000000000038               1        0  ___UDl_______________________________________      uptodate,dirty,lru
             total               1        0

缓存淘汰

每个 cgroup 都有一对活跃和非活跃列表，一对用于匿名页面，另一对用于文件页面。简单来说，发生缺页的页面被插入到非活跃列表，在非活跃列表被多次访问的页面升级到活跃列表。使用 LRU 算法结合 referenced 标志，控制页面的升级、降级和淘汰。referenced 被置位的页面，相当于在降级/淘汰时可以复活到当前列表的头部。此外，页缓存还会利用 shadow entry 计算 refault distance，从而减少非活跃列表空间不足导致的内存抖动问题。如果系统有 NUMA 节点，则会为每个节点维护列表，以减少锁竞争。

参考 2PC，3PC，Oracle Transaction Manager，Seata Transaction Mode，Seata Blog（重要）。

没有时间细看各个资料和实现，以下内容掺杂个人理解，不保证正确性。 各个方案实际上就是在强一致性和可用性之间做权衡，一般保证可用性会选择最终一致性。

2PC & 3PC & XA & AT

两阶段提交分为准备和提交/回滚阶段：① 协调者向参与者发送准备请求，参与者执行操作并持久化状态，然后回复同意/拒绝。如果准备请求超时，由于某个参与者网络分区或崩溃，则协调者会直接决定中止事务。② 协调者根据参与者的回复决定提交/中止事务，只有当所有参与者都回复同意才会决定提交。协调者会将决定持久化，然后发送提交/中止请求。③ 参与者执行提交/回滚，然后回复确认。在协调者收到所有参与者的确认之后，此时可以响应客户端。否则，协调者会一直重试请求，直到参与者确认。

存在的问题：当参与者回复同意/拒绝之后，必须等待协调者做出决定，才能真正提交/回滚本地事务，期间会一直持有数据库锁。当协调者做出决定之后，必须等待所有参与者执行完成，才能响应客户端。不论是协调者还是参与者崩溃，都会阻塞整个事务。不过，某个参与者崩溃不会阻塞其他参与者的本地事务（要么提交要么回滚），由于有准备请求有超时中止机制。而协调者崩溃会阻塞所有参与者的本地事务。实际上，协调者可以使用共识算法实现容错，避免单点故障。

三阶段提交有 CanCommit、PreCommit 和 DoCommit 阶段。CanCommit 阶段只是询问参与者是否可以执行事务，而不会执行操作锁定资源，这样可以提前发现事务无法执行，避免无效的资源锁定。在 PreCommit 阶段，如果参与者回复同意，且在超时时间内没有收到协调器的提交/中止请求，则该参与者会主动提交事务（有不一致的风险）。3PC 不保证强一致性，而且相比 2PC 有额外的网络往返开销。

XA 是异构环境下实现 2PC 的工业标准，规定事务协调者和参与者通信的 API，其中异构是指参与者由不同数据库或消息队列组成。Seata 的 AT 模式从 2PC 演化而来，在准备阶段本地事务会直接提交，只不过在提交之前需要获取相关记录的全局锁，而且本地事务需要维护回滚日志表。协调器提交事务时，会让参与者异步批量删除回滚日志。回滚时参与者会根据全局和分支事务 ID 找到对应回滚日志，将日志中的后镜像数据和当前数据进行比较，根据配置的策略进行处理。AT 模式因为有全局锁，不存在脏写问题，不过默认的隔离级别是读未提交，因为读取默认不会获取全局锁，个人认为这也是它性能比 2PC 更好的原因（或许还有其他原因）。

Sega & TCC

基本概念：应用程序 AP，事务管理器 TM，资源管理器 RM，事务协调者 TC。Saga 模式没有 TCC 模式的预留操作，参与者会直接执行本地事务转移资源，存在脏写导致无法回滚的风险。例如转账场景，A 向 B 转账，如果 B 的余额增加之后，A 扣款失败，需要回滚 B 的余额，而 B 已经使用完该余额，则无法完成回滚（或者说无法完成补偿）。

TCC 表示 Try-Confirm/Cancel，有尝试阶段和确认/取消阶段。协调者请求参与者预留资源（将资源转移到中间表），如果所有资源都预留成功，则确认所有预留，否则取消所有预留。因为请求超时会重试请求，所以需要保证预留、确认和取消操作的幂等性。该方案依赖业务层实现预留、确认和取消操作，这些操作都是单独的本地事务，不存在长期持有数据库锁的问题。

操作的幂等性可以通过在数据库中维护分支事务状态表，使用全局事务 ID + 分支事务 ID 去重来实现。分支事务状态表应该存储在本地，因为要保证操作和事务状态更新的原子性，利用本地事务可以做到。不过协调者也要维护全局事务状态表，从而根据事务状态决定执行预留、确认还是取消操作。（或者有其他方案）

如果协调者请求参与者预留资源超时且重试次数耗尽，则会直接中止事务，取消所有预留的资源。如果没有预留资源的参与者收到取消预留的请求，则不会执行任何操作而是直接返回成功（空回滚）。协调者可以使用共识算法容错，根据全局事务的状态，决定预留资源或者确认/取消分支事务预留的资源。如果参与者在收到取消预留请求之后收到预留资源的请求，则会发生资源悬挂的问题。参与者在预留之前会检查该事务是否发生空回滚，如果发生则拒绝本次预留请求。

本地消息表 & 事务消息

分布式事务的问题在于，事务发起者执行本地事务之后，无法保证其他参与者的本地事务也能够执行成功。以转账为例，A 向 B 转账，A 本地执行扣款之后，向 B 发送转账请求，A 无法保证 B 执行成功，存在不一致的风险。之前的 2PC 方案是通过数据库协调来保证事务的原子性，TCC 方案是通过业务层面的设计保证全局事务的原子性。

另一种方案就是，事务发起者将待发送的请求存储到本地消息表中，和业务操作放在同一个事务中执行。然后使用定时任务定期扫描本地消息表，将待发送的消息发送给消息队列，如果发送成功则从表中删除该消息记录（或者修改状态为已发送）。事务参与者监听消息队列，拉取消息执行本地事务，然后向消息队列回复确认消费。

由于本地事务具有原子性，事务发起者可以保证业务操作执行成功时，请求消息也被记录到本地消息表。定期扫描会保证消息最终会被发送到消息队列，消息队列可以保证消息至少被消费一次，最后消费者需要再业务层面保证消费的幂等性，例如使用唯一 ID 在数据库层面去重。

注意，Kafka 保证内部的精确一次消息传递，但涉及到外部数据库就只能保证至少一次。如果需要精确一次，可以利用业务层面的幂等性做去重，也可以使用 2PC。或者利用本地事务的原子性，将日志偏移量和业务数据同时存储到数据库，然后消费者重启时读取偏移量来保证不重复消费（其实就是本地消息表方案）。

可以使用 RocketMQ 的事务消息功能实现类似本地消息表的方案。事务发起者首先向消息队列发送半消息，该消息对消费者不可见。然后发起者执行本地事务（执行业务操作 + 维护事务状态），根据本地事务的执行结果向消息队列发送提交/回滚请求，如果提交则消费者可以消费相应消息。如果发起者长时间未提交/回滚事务消息，消息队列会调用发起者提供的回查接口来查询事务状态。超时回查机制类似本地消息表的定时任务机制，目的都是保证最终一致性。事务消息方案依然需要发起者维护事务状态表，只是不需要自己使用定时任务扫描来重试请求，而是将扫描的工作交给消息队列。

不论本地消息表还是事务消息方案，如果参与者无法消费消息直到重试次数耗尽，则需要设计额外的回滚机制或者人工干预。而且和 Saga 策略类似，由于不会预留资源，存在脏写导致无法回滚的问题。这需要业务流程上做设计，保证能够通过人工干预完成事务，或者不断重试直到成功。

参考 GitHub Awesome System Design。

短链系统

我的想法

核心功能就是长链转短链，可以从使用算法和存储方式两个方面思考。算法首先想到的是哈希函数，可以将长链转为一个短链整数（需要处理哈希冲突），然后使用 Base62 编码为包含 [0-9a-zA-z] 的短链字符串。存储时可以存储长链和短链整数/字符串，不同存储格式主要是时间和空间的权衡，然后需要分别在两个字段上建立唯一/前缀索引来加速查询。

实际上可以将数据库的主键 ID 作为短链整数，这样空间占用更小，也不存在哈希冲突。查询短链到长链的映射可以直接利用主键索引，只需给长链建立索引来加速反向查询。虽然每次查询都要将短链整数编码为短链字符串，不过时间开销不算大，长度为 7 的字符串就可以表示 \(62^7\approx3\times 10^{12}\) 个不同的短链，而且可以使用缓存提升查询性能。

文章内容

需求分析可以分为功能性需求和非功能性需求，功能性需求主要是业务需求，非功能性需求包括高性能、高可用、可扩展性和安全性。然后可以假设流量特征来估算系统的吞吐量、磁盘/内存空间以及带宽需求。流量特征可以从每日缩短 URL 的请求数量、读写比例、峰值流量和平均 URL 长度等方面思考。最后根据估算结果来估计需要的基础设施。

假设每天 100 万个缩短 URL 的请求，读写比例 100 : 1，峰值流量是平均负载的 10 倍，平均 URL 长度为 100 个字符。计算吞吐量，平均写吞吐量 \(\frac{\times 10^{6}}{24\times3600}\approx 12\) WPS，平均读吞吐量 \(100\times 12=1200\) RPS。假设每个 URL 占用 127 字节的存储空间，由短链 7 字节、长链 100 字节、创建时间 8 字节、到期时间 8 字节和点击次数 4 字节组成，那么每年就需要 \(127\times 10^{6}\times 365\approx 46.4\) GB 的磁盘存储空间。假设读取返回的 HTTP 301 重定向大小为 500 字节，每天读取带宽为 \(500\times 10^{6}\times 100= 50\) GB/day，每秒峰值读取带宽为 \(500\times RPS\times 10= 6\) MB/s。

系统负载是读多写少的，假设负载符合二八定律（Pareto principle），即 20% 的 URL 产生 80% 的读取流量。假设每天缓存 20% 的 URL，则需要 \(127\times 10^{6}\times 0.2=25.4\) MB 的内存作为缓存。假设缓存命中率为 90%，则到达数据库的平均请求数量为 \(1200\times0.1=120\) RPS。最后根据以上估算结果，估计使用 4-6 个服务器，每个服务器能够处理 200~300 RPS，10~20 个分布式数据库节点，3~4 个分布式缓存节点。

由于需要存储数十亿条记录，而且数据库操作大多是简单的键值查找，不需要执行复杂的表连接，所以选择使用 DynamoDB 或 Cassandra 等 NoSQL 数据库，因为它们能够高效处理数十亿次简单键值的查找，而且提供高可扩展性和高可用性。

可以对长链使用哈希函数（MD5、SHA-256）得到哈希值，然后取哈希值的前缀转十进制，再使用 Base64 编码得到短链。要处理哈希冲突，可以使用不同的种子重新哈希或者取哈希值的其它位生成短链，也可以将增量后缀附加到短链。另一种生成短链的方式是使用分布式 ID（数据库自增 ID、Redis 生成 ID、雪花算法），从安全性角度思考，增量 ID 是可预测的，有人可以通过使用短链服务推断系统的 URL 总数或者猜测其他用户生成的 URL，混淆（Obfuscation）增量 ID 可以缓解该问题。

额外功能：① 用户自定义短链，需要进行格式校验以及唯一性检查，如果和已有的短链发生冲突，服务器可以返回错误或者建议的替换方案。服务器还可以保留部分短链，以供内部使用。② 设置短链的过期时间，由用户指定或者使用默认的过期时间，可以使用定时任务或者在请求时检测短链是否过期，然后（逻辑）删除过期短链。③ 可以使用消息队列记录短链的访问日志，然后批量处理日志将其聚合存储在数据仓库中，以实现分析服务。

其他问题：① 使用负载均衡、基于范围/哈希的分片、缓存保证可扩展性。② 使用复制、自动故障转移、跨多个地理区域部署服务保证可用性。③ 处理边界条件，例如对于过期短链服务器返回 HTTP 401 状态码，不存在的短链返回 404 状态码，在生成短链时检测冲突。④ 限流防止滥用，输入校验确保用户提供的短链不包含恶意内容，使用 HTTPS 防止窃听和中间人攻击，对异常活动模式进行监控和报警。

遗漏的点

功能性需求没有想到重定向和过期时间的设计，以及允许用户自定义短链、数据分析等额外功能。重定向可以使用 301/302 状态码（永久/临时重定向），临时重定向每次请求都会经过短链服务，从而可以统计短链的使用次数。没有特别思考非功能性需求，基本上是从单服务器的角度思考问题。对哈希函数有点误解，误认为哈希的结果都是整数，像是 MD5、SHA 生成的哈希值都是可以包含字母的。我之前都是默认使用 MySQL + Redis 的组合，没有想到使用其他 NoSQL 数据库。使用哈希函数索引实现长链快速判重，使用布隆过滤器过滤请求。

一些疑问

Q：为什么估计使用 4-6 个服务器，10~20 个分布式数据库节点，3~4 个分布式缓存节点？

Q：文章描述的系统似乎只会检测短链冲突，而没有检测重复的长链？

Q：DynamoDB 和 Cassandra 数据库有什么特点？

排行榜系统

我的想法

排行榜主要是按照分数对用户进行排序，功能性需求主要是显示排名和更新排名。像是游戏打完排位会显示排名上升多少，然后排行榜只会显示 TopK 用户，每隔固定时间才更新榜单。像是算法比赛的排行榜会显示所有用户，榜单也是实时更新的。对于 TopK 榜单一般会使用小顶堆来实现，当新分数大于堆顶元素时，就弹出堆顶元素然后将当前元素入堆。

那么其他用户如何在分数变化之后计算排名呢？简单的想法就是直接更新 MySQL 数据库中的分数，然后获取所有小于该分数的用户数量。对于游戏这种分数频繁变化的场景，更新、查询数据库的磁盘 I/O 开销较大。如果能够将所有用户的分数信息缓存到 Redis 中，则可以直接使用跳表维护排行榜，然后使用消息队列异步更新数据库（类似后写缓存策略）。

像是算法比赛这种结束之后排名就不会变化的场景，数据库中也可以存储排名信息（而不只是分数）。如果内存中存不下所有用户的分数信息，可以对数据分片使用多个 Redis 节点维护排行榜，获取排名就需要对所有节点数据做聚合。应该也可以使用统计数据估算排名，返回给前端的是估算排名而不是真正的排名，然后后台使用定时任务去修正排名。

文章内容

排行榜分为绝对排行榜和相对排行榜，绝对排行榜显示 TopK 用户，相对排行榜显示指定用户周围的用户。HTTP 响应可以设置 cache-control: private, no-cache, must-revalidate, max-age=5 使用缓存，状态码 202 表示异步处理请求、401 表示身份未认证、403 表示没有权限，使用 HEAD 请求查看服务的健康状况。

功能性需求：绝对和相对排行榜，可以查看指定用户的排名，排行榜可以划分为全球、区域和朋友圈，可以查看历史比赛的排行榜，可以根据每天/周/月的游戏情况进行排名，客户端以分布式的方式在全球范围内更新排行榜。流量特征：每天 5000 万个写入请求，读写比例为 5 : 1，用户分布在全球各地，排行榜需实时显示。

客户端使用 WebSocket 协议和负载均衡器建立连接，保证排行榜的实时性（允许服务器主动推送数据）。依然使用 DynamoDB 实现可扩展性，将玩家 ID 作为分区键、玩家得分作为排序键。东西有点多，看得有点懵，先实现再说。

遗漏的点

单个用户的分数变化会导致其他用户的排名也发生变化（导致缓存失效），所以使用 MySQL 数据库获取排名的方式需要全表扫描更新所有用户的排名，或者延迟更新每个用户的排名，磁盘 I/O 开销会比我之前想的更大。更新 MySQL 分数之后应该主动更新缓存而不是删除缓存（从 Cache Aside 变为类似 Write Through），确保所有用户都在 Redis 的排行榜中（所以也不能设置过期时间），避免重建整个排行榜。不过主动更新缓存可能导致不一致，例如网络原因导致缓存更新失败、并发更新的顺序交错导致旧数据覆盖新数据，可以使用消息队列排队、重试请求保证正确性。

一些疑问

Q：既然游戏和用户的关系是一对多，即不同游戏的用户不会共享，那么完全没有必要将不同游戏的数据耦合到一个数据库中。而且 Redis 维护的排行榜数据以 leaderboard_id 作为键是有问题的，这可是 Leaderboards 表的主键。