Posts

FoundationDB 支持跨任意 key range 的 ACID 事务，并向应用提供严格可串行化语义。但它既没有让每个 Storage Server 参与经典的两阶段提交，也不是传统单机数据库中“共享缓冲池 + Undo/Redo”的事务实现。 它的核心方案可以概括为： 全局版本号 + MVCC 快照读 + 客户端暂存修改 + Resolver 乐观冲突检测 + 多副本 TLog 持久化。 本文结合 FoundationDB 官方源码，沿着一笔事务的完整路径，解释它如何从读取、提交、冲突检测，一直走到日志持久化和 Storage Server 应用。 本文分析的源码版本为： commit: eab21ffe07c20575d5bac9ab0745375b8f7f8357 date: 2026-08-12 源码中的具体行号会随版本变化，阅读时应以函数和类型名为主要定位依据。 一、整体架构 FoundationDB 的事务涉及以下核心角色： 角色 主要职责 Client 保存事务 mutations、读冲突范围和写冲突范围 GRV Proxy 分配 Read Version Commit Proxy 批量接收事务、分配 Commit Version、组织提交流水线 Resolver 检测乐观事务冲突 TLog 复制并持久化已提交 mutations Storage Server 提供版本化读取，异步应用 TLog mutations Sequencer 为事务系统提供版本推进基础 完整流程可以简化为： Client │ ├── 获取 Read Version │ ├── 从 Storage Server 读取该版本 │ ├── 在客户端积累 mutations 和 conflict ranges │ └── 提交 │ ▼ Commit Proxy │ ├── 组成 Commit Batch ├── 分配 Commit Version └── 按 key range 发给 Resolver │ ▼ Resolver │ ├── 检查 read conflict ranges ├── 登记 write conflict ranges └── 返回 committed / conflict / too old │ ▼ Commit Proxy │ ├── 丢弃冲突事务 ├── 为 mutation 添加 Storage Server tag └── 将成功事务写入 TLog │ ▼ TLog │ ├── 按冗余策略复制和持久化 └── 返回 durable │ ▼ Commit Proxy │ └── 向 Client 返回 Commit Version │ ▼ Storage Server ├── 异步读取自己的 tagged mutations ├── 应用到内存中的版本化数据 └── 后台持久化到 Storage Engine 最关键的解耦是： ...

传统数据库通过 Undo Log 和 Redo Log 保证事务的原子性与持久性：Undo 撤销未提交的修改，Redo 恢复已经提交但尚未写入数据文件的修改。那么，在采用分布式事务架构的 FoundationDB 中，是否也存在这两类日志？ 简短回答是： FoundationDB 有承担类似 Redo 职责的 TLog，但通常没有传统意义上的 Undo Log。 这并不意味着 FoundationDB 不支持事务回滚或 MVCC，而是因为它对未提交数据、提交日志和历史版本的组织方式与传统数据库不同。 一、先回顾传统数据库为什么需要 Undo 和 Redo 传统数据库通常允许事务直接修改缓冲池中的共享数据页。数据页何时写入磁盘，与事务何时提交并不完全同步。 因此会出现两种状态。 1. 事务未提交，数据页却已经落盘 例如事务把账户余额从 100 改成 80，但随后事务失败： BEGIN; UPDATE account SET balance = 80 WHERE id = 'A'; ROLLBACK; 如果包含 80 的脏页已经写入磁盘，数据库就必须知道原值是 100，才能撤销这次修改。这是 Undo Log 的主要职责。 2. 事务已经提交，数据页却尚未落盘 另一个事务已经执行 COMMIT，但修改可能仍然只存在于内存中的脏页里。如果服务器此时断电，已提交的数据就会丢失。 因此数据库先持久化 Redo Log，再返回提交成功。重启后，即使数据页没有及时落盘，也可以通过 Redo 重新应用修改。 可以把二者概括为： Undo：事务不应该生效，但修改可能已经进入数据文件。 Redo：事务应该生效，但修改可能还没有进入数据文件。 二、FoundationDB 的事务提交流程 FoundationDB 并不是把客户端事务中的每次 set 或 clear 立即写入 Storage Server。事务提交前，这些操作首先保存在客户端的事务对象中。 ...

选哈希算法时常有两个问题绑在一起：碰撞概率有多小、算得有多快。这篇把碰撞概率背后的数学（生日界）讲清楚，再用它算一算 256-bit 的 SHA-256/BLAKE3 与 128-bit 的 XXH128 各自的碰撞概率，最后附上一组本机实测速度数据。 本文所有实测数据均来自随机生成的字节串，不含任何业务或私有数据。 一、背景：碰撞概率的两种含义 对固定长度输出的哈希，“碰撞概率"必须分两种场景谈，否则会得出互相矛盾的结论： 随机碰撞：没有攻击者，数据是正常/随机的。这时只要输出在取值空间里均匀分布，碰撞概率就纯粹由输出位数决定，与具体算法无关。 抗恶意碰撞：有攻击者知道算法、故意构造两个哈希相同的输入。这里才真正区分加密哈希（SHA-256、BLAKE3、BLAKE2）和非加密哈希（xxHash、CityHash、Murmur）。 第一种是数学问题，用生日界就能算。第二种是密码学性质，非加密哈希直接不提供保证。 二、生日问题：直觉的陷阱 一个房间里要多少人，才有超过 50% 的概率存在两人同一天生日？答案是 23 人——远比直觉小。原因在于碰撞看的不是"某人和我同天”，而是"任意两人之间"的配对数：n 个人有 n(n-1)/2 ≈ n²/2 对，概率随 n² 增长。 哈希碰撞是同一个问题：把"人"换成"哈希输入"，把"365 天"换成"哈希空间大小 N"。对 128-bit 哈希，N = 2^128。 三、生日界公式的推导 设哈希空间大小为 N，独立均匀地放入 n 个值。直接算"至少一次碰撞"要用容斥，很麻烦，所以反过来算"全部不同"的概率： 第 1 个：随便放 → N/N 第 2 个：不能撞前 1 个 → (N-1)/N ... 第 n 个：不能撞前 n-1 个 → (N-n+1)/N 全部不同的概率是连乘： P(无碰撞) = ∏_{k=0}^{n-1} (1 - k/N) 于是至少一次碰撞： P(碰撞) = 1 - ∏_{k=0}^{n-1} (1 - k/N) 这是精确解，但连乘不好用。用近似 1 - x ≈ e^(-x)（x 很小时成立）把每一项换掉： ...