More than 1 year has passed since last update.

Googleの認可基盤Zanzibar論文メモ

Last updated at 2023-09-21Posted at 2023-09-21

Google Zanzibarの論文を読んだ。

今後の認可設計の参考にするための自分用メモ
https://authzed.com/zanzibar

概要

Zanzibarは、Calendar、Cloud、Drive、Maps、Photos、YouTubeなど、Googleの何百ものクライアントサービスからの幅広いアクセス制御ポリシーを表現することができる、サービス横断的な認可システムである。

認可判断は、アクセス制御リストやオブジェクトのコンテンツが変更されても一貫性を保つことができ、リアルタイム性を持っている。

1秒間に数兆のアクセス制御リストと数百万の認可リクエストに対応するスケーラビリティを備えている。
95パーセンタイルのレイテンシは10ミリ秒未満、可用性は3年間の実運用で99.999%以上を維持している。

導入

ウェブサービスでは、デジタルオブジェクトに対する操作をユーザーが許可されているかを確認するための認可チェックが必要となる。

例えば、Webベースの写真ストレージサービスでは、写真の所有者が友人と一部の写真を共有しながら、他の写真を非公開にすることが一般的。
このようなサービスでは、ユーザーが写真を閲覧する前に、その写真がユーザーと共有されているかどうかをチェックする必要がありる。
確実な認可チェックは、オンラインでのプライバシーを保護する上で重要な役割を持つ。

Zanzibarは以下の目標を設定している
正確さ: ユーザーの意図を尊重して、アクセス制御の決定の一貫性を確保する必要がある。
柔軟性: 消費者とエンタープライズのアプリケーションの両方が求める豊富なアクセス制御ポリシーをサポートする必要がある。
低遅延: 認可チェックは、ユーザーのインタラクションのクリティカルパスによく含まれているため、迅速に応答する必要がある。
高可用性: 明示的な認可がない場合、クライアントサービスはユーザーのアクセスを拒否する必要があるため、リクエストに確実に応答する必要がある。
大規模: 数十億のユーザーによって共有される数十億のオブジェクトを保護する必要がある。クライアントやそのエンドユーザーの近くにあるため、全世界に展開する必要がある。

データモデル

tuple

基本の認可データモデルは下記のようになり、tupleと呼ばれる

objectは認可対象のデータ
userは認可されているユーザー
relationはクライアント設定であらかじめ定義されている、objectに対するuserの関係性を示す

<tuple> ::= <object>\#<relation>@<user>

object

さらに、objcetは厳密には下記のように表現される

<object> ::= <namespace>:<object\_id>

例えばAというドキュメントが存在する場合は下記のように表される

<object> ::= doc:A

user

単純なuserだけではなく、user_setという表現もできる

<user> ::= <user\_id> || <userset>

<userset>::=<object>\#<relation>

例

文書A(doc:A)の管理者権限(owner)をTaroさんがもっているとする下記のような表記になる

doc:A\#owner@Taro

ユーザセットを利用したACLとして下記を考えてみる
エンジニアグループ(group:eng)のメンバー(member)としてTaroが所属しており
文書A(doc:A)の閲覧権限(viewer)をエンジニアグループ(group:eng)のメンバー(member)が持っている場合

エンジニアグループ(group:eng)のメンバー(member)としてTaroが所属しているユーザセット

group:eng\#member@Taro

文書A(doc:A)の閲覧権限(viewer)をエンジニアグループ(group:eng)のメンバー(member)が持っている

doc:A\#viewer@group:eng\#member

一貫性

ZanzibarはACLがアップデートされたのちに古いACLを読み込むことによるポリシーの不整合を防ぐために、zookieと呼ばれるタイムスタンプを利用する
このzookieはACLの更新毎に生成される。

例えば次のようなケースを考える

アリスはドキュメントのACLからボブを削除する。
次に、アリスはチャーリーにそのドキュメントの変更を依頼する。
ボブは新しい内容を見ることはできないはずだが、ボブの削除前の古いACLで認可が評価される場合、ボブが新しい内容を見ることができてしまう

それぞれのタイミングに対して、T1、T2、T3が存在しており、T1 < T2 < T3とする。
例えばClientがZanzibarにACLの検証を問い合わせた時、zookieのタイムスタンプTがT < T1の場合、ACL変更前の権限のためドキュメントを閲覧することができてしまうかもしれない。
しかし、このzookieを持っていることにより、最新のT3のACLよりも古い状態の認可処理であることがわかるために、最新のACLで認可を行う必要があることを判断できる。

これにより、認可のリアルタイム性と一貫性を実現している。

ネームスペースの設定

前述のデータモデルのtupleを作成するには、前提としてネームスペースが必要となる。
前例でいうと、doc:Aのdoc、ユーザーセットで登場したgroup：engのgroupがネームスペースにあたる。

リレーションタプル

リレーション・タプルはオブジェクトとユーザーの関係を表す。
有効なACLを完全に定義するものではないが、そのオブジェクトに対してどのようなリレーションが存在するかを表現する。
またリレーション同士の関係性も表現する

下記はオブジェクトdocに関する定義である。
オブジェクトdocには、リレーションとしてowner、editor、viewerが存在する。

viewerがeditorを含み、editorがownerを含む、同心円状の関係を持つ単純なネームスペース構成を示している。
同心円状の外側から内側へ権限が継承されるため、権限の強さは viewer < editor < owner となる

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 {relation: "parent"}
        computed_userset {
            object: $TUPLE_USERSET_OBJECT # parent folder
            relation: "viewer"
        }
      }
    }
  }
}

API

Read

リレーション・タプルのセットのキーを指定して、タプルを読み取る。
単一のタプル・キー、または名前空間内の指定されたオブジェクトIDまたはusersetを持つすべてのタプルを含めることができ、オプションでリレーション名による制約も可能。
読み取り要求内のすべてのタプルセットが単一のスナップショットで処理される。

zookieを使用リクエストに付与する場合、WriteによるレスポンスのzookieがこのReadで与えられた場合、そのWriteの時よりも前の読み取りスナップショットを取得することができる。
ReadレスポンスからのzookieがこのReadで与えられた場合、以前の読み取りと同じスナップショットで要求することができる。

リクエストがzookieを含まない場合、zookieが提供された場合よりも低レイテンシの応答をする可能性があるが、比較的に新しいスナップショットを選択できる。

Write

ACLを追加または削除するために、単一の関係タプルを修正することができる。
またReadの後にWriteを使用する楽観的並行性制御[を使用して、Read-ACL変更-Writeによって、オブジェクトに関連するすべてのタプルを変更することもできる。

Watch

Watchリクエストでは、1つ以上のネームスペースと、Watch開始時刻を表すzookieを指定する。
Watchレスポンスでは、要求された開始タイムスタンプからハートビート・zookieでエンコードされたタイムスタンプまで、すべてのタプル変更イベントがタイムスタンプの昇順で含まれている
クライアントはハートビートZookieを使用して、前のウォッチ応答が終了したところから監視を再開することができる。

Check

Checkリクエストでは、object#relationで表されるユーザーセット、ユーザー、およびオブジェクトのバージョンに対応するzookieを指定する。
Readと同様にCheckは常に、指定されたzookieよりも前の一貫性のあるスナップショットで評価される

アプリケーションのコンテンツ変更を認可するために、クライアントは特別なCheckリクエスト、ContentChangeCheckを送ることができる。
ContentChangeCheckリクエストは、zookieが不要で最新のスナップショットで評価される。

ContentChangeCheckリクエストが許可された場合、レスポンスには、その後のコンテンツ・バージョンのチェックに使用するためのzookieが含まれる。
zookieのタイムスタンプは、新しいコンテンツを保護するACL更新のタイムスタンプより大きいので、zookieは評価スナップショットをエンコードし、ACL変更やコンテンツ変更に追従できる。

Expand

object#relationとオプションとしてzookieを指定すると、有効なusersetを返す。
Readとは異なり、Expandはユーザセットの書き換えルールで表現された間接参照に従う。
クライアントにとって、オブジェクトにアクセスできるユーザーとグループの完全な集合を推論することは非常に重要であり、これによりアクセス制御されたコンテンツの効率的な検索インデックスを構築することができます。

アーキテクチャと実装

Zanzibarアーキテクチャ図

クラスターで構成され、Check、Read、Expand、Writeリクエストに応答する。
リクエストはクラスター内のどのaclserverにも届き、そのaclserverは必要に応じてクラスター内の他のaclserverに仕事を割り振る。

ZanzibarはACLとそのメタデータをSpannerデータベースに格納する。

ネームスペースの設定を格納するデータベースが1つ
ネームスペースのリレーション・タプルを格納するデータベースが各クライアントごとに1つずつ
すべてのネームスペースで共有される変更ログ・データベースが1つある。

watchservers は Watch リクエストに応答する特殊なサーバーとなっている。
ウォッチサーバーは変更ログをテールし、ほぼリアルタイムでネームスペースの変更をクライアントに提供します。

Leopardはインデックス・システムであり、大規模で深くネストされた集合に対する操作を最適化するために使用される。
ACLデータのスナップショットを定期的に読み込み、スナップショット間の変更を監視する。
非正規化などのデータ変換を行い、ACLサーバからのリクエストに応答する。

Leopardインデックス

ACLの検証性能を向上させる仕組みとしてLeopard indexing systemがある
ZanzibarのACLの表現ではネストされたグループ表現が可能なため、多段にネストされたグループの検索や評価を低遅延に行うことが難しくなる

Leopard indexingでは，次の2つの種類の集合を定義する。

eはsの直接的または非直接的なサブグループの集合を表す。

1. GROUP2GROUP(s)−>{e}

eはsを直接的に含むグループの集合を表す。

2. MEMBER2GROUP(s)−>{e}

あるユーザUがグループGのメンバーとなるかは次の式で評価できる。

(MEMBER2GROUP(U) ∩ GROUP2GROUP(G))=∅

この問題はグループまたはユーザをノードとし、直接的なメンバー関係をエッジと表現したグラフを構築してグループからユーザへ到達するかを検証すればよく、実装上は上記2つの集合をスキップリストなどの順序付きリストが交差するかを検証することで計算量を各集合の要素数の最小値まで抑えることができる。

ホットスポットへの対処

ACLの読み取りとチェックのワークロードは、しばしば突発的でホットスポットが生じやすい。
例えば、検索クエリに答えるためには、すべての候補結果に対してACLのチェックを行う必要があり、これらのACLはしばしば共通のグループや間接的なACLを共有している。

共通のACL（例：人気のあるグループ）上のホットスポットが、基礎となるデータベースサーバを過負荷にする可能性がある。
低レイテンシと高可用性の追求において、ホットスポットの取り扱いが最も重要な要素である。

キャッシュの利用

ReadやCheckの評価結果、中間評価結果を分散キャッシュすることでこの問題を解決している
具体的には，ReadやCheck処理時に関連する別のサーバに通信して共有する
このとき、オブジェクトIDから生成する転送キーを付与して共有することで、頻繁にやりとりされる転送キーを検知して呼び出し元/呼び出し先にキャッシュすることで効率的にキャッシュすべき情報を選別している。

パフォーマンスの分離

パフォーマンスの分離は低レイテンシと高可用性をターゲットとする共有サービスには不可欠。
Zanzibarやそのクライアントの1つが予期せぬ利用パターンを処理するのに十分なリソースをプロビジョニングできない場合、以下の分離メカニズムによって、他のクライアントのパフォーマンスに悪影響を与えないようにします。

Zanzibarはハードウェアに依存しない指標である汎用cpu-secondsで各RPCのコストを測定します。
各クライアントには、1秒あたりの最大CPU使用量に関するグローバルな制限があり、その制限を超え、システム全体に余力がない場合、そのRPCの一定時間内に送信できるリクエスト数を制限する。

メモリ使用量を制御するために、未処理の RPC の総数も制限する。
同様にクライアントごとに未処理のRPCの数を制限する。

さらに、各Spannerサーバーに対して、クライアントごとの最大同時読み取り数を制限する
これにより、1つのオブジェクトやクライアントがSpannerサーバーを独占することはなくなる。

テールレイテンシーへの対策

SpannerとLeopardインデックスへのコールには、リクエストヘッジを利用している。
つまり同じリクエストを複数のサーバーに送り、最初に返ってきたレスポンスを使い、他のリクエストはキャンセルする。

ラウンドトリップタイムを短縮するために、Zanzibarサーバーがあるすべての地域に、これらのバックエンドサービスのレプリカを少なくとも2つ配置するようにしている。
不必要に負荷を増やさないために、まず1つのリクエストを送信し、最初のリクエストが遅いことがわかるまでヘッジリクエストの送信を延期する。

Googleの教訓

Zanzibarは、Googleカレンダー、Google Cloud、Googleドライブ、Googleマップ、Googleフォト、YouTubeなど、増加するクライアントの厳しい要求に対応するために進化してきた。
ここでは、その教訓をまとめている。

アクセス制御のパターンは広範にわたる

時間とともに、特定のクライアントをサポートするための機能を追加してきた。
例えば、DriveやPhotosのように多数のプライベートオブジェクトを管理するクライアントのスペース要件を削減するために、オブジェクトIDのプレフィックスからオブジェクトの所有者IDを推定するcomputed_usersetを追加した。
同様に、1つの関係タプルごとにオブジェクトの階層を表現するためのtuple_to_usersetを追加した。
このメリットは、スペースの削減と柔軟性の両方であり、CloudのようなクライアントがACL継承をコンパクトに表現し、大量のタプルを更新せずにACL継承ルールを変更することを可能にする。

認可情報の同期要件は緩やかだが、常に緩やかでいいというわけではない

クライアントはしばしばACL評価中の適度な陳腐化を許可するが、時々、最新の評価が必要とされる。
この特性を基にzookieプロトコルを設計し、大半のリクエストを既にレプリケーションされたデフォルトのスナップショットから提供できるようにし、必要に応じて陳腐化を制限することができるようにした。

リクエストのヘッジングは、テールレイテンシの削減の鍵となる

Driveのようにユーザーに検索機能を提供するクライアントは、1つの検索結果セットを提供するために、数十から数百の認可チェックをしばしば発行する。
私たちは、たまに遅い操作が全体のユーザーインタラクションを遅らせるのを防ぐために、SpannerとLeopardのリクエストのヘッジングを導入した。

ホットスポットの軽減は、高可用性のために不可欠となる

一部のワークロードは、ACLデータのホットスポットを作成し、下層のデータベースサーバーを圧倒することがある。

パフォーマンスの分離は、誤動作するクライアントから保護するために不可欠

ホットスポットの緩和策があっても、予期しない、または意図しないクライアントの振る舞いが私たちのシステムやその下層のインフラストラクチャを過負荷にする可能性がある。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up