Check 只问一个问题:在这个快照上,该用户是否属于该用户集。回答它可能需要几十次读取,分布在多台服务器上。本页从内部跟随一次 Check:它变成的布尔表达式、各部分执行的顺序、何时可以提前停止、在缓存中留下了什么,以及它在哪里放弃。
另外两个页面涵盖相邻的内容。关系元组与用户集把同一个问题作为图搜索一次走一个分支。架构跟随请求跨越服务器:一致性哈希、缓存树、锁表、读取池化和对冲。本页只关注评估过程本身。
Check 是一个布尔表达式
论文从没有重写规则的情形讲起:“Zanzibar evaluates ACL checks by converting check requests to boolean expressions”(Zanzibar 通过把检查请求转换为布尔表达式来评估 ACL 检查)(§3.2.3)。对于用户 U 和用户集 ⟨object#relation⟩,论文的公式为:
CHECK(U, ⟨object#relation⟩) = ∃ tuple ⟨object#relation@U⟩
∨ ∃ tuple ⟨object#relation@U′⟩, where
U′ = ⟨object′#relation′⟩ s.t. CHECK(U, U′)
第一行是直接命中:某个已存储的元组指名了该用户。第二行是递归:某个已存储的元组指向另一个用户集,而该用户属于那个用户集。论文把沿着这些引用前进称为“指针追逐”,并指出它 “works well for most types of ACLs and groups, but can be expensive when indirect ACLs or groups are deep or wide”(对大多数类型的 ACL 和组都很有效,但当间接 ACL 或组很深或很宽时代价可能很高)(§3.2.3)。重写规则也并入同一个表达式:“Userset rewrite rules are also translated to boolean expressions as part of check evaluation.”(在检查评估过程中,用户集重写规则也会被转换为布尔表达式。)
以论文图 1 中 doc 的配置为例(§2.3.1)。viewer 是其自身元组、editor 和父文件夹查看者的并集;editor 是其自身元组和 owner 的并集。针对 Chen 和 readme 展开写出,并像其他页面一样假定 folder#viewer 没有重写规则:
viewer(readme, chen) = this(readme#viewer, chen)
∨ editor(readme, chen)
∨ ∃ parent tuple readme#parent@folder:X : viewer(folder:X, chen)
editor(readme, chen) = this(readme#editor, chen)
∨ this(readme#owner, chen)
每个 this(…) 是一次元组查找,每个 ∨ 是树中的一个节点。“Chen 能否查看 doc:readme?”会拆分成哪些子问题?
注意,编号标识的是子问题,而不是顺序。叶节点 ②、④a、④b 和 ⑥ 只需要 readme 自身的元组,这正是论文以对象作为转发键的原因(§3.2.5):它们都可以由负责 doc:readme 的服务器回答。第 ⑦ 步是针对另一个对象的新 Check,因此被转发到负责 folder:A 的服务器,而它本身也是一棵树,在这里只是一次 _this 查找。
所有叶节点同时执行,以及取消
叶节点按什么顺序执行?论文并不逐个遍历这棵树:“To minimize check latency, we evaluate all leaf nodes of the boolean expression tree concurrently. When the outcome of one node determines the result of a subtree, evaluation of other nodes in the subtree is cancelled.”(为尽量降低检查延迟,我们并发地评估布尔表达式树的所有叶节点。当某个节点的结果决定了子树的结果时,子树中其他节点的评估会被取消。)(§3.2.3)
对于 Chen 的检查,这在时间上是什么样子?
注意,延迟由通往决定性答案的最快路径决定,而不是由最慢的叶节点决定。如果父文件夹分支很慢,而 Chen 又不是查看者,根节点就必须等待每个子节点都回答“假”。
取消节省了工作,但也留下了空缺。被取消的子检查永远不会把结果写入缓存,而其他请求可能正在锁表中等待这个结果。论文恰好遇到了这个问题:“indirect ACL checks are frequently cancelled when the result of the parent ACL check is already determined. This leaves the cache key unpopulated.”(当父 ACL 检查的结果已经确定时,间接 ACL 检查经常被取消。这会使缓存键未被填充。)其解决办法是:“we delay eager cancellation when there are waiters on the corresponding lock table entry”(在相应锁表条目上有等待者时,我们推迟及早取消)(§3.2.5)。
各运算符何时可以提前停止
论文列出了组合子表达式的三种方式,“union, intersection, and exclusion”(并集、交集和排除)(§2.3.1),并为它们规定了同一条取消规则。子树何时“确定”取决于运算符。对每种运算符而言,哪一个答案就足够了?
注意其中的不对称。每种运算符都有一个可以提前得到的答案,和一个需要所有子节点的答案。对并集而言,提前得到的答案是是;对交集和排除而言则是否。因此,写成并集的权限回答“允许”的速度取决于其最快的路径,而带有交集或排除的权限回答“允许”的速度只能取决于其最慢的必需部分。下表把它列了出来:
| 运算符 | 可提前确定的条件 | 需要所有子节点回答 |
|---|---|---|
并集 A ∪ B |
任一子节点为真 → 真 | 假,才能回答假 |
交集 A ∩ B |
任一子节点为假 → 假 | 真,才能回答真 |
排除 A − B |
基础为假,或被排除侧为真 → 假 | 基础为真且被排除侧为假,才能回答真 |
各产品遵循同样的逻辑。在 OpenFGA 的 check.go(v1.22.1)中,并集归约器在第一个“允许”结果处返回(“Short-circuit success”),交集归约器在第一个“不允许”结果处返回(“Short-circuit failure”),排除归约器则并发运行基础侧和被减侧,并在 “base is false”(基础为假)或 “subtract is true”(被减侧为真)时返回“不允许”。AuthZed 关于交集和排除的文章(2022-03-03)说,对于这些运算符,“SpiceDB can only partially short-circuit the subproblems”(SpiceDB 只能对子问题进行部分短路),而在其示例中,一旦交集的某个分支回答“否”,“SpiceDB was able to cancel the other check immediately”(SpiceDB 就能立即取消另一个 check)。对于并集,其更早的文章(2021-03-17)说得很简单:“any path found suffices to grant permission!”(找到任意一条路径就足以授予权限!)
在快照上缓存子结果
树中的每个节点都是一个有答案的问题,而论文把它们全部缓存起来:服务器 “form a distributed cache for both reads and check evaluations, including intermediate check results evaluated during pointer chasing”(为读取和检查评估构成一个分布式缓存,包括指针追逐过程中评估的中间检查结果)(§3.2.5)。上面的第 ⑦ 步“Chen 是否属于 folder:A#viewer”就是这样一个中间结果。之后任何到达同一问题的检查都可以复用它。
是什么让复用变得安全?一个结果只在某个快照上成立。论文把快照放进了键里:“We avoid reusing results evaluated from a different snapshot by encoding snapshot timestamps in cache keys.”(我们通过在缓存键中编码快照时间戳,避免复用在不同快照上评估得到的结果。)然后它把评估时间戳向上取整,“to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies”(到较粗的粒度,例如 1 秒或 10 秒,同时遵循请求 zookie 中的陈旧度约束),从而使大多数检查落在同样的少数几个时间戳上(§3.2.5;取整过程画在一致性页面上)。
缓存的子结果何时有用,何时会未命中?
注意,这里没有失效这一步。以快照为键的条目永远不会变错,因为 13 s 时的数据永远不会改变;只是当评估转移到更晚的时间戳之后,就不再有人查询它了。AuthZed 关于 SpiceDB 版本的文章(2023-05-10)表达了同样的想法:“For any given problem or sub-problem, at a specified time, the result to the check is immutable”(对于任何给定的问题或子问题,在指定的时间点,检查的结果是不可变的),以及 “if we were to change the evaluation timestamp, the cache keys would change as well”(如果我们改变评估时间戳,缓存键也会随之改变)。
§3.2.5 中还有两种机制围绕着这个缓存,两者都画在架构页面上:通过 “at both the caller and the callee of internal RPCs”(在内部 RPC 的调用方和被调用方)缓存而形成的缓存树,以及锁表,在锁表中 “Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.”(在共享同一缓存键的请求中,只有一个请求会开始处理;其余请求阻塞,直到缓存被填充。)
在产品中:
- SpiceDB 把修订版本取整到由
--datastore-revision-quantization-interval设定的窗口中,默认为5s(dsconfig/config.go,v1.57.1),并在其分派器外包了一层singleflight,用于统计 “dispatch requests that were single flighted”(被 single flight 合并的分派请求),起到锁表的作用。 - OpenFGA 的检查缓存默认关闭(
checkQueryCache.enabled为false,开启时 TTL 为10s)(配置)。其条目在 TTL 之后过期,而不属于某个快照,这就是 OpenFGA 需要HIGHER_CONSISTENCY模式来绕过它的原因(一致性;参见没有 TrueTime 时的顺序保证)。
每次检查的读取会被池化
叶节点 ②、④a、④b 和 ⑥ 都读取 doc:readme 的行。与其单独发送每次读取,“We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner”(我们采用一种池化机制,把同一 ACL 检查的读取归并在一起,以尽量减少发往 Spanner 的读取 RPC 数量)(§3.2.3)。除了这句话,论文没有描述该机制。架构页面画出了这四次读取汇聚到一台服务器上的情形;按对象和关系排序的存储布局(§3.1.1)使它们能够变成对相邻行的范围读取。
能递归多深
CHECK(U, U′) 中的递归没有内置的上界:一个组可以包含一个组,后者又包含一个组,数据模型中也没有任何东西禁止环。检查遇到环时会怎样?
论文没有给出具体数字。它对 “selected namespaces that exhibit such structure”(呈现此类结构的选定命名空间)用 Leopard 来处理深而宽的嵌套(§3.2.4;参见 Leopard 页面),§5 则声称 “safe pointer chasing despite potentially deep recursion (e.g. membership checks on hierarchical groups)”(尽管可能存在深度递归,例如对层级组的成员关系检查,仍能安全地进行指针追逐),但除此之外没有说明是什么使其安全。§3.2.6 中按客户端的限制约束的是 CPU 和未完成的 RPC,而不是深度。各产品选择了明确的上限:
| 系统 | 限制 | 默认值 | 达到时 | 来源 |
|---|---|---|---|---|
| 论文 | 未说明 | 无 | 未描述 | §3.2.4、§5 |
| SpiceDB | --dispatch-max-depth |
50 | 报错:“the check request has exceeded the allowable maximum depth of 50” | Cyclical relationships and traversal limits,serve.go |
| OpenFGA | resolveNodeLimit |
25 | 报错;环会先被检测出来并回答“不允许” | 配置,check.go |
| OpenFGA | resolveNodeBreadthLimit |
10 | 限制 “how many nodes on a given level can be evaluated concurrently”(同一层上可以并发评估的节点数) | 配置 |
| Ory Keto | limit.max_read_depth |
5 | 全局最大值;请求只能把它调低 | config.schema.json |
SpiceDB 的文档说它没有单独的环检测器:环会一直运行到深度上限,并返回与极深层级相同的错误;文档解释说,出于语义和性能方面的原因,没有采用跟踪已访问对象的做法(recursion and max depth)。OpenFGA 的 LocalChecker 为每个请求维护一个已访问元组键的集合,一旦某个键重复,就返回“不允许”并带上 CycleDetected(check.go,hasCycle)。这两个上限都计算沿一条路径的跳数,也就是第一张图中树的深度;resolveNodeBreadthLimit 是其中唯一一个约束论文中 “evaluate all leaf nodes … concurrently”(并发地评估所有叶节点)的限制。
来源
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §2.3.1, §3.1.1, §3.2.3, §3.2.4, §3.2.5, §3.2.6, §5.
- AuthZed, Check it out: How permissions are answered in SpiceDB and Authzed, 2021-03-17(厂商博客)。
- AuthZed, Check it out #2: How intersections and exclusions are computed in SpiceDB and Authzed, 2022-03-03(厂商博客)。
- AuthZed, Hotspot Caching in Google Zanzibar and SpiceDB, 2023-05-10(厂商博客)。
- AuthZed, Cyclical Relationships and Traversal Limits, SpiceDB 文档。
- SpiceDB v1.57.1 源码:
pkg/cmd/serve.go、pkg/cmd/datastore/dsconfig/config.go、internal/dispatch/singleflight/singleflight.go。 - OpenFGA, Configuring OpenFGA 和 Query Consistency Modes。
- OpenFGA v1.22.1 源码:
internal/graph/check.go。 - Ory Keto,
.schema/config.schema.json(limit.max_read_depth)。