🔒

Google認可システムZanzibar解剖メモ ~ Resistance is Futile! ~

に公開
Google
authorization
zanzibar
tech

はじめに

Googleの様々なサービスを支える認可基盤について調べたメモ。

Zanzibarという名前のこのシステムは、Calendar、Cloud、Drive、Maps、Photos、YouTubeなど多様なサービスの認可を一元的に処理している。世界規模で動いていて、数兆のアクセス制御リスト（ACL）を管理しつつ、毎秒数百万のリクエストをさばいている。しかも10ms未満の応答時間と99.999%以上の可用性を実現しているらしい。かなりすごい。

以降、論文「Zanzibar: Google’s Consistent, Global Authorization System」をもとにまとめる。

設計思想と目標

Zanzibarを作るときに設定された主な目標はこんな感じ。

設計目標 内容
正確性 ユーザーの意図通りにアクセス制御が動くように一貫性を確保する
柔軟性 一般ユーザー向けもビジネス向けも、様々なアクセス制御ポリシーに対応できるようにする
低レイテンシ ユーザー操作の途中で認可チェックが必要になることが多いから、とにかく速く応答する
高可用性 明示的に許可されていない場合はアクセス拒否になるので、システムが落ちると大変なことになる
大規模スケーラビリティ 数十億のユーザーが共有する数十億のオブジェクトを保護して、全世界で使えるようにする

認可を一箇所にまとめることで得られるメリットは多い。一貫した操作感を提供できるし、アプリ間の連携もしやすくなる。複数のアプリを横断して検索するときにアクセス制御を考慮できるし、難しい一貫性の問題を一度解決すればすべてのアプリで使い回せる。

データモデル

Zanzibarの核心となるのは「relation tuples（関係タプル）」というシンプルなデータ形式。

<tuple> ::= <object>'#'<relation>'@'<user>
<object> ::= <namespace>':'<object id>
<user> ::= <user id> | <userset>
<userset> ::= <object>'#'<relation>

この表記を使うと、こんな感じで権限を表現できる。

タプル例 意味
doc:readme#owner@10 ユーザー10がdoc:readmeのオーナー
group:eng#member@11 ユーザー11がgroup:engのメンバー
doc:readme#viewer@group:eng#member group:engのメンバーはdoc:readmeが見られる
doc:readme#parent@folder:A#... doc:readmeはfolder:Aに入っている

シンプルに見えるけど、これでACLとグループを統一的に扱えるようになっている。読み書きも増分更新も効率的にできる。

あと、ここで重要なのが<relation>の定義。これも単なる文字列でしかないけど、使う前に名前空間（後述）の設定で定義しておく必要がある。

例えば「viewer」「editor」「owner」「member」「parent」といった文字列で、これらは名前空間設定の中で前もって宣言しておく。単なる名前だけじゃなくて、その関係が他の関係とどう絡むかも設定できる（例：editorは自動的にviewerの権限も持つ、とか）。

relationは言ってみれば「この人とこのオブジェクトがどういう関係か」を表す述語みたいなもの。この単純な仕組みで、「Aさんはこの文書を編集できる」「Bグループのメンバーはこのフォルダを閲覧できる」といった多様なアクセス制御を表現できるようになる。うまく設計されてる

名前空間と関係の設定

Zanzibarを使う前に、クライアントは名前空間を設定する必要がある。名前空間設定では関係（relation）とストレージのパラメータを指定する。

特に面白いのが「userset rewrite rules」という機能。これを使うと、関係間の繋がりを定義できる。例えば「ドキュメントの編集者は自動的に閲覧者にもなる」みたいなルールを作れる。

簡単な名前空間設定の例を見てみよう。

name: "doc"                     # 「doc」という名前空間を定義

relation { name: "owner" }      # 「owner」という関係を定義。特別なルールなし

relation {
  name: "editor"                # 「editor」という関係の定義
  userset_rewrite {             # この関係の特別ルールを定義
    union {                     # 「または」の意味。どれかに当てはまれば「editor」になる
      child { _this {} }        # 直接「editor」として指定されたユーザー
      child {
        computed_userset {
          relation: "owner"     # 「owner」の人も自動的に「editor」になる
        }
      }
    }
  }
}

relation {
  name: "viewer"                # 「viewer」という関係の定義
  userset_rewrite {             # この関係の特別ルールを定義
    union {                     # 「または」の意味。どれかに当てはまれば「viewer」になる
      child { _this {} }        # 直接「viewer」として指定されたユーザー
      child {
        computed_userset {
          relation: "editor"    # 「editor」の人も自動的に「viewer」になる
        }
      }
      child {
        tuple_to_userset {      # 親フォルダの権限を継承する仕組み
          tupleset {
            relation: "parent"  # 「parent」関係を探す（親フォルダを意味する）
          }
          computed_userset {    # 見つかった親フォルダに対して
            object: $TUPLE_USERSET_OBJECT  # この親フォルダの
            relation: "viewer"  # 「viewer」権限を持つ人も、このドキュメントの「viewer」になる
          }
        }
      }
    }
  }
}

この設定だと、オーナーは勝手に編集者になるし、編集者は勝手に閲覧者になる。そして親フォルダの閲覧者はドキュメントも見られるようになる。階層的なアクセス制御がシンプルに表現できている。

一貫性モデルとZookieプロトコル

Zanzibarの重要な特徴として、一貫性モデルがある。特に「new enemy」問題への対策が重視されている。この問題は、ACLの更新順序を守らなかったり、古いACLを新しいコンテンツに適用すると発生する。

問題例 起こりうるシナリオ
ACL更新順序の無視 1. アリスがフォルダからボブを削除
2. アリスがチャーリーに新しいドキュメントをそのフォルダに移動するよう頼む
3. 更新順序を無視すると、ボブが新しいドキュメントを見れてしまう
古いACLの誤適用 1. アリスがドキュメントからボブを削除
2. アリスがチャーリーに新しい内容を追加するよう頼む
3. 古いACLで判断すると、ボブが新しい内容まで見れてしまう

この問題を解決するため、Zanzibarは「外部一貫性（external consistency）」と「鮮度に下限のあるスナップショット（bounded staleness）」という二つの特性を提供している。そして「zookie」と呼ばれるトークンを導入している。

zookieプロトコルの流れはこんな感じ。

  1. クライアントがコンテンツ変更前に「content-change ACL check」というリクエストを送る。このとき特別なzookieは必要ない。
  2. Zanzibarは現在のグローバルタイムスタンプをzookieにエンコードして返す。このタイムスタンプは、それまでのすべてのACL書き込みよりも新しいことが保証されている。
  3. クライアントはコンテンツ変更とzookieを一緒に自分のストレージにアトミックに保存。この保存処理とACLチェックは同じトランザクションである必要はない。
  4. 後で誰かがそのコンテンツにアクセスしようとするとき、クライアントはそのzookieを添えてACLチェックリクエストを送る。
  5. Zanzibarはzookieから取り出したタイムスタンプ「以上に新しい」スナップショットでチェックを実行。

これによって、ACLとコンテンツの更新間の順序関係を守りつつ、レイテンシと可用性の目標も達成できる柔軟性を確保している。

システムアーキテクチャ


https://storage.googleapis.com/gweb-research2023-media/pubtools/5068.pdf

Zanzibarのアーキテクチャは主にこんなコンポーネントで構成されている。

コンポーネント 役割
aclservers メインのサーバータイプで、Check、Read、Expand、Writeリクエストを処理する
watchservers Watchリクエストを処理する特殊なサーバータイプ
Spanner ACLとメタデータを保存するグローバルデータベースシステム
オフラインパイプライン 名前空間スナップショットの作成などのバックグラウンド処理を実行する
Leopard 大規模で深くネストされたセットの操作を最適化する索引システム

aclservers が処理のメインを担い、クライアントからのリクエスト（Check、Read、Expand、Write）を受け取る。このリクエストが到着すると、サーバーは必要な処理を他の aclservers に分散させる。例えば、あるグループメンバーシップをチェックするとき、そのグループが他のグループを含んでいる場合は、チェック処理が複数のサーバーに広がっていく（論文では「fan out」と表現している）。

データ自体はSpannerというグローバルデータベースに保存されていて、各relation tupleは (shard ID, object ID, relation, user, commit timestamp) という主キーで識別される。つまり、「誰が」「どのオブジェクトに対して」「どんな関係を」「いつ」持ったかが記録されている。
面白いのは、Zanzibarでは複数バージョンのタプルを異なる行に保存していること。これによって過去の任意の時点のスナップショットでACLチェックができる仕組みになっている。

ホットスポット（多くのリクエストが集中するデータ）対策として、サーバー間で分散キャッシュも使っている。これにより同じチェックが繰り返されても高速に処理できる。さらに、Leopardという索引システムもあり、深くネストされたグループなどの複雑な構造を効率的に処理している。

おおまかな処理の流れをシーケンス図にすると、下記のようになるだろうか（たぶん）。

データはこんな感じで保存される。

ストレージ 内容
名前空間データベース 各クライアント名前空間のrelation tuplesを保存
名前空間設定データベース すべての名前空間設定を保持
変更ログデータベース すべての名前空間の変更を記録

このデータは世界中の数十の地域に完全に複製され、数千のサーバーに分散されている。かなりのスケールだ。

パフォーマンス最適化

Zanzibarはいろんな技術を使って低レイテンシと高可用性を実現している。

最適化技術 中身
評価タイムスタンプ クライアントがzookieを提供しない場合、レイテンシに影響しない範囲で最新のスナップショットを選ぶ
設定一貫性 名前空間設定用に単一スナップショットタイムスタンプを選び、クラスタ内の全サーバーで同じタイムスタンプを使う
チェック評価 ACLチェックをブール式に変換して評価し、ポインタチェーシングで間接ACLやグループを再帰的に調べる
Leopard索引システム 深くネストされたグループメンバーシップを効率的に処理するための特殊な索引
ホットスポット対策 ・分散キャッシュとロックテーブル
・タイムスタンプ量子化でキャッシュ効率を上げる
・並列リクエストによるキャッシュスタンピード問題の防止
・人気オブジェクトのrelation tuplesを一括で読み取る
・ロックテーブルに待機者がいる場合はキャンセルを遅らせる
パフォーマンス分離 ・クライアントごとのCPU使用量上限
・サーバーごとの未処理RPC数の制限
・オブジェクトごと、クライアントごとの同時読み取り数の制限
・クライアントごとに異なるロックテーブルキー
テールレイテンシ緩和 ・SpannerとLeopardへのリクエストヘッジング
・動的に計算されるヘッジング遅延閾値
・地域ごとに複数のレプリカを配置

これらの最適化のおかげで、ホットスポットや遅延が起きそうな状況でも高いパフォーマンスを維持できている。

運用実績

Zanzibarは（参考にしている論文執筆時点で）5年以上本番環境で使われていて、クライアント数と負荷が着実に増えている。

規模の指標 数値
管理名前空間数 1,500以上
relation tuples数 2兆以上
データ容量 約100テラバイト
レプリケーション 世界30か所以上
処理クエリ数 毎秒1,000万以上
サーバー数 10,000以上

リクエストの種類によって特性も違う。

リクエスト種別 特徴
Safe リクエスト 10秒以上前のzookieを持ち、ほとんどの場合リージョン内で処理できる
Recent リクエスト 10秒未満のzookieを持ち、リージョン間のラウンドトリップが必要なことが多い

Check Safeリクエストのレイテンシを見ると、50%が約3ms、95%が約11ms、99%が約20ms、99.9%が約93msで処理されている。

可用性については、過去3年間で99.999%を超える値を維持している。かなり安定していると言える。

学んだ教訓

Zanzibarの開発・運用から得られた教訓として述べられていることを、次のようにまとめた。

教訓 詳細
柔軟性の重要性 ・クライアントによってアクセス制御パターンが全然違う
・computed_usersetやtuple_to_usersetなどの機能を追加して個別ニーズに対応
・鮮度要件は普段緩やかだけど、厳密さが必要な場合もある
パフォーマンス最適化の必要性 ・リクエストヘッジングがテールレイテンシの削減に効く
・ホットスポット緩和が高可用性のカギ
・パフォーマンス分離でクライアント間の影響を防ぐ

これらの教訓は大規模分散システムを作る上で普遍的な価値がある。

まとめ

Zanzibarは、Googleのサービス群を支える統一認可システムとして、正確性、柔軟性、低レイテンシ、高可用性、大規模スケーラビリティという厳しい要件を満たしている。シンプルなデータモデル、強力な設定言語、外部一貫性、効率的なグローバル分散などの特徴を組み合わせ、数兆のACLと毎秒数百万のリクエストを処理する能力を実現している。

We are Google. Resistance is Futile!
https://youtu.be/rtEaR1JU-ps

Discussion