🐡

Googleの認可基盤Zanzibarを読んだメモ

2022/09/04に公開

はじめに

ZanzibarはGoogleの研究者が中心となって提案した大規模認可基盤です．アクセスコントロールリスト(ACL)の保存や評価をグローバルなシステム規模で行うための基盤であり，本論文ではACLのデータモデルや設定言語も提案しています．Googleの各種サービス(Google Calendar, Cloud, Drive, Maps, Photos, YouTube)などで利用されているらしく，グローバルスケールの認可基盤がこの論文で提案されたモデルにもとづいて作られています．

どんな問題を解決したいのか

様々なアプリケーションにまたがる統一の認可基盤を作るメリットとして，アプリケーション間にまだがる認可の意味を一致させて一貫性のあるユーザエクスペリエンスを保ち相互運用性を高めることが挙げられています．また，前述したようにGoogleが全世界に展開する様々なアプリケーションで共通的に利用されるため，Zanzibarに求められる認可基盤特有の要件として以下の5点をあげています．

正確性
ユーザの意図に即した一貫した認可制御判断．
柔軟性
コンシューマ向け，企業向けどちらの要求にも対応できる柔軟なアクセス制御ポリシー．
低遅延
ユーザーインタラクションを妨げない素早い応答．
Zanzibarでは95%の要求を10ms以内に応答できているようです．
高可用性
認可基盤が落ちるとクライアントサービスで認可判断ができないため高い可用性．
Zanzibarでは3年間で稼働率99.999%を達成しています．
高スケーラビリティ
世界中のユーザに利用され，利用者の近くにデプロイするためのスケール性．

認可情報のモデル

柔軟な認可情報を表現するため，ZanzibarにおけるACLの概念は次のような関係タプルとして表します．

\langle tuple \rangle \Coloneqq \langle object \rangle \# \langle relation \rangle @ \langle user \rangle

このとき， $\langle object \rangle$ は次のように表されます．

\langle object \rangle \Coloneqq \langle namespace \rangle:\langle object\_id \rangle

例えば，文書A(doc:A)の管理者権限(owner)をTaroさんがもっているとすると，次のように表されます．

doc:A#owner@Taro

また， $\langle user \rangle$ の表現は単純なユーザIDだけでなく，ユーザセットと呼ばれる次のような表現も可能です．

\langle userset \rangle \Coloneqq \langle object \rangle \# \langle relation \rangle

ユーザセットを利用したACLとして，例えば文書Aの閲覧権限をエンジニアグループ(group:eng)のメンバー（花子）が持っているという表現は次のようにできます．

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

一貫性の問題への対処

分散システムとして構成されているZanzibarはACLがアップデートされたのちに古いACLを読み込むことによるポリシーの不整合を防ぐために，zookieと呼ばれるタイムスタンプを利用します．例えば，次のような例を考えます．

アリスがボブの文書に関する権限を剥奪する．
アリスがチャーリーに文書の改訂を依頼する．
もしボブにフォルダ権限が残っている古いACLが参照されると，ボブは改訂された文書を見れる可能性がある．

上記のそれぞれのタイミングのタイムスタンプを $T_1$ , $T_2$ , $T_3$ とし，$　T_1 < T_2 < T3$とします．例えばClientがZanzibarにACLの検証を問い合わせた時，zookieのタイムスタンプ $T$ が $T \leq T2$ であれば，ドキュメントが変更される前に検証された古い結果の可能性があります．したがって， $T > T_2$ の評価結果であることを確認すれば， $T_1 < T_2$ より，ボブが文書権限を剥奪されたのちのACLの評価結果であることが保証されます．このように，zookieを利用することによってZanzibarのACLの一貫性を保っています．

性能向上のための仕組み

前述した高可用，低遅延，高スケーラブルな性能を達成するため，Zanzibarでは色々な工夫がされています．本論文で挙げられている性能向上の仕組みとしてインデックス，ホットスポットの制御，クライアントごとの性能制限，テールレイテンシの緩和があります．

インデックス

ACLの検証性能を向上させる仕組みとしてLeopard indexing systemがあります．ZanzibarのACLの表現ではネストされたグループ表現が可能なため，多段にネストされたグループの検索や評価を低遅延に行うことが難しくなります．Leopard indexingでは，次の2つの種類の集合を定義します．

$GROUP2GROUP(s) -> \{e\}$ ]
$e$ は $s$ の直接的または非直接的なサブグループの集合を表します．
$MEMBER2GROUP(s) -> \{e\}$
　　　　　　 $e$ は $s$ を直接的に含むグループの集合を表します．
あるユーザ $U$ がグループ $G$ のメンバーとなるかは次の式で評価できます．

(MEMBER2GROUP(U) \cap GROUP2GROUP(G)) \neq \emptyset

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

ホットスポットの制御

ZanzibarがもつACLは前述したようにグループや他のACLなどに依存しており，しばしば共通的に利用されるグループと関係をもちます．こうした共通のグループは頻繁に参照されるホットスポットとなり，データベースの性能ボトルネックの原因となってしまいます． ZanziberのサーバクラスターではACLや評価結果，中間評価結果を分散キャッシュすることでこの問題を解決しています．具体的には，検証や読み込み処理時に関連する別のサーバに通信して共有します．このとき，オブジェクトIDから生成する転送キーを付与して共有することで．頻繁にやりとりされる転送キーを検知して呼び出し元/呼び出し先にキャッシュすることで効率的にキャッシュすべき情報を選別しています．

クライアントごとの性能制限

Zanzibarは各クライアントに払い出す資源を次のように制限することで，一部のクライアントの過剰な要求が全体の性能に影響を及ぼさないようにしています．

リクエスト時のCPU使用率を計測してクライアントごとに最大CPU使用率を制限
クライアントごとに未処理リクエスト数を制限
クライアントごとにSpannerからの同時読み込み数を制限

テールレイテンシの緩和

大規模なサーバにおいては，テールレイテンシと呼ばれる低確率で発生する大きなアクセス遅延の影響が大きくなってしまうため緩和する必要があることが知られています[Dean13]．
テールレイテンシの緩和のために，認可情報を持つSpannerやLeopard indexへのアクセス時に複数のサーバに同時にリクエストを投げておき最初に返ってきたもの以外をキャンセルするリクエストヘッジと呼ばれる手法を使っています．一方で，単純にリクエストを複数送信するのはサーバの処理負荷の増大につながるため，最初のリクエストの応答時間を監視して，ある閾値を超えたらリクエストヘッジをかける工夫を施しています．また，地域ごとに最低2つのレプリカを配置することで各リクエストのラウンドトリップ時間削減を図っています．

おわりに

Zanzibarが設定している解決すべき課題の大半は大規模システムに対応する認可基盤ならではのものですが，様々なサービスが使うことを前提とした柔軟な認可情報モデルも面白いです．認可周りはシステムやサービスの成長とともに複雑化する部分のためよく悩むところなので参考になるなと思いながら読んでいました．SpiceDBと呼ばれるOSSがこの論文をベースに作られているようなので，試しに使ってみようと思います．