Zanzibar 用 zookie 防止“new enemy”问题,而 zookie 之所以有效,是因为 Spanner 为每次写入分配一个遵循因果关系的时间戳。一致性、快照与 zookie 解释了这两点,包括 TrueTime 和提交等待如何产生这些时间戳。Google 之外几乎没有人运行在 TrueTime 之上。本页探讨 zookie 协议实际上需要数据库提供什么,以及构建在其他数据库上的产品如何获得它,或者如何在没有它的情况下运作。
zookie 需要数据存储提供什么
zookie 协议依赖于 §2.2 对存储层提出的两个性质,“external consistency and snapshot reads with bounded staleness”(外部一致性和有界陈旧度的快照读):
- 提交顺序遵循因果关系。 如果写入
x发生在写入y之前(例如,Anne 看到x成功后才进行y),那么T_x < T_y。用论文的话说,两个具有因果关系的更新x ≺ y“will be assigned timestamps that reflect the causal order:T_x < T_y”(将被分配反映其因果顺序的时间戳:T_x < T_y)(§2.2),而 zookie 协议 “ensures that all prior ACL writes have lower timestamps”(确保所有先前的 ACL 写入都具有更低的时间戳)。 - 在给定点或之后进行快照读。 在
T上的读取 “observes all updates with timestamps ≤ T”(会观察到所有时间戳 ≤ T 的更新)(§2.2),并且检查 “is always evaluated at a consistent snapshot no earlier than the given zookie”(总是在一个不早于给定 zookie 的一致快照上评估)(§2.4.4)。
这份清单中没有任何一处说的是挂钟时间意义上的“时间戳”。zookie 中的值可以是历史中的任何位置,只要两个性质对它成立即可。这正是论文把 zookie 设计成不透明的原因:“to discourage our clients from choosing arbitrary timestamps and to allow future extensions”(为了避免客户端选择任意时间戳,并为未来的扩展留有余地)(§2.4)。
这两个性质如何结合起来,阻止 Chen 在被从文件夹 A 中移除之后看到 readme?
注意,性质 ① 针对的是数据库可能永远看不出相关的写入。§2.2 要求对 “updates on different ACLs or objects and those coordinated via channels invisible to Zanzibar”(针对不同 ACL 或对象的更新,以及通过 Zanzibar 不可见的渠道所协调的更新)进行排序。在论文的例 A 中,两次写入之间的联系是 Alice 请 Charlie 帮忙,发生在任何系统之外。数据库仍然必须正确地对这两次提交排序。
获得顺序的三种方式
Spanner 通过具有已知误差界的同步时钟获得性质 ①,代价是每次写入都要等待不确定区间过去(Spanner,OSDI ’12;图示见一致性页面)。其他数据库以不同方式获得它,或获得其中的大部分。在每种数据库中,顺序从何而来?
注意,单主库数据库天然具备性质 ①,因为一台服务器按顺序看到每次提交;它们放弃的是论文中的全球复制。CockroachDB 在全球复制,但只部分提供性质 ①。下一节讨论这一缺口。
CockroachDB:键重叠规则
CockroachDB 没有 TrueTime。其节点保持松散同步的时钟,集群有一个最大时钟偏移 --max-offset,默认为 500ms;“If observed clock offsets exceed this limit, servers will crash to minimize the likelihood of reading inconsistent data”(如果观测到的时钟偏移超过该限制,服务器会崩溃,以尽量降低读到不一致数据的可能性)(cockroach start)。Cockroach Labs 自己与 Spanner 的对比文章说 “CockroachDB only goes as far as to claim serializability”(CockroachDB 只声称做到了可串行化),并把它所允许的异常称为 “causal reverse”(因果倒置):具有因果关系的事务可能以错误的时间戳顺序提交(Living without atomic clocks,2022-01-27)。
AuthZed 于 2021 年用 SpiceDB 在 CockroachDB 上复现了“new enemy”问题(The One Crucial Difference Between Spanner and CockroachDB,2021-10-14)。文章对这一缺口的概括是:“Cockroach does not provide external consistency for transactions involving non-overlapping keys.”(对于涉及不重叠键的事务,Cockroach 不提供外部一致性。)其测试使用两次写入和一次检查,“in sequence (not parallel)”(按顺序(而非并行))运行:写入一个 excluded 元组,写入一个 direct 元组,然后在第二次写入的修订版本上检查 allowed = direct - excluded;“the check in 3 will succeed”(第 3 步中的检查会成功)。
如果某个节点的时钟走快了,用贯穿示例来看会是什么样子?
注意右边一帧中标有“同一个键 K”的箭头。两个时钟都没有变好;改变的是两个事务现在发生冲突,而 CockroachDB 会正确地对冲突的事务排序。两帧中的时间戳都只是示意;偏差远在 500ms 默认值之内,因此没有服务器会崩溃。
AuthZed 发现共享读取还不够:“we needed both transactions to write to the same key”(我们需要两个事务都写入同一个键)。因此 SpiceDB 的 CockroachDB 驱动会给写入加上一个重叠键,具体策略由 --datastore-tx-overlap-strategy 选择(datastores):
| 策略 | SpiceDB 文档 |
|---|---|
static(默认) |
“All writes overlap to guarantee safety at the cost of write throughput”(所有写入都重叠,以写吞吐量为代价保证安全) |
prefix |
“Only writes that contain objects with same prefix overlap”(只有包含相同前缀对象的写入才重叠) |
request |
“Only writes with the same io.spicedb.requestoverlapkey header overlap”(只有带相同 io.spicedb.requestoverlapkey 请求头的写入才重叠) |
insecure |
“No writes overlap, providing the best write throughput, but possibly leaving you vulnerable to the New Enemy Problem”(写入都不重叠,提供最好的写吞吐量,但可能使你容易受到“new enemy”问题的影响) |
用 AuthZed 的话说,代价是:“This does add a small amount of latency to the write path, but it leaves the read paths performant.”(这确实会给写路径增加少量延迟,但读路径的性能不受影响。)每次 static 写入都在同一行上争用,这正是论文改用提交等待来支付的代价。
数据存储文档还补充了一个读取侧的 CockroachDB 注意事项:SpiceDB 用 cluster_logical_timestamp() 选择修订版本,“which can differ across nodes by up to the cluster’s”(各节点之间可能相差最多达集群的)最大偏移,并且 “A read may not see a recently committed write if the reading node’s timestamp is behind the writing node’s.”(如果读取节点的时间戳落后于写入节点,读取可能看不到最近提交的写入。)因此,“fully_consistent does not guarantee read-after-write consistency on CockroachDB.”(在 CockroachDB 上,fully_consistent 不保证写后读一致性。)来自写入的 ZedToken 可以避免这一问题,因为它指明的是该写入自身的修订版本(datastores)。
PostgreSQL 与 MySQL:由一个主库决定
单主库数据库本来就按顺序看到每次提交,因此性质 ① 不需要时钟。悬而未决的是性质 ②:读取可能发往一个落后的副本。
SpiceDB 的 PostgreSQL 驱动在排序时完全不使用时间。修订版本是来自 pg_current_xact_id() 和 pg_current_snapshot() 的事务 ID 和快照;驱动中的一条注释说 “timestamps cannot be used for ordering transactions in PG”(在 PG 中不能用时间戳对事务排序),并且两个快照可能 “mutually uncomparable”(互相不可比较)(postgres/revisions.go,v1.57.1)。在 x 提交之后获取的快照会把 x 列为已提交,这就是用 PostgreSQL 自己的术语表述的性质 ①。MySQL 驱动向一张事务表写入一行,其 id 为 AUTO_INCREMENT,并把该 id 用作修订版本(migrations,revisions.go)。在另一次写入提交之后才开始的写入会更晚插入其行,因此获得更大的 id;这一推理是本页的,并非 SpiceDB 文档的说法。
只读副本重新引入了延迟。当副本落后时,SpiceDB 如何让检查至少与其令牌一样新?
文档描述的正是这一点:复制延迟 “would be problematic to SpiceDB’s ability to solve the new enemy problem”(会妨碍 SpiceDB 解决“new enemy”问题的能力),因此 SpiceDB 会检查 “if the revision has been replicated into the target replica. If missing, it will fall back to the primary.”(该修订版本是否已复制到目标副本。如果没有,就回退到主库。)对于 MySQL,这 “requires two roundtrips instead of one”(需要两次往返而不是一次),文档还警告不要在 MySQL 副本前面放负载均衡器,“because SpiceDB will not be able to maintain consistency guarantees”(因为 SpiceDB 将无法维持一致性保证)(datastores)。
运行在 PostgreSQL 上的 Permify 以同样的方式构造其 Snap Token:令牌包含一个 PostgreSQL XID8 和一个快照字符串(snapshot/token.go,v1.7.6)。其文档只把该令牌描述为 “a token that consists of an encoded timestamp”(一个由编码后的时间戳构成的令牌)(snap tokens)。
论文之外的 Spanner
SpiceDB 也运行在拥有 TrueTime 的 Cloud Spanner 上。在那里,驱动 “assumes the database is linearizable and skips the transaction overlap strategy”(假定数据库是可线性化的,并跳过事务重叠策略)(datastores),并用 SELECT CURRENT_TIMESTAMP() 读取其修订版本(spanner/revisions.go)。这是最接近论文的配置。
完全没有令牌
OpenFGA 没有 zookie;其文档说论文 “has a feature called Zookies”(有一项名为 Zookies 的功能),而 OpenFGA “is considering a similar feature in future releases”(正在考虑在未来版本中加入类似功能)(一致性)。取而代之的是,查询选择 MINIMIZE_LATENCY(默认)或 HIGHER_CONSISTENCY,后者 “will skip the cache and query the database directly”(会跳过缓存,直接查询数据库)。在配置了二级数据存储的 PostgreSQL 上(datastore.secondaryUri,“for postgres only”,仅限 postgres,配置),HIGHER_CONSISTENCY 还会选择主库:代码注释写道 “If we are using higher consistency, we need to use the write database”(如果使用更高的一致性,就需要使用写数据库)(postgres.go,v1.22.1)。
这提供的是“与主库一样新”,而不是“至少与我的写入一样新”。这一区别关系到成本:zookie 让大多数检查可以使用缓存或副本,只有较新的检查才发往主库,而 HIGHER_CONSISTENCY 会把每个这样的查询都发往主库。OpenFGA 页面画出了缓存的情形;文档建议按请求选择模式,即比较资源的最后修改时间与缓存 TTL,这就让应用自己保存了 zookie 的一部分信息。
其他产品:
- Ory Keto 的 Check API 中有
snaptoken和latest字段,每一个都标注为 “This field is not implemented yet and has no effect”(该字段尚未实现,没有任何效果)(check_service.proto)。 - Warrant 读取
Warrant-Token请求头,只对值latest作出反应,即把读取发往主库;其他任何值都会被忽略,而且开源服务器不返回令牌(wookie.go,Warrant)。 - Topaz 的文档中没有令牌;见对比页面。
Tom MacWright 关于这篇论文的阅读笔记从外部得出了同样的观察:OpenFGA 没有任何类似 zookie 的东西,“neither does Ory Keto”(Ory Keto 也没有)(Reading Zanzibar,2025-05-02)。
没有令牌时,需要论文所述保证的应用有两个选择:从一个始终最新的存储读取(单个主库,没有缓存),或者接受一个时间窗口,在此期间已被移除的用户仍可能被允许。
各产品的机制
| 产品与数据存储 | 顺序从何而来 | 令牌 | 在令牌或之后读取 |
|---|---|---|---|
| 论文(Spanner) | TrueTime + 提交等待 | zookie | 任意副本;必要时等待(§3.2.5) |
| SpiceDB on Spanner | TrueTime;跳过重叠策略 | ZedToken | Spanner 快照读 |
| SpiceDB on CockroachDB | HLC 时间戳;写入时加重叠键(默认 static) |
ZedToken | AS OF SYSTEM TIME;fully_consistent 可能漏掉另一节点上的写入 |
| SpiceDB on PostgreSQL | 主库的事务 ID 和快照 | ZedToken | 副本有该修订版本时用副本,否则用主库 |
| SpiceDB on MySQL | AUTO_INCREMENT 事务 ID |
ZedToken | 副本有该修订版本时用副本,否则用主库(两次往返) |
| Permify on PostgreSQL | 主库的 XID8 和快照 |
Snap Token | 来自令牌的快照 |
| OpenFGA | 未对外暴露 | 无 | HIGHER_CONSISTENCY:跳过缓存,使用主库 |
| Ory Keto | 未对外暴露 | snaptoken 字段,未实现 |
不可用 |
| Warrant | 无(不返回令牌) | Warrant-Token 请求头 |
仅 latest;其他值被忽略 |
每一行的来源见上文各节。Permify 带令牌时的读取路径没有在其源码中追踪;该行只反映令牌的内容。
来源
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.2, §2.4, §2.4.4, §3.2.5, §5.
- James C. Corbett et al., Spanner: Google’s Globally-Distributed Database, OSDI ’12.
- AuthZed,The One Crucial Difference Between Spanner and CockroachDB,2021-10-14(厂商博客)。
- AuthZed,Enforcing Causal Ordering in Distributed Systems: The Importance of Permissions Checking,2021-02-17(厂商博客)。
- AuthZed,Datastores,SpiceDB 文档。
- SpiceDB v1.57.1 源码:
postgres/revisions.go、mysql/revisions.go、mysql初始 schema、spanner/revisions.go。 - Cockroach Labs,
cockroach start(--max-offset)。 - Spencer Kimball and Irfan Sharif,Living without atomic clocks: Where CockroachDB and Spanner diverge,Cockroach Labs,2022-01-27(厂商博客)。
- OpenFGA,Query Consistency Modes 和 Configuring OpenFGA;v1.22.1 源码
pkg/storage/postgres/postgres.go。 - Permify,Snap Tokens;v1.7.6 源码
snapshot/token.go。 - Ory Keto,
check_service.proto。 - Warrant,
pkg/wookie/wookie.go。 - Tom MacWright,Reading Zanzibar,2025-05-02。