传统数据库通过 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 很小时成立）把每一项换掉： ...