Zanzibar モデルで考えるグラフの単調性と権限追記の安全性

Masaki Haga

2026.6.22

はじめに

Sreake 事業部の芳賀雅樹 (@silasolla) です．

システムを運用する上で，しばしば権限を管理することがあるかと思います．パブリッククラウドにはマネージドの管理基盤もあるでしょう．唐突ですが，こういった基盤に権限情報を追記したときの挙動を考えてみます．ある情報を追加するだけで削除することはないと思えば (誤って強い権限を与えてしまうような人的問題が無ければ) 直感的には安全に思えます．たとえば，新しいメンバーをグループに入れるとか，あるいは新しいドキュメントを共有するだとか，いずれも既存の権限を失わせる操作には見えません．

しかしながら，実際の権限管理では「特定の条件を除外する」といった複雑なルールも求められます．分散システムにおいては，こういったルールが存在すると「情報を追加しただけなのに，本来拒否されるべきアクセスが許可されてしまう」といった，直感に反した重大な事故が起きかねません．データの届く順序がレプリカごとに保証されない分散環境において，そういった状態の揺らぎがなぜ起きるのか，どういう権限モデルであれば，データの届く順序を気にしなくても安全だと言い切れるのか，これから順を追って見ていきましょう．

素朴な権限管理

簡単な例として，ユーザとリソースの対応を 1 行ずつテーブルに置く場合を考えます．

CREATE TABLE access_control (
    user_id   TEXT,
    doc_id    TEXT,
    role      TEXT,  -- 'viewer', 'editor', etc.
    PRIMARY KEY (user_id, doc_id, role)
);

alice が doc-1 を閲覧できるかどうかは，1 つの SELECT 文で判定できます．

SELECT 1 FROM access_control
WHERE user_id = 'alice' AND doc_id = 'doc-1' AND role = 'viewer';

シンプルな設計ですね．ユーザとリソースが直接対応するので，あまり難しいことは考えなくてよさそうです．それでは，少し複雑にして直接対応ではない場合を考えます．グループの概念を導入できるよう，スキーマを調整してみましょう．

CREATE TABLE group_members (
    group_id  TEXT,
    user_id   TEXT
);
CREATE TABLE group_access (
    group_id  TEXT,
    doc_id    TEXT,
    role      TEXT
);

ユーザと直接対応するのは，あくまでも「権限グループ」で，そのグループに個々の閲覧権限を設定します．たとえば，alice は engineering グループのメンバーで，そこに所属するメンバーは doc-1 に対する viewer 権限があるというのは，1 回の JOIN で判定できるでしょう．

SELECT 1
FROM group_members gm
JOIN group_access ga ON gm.group_id = ga.group_id
WHERE gm.user_id = 'alice' AND ga.doc_id = 'doc-1' AND ga.role = 'viewer';

これもやはり問題なさそうですね．さらに複雑な場合を考えます．権限のグループをネストさせてみましょう．次のようなスキーマを追加して，グループの権限を子グループへ継承させます．

CREATE TABLE group_nests (
    parent_group_id TEXT,
    child_group_id  TEXT
);

例によって，alice は backend-team に所属しており，さらに backend-team は engineering に所属しており，engineering は doc-1 の viewer である場合を考えましょう．こんなクエリで判定できるでしょうか．

SELECT 1
FROM group_members gm
JOIN group_nests gn ON gm.group_id = gn.child_group_id
JOIN group_access ga ON gn.parent_group_id = ga.group_id
WHERE gm.user_id = 'alice' AND ga.doc_id = 'doc-1' AND ga.role = 'viewer';

ネストが 2 段の場合を考えたので，このように group_members → group_nests → group_access と JOIN する数が増えました．この調子でネストが 3, 4, … と深くなれば，この group_nests を自己結合する JOIN がさらに増えてしまいます．こういう問題は，テーブルのスキーマが「グループ」や「ドキュメント」といった，具体的な権限モデルに依存していることで引き起こされます．どうすれば，こうした依存を断ち切れるでしょうか．

たとえば，モデルごとにテーブルを作るのをやめ，全ての権限関係を (subject, relation, object) といった形で 1 つのテーブルに押し込み，WITH RECURSIVE のような再帰 CTE を用いて複数の階層をグラフとして探索する方法があります．この記事で紹介する Google の Zanzibar [1] が採っているのも，本質的にはそういったアプローチです．

Relation Tuple による一様な表現

Google の Zanzibar と言われてもパッとイメージの湧かない方もいるかと思います．これは Calendar, Cloud, Drive, Maps, Photos, YouTube, … をはじめとした，Google のサービス群における巨大な認可基盤です．Zanzibar では，誰が何にどうアクセスできるかという ACL データを，その種類によらず 1 つのタプルの形で表現します．

先ほど RDB で表現しようと試みた関係を，次のように書き直してみましょう．

権限の表現権限の意味
group:engineering#member@alicealice は engineering のメンバー
group:engineering#member@bobbob は engineering のメンバー
doc:doc-1#viewer@group:engineering#memberengineering のメンバーは doc-1 の閲覧者

最初の 2 つは object#relation@user という形で権限を定義しています．3 つ目では @ の右側に単一のユーザではなく group:engineering#member というグループが置かれます．このグループは engineering における全てのメンバーを表現しており，グループ全体に対する権限の付与を 1 つの表現で記述しています．

グループのネストも同じ形式で自然に表現されます．

権限の表現権限の意味
group:backend-team#member@alicealice は backend-team のメンバー
group:engineering#member@group:backend-team#memberbackend-team のメンバーは engineering のメンバー
doc:doc-1#viewer@group:engineering#memberengineering のメンバーは doc-1 の閲覧者

ネストの深さが変わったとしても，テーブルのスキーマやクエリの形は変わりません．モデルが変わってもタプルを追加するだけで済みます．こういった「一様な」表現によって，Zanzibar はスキーマのモデル依存を回避しています．

BNF による定義 (§2.1) を見てみましょう．

\begin{aligned} \langle tuple \rangle &\mathrel{\texttt{::=}} \langle object \rangle \mathrel{\texttt{\#}} \langle relation \rangle \mathrel{\texttt{@}} \langle user \rangle \\ \langle object \rangle &\mathrel{\texttt{::=}} \langle namespace \rangle \mathrel{\texttt{:}} \langle object\_id \rangle \\ \langle user \rangle &\mathrel{\texttt{::=}} \langle user\_id \rangle \mid \langle userset \rangle \\ \langle userset \rangle &\mathrel{\texttt{::=}} \langle object \rangle \mathrel{\texttt{\#}} \langle relation \rangle \\ \end{aligned}

\langle user \rangle として \langle user\_id \rangle (単一ユーザ) だけでなく \langle userset \rangle (ユーザの集まり) の選択を許しています．これにより，ネストしたグループのメンバーシップを表現でき，考えている関係の種類や深さによらない一様性を支えています．

権限の表現が分かったところで，それを具体的にどうやって判定するのか，先ほどの例で言えば alice が doc-1 の閲覧者であることをどう判定するのか見ていきましょう．

タプルの集まりをグラフとして捉える

タプルの集まりを，有向グラフとして解釈します．各タプルにおける @user 部分を始点ノード，namespace:object 部分を終点ノードとし，タプル 1 つにつき 1 本の有向辺を引いていきます．また辺のラベルには関係の情報 (relation) を付与します．

先ほどの 3 つのタプルを変換すると，以下のようなグラフが得られます．

実際の Zanzibar では，グラフのノードは単なる object ではなく object#relation (すなわち \langle userset \rangle) 単位で表現され，さらに relation 間の演算を定義する userset rewrite rules が加わるため，権限の判定は「グラフ探索」に「式の評価」を交えたハイブリッドな処理になります．

この記事では，議論を本質的な骨格に絞るため，まずは rewrite を外した最小モデルで考えていきます．考える relation も member と viewer の 2 種類のみに絞り，少しずつ演算を戻していきながら振る舞いを見ていきます．これにより，グループのノード (group:engineering#member) をオブジェクト (group:engineering) と同一視し，辺のラベルも区別することなく，単なるパスの有無として扱います．

こうすることで「alice は doc-1 の閲覧者かどうか」は「alice から doc-1 へのパスが存在するか？」と読み替えられます．どれだけネストが深くなっても，権限の判定はパスの到達性という単一の問題に帰着できて，これがこのモデルの嬉しいところです．

\text{check} (\texttt{alice}, \texttt{doc-1\#viewer}, T) \iff \texttt{alice} \to^{+} \texttt{doc-1\#viewer} \mathrel\text{in} G(T)

グループのメンバーシップを到達性の問題に帰着させるアプローチは Zanzibar の論文 (§3.2.4) でも言及していました．この記事ではその到達性がどのような場合に崩れないのかを見ていきます．

リレーション追加の安全性

グラフを用いた権限判定のモデルができたところで，まずは一度成立した権限が後からタプルを追加したことによって壊れないことを確かめていきましょう．

辺集合 E を持つ有向グラフ G = (V, E) において，頂点 v から到達可能な頂点の集合を \text{Reach}(v, E) とします．このとき，以下が成立します．

E \subseteq E' \implies \text{Reach}(v, E) \subseteq \text{Reach}(v, E')

すなわち，辺を追加しても到達可能な頂点の集合は縮小しません．

w \in \text{Reach}(v, E) とします．定義より E の辺のみを使った v から w へのパス v = v_0 \to v_1 \to \cdots \to v_k = w が存在します．E \subseteq E' であるから，このパスの各辺は E' にも含まれます．したがって，同じパスが E' でも有効であり，w \in \text{Reach}(v, E') が成り立ちます．

たとえば，初期状態として 2 つのタプルがあるとしましょう．

タプル対応する辺
group:engineering#member@alice\texttt{alice} \to \texttt{engineering}
doc:doc-1#viewer@group:engineering#member\texttt{engineering} \to \texttt{doc-1}

alice から到達できる頂点の集合 \text{Reach}(\texttt{alice}) は \lbrace\texttt{engineering}, \texttt{doc-1}\rbrace ですね．ここに doc:doc-2#viewer@group:engineering#member というタプルを追加したとします．すると engineering のメンバーに doc-2 の閲覧権限が付与されます．

到達可能な頂点の集合 \text{Reach}(\texttt{alice}) は \lbrace\texttt{engineering}, \texttt{doc-1}, \texttt{doc-2}\rbrace に拡大しました．doc-2 の追加で doc-1 へのアクセスは失われません．

合成演算における単調性

ここまでの議論では，単一の relation (member や viewer) による単純な辺の追加を扱いました．しかしながら，Zanzibar をはじめとした実際の権限モデルでは，複数の relation を合成して 1 つの権限を定義することでしょう．こういった合成演算が単調性にどう影響するのかを見ていきます．

たとえば，以下のようなケースを考えてみましょう．

  1. viewer または editor であれば閲覧できる
  2. viewer かつ nda-signer であれば機密文書を閲覧できる
  3. engineering のメンバーから contractor を除外して閲覧を許可する

これらはそれぞれ，到達可能な集合に対して「和集合 (union)」や「共通部分 (intersection)」や「差集合 (exclusion)」を取ることに対応しています．これらの演算子で合成された権限も，情報の追加に対して単調性を保つのでしょうか．

まずは，和集合を取る場合を考えます．あるタプル集合 T が与えられたとき「viewer または editor であれば対象 doc-1 を閲覧できる」という権限 \text{view}(u, \texttt{doc-1}, T) は，viewer としての到達可能性と editor としての到達可能性の論理和 (OR) として定義できます．

\text{check}(u, \texttt{doc-1\#viewer}, T) \lor \text{check}(u, \texttt{doc-1\#editor}, T)

\text{view}(u, \texttt{doc-1}, T) が成立しているとしましょう．定義より \text{check}(u, \texttt{doc-1\#viewer}, T) と \text{check}(u, \texttt{doc-1\#editor}, T) のどちらか一方は成立しています．ここで T \subseteq T' となるようにタプル集合が T' に拡大したとき，これまでに見てきた通り個々の条件は単調であるため，どちらが成立していたとしても T' において条件が維持されます．したがって，論理和を取った \text{view}(u, \texttt{doc-1}, T') も成立します．つまり，和集合は単調性を保ちます．

共通部分を取る場合も考えてみます．たとえば「viewer かつ nda-signer であれば機密文書を閲覧できる」という権限 \text{view}(u, \texttt{doc-1}, T) は，これらの条件の論理積 (AND) にあたります．

\text{check}(u, \texttt{doc-1\#viewer}, T) \land \text{check}(u, \texttt{nda-signer\#member}, T)

T \subseteq T' とし \text{view}(u, \texttt{doc-1}, T) が成立しているとしましょう．定義より \text{check}(u, \texttt{doc-1\#viewer}, T) と \text{check}(u, \texttt{nda-signer\#member}, T) の両方が成立しています．これらは単調であるため T' においても両方が成立し続けます．したがって，論理積を取った \text{view}(u, \texttt{doc-1}, T') も成立します．つまり，共通部分も単調性を保ちます．

最後に，差集合を取る場合を考えましょう．たとえば「engineering のメンバーから contractor を除外して閲覧を許可する」という権限を考えます．これは member としての到達可能性から contractor としての到達可能性を差し引くものであり，\text{view}(u, \texttt{doc-1}, T) の条件としては，後者の否定を取ったうえでの論理積 (AND NOT) に対応します．

\text{check}(u, \texttt{engineering\#member}, T) \land \lnot \text{check}(u, \texttt{contractor\#member}, T)

和集合や共通部分と同じように \text{view}(u, \texttt{doc-1}, T) を仮定して，タプル集合が T \subseteq T' なる T' に拡大したときを考えてみましょう．定義より \text{check}(u, \texttt{engineering\#member}, T) は成立しており，かつ \text{check}(u, \texttt{contractor\#member}, T) は成立していません．

前者の条件は，単調性によって T' においても成立します．ところが，後者が問題です．タプルの追加によって，もし \text{check}(u, \texttt{contractor\#member}, T') が偽から真に変わってしまったとしたらどうなるでしょうか．否定 (\lnot) を取っているため，後半の条件は真から偽に反転し，最終的に論理積を取った \text{view}(u, \texttt{doc-1}, T') も成立しなくなってしまいます．

そういうわけで，論理和 (OR) と論理積 (AND) だけで構成された否定 (NOT) を含まない権限の定義は情報の追加に対する単調性を保ちますが，ここに否定が入ってしまうと単調性の保証が失われるわけです．これは Zanzibar に固有の話ではなく，集合演算の一般的な性質です．和集合と積集合は引数の拡大に対して単調ですが，差集合は引かれる側の拡大に対して反単調です．

単調性の崩れが引き起こす問題

単調性が崩れるような，具体的なシナリオを見てみましょう．alice は engineering のメンバーであり，contractor ではない状態で，doc-1 の閲覧者だとします．

権限の表現権限の意味
group:engineering#member@alicealice は engineering のメンバー
doc:doc-1#viewer@group:engineering#memberengineering のメンバーは doc-1 の閲覧者

ここに group:contractor#member@alice (alice を contractor に追加する) というタプルを 1 つ追加します．alice は engineering メンバーのままですが，このルールにより doc-1 の閲覧者ではなくなってしまいます．つまり，権限情報 (辺) の追加が既存の権限を縮小させてしまいました．ルール通りに除外されたのだから，何も問題ないのでは？ と思うかもしれません．単一のデータベースであればそうなのですが，今回はデータの届く順序が保証されない分散システムを考えています．

もし管理者が，新入りの alice を「engineering に入れる」操作と「contractor に入れる (機密文書は見せない)」操作を同時に行ったとします．このとき，あるレプリカに engineering のタプルだけが先に届き，contractor のタプルがネットワーク遅延で届いていなかったらどうなるでしょうか．そのレプリカは「alice は engineering のメンバーで contractor のタプルは見当たらないからアクセス許可しよう」と判定してしまいます．権限データの到着が遅れることで，本来は見せたくない機密文書を閲覧させてしまう事故が発生しかねないわけです．

まだ届いていないだけなのか，本当に存在しないのかを区別できない分散環境において，単調性の崩壊 (情報の不在に依存した判定) は，こうした致命的な状態の揺らぎを引き起こします．

このように，単調であれば順序によらず安全で，否定が入ると崩れるという性質は，Zanzibar に限った話ではありません．これは分散システムにおける CALM 定理 [2] として知られます．CALM 定理は，ある計算を coordination-free (データ交換以外の調整や同期を伴わない) なまま結果整合性の分散環境で安全に実行できることと，その計算が単調であることが等価だという結果です．

分散システムにおける一貫性は，しばしば線形化可能性といった，ストレージやメモリに対する読み書きの順序をどう制御するかを重視してきました．一方で CALM 定理は「合流性」という，プログラムの出力レベルでの一貫性を，安全性の基準に置いています．ストレージへの入力順が通信の遅延によってどれほどバラバラ (非決定的) であっても，アプリケーションにおける最終的な判定結果は一致するという性質です．

これを今回の権限モデルに当てはめると，否定を含まない単調なルールであれば，たとえデータの到着順をレプリカ間で調整しなくても，途中で誤った判定を下すことなく，最終的には正しい権限状態へ落ち着くということになります．さらに裏を返せば，差集合を含んで単調でなくなったルールは，そのままでは安全性を保証できず，予期せぬ誤判定を防ぐためには，レプリカ間での同期や別の仕組みによる調整が必要です．

SpiceDB [3] や OpenFGA [4] といった Zanzibar に影響を受けた認可システムでは，これまで見てきた演算の概念が，スキーマ言語として明示的に提供されます (SpiceDB では + が union に，& が intersection に，- が exclusion に対応します)．

これらのシステムにおいて，スキーマを設計する際にどの演算子を用いるかは，システムにおける単調性の境界をどこに引くかの選択を伴います．和集合や共通部分のみを用いてレプリカ間の調整が要らない安全性を得るか，あるいはレプリカ間の同期などを許容してでも差集合による表現力を得るか，スキーマ上で明示的に選択しているわけです．

もっと踏み込んだ話

この記事では，本質に目を向けるために簡略化したモデルを考えましたが，実際の認可システムの運用はもう少し複雑です．現実の Zanzibar には computed_userset や tuple_to_userset といった userset rewrite rules があり，この上での演算子の挙動を追う必要があります．こうした複雑なルールの組み合わせが意図通りに機能することを担保するため，SpiceDB や OpenFGA などのエコシステムでは，スキーマに対する単体テストや検証ツールが標準的に提供されています．

ルールの評価そのものに加えて，権限の削除がシステム全体に反映される順序も重要です．単調性が保証するのは，あくまでも追記に対する安全性のみであり，権限を削除した直後に古いスナップショットで評価してしまう New Enemy 問題などはスコープ外です．こういった問題の本質は「権限を剥奪した直後に別のチャットツールで連絡を取り合う」といった外部のやり取りによって，システムが認識する状態と現実の因果関係に矛盾が生じてしまう点にあります．システム内の通信しか追跡できない論理時計では外の因果関係を捉えきれないため，外部整合性を保証できる仕組みが必要です．Zanzibar は zookie による符号化で対処しますが，これを支えているのが Spanner の TrueTime と Paxos です (Spanner については，手前味噌ですが以下の記事をご覧ください)．SpiceDB などのエコシステムでも，ZedToken と分散データベースを組み合わせることで，この問題を防いでいます．

地球規模の「時間のずれ」を Cloud Spanner はどう解決したか

最後に差集合が単調性を崩すことを見ましたが，単調なルールは評価に用いるスナップショットが古くても「許可を取りこぼして拒否する」フェイルセーフ側にしか倒れない一方で，差集合は「拒否を取りこぼして許可する」側に倒れかねないのが厄介でした．やはり本質的には，権限を縮小してしまう変更が古い状態で評価されるのが問題なので，これも New Enemy と同様に zookie や ZedToken などを利用して読み取りの精度を要求し，インフラ層として必要な分だけ調整すればよいでしょう．その上で，ルールの記述そのものが意図通りに対象者を弾けているかという論理的な正しさを担保するのは，スキーマテストの領分となります．差集合は利用する箇所の一つ一つがこの危険な点を孕むので，実際の運用においては退職者や凍結アカウントの除外のように，ビジネス要件として自明かつ検証しやすい箇所に絞る設計が求められるでしょう．

まとめ

この記事では Zanzibar の権限モデルを題材にして，Relation Tuple を有向グラフとして捉えて権限の判定をパスの到達性に帰着させる流れや，単調性に関する振る舞いを見てきました．否定を含まないルールであればタプルの到着順によらない安全な判定が保証され，否定を含めるとこの保証が失われます．実際の Zanzibar では Spanner などの枠組みでその穴を埋めています．

ソフトウェアの設計において，システムの表現力を拡張することは，往々にして，これまで持っていた構造的な保証を手放すことを意味します．どこまでを単調性で保証し，どこから先を外部に委ねるのか，SpiceDB や OpenFGA が提供するスキーマ演算の選択は，まさにこの境界を宣言するようなものです．認可モデルという特定のドメインに限らず，得られる表現力と手放す保証の境界やバランスを見極めることは，複雑なシステムを設計していく上での確かな指針となるはずです．

参考文献

  1. Pang, R., et al. (2019). Zanzibar: Google’s Consistent, Global Authorization System. USENIX Annual Technical Conference (USENIX ATC 19), 33–46.
  2. Hellerstein, J. M., & Alvaro, P. (2020). Keeping CALM: When Distributed Consistency is Easy. Communications of the ACM, 63(9), 72–81.
  3. AuthZed. SpiceDB. https://github.com/authzed/spicedb
  4. OpenFGA. OpenFGA. https://openfga.dev/

関連ブログ

Snowflake Cortex AIのコスト管理・監視 実践ガイド — 本番運用前に押さえておきたいこと

Kaneko Shohei

2026.6.18

ディレクトリ構成 ~ハイブリッド型編~

Kodai Nakahara

2025.10.16

MultiKueueを利用した外部クラスタへのジョブスケジューリング

Ryosuke Sakurai

2025.6.19

ブログ一覧へ戻る

お気軽にお問い合わせください

SREの設計・技術支援から、
SRE運用で使用する
ツールの導入など、
SRE全般についてご支援しています。

資料請求・お問い合わせ