Zanzibar は権限を リレーションタプル として格納する。1 行に 1 つの事実を持ち、「このユーザーはこのオブジェクトに対してこの関係を持つ」と読む。このページで扱うそれ以外のもの、すなわち書き換えルール、Check、Expand はすべて、これらの行から計算される。
本サイトで共通に使う例は次のとおりである。Anne、Beto、Chen (user:anne、user:beto、user:chen)、folder:A の中にあるドキュメント doc:readme、グループ group:eng。Anne は readme を所有し、Beto は eng に所属し、eng のメンバーは readme を閲覧でき、Chen はフォルダ A を閲覧できる。
文法
論文 (§2.1) は、テキスト表記を 4 つの規則で示している。
⟨tuple⟩ ::= ⟨object⟩ ‘#’ ⟨relation⟩ ‘@’ ⟨user⟩
⟨object⟩ ::= ⟨namespace⟩ ‘:’ ⟨object_id⟩
⟨user⟩ ::= ⟨user_id⟩ | ⟨userset⟩
⟨userset⟩ ::= ⟨object⟩ ‘#’ ⟨relation⟩
タプルは 3 つの部分から成る。オブジェクト は名前空間と ID の組で、たとえば doc:readme である。関係 は名前空間が定義する名前で、たとえば owner や viewer である。ユーザー は単一のユーザー ID か ユーザーセット のいずれかである。論文ではユーザー ID は整数だが、本サイトでは例を読みやすくするために user:anne と書く。
1 つのタプルは何を表しているのか。
表しているのは 1 つのことだけである。Anne は doc:readme に対して関係 owner を持つ。論文は、タプルを識別する主キーとして名前空間、オブジェクト ID、関係、ユーザーを挙げている。
ユーザーセット:グループを指すタプル
文法の 4 番目の規則が重要である。ユーザーセットそれ自体もオブジェクトと関係の組であり、group:eng#member は「group:eng に対して関係 member を持つすべてのユーザー」を意味する。タプルのユーザーがユーザーセットである場合、1 行でユーザーの集合全体に何かを付与することになり、その集合は別の行によって定義される。
1 つのタプルで、eng の全メンバーに readme へのアクセスを与えるにはどうするのか。
Beto と readme の両方に言及する行が 1 つもないことに注意されたい。Beto が閲覧者であるのは、2 つ目のタプルが指す集合に彼が含まれているからである。eng にメンバーを追加すれば、readme の ACL を変更しなくても、そのメンバーは readme を閲覧できる。
同じ仕組みは入れ子にできる。グループのメンバーを別のユーザーセットにすることができ、たとえば group:eng#member@group:sre#member (仮のサブチームであり、共通の例には含まれない) のように書ける。こうするとメンバーシップは、タプルが記述する段数だけたどられる。論文はこれを 1 文で述べている。“a ⟨userset⟩ allows ACLs to refer to groups and thus supports representing nested group membership” (⟨userset⟩ によって ACL がグループを参照でき、それにより入れ子のグループメンバーシップを表現できる) (§2.1)。その利点も説明している。オブジェクトごとの ACL ではなくタプルでモデル化することは “allows us to unify the concepts of ACLs and groups” (ACL とグループの概念を統一できる) (§2.1)。グループとは、member 関係が ACL であるオブジェクトにすぎない。
表 1 を 1 つのグラフとして見る
論文の表 1 は 4 つのタプルの例を挙げている。ユーザー 10 と 11 を Anne と Beto に置き換え、Chen のタプルを 1 つ加えると、次のようになる。
| タプル | 読み方 |
|---|---|
doc:readme#owner@user:anne |
Anne は readme の所有者である |
group:eng#member@user:beto |
Beto は eng のメンバーである |
doc:readme#viewer@group:eng#member |
eng のメンバーは readme の閲覧者である |
doc:readme#parent@folder:A#... |
readme はフォルダ A の中にある |
folder:A#viewer@user:chen |
Chen はフォルダ A の閲覧者である (表 1 にはない) |
4 行目の #... は、“a relation that does not affect the semantics of the tuple” (タプルのセマンティクスに影響しない関係) を表す論文の記法である (表 1 のキャプション)。このタプルはフォルダのユーザーの集合ではなく、フォルダそのものを指している。
5 行すべてをまとめるとどうなるか。
parent の辺はアクセスについて何も述べていないことに注意されたい。論文の言葉では、一部の関係は “only define abstract relations between objects. These abstract relations may indirectly affect access control given userset rewrite rules specified in namespace configs” (オブジェクト間の抽象的な関係を定義するだけである。これらの抽象的な関係は、名前空間設定で指定されたユーザーセット書き換えルールによって、間接的にアクセス制御に影響することがある) (§2.1)。Chen が readme を閲覧できるかどうかはそのようなルールによって決まる。それが次の節の内容である。
名前空間の設定
クライアントはタプルを格納する前に、doc や folder のような 名前空間 を設定する (§2.3)。設定には名前空間の関係が列挙され、それぞれが名前と リレーション設定 を持つ。さらにストレージパラメータ、すなわちシャーディングの設定とオブジェクト ID のエンコーディングも含まれる。
タプルだけでは実効的な ACL は定まらない。多くのクライアントは、すべての編集者を閲覧者にもしたいと考える。各オブジェクトの各編集者について viewer タプルを追加で格納するのは、論文の言葉では “wasteful and make it hard to make modifications across all objects” (無駄であり、全オブジェクトにまたがる変更も困難になる) (§2.3.1)。代わりに、リレーション設定は ユーザーセット書き換えルール を持つことができる。これはオブジェクト ID を受け取り、ユーザーセット式の木を返す関数である。
以下は論文の図 1 をそのまま写したものである。
name: "doc"
relation { name: "owner" }
relation {
name: "editor"
userset_rewrite {
union {
child { _this {} }
child { computed_userset { relation: "owner" } }
} } }
relation {
name: "viewer"
userset_rewrite {
union {
child { _this {} }
child { computed_userset { relation: "editor" } }
child { tuple_to_userset {
tupleset { relation: "parent" }
computed_userset {
object: $TUPLE_USERSET_OBJECT # parent folder
relation: "viewer"
} } }
} } }
Figure 1: Simple namespace configuration with concentric relations on documents. All owners are editors, and all editors are viewers. Further, viewers of the parent folder are also viewers of the document. (図 1: ドキュメントに対する同心円状の関係を持つ単純な名前空間設定。すべての所有者は編集者であり、すべての編集者は閲覧者である。さらに、親フォルダの閲覧者はそのドキュメントの閲覧者でもある。)
書き換え木の葉には 3 種類がある (§2.3.1)。
| 葉 | 返すもの | 図 1 での例 |
|---|---|---|
_this |
このオブジェクトと関係について格納されたタプル中のユーザー。それらのタプルが指すユーザーセットも含む。関係にルールがない場合のデフォルト。 | doc:readme に格納された viewer タプル |
computed_userset |
同じオブジェクトの別の関係のユーザーセット。 | 同じドキュメントの editor。editor については owner |
tuple_to_userset |
オブジェクトから タプルセット を読み取り、見つかった各タプルからユーザーセットを計算する。 | ドキュメントの parent タプルを読み、各親フォルダの viewer を取る |
葉は和集合、積集合、除外で組み合わされる (§2.3.1)。図 1 は和集合だけを使っている。積集合はユーザーがすべての子に含まれることを要求し、たとえば「eng にも所属する編集者」を表せる。除外は集合を取り除き、たとえば「ブロックリストを除いた閲覧者」を表せる。この 2 つの例は説明のためのものであり、論文にはない。
viewer ルールは 1 つのドキュメントに対してどのような木を作るのか。
owner が 2 段下にあることに注意されたい。所有者は編集者であり、編集者は閲覧者である。これが図 1 のキャプションにある「同心円状の関係」の意味である。ドキュメントの外に出るのは右の枝だけであり、格納された parent の辺をたどって別のオブジェクトに向かう。
グラフ探索としての Check
Check リクエストはユーザーセット ⟨object#relation⟩ とユーザーを指定し、そのユーザーがユーザーセットに含まれるかを問う (§2.4.4)。書き換えルールがない場合、論文は評価を再帰的な式として書いている (§3.2.3)。タプル ⟨object#relation@U⟩ が存在するか、U′ がユーザーセットでありユーザーが U′ に含まれるようなタプル ⟨object#relation@U′⟩ が存在すれば、ユーザーは ⟨object#relation⟩ に含まれる。論文はこの再帰を「pointer chasing」(ポインタ追跡) と呼ぶ。書き換えルールも “are also translated to boolean expressions as part of check evaluation” (チェック評価の一部としてブール式に変換される) (§3.2.3)。したがって上の式の木は、3 つの枝の OR になる。
次の 4 つの図で扱う問いは、Chen は doc:readme を閲覧できるか、である。どの図も同じグラフを使い、その時点の枝が読む辺を強調している。folder の名前空間設定は論文にはない。これらの図では folder#viewer には書き換えルールがなく、単に _this であると仮定する。
ステップ 1:_this
readme に格納された viewer タプルは Chen を含むか。
格納された閲覧者はユーザーセットだけなので、Check は group:eng#member へ再帰する。そのメンバーは Beto だけである。この枝の答えは no である。
ステップ 2:computed_userset で editor、次に owner
Chen は編集者か、あるいは所有者か。
書き換えは同じオブジェクト上で viewer から editor、owner へと移る。最初の 2 つのホップに格納されたタプルは要らない。それらは設定から得られる。所有者は Anne 1 人なので、この枝の答えも no である。
ステップ 3:tuple_to_userset で親を見つける
readme はどのフォルダにあるか。
parent タプルは表 1 の「抽象的な関係」である。それ自体は何も付与しない。書き換えルールがそれを、別のオブジェクトについての新しい問いに変える。
ステップ 4:folder:A#viewer
Chen はフォルダ A の閲覧者か。
経路 user:chen → folder:A → doc:readme が問いに答える。どの図でも辺の向きは同じだが、探索は readme から外側へ向かって進んだことに注意されたい。Check は ⟨object#relation⟩ から出発してユーザーを探す。
このようなポインタ追跡は “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)。そうした名前空間に対して Zanzibar は Leopard インデックスを使う。これは Leopard のページ で説明する。
Read と Expand
2 つの API 呼び出しは、同じデータを異なる抽象度で見る。
Read (§2.4.1) は格納されたタプルだけを返す。リクエストは 1 つ以上の タプルセット を指定する。タプルセットは単一のタプルキーか、名前空間内のあるオブジェクト ID またはユーザーセットを持つすべてのタプルであり、任意で 1 つの関係に絞り込める。論文は “Read results only depend on contents of relation tuples and do not reflect userset rewrite rules” (Read の結果はリレーションタプルの内容のみに依存し、ユーザーセット書き換えルールを反映しない) (§2.4.1) と明言している。共通の例で doc:readme を関係 viewer で Read すると、1 行が返る。
doc:readme#viewer@group:eng#member
すべての所有者は閲覧者であるにもかかわらず Anne は含まれず、Chen も readme を閲覧できるにもかかわらず含まれない。
Expand (§2.4.5) は “follows indirect references expressed through userset rewrite rules” (ユーザーセット書き換えルールによって表現された間接参照をたどる)。Expand は ユーザーセット木 を返す。葉はユーザー ID か、他の ⟨object#relation⟩ ペアを指すユーザーセットであり、中間ノードは和集合、積集合、除外である。
doc:readme#viewer に対して Expand は何を返すか。
破線の葉が 2 つあることに注意されたい。§2.4.5 によれば、葉は他所を指すユーザーセットでありうるので、個々のユーザー (Beto、Chen) をすべて知りたいクライアントは、それらの葉をさらに Expand する。1 回の Expand 呼び出しがどの深さまで再帰するかは論文に書かれていない。この図は、ドキュメント自身のルールが到達するユーザーセットで止めている。論文はユースケースを挙げている。Expand によってクライアントは “reason about the complete set of users and groups that have access to their objects, which allows them to build efficient search indices for access-controlled content” (自身のオブジェクトにアクセスできるユーザーとグループの完全な集合を把握でき、それによってアクセス制御されたコンテンツのための効率的な検索インデックスを構築できる) (§2.4.5)。
出典
- Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang