秒間100万リクエストをさばく - Googleの共通認可基盤 Zanzibar

はじめに

Googleの提供するサービス郡が共通して利用している認可システムにはZanzibarという名前がついています。ZanzibarはGoogleDrive・Google Map・Youtubeなどの巨大なサービスにも使用されています。
そのため、利用量も凄まじく

数10億のユーザー
数兆のACL(access control list)
秒間100万リクエスト

もの量をさばいています。
にも関わらず、Zanzibarはこれを10ミリ秒以内に返します(95パーセンタイル)。

この記事では、そんなZanzibarの内部構造に関する論文「Zanzibar: Google’s Consistent, Global Authorization System」の中から、主に大量のリクエストをさばくための工夫を紹介します。

ちなみに、以前Googleの社内システム用の認可システム「Beyond Corp」について書きましたが、Beyond CorpがGoogleの社員の利用を想定して強固なセキュリティに重きを置いているのに対して、Zanzibarは世界中の人が使用しても耐えられるような柔軟性と速度を重点に設計されています。

Zanzibarとは

多くのサービスがそうであるように、Googleのサービスでも認可は必須です。GoogleはZanzibarという認可システムを自作しています。

そのZanzibarは、以下を目標にしています。

Correctness: ユーザーが意図したとおりのアクセス制御を実現する
Flexibility: toC, toBのサービス両方の要望を満たせる柔軟なアクセス制御
Low latency: 頻繁に利用されるので、素早く返したい
High availability: 認可が止まるとサービス提供ができなくなるので、止まるのは厳禁
Large scale: ユーザーは世界中に居るので、ユーザーの近くにシステムを置くために世界中に配置したい

アーキテクチャ

前章のZanzibarの目標を達成したアーキテクチャについて概説します。

f:id:mrasu:20190813213002g:plain

Zanzibarには３つの種類のデータを保持するストレージがあります。(上図の緑の円柱部分)

Relation Tuple Storage
オブジェクト(アクセス制限対象。GoogleDriveにあるファイルなど)とユーザーの関係を保持するストレージ。
バージョン管理も持っているので、少し昔のデータにもアクセスできます。
シャーディングされていて、シャーディングキーはクライアントが決めています。
Changelog
権限情報の変更をストリーミングするための履歴をもつストレージ。
権限管理のためにはリアルタイムで情報を更新する必要もあるので、その部分を担当している。ちなみに、Relation Tuple StorageとChangelogは同一のトランザクションで更新しています。
Namespace Config Storage
Namespace Configという、アプリケーションが事前に定義する権限設定を保持するストレージ。
開始時からの変更履歴を保持しています。

Zanzibarはこの３つのストレージが管理しているデータを使って、検索しています。
ちなみに、内部通信はRPCです。

Access Control List

Zanzibarは、RPCを通して権限を管理できます。
オブジェクトとユーザーの関係の宣言の仕方は、

オブジェクトとユーザーの関係を直接書く
グループを定義して、そのグループとオブジェクトの関係を書く

の２通りが出来ます。例えば、

doc:readme#owner@10  
group:eng#member@11  
doc:readme#viewer@group:eng#member

という書き方で、「readmeというファイルをid10のユーザーが所有している」、「11はengグループのメンバー」、「readmeはengグループのメンバーは閲覧可能」という関係をZanzibarに伝えることが出来ます。

高速化のために

ZanzibarはGoogleが提供するあらゆるサービスの認可基盤になることを想定しているので、速度と安定性はとても重要です。高速化のためにZanzibarが行っている工夫を紹介します。

Leopard Indexing System

ZanzibarにはLeopard Indexing Systemという、オブジェクトやグループの関係を高速に検索するためのインデックスが存在します。

Zanzibarは前章のACLを使って「グループに所属している人」も「グループ(親)に所属するグループ(子)」という関係も定義できます。すると、あるグループに多くの子グループが存在したり、グループのネストが深くなったりした場合に検索が大変です。
それを解消するために、Leopardはグループの関係をフラットにして

Group2Group: あるグループの子孫のグループ
Member2Group: あるユーザーが直接所属しているグループ (所属グループの親グループは含まない)

の２種類のグループの集合を保持しています。
更に、スキップリストのような順序付きリスト(ordered list)でグループを管理しているので、集合A・Bの和や交叉を O(min(|A|, |B|)) で計算できます。

すると、例えば

Member2Group(U) ∩ Group2Group(G)

の関係が空集合かどうかをLeopardで調べることで、「ユーザーUがグループGに所属しているか」を上記の計算量で答えられます。
Leopardのおかげで、Zanzibarが高速に権限チェックができるということです。

Zanzibarはデータを非正規化をせずに(Leopardは例外)、代わりにキャッシュを使って対処しています。
例えば、権限チェックや参照のリクエストの結果は中間結果も含めてキャッシュされ分散されています。
また、cache stampede対策として、各サーバーは「lock table」を使って、同じリクエストが同時に複数実行されそうな場合に、リクエストを１つしか実行しないよう調整しています。
他にも、よく参照されるオブジェクトの結果を事前に読み込んでおくという工夫もあります。

パフォーマンスの分離

重いリクエストの影響でシステム全体が遅くなることも避ける必要があります。

Zanzibarでは、あるリクエストが他のリクエストに影響を与えないように、

各RPCが使用しているCPUを監視し、システム全体として余裕がない場合には閾値を超えたRPCに調整が入る
クライアントとサーバーそれぞれに、RPCの同時送信・受信数の制限がある
Spannerのために、クライアントとクライアントが参照するオブジェクト毎のアクセス制限がある
クライアント毎に別のキーをlock tableに使って、Spannerのthrottlingの影響を他のクライアントが受けないようにする

という工夫をしています。

Reqeust hedging

その他にも障害に備えて、SpannerとLeopardを使う時には同一リクエストを２つのサーバーに送信して障害や遅延に備えています。そして、どちらかのリクエストが返ってきたらもう一方をキャンセルするのです(request hedging)。ただし、同時に２つリクエストを出すのではなく、最初に１つリクエストを出して「遅い」と判断された時にもう一つのリクエストが追加で出されます