Check が答えるのは 1 つの問い、すなわちこのユーザーはこのオブジェクトにこの操作を行ってよいか、である。一覧ページは別の問いを投げる。このユーザーはどのオブジェクトを見てよいか、それを絞り込み、並べ替え、1 ページずつ返す、という問いである。本ページでは、2 つ目の問いがなぜ難しいのか、論文がそれに対して何を提供しているのか、そして Zanzibar 系の製品が文書化している 3 つの手法を説明する。
Check とは別の問い
Check は 1 つのオブジェクトから出発し、ユーザーが見つかるか経路が尽きるまでタプルをたどる (§2.4.4、§3.2.3)。作業量は、そのオブジェクトにぶら下がっているものによって上限が決まる。「Anne が見られるすべてのドキュメント」には出発点となるオブジェクトがない。これを Check で答えるには、システム内のドキュメントごとに 1 回ずつ Check を行うことになり、その答えの大半は「no」になる。
一覧には、認可サービスが保持していないデータも必要である。OpenFGA のガイドはこう述べている。認可サービスは “does not store object metadata (names of files, creation dates, time of last update, etc)” (オブジェクトのメタデータ (ファイル名、作成日、最終更新時刻など) を格納しない) ので、検索は “will require data from your database” (自身のデータベースのデータを必要とする) (OpenFGA, Search With Permissions)。絞り込みと並べ替えは自分のデータベースで行われ、認可は別のサービスで行われ、答えはその 2 つの共通部分である。
論文はこのユースケースをよく知っている。統一されたシステムの利点として挙げたものの中に “a search index that respects access control and works across applications” (アクセス制御を尊重し、アプリケーションをまたいで機能する検索インデックス) があり (§1)、レイテンシの目標では “serving search results, which often require tens to hundreds of checks” (しばしば数十から数百のチェックを必要とする検索結果の提供) を特に取り上げている (§1)。
論文が提供するもの、しないもの
論文の API には Read、Write、Watch、Check、Expand の 5 つの呼び出しがある (§2.4)。そのどれも「ユーザー U が見られるすべてのオブジェクト」を返さない。
- Read は格納されたタプルだけを返す。ユーザーをキーとするタプルセットを使えば、クライアントは “look up all groups with a given user as a direct member” (特定のユーザーを直接のメンバーとするすべてのグループを調べる) ことができる (§2.4.1)。要点は 直接 という点である。Read は書き換えルールを適用しないので、
editorからviewerへ、あるいはフォルダからその中のドキュメントへとたどることはない。 - Expand は書き換えルールをたどるが、方向が逆である。⟨object#relation⟩ ペアを受け取り、その “effective userset” (実効的なユーザーセット) を ユーザーセット木 として返す。その葉は “are user IDs or usersets pointing to other ⟨object#relation⟩ pairs” (ユーザー ID、または他の ⟨object#relation⟩ ペアを指すユーザーセットである) (§2.4.5)。論文はその目的を明記している。Expand によりクライアントは “build efficient search indices for access-controlled content” (アクセス制御されたコンテンツのための効率的な検索インデックスを構築する) ことができる (§2.4.5)。インデックスを構築するのはクライアントの仕事である。
- Watch はタプルの変更をストリームで返し、“clients maintain secondary indices of relation tuples” (クライアントがリレーションタプルの二次インデックスを維持する) ことを可能にする (§2.4.3)。
- Leopard (§3.2.4) は入れ子の グループ を平坦化する。ユーザーがグループに属するかどうかを 1 回の積集合演算で答える。Zanzibar の内部で “selected namespaces” (選ばれた名前空間) の Check を高速化するために使われており、論文はこれを一覧取得の API としては説明していない。Leopard、グループのインデックス を参照。
readme の閲覧者について Expand が返すものは、クライアントが実際に欲しい平坦な一覧と比べてどう違うか。
木が答えているのは「このドキュメントを誰が見られるか」であって、「Anne が何を見られるか」ではないことに注意したい。Expand だけで Anne のドキュメントを一覧するには、クライアントはすべてのドキュメントを展開するか、§2.4.5 が示唆するように、前もって展開して結果を自前のインデックスに保持することになる。SpiceDB のドキュメントも同じ隔たりを説明している。Expand は “responds with a tree structure that can be awkward for applications to consume” (アプリケーションが扱いにくい木構造で応答する) ので、SpiceDB は LookupResources と LookupSubjects を追加した。これらは “return a flattened list of results” (平坦化された結果の一覧を返す) (SpiceDB, Google Zanzibar)。
手法 1: ルックアップ API のあとにデータベースで絞り込む
認可サービスが逆向きの問いを直接計算する。SpiceDB の LookupResources と OpenFGA の ListObjects は、ユーザーが権限を持つ、ある型のすべてのオブジェクトの ID を返す。アプリケーションはそれらの ID をデータベースのクエリ (WHERE id = ANY(…)) に渡し、データベースは通常どおり絞り込み、並べ替え、ページ分割を行う。SpiceDB はこれを “the simplest approach from a bookkeeping perspective and is a good place to start” (管理の観点では最も単純な手法であり、出発点として適している) と呼んでいる (SpiceDB, Protecting a List Endpoint)。
代償は、最初の行が表示される前に ID の全集合が返ってくることであり、その計算はユーザーからグラフを逆向きにたどる。
- SpiceDB: “it’s a heavy request that can cause performance problems when more than 10k results are involved” (重いリクエストであり、結果が 1 万件を超えると性能問題を起こしうる) (SpiceDB, Querying Data)。また “can get slow quickly: with a sufficiently large relation dataset, a sufficiently complex schema, or a sufficiently large set of accessible results” (十分に大きな関係のデータセット、十分に複雑なスキーマ、あるいは十分に大きなアクセス可能な結果の集合があると、すぐに遅くなりうる) (Protecting a List Endpoint)。このリクエストは結果をストリームで返し、カーソルをサポートする。
- OpenFGA:
ListObjectsは “will return the results found within the time allotted (listObjectsDeadline, default:3s) up to the maximum number of results configured (listObjectsMaxResults, default:1000)” (割り当てられた時間 (listObjectsDeadline、デフォルト3s) 内に見つかった結果を、設定された最大件数 (listObjectsMaxResults、デフォルト1000) まで返す)、そして “access-aware filtering on small object collections” (小さなオブジェクト集合に対するアクセスを考慮した絞り込み) 向けと位置付けられている (OpenFGA, Relationship Queries)。その性能は “drastically depending on the model complexity, number of tuples, and the relations it needs to evaluate” (モデルの複雑さ、タプルの数、評価する必要のある関係によって大きく) 変わり、andやbut notを含む関係は “are more expensive to evaluate than relations withor” (orを含む関係より評価のコストが高い) (Search With Permissions)。
部分的な一覧では並べ替えには足りない。OpenFGA は、一覧全体が手元にそろうまでは “you won’t be able to sort using it” (それを使って並べ替えることはできない) と注記している (Search With Permissions)。
手法 2: データベースに問い合わせたあとにまとめてチェックする
逆の方向である。データベースに候補のページを作らせ (ユーザーのクエリで絞り込み、並べ替えたもの)、そのページを 1 回の一括呼び出し (SpiceDB の CheckBulkPermissions、OpenFGA の /batch-check) でチェックし、拒否された行を落とし、ページが埋まるまで繰り返す。これは、§1 が検索結果について述べているとおりの、一度に数十から数百件という Check の使い方である。
SpiceDB のガイドはこのループとその制約を示している。“because we don’t know how many results are going to be accessible beforehand, we need to iterate until we have a full page of accessible results” (アクセス可能な結果がいくつになるか事前にはわからないので、アクセス可能な結果でページが埋まるまで繰り返す必要がある)。性能は “will depend in part on choosing the size of the page of candidate results” (候補の結果のページサイズの選び方に部分的に依存する)。そして “works better with an API backed by cursor-based pagination than limit-offset pagination, since the database doesn’t know the offset associated with the last accessible result” (データベースは最後のアクセス可能な結果に対応するオフセットを知らないので、limit-offset 方式のページ分割よりカーソル方式のページ分割に基づく API のほうがうまく機能する) (Protecting a List Endpoint)。さらに、すべての一括呼び出しを “at the same revision” (同じリビジョンで) 実行することを推奨している。最初の呼び出しから ZedToken (SpiceDB における zookie) を取り、残りの呼び出しにそれを送ることで、1 つのページが 2 つのスナップショットから組み立てられないようにする。
Anne が自分のドキュメント一覧を開いたとき、2 つの手法はそれぞれどの順で呼び出しを行うか。
コストがどこに移るかに注意したい。事前絞り込みは、Anne が見られるものすべてに比例するコストを 1 回払う。事後絞り込みは、彼女が見られない候補の数に比例するコストを往復ごとに払う。OpenFGA のガイドはこれを規則にしている。検索してからチェックする方式は、データベースのクエリが返す行が少ないか、ユーザーがその行の高い割合を見られる場合に適している。ユーザーが多くのオブジェクトを見られるが、それが全体のごく一部にすぎない場合 (同ガイドの「Google Drive」のケース) には適さない。“you will be retrieving and checking against a lot of items and discarding most of them” (大量の項目を取得してチェックし、その大半を捨てることになる) からである (Search With Permissions)。
手法 3: Watch で更新する非正規化インデックス
3 つ目の手法は §2.4.3 と §2.4.5 が述べているものである。誰が何を見られるかのインデックスを、それが保護するデータの隣に自前で持ち、変更ストリームから最新に保つ。すると一覧のクエリは自分のデータベース内の結合になる。
各部品はどこにあり、何がインデックスを最新に保つのか。
インデクサーの箱に注意したい。これは Zanzibar の内部で Leopard が行っている仕事を担っている。1 つのタプルが多くの行を変えうる。group:eng#member@user:beto を追加すると、group:eng が閲覧できるすべてのドキュメントについて行が 1 つずつ増える。folder:A に閲覧者を追加すると、そのフォルダ内のすべてのドキュメントについて行が 1 つずつ増える。論文は Leopard について同じファンアウトを報告している。“a single Zanzibar tuple addition or deletion may yield potentially tens of thousands of discrete Leopard tuple events” (Zanzibar のタプル 1 つの追加または削除が、数万もの個別の Leopard タプルイベントを生じうる) (§3.2.4)。
製品はこれを構築する方法を 2 つ文書化している。
- 変更ストリームから自分で構築する。 OpenFGA のオプション 2 は
GET /changesを消費し、使用中のモデルバージョンに合わせて変更を平坦化し (同ドキュメントの例: “user:anne, writer, doc:planningbecomes two tuples” (user:anne, writer, doc:planningは 2 つのタプルになる))、最終結果に対して/checkを呼んで “to filter out any resource with permissions revoked but whose authorization data has not made it into your index yet” (権限が取り消されたが、その認可データがまだインデックスに反映されていないリソースを除外する) (Search With Permissions)。SpiceDB ではストリームはWatchである。そのストリームが永続的なキューではない理由は タプルをデータと同期させる で扱う。 - ベンダーに計算させる。 AuthZed Materialize は “takes inspiration from the Leopard index” (Leopard インデックスに着想を得ており)、設定された権限を事前計算する。その Event Streams 機能により “keep your own copy of it — either colocated alongside the data it protects in your application database, or in a secondary index like a search engine” (その自分用のコピーを、保護対象のデータと並べてアプリケーションのデータベースに置くか、検索エンジンのような二次インデックスに置いて保持する) ことができる (AuthZed, What is Materialize?)。これは商用機能である。Event Streams は “currently in early access for AuthZed Dedicated users” (現在 AuthZed Dedicated のユーザー向けにアーリーアクセス中) であり (Protecting a List Endpoint)、文書化された制限には “your application must be able to tolerate some lag” (アプリケーションはある程度の遅延を許容できなければならない) が含まれる (Materialize limitations)。
3 つの比較
規模の上限は各製品のドキュメントからの引用である。レイテンシと手間は相対的なものであり、計測値ではない。
| ルックアップ API のあとにクエリ | クエリのあとに一括チェック | Watch で更新するインデックス | |
|---|---|---|---|
| レイテンシ | アクセス可能なオブジェクトの数とスキーマの深さに応じて増える。最初の行より前に全集合 | 往復の回数、すなわち拒否される候補の割合に応じて増える | データベースの結合。グラフの深さに依存しない |
| 鮮度 | Check と同じ一貫性オプション (SpiceDB では ZedToken、OpenFGA では MINIMIZE_LATENCY / HIGHER_CONSISTENCY) |
Check と同じ。1 ページのすべての往復で 1 つのトークンを使う | ストリームより遅れる。ページを再チェックして取り消された行を落とす |
| ドキュメントにある規模の上限 | SpiceDB: “performance problems when more than 10k results are involved”。OpenFGA: デフォルト 3s と 1000 件、“small object collections” |
SpiceDB: “the size of the page of candidate results” に依存。OpenFGA: ユーザーが多数のオブジェクトのごく一部しか見られない場合は不向き | SpiceDB: “the greatest scalability of the three options” (Materialize 経由) |
| 手間 | 1 回の呼び出しと IN 句 |
ループ、カーソル方式のページ分割、ページサイズの選択 | インデクサー、平坦化のロジック、保存したストリーム位置、再構築。または商用サービス |
OpenFGA のガイドは、ユーザーが多数のうち少数のオブジェクトしか見られない場合に事後絞り込みを実用的にする方法を 2 つ追加している。データベースのクエリでテナントによって絞り込む (“Duplicating logic from the authorization model is not ideal, but it can be a reasonable trade-off” (認可モデルのロジックを重複させるのは理想的ではないが、妥当なトレードオフになりうる))、あるいはより粗いリソース、たとえばユーザーが見られるフォルダを先に一覧し、ドキュメントをフォルダで絞り込む、という方法である (Search With Permissions)。共通の例では、Chen のアクセスは folder:A に由来するので、「Chen が閲覧できるフォルダ内のドキュメント」は 1 つのフォルダからなる一覧で彼をカバーする。
空の一覧についても判断が必要である。SpiceDB のガイドは、きめ細かいシステムでは 403 を返すのではなく “often makes sense to treat ‘there is no data’ and ‘there is nothing you’re authorized to see’ as the same, by returning a successful response with an empty result set” (「データがない」と「見る権限のあるものがない」を、空の結果集合を持つ成功レスポンスを返すことで同じものとして扱うのが理にかなうことが多い) と示唆している (Protecting a List Endpoint)。
出典
- Ruoming Pang et al., Zanzibar: Google’s Consistent, Global Authorization System, USENIX ATC ’19, §1, §2.4.1, §2.4.3, §2.4.5, §3.2.4.
- AuthZed (ベンダー), Protecting a List Endpoint, SpiceDB ドキュメント。
- AuthZed (ベンダー), Querying Data, SpiceDB ドキュメント。
- AuthZed (ベンダー), Google Zanzibar, SpiceDB ドキュメント, 「Reverse Indices」の節。
- AuthZed (ベンダー), What is Materialize? および Limitations。
- AuthZed, Proposal: Lookup Watch API and Tiger Cache for fast ACL-aware filtering, spicedb issue #207, 2021-10-22 起票。
- OpenFGA, Search With Permissions。
- OpenFGA, Relationship Queries: Check, Read, Expand, ListObjects and ListUsers。
- OpenFGA, Query Consistency Modes。