OpenFGA ListObjects 实现解析:从授权模型图到 ReverseExpand 反向展开算法

原创2026-10-09 21:39:581,826 阅读
文章标签:认证鉴权身份认证后端云原生

OpenFGA ListObjects 实现解析:从授权模型图到 ReverseExpand 反向展开算法

本文以 docs/list_objects/example/example.md 为主线,结合 OpenFGA 源码,系统讲解 ListObjects API 的内部实现:如何把授权模型建模为一张有向图,如何通过 ReverseExpand 反向展开 + BFS 式的迭代遍历找出用户"可能拥有"某关系的全部对象,以及何时需要进入第二阶段用 Check 做最终判定。读完本文,你将掌握 ListObjects 的两阶段执行模型、direct / computed userset / tuple-to-userset 三类边的处理方式,以及与之对应的源码位置与工程参数。

一、核心思想:把授权模型当作一张有向图

OpenFGA 的授权模型(authorization model)可以表示成一张有向、且可能带环的图。图中的节点是"类型"(type,例如 user)和"用户集"(userset,例如 user:*、group#member),边则刻画了类型/用户集之间可能存在的关系。

例如,考虑如下的授权模型:

type user

type group
  relations
    define member: [user, group#member]

type folder
  relations
    define viewer: [user]

type document
  relations
    define parent: [folder]
    define editor: [user]
    define viewer: [user, user:*, group#member] or editor or viewer from parent

这个模型可以被画成一张图(图中节点如 user、group#member、folder#viewer、document#editor、document#viewer,边代表模型中的 rewrite 关系):

ListObjects 示例授权模型对应的有向关系图

回答一个 ListObjects 查询,在高层面上分为两个阶段:

  • Phase 1(反向展开,reverse expand):以"画模型 + 类似广度优先搜索(BFS)"的方式,从给定的源节点出发,尝试到达目标节点。具体来说,从用户所在节点开始,反向展开所有可能通向"目标对象类型 + 目标关系"的路径。在展开过程中不断读取 tuple,把沿途找到的、属于目标类型的对象加入响应;其中一部分对象可能还需要进一步求值,于是被标记为 candidate(候选)。
  • Phase 2(Check 二次校验):对所有需要进一步求值的 candidate 对象调用 Check。若 Check 返回 allowed=true,则把该对象加入最终响应。

注:在本文的示例模型中,所有路径都是"或(or)"关系,Phase 2 并不必要,因此下文会略去 Phase 2。想看 intersection / exclusion 场景下 Phase 2 如何工作的读者,请直接阅读 docs/list_objects/example_with_intersection_or_exclusion/example.md。

二、示例数据:8 条 tuple 与一个查询

沿用上面的模型,假设 store 中写入如下 8 条 tuple:

document:1#viewer@user:andres
document:2#viewer@group:eng#member
document:3#editor@user:andres
document:4#parent@folder:1
document:5#viewer@user:*
folder:1#viewer@user:andres
group:eng#member@group:fga#member
group:fga#member@user:andres

现在考虑这样的查询:

ListObjects(type= document, relation= viewer, user= user:andres)

即:找出所有 user:andres 对其拥有 viewer 关系的 document 对象。直觉上,命中应该是 document:1、document:2、document:3、document:4、document:5——下文逐步验证这一结果。

在 Phase 1 中,需要做两件事:

  1. 借助上面的有向图,确定源节点(user)与目标节点(document#viewer)之间的边;
  2. 利用 store 中的 tuple 沿这些边做一次 BFS:沿途把找到的、属于目标类型的对象直接加入响应,或者对找到的 userset 递归地继续考察。

这里的关键内部 API 是 ReverseExpand,其函数签名可以概括为:

ReverseExpand(source Object or Userset, neighbor Userset) -> Object or [Usersets]

即给定一个源对象/用户集和一个邻居用户集,返回从源出发能直接连到的对象或需要继续递归的用户集。OpenFGA 中对应的真实实现位于 pkg/server/commands/reverseexpand/reverse_expand.go,其 Execute 方法会把"用户可能对某对象类型拥有某关系"的全部对象产出一个 channel 上,并保证不重复、尊重 context 超时与取消:

Execute yields all the objects of the provided objectType that the given user possibly has, a specific relation with and sends those objects to resultChan. It MUST guarantee no duplicate objects sent.(见 reverse_expand.go)

三、Phase 1 逐步演示:四轮迭代

Iteration 1:从 user:andres 出发找距离 0~1 的边

首先确定 user:andres(图中浅蓝色)到目标用户集 document#viewer(图中洋红色)之间的所有可能路径,然后取出这些路径中距离为 0 或 1 的边(从左到右即边 11、4、1、14、5),并考察它们的尾节点:

Iteration 1:计算 user 到 document#viewer 的边并取出距离 0~1 的边

// compute all paths, grab edges at distance 0 or 1, and grab their tails
Edges(user, document#viewer) → [group#member, document#viewer, document#editor, folder#viewer, document#viewer]

对每个邻居节点需要分别展开。展开方式是遍历 tuple,找出从源对象 user:andres 连到每个节点的所有对象,即调用 ReverseExpand:

// find all tuples of form `group:...#member@user:andres`
a. ReverseExpand(user:andres, group#member) → [group:fga#member]

// find all tuples of form `document:...#viewer@user:andres`
b. ReverseExpand(user:andres, document#viewer) → [document:1#viewer]

// find all tuples of form `document:...#editor@user:andres`
c. ReverseExpand(user:andres, document#editor) → [document:3#editor]

// find all tuples of form `folder:...#viewer@user:andres`
d. ReverseExpand(user:andres, folder#viewer) → [folder:1#viewer]

// find all tuples of form `document:...#viewer@user:*`
e. ReverseExpand(user:*, document#viewer) → [document:5#viewer]

注意第 e 条:user:* 是类型化通配符(typed wildcard),它命中了 document:5#viewer@user:* 这条 tuple。源码中,ReverseExpand 会把请求中的 user:* 解析为 UserRefTypedWildcard,并在读取 tuple 时追加 user:* 过滤条件(见 reverse_expand.go 与 reverse_expand.go)。

以上 5 条结果中,document:1#viewer 与 document:5#viewer 本身就是目标类型 document 的 viewer 用户集,可以直接作为候选对象;其余 group:fga#member、document:3#editor、folder:1#viewer 是需要继续递归的用户集。于是进入 Iteration 2。

Iteration 2:对上一轮得到的用户集分别递归

2a. ReverseExpand(group:fga#member, document#viewer)

Iteration 2a:从 group:fga#member 展开

// compute all paths, grab edges at distance 0 or 1, and grab their tails
Edges(group#member, document#viewer) → [group#member, document#viewer]

分别考察每个邻居节点:

// find all tuples of form `document:...#viewer@group:fga#member`
ReverseExpand(group:fga#member, document#viewer) → []

// find all tuples of form `group:X#member@group:fga#member`
ReverseExpand(group:fga#member, group#member) → [group:eng#member]

也就是说,group:fga#member 本身没有直接查看任何 document,但 group:eng#member 是 group:fga#member 的成员(来自 tuple group:eng#member@group:fga#member)。因此下一轮(3a)需要继续递归 group:eng#member。

2b. ReverseExpand(document:1#viewer, document#viewer)

这里 source 与 target 都是同一类型、同一关系的用户集,恰好就是原始请求所查询的"对象类型 + 关系"。因此可以直接断定找到了对象 document:1,把它加入结果列表并终止该分支的递归。

这正是源码中 trySendCandidate 触发的场景:当 req.User 是 UserRefObjectRelation 且其类型与关系匹配原始请求时(tuple.UsersetMatchTypeAndRelation(...)),直接产出候选对象(见 reverse_expand.go)。

2c. ReverseExpand(document:3#editor, document#viewer)

Iteration 2c:computed userset 边 8

// compute all paths, grab edges at distance 0 or 1, and grab their tails
Edges(document:#editor, document#viewer) → [document#viewer]

从 document#editor 到 document#viewer 的边 8 是一条 computed userset 关系(模型中的 or editor)。这条边很特殊:它意味着"所有 editor 同时也是 viewer"。因此不需要再查任何 tuple,直接把源换成 document:3#viewer 继续即可:

ReverseExpand(document:3#viewer, document#viewer)

下一轮(3b)处理。源码中的对应实现是:当边的类型是 ComputedUsersetEdge 时,不需要额外读取数据,直接把 req.User 改写为 sourceUserObj#目标关系 后再次 dispatch(见 reverse_expand.go)。

2d. ReverseExpand(folder:1#viewer, document#viewer)

Iteration 2d:tuple-to-userset 边 9

// compute all paths, grab edges at distance 0 or 1, and grab their tails
Edges(folder:1#viewer, document#viewer) → [document#viewer]

从源 folder#viewer(浅蓝)到目标 document#viewer(洋红)的边 9 是一条 tuple-to-userset(TTU) 重写,它基于 document#parent 这个 tupleset 触发。含义是:如果某用户能查看某个 folder,而某 document 的 parent 是那个 folder,那么该用户也能查看这个 document。

换句话说:我们已经知道 user:andres 属于 folder:1#viewer,现在需要找到所有以 folder:1 为 parent 的 document:

// we know `folder:1#viewer@user:andres`
// find all tuples of form `document:...#parent@folder:1` and then return `document:...#viewer`
ReverseExpand(folder:1#viewer, document#viewer) → [document:4#viewer]

下一轮(3c)需要继续递归 document:4#viewer。源码层面,TTU 边的展开会走 reverseExpandTupleToUserset → readTuplesAndExecute,其中 relationFilter 被设置为 edge.TuplesetRelation(即 parent),读取形式为 document:...#parent@folder:1 的 tuple(见 reverse_expand.go);读到的对象再以 foundObject#目标关系(即 document:4#viewer)的形式继续递归(见 reverse_expand.go)。

2e. ReverseExpand(document:5#viewer, document#viewer)

与 2b 同理:source 与 target 是同一类型、同一关系的用户集,匹配原始请求。因此直接找到对象 document:5,加入结果并终止该分支的递归。

Iteration 3:继续考察上一轮遗留的用户集

3a. ReverseExpand(group:eng#member, document#viewer)

Iteration 3a:从 group:eng#member 展开

// compute all paths, grab edges at distance 0 or 1, and grab their tails
Edges(group#member, document#viewer) → [group#member, document#viewer]

分别考察每个邻居节点:

// find all tuples of form `document:...#viewer@group:eng#member`
ReverseExpand(group:eng#member, document#viewer) → [document:2#viewer]

// find all tuples of form `group:X#member@group:eng#member`
ReverseExpand(group:eng#member, group#member) → []

命中了 tuple document:2#viewer@group:eng#member,因此下一轮(4a)继续递归 document:2#viewer;而 group:eng#member 不再有下层成员(group:X#member@group:eng#member 为空),这条链到此为止。

3b. ReverseExpand(document:3#viewer, document#viewer)

source 与 target 同为 document#viewer 且匹配原始请求:找到对象 document:3,加入结果,终止递归。(文档中此处小节标题有笔误为 3b,实际应为 3b/3c 两个分支,语义不变。)

3c. ReverseExpand(document:4#viewer, document#viewer)

同理:找到对象 document:4,加入结果,终止递归。

Iteration 4:收尾

4a. ReverseExpand(document:2#viewer, document#viewer)

source 与 target 同为 document#viewer 且匹配原始请求:找到对象 document:2,加入结果,终止递归。

最终结果

此时已没有遗留的、等待继续递归的用户集,可以直接返回:

ListObjects(type= document, relation= viewer, user= user:andres) → [document:1, document:2, document:3, document:4, document:5]

与直觉预期完全一致:document:1(直接 viewer)、document:2(经 group:eng → group:fga 两级成员关系)、document:3(editor 即 viewer 的 computed userset)、document:4(经 folder:1#viewer 的 TTU parent 关系)、document:5(user:* 通配符)。

四、源码纵深:三类边、去重、候选与 Check 回调

4.1 三类关系边

从源码 reverse_expand.go 可以看到,ReverseExpand 实际处理的边类型与文档中的语义一一对应:

边类型 文档中的例子 处理方式
DirectEdge(直接关系) document:1#viewer@user:andres 以 ReadStartingWithUser 直接读取 目标类型#关系@用户 形式的 tuple
ComputedUsersetEdge(计算用户集) viewer: ... or editor 不读 tuple,直接把源改写为 源对象#目标关系 后继续 dispatch
TupleToUsersetEdge(元组到用户集) viewer from parent 以 TuplesetRelation(如 parent)为过滤关系读取 tuple,再以 对象#目标关系 继续递归

所有 tuple 读取都走 c.datastore.ReadStartingWithUser,即按"对象类型 + 关系 + 用户过滤器"一次性反向读取满足条件的 tuple(见 reverse_expand.go)。值得注意的工程细节:

  • 读取结果还会经过 storage.NewFilteredTupleKeyIterator + validation.FilterInvalidTuples 过滤,剔除数据库迭代器中不符合模型的非法 tuple(见 reverse_expand.go);
  • 如果 tuple 带条件(condition),展开时会对每条 tuple 求值条件表达式,条件不满足的直接跳过(见 reverse_expand.go);
  • 对 group:eng#member@group:fga#member 这类"用户集套用户集"的递归,源码用 visitedUsersetsMap 记录"已经通过某条边访问过的用户集",避免模型带环时陷入无限循环(见 reverse_expand.go)。

4.2 候选对象与 NoFurtherEval / RequiresFurtherEval 状态

文档中"直接加入结果"与"标记为 candidate"的区分,在源码里体现为 trySendCandidate 中的两种状态(见 reverse_expand.go):

  • 若到达该对象的路径没有经过 intersection / exclusion 重写,则标记为 NoFurtherEvalStatus,ListObjects 直接将其写入响应;
  • 若路径经过了 intersection / exclusion(例如模型的 and / but not 重写),则标记为 RequiresFurtherEvalStatus,该对象成为 candidate,等待 Phase 2 的 Check 判定。

同时,trySendCandidate 通过 candidateObjectsMap 的 LoadOrStore 保证同一个对象只被发送一次,这正好兑现了 Execute 的"no duplicate objects"承诺。

4.3 ListObjects 如何编排 ReverseExpand 与 Check

在 pkg/server/commands/list_objects.go 的 evaluate 中,整体编排如下:

  1. 根据请求的 type / relation / user 构造 sourceUserRef(普通对象 / 类型化通配符 / 用户集三种形态,见 list_objects.go);
  2. 构建 ReverseExpandQuery(注入 resolveNodeLimit、resolveNodeBreadthLimit、dispatch throttler 等配置),并发池大小为 1 + resolveNodeBreadthLimit;
  3. 启动一个协程执行反向展开,把结果推入 reverseExpandResultsChan;主协程消费该 channel(见 list_objects.go):
    • 结果状态为 NoFurtherEvalStatus:计数 list_objects_no_further_eval_required_count,直接发送对象;
    • 结果状态为 RequiresFurtherEvalStatus:计数 list_objects_further_eval_required_count,启动子协程调用 NewCheckCommand(...).Execute(...) 对 (对象, relation, user) 做 Check;Allowed == true 才发送(见 list_objects.go)。
  4. 响应受两个硬约束约束:listObjectsDeadline(超时截断)与 listObjectsMaxResults(结果数上限,且单个请求的结果数被硬性 cap 在 1000,见 list_objects.go)。

ListObjectsQuery 的默认配置来自 serverconfig(如 DefaultListObjectsDeadline、DefaultListObjectsMaxResults、DefaultResolveNodeLimit、DefaultResolveNodeBreadthLimit 等,见 list_objects.go),这些参数可通过服务端配置项调整,是控制 ListObjects 耗时与资源消耗的关键旋钮。

4.4 剪枝:intersection / exclusion 时只展开一个操作数

当目标关系涉及 and / but not 重写时,OpenFGA 并不会展开全部操作数,而是做剪枝:GetPrunedRelationshipEdges 只返回"最先涉及该重写的那条边",并对由此找到的结果标记 RequiresFurtherEvalCondition(见 internal/graph/graph.go)。graph.go 中的注释点明了设计动机:

对于 a but not b,我们剪掉 b,只解析 a,并对每个结果打上 further eval 标记(见 graph.go)。

之后由 Phase 2 的 Check 去完整求值整条 and / but not 规则,从而在"减少 Phase 1 的存储读取"与"保证语义正确"之间取得平衡。这正是 docs/list_objects/example_with_intersection_or_exclusion/example.md 所演示的场景:Phase 1 剪枝后得到候选 document:1,Phase 2 调用 Check(user:andres, c, document:1) 返回 allowed: true,最终才把 document:1 写入结果。

五、测试与工程佐证

仓库中针对反向展开的测试(pkg/server/commands/reverseexpand/reverse_expand_test.go)直接验证了文档所描述的执行契约:

  • TestReverseExpandResultChannelClosed:验证即使没有任何 tuple,Execute 也会正常关闭结果 channel(配合 goleak.VerifyNone 检查协程泄漏);
  • TestReverseExpandRespectsContextCancellation:构造 100 条 tuple 验证 context 取消时 Execute 立即返回、不再产出结果。

这两条测试对应了文档示例中"没有更多可递归的用户集就终止并返回"的收敛语义,也印证了 Execute 注释中"尊重 context 超时与取消"的工程承诺。

六、小结

  • ListObjects 的 Phase 1 本质上是在授权模型图上做一次 ReverseExpand 驱动的 BFS:每轮迭代取出距离 0~1 的边,分别展开 direct、computed userset、tuple-to-userset 三类边,命中目标类型的对象直接产出,命中用户集则继续递归;
  • 所有路径均为 or 关系时(本文示例),一轮轮递归即可收敛出全部结果,无需 Phase 2;
  • 一旦路径经过 intersection / exclusion,结果被标记为 candidate,必须由 Phase 2 的 Check 做最终裁决——完整流程见 docs/list_objects/example_with_intersection_or_exclusion/example.md;
  • 源码层面,reverseExpand.Execute 保证结果无重复、尊重超时取消、对带条件 tuple 逐条求值,并用 visitedUsersetsMap 打破模型中的环;ListObjectsQuery.evaluate 则负责把 ReverseExpand 的输出按 NoFurtherEvalStatus / RequiresFurtherEvalStatus 分流到"直接返回"与"Check 二次校验"两条路径。

掌握这一实现脉络,有助于在真实业务中预判 ListObjects 的存储读取量与耗时:模型中 or 分支越多、递归层级越深,Phase 1 的展开量越大;and / but not 分支则会把成本转移到 Phase 2 的 Check 上。结合 resolveNodeLimit、resolveNodeBreadthLimit、listObjectsMaxResults、listObjectsDeadline 等参数,可以针对具体模型做出合理的资源预算与调优。

登录后查看全文
openfga